C++：用红黑树封装map与set-1

---

前言

之前我们学习了红黑树的实现，现在我们一起来看一看如何使用红黑树封装出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。

其次，如果我们进行++操作，迭代器会到那里去呢？
这里分以下几种情况：

1. 如果右不为空

那么下一个访问的，将是右树的最左：

---

2. 如果右为空

这里又分两种情况：

• 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 的具体含义根据容器类型不同而不同。