C++ set 和 map 的封装实现原理

一、框架搭建

set 和 map 的底层都是红黑树，但由于存储元素的差异（一个只存储 key，一个既存储 key 又 value），库里面采用了改变红黑树结构的方式使其完美匹配。

1. 分析库中 set 与 map 的实现

RBTree 的实现一共有 5 个模板参数，分别是 Key, Value, KeyOfValue, Compare 和 Alloc。Compare 是控制比较规则的仿函数类型，Alloc 是内存池。

1. 对于 set，它只有一个用来接收 key 类型的模板参数 Key，并把 Key 同一个类型命名为 key_type 与 value_type。
2. 对于 map，它有两个分别用来接收 key 和 value 类型的模板参数 Key 和 T。将 Key 重命名为 key_type，将 pair<const Key, T> 重命名为 value_type。
3. 它们复用同一棵红黑树，将 4 个类型传给红黑树。

重点观察 Value 这个模板参数，它的类型是节点所存储的元素的类型。set 传过来的是 Key 类型，map 传过来的是 pair<const Key, T> 类型。利用模板来控制红黑树所存储的类型，满足 set 和 map 不同的存储需求。

我们传递给 map 的只是 key 和 value 的类型，而 map 要存储的是 pair<const key, value> 类型（实现 key 和 value 的绑定，const 实现不可修改以后再加），所以我们需要做一个加工。 既然有了接收存储元素类型的 Value 类型，而为什么不删除第一个用来单独存储 key 类型的模板参数 Key，似乎用不上它，这个以后就能知道了。

2. 分析第三个模板参数 KeyOfValue

我们在进行插入时，需要根据 key 的大小来找到插入的位置，而由于 set 和 map 存储类型的不同，set 直接用 Value（key）类型的元素就好，而 map 则需要取出 Value(pair<const key, value>) 里面的 key 值来找到插入的位置。

KeyOfValue 这个模板参数就是用来接收功能为取出 key 的仿函数类型，KeyOfValue 是匿名对象。

1. set 里面传给 KeyOfValue 的是一个 identity<value_type> 类型的仿函数，identity 在这里是本身的意思，它的功能就是取出 key 值就是 value_type 类型的元素它本身。
2. map 里面传给 KeyOfValue 的是一个 select1st<value_type> 类型的仿函数，它的功能就是取出 key 值就是 value_type 类型元素里的第一个值。

所以我们在 set 和 map 里面的实现里面都要实现一个仿函数用来传递给 KeyOfValue。

set:

namespace mosheng {
    template<class K>
    class identity {
    public:
        K& operator()(const K& key) { return key; }
    };
    template<class Key>
    class set {
        typedef RBTree<Key, Key, identity<Key>> rbType;
    };
}

map:

namespace mosheng {
    template< ,  >
      {
    :
        {  kv.first; }
    };
    < ,  >
      {
         RBTree<Key, std::pair<Key, Value>, select1st<Key, std::pair<Key, Value>>> rbType;
    };
}