概述
本文模仿SGI STL对红黑树进行封装，以实现简单的 set 和 map。本文的目的不是造一个更好的轮子，而是加深对C++封装与泛型技法的体会与理解。阅读本文之前，建议先对红黑树进行学习。本文是以rb_tree的实现为基础的，建议与关联式数据结构_红黑树剖析 #C++进行结合阅读。
map
因为map的实现更具代表性，所以先对map进行讨论。
map的所有元素都会根据的元素的键值自动被“排序”，通过对红黑树的了解，这种“排序”其实是通过对二叉搜索树的中序遍历体现的。map的所有元素类型都是pair，pair的第一个成员为键值(Key)，第二个成员为实值(Value)，map不允许两个元素具有相同的键值。
MapKeyOfT
由于在rb_tree层面，实际的数据类型都被视为模板参数 T，所以对于map来说，key的拿取变得困难。仿函数MapKeyOfT的设计便是是为了取出map元素的键值，即pair的第一个成员，以便于根据键值维系红黑树的结构。
struct MapKeyOfT
{
const Key& operator()(const std::pair<const Key, Value>& kv)
{
return kv.first; //返回pair的第一个成员
}
};在rb_tree层面，MapKeyOfT被视为模板参数KeyOfT，以同时兼容map和set，而不必关心rb_tree的具体使用者及具体函数的内部实现细节。
迭代器
对于map，可以通过迭代器修改元素的Value，但不允许通过迭代器修改元素的Key，这是因为任意修改Key会破坏底层红黑树的组织。map的迭代器直接对rb_tree进行复用即可。
public:
typedef typename RB_tree<Key, std::pair<const Key, Value>, MapKeyOfT>::iterator iterator;
typedef typename RB_tree<Key, std::pair<const Key, Value>, MapKeyOfT>::const_iterator const_iterator;
public:
iterator begin()
{
return _tree.begin();
}
iterator end()
{
return _tree.end();
}
const_iterator begin() const
{
return _tree.begin();
}
const_iterator end() const
{
return _tree.end();
}在对map进行插入操作时，不存在迭代器失效问题；进行删除操作(这里没有实现)时，被删除的元素迭代器失效。
insert接口
map的insert接口直接对rb_tree进行复用。
std::pair<iterator, bool> insert(const std::pair<Key, Value>& kv)
{
return _tree.insert(kv);
}operator[]
operator[] 是map独有的一个接口，可以支持用户通过Key方便地对其Value进行修改。operator[]的底层本质是对红黑树insert接口的复用，通过insert的返回值拿到对应元素的迭代器，并通过迭代器拿到元素的Value并返回。
Value& operator[](const Key& key)
{
std::pair<iterator, bool> ret = _tree.insert(std::make_pair(key, Value()));
return ret.first->second; //通过迭代器返回元素的Value引用
}
const Value& operator[](const Key& key) const
{
std::pair<iterator, bool> ret = _tree.insert(std::make_pair(key, Value()));
return ret.first->second; //通过迭代器返回元素的Value的const引用
}set
和map一样，set中的所有元素都会根据元素的键值被自动排序。set的元素不像map那样同时拥有Key和Value，可以认为，set的Key就是Value，Value就是Key，set不允许两个元素具有相同的键值。
SetKeyOfT
对于set的KeyOfT仿函数，只需要直接返回元素的Key值即可。set的KeyOfT的设计目的完全是为了迁就map，以进行兼容。
struct SetKeyOfT
{
const Key& operator()(const Key& key)
{
return key;
}
};迭代器
不能通过set的迭代器修改set的键值，因为如果任意修改元素的键值，会破坏底层红黑树的结构。为了杜绝写入操作，可以直接将rb_tree的const迭代器作为set的迭代器，即set的迭代器是一种const iterators。
public:
//set的普通迭代器和const迭代器都是红黑树的const迭代器
typedef typename shr::RB_tree<Key, Key, SetKeyOfT>::const_iterator iterator;
typedef typename shr::RB_tree<Key, Key, SetKeyOfT>::const_iterator const_iterator;
public:
iterator begin() const
{
return _tree.begin();
}
iterator end() const
{
return _tree.end();
}insert接口
set的insert接口不能对rb_tree直接复用，这是因为存在返回值类型不一致的问题。正如上文所说，set的普通迭代器和const迭代器其实都是rb_tree的const迭代器，在set层面，insert的返回值本质是pair<typename RB_tree<Key, Key, SetKeyOfT>::const_iterator, bool>，而rb_tree的返回值类型是pair<typename RB_tree<Key, Key, SetKeyOfT>::iterator, bool>，两个pair对象的类型不同，直接复用会发生报错。
解决方法是，在rb_tree的迭代器中增加一个构造函数：
template<typename T, typename Ref, typename Ptr>
class __RB_tree_iterator
{
private:
typedef __RB_tree_iterator<T, T&, T*> iterator;
public:
__RB_tree_iterator(const iterator& it)
:_node(it._node)
{ }
/*…………*/
}如果__RB_tree_iterator类是一个普通迭代器，则该构造函数是一个拷贝构造；如果__RB_tree_iterator类是一个const迭代器，则该构造函数是一个普通构造。
完成这个特殊的构造函数之后，就可以在set的insert接口中，将rb_tree的insert接口的返回值做一层转换，即可顺利返回。这其实是一种用普通迭代器构造const迭代器的行为。
std::pair<iterator, bool> insert(const Key& k)
{
//先接收rb_tree的返回值
std::pair<typename RB_tree<Key, Key, SetKeyOfT>::iterator, bool> p = _tree.insert(k);
//用普通迭代器构造const迭代器
return std::pair<iterator, bool>(p.first, p.second);
}总结
对红黑树的实现、以及本文对红黑树的封装均与SGI STL的源码有些不同，是对SGI STL的简化版，但大体结构是类似的。正如开头所说，本文的目的不是造一个更好的轮子，而是学习泛型技法的内涵与STL的学理。
一如侯捷老师所说，“参观飞机工厂不能让你学得流体力学，也不能让你学会开飞机。但如果你既会开飞机又懂流体力学，参观飞机工厂可以给你带来最大的乐趣和价值”。
