文章目录
前言一、STL源码分析二、红黑树的构建三、map与set整体框架的搭建与解析四、如何取出进行比较？1. met与set的数据是不同的2. 取出数据进行比较1）问题发现2）仿函数解决 五、封装插入六、迭代器的实现1. operator* 与operator->2. operator!=3. operator++4. operator- -5. 套用普通迭代器 七、const迭代器八、查找总结
前言
之前我们学习了红黑树的实现，现在我们一起来看一看如何使用红黑树封装出set与map~~~
一、STL源码分析
我们一起来分析分析STL源码，看一看库中是如何实现的??
首先，库里面stl_set与stl_map中，
对于set来说，key_type是key，value_type也是key，也就是说set是一个rbTree<Key, Key>的模型。
对于map来说，key_type是key，但是value_type是pair<const key, T>，也就是说map是一个rbTree<Key, pair<Key, Value>>的模型。
我们再来看一下rb_tree的结构：
rb_tree中，前两个参数是<key, value>，而__rb_tree_node<value>里面的参数传的是value，因此我们可以总结出，这里map的结点中存储的是pair<key, value>，而set的结点中存储的是key。
那么到底为什么是这样的结构呢？
我们将在下面的讲解中逐一解释?
二、红黑树的构建
对于红黑树的构建，J桑之前的文章有详细的讲解，因此这里就直接给出代码啦，还不清楚的观众老爷门可以点击下方的传送门???
深入探索：C++红黑树原理与实现
当然，我们之前红黑树是默认存储pair，现在要同时满足map与set，因此一些地方需要改变，之后总结的时候会给出完整的更改后的代码，下面讲解也会被提到。
#pragma once#include<iostream>using namespace std;enum Colour{RED,BLACK};template<class K, class V>struct RBTreeNode{pair<K, V> _kv;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;Colour _col;RBTreeNode(const pair<K, V>& kv): _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED){}};template<class K, class V> class RBTree{typedef RBTreeNode<K, V> Node;public:bool Insert(const pair<K, V>& kv){// 树为空，直接插入然后返回if (_root == nullptr){_root = new Node(kv);// 根节点必须是黑色_root->_col = BLACK;return true;}Node* cur = _root;Node* parent = nullptr;while (cur){// 小于往左走if (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else if (kv.first > cur->_kv.first) // 大于往右走{parent = cur;cur = cur->_right;}else{return false;}}cur = new Node(kv);// 其他结点初始颜色为红色cur->_col = RED;// 链接if (cur->_kv.first < parent->_kv.first){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;// 如果我们parent是黑色，不用处理，就结束了// 情况一：cur为红，parent为红，grandfather为黑，uncle不确定// 用while循环是因为我们要不断的向上调整while (parent && parent->_col == RED){// 首先我们要找到grandfatherNode* grandfather = parent->_parent;// 接下来通过grandfather找到uncle//如果parent是grandfather->_leftif (parent == grandfather->_left){// 说明uncle在右边Node* uncle = grandfather->_right;// uncle存在且为红if (uncle && uncle->_col == RED){// 满足上述情况，开始调整颜色parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;// 继续向上调整cur = grandfather;parent = cur->_parent;// 但是走到这里有一个问题，如果当前parent就是根，// 并且parent是红色，我们要把它变为黑色，// 处理方式是：出循环后，暴力将_root->_col变为黑色}else // uncle不存在 或 uncle存在且为黑色{// 判断要怎样旋转// 右单旋if (cur == parent->_left){// g// p// cRotateR(grandfather);// 调整颜色parent->_col = BLACK;grandfather->_col = RED;}else // 左右双旋{// g// p//cRotateL(parent);RotateR(grandfather);// 调整颜色cur->_col = BLACK;grandfather->_col = RED;}// 旋转变色完就结束了，这里不加这个也可以，条件判断就会退出break;}}else //(parent == grandfather->_right) // 如果parent是grandfather->_right{// 说明uncle在左边Node* uncle = grandfather->_left;// uncle存在且为红if (uncle && uncle->_col == RED){// 满足上述情况，开始调整颜色parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;// 继续向上调整cur = grandfather;parent = cur->_parent;}else // uncle不存在 或 uncle存在且为黑色{// 判断要怎样旋转// 左单旋if (cur == parent->_right){// g// p// cRotateL(grandfather);// 调整颜色parent->_col = BLACK;grandfather->_col = RED;}else // 右左双旋{// g// p// cRotateR(parent);RotateL(grandfather);// 调整颜色cur->_col = BLACK;grandfather->_col = RED;}break;}}}// 这里保证根为黑色_root->_col = BLACK;return true;}// 左单旋void RotateL(Node* parent){Node* cur = parent->_right;Node* curleft = cur->_left;// 重新链接parent->_right = curleft;if (curleft) // 如果curleft存在{curleft->_parent = parent;}cur->_left = parent;Node* ppnode = parent->_parent;parent->_parent = cur;if (ppnode == nullptr){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}}// 右单旋void RotateR(Node* parent){Node* cur = parent->_left;Node* curright = cur->_right;parent->_left = curright;if (curright){curright->_parent = parent;}cur->_right = parent;Node* ppnode = parent->_parent;parent->_parent = cur;if (ppnode == nullptr){cur->_parent = nullptr;_root = cur;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}}// 检查是否构建正确bool CheckColour(Node* root, int blacknum, int benchmark){if (root == nullptr){if (blacknum != benchmark)return false;return true;}if (root->_col == BLACK){++blacknum;}if (root->_col == RED && root->_parent && root->_parent->_col == RED){cout << root->_kv.first << "出现连续红色节点" << endl;return false;}return CheckColour(root->_left, blacknum, benchmark)&& CheckColour(root->_right, blacknum, benchmark);}bool IsBalance(){return IsBalance(_root);}bool IsBalance(Node* root){if (root == nullptr)return true;if (root->_col != BLACK){return false;}// 基准值int benchmark = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK)++benchmark;cur = cur->_left;}return CheckColour(root, 0, benchmark);}private:Node* _root = nullptr;};三、map与set整体框架的搭建与解析
代码：
namespace jyf{template<class k, class v>class map{public:private:RBTree<k, pair<k, v>> _t;};}namespace jyf{template<class k>class set{public:private:RBTree<k, k> _t;};}解析：
首先无论是map还是set都有两个模板参数，第一个是key，这个key是多存的，它的作用体现在像find()这样的函数中，我们后面在做解析。
这里先看第二个参数，传给了RBTree的T，而T就是结点中储存的东西，也就是说，你是set，那么节点中就储存的是key, 你是map，那么节点中就储存的是pair<k, v>。
四、如何取出进行比较？
1. met与set的数据是不同的
我们要明白一个我问题，met与set结点中存储的数据是不一样的，因此，如果节点中还存储的是pair就不对了，因此，我们结点之中存储的数据因该是T类型的数据，如果是set就是key,如果是map就是pair。
2. 取出数据进行比较
1）问题发现
再insert函数中，我们之前的红黑树是这样实现的，比如这个找到插入位置的逻辑：
在这张图片里面，我们之前使用pair，但是现在对于map和set存储的数据不同，因此需要用data来比较。
但是！！！
对于map来说，它的value是pair，但是pair的比较逻辑能满足我们的需要吗？
可以看到，pair的比较逻辑是先比first，first一样就比second，但是，我们这里不需要比较second，key_value的模型中，只需要比较key不同，因此我们需要一种方法，重新定义我们的比较。
怎么重新比较呢？
这里我们通过观察发现，对于set来说，它的data是key，可以直接比较，唯一有问题的是map，因此我们采取的方式是仿函数。
2）仿函数解决
我们可以多定义一个模板参数KeyOfT，这个模板参数用来定义仿函数，他的作用是取出Set或Map中的Key。
对于Set，它的data直接就是key：
struct SetKeyOfT{const K& operator()(const K& key){return key;}};对于Map，它的data是一个pair，我们需要pair的first，也就是key：
struct MapKeyOfT{const K& operator()(const pair<K,V>& kv){return kv.first;}};
至此，我们在取出数据的时候，只要定义出一个对象，重载operator()，用()将data包起来，就得到了我们想要的数据。
可以说，这里set迁就了map~
五、封装插入
完成了上述步骤，我们就可以实现封装map与set的插入了~
对于set:
bool insert(const K& key){return _t.Insert(key);}对于map:
bool insert(const pair<K,V>& kv){return _t.Insert(kv);}插入结果：
六、迭代器的实现
要实现迭代器，就要先理解迭代器是怎么用的：
下面是一个模板表示迭代器的使用：
it = s.begin();while (it != s.end()){ cout << *it << endl; ++it;}为了实现这个过程，我们需要重载很多东西。
我们先将框架搭出来：
template<class T>struct __TreeIterator{typedef RBTreeNode<T> Node;typedef __TreeIterator<T> Self;Node* _node;__TreeIterator(Node* node):_node(node){}};1. operator* 与operator->
RBTree中：
T& operator* (){return _node->_data;}T* operator-> (){return &(_node->_data);}2. operator!=
bool operator!= (const Self& s){return _node != s._node;}3. operator++
对于树的迭代器，++与- -就非常重要了，这里有很多坑~
首先对于一个红黑树，他走的是中序的排序，图如下：
那么，it.begin()是谁呢？
我们说中序是左-根-右，也就是说，begin应该是上图中的1。
其次，如果我们进行++操作，迭代器会到那里去呢？
这里分以下几种情况：
那么下一个访问的，将是右树的最左：
如果右为空
这里又分两种情况：
cur是parent的左——下一个访问parent
cur是parent的右——下一个访问没有被访问的祖先
通过观察这两种情况我们可以发现：
也就是说，当右为空的时候，下一个访问的是孩子是父亲的左侧的那一个祖先。
代码总结：
Self& operator++ (){if (_node->_right != nullptr){Node* curleft = _node->_right;while (curleft->_left){curleft = curleft->_left;}_node = curleft;}else{// 找孩子是父亲左的那个祖先节点，就是下一个要访问的节点Node* cur = _node;Node* parent = _node->_parent;while (parent){if (parent->_left == cur){break;}else{cur = parent;parent = parent->_parent;}}_node = parent;}return *this;}4. operator- -
原理与++是一样的，只不过原本++的顺序是中序，即左-根-右，- - 是反过来的，因此是右-根-左
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 && cur == parent->_left){cur = cur->_parent;parent = parent->_parent;}_node = parent;}return *this;}5. 套用普通迭代器
RBTree中：
经过前面的分析，begin就是树最左边的结点，end我们设置为nullptr。
typedef __TreeIterator<T> iterator;public:iterator begin(){Node* leftMin = _root;while (leftMin && leftMin->_left){leftMin = leftMin->_left;}return iterator(leftMin);}iterator end(){return iterator(nullptr);}set与map中，我们要封装这个方法：
iterator begin(){return _t.begin();}iterator end(){return _t.end();}测试普通迭代器：
jyf::map<int, int> m;m.insert(make_pair(1, 1));m.insert(make_pair(3, 3));m.insert(make_pair(2, 2));jyf::map<int, int>::iterator mit = m.begin();while (mit != m.end()){mit->first = 1;mit->second = 2;cout << mit->first << ":" << mit->second << endl;++mit;}cout << endl;for (const auto& kv : m){cout << kv.first << ":" << kv.second << endl;}cout << endl;jyf::set<int> s;s.insert(5);s.insert(2);s.insert(2);s.insert(12);s.insert(22);s.insert(332);s.insert(7);auto it = s.begin();while (it != s.end()){// Ӧif (*it % 2 == 0){*it += 10;}cout << *it << " ";++it;}cout << endl;for (const auto& e : s){cout << e << " ";}cout << endl;结果为：
七、const迭代器
我们知道set是不允许修改的，map的key不允许修改，而value允许修改，再通过观察库中的实现，我们可以发现:
set实现不能修改的原因是——interator迭代器与const_iterator都是const迭代器。
而map实现key不能修改，value可以修改的方法是，在定义map的value的时候，pair<K, V>修改为pair<const K, V>
具体的逻辑我们下一次在进行讲解~
八、查找
查找是通过key来查找的，而不是通过value来查找的，这也就解释了为什么最开始定义模板参数还要多定义一个key。
同样，为了取出对应的值，我们也需要仿函数来包上data。
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;}总结
红黑树在 STL 的应用
set 与 map 的实现：
set 节点存储 key（rbTree<Key, Key> 模型）。
map 节点存储 pair<const Key, T>（rbTree<Key, pair<Key, Value>> 模型）。
rbTree 的设计：
节点使用 __rb_tree_node，value 的具体含义根据容器类型不同而不同。
