C++从入门到起飞之——红黑树封装map和set 全方位剖析！

目录

1、map和set的整体框架

2、map和set迭代器的实现

3、map支持[]

4、完整源码

set.h

map.h

RBTree.h

---

1、map和set的整体框架

因为map和set的底层都是红黑树，所以我们考虑用一个红黑树的类模版去实例化map和set对象！不过，map节点中存储的是一个pair对象，而set中存储的是一个key对象。所以我们第一步就是先调整一下我们之前实现的红黑树的节点结构。

//节点结构（不知道存储pair类型的key/val结构还是Key结构）
template<class T>
struct RBTreeNode
{RBTreeNode(const T& data):_data(data), _parent(nullptr), _left(nullptr), _right(nullptr), _col(RED){}T _data;RBTreeNode* _parent;RBTreeNode* _left;RBTreeNode* _right;Colour _col;//初始化为红色
};

无论是set还是map的查找都是根据key来进行的，所以我们的红黑树类模版的第一个参数类型是接受上层传递过来的K类型。

再有，set和map的insert（插入），一个是pair类型，一个是key类型。所以我们的红黑树类模版的第二个参数类型是接受上层传递过来的T类型。

最后，我们还要在上层传递一个仿函数用于底层红黑树查找和插入删除时用key比较。因为set直接插入一个key可以用于比较，但是map插入一个pair，而pair支持的比较是first和second一起比较，而我们只希望用key比较。又因为底层并不知道上层是set还是map，所以我们要在上层传递一个仿函数给到下层让下层用上层的仿函数拿到key来比较大小！

set整体框架：

namespace my_set
{template<class K>class set{//仿函数用于底层红黑树查找和插入删除时用key比较struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:bool insert(const K& key){return _t.insert(key);}private:RBTree<K, K, SetKeyOfT> _t;};
}

map整体框架：

namespace my_map
{template<class K,class V>class map{/*仿函数用于底层红黑树查找和插入删除时用key比较因为set直接插入一个key可以用于比较，但是map插入一个pair，而pair支持的比较是first和second一起比较，而我们只希望用key比较又底层并不知道上层是set还是map，所以我们要在上层传递一个仿函数给到下层让下层用上层的仿函数拿到key来比较大小！*/struct MapKeyOfT{const K& operator()(const pair<K,V>& kv){return kv.first;}};public:bool insert(const pair<K,V>& kv){return _t.insert(kv);}private:RBTree<K, pair<K,V>, MapKeyOfT> _t;};
}

调整过后的底层红黑树：

//枚举类型定义颜色
enum Colour
{RED,BLACK
};
//节点结构（不知道存储pair类型的key/val结构还是Key结构）
template<class T>
struct RBTreeNode
{RBTreeNode(const T& data):_data(data), _parent(nullptr), _left(nullptr), _right(nullptr), _col(RED){}T _data;RBTreeNode* _parent;RBTreeNode* _left;RBTreeNode* _right;Colour _col;//初始化为红色
};//红黑树
template<class K, class T,class KeyOfT>
class RBTree
{typedef RBTreeNode<T> Node;
public:KeyOfT kot;//默认构造RBTree() = default;//拷贝构造RBTree(const T& rbt){_root = _copy(rbt._root);}// 赋值重载RBTree<K, T,KeyOfT>& operator=(T tmp){std::swap(_root, tmp._root);return *this;}//二叉树的析构~RBTree(){_Destroy(_root);}//红黑树的查找Node* Find(const K& key){Node* cur = _root;while (cur){if (kot(cur->_data) < kot(key)){cur = cur->_right;}else if (kot(cur->_data) > kot(key)){cur = cur->_left;}else{return cur;}}return nullptr;}//红黑树的插入bool insert(const T& data){//如果树为空，在根插入并且颜色为黑色if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return true;}//树不为空按搜索树规则先进行插入Node* parent = nullptr;Node* cur = _root;while (cur){if (kot(data) < kot(cur->_data))//小往左走{parent = cur;cur = parent->_left;}else if (kot(data) > kot(cur->_data))//大往右走{parent = cur;cur = parent->_right;}else{return false;//不支持相同元素的插入}}cur = new Node(data);cur->_col = RED;if (kot(data) < kot(parent->_data))//K小插入在左边parent->_left = cur;else//K大插入在右边parent->_right = cur;cur->_parent = parent;//插入后进行维护红黑树规则的逻辑//parent存在且为红while (parent && parent->_col == RED){Node* grandfather = parent->_parent;//p在g的右边if (parent == grandfather->_right){//g//u		pNode* uncle = grandfather->_left;if (uncle && uncle->_col == RED)//uncle存在且为红{//变色处理uncle->_col = parent->_col = BLACK;grandfather->_col = RED;//更新cur继续向上处理cur = grandfather;parent = cur->_parent;}else//uncle不存在或者存在且为黑{if (cur == parent->_right){//g//u		p//		   c//以g为旋转点进行左单旋RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//g//u		p//	  c//进行右左双旋RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}//旋转+变色后链接祖先节点的节点为黑，必然不会发生连续红色节点的情况直接break;break;}}else//p在g的左边{//g//p		uNode* uncle = grandfather->_right;if (uncle && uncle->_col == RED)//uncle存在且为红{//变色处理uncle->_col = parent->_col = BLACK;grandfather->_col = RED;//更新cur继续向上处理cur = grandfather;parent = cur->_parent;}else//uncle不存在或者存在且为黑{if (cur == parent->_left){//g//p		u//c//以g为旋转点进行右单旋RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//g//p		u//		c//进行左右双旋RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}//旋转+变色后链接祖先节点的节点为黑，必然不会发生连续红色节点的情况直接break;break;}}}//如果持续更新变色到根_root->_col = BLACK;return true;}private://右单旋void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;Node* pParent = parent->_parent;parent->_left = subLR;if (subLR)//如果不为空subLR->_parent = parent;subL->_right = parent;parent->_parent = subL;if (pParent == nullptr){_root = subL;subL->_parent = nullptr;}else{if (pParent->_left == parent){pParent->_left = subL;}else{pParent->_right = subL;}subL->_parent = pParent;}}//左单旋void RotateL(Node* parent){Node* pParent = parent->_parent;Node* subR = parent->_right;Node* subRL = subR->_left;subR->_left = parent;parent->_parent = subR;parent->_right = subRL;if (subRL)subRL->_parent = parent;if (pParent == nullptr){_root = subR;subR->_parent = nullptr;}else{if (pParent->_left == parent){pParent->_left = subR;}else{pParent->_right = subR;}subR->_parent = pParent;}}//递归拷贝Node* _copy(Node* root){if (root == nullptr)return nullptr;Node* newNode = new Node(root->_data);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;}private:Node* _root = nullptr;
};

2、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;Node* _root;RBTreeIterator(Node* node,Node* root):_node(node),_root(root){}//迭代器的++Self& operator++(){}//迭代器的--Self& operator--(){}//简单的运算符重载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;}
};

 map和set迭代器的难点在于++和--：

iterator实现思路分析

• iterator实现的⼤框架跟list的iterator思路是⼀致的，⽤⼀个类型封装结点的指针，再通过重载运算 符实现，迭代器像指针⼀样访问的⾏为。

• 这⾥的难点是operator++和operator--的实现。之前使⽤部分，我们分析了，map和set的迭代器⾛ 的是中序遍历，左⼦树->根结点->右⼦树，那么begin()会返回中序第⼀个结点的iterator也就是10 所在结点的迭代器。

• 迭代器++的核⼼逻辑就是不看全局，只看局部，只考虑当前中序局部要访问的下⼀个结点。

• 迭代器++时，如果it指向的结点的右⼦树不为空，代表当前结点已经访问完了，要访问下⼀个结点 是右⼦树的中序第⼀个，⼀棵树中序第⼀个是最左结点，所以直接找右⼦树的最左结点即可。

• 迭代器++时，如果it指向的结点的右⼦树空，代表当前结点已经访问完了且当前结点所在的⼦树也 访问完了，要访问的下⼀个结点在当前结点的祖先⾥⾯，所以要沿着当前结点到根的祖先路径向上 找。

• 如果当前结点是⽗亲的左，根据中序左⼦树->根结点->右⼦树，那么下⼀个访问的结点就是当前结 点的⽗亲；

如下图：it指向25，25右为空，25是30的左，所以下⼀个访问的结点就是30。

• 如果当前结点是⽗亲的右，根据中序左⼦树->根结点->右⼦树，当前当前结点所在的⼦树访问完 了，当前结点所在⽗亲的⼦树也访问完了，那么下⼀个访问的需要继续往根的祖先中去找，直到找 到孩⼦是⽗亲左的那个祖先就是中序要问题的下⼀个结点。

如下图：it指向15，15右为空，15是10 的右，15所在⼦树话访问完了，10所在⼦树也访问完了，继续往上找，10是18的左，那么下⼀个 访问的结点就是18。

• end()如何表⽰呢？

如下图：当it指向50时，++it时，50是40的右，40是30的右，30是18的右，18 到根没有⽗亲，没有找到孩⼦是⽗亲左的那个祖先，这是⽗亲为空了，那我们就把it中的结点指针 置为nullptr，我们⽤nullptr去充当end。需要注意的是stl源码空，红⿊树增加了⼀个哨兵位头结点 做为end()，这哨兵位头结点和根互为⽗亲，左指向最左结点，右指向最右结点。相⽐我们⽤ nullptr作为end()，差别不⼤，他能实现的，我们也能实现。只是--end()判断到结点时空，特殊处 理⼀下，让迭代器结点指向最右结点。具体参考迭代器--实现。

• 迭代器--的实现跟++的思路完全类似，逻辑正好反过来即可，因为他访问顺序是右⼦树->根结点-> 左⼦树，具体参考下⾯代码实现。

• set的iterator也不⽀持修改，我们把set的第⼆个模板参数改成const K即可， RBTreeconst K, SetKeyOfT> _t;

• map的iterator不⽀持修改key但是可以修改value，我们把map的第⼆个模板参数pair的第⼀个参 数改成const K即可， RBTreepair, MapKeyOfT> _t; 

• ⽀持完整的迭代器还有很多细节需要修改，具体参考下⾯题的代码。

 

 迭代器++代码：

//迭代器的++
Self& operator++()
{//如果当前节点的右不为空，那下一个节点就是右子树的最左节点if (_node->_right){Node* leftMost = _node->_right;while (leftMost->_left){leftMost = leftMost->_left;}_node = leftMost;}/*如果当前节点的右为空，则说明当前节点的中序已近完毕如果当前节点是父亲的右，说明父亲的中序也完毕所以我们要找到祖先节点中是父亲的左的那个节点，那下一个节点就是就是父亲*/else{Node* cur = _node;Node* parent = cur->_parent;//父亲不为空并且cur是父亲的右，不断向上寻找while (parent && cur == parent->_right){cur = parent;parent = cur->_parent;}//走到这里父亲为空说明走到end，不为空父亲则是中序的下一个_node = parent;}return *this;
}

因为我们用空来代表数的末尾，但我们--时，如果此时迭代器恰好在end()位置，那我们就要单独考虑这种情况。其他逻辑就和++相反！

要找到树的最右节点，那么就还必须知道根节点_root！所以我们在红黑树中构造一个迭代器时，不仅要传递当前位置的节点，还要传根节点！

//迭代器的--
Self& operator--()
{//--后为中序的最右那一个if (_node == nullptr){Node* rightMost = _root;while (rightMost&&rightMost->_right){rightMost = rightMost->_right;}_node = rightMost;}//如果当前节点的左不为空，那下一个节点就是左子树的最右节点else if (_node->_left){Node* rightMost = _node->_left;while (rightMost->_right){rightMost = rightMost->_right;}_node = rightMost;}/*如果当前节点的左为空，则说明当前节点的中序已近完毕如果当前节点是父亲的左，说明父亲的中序也完毕所以我们要找到祖先节点中是父亲的右的那个节点，那下一个节点就是就是父亲*/else{Node* cur = _node;Node* parent = cur->_parent;//父亲不为空并且cur是父亲的左，不断向上寻找while (parent && cur == parent->_left){cur = parent;parent = cur->_parent;}//走到这里父亲为空说明走到end，不为空父亲则是中序的下一个_node = parent;}return *this;
}

底层红黑树的begin和end： 

typedef RBTreeNode<T> Node;
typedef RBTreeIterator<T, T&, T*> Iterator;
typedef RBTreeIterator<T, const T&, const T*> ConstIterator;
Iterator Begin()
{Node* leftMost = _root;while (leftMost && leftMost->_left){leftMost = leftMost->_left;}return Iterator(leftMost, _root);
}
Iterator End()
{return Iterator(nullptr, _root);
}
ConstIterator CBegin() const
{Node* leftMost = _root;while (leftMost && leftMost->_left){leftMost = leftMost->_left;}return Iterator(leftMost, _root);
}
ConstIterator CEnd() const
{return Iterator(nullptr, _root);
}

3、map支持[]

map的[]重载主要是复用了底层红黑树当中的insert接口，insert充当查找和插入的功能！

我们在使用[]时，如果map中有和我们外面传递的key相同的key，那insert就会插入失败并且返回这个key的迭代器。如果不存在，那insert就会插入成功并且返回这个key的迭代器。所以我们要调整一下insert的返回值为pair<iterator,bool>

而map的[]还支持修改（key所映射的val）的功能，insert返回的迭代器在修改val时发挥作用！

V& operator[](const K& key)
{pair<iterator, bool> ret = _t.Insert(make_pair(key, V()));return ret.first->second;
}

4、完整源码

set.h

#pragma once
#include"RBTree.h"
namespace my_set
{template<class K>class set{//仿函数用于底层红黑树查找和插入删除时用key比较struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:typedef typename RBTree<K, const K, SetKeyOfT>::Iterator iterator;typedef typename RBTree<K, const K, SetKeyOfT>::ConstIterator const_iterator;iterator begin(){return _t.Begin();}iterator end(){return _t.End();}const_iterator cbegin() const{return _t.CBegin();}const_iterator cend() const{return _t.CEnd();}pair<iterator,bool> insert(const K& key){return _t.Insert(key);}iterator find(const K& key){return _t.Find(key);}private:RBTree<K, const K, SetKeyOfT> _t;};
}

map.h

#pragma once
#include"RBTree.h"
namespace my_map
{template<class K,class V>class map{/*仿函数用于底层红黑树查找和插入删除时用key比较因为set直接插入一个key可以用于比较，但是map插入一个pair，而pair支持的比较是first和second一起比较，而我们只希望用key比较又底层并不知道上层是set还是map，所以我们要在上层传递一个仿函数给到下层让下层用上层的仿函数拿到key来比较大小！*/struct MapKeyOfT{const K& operator()(const pair<K,V>& kv){return kv.first;}};public:typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::Iterator iterator;typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::ConstIterator const_iterator;iterator begin(){return _t.Begin();}iterator end(){return _t.End();}const_iterator cbegin() const{return _t.CBegin();}const_iterator cend() const{return _t.CEnd();}pair<iterator, bool> insert(const pair<K,V>& kv){return _t.Insert(kv);}iterator find(const K& key){return _t.Find(key);}V& operator[](const K& key){pair<iterator, bool> ret = _t.Insert(make_pair(key, V()));return ret.first->second;}private:RBTree<K, pair<const K,V>, MapKeyOfT> _t;};
}

RBTree.h

#pragma once
#include<iostream>
using namespace std;//枚举类型定义颜色
enum Colour
{RED,BLACK
};//节点结构（不知道存储pair类型的key/val结构还是Key结构）
template<class T>
struct RBTreeNode
{RBTreeNode(const T& data):_data(data), _parent(nullptr), _left(nullptr), _right(nullptr), _col(RED){}T _data;RBTreeNode* _parent;RBTreeNode* _left;RBTreeNode* _right;Colour _col;//初始化为红色
};//封装一个节点指针作为迭代器
template<class T,class Ref,class Ptr>
struct RBTreeIterator
{typedef  RBTreeNode<T> Node;typedef  RBTreeIterator<T,Ref,Ptr> Self;Node* _node;Node* _root;RBTreeIterator(Node* node,Node* root):_node(node),_root(root){}//迭代器的++Self& operator++(){//如果当前节点的右不为空，那下一个节点就是右子树的最左节点if (_node->_right){Node* leftMost = _node->_right;while (leftMost->_left){leftMost = leftMost->_left;}_node = leftMost;}/*如果当前节点的右为空，则说明当前节点的中序已近完毕如果当前节点是父亲的右，说明父亲的中序也完毕所以我们要找到祖先节点中是父亲的左的那个节点，那下一个节点就是就是父亲*/else{Node* cur = _node;Node* parent = cur->_parent;//父亲不为空并且cur是父亲的右，不断向上寻找while (parent && cur == parent->_right){cur = parent;parent = cur->_parent;}//走到这里父亲为空说明走到end，不为空父亲则是中序的下一个_node = parent;}return *this;}//迭代器的--Self& operator--(){//--后为中序的最右那一个if (_node == nullptr){Node* rightMost = _root;while (rightMost&&rightMost->_right){rightMost = rightMost->_right;}_node = rightMost;}//如果当前节点的左不为空，那下一个节点就是左子树的最右节点else if (_node->_left){Node* rightMost = _node->_left;while (rightMost->_right){rightMost = rightMost->_right;}_node = rightMost;}/*如果当前节点的左为空，则说明当前节点的中序已近完毕如果当前节点是父亲的左，说明父亲的中序也完毕所以我们要找到祖先节点中是父亲的右的那个节点，那下一个节点就是就是父亲*/else{Node* cur = _node;Node* parent = cur->_parent;//父亲不为空并且cur是父亲的左，不断向上寻找while (parent && cur == parent->_left){cur = parent;parent = cur->_parent;}//走到这里父亲为空说明走到end，不为空父亲则是中序的下一个_node = parent;}return *this;}//简单的运算符重载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;}
};//红黑树
template<class K, class T,class KeyOfT>
class RBTree
{
public:typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, T&, T*> Iterator;typedef RBTreeIterator<T, const T&, const T*> ConstIterator;Iterator Begin(){Node* leftMost = _root;while (leftMost && leftMost->_left){leftMost = leftMost->_left;}return Iterator(leftMost, _root);}Iterator End(){return Iterator(nullptr, _root);}ConstIterator CBegin() const{Node* leftMost = _root;while (leftMost && leftMost->_left){leftMost = leftMost->_left;}return Iterator(leftMost, _root);}ConstIterator CEnd() const{return Iterator(nullptr, _root);}KeyOfT kot;//默认构造RBTree() = default;//拷贝构造RBTree(const T& rbt){_root = _copy(rbt._root);}// 赋值重载RBTree<K, T,KeyOfT>& operator=(T tmp){std::swap(_root, tmp._root);return *this;}//二叉树的析构~RBTree(){_Destroy(_root);}//红黑树的查找Node* Find(const K& key){Node* cur = _root;while (cur){if (kot(cur->_data) < kot(key)){cur = cur->_right;}else if (kot(cur->_data) > kot(key)){cur = cur->_left;}else{return Iterator(cur,_root);}}return End();}//红黑树的插入pair<Iterator,bool> Insert(const T& data){//如果树为空，在根插入并且颜色为黑色if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return make_pair(Iterator(_root,_root),true);}//树不为空按搜索树规则先进行插入Node* parent = nullptr;Node* cur = _root;while (cur){if (kot(data) < kot(cur->_data))//小往左走{parent = cur;cur = parent->_left;}else if (kot(data) > kot(cur->_data))//大往右走{parent = cur;cur = parent->_right;}else{return make_pair(Iterator(cur, _root), false);//不支持相同元素的插入}}cur = new Node(data);Node* newnode = cur;cur->_col = RED;if (kot(data) < kot(parent->_data))//K小插入在左边parent->_left = cur;else//K大插入在右边parent->_right = cur;cur->_parent = parent;//插入后进行维护红黑树规则的逻辑//parent存在且为红while (parent && parent->_col == RED){Node* grandfather = parent->_parent;//p在g的右边if (parent == grandfather->_right){//g//u		pNode* uncle = grandfather->_left;if (uncle && uncle->_col == RED)//uncle存在且为红{//变色处理uncle->_col = parent->_col = BLACK;grandfather->_col = RED;//更新cur继续向上处理cur = grandfather;parent = cur->_parent;}else//uncle不存在或者存在且为黑{if (cur == parent->_right){//g//u		p//		   c//以g为旋转点进行左单旋RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//g//u		p//	  c//进行右左双旋RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}//旋转+变色后链接祖先节点的节点为黑，必然不会发生连续红色节点的情况直接break;break;}}else//p在g的左边{//g//p		uNode* uncle = grandfather->_right;if (uncle && uncle->_col == RED)//uncle存在且为红{//变色处理uncle->_col = parent->_col = BLACK;grandfather->_col = RED;//更新cur继续向上处理cur = grandfather;parent = cur->_parent;}else//uncle不存在或者存在且为黑{if (cur == parent->_left){//g//p		u//c//以g为旋转点进行右单旋RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//g//p		u//		c//进行左右双旋RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}//旋转+变色后链接祖先节点的节点为黑，必然不会发生连续红色节点的情况直接break;break;}}}//如果持续更新变色到根_root->_col = BLACK;return make_pair(Iterator(newnode, _root), true);}private://右单旋void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;Node* pParent = parent->_parent;parent->_left = subLR;if (subLR)//如果不为空subLR->_parent = parent;subL->_right = parent;parent->_parent = subL;if (pParent == nullptr){_root = subL;subL->_parent = nullptr;}else{if (pParent->_left == parent){pParent->_left = subL;}else{pParent->_right = subL;}subL->_parent = pParent;}}//左单旋void RotateL(Node* parent){Node* pParent = parent->_parent;Node* subR = parent->_right;Node* subRL = subR->_left;subR->_left = parent;parent->_parent = subR;parent->_right = subRL;if (subRL)subRL->_parent = parent;if (pParent == nullptr){_root = subR;subR->_parent = nullptr;}else{if (pParent->_left == parent){pParent->_left = subR;}else{pParent->_right = subR;}subR->_parent = pParent;}}//递归拷贝Node* _copy(Node* root){if (root == nullptr)return nullptr;Node* newNode = new Node(root->_data);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;}
private:Node* _root = nullptr;
};