1.前置知识
在之前的文章中，我们模拟实现了红黑树的插入。STL种的map和set底层都是红黑树，所以今天我们要做的事情就是利用我们之前模拟实现的红黑树来简化的封装一个map和set
首先，我们把之前的红黑树代码中用于检测的部分剔除掉，下面是剔除之后的代码：
#include <iostream> enum Color { RED, BLACK }; template<class K, class V> struct RBTreeNode { pair<K,V> _kv; RBTreeNode* _left; RBTreeNode* _right; RBTreeNode* _parent; Color _col; RBTreeNode(const pair<K,V> kv) :_kv(kv) ,_left(nullptr) ,_right(nullptr) ,_parent(nullptr) ,_col(RED) {} }; template<class K, class V> class RBTree { typedef RBTreeNode<K, V> Node; public: bool Insert(const pair<K,V>& kv) { if(_root == nullptr) { _root = new Node(kv); _root->_col = BLACK; return true; } Node* cur = _root; Node* parent = nullptr; while(cur) { if(cur->_kv.first < kv.first) { parent = cur; cur = cur->_right; } else if(cur->_kv.first < kv.first) { parent = cur; cur = cur->_left; } else { return false; } } cur = new Node(kv); cur->_col = RED; cur->_parent = parent; if(parent->_kv.first > cur->_kv.first) { parent->_left = cur; } else { parent->_right = cur; } while(parent && cur->_parent->_col == RED) { Node* grandfather = parent->_parent; if(parent == grandfather->_left) { Node* uncle = grandfather->_right; if(uncle && uncle->_col == RED) { grandfather->_col = RED; uncle->_col = parent->_col = BLACK; cur = grandfather; parent = cur->_parent; } else { if(parent->_left == cur) { RotateR(grandfather); grandfather->_col = RED; parent->_col = BLACK; } else { RotateL(parent); RotateR(grandfather); cur->_col = BLACK; grandfather->_col = RED; } break; } } else { Node* uncle = grandfather->_left; if(uncle && uncle->_col == RED) { parent->_col = uncle->_col = BLACK; grandfather->_col = RED; cur = grandfather; parent = cur->_parent; } else { if(parent->_right == cur) { RotateL(grandfather); grandfather->_col = RED; parent->_col = BLACK; } else { RotateR(parent); RotateL(grandfather); grandfather->_col = RED; cur->_col = BLACK; } break; } } } _root->_col = BLACK; return true; } void RotateL(Node* parent)//左单旋 { Node* subR = parent->_right; Node* subRL = subR->_left; Node* ppNode = parent->_parent; parent->_right = subRL; if(subRL) subRL->_parent = parent; subR->_left = parent; parent->_parent = subR; if(ppNode) { subR->_parent = ppNode; if(ppNode->_left == parent) { ppNode->_left = subR; } else//paren { ppNode->_right = subR; } } else { _root = subR; subR->_parent = nullptr; } } void RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; Node* ppNode = parent->_parent; if(subLR) subLR->_parent = parent; parent->_left = subLR; subL->_right = parent; parent->_parent = subL; if(ppNode) { subL->_parent = ppNode; if(ppNode->_left == parent) ppNode->_left = subL; else ppNode->_right = subL; } else { _root = subL; subL->_parent = nullptr; } } private: Node* _root = nullptr; };
我们要做的就是在此基础上改写部分代码，封装出map和set。
2.结构的改写与封装
现在直接让我们来封装肯定是一头雾水，所以首先我们来看一下STL源码是怎么实现的(这里参考的是SGI版本的stl3.0，与侯捷老师的STL源码剖析相对应)
这里简化一下源码，方便观看，去除掉一些不必要的东西
set的简化源码：
map的简化源码：
所以，map和set在底层上都是同一个红黑树，只是传入的第二个参数不同，set传入的第二个参数只是Key，而map传入的是一个键值对。
所以，这里对RBTree的模板做一下修改，变成template class RBTree,这里的第二个参数类型就是分辨map和set的依据。
2.1 map和set的结构框架
所以对于map和set来说，其类的结构如下
//set传入Key和Key template<class K> class set { public: //... private: RBTree<K,K> _t; }; //map传入Key和pair template<class K, class V> class map { public: //.... private: RBTree<K, pair<const K, V>> _t; };
那么这里出现一个问题：既然通过第二个参数就已经能够区分了，为什么还要传第一个参数？
✅对于insert来说，确实不需要第一个参数，插入的值是Key或者pair即可，但是对于find函数，通过传入的参数找到值得时候，找的是第一个参数Key而不是第二个参数，所以这里还是需要一个单独得Key存在的。
2.2 RBTreeNode结构的改写
由于在RBTree层，不知道要实现的是map还是set，所以这里使用T来代替节点内存放的数据，改写后的节点结构如下
template<class T> struct RBTreeNode { T _data;// RBTreeNode* _left; RBTreeNode* _right; RBTreeNode* _parent; Color _col; RBTreeNode(const T data) :_data(data) ,_left(nullptr) ,_right(nullptr) ,_parent(nullptr) ,_col(RED) {} };
2.3 RBTree结构改写（仿函数的引入）
由于RBTreeNode结构的改写，RBTree也需要相应的改变，
template<class K, class T> class RBTree { typedef RBTreeNode<T> Node; }
但是这样的话会出现一个问题：怎么找到插入的位置？
在没有改写之前，可以采用kv.first的方式访问到Key，然后找到插入的位置和查找等。但是现在数据只有_data这一个东西，没办法确定传入的是pair还是Key，所以这里封装一个仿函数KeyOfT随着类型一起传入。所以改进后的RBTree结构和插入函数如下：
//最终的RBTree结构 template<class K, class T, class KeyOfT>//增加KeyOfT仿函数模板参数 class RBTree { typedef RBTreeNode<T> Node; public: bool Insert(const T& data) { if(_root == nullptr) { _root = new Node(data); _root->_col = BLACK; return true; } KeyOfT kot;//实例化一个仿函数（函数对象），这个仿函数的功能是拿到Key Node* cur = _root; Node* parent = nullptr; while(cur) { if(kot(cur->_data) < kot(data))//通过仿函数拿到Key { parent = cur; cur = cur->_right; } else if(kot(cur->_data) > kot(data))//通过仿函数拿到Key { parent = cur; cur = cur->_left; } else { return false; } } cur = new Node(data); cur->_col = RED; cur->_parent = parent; if(kot(parent->_data) > kot(cur->_data))//通过仿函数拿到Key { parent->_left = cur; } else { parent->_right = cur; } while(parent && cur->_parent->_col == RED) { Node* grandfather = parent->_parent; if(parent == grandfather->_left) { Node* uncle = grandfather->_right; if(uncle && uncle->_col == RED) { grandfather->_col = RED; uncle->_col = parent->_col = BLACK; cur = grandfather; parent = cur->_parent; } else { if(parent->_left == cur) { RotateR(grandfather); grandfather->_col = RED; parent->_col = BLACK; } else { RotateL(parent); RotateR(grandfather); cur->_col = BLACK; grandfather->_col = RED; } break; } } else { Node* uncle = grandfather->_left; if(uncle && uncle->_col == RED) { parent->_col = uncle->_col = BLACK; grandfather->_col = RED; cur = grandfather; parent = cur->_parent; } else { if(parent->_right == cur) { RotateL(grandfather); grandfather->_col = RED; parent->_col = BLACK; } else { RotateR(parent); RotateL(grandfather); grandfather->_col = RED; cur->_col = BLACK; } break; } } } _root->_col = BLACK; return true; } private: Node* _root = nullptr; };
然后对于map和set，分别实现一个仿函数传入
//map template<class K, class V> class map { struct MapKeyOfT { const K& operator()(const pair<const K, V>& kv) { return kv.first; } }; private: RBTree<K, pair<const K, V>, MapKeyOfT> _t; }; //set template<class K> class set { struct SetKeyOfT { const K& operator()(const K& key) { return key; } }; private: RBTree<K, K, SetKeyOfT> _t; };
这个时候，针对set和map，就可以通过KeyOfT实例化出不同的仿函数(函数对象)，从而按照不同的方式获取到Value中的Key。
现在针对之前已有的代码的修改就已经差不多啦，下面就要开始增加一点东西了。
