map和set的实现原理
为了方便实现我们的map和set，我们肯定是要养成看源码的习惯的，看了源码之后你才会感受到大佬的强大！
在源码里面，对于map和set的实现，底层是用同一棵红黑树封装出来的，并不是用了两棵红黑树
那么大家肯定会有疑问了，一棵红黑树这么能两用呢，况且map和set的底层存储的节点类型不一样啊，map是存储的键值对，set只是存储key
这时设计map和set的大佬就想到了一个极佳的办法，在红黑树底层中用了一个模板参数Value来代表红黑树结点存储对象的类型，这个类型可能是pair键值对，也有可能是key类型。
红黑树其实并不知道自己的节点是什么类型，只能用模板来接受存储对象的类型
enum Color {RED,BLACK}; template<class T>//节点存储对象类型，可能是键值对也有可能是key class RBTreeNode { T _data; RBTreeNode<T>* _left; RBTreeNode<T>* _right; RBTreeNode<T>* _parent; Color _col; RBTreeNode(const T& data) :_data(data) , _left(nullptr) , _right(nullptr) , _parent(nullptr) , _col(RED) {} };
这样，我们就可以实现一树多用了！
我们就可以根据value的类型来去确定是map还是set了，但是大家可能会有一点小疑问，既然有了value就可以实现红黑树了，那我们还要关键码key有什么用呢？
这里的关键码key是必不可少的！
因为在红黑树搜索的时候，依靠的还是关键码进行搜索，通过所传关键码和红黑树结点中的关键码的大小关系，确定到红黑树中要搜索的某个结点。
红黑树的find函数的参数类型必须是key！
在实现map和set之前，我们先想一想，上一篇博文的红黑树有哪些地方需要进行改进的？
细心的朋友就会发现，上篇博文的代码，插入时比较的就只是在整形情况下的key的比较，但是map和set就只是存储整形吗？显然不是，所以我们就要想办法提取其他类型下的key关键码来进行比较，并且map的节点的value类型是键值对的话，要提取的first，set只需要直接比较key，该如何结局这个问题呢？
我们这个时候就可以使用仿函数了！
我们可以在map和set中各自增加一个仿函数类，在模板传参时，再增加一个仿函数类来提取节点的关键码的参数，我们将他命名为KeyOfT
set
template<class K> class set { struct SetKeyOfT { const K& operator()(const K& key) { return key; } }; public: private: RBTree<K, K, SetKeyOfT> _t; };
map
template<class K, class V> class map { struct MapKeyOfT { const K& operator()(const pair<const K, V>& kv) { return kv.first; } }; public: private: RBTree<K, pair<const K, V>, MapKeyOfT> _t; };
rbtree
template<class K,class T,class KeyOfT> class RBTree { typedef RBTreeNode<T> Node; public: private: Node* _root = nullptr; };
这样我们再插入的时候就可以直接提取关键码进行插入了
map和set的迭代器
关于map和set的迭代器的实现，设计库里面的源码的大佬很巧妙地运用了const
大家都知道，set是不可以修改的，map可以修改，但是修改的也只是pair键值对的value，pair里面的key可是不能修改的
对红黑树类型中的迭代器类型进行typedef时，可以看到我们在typedef后面加了typename，typename的作用就是告诉编译器后面的东西是一个类型，你先不要编译他，等到模板实例化为真正类型后，你再去取他里面的内嵌类型iterator。因为我们知道编译器是不编译模板的，编译的是模板实例化之后的代码，只有模板实例化之后，它里面的内嵌类型我们才可以取到，所以如果你不加typename，有可能取的不是类型，因为静态变量或函数都是可以通过类+域访问符进行访问的，所以如果你要取模板里面的类型，那就必须在模板前面加typename，告诉编译器你取的是类型。
rbtree迭代器实现
struct __RBTreeIterator { typedef RBTreeNode<T> Node; typedef __RBTreeIterator<T> Self; Node* _node; __RBTreeIterator(Node* node) :_node(node) {} T& operator*() { return _node->_data; } T* operator->() { return &_node->_data; } Self& operator++() { if (_node->_right) { Node* min = _node->_right; while (min->_left) { min = min->_left; } _node = min; } else { Node* cur = _node; Node* parent = cur->_parent; while (parent && cur == parent->_right) { cur = cur->_parent; parent = parent->_parent; } _node = parent; } return *this; } Self& operator--() { //右子树 根 左子树 if (_node->_left) { //找左子树的最右结点，其实就是次大的结点 _node = _node->_left; while (_node->_right) { _node = _node->_right; } } else { Node* cur = _node; Node* parent = _node->_parent; while (parent && cur == parent->_left) { cur = parent; parent = parent->_parent; } //如果cur是parent的右，则直接让_node指向到parent即可 _node = parent; } return *this;//返回迭代器对象 } bool operator!=(const Self& it)const//const修饰表示在该成员函数内部，不能修改对象的任何成员变量 { return this->_node != it._node; } bool operator==(const Self& it)const//const对象和非const对象都可以调用 { return this->_node == it._node; } };
那么map和set的实现就很简单了：
template <class K> class set { public: //set表层的普通迭代器底层用的依旧是const_iterator，就是不允许对set的迭代器指向内容进行修改 typedef typename RBTree<K, K, SetKeyOfT<K>>::const_iterator iterator; typedef typename RBTree<K, K, SetKeyOfT<K>>::const_iterator const_iterator; iterator begin() const //为了防止权限的放大，我们直接使用const，如果对象是const，调用const的begin，不是const也调用const的begin和end { return _t.begin(); } iterator end() const { return _t.end(); }
map的迭代器是需要实现两个版本的，因为map容器中的数据是可以被修改的，如果你想修改map中的数据那就用iterator，如果你想修改map中的数据那就用const_iterator。
如果是const_iterator，那解引用或者→返回的就是键值对的常引用或const修饰的指向键值对的结构体指针，那么此时键值对的key和value都是不可以修改的。
如果是iterator，解引用或者→返回的就是键值对的普通引用或无const修饰的指向键值对的结构体指针，但此时键值对的key依旧不可以被修改，只能对键值对中的value进行修改所以即使你用的是iterator，他所指向的键值对的key依旧是不能修改的，我们只能修改他的value。
template <class K, class V> class map { public: typedef typename RBTree<K, pair<const K, V>, MapKeyOfT<K, V>>::const_iterator const_iterator; typedef typename RBTree<K, pair<const K, V>, MapKeyOfT<K, V>>::const_iterator const_iterator; //map的迭代器需要提供两个版本 iterator begin() { return _t.begin(); } iterator end() { return _t.end(); } const_iterator begin()const { return _t.begin(); } const_iterator end()const { return _t.end(); } private: RBTree<K, pair<const K, V>, MapKeyOfT<K,V>> _t; };
红黑树插入的改造
我们使得插入后其返回值为键值对，如果出现插入key值相等的情况，则将bool改为false即可。最后调色后返回键值对时，我们不能直接返回cur构造的迭代器，因为如果发生调色，则cur位置会更改，所以在插入结点后，用一个curit的结点指针记录一下插入结点的位置，最后返回由curit结点指针构造出来的迭代器
pair<iterator, bool> Insert(const T& data) //红黑树必须通过结点里面存储的key来进行比较才可以插入结点，所以出现了kot仿函数对象 { KeyOfT kot; Node* parent = nullptr; Node* cur = _root; if (_root == nullptr) { _root = new Node(data); _root->_col = BLACK; return make_pair(iterator(_root), true); } while (cur) { if (kot(cur->_data) < kot(data)) { parent = cur; cur = cur->_right; } else if (kot(cur->_data) > kot(data)) { parent = cur; cur = cur->_left; } else { return make_pair(iterator(cur), false); } } cur = new Node(data); Node* curit = cur;//保存一下cur的位置否则下面旋转调色过程中，cur有可能被改了 if (kot(parent->_data) > kot(data)) { parent->_left = cur; cur->_parent = parent; } else { parent->_right = cur; cur->_parent = parent; } while (parent && parent->_col == RED) { Node* grandparent = parent->_parent; if (parent == grandparent->_left) { Node* uncle = grandparent->_right; if (uncle && uncle->_col == RED) { parent->_col = uncle->_col = BLACK; grandparent->_col = RED; cur = grandparent; parent = cur->_parent; } else if (cur == parent->_left) { RotateR(grandparent); grandparent->_col = RED; parent->_col = BLACK; break; } else if (cur == parent->_right) { RotateL(parent); RotateR(grandparent); cur->_col = BLACK; grandparent->_col = RED; break; } else { assert(false); } } else { Node* uncle = grandparent->_left; if (uncle && uncle->_col == RED) { grandparent->_col = RED; uncle->_col = parent->_col = BLACK; cur = grandparent; parent = cur->_parent; } else if (cur == parent->_right) { RotateL(grandparent); parent->_col = BLACK; grandparent->_col = RED; break; } else if (cur == parent->_left) { RotateR(parent); RotateL(grandparent); cur->_col = BLACK; grandparent->_col = RED; break; } else { assert(false); } } } _root->_col = BLACK; return make_pair(iterator(curit), true); }
map的[]重载
[]直接返回插入节点的值，如果[]内的key值不在红黑树中，就直接插入，若在其中也有进行修改，最后返回iterator的first的second
template <class K, class V> class map { public: pair<iterator, bool> insert(const pair<const K, V>& kv) { return _t.Insert(kv); } V& operator[](const K& key) { pair<iterator, bool> ret = insert(make_pair(key, V())); return (ret.first)->second; } private: RBTree<K, pair<const K, V>, MapKeyOfT<K,V>> _t; };
由于博主的能力有限，部分讲解不到位，等我巩固知识后再做修正！希望大家指正！本篇博文的分享到这里就结束了，感谢大家的支持！
