零、前言
本章是继红黑树的介绍和实现后，讲解使用红黑树来封装实现map和set
一、红黑树及其节点的设计
对于底层都是红黑树的map和set来说，他们之间存在的最大的区别就是：对于set是K模型的容器，而map是KV模型的容器。为了更好的灵活兼容实现map和set，就需要在红黑树以及树节点上进行特别的设计
1、树节点的设计
对于红黑树的节点我们需要节点对于set来说储存key，对于map来说储存key-value键值对，所以这里我们就直接让节点类型的阈值类型为T，用来控制储存类型
实现代码：
template<class T> struct RBTreeNode { RBTreeNode<T>* _left; RBTreeNode<T>* _right; RBTreeNode<T>* _parent; T _data;//T可以是key也可以是pair<K,V> Colour _col; RBTreeNode(const T& data) :_left(nullptr) , _right(nullptr) , _parent(nullptr) , _data(data) , _col(RED) {} };
- 解释：
对于set实现我们传入key，对于map实现我们传入pair<key,value>，由此满足set和map各自的需求
2、红黑树的设计
想要兼容map和set，我们依旧需要红黑树的模板有两个类型来控制和满足上层对下层的需求
- 实现代码：
template<class K, class T> class RBTree { typedef RBTreeNode<T> Node; public: //....... private: Node* _root; };
注：这里的Node我们不想让外部直接获取使用，我们typedef在private域中
解释：
为了兼容set和map，对于第一个参数我们是用来比较的key类型，第二个参数是用来储存数据的类型
这里我们对红黑树第二个模板参数进行灵活传参，可能是键值key，也可能是pair<key,value>
对于set传入底层红黑树的模板参数就是key和key；对于map传入底层红黑树的模板参数就是key和pair<key,value>
注：对于set来说第二个参数有点多余，但是对于map来说，因为map的接口当中有些是只要求给出键值key用来比较的（如find()和erase()）,如果只有一个参数传入pair<key,value>类型，但是只能得到第一个key类型的值，无法获得key的类型（不能实现模板函数）
3、取值仿函数的使用
我们在设计树节点之后达到了对于不同容器存入不同类型的效果，但是真实在实现时在插入或者删除时，我们需要要拿出节点中储存类型的数据进行比较
分析：
对于set的T本身就是键值key，直接用T进行比较即可，但是对于map的储存类型是pair<Key, Value>我们需要取出pair的first（key值）进行比较
这两种的都是取值比较，但是需要的行为是不一样的，由此我们还需要一个仿函数用来灵活取值比较
对于不同容器我们需要不同的仿函数类型，由此在红黑树的模板列表中还需要一个模板类型参数，灵活控制传入的仿函数类型
注：仿函数，就是使一个类的使用看上去像一个函数，其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了
红黑树框架：
template<class K, class T, class KeyOfT> class RBTree { typedef RBTreeNode<T> Node; public: //... private: Node* _root; };
- map实现框架：
namespace cole { template<class K, class V> class map { struct MapOfKey { const K& operator()(const pair<K, V>& kv) { return kv.first; } }; public: //... private: RBTree<K, pair<const K, V>, MapOfKey> _t; }; }
- set实现框架：
namespace cole { template<class K> class set { struct SetOfKey { const K& operator()(const K& key) { return key; } }; public: //... private: RBTree<K, K, SetOfKey> _t; }; }
- 仿函数使用示例：
Node* Find(const K& key) { KeyOfT kot; Node* cur = _root; while (cur) { if (kot(cur->_kv.first) > key) { cur = cur->_left; } else if (kot(cur->_kv.first) < key) { cur = cur->_right; } else { return cur; } } return nullptr; }
