【C++】封装map和set（红黑树实现）

前言：

       前面，我们学习了set和map的用法，这两个容器可以完成查找，排序等操作，后来我们在学习过二叉搜索树的基础上又学习了两种特殊的二叉搜索树——AVL树和红黑树，他们俩可以是效率进一步提高，其实set和map的底层就是由红黑树封装而成的！

       所以，本篇文章我们自己学习用红黑树封装set和map。用红黑树封装，特别是用同一棵红黑树实现封装有一定的难度，其中很多操作（比如复用）我们会第一次尝试，所以大家请跟紧作者的脚步来。

目录

（一）如何复用同一棵红黑树

（二）红黑树的改造流程（为封装做铺垫）

1、结点的定义

2、模拟实现结点的比较大小

3、改造后的红黑树

4、map和set迭代器的模拟实现

4.1模版参数的构成

4.2begin()和end()的模拟实现

4.3operator* 和 operator->模拟实现

4.4 operator++ 和 operator--模拟实现

4.5 operator== 和 operator!=模拟实现

4.6迭代器代码详解

 （三）封装map和set

---

（一）如何复用同一棵红黑树

前提疑问：

在我们这所有的之前我们知道，map和set这两个容器都是用红黑树来实现的，那么就有了接下来的问题。

• map和set都是用的同一棵红黑树复用的吗
• 或者这两个容器各自使用一棵红黑树吗

其实在前言中我们就知道了，根据STL的设计理念和泛型编程的理念，我们不会冗余的写两课红黑树，而是用一棵红黑树实现复用的效果。

我们调用STL库中的原码来看：

我们发现：

• STL库中的原码也确实调用的同一棵红黑树
• 他们实现的都是key_value模型

我们设set中存放结点的值是K，map中存放的节点是pair<key,value>键值对：

• 对于set而言，底层红黑树的模版就是RBTree<K, K>
• 对于map而言，底层红黑树的模版就是RBTree<K, pair<K, V>>

这时我们就有了另一个疑问，两个模板参数的第一个Key，不能省略掉吗？？

• 首先，答案肯定是不能的
• 那么原因又是什么呢？

因为map的这个类中，无论怎么省略都会有一个查找函数要单独用到Key

如果第一个Key删去了，那么map和set的查找函数就没法统一实现了，违背了我们一开始泛型编程的思想。

综上所述：

• map和set都是用了，Key_value模型
• set中的K是K，V也是K
• map中的K是K，V是pair<K，V>
• 并且模板参数中第一个K都不能省

（二）红黑树的改造流程（为封装做铺垫）

1、结点的定义

这里由于set和map存放的结点一个是Key一个是pair<Key,Value>，所以我们使用模版，把存放的结点泛化。

2、模拟实现结点的比较大小

• 上述提到，在模拟实现中，map和set我们复用同一棵红黑树的时候都是用的是Kye_value的结构
• 但是红黑树中的数据比较又是Key值的比较，而现在我们用的则是pair的比较
• 虽然编译上是可以通过但是真的就是我们所想要的吗？

pair的比较大小：

很显然这种比较规则不是我们所想要的，并且map和set想要取到用来比较的数据是不同的。 

为了取到我们想要的数据，我们引入了仿函数：

• 根据map和set的需求不同
• 我们在红黑树中新引入了一个模板参数KeyOfT

 

引入KeyOfT模板参数后，我们想要不同方式的比较方法只需要在set和map的封装中给出属于他们自己的比较仿函数。

map中的仿函数： 

set中的仿函数：

使用方法：

 此时前面所说的仿函数的便利之处就体现出来了。

3、改造后的红黑树

具体代码：

//红黑树的实现
//KeyOfT --> 支持取出T对象中key的仿函数
template<class K, class T, class KeyOfT>
class RBTree
{typedef RBTreeNode<T> Node;
public:typedef __RBTreeIterator<T, T&, T*> iterator;typedef __RBTreeIterator<T, const T&, const T*> const_iterator;//构造 拷贝构造 赋值 和析构 跟搜索树实现方式是一样的//迭代器中序遍历，要找最左结点iterator Begin(){Node* subLeft = _root;while (subLeft && subLeft->_left){subLeft = subLeft->_left;}//树的迭代器用结点的指针就可以构造return iterator(subLeft);}iterator End(){return iterator(nullptr);}const_iterator Begin() const{Node* subLeft = _root;while (subLeft && subLeft->_left){subLeft = subLeft->_left;}//树的迭代器用结点的指针就可以构造return const_iterator(subLeft);}const_iterator End() const{return const_iterator(nullptr);}pair<iterator, bool> Insert(const T& data){//1、搜索树的规则插入//2、看是否违反平衡规则，如果违反就需要处理：旋转if (_root == nullptr){_root = new Node(data);_root->_col = BLACK; //根节点是黑色return make_pair(iterator(_root), true);}KeyOfT kot;Node* parent = nullptr;Node* cur = _root;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* newnode = cur;cur->_col = RED;if (kot(parent->_data) < kot(data)){parent->_right = cur;}else{parent->_left = cur;}//三叉链的链接 -- 链上父节点cur->_parent = parent;//存在连续红色结点while (parent && parent->_col == RED){//理论而言，祖父是一定存在的，父亲存在且是红不可能是根（根一定是黑的）Node* grandfather = parent->_parent;assert(grandfather);if (grandfather->_left == parent){Node* uncle = grandfather->_right;//情况一：（叔叔存在且为红）if (uncle && uncle->_col == RED){//祖父和叔叔变成黑色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续往上处理cur = grandfather;parent = cur->_parent;}//情况二：（叔叔不存在 or 叔叔存在且为黑）else{//单旋//	   g//	 p// cif (cur == parent->_left){RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}//双旋//    g//  p//    celse{RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}//无论父亲和叔叔是左是右都是一样的//grandfather->_right == parent;else{Node* uncle = grandfather->_left;//情况一：if (uncle && uncle->_col == RED){//祖父和叔叔变成黑色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续往上处理cur = grandfather;parent = cur->_parent;}else{//单旋// g//   p//     cif (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}//双旋//  g//    p//  celse{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}//父亲为空就出循环，将根节点设置成黑色_root->_col = BLACK;return make_pair(iterator(newnode), true);}
}

插入（Insert）和寻找（Find）代码：
 

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<itertaor, bool> Insert(const T& data){if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return make_pair(itertaor(_root), true);}KeyOfT kot;Node* parent = nullptr;Node* cur = _root;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(itertaor(cur), false);}}cur = new Node(data);Node* newnode = cur;if (kot(parent->_data) > kot(data)){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;while (parent && parent->_col == RED){Node* grandfather = parent->_parent;if (grandfather->_left == parent){Node* uncle = grandfather->_right;// 情况1：u存在且为红，变色处理，并继续往上处理if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;// 继续往上调整cur = grandfather;parent = cur->_parent;}else // 情况2+3：u不存在/u存在且为黑，旋转+变色{//     g//   p   u// c if (cur == parent->_left){RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//     g//   p   u//     cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;//parent->_col = RED;grandfather->_col = RED;}break;}}else // (grandfather->_right == parent){//    g//  u   p//        cNode* uncle = grandfather->_left;// 情况1：u存在且为红，变色处理，并继续往上处理if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;// 继续往上调整cur = grandfather;parent = cur->_parent;}else // 情况2+3：u不存在/u存在且为黑，旋转+变色{//    g//  u   p//        cif (cur == parent->_right){RotateL(grandfather);grandfather->_col = RED;parent->_col = BLACK;}else{//    g//  u   p//    cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return make_pair(itertaor(newnode), true);;}

4、map和set迭代器的模拟实现

上面改造后的红黑树中已经涉及到了迭代器，这里我们来模拟实现。

备注：

• T：数据
• Ref：引用
• Ptr：指针
• Sef：iterator本身

4.1模版参数的构成

要想实现同一棵红黑树的复用，模版参数的构成极为重要。

之前我们也遇到过相似的情况，我们这里的实现方法参看之前。

迭代器的实现中：

• 涉及到了*解引用操作，返回的是数据的引用；
• 涉及到了->指针操作，返回的是数据的地址;
• 涉及到++，--操作，返回的是操作后迭代器本身的位置。

但是以上的行为，我们都涉及结点，所以结点的数据类型也尤为重要！

综上，模版参数的构成如下图：

4.2begin()和end()的模拟实现

• 因为是二叉搜索树，为了更有顺序，所以我们采取的是中序遍历。
• 那么中序遍历Begin（）就应该是最左结点
• 我们实现的版本中End（）定义为空是（nullptr）

ps：

而库中的红黑树则是设计了一个哨兵位的头结点：

所以我们实现的只是简化版本。

4.3operator* 和 operator->模拟实现

就是正常的运用operator，但是operator->和list中讲的一样，返回的是地址的原因是为了连续访问（连续的operator->会优化成一个->）

4.4 operator++ 和 operator--模拟实现

这里迭代器的++和- - 需要分类一下，分别是：前置++，- - 、后置++，- -

前置++ ：
因为我们是中序遍历，我们访问完自己之后，下一个该访问哪一个结点？

我们观察任何一棵二叉树都能看出，无非是下面两种情况：

分如下两种情况：（重点）

• 右子树为空：找孩子是父亲的左的那个祖先节点，否则继续往上走，直到空（nullptr）
• 右子树为非空：找右子树的最左节点

这一过程有点类似于递归思想，但是是非递归实现的

代码实现：

 前置-- ：

有了上面的思路，我们联想一下，现在需要看当前位置左子树是否是空。

前置- -就是倒着走，同样还是对当前位置分两种情况：（重点）

1. 左子树为空：找孩子是父亲的右的那个祖先节点，否则继续往上走，直到空（nullptr）
2. 左子树为非空：找左子树的最右节点

只要前置++理解了，那么前置- -完全就是前置++倒过来走一遍。

后置++、后置- - ：

和之前实现容器的得带器一样，我们这里直接复用即可：

4.5 operator== 和 operator!=模拟实现

有了之前封装迭代器的经验，这两个的视线还是比较容易得：

4.6迭代器代码详解

template<class T, class Ref, class Ptr>
struct __RBTreeIterator
{typedef RBTreeNode<T> Node;Node* _node;typedef __RBTreeIterator<T, Ref, Ptr> Self;__RBTreeIterator(Node* node):_node(node){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}Self& operator++(){if (_node->_right == nullptr){//找祖先里面，孩子是父亲左的那个Node* cur = _node;Node* parent = cur->_parent;while (parent && parent->_right == cur){cur = cur->_parent;parent = parent->_parent;}_node = parent;}else{//右子树的最左结点Node* subLeft = _node->_right;while (subLeft->_left){subLeft = subLeft->_left;}//左为空_node = subLeft;}return *this;}Self& operator--(){if (_node->_left == nullptr){//找祖先里面，孩子是父亲Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_left){cur = cur->_parent;parent = parent->_parent;}_node = parent;}else{//左子树的最右结点Node* subRight = _node->_left;while (subRight->_right){subRight = subRight->_right;}_node = subRight;}return *this;}Self operator++(int){Self tmp(*this);++(*this);return tmp;}Self operator--(int){Self tmp(*this);--(*this);return tmp;}bool operator!=(const Self& s) const{return _node != s._node;}bool operator==(const Self& s) const{return _node == s._node;}
};

 （三）封装map和set

有了上面的红黑树的改装，我们这里的对map和set的封装就显得很得心应手了。

封装主要是把map和set的基本操作封装在一个类中。

map的封装：

template<class K, class V>
class map
{//定义一个内部类struct MapKeyOfT{const K& operator()(const pair<K, V>& kv)//operator() 可以像函数一样去使用{return kv.first;}};public:typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator;typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::const_iterator const_iterator;iterator begin(){return _t.Begin();}iterator end(){return _t.End();}pair<iterator, bool> insert(const pair<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<K, V>, MapKeyOfT> _t;
};

这里map中的operator[ ]我们知道其原理之后，模拟实现就非常方便，直接调用插入函数，控制好参数和返回值即可。

对set的封装：

template<class K>
class set    
{struct SetKeyOfT{const K& operator()(const K& key)//operator() 可以像函数一样去使用{return key;}};
public://加上typename告诉编译器这是个类型，类模板实例化了再去取typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;iterator begin() const{return _t.Begin();}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);auto ret = _t.Insert(key);return pair<iterator, bool>(iterator(ret.first._node), ret.second);}iterator find(const K& key){return _t.Find(key);}private:RBTree<K, K, SetKeyOfT> _t;
};

附详细代码：——》红黑树封装map和set