前言
上篇博客已经讲解了红黑树插入的模拟实现，这篇文章的目的是利用上节课讲解的底层实现来封装map和set.参考代码借鉴的是STL SGI版本3.0
1 大致框架
首先我们来看看源码里面怎么定义的:
从源码中我们不难发现map和set底层是用了一颗红黑树来封装的，并且模板参数与我们自己想的不太一样。set中传入的是<K,K>,map中传入的是<K,Pair<K,V>> (其他参数可以暂时不用考虑)
大家想想，为什么要这么设计❓这样设计的好处是什么❓
我们传入两个参数的目的就是为了用一颗红黑树封装map和set，也就是第二个参数我们可以理解为给的是一个T,T可以接受上层的传入来的参数。
那可能大家又有了疑问？那为啥要传入第一个参数呀？直接用第二个参数不行吗？
大家别忘了，我们使用find接口和erase接口是用的参数是啥？是不是无论是map还是set都是用的是K,所以这个参数我们必须的传。
但是这样做问题又来了，上层是如何知道我们比较结点大小的时候比较的是K,还是Pair<K,V>?
所以我们还得再传入一个模板参数，不妨给一个仿函数，通过仿函数来取得数据。
2 迭代器
同样，迭代器往往就是容器中最精华的部分，所以迭代器的设计也是有着举足轻重的地位，这里迭代器的设计思路类似于链表的迭代器，不过具体实现却是比链表更加复杂，接下来我们便来看看。
像* -> == !=这些运算符重载好说，实现起来不难，关键是如何实现++重载？–重载?
给了一颗红黑树，如下图，我们如何走到下个结点呢？
我们不妨采用这种思路：如果右子树存在，就找右子树的最左结点；右子树不存在,需要判断是否孩子是父亲的右节点，是的话还要往祖宗向上找，直到找到孩子是父亲的左节点为止。
我们不妨来举一个例子：假如当前在1这个结点，由于1的右子树存在，且6这个结点恰好是1右子树的最左节点，所以++后应该走到了6；假如现在当前结点为11，由于11的右子树为空，所以要往上找，直到找到孩子是父亲左节点为止：11往上找父亲为8，8的右孩子是11，所以没有找到孩子是父亲右孩子的情况继续往上走，孩子为8，父亲为13，13的左孩子为8，随意此时找到了孩子是父亲左的那一个，所以++后就走到了13这个位置。
同理- -运算符的重载可以与++运算符重载反着来，思路类似：如果左子树存在，就找左子树的最右结点；左子树不存在,需要判断是否孩子是父亲的右节点，是的话还要往祖宗向上找，直到找到孩子是父亲的右节点为止。
这个我就不再分析了，大家可以自行分析。
为了方便，我们将用nullptr来构造找到了末尾，不用继续找了，但是STL中并不是这样设计的，是用了一个头结点来连接：
走到了头结点就表示找到了末尾。
用这种方式会稍微麻烦些，不过总体也是不难的。
然后我们自己便可以实现一份迭代器了：
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& self)const { return _node == self._node; } bool operator!=(const Self& self)const { return _node != self._node; } Self& operator++() { if (_node->_right)//右子树存在，就找右子树的最左结点 { Node* left = _node->_right; while (left->_left) { left = left->_left; } _node = left; } else { //右子树不存在,需要判断是否孩子是父亲的右节点，是的话还要往祖宗向上找，直到找到 //孩子是父亲的左节点为止 Node* child = _node; Node* parent = _node->_parent; while (parent && parent->_right == child) { child = parent; parent = parent->_parent; } //走到这里说明找到了孩子是父亲的左节点或者 //孩子已经是根节点了(表明在根节点也没有找到，说明已经遍历完成了) _node = parent; } return *this; } Self& operator--() { if (_node->_right)//左子树存在，就找左子树的最右结点 { Node* right = _node->_left; while (left->_right) { left = left->_right; } _node = right; } else { //左子树不存在,需要判断是否孩子是父亲的左节点，是的话还要往祖宗向上找，直到找到 //孩子是父亲的右节点为止 Node* child = _node; Node* parent = _node->_parent; while (parent && parent->_left == child) { child = parent; parent = parent->_parent; } //走到这里说明找到了孩子是父亲的右节点或者 //孩子已经是根节点了(表明在根节点也没有找到，说明已经遍历完成了) _node = parent; } return *this; } };
3 map和set的封装
其他的都好说，关键是如何实现set不能够修改，而map中可以修改Val;
我们可以采取这种方式：set的普通迭代器我们用上层的const迭代器实现，set的const迭代器我们也用上层的const迭代器实现。map的话我们只需要将==第二个模板参数给pair<const K,V>==就可以了。
set.hpp:
namespace grm { template<class K> class set { struct SetOfKey { const K& operator()(const K& k) { return k; } }; private: RBTree<K, K, SetOfKey> _rbTree; //typedef typename RBTree<K, const K, SetOfKey>::Iterator iterator; //不能够像上面这样传入参数 typedef typename RBTree<K, K, SetOfKey>::ConstIterator iterator; typedef typename RBTree<K, K, SetOfKey>::ConstIterator const_terator; public: iterator begin() { return _rbTree.begin(); } iterator end() { return _rbTree.end(); } const_terator begin()const { return _rbTree.begin(); } const_terator end()const { return _rbTree.end(); } pair<iterator, bool> insert(const K& k) { return _rbTree.insert(k); } };
map.hpp:
namespace grm { template<class K, class V> class map { struct MapOfKey { const K& operator()(const pair<const K, V>& kv) { return kv.first; } }; private: RBTree<K, pair<const K,V>, MapOfKey> _rbTree; public: typedef typename RBTree<K, pair<const K, V>, MapOfKey>::Iterator iterator; typedef typename RBTree<K, pair<const K, V>, MapOfKey>::ConstIterator const_iterator; iterator begin() { return _rbTree.begin(); } iterator end() { return _rbTree.end(); } const_iterator begin()const { return _rbTree.begin(); } const_iterator end()const { return _rbTree.end(); } pair<iterator, bool> insert(const pair<K,V>& kv) { return _rbTree.insert(kv); } V& operator[](const K& k) { pair<iterator, bool> tmp = insert(make_pair(k,V())); return tmp.first->second; } };
但是这样实现set时也还是会遇到问题：那就是我们用了普通迭代器来构造const迭代器，这样势必是会报错的，有什么处理方式吗？
我们可以在迭代器中多给出一个构造：
//模板参数是普通迭代器就是拷贝构造 //模板参数是const迭代器就是用普通迭代器构造const迭代器 __RBTreeIterator(const __RBTreeIterator<T,T&,T*>& it) :_node(it._node) {}
这样就能够解决问题了。
如果大家还有哪里不懂的地方可以私信博主，有需要的可以参考博主的码云：
