目录
改造红黑树
红黑树的迭代器
map的模拟实现
set的模拟实现
在上一篇博客中，我们实现了红黑树，但是红黑树节点中的值是pair<K,V> _kv形式，这种红黑树适用于map的底层，那么如果我们想要红黑树节点中的值是key的形式（适用于set的底层），我们该怎么搞呢？难道我们只把红黑树节点的类型改一下，其它基本保持不变，再来实现一遍吗？这未免太繁琐了！
我们先来看一看stl库中如何实现map和set的：
它们貌似用的同样的红黑树实现的，它们的区别在于红黑树的第二个模版参数，一个是key，一个是kv的pair，我们再来看看stl库里怎么实现的rb_tree，
在stl中，红黑树在实现时，并没有直接确定是key还是kv的pair，而是由模版的第二个参数Value决定，本质上这是一个高级的泛型编程，不得不说，大佬写的模版比我们技高一筹！
改造红黑树
为了达到和stl库中一样的效果，我们需要对上节的红黑树进行改造，即对红黑树中值的类型不指定，使用模版：
//写成一个模版，T有可能是key，有可能是pair
template<class T>
struct RBTreeNode
{RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;Color _color;T _data;RBTreeNode(const T& data): _left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _color(RED){}
};调用示意图如下：
肯定有人会有疑问，RBTree中第一个模版参数class K好像没用到，其实在Find函数中可以用到，Find函数肯定要通过Key来查找（Node* Find(const K& key)）。
当我们对红黑树改造后，在Insert函数中，会遇到这样的问题：我们需要对待插入的数据和节点值进行比较以便插入，但是，待比较数据和节点值有可能是key，也有可能是pair，为了解决这样的问题，在class set和class map中分别增加一个内部类，
template<class K>
class set
{struct SetKeyOfT{const K& operator()(const K& key){return key;}};...
};template<class K,class V>
class map
{struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};...
};在class RBTree上加模版参数class KeyOfT，然后在类中定义KeyOfT的对象，
template<class K,class T,class KeyOfT>
class RBTreebool Insert(const T& data)
{if (_root == nullptr){_root->_color = BLACK;return true;}KeyOfT kot;Node* cur = _root;Node* parent = nullptr;while (cur){//K//pair<K,V>//kot对象，是用来取T类型的data对象中的key//如果data是pair，则通过kot仿函数去调用上面的内部类，从而得到pair中的keyif (kot(cur->_data) > kot(data)){parent = cur;cur = cur->_left;}else if(kot(cur->_data) < kot(data)){parent = cur;cur = cur->_right;}else{return false;}}...
}红黑树的迭代器
我们先来看stl里是怎么实现的：
迭代器里就是一个节点指针去封装，
然后实现operator++、operator->等的重载，我们自己来实现一下红黑树的迭代器：
template<class T,class Ref,class Ptr>
struct __RBTreeIterator
{typedef RBTreeNode<T> Node;typedef __RBTreeIterator<T, Ref, Ptr> Self;Node* _node;__RBTreeIterator(Node* node):_node(node){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!=(const Self& s){return _node != s._node; }Self& operator++(){if (_node->_right){//下一个，右树最左节点Node* leftMin = _node->_right;while (leftMin && leftMin->_left){leftMin = leftMin->_left;}_node = leftMin;}else{//下一个，孩子等于父亲左的那个祖先Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}
};上面中最复杂的是operator++的实现，我们分情况讨论一下：
1.当前结点的右子树不为空，中序下一个访问的节点，是右子树的最左节点。
2.右为空，下一个访问，倒着在祖先里找，找孩子是父亲左的祖先。
在红黑树的实现中，我们typedef一下：
typedef __RBTreeIterator<T, T&, T*> Iterator;在红黑树中，我们要实现begin()、end()等接口：
//begin是最左节点
Iterator begin()
{Node* leftMin = _root;while (leftMin && leftMin->_left){leftMin = leftMin->_left;}return Iterator(leftMin);
}
//end是最后一个节点的下一个，也就是nullptr
Iterator end()
{return Iterator(nullptr);
}map的模拟实现
如果我们想要实现map或set的拷贝构造，我们知道默认的拷贝构造，对于内置类型完成值拷贝，针对自定义类型会调用它的拷贝构造，这样会造成浅拷贝，所以，我们需要自己写拷贝构造函数：
//强制生成默认构造函数
RBTree() = default;RBTree(const RBTree<K, T, KeyOfT>& t)
{_root = Copy(t._root);
}
private:Node* Copy(Node* root){if (root == nullptr)return nullptr;//构造新节点Node* newroot = new Node(root->_data);//改变新节点的颜色newroot->_color = root->_color;//把递归Copy得到的子树链接到newroot的左侧newroot->_left = Copy(root->_left);//让newroot->_left向上链接到newrootif (newroot->_left)newroot->_left->_parent = newroot;//把递归Copy得到的子树链接到newroot的右侧newroot->_right = Copy(root->_right);//让newroot->_left向上链接到newrootif (newroot->_right)newroot->_right->_parent = newroot;return newroot;}除此之外，我们还要写析构函数：
~RBTree()
{Destroy(_root);_root = nullptr;
}
void Destroy(Node* root)
{//走一个后序遍历if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;root = nullptr;
}在map中我们还要实现operator[]重载，我们之前学过，库里的[]重载是调用insert函数，operator[]返回值是key所在的迭代器，
因此，我们主要就是调整insert函数，insert函数的返回值类型是pair<Iterator,bool>，修改insert函数的返回值：
pair<Iterator,bool> Insert(const T& data)实现operator[]：
V& operator[](const K& key)
{pair<iterator, bool> ret = _t.Insert(make_pair(key, V()));//ret.first.operator->()->secondreturn ret.first->second;
}完整的map模拟实现代码如下：
namespace ghs
{template<class K,class V>class map{struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};public://此时RBtree还没有实例化，需要加typename告诉编译器，等实例化了再去确认typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::Iterator iterator;typedef typename RBTree<K, const K, MapKeyOfT>::ConstIterator const_iterator;const_iterator begin()const{return _t.begin();}const_iterator end()const{return _t.end();}iterator begin(){return _t.begin();}iterator end(){return _t.end();}pair<iterator, bool> insert(const pair<K, V>& kv){return _t.Insert(kv);}V& operator[](const K& key){pair<iterator, bool> ret = _t.Insert(make_pair(key, V()));//ret.first.operator->()->secondreturn ret.first->second;}private://由于RBTree的第二个模版参数是用来确定节点的类型,map要求pair中给的key不能变，但是val可以变//因此，pair<const K, V>中第一个参数加const，第二个参数不加constRBTree<K, pair<const K, V>, MapKeyOfT> _t;};}set的模拟实现
namespace ghs
{template<class K>class set{struct SetKeyOfT{const K& operator()(const K& key){return key;}};public://没有实例化的类，去取，需要加typenametypedef typename RBTree<K, const K, SetKeyOfT>::Iterator iterator;typedef typename RBTree<K, const K, SetKeyOfT>::ConstIterator const_iterator;const_iterator begin()const{return _t.begin();}const_iterator end()const{return _t.end();}iterator begin(){return _t.begin();}iterator end(){return _t.end();}pair<iterator, bool> insert(const K& key){return _t.Insert(key);}iterator find(const K& key){return _t.Find(key);}private://由于RBTree的第二个模版参数是用来确定节点的类型，set的key是不可以改变的，所以要加constRBTree<K, const K, SetKeyOfT> _t;};
}在学完vector、list、map、set的迭代器iterator后，我们可以进一步理解一下封装：它们底层的operator++、operator*、operator->完全不一致，但是对外提供的方式是一致的（统一的迭代器行为）。
