在stl中map,set内部都是使用相同的红黑树实现，map对应模板参数key_type,mapped_type,而set对应模板参数没有mapped_type
两者都支持insert操作
pair<iterator, bool> insert(const value_type& value);
对于map
typedef pair<key_type, mapped_type> value_type;
对于set
typdef key_type value_type;
那么在扩展库pb_ds中(代码在ext/pb_ds)
是这样设计的，比如trie
trie<string, int> 表示key是string,mapped 是int
trie<string, null_type> 表示key是string 没有mapped 类似一个TrieSet的概念。
那么是怎样做到这些的呢，比如自己写一个trie的结构，如何更好的避免TrieMap,TrieSet的实现代码重复，同时能提供两种实现(TrieSet没有mapped占用更少空间)。
除了模板类常用的技巧traits和tag forward之外，这里用到了#define #endef的技巧，先看下folly的一个
关于FBVector的test。
在test的.h中
TESTFUN(clause_23_3_6_1_1) {
VECTOR v;
EXPECT_TRUE(v.empty());
VECTOR::allocator_type a;
VECTOR v1(a);
EXPECT_TRUE(v1.empty());
}
在test的cpp中
typedef vector<int> IntVector;
typedef fbvector<int> IntFBVector;
typedef vector<folly::fbstring> FBStringVector;
typedef fbvector<folly::fbstring> FBStringFBVector
#define VECTOR IntVector
#include <folly/test/FBVectorTestBenchmarks.cpp.h> // nolint
#undef VECTOR
#define VECTOR IntFBVector
#include <folly/test/FBVectorTestBenchmarks.cpp.h> // nolint
#undef VECTOR
#define VECTOR FBStringVector
#include <folly/test/FBVectorTestBenchmarks.cpp.h> // nolint
#undef VECTOR
#define VECTOR FBStringFBVector
#include <folly/test/FBVectorTestBenchmarks.cpp.h> // nolint
#undef VECTOR
pb_ds也是类似的方法
#define PB_DS_DATA_TRUE_INDICATOR
#define PB_DS_V2F(X) (X).first
#include <ext/pb_ds/detail/pat_trie_/pat_trie_.hpp>
#undef PB_DS_DATA_TRUE_INDICATOR
#undef PB_DS_V2F
#define PB_DS_DATA_FALSE_INDICATOR
#define PB_DS_V2F(X) (X)
#include <ext/pb_ds/detail/pat_trie_/pat_trie_.hpp>
#undef PB_DS_DATA_FALSE_INDICATOR
#undef PB_DS_V2F
这里看下pat_trie_.hpp
#ifdef PB_DS_DATA_TRUE_INDICATOR
#define PB_DS_PAT_TRIE_NAME pat_trie_map
#endif
#ifdef PB_DS_DATA_FALSE_INDICATOR
#define PB_DS_PAT_TRIE_NAME pat_trie_set
#endif
template<typename Key, typename Mapped, typename Node_And_It_Traits,
typename _Alloc>
class PB_DS_PAT_TRIE_NAME :
也就是其实两次#include pat_trie_.hpp分别定义了
pat_trie_map和pat_trie_set
看看class PB_DS_PAT_TRIE_NAME内部
inline std::pair<point_iterator, bool>
insert(const_reference);
inline mapped_reference
operator[](key_const_reference r_key)
{
#ifdef PB_DS_DATA_TRUE_INDICATOR
return insert(std::make_pair(r_key, mapped_type())).first->second;
#else
insert(r_key);
return traits_base::s_null_type;
#endif
}
看下这个insert的实现
pat_trie_/insert_join_fn_imps.hpp
PB_DS_CLASS_T_DEC
inline std::pair<typename PB_DS_CLASS_C_DEC::iterator, bool>
PB_DS_CLASS_C_DEC::
insert(const_reference r_val)
{
node_pointer p_lf = find_imp(PB_DS_V2F(r_val));
if (p_lf != 0 && p_lf->m_type == leaf_node &&
synth_access_traits::equal_keys(PB_DS_V2F(static_cast<leaf_pointer>(p_lf)->value()), PB_DS_V2F(r_val)))
{
PB_DS_CHECK_KEY_EXISTS(PB_DS_V2F(r_val))
PB_DS_ASSERT_VALID((*this))
return std::make_pair(iterator(p_lf), false);
}
PB_DS_CHECK_KEY_DOES_NOT_EXIST(PB_DS_V2F(r_val))
leaf_pointer p_new_lf = s_leaf_allocator.allocate(1);
cond_dealtor cond(p_new_lf);
new (p_new_lf) leaf(r_val);
apply_update(p_new_lf, (node_update*)this);
cond.set_call_destructor();
branch_bag bag;
bag.add_branch();
m_p_head->m_p_parent = rec_join(m_p_head->m_p_parent, p_new_lf, 0, bag);
m_p_head->m_p_parent->m_p_parent = m_p_head;
cond.set_no_action_dtor();
++m_size;
update_min_max_for_inserted_leaf(p_new_lf);
_GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(r_val));)
PB_DS_ASSERT_VALID((*this))
return std::make_pair(point_iterator(p_new_lf), true);
}
OK，就是这么个意思了。。 map里面使用的时候PB_DS_V2F是 x.first 而set里面使用PB_DS_V2F就是x本身。