【c++丨STL】基于红黑树模拟实现set和map（附源码）
【c++丨STL】基于红黑树模拟实现set和map（附源码）
ephemerals__
发布于 2025-02-14 08:57:35
发布于 2025-02-14 08:57:35
代码可运行
文章被收录于专栏：ephemerals__的技术专栏
运行总次数：0
代码可运行
前言
之前我们学习了红黑树以及STL中的set和map两种容器，本篇文章，基于之前实现的红黑树代码，我们将仿照SGI STL的实现方式，尝试对同一棵红黑树进行封装和一系列适配修改，模拟实现set和map两种容器。
建议大家掌握了红黑树以及set和map的使用之后，再来阅读本文，否则部分内容可能较难理解。
【数据结构进阶】红黑树超详解 + 实现（附源码）-CSDN博客
一、红黑树源码
之前实现的红黑树源代码如下：
#include <iostream>
#include <utility>
using namespace std;
enum Color//枚举值表示颜色
{
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;//指向父亲的指针
Color _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:
//强制生成无参构造
RBTree() = default;
//拷贝构造
RBTree(const RBTree<K, V>& t)
{
_root = _Copy(t._root);
}
//析构函数
~RBTree()
{
_Destroy(_root);
}
//插入
bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr)//树为空，直接插入
{
_root = new Node(kv);
_root->_col = BLACK;
return true;
}
//先查找合适的插入位置
Node* parent = nullptr;
Node* cur = _root;
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);
if (kv.first < parent->_kv.first)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
cur->_parent = parent;
//parent为红，进行平衡调整
while (parent && parent->_col == RED)
{
//确定grandfather
Node* grandfather = parent->_parent;
if (parent == grandfather->_left)
{
//确定uncle
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == RED)//uncle为红，仅变色
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
//继续向上判断
cur = grandfather;
parent = cur->_parent;
}
else//uncle为黑或不存在，旋转+变色
{
if (cur == parent->_left)//右单旋
{
RotateR(grandfather);
//变色
parent->_col = BLACK;
grandfather->_col = RED;
}
else//左右双旋
{
RotateL(parent);
RotateR(grandfather);
//变色
cur->_col = BLACK;
grandfather->_col = RED;
}
break;//旋转完成，直接跳出循环
}
}
else
{
//确定uncle
Node* uncle = grandfather->_left;
if (uncle && uncle->_col == RED)//uncle为红，仅变色
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
//继续向上判断
cur = grandfather;
parent = cur->_parent;
}
else//uncle为黑或不存在，旋转+变色
{
if (cur == parent->_right)//左单旋
{
RotateL(grandfather);
//变色
parent->_col = BLACK;
grandfather->_col = RED;
}
else//右左双旋
{
RotateR(parent);
RotateL(grandfather);
//变色
cur->_col = BLACK;
grandfather->_col = RED;
}
break;//旋转完成，直接跳出循环
}
}
}
//最后将根节点设置为黑色
_root->_col = BLACK;
return true;
}
//查找
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (key < cur->_kv.first)
{
cur = cur->_left;//小了往左走
}
else if (key > cur->_kv.first)
{
cur = cur->_right;//大了往右走
}
else
{
return cur;//找到了，返回
}
}
return nullptr;//没找到，返回空指针
}
private:
//右单旋
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR) subLR->_parent = parent;
Node* ppNode = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (parent == _root)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (ppNode->_left == parent) ppNode->_left = subL;
else ppNode->_right = subL;
subL->_parent = ppNode;
}
}
//左单旋
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL) subRL->_parent = parent;
Node* ppNode = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
if (parent == _root)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (ppNode->_left == parent) ppNode->_left = subR;
else ppNode->_right = subR;
subR->_parent = ppNode;
}
}
//拷贝构造
Node* _Copy(Node* root, Node* parent = nullptr)
{
if (root == nullptr) return nullptr;
Node* NewRoot = new Node(root->_kv);
NewRoot->_col = root->_col;//复制颜色
NewRoot->_parent = parent;//设置父指针
//递归拷贝左子树和右子树
NewRoot->_left = _Copy(root->_left, NewRoot);
NewRoot->_right = _Copy(root->_right, NewRoot);
return NewRoot;
}
//销毁
void _Destroy(Node* root)
{
if (root == nullptr) return;
_Destroy(root->_left);
_Destroy(root->_right);
delete root;
}
Node* _root = nullptr;//根节点指针
};二、set和map的模拟实现
1. 数据类型的设置
由于set元素类型是键(key)，而map是键值对(key_value)，它们底层的数据类型是不同的，那么如何通过封装同一棵红黑树实现两种不同数据类型的容器呢？解决方法：通过传入不同的模板参数类型决定红黑树的数据类型。
template<class K>
class Set
{
public:
//...
private:
RBTree<K, const K> _rbtree;
};template<class K, class V>
class Map
{
public:
//...
private:
RBTree<K, pair<const K, V>> _rbtree;
};我们将红黑树作为set和map的成员，在红黑树的第二个模板参数处，set传入const K（加const保证K不被修改）；map传入pair<const K, V>，这样红黑树就能根据不同的类型实例化出不同对象，以适应set和map的不同需求。
相应地，我们需要对红黑树节点结构和红黑树的模板参数名进行修改：
//节点
template<class T>
struct RBTreeNode
{
T _data;//将pair改为T对象
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
Color _col;
RBTreeNode(const T& data)
:_data(data)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _col(RED)
{}
};//红黑树类
template<class K, class T>
class RBTree
{
typedef RBTreeNode<T> Node;//将第二个模板参数T作为节点的数据类型如此，当我们创建set对象时，传入模板参数const K，底层红黑树接收到的参数T就是K（键），节点存放的数据类型就是K；创建map对象时，传入模板参数pair<const K, V>，红黑树接收到的参数T就是<K, V>（键值对），节点存放的数据类型就是<K, V>。
既然第二个模板参数就可以决定红黑树的数据类型，那么是否可以取消第一个模板参数呢？
其实不然。 虽然set和map的数据元素类型不同，但查找或删除操作都是按键查找/删除，函数的参数必须传入K类型。如果只是实现set容器，那么第二个参数的作用就完全可以替代第一个参数；但对于map容器，则K类型的第一个模板参数无法省去。所以第一个模板参数存在的意义是为了保证查找和删除操作的参数正确性。
2. 键值比较的适配
我们都知道，set和map是关联式容器，在进行插入或查找操作时，难免要和其他元素进行比较。虽然两者的数据类型不同，但比较的对象都是键Key。
但之前我们已经对红黑树节点的数据类型进行了修改：set为K，map为<K, V>。怎么使它们在进行元素比较时都按照Key值进行比较呢？解决方法：针对不同容器实现不同仿函数，对数据类型进行适配转化。
对于set，数据类型就是K，返回原值即可：
//仿函数，将数据类型转化为要比较的K值
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};而对于map而言，获取到的数据类型是pair<const K, V>，需要返回其第一个成员K，用作比较。
//仿函数，将数据类型转化为要比较的K值
struct MapKeyOfT
{
const K& operator()(const pair<const K, V>& _kv)
{
return _kv.first;
}
};接下来，我们需要给红黑树新增一个模板参数KeyOfT，用于接收两种不同的仿函数：
//红黑树类
template<class K, class T, class KeyOfT>
class RBTree在set和map中传入各自的仿函数给第三个模板参数：
//set
RBTree<K, const K, SetKeyOfT> _rbtree;
//map
RBTree<K, pair<const K, V>, MapKeyOfT> _rbtree;最后，修改红黑树的Insert和Find代码， 以适配Key值比较：
（注：所有需要进行键值比较的位置都需要进行仿函数转化。）
KeyOfT _kot;//红黑树中新增一个仿函数对象便于调用//插入
//bool Insert(const pair<K, V>& kv)
bool Insert(const T& data)//参数修改为T类型的data
{
if (_root == nullptr)
{
//_root = new Node(kv);
_root = new Node(data);//改名
_root->_col = BLACK;
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
//if (kv.first < cur->_kv.first)
if(_kot(data) < _kot(cur->_data))//仿函数包装data，转化为K值进行比较
{
parent = cur;
cur = cur->_left;
}
//else if (kv.first > cur->_kv.first)
else if(_kot(data) > _kot(cur->_data))//仿函数包装data
{
parent = cur;
cur = cur->_right;
}
else
{
return false;
}
}
//cur = new Node(kv);
cur = new Node(data);//改名
//if (kv.first < parent->_kv.first)
if (_kot(data) < _kot(parent->_data))//仿函数包装data
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
cur->_parent = parent;
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else
{
if (cur == parent->_left)
{
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else
{
Node* uncle = grandfather->_left;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else
{
if (cur == parent->_right)
{
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return true;
}//查找
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
//if (key < cur->_kv.first)
if(key < _kot(cur->_data))//仿函数包装data
{
cur = cur->_left;
}
//else if (key > cur->_kv.first)
else if(key > _kot(cur->_data))//仿函数包装data
{
cur = cur->_right;
}
else
{
return cur;
}
}
return nullptr;
}这样，尽管数据类型不同，但set和map传入各自的仿函数，然后对所有需要进行比较的data值进行适当的转化，就能保证插入和查找时进行比较的是Key值。
3. 迭代器实现
set和map的迭代器是双向迭代器，由于红黑树特殊的物理结构，我们实现迭代器的方式与list相同，也是对原生指针进行封装，然后通过重载运算符实现指针的各种行为。
为减少代码冗余，本次的迭代器实现当中，两种容器也将封装同一份迭代器代码。
迭代器类型定义如下：
//迭代器
template<class T, class Ref, class Ptr>
struct rbtree_iterator
{
typedef RBTreeNode<T> Node;
typedef rbtree_iterator<T, Ref, Ptr> Self;
Node* _ptr;//指向当前节点
Node* _root;//指向红黑树的根节点，方便后续表示根节点
};接下来实现迭代器的各种操作接口：
迭代器的构造函数
//迭代器构造
rbtree_iterator(Node* ptr, Node* root)
:_ptr(ptr)
,_root(root)
{}*重载和->重载
这两种运算符重载的实现方式与list相同，返回_ptr指向data的值以及地址。
//解引用重载
Ref operator*()
{
return _ptr->_data;
}
//结构成员间接访问重载
Ptr operator->()
{
return &(_ptr->_data);
}前置++
由于set和map的正向遍历遵循二叉树的中序遍历原则，因此实现operator++时，需要找到当前节点在中序遍历中的下一个节点，然后移动指针。有两种情况需要讨论：
情况一：当前节点的右子树不为空
如图，当前节点是2时，其右子树不为空，中序需要访问的下一个节点就是3；当前节点是4时，中序的下一个节点是5；当前节点是6，中序的下一个节点就是7。所以当前节点的右子树不为空时，寻找右子树的最小值（也就是右子树的最左节点）。
情况二：当前节点的右子树为空
由图可知，当前节点的右子树为空时，下一个节点不外乎在其祖先当中。所以要让cur沿着祖先路径向上寻找。寻找过程中，若cur是其父亲的左孩子，则父亲就是下一个访问的节点；若cur已经走到根节点处，则说明已经遍历完成。
如上图所示：
当前节点是3，右子树为空，则向上寻找。3是2的右孩子，继续向上寻找。2是4的左孩子，则4是中序的下一个节点。
当前节点是9，右子树为空，向上寻找。直到找到根节点4，也没有出现左孩子，说明遍历完成。
代码实现：
//前置++
Self& operator++()
{
if (_ptr->_right)//右子树存在，寻找右子树的最左节点
{
Node* rightMin = _ptr->_right;
while (rightMin->_left)//循环往左走，直到叶子节点
{
rightMin = rightMin->_left;
}
_ptr = rightMin;//移动_ptr指针
}
else//右子树不存在，向上寻找
{
//标记当前节点和父亲
Node* cur = _ptr;
Node* parent = cur->_parent;
//父亲存在且cur是父亲的右孩子，一直向上找
while (parent && parent->_right == cur)
{
cur = parent;
parent = parent->_parent;
}
//此时两种情况：一是父亲不存在，说明cur已经走到根；二是cur是父亲的左孩子，找到了
//直接将父节点赋值给_ptr，若遍历完成则_ptr是空；若没有则_ptr就是下一个节点
_ptr = parent;
}
return *this;
}前置--
前置--的实现逻辑与前置++基本相似（遵循 “ 反向中序遍历 ” ），但需要考虑已经遍历结束（_ptr指向空）的情况：
当_ptr指向空时，--操作需要找到前一个节点（也就是中序遍历的最后一个节点），即整颗树的最右节点。
其余实现逻辑与++操作刚好对称：
若当前节点左子树不为空，则寻找左子树最右节点。 若左子树为空，则向上寻找，直到cur是父亲的右孩子或走到根节点处。
代码实现：
//前置--
Self& operator--()
{
if (_ptr == nullptr)//已经遍历结束的情况
{
Node* cur = _root;
while (cur && cur->_right)//循环寻找最右节点
{
cur = cur->_right;
}
_ptr = cur;
}
else if (_ptr->_left)//左子树存在，寻找左子树最右节点
{
Node* leftMax = _ptr->_left;
while (leftMax->_right)
{
leftMax = leftMax->_right;
}
_ptr = leftMax;
}
else//左子树不存在，向上寻找右孩子的父亲
{
Node* cur = _ptr;
Node* parent = cur->_parent;
while(parent && parent->_left == cur)
{
cur = parent;
parent = parent->_parent;
}
_ptr = parent;
}
return *this;
}后置++和--
后置++/--直接调用前置++/--，然后记录中间变量即可。
//后置++
Self operator++(int)
{
Self tmp(*this);
++(*this);
return tmp;
}
//后置--
Self operator--(int)
{
Self tmp(*this);
--(*this);
return tmp;
}operator!=
判断它们的_ptr指针是否相等。
//!=运算符重载
bool operator!=(const Self& it)
{
return _ptr != it._ptr;
}迭代器全部实现代码：
//迭代器
template<class T, class Ref, class Ptr>
struct rbtree_iterator
{
typedef RBTreeNode<T> Node;
typedef rbtree_iterator<T, Ref, Ptr> Self;
Node* _ptr;//指向当前节点
Node* _root;//指向红黑树的根节点，方便后续表示根节点
//迭代器构造
rbtree_iterator(Node* ptr, Node* root)
:_ptr(ptr)
,_root(root)
{}
//解引用重载
Ref operator*()
{
return _ptr->_data;
}
//结构成员间接访问重载
Ptr operator->()
{
return &(_ptr->_data);
}
//前置++
Self& operator++()
{
if (_ptr->_right)//右子树存在，寻找右子树的最左节点
{
Node* rightMin = _ptr->_right;
while (rightMin->_left)//循环往左走，直到叶子节点
{
rightMin = rightMin->_left;
}
_ptr = rightMin;//移动_ptr指针
}
else//右子树不存在，向上寻找左孩子的父亲
{
//标记当前节点和父亲
Node* cur = _ptr;
Node* parent = cur->_parent;
//父亲存在且cur是父亲的右孩子，一直向上找
while (parent && parent->_right == cur)
{
cur = parent;
parent = parent->_parent;
}
//此时两种情况：一是父亲不存在，说明cur已经走到根；二是cur是父亲的左孩子，找到了
//直接将父节点赋值给_ptr，若遍历完成则_ptr是空；若没有则_ptr就是下一个节点
_ptr = parent;
}
return *this;
}
//前置--
Self& operator--()
{
if (_ptr == nullptr)//已经遍历结束的情况
{
Node* cur = _root;
while (cur && cur->_right)//循环寻找最右节点
{
cur = cur->_right;
}
_ptr = cur;
}
else if (_ptr->_left)//左子树存在，寻找左子树最右节点
{
Node* leftMax = _ptr->_left;
while (leftMax->_right)
{
leftMax = leftMax->_right;
}
_ptr = leftMax;
}
else//左子树不存在，向上寻找右孩子的父亲
{
Node* cur = _ptr;
Node* parent = cur->_parent;
while(parent && parent->_left == cur)
{
cur = parent;
parent = parent->_parent;
}
_ptr = parent;
}
return *this;
}
//后置++
Self operator++(int)
{
Self tmp(*this);
++(*this);
return tmp;
}
//后置--
Self operator--(int)
{
Self tmp(*this);
--(*this);
return tmp;
}
//!=运算符重载
bool operator!=(const Self& it)
{
return _ptr != it._ptr;
}
};4. set和map迭代器接口实现和适配
首先在红黑树以及set和map内部声明迭代器类型：
//红黑树
typedef rbtree_iterator<T, T&, T*> Iterator;//普通迭代器
typedef rbtree_iterator<T, const T&, const T*> ConstIterator;//const迭代器//set
typedef typename RBTree<K, const K, SetKeyOfT>::Iterator iterator;//二次封装普通迭代器
typedef typename RBTree<K, const K, SetKeyOfT>::ConstIterator const_iterator;//二次封装const迭代器//map
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::Iterator iterator;//二次封装普通迭代器
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::ConstIterator const_iterator;//二次封装const迭代器注意：这里typename的作用是告诉编译器Iterator和ConstIterator是类型名，缺失会编译报错。
然后在红黑树内部实现迭代器接口：
Iterator Begin()
{
//整棵树的最左节点即首元素
Node* cur = _root;
while (cur && cur->_left)
{
cur = cur->_left;
}
return Iterator(cur, _root);
}
Iterator End()
{
//尾迭代器的_ptr指针制为空
return Iterator(nullptr, _root);
}
ConstIterator Begin() const
{
//整棵树的最左节点即首元素
Node* cur = _root;
while (cur && cur->_left)
{
cur = cur->_left;
}
return ConstIterator(cur, _root);
}
ConstIterator End() const
{
//尾迭代器的_ptr指针制为空
return ConstIterator(nullptr, _root);
}在set和map中，对以上接口进行封装调用：
iterator begin()
{
return _rbtree.Begin();
}
iterator end()
{
return _rbtree.End();
}
const_iterator begin() const
{
return _rbtree.Begin();
}
const_iterator end() const
{
return _rbtree.End();
}迭代器实现完成之后，我们再对Insert和Find函数的返回值进行迭代器适配修改：
//插入
//bool Insert(const T& data)
pair<Iterator, bool> Insert(const T& data)//返回迭代器和布尔值的二元组
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
//return true;
return { Iterator(_root,_root),true };//插入成功返回新元素迭代器和true
}
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 false;
return { Iterator(cur, _root), false };//插入失败返回重复元素的迭代器和false
}
}
cur = new Node(data);
if (_kot(data) < _kot(parent->_data))
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
cur->_parent = parent;
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else
{
if (cur == parent->_left)
{
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else
{
Node* uncle = grandfather->_left;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else
{
if (cur == parent->_right)
{
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
//return true;
return { Iterator(cur,_root),true };//插入成功返回新元素迭代器和true
}//查找
//Node* Find(const K& key)
Iterator Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if(key < _kot(cur->_data))
{
cur = cur->_left;
}
else if(key > _kot(cur->_data))
{
cur = cur->_right;
}
else
{
//return cur;
return Iterator(cur, _root);//找到了，返回该元素迭代器
}
}
//return nullptr;
return Iterator(nullptr, _root);//没找到，返回尾迭代器
}5. set和map功能实现
之前我们已经实现了封装实现了set和map的迭代器接口，最后封装Insert和Find接口，以及实现map的operator[ ]接口。
insert和find
直接对红黑树的Insert和Find函数进行封装调用即可：
//set
pair<iterator, bool> insert(const K& key)
{
return _rbtree.Insert(key);
}
iterator find(const K& key)
{
return _rbtree.Find(key);
}//map
pair<iterator, bool> insert(const pair<K, V>& kv)
{
return _rbtree.Insert(kv);
}
iterator find(const K& key)
{
return _rbtree.Find(key);
}map的operator[ ]
operator既支持元素插入，也支持修改，是因为其底层封装了insert方法，并且返回了Value值的引用。代码实现如下：
V& operator[](const K& key)
{
pair<iterator, bool> ret = insert({ key,V() });
return ret.first->second;//返回迭代器指向元素的Value值的引用
}至此，通过对同一棵红黑树进行封装和适配，两种容器的基本功能已经实现完成。
三、测试
写一段代码测试我们实现的set和map：
void test_set()
{
Set<int> s;
s.insert(5);
s.insert(3);
s.insert(1);
s.insert(7);
s.insert(0);
s.insert(9);
s.insert(6);
s.insert(4);
for (auto& e : s)
{
cout << e << ' ';
}
cout << endl;
}运行结果：
void test_map()
{
string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
Map<string, int> m;
for (auto& str : arr)
{
m[str]++;
}
for (auto& kv : m)
{
cout << kv.first << ':' << kv.second << endl;
}
}运行结果：
四、程序全部代码
set和map实现相关的全部代码如下：
RBTree.h
#pragma once
#include <iostream>
#include <utility>
using namespace std;
enum Color//枚举值表示颜色
{
RED,
BLACK
};
//节点
template<class T>
struct RBTreeNode
{
T _data;//将pair改为T对象
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
Color _col;
RBTreeNode(const T& data)
:_data(data)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _col(RED)
{}
};
//迭代器
template<class T, class Ref, class Ptr>
struct rbtree_iterator
{
typedef RBTreeNode<T> Node;
typedef rbtree_iterator<T, Ref, Ptr> Self;
Node* _ptr;//指向当前节点
Node* _root;//指向红黑树的根节点，方便后续表示根节点
//迭代器构造
rbtree_iterator(Node* ptr, Node* root)
:_ptr(ptr)
, _root(root)
{}
//解引用重载
Ref operator*()
{
return _ptr->_data;
}
//结构成员间接访问重载
Ptr operator->()
{
return &(_ptr->_data);
}
//前置++
Self& operator++()
{
if (_ptr->_right)//右子树存在，寻找右子树的最左节点
{
Node* rightMin = _ptr->_right;
while (rightMin->_left)//循环往左走，直到叶子节点
{
rightMin = rightMin->_left;
}
_ptr = rightMin;//移动_ptr指针
}
else//右子树不存在，向上寻找左孩子的父亲
{
//标记当前节点和父亲
Node* cur = _ptr;
Node* parent = cur->_parent;
//父亲存在且cur是父亲的右孩子，一直向上找
while (parent && parent->_right == cur)
{
cur = parent;
parent = parent->_parent;
}
//此时两种情况：一是父亲不存在，说明cur已经走到根；二是cur是父亲的左孩子，找到了
//直接将父节点赋值给_ptr，若遍历完成则_ptr是空；若没有则_ptr就是下一个节点
_ptr = parent;
}
return *this;
}
//前置--
Self& operator--()
{
if (_ptr == nullptr)//已经遍历结束的情况
{
Node* cur = _root;
while (cur && cur->_right)//循环寻找最右节点
{
cur = cur->_right;
}
_ptr = cur;
}
else if (_ptr->_left)//左子树存在，寻找左子树最右节点
{
Node* leftMax = _ptr->_left;
while (leftMax->_right)
{
leftMax = leftMax->_right;
}
_ptr = leftMax;
}
else//左子树不存在，向上寻找右孩子的父亲
{
Node* cur = _ptr;
Node* parent = cur->_parent;
while (parent && parent->_left == cur)
{
cur = parent;
parent = parent->_parent;
}
_ptr = parent;
}
return *this;
}
//后置++
Self operator++(int)
{
Self tmp(*this);
++(*this);
return tmp;
}
//后置--
Self operator--(int)
{
Self tmp(*this);
--(*this);
return tmp;
}
//!=运算符重载
bool operator!=(const Self& it)
{
return _ptr != it._ptr;
}
};
//红黑树类
template<class K, class T, class KeyOfT>
class RBTree
{
typedef RBTreeNode<T> Node;//将第二个模板参数T作为节点的数据类型
public:
typedef rbtree_iterator<T, T&, T*> Iterator;//普通迭代器
typedef rbtree_iterator<T, const T&, const T*> ConstIterator;//const迭代器
//强制生成无参构造
RBTree() = default;
//拷贝构造
RBTree(const RBTree<K, T, KeyOfT>& t)
{
_root = _Copy(t._root);
}
//析构函数
~RBTree()
{
_Destroy(_root);
}
Iterator Begin()
{
//整棵树的最左节点即首元素
Node* cur = _root;
while (cur && cur->_left)
{
cur = cur->_left;
}
return Iterator(cur, _root);
}
Iterator End()
{
//尾迭代器的_ptr指针制为空
return Iterator(nullptr, _root);
}
ConstIterator Begin() const
{
//整棵树的最左节点即首元素
Node* cur = _root;
while (cur && cur->_left)
{
cur = cur->_left;
}
return ConstIterator(cur, _root);
}
ConstIterator End() const
{
//尾迭代器的_ptr指针制为空
return ConstIterator(nullptr, _root);
}
//插入
pair<Iterator, bool> Insert(const T& data)
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return { Iterator(_root,_root),true };//插入成功返回新元素迭代器和true
}
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 { Iterator(cur, _root), false };//插入失败返回重复元素的迭代器和false
}
}
cur = new Node(data);
if (_kot(data) < _kot(parent->_data))
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
cur->_parent = parent;
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else
{
if (cur == parent->_left)
{
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else
{
Node* uncle = grandfather->_left;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else
{
if (cur == parent->_right)
{
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return { Iterator(cur,_root),true };//插入成功返回新元素迭代器和true
}
//查找
Iterator Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (key < _kot(cur->_data))
{
cur = cur->_left;
}
else if (key > _kot(cur->_data))
{
cur = cur->_right;
}
else
{
return Iterator(cur, _root);//找到了，返回该元素迭代器
}
}
return Iterator(nullptr, _root);//没找到，返回尾迭代器
}
private:
//右单旋
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR) subLR->_parent = parent;
Node* ppNode = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (parent == _root)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (ppNode->_left == parent) ppNode->_left = subL;
else ppNode->_right = subL;
subL->_parent = ppNode;
}
}
//左单旋
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL) subRL->_parent = parent;
Node* ppNode = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
if (parent == _root)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (ppNode->_left == parent) ppNode->_left = subR;
else ppNode->_right = subR;
subR->_parent = ppNode;
}
}
//拷贝构造
Node* _Copy(Node* root, Node* parent = nullptr)
{
if (root == nullptr) return nullptr;
Node* NewRoot = new Node(root->_kv);
NewRoot->_col = root->_col;
NewRoot->_parent = parent;
NewRoot->_left = _Copy(root->_left, NewRoot);
NewRoot->_right = _Copy(root->_right, NewRoot);
return NewRoot;
}
//销毁
void _Destroy(Node* root)
{
if (root == nullptr) return;
_Destroy(root->_left);
_Destroy(root->_right);
delete root;
}
Node* _root = nullptr;
KeyOfT _kot;//新增一个仿函数对象便于调用
};Set.h
#pragma once
#include "RBTree.h"
template<class K>
class Set
{
//仿函数，将数据类型转化为要比较的K值
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;//二次封装const迭代器
iterator begin()
{
return _rbtree.Begin();
}
iterator end()
{
return _rbtree.End();
}
const_iterator begin() const
{
return _rbtree.Begin();
}
const_iterator end() const
{
return _rbtree.End();
}
pair<iterator, bool> insert(const K& key)
{
return _rbtree.Insert(key);
}
iterator find(const K& key)
{
return _rbtree.Find(key);
}
private:
RBTree<K, const K, SetKeyOfT> _rbtree;
};Map.h
#pragma once
#include "RBTree.h"
template<class K, class V>
class Map
{
//仿函数，将数据类型转化为要比较的K值
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;//二次封装普通迭代器
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::ConstIterator const_iterator;//二次封装const迭代器
iterator begin()
{
return _rbtree.Begin();
}
iterator end()
{
return _rbtree.End();
}
const_iterator begin() const
{
return _rbtree.Begin();
}
const_iterator end() const
{
return _rbtree.End();
}
pair<iterator, bool> insert(const pair<K, V>& kv)
{
return _rbtree.Insert(kv);
}
iterator find(const K& key)
{
return _rbtree.Find(key);
}
V& operator[](const K& key)
{
pair<iterator, bool> ret = insert({ key,V() });
return ret.first->second;//返回迭代器指向元素的Value值的引用
}
private:
RBTree<K, pair<const K, V>, MapKeyOfT> _rbtree;
};总结
本篇文章我们基于之前实现的红黑树模拟实现了set和map两种容器。不难发现，加入了模板和仿函数之后，两种容器能共用同一份红黑树代码，大大减少了代码冗余。如果你觉得博主讲的还不错，就请留下一个小小的赞在走哦，感谢大家的支持❤❤❤
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2025-02-13，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
