map与set的部分源码参考
map和set的底层都是由红黑树实现的。
所以这里将上次实现的红黑树插入拿来用。
首先想一想，搜索二叉树不能修改值，因为会破坏整棵树的平衡。
set与map的部分源码：
class set { public: // typedefs: typedef Key key_type; typedef Key value_type; typedef Compare key_compare; typedef Compare value_compare; private: typedef rb_tree<key_type, value_type, //set这里传了一个K，一个V identity<value_type>, key_compare, Alloc> rep_type; rep_type t; // red-black tree representing set
template <class Key, class T, class Compare = less<Key>, class Alloc = alloc> class map { public: // typedefs: typedef Key key_type; typedef T data_type; typedef T mapped_type; typedef pair<const Key, T> value_type; private: typedef rb_tree<key_type, value_type, //map这里传了一个K，一个V select1st<value_type>, key_compare, Alloc> rep_type; rep_type t; // red-black tree representing map
这个是红黑树的部分源码：
template <class Key, class Value, class KeyOfValue, class Compare,class Alloc = alloc> class rb_tree { protected: typedef void* void_pointer; typedef __rb_tree_node_base* base_ptr; typedef __rb_tree_node<Value> rb_tree_node; public: typedef rb_tree_node* link_type; protected: size_type node_count; // keeps track of size of tree link_type header; Compare key_compare;
set要传入到红黑树的Value的值是K,map要传入的值是pair<const K,V>
那么，这里完全可以区分传入的是set还是map，为什么要给红黑树传入第一个模板参数呢？
第一个模板参数是用来查找的，因为无论是set还是map都是用kay去查找的。
改造红黑树
这是红黑树的结点：
enum Color//利用枚举来给红黑树配色 { RED, BLACK }; template<class T> struct RBTreeNode { RBTreeNode(const T& data)//让红黑树的结点变成一个模板就行了，因为有可能是set有可能是map :_data(data) , _color(RED)//这里一定要给红色，如果给黑色其他路径就要涉及到也要加黑色结点，更加麻烦 , _left(nullptr) , _right(nullptr) , _parent(nullptr) {} RBTreeNode* _left; RBTreeNode* _right; RBTreeNode* _parent; T _data; Color _color;//结点的配色 };
namespace baiye { template<class K> class set { public: private: RBTree<K, K> _t;//K模型 }; }
namespace baiye { template<class K, class V> class map { public: private: RBTree<K, pair<const K, V>> _p;//KV模型 }; }
然后我们发现，后面的插入这里调用出现了问题：
原来写的是VK模型，但是现在set是K模型，要兼容两个模型。
让我们来看看源码是怎么做的：
源码这里多了一个模板参数，意思是将key取出来比较大小。
这里可以写两个仿函数用：
namespace baiye { template<class K> class set { struct setKeyOFV { const K& operator()(const K& key) { return key; } }; public: bool insert(const K& key) { return _t.Insert(key); } private: RBTree<K, K, setKeyOFV> _t; }; }
namespace baiye { template<class K, class V> class map { struct mapKeyOFV { const K& operator()(const pair<const K, V>& kv) { return kv.first; } }; public: bool insert(const pair<const K, V>& kv) { return _p.Insert(kv); } private: RBTree<K, pair<const K, V>, mapKeyOFV> _p; }; }
红黑树的迭代器
先来实现*与->：
template<class T> struct RBTreeIterator { typedef RBTreeNode<T> Node; Node* _node; RBTreeIterator(Node* node) :_node(node) {} T& operator*() { return _node->_data; } T* operator->() { return &_node->_data; } bool operator!=(const Self& it) { return _node != it._node; } };
迭代器难的是++和- -操作：
原来stl中的红黑树其实有一个哨兵位的头结点：
哨兵位中还有两个指针分别指向红黑树中的最小值和最大值，但是这里我并没有去实现这个哨兵位，所以就用另一种方法。
首先先给红黑树加begin和end函数：
iterator begin() { Node* cur = _root; while (cur && cur->left) { cur = cur->_left; } return iterator(cur); } iterator end() { return iterator(nullptr); }
然后是++，++是要走中序遍历的，我们要采用迭代的方式，以前要借助一个队列来进行中序遍历的方法进行++。
假设我们传入的迭代器的结点是8结点，那么下一个结点就是10号结点，也就是8号结点的右子树最小结点。
那么如果右为空呢？
右子树为空就说明不需要去右子树找了，需要向上找节点，假设是这样子的：
it指向5结点，发现右为空，那就向上走，走到6结点发现右不为空然后走到7结点，7结点右为空就要继续往上走，这个时候不应该走到6结点的位置，应该是8结点的位置。
假设这里再多出一个结点：
那么他的右为空也不能再走到7结点的位置了。
所以我们能总结出来一个规律。
右不为空就去找右子树的最小节点。
右为空就去找祖先（孩子为父节点的左的那个祖先）
