前言
前面我们学习过map、set、multimap、multiset的使用，这四种容器都是使用红黑树作为其底层结构。红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O(
)，但是红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对AVL树而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。
今天我们就可以利用之前实现过的红黑树来对C STL库中的set和map进行模拟实现。
1. 修改红黑树
我们之前模拟实现过红黑树，插入的节点是键值对pair类型，而如果要使用红黑树来对set和map封装的话，set存储的应该是单个值，而不是键值对，所以我们就需要对红黑树进行修改，使得set和map都能使用：
- 首先红黑树存储节点的类需要从只能存储键值对改为能够存储任意数据：
template<class T>
struct RBTreeNode
{
T _data; //存放数据，不再只能存放键值对：pair<K, V> _kv;
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
Colour _col; //保存颜色
RBTreeNode(const T& data)
:_data(data)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _col(RED)
{}
};- 相应的，红黑树的模板参数也需要修改：
修改前：
代码语言：javascript复制//红黑树类
template<class K, class V>
class RBTree
{
public:
typedef RBTreeNode<K, V> Node;
Node* Find(const K& key);//查找函数
private:
Node* _pHead = nullptr;
};因为节点类只有一个模板参数了，所以红黑树两个模板参数有点多余，但是如果将红黑树的模板参数也改为一个，如下面代码所示：
代码语言：javascript复制//红黑树类
template<class T>
class RBTree
{
public:
typedef RBTreeNode<T> Node;
Node* Find(const T& key);//？查找函数
private:
Node* _pHead = nullptr;
};那么在实现查找上面代码中的Find函数时，对于map查找时Find函数参数就得传一个完整的键值对，我们不可能把完整的键值对全部传过去查找，这样查找就没有意义，我们只需要获得键值对的键查找到相应的键值对即可，所以我们还应该传一个模板参数：
代码语言：javascript复制template<class K, class T>//K存储键，T存储键值对
class RBTree
{
public:
typedef RBTreeNode<T> Node;//传入键值对
Node* Find(const K& key);//查找函数，只传键
private:
Node* _pHead = nullptr;
};这样对于不同函数的需求就可以传入不同的模板参数了
