【C++】红黑树的封装——同时实现map和set

在list模拟实现一文中，介绍了如何使用同一份代码封装出list的普通迭代器和const迭代器。今天学习STL中两个关联式容器map和set，其底层就是红黑树，而且是同一棵红黑树。所以今天学习如何用同一棵红黑树封装出map和set。

红黑树的完善

默认成员函数

map和set的底层是红黑树，所以先将红黑树重要的四个默认成员函数完善好。这四个成员函数在介绍搜索二叉树时已进行过介绍，这里不再讲解。

public://RBTree() = default;RBTree():_root(nullptr){}RBTree(const RBTree& t)//拷贝构造{_root = Copy(t._root);}RBTree& operator=(RBTree t)//赋值重载{swap(_root, t._root);return *this;}~RBTree(){Destroy(_root);_root = nullptr;}
private:Node* Copy(Node* root){if (root == nullptr){return nullptr;}Node* newnode = new Node(root->_kv);newnode->_left = Copy(root->_left);newnode->_right = Copy(root->_right);return newnode;//返回时才连接}void Destroy(Node* root){if (root == nullptr){return;}Destroy(root->_left);Destroy(root->_right);delete root;}

迭代器的增加

map和set作为关联式容器，迭代器是必不可少的，而map和set都是由同一颗红黑树封装而成，所以，map和set的迭代器其实就是红黑树的迭代器。

map和set的迭代器都是双向迭代器，也就是说都支持++，- -的操作。

红黑树的迭代器的结构和list的是类似的，其成员都只有一个节点类，只有一个构造函数初始化节点。

迭代器：

template<class T, class Ref, class Ptr>
struct RBTreeIterator
{typedef RBTreeNode<T> Node;typedef RBTreeIterator<T,Ref,Ptr> self;Node* _node;//成员RBTreeIterator(Node* node):_node(node){}
};

节点类：

template<class T>
struct RBTreeNode
{T _kv;RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;Color _col;RBTreeNode(const T& kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED)//默认为红色{}};

对于自封装的迭代器：解引用，是否相等的比较是少不了的，而这部分操作还是比较容易的，不理解的可参考list迭代器的实现

• 注意此时要访问的的对象是_kv

	Ref operator*(){return _node->_kv;}Ptr operator->(){return &_node->_kv;}bool operator==(const self& s){return _node == s._node;}bool operator!=(const self& s){return _node != s._node;}

真正的难点是红黑是迭代器的遍历：中序遍历红黑树便能得到一个升序序列，而迭代器访问的顺序也是中序：左根右。采用Inorde来遍历是很简单的，但是它是不可控的，只能一把把红黑树全遍历完。而迭代器必须是一个一个节点访问的，这就增加了它实现的难度。

前置++

对于++，即按中序访问下一个节点，但查找时此时的节点已经为根，所以查找的顺序为根，右；此时关注的点是下一个节点是否为空，由此分为两种情况。

• 右子树不为空；则，右子树的最左节点即为下一个要访问的节点。
• 右子树为空，说明当前子树已经访问完了；沿着到根节点的路径查找祖先节点中左孩子为父亲的节点即为下一个要访问的节点。
  • 如果父节点为祖先节点的右孩子，说明递归有一定深度，需要不断向上查找。

	self& operator++(){if (_node->_right){Node* leftMost = _node->_right;while (leftMost->_left){leftMost = leftMost->_left;}_node = leftMost;//return self(leftMost);}else//说明当前子树访问完了{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right){cur = parent;parent = parent->_parent;}//return self(parent);_node = parent;}return *this;}

前置++可以引用返回。

后置++

后置++逻辑与前置是一样的，只不过返回的是++之前的值。所以用ret保留原先的值，再访问下一个节点，最后返回ret即可。此时不能引用返回。

	self operator++(int){self ret = *this;if (_node->_right){Node* leftMost = _node->_right;while (leftMost->_left){leftMost = leftMost->_left;}_node = leftMost;}else//说明当前子树访问完了{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right){cur = parent;parent = parent->_parent;}_node = parent;}return ret;}

前置- -

红黑树的- -即访问当前节点的前一个节点。此时的查找顺序变为根，左；自身就作为根节点，所以此时只需要注意左节点是否为空。

• 左节点不为空，则按右根左的遍历顺序遍历；访问左子树的最右孩子。
• 左节点为空，说明当前子树已经访问完了；沿着到根节点的路径查找祖先节点中右孩子为父亲的节点即为下一个要访问的节点。
  • 如果父节点为祖先节点的左孩子，说明递归有一定深度，需要不断向上查找

    self& operator--(){if (_node->_left){Node* rightMost = _node->_left;while (rightMost->_right){rightMost = rightMost->_right;}_node = rightMost;}else//说明当前子树访问完了{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_left){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}

后置- -

返回- -之前的节点。

	self operator--(int){Node* ret = *this;if (_node->_left){Node* rightMost = _node->_left;while (rightMost->_right){rightMost = rightMost->_right;}_node = rightMost;}else//说明当前子树访问完了{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_left){cur = parent;parent = parent->_parent;}_node = parent;}return ret;}

迭代器实现后，我们需要在红黑树的实现当中进行迭代器类型的typedef。需要注意的是，为了让外部能够使用typedef后的迭代器类型iterator，需要在public区域进行typedef。

然后在红黑树当中实现成员函数begin和end：

• begin函数返回中序序列当中第一个结点的迭代器，即最左结点。
• end函数返回中序序列当中最后一个结点下一个位置的迭代器，这里直接用空指针构造一个迭代器。

实现时红黑树一层命名为与map和set作区分，首字母大写。

template<class K, class T,class KeyOfT>//map时T为pair，set时为K
class RBTree
{typedef RBTreeNode<T> Node;
public:typedef RBTreeIterator<T, T&, T*> Iterator;typedef RBTreeIterator<T, const T&, const T*> Const_Iterator;//map和set的迭代器也是使用红黑树的迭代器，但树的结构有所区别。//红黑树的迭代器Iterator Begin(){Node* leftMost = _root;while (leftMost->_left){leftMost = leftMost->_left;}return leftMost;//此时返回的是节点，而返回类型为迭代器，所以会发生隐式类型转化，调用红黑树的迭代器构造函数构造一个迭代器}Iterator End()//与库里的带头红黑树不同，我们这里不带头，为空即尾{return nullptr;}Const_Iterator Begin()const{Node* leftMost = _root;while (leftMost->_left){leftMost = leftMost->_left;}return leftMost;}Const_Iterator End()const//与库里的带头红黑树不同，我们这里不带头，为空即尾{return nullptr;}private:Node* _root = nullptr;};

库中红黑树的结构实现

库里的红黑树结构中还有一个头节点header，header的parent指针指向_root,_root的parent指针指向header，header的左右指针分别指向红黑树的最小和最大节点。

由于结构不同，所以我们迭代器的实现也有一定缺陷，但不妨碍正常使用，所以就不进行完善了。

红黑树的封装

都知道set是key模型，而map是key_value模型，如何才能使用同一棵红黑树满足二者的需求呢？这就是封装的魅力。

了解map和set之后，两者的冲突点主要有：

1. map是KV模型，set的K模型
2. 获取Key
   • map和set储存数据的方式不一样；红黑树的大多数操作都是需要支持用Key比大小的。
3. map和set的Key不可修改问题

红黑树模板参数的控制

关于set和map的不同模型问题，先看看库中是如何解决这个问题的。

对于红黑树而言，它是不知道上层是map还是set的，但是这些都不重要；底层红黑树利用泛型的思想，将map和set传过来的参数实例化为模板；这样一来，上层map传对应的参数过来，底层红黑树就将这些参数泛化成模板，就能生成对应数据类型的红黑树了；set也是同理。

如简化版的下图：map和set的底层都是一棵红黑树，其中map和set中的红黑树传入的第一个参数都为K；而map的第二个参数传入的是一个键值对pair，这也正是map的数据类型。set的第二个参数继续传入一个K，作为set的数据类型。也正是这样的设计，能够让一棵红黑树同时封装map和set。

这样一来，你上层传的是pair，底层红黑树实例出来的就是map，传入的为K，则为set。

• 第三个模板参数是解决下一个问题所提供的仿函数。

set中调用的红黑树为什么要传两次K？

• set中传两次K确实有点多余，但此时是map和set共用一棵红黑树，在map的日常使用中如：find，erase这样的操作，其参数就是一个K类型，所以map中是需要有K的。

• 

• 

仿函数解决取K问题

所谓取K，就是由于map和set的数据类型不一致，一个是KV的键值对，一个是模板参数K。作为而平衡二叉树的红黑树，Key值的比对是少不了的，如插入，查找等功能都是需要有Key值的比对的。对于set来说，可以直接用传入的K进行比对；而map是pair，需要解引用访问其first才能找到Key，否则直接比对pair不一定是我们想要的比对结果。

所以，为了解决这个问题，继续参考上一个问题的解决方式：在map和set调用红黑树传参时传入一个可以取Key的仿函数。仿函数介绍

map的仿函数：要获取是数据是什么类型，仿函数的参数就是什么类型。

		struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};

set的仿函数：set的仿函数看起来有点多此一举，但为了适配map的解决，提供一个仿函数也无妨。

		struct SetKeyOfT{const K& operator()(const K& key){return key;}};

这样一来，set容器传入底层红黑树的就是set的仿函数，map容器传入底层红黑树的就是map的仿函数。

有了仿函数，当底层红黑树需要进行两个结点之间键值的比较时，都会通过传入的仿函数来获取相应结点的键值，然后再进行比较，下面以红黑树的查找函数为例。

Iterator Find(const T& data){KeyOfT kot;if (_root == nullptr){return nullptr;}Node* cur = _root;//Node* parent = nullptr;while (cur){if (kot(data) > kot(cur->_kv)){//parent = cur;cur = cur->_right;}else if (kot(data) < kot(cur->_kv)){//parent = cur;cur = cur->_left;}else{return cur;}}return nullptr;}

对Key的非法操作

map和set都是不支持修改Key的

map对此的解决方案是pair对中的Key用const修饰

map成员的定义：

private:RBTree<K, pair<const K, V>, MapKeyOfT> _rbt;

set将红黑树的第二个参数改为const K好像也能解决问题，但库里并没有采用这种方法。

简易办法：使用const K禁止被修改。目前还没发现什么大问题，如果发现问题请告知
set成员的定义：

	private:RBTree<K,const K, SetKeyOfT> _rbt;

第二种就是采用库里的方法。
set无论普通还是const迭代器都使用红黑树的const迭代器

public://库里的方法：typedef typename RBTree<K, K, SetKeyOfT>::Const_Iterator iterator;typedef typename RBTree<K, K, SetKeyOfT>::Const_Iterator const_iterator;

但是这样就会出现类型转化问题

原因如下：

这里的迭代器不是原生指针的迭代器，而是通过封装而来的，借助模板实现了const和非const版的迭代器；也就导致普通的无法转为const迭代器；通过调试发现问题出现在获取迭代器上，由于set的普通迭代器也由const迭代器封装而来，set在获取普通迭代器时，最底层的红黑树返回的是普通迭代器，但set的普通迭代器实际为const迭代器，此时就发生了类型不匹配的问题。

对此，库中提供了如下解决方案：在红黑树迭代器中提供一个构造函数

在红黑树迭代器中增加一个参数为普通迭代器类型的构造函数。该构造函数取参数中普通迭代器的节点重新构造一个迭代器（const版）。该方法绕过转化，采用构造，生成一个const版的迭代器，自然就没有类型转化的问题。

虽然这个构造函数增加在红黑树的迭代器中，但是map的迭代器不会有影响，这个构造函数只会匹配到set对应的状况。

	typedef RBTreeIterator<T, T&, T*> Iterator;	//声明类型：普通迭代器RBTreeIterator(const Iterator& it)//类型为普通迭代器，因为就是由于普通迭代器转化为const迭代器这一环出了                   问题，这里专门针对这一情况处理:_node(it._node)//此时需要的是一个const迭代器，（由于模板无法转化？）普通转const直接转化不行，那么我们就在返回时利用隐式类型转化{}

具体过程请看下图。

insert的调整

在AVL树红黑树阶段实现的insert的返回值都为bool，在map和set中则是改为返回键值对pair。

以map为例：

函数声明：

pair<iterator,bool> insert (const value_type& val);

可以看到其返回值为pair，pair的第一个成员为一个迭代器指向新插入的元素，或者已存在的等效元素，第二个成员为bool，用来检测插入是否成功；也就是说insert成功的话会返回一个指向新插入元素的迭代器，其bool值为true的pair，如果insert失败则会返回一个指向容器中原有的K的迭代器，其bool值为false的pair。

map的[]运算符重载

map支持[]访问容器中Key值并返回Key对应的Value；set不支持[]重载，因为只有一个Key。

也就是说[]的参数为pair中的第一个成员K，其使用说明如下：

如果K与容器中某个元素的键匹配，则该函数返回K值关联的Value引用。如果K与容器中任何元素的键不匹配，则该函数用该键插入一个新元素，并返回对其映射值的引用。这个新元素会有默认值。

调用[]类似于下面的操作：

(*((this->insert(make_pair(k,mapped_type()))).first)).second

也就是说[]的实现是借助于insert实现的。而这样的话[]的用法就有两种：

1. 插入
   • 如果K是map中不存在的，那么这就是一个插入操作；由于其返回值为第二个模板参数value的引用，所以可以直接修改。
   • 
2. 修改
   • 如果K是map中已有的值，那么insert将会返回已存在K的迭代器，[]最终返回一个K的引用，相当于支持修改操作。
   • 

所以[]重载运算符的实现如下。

		//返回value的引用V& operator[](const K& key){pair<iterator, bool> ret = _rbt.Insert({ key,V() });return ret.first->second;//不理解返回second的结合operator->看}

• 返回值类型为第二个参数的引用，所以支持直接修改。
• 关于返回V&为何是返回it.first->second：it 为接受的是insert返回的pair对，其first为指向元素的迭代器，->调用了迭代器的operator->，此时返回的是存储KV的pair，此时的second为V