【C++】 使用红黑树模拟实现STL中的map与set
前言
<font color = "#000066">前面的文章我们学习了红黑树，也提到了C++STL中的map和set的底层其实就是用的红黑树来实现的（而map和set的使用我们前面也学过了）。
1. 对之前实现的红黑树进行一些补充和完善
上一篇文章我们实现了红黑树，但是我们实现的那个类并不是特别完善，所以，为了后面map和set的模拟实现，我们先对之前写的那个红黑树的类做一些补充和完善。
1.1 析构
构造函数的话其实不写也没事，我们给了缺省值，但是析构的话有必要写一下，因为我们的红黑树是涉及资源管理的。
我们来实现一下：
<font color = black>二叉树的销毁我们之前也有讲过，走一个后序遍历销毁就行了
代码很简单，我就不解释了
1.2 查找
那红黑树的查找呢我们上一篇文章有提到，但是当时没写，因为就跟搜索二叉树的查找一样嘛。
那这里由于后面我们要用红黑树模拟实现map和set（它们是有find这个接口的）的缘故，所以我们也补充一下：
<font color = black>直接上代码
2. STL源码中map和set的实现
那在正式实现之前，我们先一起来看一下STL（SGI版本）中map和set的源码，大致了解一下库里面是怎么实现的。
我们先来看一下map的源码:
<font color = "#000066">由于源码里面内容比较多，我们这里不需要全部都看，所以我这里有选择性地提取一些内容给大家看 先来看这些
key_type和value_type就对应的是Key和Value的的类型，我们看到这里面的key_type就是key，但是value_type却是一个pair。 可以按我们之前的理解，map里面存的就是一个pair（键值对）嘛，pair的first对应key，second对应value。 但是它里面为什么value的类型就是一个pair呢？ 那先不急，我们后面会解释。
然后我们再来看一下set：
<font color = "#000066">
那它这里是如何做到map和set底层都用同一个红黑树的类模板呢？
观察set的结构我们会发现：
<font color = "#000066">
key_type之外，也有value_type，但是set里面的key_type和value_type都是Key的typedef，所以相当于传来两个key。 当然从表面上来看他之所以这样做的原因是他和map用的是同一个红黑树的类模板，而这个类模板是有两个参数的，所以它必须传两个。
那红黑树为什么要这样设计呢？所以我们再来观察一下红黑树的实现：
<font color = "#000066">
link_type这个类型其实就是结点的指针，这个header代表啥我们可以先不管。 然后我们看到红黑树这里的模板参数是固定的，前两个模板参数是key和value，而红黑树结点里面放的其实就是value
所以它们这里这两个模板参数的传递是这样的：
<font color = black>
那问题来了，第一个模板参数的作用是啥？
<font color = "#000066">
所以，我想大家现在应该就明白第一个模板参数Key是干嘛的了：
<font color = blue>因为map里面存的是KV的键值对，但是查找这些操作的时候是以K为目标去查找的，所以红黑树里面要多搞出来一个参数Key来单独获取这个Key。 那其实对于set来说是不需要的（因为set里面存的就是单独一个key,查找也是用的key，上面我们也看了，它传的前两个模板就是一样的，都是key），但是因为你set要和map共用一个红黑树模板，所以你必须迎合这个红黑树的结构，也去多传一个。 当然其实map也可以不用第一个参数，查找的时候用pair.first就行了，但是set里面只存了一个key，它可找不来什么first的东西，所以红黑树才要增加一个模板参数，这样红黑树里面的find，erase这些函数就可以以一种统一的实现（即都用第一个模板参数接收的key去查找），这样map和set才可以共同复用同一个红黑树的模板类。
当然它们只是共用了同一个类模板而已，最后实例化出来的还是不同的类对象，但是这不就正是模板出现的主要意义嘛，实现代码的复用，对我们程序员来说还是方便了很多的。
那源码呢我们就先看到这里，接下来我们就来自己尝试模拟实现一下，其实就是去对红黑树进行一个封装嘛。 后面有需要我们再来看相应的源码。
3. 改造红黑树+封装map和set
3.1 红黑树结构修改
先要封装的话首先我们得对我们之前自己实现得红黑树做一些改造。
首先结点的结构我们可以不用改，虽然我们的跟库里面源码不太一样：
<font color = black>
那红黑树的结构我们就需要修改一下了：
<font color = "#000066">因为我们当时是按照K模型实现的，只有一个模板参数
3.2 map、set的结构定义
那然后我们来创建一个头文件，先把map的结构简单定义一下
<font color = "#000066">
然后写一下set的：
<font color = black>
3.3 insert的封装
先来看map：
<font color = black>
然后set：
<font color = black>也是一样
3.4 insert测试
我们分别对map和set插入一些数据试一试：
<font color = black>
然后呢：
<font color = black>
3.5 发现问题并解决
什么问题呢？
<font color = "#000066">🆗，我们前面实现的红黑树是K模型的，里面的插入就是按照结点里面的data去比较的
那我们怎么去解决这个问题啊：
<font color = "#000066">那这个地方库里面的做法是比较不错的，我们可以来学习一下 再来看源码里面红黑树的结构
3.6 红黑树迭代器实现
那接下来我们来实现一下迭代器，实现好之后也可以测试一下我们上面插入之后到底对不对。
迭代器我们重点实现红黑树的，map和set直接复用就行了，库里面源码也是这样搞的。
那红黑树的迭代器呢其实就是结点指针的封装，跟我们之前学的list的迭代器差不多：
<font color = "#000066">那在这里我们控制const迭代器以及重载->这个运算符其实用的方法都和之前list一样，通过增加模板参数去控制，大家遗忘的话可以复习一下list那里相关的实现，下面我就直接写了，有些地方就不过多解释了
那我们先来定义一下它的结构：
<font color = "#000066">里面其实就是封装一个结点的指针
然后常见的几个成员函数实现一下：
<font color = black>
那红黑树的类模板里面这样写就行了：
<font color = "#000066">
然后我们写一下迭代器的begin和end吧：
<font color = "#000066">首先说一下我们下面的实现和库里面有所不同，库里面其实稍微麻烦一点，我们后面也会提到，但大家按照我们这里讲的实现就行。 那大家想一下，begin返回的是啥？ 🆗，在这里是不是应该返回指向中序遍历第一个结点的迭代器啊。 而中序遍历的第一个结点不就是整棵树最左边的那个结点嘛。
那const版本的begin和end我们也直接写一下：
<font color = black>
另外这里稍微有点挑战的就是++和- -的重载，这两个重载之后我们就可以使用迭代器遍历红黑树了（后面封装好就是遍历map和set），那我们来讲一下：
<font color = "#000066">其实这里相当于我们要搞出一种新的遍历二叉树的方式，之前我们学了递归和利用栈的非递归的方式。 首先++的重载
然后再来搞一下- -（map和set的迭代器是双向迭代器）：
<font color = "#000066">那大家思考一下- -要怎么走？ 其实就是跟++的反过来就行了，中序是左子树、根、右子树，那- -就右子树、根、左子树就行了 那这样反过来的话就是先判断it的左子树为不为空，不为空就访问左子树的最右结点，如果左为空，那就要向上去找it是谁的右子树，找到的话当前it的这个父亲就是下一个要访问的结点。
如果大家去看源码的话会发现它的实现跟我们有一些不同：
<font color = "#000066">他给这棵红黑树增加了一个头结点
然后反向迭代器大家有兴趣可以自己搞一下，前面我们也讲过怎么弄，这里就不写了。
3.7 封装set和map的迭代器并测试
那红黑树的迭代器实现的差不多了，我们就可以用它封装set和map的迭代器了。
先来搞一下set：
<font color = black>
那然后我们再来封装一下map的迭代器并测试一下：
<font color = black>
3.8 map的[]重载
那map与set不同的是不是他还重载了[]啊，这个我们之前在map和set的使用那篇文章也讲过。
那我们接下来就来实现一下map的【】：
<font color = "#000066">那通过前面的学习，我们知道map重载的[]，底层的实现是跟insert的返回值有关系的，所以我们得修改一下红黑树的insert
那map和set里面insert的封装我们也要改一下：
<font color = black>其实把返回值改一下就行了
然后就可以给map重载[]了：
<font color = "#000066">
我们可以用统计次数那个程序测试一下：
<font color = black>
3.9 元素可以修改的问题解决
但是我们上面的实现其实还存在一些问题：
<font color = "#000066">通过前面的学习我们知道set里面的元素是不能修改的，因为底层是搜索树，如果可以随意修改的话就会破坏搜索树的关系。 而对于map，key是不可以修改的，不过value可以修改。
那如何解决呢？
<font color = "#000066">我们可以看一下库里面是怎么解决的： 先来看set里面的迭代器
__rb_tree_iterator这个迭代器的类模板被实例化成iterator的话那它就是一个拷贝构造了，因为这是这个参数就跟类对象的类型匹配了； 如果被实例化成这个const_iterator的话，那它就是一个可以用iterator去构造const_iterator的构造函数了。 那它这里支持了普通迭代器构造const迭代器的话我们上面提到的那个问题是不是就解决了，因为单参数的构造函数是可以支持隐式类型转换的，这个我们之前学过的。
那大家可能会想既然不能修改那直接让红黑树只实现const迭代器不就行了？
<font color = "#000066">这样对于set是可行的，但是map也要复用这棵红黑树啊，map的key虽然不支持修改，但是value是可以修改的。 所以map是要区分普通迭代器和const迭代器的，不能像set那样普通迭代器和const迭代器都是用的红黑树的const迭代器。
那现在我们来解决一下：
<font color = blue>我们也加一个可以支持普通迭代器构造const迭代器的构造函数就行了
__RBTreeIterator被实例化成了普通迭代器还是const迭代器（取决于Ref和Ptr传的是啥），我这里都是用普通迭代器去构造你的（因为参数是<T, T&, T*>） 然后再运行
那map要如何解决Key不能修改，但是value可以修改的问题呢？
<font color = "#000066">那这个我们其实上面已经提到过了
🆗，那我们的map和set的模拟实现就差不多讲到这里，其它一些我们这里没实现的东西大家有兴趣的可以自己补充，这里我们就不写了。
4. 代码展示
4.1 RBTree.h
#pragma once
enum Colour
{
RED,
BLACK,
};
template <class T>
struct RBTreeNode
{
RBTreeNode<T>* _parent;
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
T _data;
Colour _col;
RBTreeNode(const T& data)
:_parent(nullptr)
, _left(nullptr)
, _right(nullptr)
, _data(data)
, _col(RED)
{}
};
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)
{}
//不论`__RBTreeIterator`被实例化成了普通迭代器还是const迭代器（取决于Ref和Ptr传的是啥）
//，我这里都是用普通迭代器去构造的（因为参数是`<T, T&, T*>`）
__RBTreeIterator(const __RBTreeIterator<T, T&, T*>& it)
:_node(it._node)
{}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
Self operator++()
{
//如果右不为空，下一个访问的是右子树的最左结点
if (_node->_right)
{
Node* subLeft = _node->_right;
while (subLeft->_left)
{
subLeft = subLeft->_left;
}
_node = subLeft;
}
//右为空，往上找it是谁的左子树
else
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->_right)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
Self operator--()
{
//如果左不为空，下一个访问的是左子树的最右结点
if (_node->_left)
{
Node* subRight = _node->_left;
while (subRight->_right)
{
subRight = subRight->_right;
}
_node = subRight;
}
//左为空，往上找it是谁的右子树
else
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->_left)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
};
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* cur = _root;
while (cur && cur->_left)
{
cur = cur->_left;
}
return iterator(cur);
}
iterator end()
{
return iterator(nullptr);
}
//const版本begin和end
const_iterator begin()const
{
Node* cur = _root;
while (cur && cur->_left)
{
cur = cur->_left;
}
return const_iterator(cur);
}
const_iterator end()const
{
return const_iterator(nullptr);
}
pair<iterator,bool> Insert(const T& data)
{
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(data) < kot(cur->_data))
{
parent = cur;
cur = cur->_left;
}
else if (kot(data) > kot(cur->_data))
{
parent = cur;
cur = cur->_right;
}
else
{
return make_pair(iterator(cur), false);
}
}
//走到这里cur为空，就是key应该插入的位置
cur = new Node(data);
Node* newNode = cur;
//链接
if (kot(data) < kot(parent->_data))
parent->_left = cur;
if (kot(data) > kot(parent->_data))
parent->_right = cur;
//链接父亲指针
cur->_parent = parent;
//如果插入之后它的parent是红的，就需要进行调整
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;
//如果父亲是祖父的左孩子，那右孩子就是叔叔
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
//这里处理的情况是叔叔存在且为红，变色+向上继续处理
if (uncle && uncle->_col == RED)
{
//将p,u改为黑，g改为红
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
//更新cur为grandfather，判断它的父亲是什么情况：
//1.如果不存在或者为黑，就需要继续处理了，也不会进行循环了
//2.如果它的父亲存在且为红，重新循环进行调整
cur = grandfather;
parent = cur->_parent;
}
else//叔叔不存在/叔叔存在且为黑的情况
{
// g
// p u
// c
if (cur == parent->_left)//左左——右单旋+变色
{
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;
}
}
//如果父亲是祖父的右孩子，那左孩子就是叔叔
else //parent = grandfather->_right
{
Node* uncle = grandfather->_left;
//这里处理的情况是叔叔存在且为红
if (uncle && uncle->_col == RED)
{
//将p,u改为黑，g改为红
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
//更新cur为grandfather，判断它的父亲是什么情况：
//1.如果不存在或者为黑，就需要继续处理了，也不会进行循环了
//2.如果它的父亲存在且为红，重新循环进行调整
cur = grandfather;
parent = cur->_parent;
}
else
{
if (cur == parent->_right)//右右——左单旋+变色
{
// g
// u p
// c
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else//右左——右左双旋+变色
{
// g
// u p
// c
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
//上面处理过程中有可能会把根变成红色，这里统一处理一下，把根置成黑
_root->_col = BLACK;
return make_pair(iterator(newNode), true);
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
bool IsBlance()
{
if (_root && _root->_col == RED)
{
cout << "根结点是红色" << endl;
return false;
}
//先求出一条路径黑色结点数量
int mark = 0;
Node* cur = _root;
while (cur)
{
if (cur->_col == BLACK)
++mark;
cur = cur->_left;
}
//检查是否出现连续红色结点及所有路径黑色结点数量是否相等
return _Check(_root, 0, mark);
}
int TreeHeight()
{
return _TreeHeight(_root);
}
Node* find(const T& data)
{
KeyOfT kot;
Node* cur = _root;
while (cur)
{
if (kot(data) < kot(cur->_data))
{
cur = cur->_left;
}
else if (kot(data) > kot(cur->_data))
{
cur = cur->_right;
}
else
{
return cur;
}
}
return nullptr;
}
~RBTree()
{
_Destroy(_root);
_root = nullptr;
}
private:
void _Destroy(Node* root)
{
if (root == nullptr)
return;
_Destroy(root->_left);
_Destroy(root->_right);
delete root;
}
int _TreeHeight(Node* root)
{
if (root == nullptr)
return 0;
int RightH = _TreeHeight(root->_left);
int leftH = _TreeHeight(root->_right);
return RightH > leftH ? RightH + 1 : leftH + 1;
}
bool _Check(Node* root, int blackNum, int mark)
{
if (root == nullptr)
{
//走到空就是一条路径走完了，比较一下是否相等
if (blackNum != mark)
{
cout << "存在黑色结点数量不相等" << endl;
return false;
}
return true;
}
if (root->_col == BLACK)
++blackNum;
if (root->_col == RED && root->_parent->_col == RED)
{
cout << "出现连续红色结点" << endl;
return false;
}
return _Check(root->_left, blackNum, mark)
&& _Check(root->_left, blackNum, mark);
}
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_data << " ";
_InOrder(root->_right);
}
//左单旋
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
//旋转并更新_parent指针
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
//先保存一下parent->_parent，因为下面会改它
Node* pparent = parent->_parent;
//旋转并更新_parent指针
subR->_left = parent;
parent->_parent = subR;
//若pparent为空则证明旋转的是一整棵树，因为根结点的_parent为空
if (pparent == nullptr)
{
//subR是新的根
_root = subR;
_root->_parent = nullptr;
}
//若pparent不为空，则证明旋转的是子树，parent上面还有结点
else
{
//让pparent指向子树旋转之后新的根
if (pparent->_left == parent)
{
pparent->_left = subR;
}
else
{
pparent->_right = subR;
}
//同时也让新的根指向pparent
subR->_parent = pparent;
}
}
//右单旋
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
//旋转并更新_parent指针
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
//先保存一下parent->_parent，因为下面会改它
Node* pparent = parent->_parent;
//旋转并更新_parent指针
subL->_right = parent;
parent->_parent = subL;
//若parent等于_root则证明旋转的是一整棵树（这也是一种判断方法）
if (parent == _root)
{
_root = subL;
_root->_parent = nullptr;
}
else
{
//让pparent指向子树旋转之后新的根
if (parent == pparent->_left)
{
pparent->_left = subL;
}
else
{
pparent->_right = subL;
}
//同时也让新的根指向pparent
subL->_parent = pparent;
}
}
private:
Node* _root = nullptr;
};4.2 Map.h
#pragma once
#include "RBTree.h"
namespace yin
{
template <class K, class V>
class map
{
struct MapKeyOfT
{
const K& operator()(const pair<const K, V>& kv)
{
return kv.first;
}
};
public:
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
V& operator[](const K& key)
{
pair<iterator, bool> ret = _t.Insert(make_pair(key, V()));
return ret.first->second;
}
pair<iterator,bool> insert(const pair<const K, V>& kv)
{
return _t.Insert(kv);
}
private:
RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};
void test_map1()
{
map<string, string> dict;
dict.insert(make_pair("sort", "排序"));
dict.insert(make_pair("left", "左边"));
dict.insert(make_pair("right", "右边"));
dict.insert(make_pair("string", "字符串"));
dict.insert(make_pair("insert", "插入"));
dict.insert(make_pair("erase", "删除"));
dict.insert(make_pair("erase", "删除"));
map<string, string>::iterator it = dict.begin();
while (it != dict.end())
{
cout << it->first << ":" << it->second << endl;
++it;
}
cout << endl;
/*for (auto e : dict)
{
cout << e.first << ":" << e.second << endl;
}*/
}
void test_map2()
{
string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
"苹果", "香蕉", "苹果", "香蕉" };
map<string, int> m;
for (auto e : arr)
{
m[e]++;
}
for (auto e : m)
{
cout << e.first << ":" << e.second << endl;
}
}
}4.3 Set.h
#pragma once
#include "RBTree.h"
namespace yin
{
template <class K>
class set
{
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;
typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
pair<iterator,bool> insert(const K& key)
{
return _t.Insert(key);
}
private:
RBTree<K, K, SetKeyOfT> _t;
};
void test_set1()
{
int arr[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
set<int> s1;
for (auto e : arr)
{
s1.insert(e);
}
set<int>::iterator it = s1.begin();
while (it != s1.end())
{
cout << *it << " ";
++it;
}
/*for (auto e : s1)
{
cout << e << " ";
}*/
cout << endl;
}
}4.4 Test.cpp
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
#include "Map.h"
#include "Set.h"
#include <set>
int main()
{
//yin::test_set1();
yin::test_map1();
return 0;
}
- 点赞
- 收藏
- 关注作者
评论（0）