一、map与set的STL源码分析
我们首先可以观察到，在set和map中包含有如下的头文件
于是我们可以先打开这些头文件，我们先不考虑multimap与multiset
我们可能会因为set只有一个数据存储而会误以为他里面使用的是key模型的红黑树，但是其实不是的。在stl库里面map和set使用的是同一棵key-val的红黑树。
如下所示，可以看出来
不过虽然使用的是key-val的红黑树，但是它的key和val都是key
根据上面的结构，我们似乎可以猜测，难道库里面以空间换时间，为了只使用同一颗树，牺牲了一半的空间吗？当然以上都仅仅只是我们个人的猜测
我们先再来看一下map的底层
我们似乎发现，这个也很奇怪，key是Key这个是可以的，但是val竟然是个pair类型的。
也就是说
- set是<K,K>模型的树
- map是<K，pair>模型的树
这样的话，我们就必须得观察一下这棵树到底是什么情况了
如下所示，header就是这棵树的根节点，它的类型是通过的两次typedef出来的，我们可以注意到，这个结点的类型，存储的就是value。
但是这个val不是我们前面所说的key-val中的val。这里的val对于map而言是pair，对于set而言是key
所以说，真正决定树里面存储的是什么，看的是第二个模板参数，而不是第一个模板参数。
我们现在再来观测一下这个红黑树结点里面是什么，如下所示，这里是通过一个继承关系来搞定的。派生类存储的是value，而基类存储的是三叉链的指针，以及颜色
那么在这里我们似乎看到了，在这棵树里面，我们好像并不是很需要这个key类型的模板参数，那么事实上是如此的吗？其实不是的，这个key还必须得传入，因为有一个接口会使用到他。即对于map而言，find这个接口它是通过key来进行比较的。所以必须传入key的类型
二、改造红黑树
1.基本结构
对于我们之前所实现的红黑树，我们可以对其进行修改，以便适应我们的map和set
如下所示，是我们红黑树结构的改变，红色圈出来的部分就是改变的部分。由于map和set都需要使用这颗红黑树，那么我们就得在红黑树这一层实现一层模板。所以，我们利用T类型的不同来进控制，如果是map的话那么T就是pair，如果是set，T就是K
如下是map与set的基本结构
可以看到，我们很巧妙的使用了一层红黑树上的泛型，使用同一个树模板来实现的
如下是调用图
2.比较
如下所示，当我们将原来的kv改为了_data的时候，下面的代码也要随之改变，但是下面的代码真的正确吗？
对于set而言，_data就是目标值的类型，这个类型是什么我们是不确定的，所以需要它自己提供一个运算符重载，或者仿函数来解决。
如果是map的话，这里的_data就是pair类型的，我们就需要去取出第一个元素，也就是key类型的来进行比较。（这里需要注意，虽然pair本身提供了比较，但是这里的比较并非我们所期望的比较方式，我们只需要比较first，而库里面的重载先比较first，然后比较second的）
所以，我们先来解决当_data为pair时候，如何取出第一个元素呢？，因为我们的是泛型，所以这个_data的取法还是需要注意的。这里我们可以使用一共仿函数，但是这里的仿函数与之前不同的是这里的仿函数主要集中解决取数的问题
如下所示，我们在map和set里面写两个内部类，这个内部类里面是一个运算符重载，充当仿函数。对于map萃取处它的key，对于set萃取出它本身
这样的话，我们就可以将仿函数应用于我们的红黑树中了
现在也就成功的解决了如何辨别是map还是set的比较
如下是他们之间的调用关系
对于我们这样的处理，当我们写find函数的时候，也是可以去使用的
然后我们就可以去写出insert的接口了
可以看到代码并未报错
三、迭代器
1.STL源码分析
我们前面的插入功能已经可以正常运行了，现在需要的就是迭代器
从上图中我们就可以很容易的看到，在set中，两个迭代器其实都是const迭代器，这个迭代器也是依靠着红黑树里面的迭代器去实现的
那么我们可以去溯源，去找到红黑树里面这两个迭代器的定义，如下所示
我们可以看到，这个迭代器与链表的迭代器是比较相似的，都是通过使用一个自定义类型来实现的，我们可以继续找到这个迭代器所在的位置，我们还可以发现，这个其实还搞了一层继承
那么我们就在去找到继承的基类，如下所示，可以看到里面就有一个结点指针了
同样的，在派生类中，我们是可以看到很多迭代器的操作的
2. 迭代器
对于这里的迭代器，我们可以参考库里面的代码去进行实现，即专门封装一个迭代器类。
这个迭代器类专门用来处理红黑树中的迭代器
如下所示，是我们完成的迭代器类，这个迭代器我们先只考虑++功能，解引用功能，还有比较功能。这是为了方便后面进行测试，后续可以进行补充。
在这个迭代器类中，只有一个成员变量_node,这里的解引用功能的重载是比较简单的，直接返回对该_node解引用返回即可。
需要注意的就是++操作不是那么容易想到的。
对于++操作，即如下所示的红黑树
- 右树不为空，访问的是右树的最左结点（即最小结点）
- 右树为空，那么下一个访问的就是孩子是父亲的左孩子的那个祖先（这句话听起来可能有点绕口，因为我们可以根据下图去分析，如果parent的右孩子是cur，那么就说明此时的parent结点已经被访问过了，如果parent的左孩子是cur，那么就说明此时的parent没有被访问。当然还需要考虑parent为空的时候，也代表着已经访问结束了，此时说明，整棵树全部被访问了）
template<class T> struct __TreeIterator { typedef RBTreeNode<T> Node; typedef __TreeIterator<T> Self; Node* _node; __TreeIterator(Node* node) :_node(node) {} T& operator*() { return _node->_data; } T* operator->() { return &_node->_data; } bool operator!=(const Self& s) { return _node != s._node; } Self& operator++() { if (_node->_right) { Node* subLeft = _node->_right; while (subLeft->_left) { subLeft = subLeft->_left; } _node = subLeft; } else { Node* cur = _node; Node* parent = _node->_parent; while (parent) { if (parent->_right == cur) { cur = parent; parent = parent->_parent; } else { break; } } _node = parent; } return *this; } };
有了迭代器类，我们可以在红黑树层次去调用这个迭代器类了
然后我们依次到map和set层次去封装
如下是set
如下是map
不过在这里我们需要考虑到的问题就是，在我们使用typedef去定义一个类型的时候，这里我们需要将红黑树中的迭代器给再次typedef，但是编译器一开始没有实例化模板，并不知道这个iterator是内嵌类型还是一个静态成员变量。所以我们需要使用typename来说明他是一个类型。
有了如上的封装之后，我们就可以简单的跑一下迭代器了
不过在这里我们似乎发现了一个问题，那就是我们的set里面的数据应该是不可以被修改的，但是我们对他进行了修改，而且还可以成功使用。这是我们不可以接收的，因为一旦修改了set里面的数据，那么就意味着这棵树已经乱了。可能不再是一个搜索二叉树了。
而在库里面是这样实现的，对于set，两个迭代器本质都是const迭代器。对于map，它的key应该不可以被修改，这里是通过对pair的第一个参数进行const限定的，从而锁死了第一个参数。
那么我们先来解决一下set的问题，首先我们需要提供一个const迭代器。这个迭代器与之前链表的十分相似，我们可以直接通过多传两个模板参数来进行控制，因为const的本质其实就仅仅只是返回值不可以修改罢了。
下面是红黑树中的修改
然后我们来修改set中的迭代器函数，如下所示，注意这里我们千万不能写上我们注释掉的部分，因为我们只是想把set的迭代器给控制住。但是我们的set对象本身还是需要增加和删除的。所以我们可以用const修饰this指针，来使得set的权限缩小，以至于里面的红黑树就变成了const类型了，就可以去调用红黑树中的const迭代器了。如果我们不去进行权限缩小，那么这颗红黑树就是一个普通对象，就会去调用红黑树中的普通迭代器，就会产生类型不匹配问题了。
然后我们来处理map的迭代器问题
如下所示，处理了set以后，map就简单了，我们只需要让pair中的第一个参数给带上const即可。这样一来，无论如何，是无法修改pair的第一个参数的。
通过以下代码的报错，我们可以证明我们的代码确实是可以的
然后这样一来已经处理好了const迭代器的问题了
现在我们继续完善–操作
如下代码所示，完全是与++操作相反的。以前判断右子树，现在判断左子树即可
Self& operator--() { if (_node->_left) { Node* subRight = _node->_left; while (subRight->_right) { subRight = subRight->_right; } _node = subRight; } else { Node* cur = _node; Node* parent = cur->_parent; while (parent) { if (parent->_left == cur) { cur = parent; parent = parent->_parent; } else { break; } } _node = parent; } return *this; }
3. 与库里面的迭代器的差异
上面是我们自己实现的迭代器，但是与库里面的迭代器还是有很大的区别的
实际上在库里面的红黑树还有一个哨兵位
这个哨兵位的意义它的parent指向根节点，左孩子和右孩子分别指向最小和最大，这样的话会使得迭代器找最小结点和最大结点的时候会方便很多
不过虽然如此，但是也是需要付出一定的代价的，那就是对于实现的难度上来说，更加困难了，因为旋转以后这个哨兵位的指针就需要做出一定的改变
而且上面的话对于正常情况下++和–都是没有什么问题的，但是当出现下面的这种特殊情况的时候，就会出现死循环，即parent和cur陷入死循环了。我们就需要额外做出特殊判断了
四、map的[]操作
我们在前面已经知道，map的[]操作主要是依靠insert操作完成的。所以我们还得将insert在进一步完善
于是，我们就要从底层开始修改，先处理红黑树的插入操作
如下就是我们想办法将红黑树的插入操作由bool变为了pair的返回值
pair<iterator,bool> Insert(const T& data) { KeyOfT kot; if (_root == nullptr) { _root = new Node(data); _root->_color = BLACK; //根节点必须是黑色 return make_pair(iterator(_root), true); } Node* cur = _root; Node* parent = nullptr; while (cur) { if (kot(cur->_data) > kot(data)) { parent = cur; cur = cur->_left; } else if (kot(cur->_data) < kot(data)) { parent = cur; cur = cur->_right; } else { return make_pair(iterator(cur), false); } } cur = new Node(data); //插入红色结点 //用于保存新节点的指针 Node* newnode = cur; if (kot(parent->_data) < kot(data)) { parent->_right = cur; } else if (kot(parent->_data) > kot(data)) { parent->_left = cur; } cur->_parent = parent; //开始处理颜色 while (parent && parent->_color == RED) { Node* grandfather = parent->_parent; if (grandfather->_left == parent) { Node* uncle = grandfather->_right; if (uncle && uncle->_color == RED) { parent->_color = BLACK; uncle->_color = BLACK; grandfather->_color = RED; cur = grandfather; parent = grandfather->_parent; } else if (uncle == nullptr || uncle->_color == BLACK) { if (parent->_left == cur) { RotateR(grandfather); parent->_color = BLACK; grandfather->_color = RED; break; } else { RotateL(parent); RotateR(grandfather); cur->_color = BLACK; grandfather->_color = RED; break; } } } else { Node* uncle = grandfather->_left; if (uncle && uncle->_color == RED) { parent->_color = BLACK; uncle->_color = BLACK; grandfather->_color = RED; cur = grandfather; parent = grandfather->_parent; } else if (uncle == nullptr || uncle->_color == BLACK) { if (parent->_right == cur) { RotateL(grandfather); grandfather->_color = RED; parent->_color = BLACK; break; } else { RotateR(parent); RotateL(grandfather); cur->_color = BLACK; grandfather->_color = RED; break; } } } } _root->_color = BLACK; return make_pair(iterator(newnode), true); }
解决了红黑树的返回值，然后我们可以直接修改map与set的返回值了
如上图所示，但是当我们运行的时候，很遗憾，报错了
我们注意到是set中的pair的迭代器出问题了
我们也不难发现问题的根源，就是因为set中的迭代器都是const迭代器，而红黑树是一个普通对象，它返回的是一个普通的迭代器。
所以我们上面的写法出现了类型不兼容的问题
那么我们有没有什么办法可以处理呢？其实是有的，我们可以看库里面是这样处理的
于是我们可以仿照它去实现
但是可惜的是还是没有通过
这里其实涉及到pair的构造函数了
如下代码所示
可以看到，pair其实是通过初始化列表完成的。所以说在将first初始化的时候，会调用它的构造函数。去用它的迭代器去构造一个const迭代器。
这里我们需要注意的一个问题是，这个构造如何写？我们参照库里面的代码。可以看到，库里面专门将普通迭代器和const迭代器给再次typedef了，这样的好处就在于，当这个迭代器类是一个const迭代器的时候，那么这里就是构造函数，如果这个迭代器被实例化为了普通迭代器的时候，这里就是一个拷贝构造函数了
于是我们可以仿照库里面的代码，写出这样的代码
最终我们再次运行，编译成功了
那么最后这个[]操作就很容易实现了
五、map与set完整代码
- 红黑树代码
#pragma once enum Color { RED, BLACK }; template<class T> struct RBTreeNode { T _data; RBTreeNode<T>* _left; RBTreeNode<T>* _right; RBTreeNode<T>* _parent; Color _color; RBTreeNode(const T& data) :_data(data) ,_left(nullptr) ,_right(nullptr) ,_parent(nullptr) ,_color(RED) // 插入红色结点，违反规则3，只影响一条路径，甚至可能不影响。如果插入黑色结点，违反规则4，影响所有路径 {} }; template<class T, class Ptr, class Ref> struct __TreeIterator { typedef RBTreeNode<T> Node; typedef __TreeIterator<T, Ptr, Ref> Self; typedef __TreeIterator<T, T*, T&> Iterator; Node* _node; __TreeIterator(Node* node) :_node(node) {} __TreeIterator(const Iterator& it) :_node(it._node) {} Ref operator*() { return _node->_data; } Ptr operator->() { return &_node->_data; } bool operator!=(const Self& s) const { return _node != s._node; } bool operator==(const Self& s) const { return _node == s._node; } Self& operator++() { if (_node->_right) { Node* subLeft = _node->_right; while (subLeft->_left) { subLeft = subLeft->_left; } _node = subLeft; } else { Node* cur = _node; Node* parent = _node->_parent; while (parent) { if (parent->_right == cur) { cur = parent; parent = parent->_parent; } else { break; } } _node = parent; } return *this; } Self& operator--() { if (_node->_left) { Node* subRight = _node->_left; while (subRight->_right) { subRight = subRight->_right; } _node = subRight; } else { Node* cur = _node; Node* parent = cur->_parent; while (parent) { if (parent->_left == cur) { cur = parent; parent = parent->_parent; } else { break; } } _node = parent; } return *this; } }; template<class K, class T, class KeyOfT> class RBTree { typedef RBTreeNode<T> Node; public: typedef __TreeIterator<T,T*,T&> iterator; typedef __TreeIterator<T, const T*, const T&> const_iterator; iterator begin() { Node* leftMin = _root; while (leftMin && leftMin->_left) { leftMin = leftMin->_left; } return iterator(leftMin); } iterator end() { return iterator(nullptr); } const_iterator begin() const { Node* leftMin = _root; while (leftMin && leftMin->_left) { leftMin = leftMin->_left; } return const_iterator(leftMin); } const_iterator end() const { return const_iterator(nullptr); } RBTree() :_root(nullptr) {} Node* Find(const K& key) { Node* cur = _root; KeyOfT kot; while (cur) { if (kot(cur->_data) < key) { cur = cur->_right; } else if (kot(cur->_data) > key) { cur = cur->_left; } else { return cur; } } return nullptr; } pair<iterator,bool> Insert(const T& data) { KeyOfT kot; if (_root == nullptr) { _root = new Node(data); _root->_color = BLACK; //根节点必须是黑色 return make_pair(iterator(_root), true); } Node* cur = _root; Node* parent = nullptr; while (cur) { if (kot(cur->_data) > kot(data)) { parent = cur; cur = cur->_left; } else if (kot(cur->_data) < kot(data)) { parent = cur; cur = cur->_right; } else { return make_pair(iterator(cur), false); } } cur = new Node(data); //插入红色结点 //用于保存新节点的指针 Node* newnode = cur; if (kot(parent->_data) < kot(data)) { parent->_right = cur; } else if (kot(parent->_data) > kot(data)) { parent->_left = cur; } cur->_parent = parent; //开始处理颜色 while (parent && parent->_color == RED) { Node* grandfather = parent->_parent; if (grandfather->_left == parent) { Node* uncle = grandfather->_right; if (uncle && uncle->_color == RED) { parent->_color = BLACK; uncle->_color = BLACK; grandfather->_color = RED; cur = grandfather; parent = grandfather->_parent; } else if (uncle == nullptr || uncle->_color == BLACK) { if (parent->_left == cur) { RotateR(grandfather); parent->_color = BLACK; grandfather->_color = RED; break; } else { RotateL(parent); RotateR(grandfather); cur->_color = BLACK; grandfather->_color = RED; break; } } } else { Node* uncle = grandfather->_left; if (uncle && uncle->_color == RED) { parent->_color = BLACK; uncle->_color = BLACK; grandfather->_color = RED; cur = grandfather; parent = grandfather->_parent; } else if (uncle == nullptr || uncle->_color == BLACK) { if (parent->_right == cur) { RotateL(grandfather); grandfather->_color = RED; parent->_color = BLACK; break; } else { RotateR(parent); RotateL(grandfather); cur->_color = BLACK; grandfather->_color = RED; break; } } } } _root->_color = BLACK; return make_pair(iterator(newnode), true); } void RotateL(Node* parent) { _rotatecount++; Node* cur = parent->_right; Node* curleft = cur->_left; Node* ppnode = parent->_parent; //改变parent parent->_right = curleft; parent->_parent = cur; //改变curleft if (curleft != nullptr) { curleft->_parent = parent; } //改变cur cur->_left = parent; cur->_parent = ppnode; //改变ppnode if (ppnode == nullptr) { _root = cur; } else { if (ppnode->_left == parent) { ppnode->_left = cur; } else { ppnode->_right = cur; } } } void RotateR(Node* parent) { _rotatecount++; Node* cur = parent->_left; Node* curright = cur->_right; Node* ppnode = parent->_parent; //改变parent parent->_left = curright; parent->_parent = cur; //改变curright if (curright != nullptr) { curright->_parent = parent; } //改变cur cur->_right = parent; cur->_parent = ppnode; //改变ppnode if (ppnode == nullptr) { _root = cur; } else { if (ppnode->_left == parent) { ppnode->_left = cur; } else { ppnode->_right = cur; } } } bool IsBalance() { return IsBalance(_root); } bool IsBalance(Node* root) { if (root == nullptr) { return true; } if (root->_color == RED) { return false; } int benchmark = 0; Node* cur = root; while (cur) { if (cur->_color == BLACK) { benchmark++; } cur = cur->_left; } return CheckColor(root, 0, benchmark); } bool CheckColor(Node* root, int blacknum, int benchmark) { //检查每条路径的黑色结点数量是否相等 if (root == nullptr) { if (blacknum != benchmark) { return false; } return true; } if (root->_color == BLACK) { blacknum++; } //检查颜色 if (root->_color == RED && root->_parent && root->_parent->_color == RED) { cout << root->_kv.first << ":" << "出现两个连续的红色结点" << endl; return false; } return CheckColor(root->_left, blacknum, benchmark) && CheckColor(root->_right, blacknum, benchmark); } int Height() { return Height(_root); } int Height(Node* root) { if (root == nullptr) { return 0; } int leftheight = Height(root->_left); int rightheight = Height(root->_right); return leftheight > rightheight ? 1 + leftheight : 1 + rightheight; } int Getrotatecount() { return _rotatecount; } private: Node* _root; int _rotatecount = 0; };
- map代码
#pragma once #include"RBTree.h" namespace Sim { template<class K,class V> class map { public: struct MapKeyOfT { const K& operator()(const pair<K,V>& kv) { return kv.first; } }; typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator; typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator; iterator begin() { return _t.begin(); } iterator end() { return _t.end(); } const_iterator begin() const { return _t.begin(); } const_iterator end() const { return _t.end(); } V& operator[](const K& key) { pair<iterator, bool> ret = insert(make_pair(key, V())); return ret.first->second; } pair<iterator,bool> insert(const pair<const K, V>& kv) { return _t.Insert(kv); } private: RBTree<K, pair<const K, V>, MapKeyOfT> _t; }; }
- set代码
#pragma once #include"RBTree.h" namespace Sim { template<class K> class set { public: struct SetKeyOfT { const K& operator()(const K& key) { return key; } }; typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator; typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator; //iterator begin() //{ // return _t.begin(); //} //iterator end() //{ // return _t.end(); //} const_iterator begin() const { return _t.begin(); } const_iterator end() const { return _t.end(); } pair<iterator,bool> insert(const K& key) { pair<typename RBTree<K, K, SetKeyOfT>::iterator, bool> ret = _t.Insert(key); return pair<iterator, bool>(ret.first, ret.second); } private: RBTree<K, K, SetKeyOfT > _t; }; }
- 测试代码
#define _CRT_SECURE_NO_WARNINGS 1 #include<iostream> #include<map> #include<set> using namespace std; #include "MyMap.h" #include "MySet.h" void func(const Sim::map<int, int>& m) { Sim::map<int, int>::const_iterator itm = m.begin(); while (itm != m.end()) { //itm->first = 1; //itm->second = 1; cout << (*itm).first << " " << itm->second << endl; ++itm; } cout << endl; } void test1() { Sim::map<int, int> m; m.insert(make_pair(1, 1)); m.insert(make_pair(2, 2)); m.insert(make_pair(3, 3)); m.insert(make_pair(5, 5)); m.insert(make_pair(3, 3)); m.insert(make_pair(4, 4)); Sim::map<int, int>::iterator itm = m.begin(); while (itm != m.end()) { itm->second = 1; cout << (*itm).first << " " << itm->second << endl; ++itm; } cout << endl; Sim::set<int> s; s.insert(1); s.insert(2); s.insert(3); s.insert(2); s.insert(5); s.insert(0); Sim::set<int>::iterator it = s.begin(); while (it != s.end()) { //*it += 1; cout << *it << " "; ++it; } cout << endl; } void test2() { Sim::map<int, int> m; m.insert(make_pair(5, 5)); m[1] = 2; m[2] = 3; m[4] = 5; m[5] = 1; Sim::map<int, int>::iterator itm = m.begin(); while (itm != m.end()) { cout << (*itm).first << " " << itm->second << endl; ++itm; } cout << endl; } int main() { test2(); return 0; }
