当前位置： 首页 > news >正文

【C++】论如何封装红黑树模拟实现set和map

news 2025/7/28 7:46:44

在这里插入图片描述
各位大佬好，我是落羽！一个坚持不断学习进步的大学生。
如果您觉得我的文章有所帮助，欢迎多多互三分享交流，一起学习进步！
也欢迎关注我的blog主页: 落羽的落羽

上一篇文章【C++】红黑树，详解其规则与插入操作，认识学习了红黑树，今天我们利用它来学习模拟实现STL库中的set和map

文章目录

  • 一、STL源码分析
  • 二、模拟实现myset和mymap
    • 1. 实现红黑树及其insert操作
    • 2. 实现set和map框架
    • 3. 实现iterator
    • 4. map的[ ]重载
    • 5. set和map的完整结构

一、STL源码分析

STL库中的set和map，是用红黑树封装实现了，它们的结构定义源码分别在set、map、stl_set.h、stl_map.h、stl_tree.h等头文件中

以下是部分源码截图：
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
可以看出，源码中的rb_tree（红黑树）也是运用了泛型思维来满足set的key场景和map的key/value场景。rb_tree的前两个模板参数是_Key，_Value，set中这两个传的都是key类型；map中第一个传key类型，第二个传key和value的pair。

源码中模板参数T代表value，而内部写的value_type不是我们说的key/value的value，而是代表红黑树结点中存储的真实的数据的类型。源码的命名风格较为混乱也是一个小缺陷。

那么，既然rb_tree的第二个模板参数_Value已经控制了红黑树中存储的数据类型，为什么还要有第一个模板参数_Key呢？这是因为对于set和map，find/erase操作函数参数只需要key，所以第一个模板参数_Key是传给find/erase等函数做形参类型的。但insert操作不同，set需要传key对象，map需要传pair对象。第二个模板参数_Value就是控制这个的。

二、模拟实现myset和mymap

我们的实现过程可以分为以下步骤，一步一步来：

  • 实现红黑树，且支持insert操作
  • 实现set和map框架
  • 实现iterator
  • map的[ ]重载

1. 实现红黑树及其insert操作

key参数类型用K表示，value参数类型用V表示，红黑树结点存储数据类型用T表示，那么红黑树的代码也要做出一些调整。
问题来了，由于泛型，RBTree中不知道T是K还是pair<K,V>，insert内部需要进行插入逻辑比较key时，就无法进行。如果T是K，还好说，直接比较就好了；但T是pair时，就不能直接对pair对象进行<操作符运算了，因为库中默认的pair对象的<方法并不符合我们的需求，我们需要的是只比较pair中的key，库中的不是这个逻辑：在这里插入图片描述

所以，我们的红黑树需要增加一个类型参数Key_Of_T作为仿函数，作用是取出T对象中的key。然后在map层和set层中分别写出对应的仿函数类重载()：map是返回pair的key，set是直接返回key。再各自传给RBTree，RBTree中涉及使用key的地方则改变为Key_Of_T

//RBTree.h
enum Color
{RED,BLACK
};template<class T>
struct RBTreeNode
{T _data;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 Key_Of_T>
class RBTree
{typedef RBTreeNode<T> Node;public:bool Insert(const T& data){if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return true;}Node* parent = nullptr;Node* cur = _root;Key_Of_T kot;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 false;}}cur = new Node(data);cur->_col = RED;cur->_parent = parent;if (kot(parent->_data) < kot(data)){parent->_right = cur;}else{parent->_left = cur;}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;}private:Node* _root = nullptr;void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;Node* parentParent = parent->_parent;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;parent->_parent = subL;if (parentParent == nullptr){_root = subL;subL->_parent = nullptr;}else{if (parent == parentParent->_left){parentParent->_left = subL;}else{parentParent->_right = subL;}subL->_parent = parentParent;}}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;Node* parentParent = parent->_parent;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;parent->_parent = subR;if (parentParent == nullptr){_root = subR;subR->_parent = nullptr;}else{if (parent == parentParent->_left){parentParent->_left = subR;}else{parentParent->_right = subR;}subR->_parent = parentParent;}}
};

2. 实现set和map框架

set和map的私有成员只需要一个红黑树，然后还需各自内部提供一个Key_Of_T仿函数，传给红黑树。

#include"RBTree.h"
namespace lydly
{template<class K>class set{struct set_Key_of_T{const K& operator()(const K& key){return key;}};public:bool insert(const K& key){return _t.Insert(key);}private://保证key不被修改RBTree<K, const K, set_Key_of_T> _t;};
}

#include"RBTree.h"
namespace lydly
{template<class K, class V>class map{struct map_Key_of_T{const K& operator()(const pair<K, V>& kv){return kv.first;}};public:bool insert(const pair<K, V>& kv){return _t.Insert(kv);}private://pair可能被修改，里面的key加上const防止被修改RBTree<K, pair<const K, V>, map_Key_of_T> _t;};
}

3. 实现iterator

实现的map和set的迭代器，大体思路和list的迭代器是一样的，用一个类封装结点的指针类型，再重载一系列运算符。

//在list的文章中介绍过，还需实现const版本迭代器，因此模板参数需要Ref和Ptr
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){ }
};

库中迭代器的遍历顺序是按照中序进行的，begin()返回的也是中序的第一个结点（最左结点）的迭代器，end()返回的是中序的最后一个结点（最右结点）的下一个位置的迭代器。
begin()很好说，找到最左结点后返回它的迭代器就好；至于end()，我们用nullptr构造迭代器返回，这样做有一个问题，正常的end()--能找到最后一个结点的迭代器，解决方法是实现--重载时特殊判断处理一下就好。

那么我们的迭代器该怎么实现++和–呢？

以++为例，核心逻辑是“只看局部”，只考虑当前结点的下一个要访问的结点是哪个。

  • 迭代器it++时，如果it指向结点的右子树不为空，说明it的左子树和其自身已经遍历完了，下一个结点是右子树的中序第一个结点，也就是右子树的最左结点。
  • it++时，如果it指向结点的右子树为空，说明以当前结点为根的子树已经全部遍历完了，要访问的下一个结点要去祖先里找。
    • 如果当前结点是其父亲的左，根据中序是“左根右”，那么下一个结点就是这个父亲了。
    • 如果当前结点是其父亲的右，说明这个父亲也已经访问过了，以这个父亲为根的子树也都遍历完了，那么下一个结点就还要继续看父亲的父亲，还是上述规则。
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;while (parent && cur == parent->_right){cur = parent;parent = cur->_parent;}_node = parent;}return *this;
}

--是一样的逻辑，只是反过来。

Self& operator--()
{if (_node == nullptr){//此时迭代器是end()，--后需要指向整棵树的最右结点Node* rightMost = _root;while (rightMost && rightMost->_right){rightMost = rightMost->_right;}_node = rightMost;}else if(_node->_left){//左子树不为空,下一个结点是左子树的最右结点Node* rightMost = _node->_left;while (rightMost->_right){rightMost->_right;}_node = rightMost;}else{//左子树为空，下一个结点要去祖先里找Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_left){cur = parent;parent = cur->_parent;}_node = parent;}return *this;
}

解决了这两个问题，迭代器剩下的一些常用接口就好说了，以下是实现的完整代码：

//RBTree.h
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;while (parent && cur == parent->_right){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}Self& operator--(){if (_node == nullptr){//此时迭代器是end()，--后需要指向整棵树的最右结点Node* rightMost = _root;while (rightMost && rightMost->_right){rightMost = rightMost->_right;}_node = rightMost;}else if(_node->_left){//左子树不为空,下一个结点是左子树的最右结点Node* rightMost = _node->_left;while (rightMost->_right){rightMost->_right;}_node = rightMost;}else{//左子树为空，下一个结点要去祖先里找Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_left){cur = parent;parent = cur->_parent;}_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;}};

然后，我们就可以在RBTree中补充几个迭代器相关的接口:
在这里插入图片描述在这里插入图片描述

除此之外，原版的insert返回是pair<iterator, bool>，所以我们也这样写，insert中需要修改一些地方。

pair<Iterator, bool> Insert(const T& data)
{if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return { Iterator(_root, _root), true };}Node* parent = nullptr;Node* cur = _root;Key_Of_T kot;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 { Iterator(cur, _root), false };}}cur = new Node(data);//newnode保存新增结点位置Node* newnode = cur;cur->_col = RED;cur->_parent = parent;if (kot(parent->_data) < kot(data)){parent->_right = cur;}else{parent->_left = cur;}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(newnode,_root), true };
}

4. map的[ ]重载

由于RBTree的Insert返回的是pair<iterator, bool>，利用iterator就能找到对应的value了。

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

5. set和map的完整结构

#include"RBTree.h"
namespace lydly
{template<class K, class V>class map{struct map_Key_of_T{const K& operator()(const pair<K, V>& kv){return kv.first;}};public:typedef typename RBTree<K, pair<const K, V>, map_Key_of_T>::Iterator iterator;typedef typename RBTree<K, pair<const K, V>, map_Key_of_T>::ConstIterator const_iterator;iterator begin(){return _t.Begin();}iterator end(){return _t.End();}const_iterator begin() const{return _t.Begin();}const_iterator end() const{return _t.End();}iterator find(const K& key){return _t.Find(key);}pair<iterator, bool> insert(const pair<K, V>& kv){return _t.Insert(kv);}V& operator[](const K& key){pair<iterator, bool> ret = _t.Insert({ key, V() });return ret.first->second;}private:RBTree<K, pair<const K, V>, map_Key_of_T> _t;};
}

#include"RBTree.h"
namespace lydly
{template<class K>class set{struct set_Key_of_T{const K& operator()(const K& key){return key;}};public:typedef typename RBTree<K, const K, set_Key_of_T>::Iterator iterator;typedef typename RBTree<K, const K, set_Key_of_T>::ConstIterator const_iterator;iterator begin(){return _t.Begin();}iterator end(){return _t.End();}const_iterator begin() const{return _t.Begin();}const_iterator end() const{return _t.End();}iterator find(const K& key){return _t.Find(key);}pair<iterator, bool> insert(const K& key){return _t.Insert(key);}private:RBTree<K, const K, set_Key_of_T> _t;};
}

简单测试：
在这里插入图片描述

本文完整项目代码已上传至我的gitee仓库，欢迎浏览：
https://gitee.com/zhang-yunkai060524/luoyu-c-language

本篇完，感谢阅读。

http://www.lryc.cn/news/601398.html

相关文章：

  • Java全栈面试实战：从JVM到AI的技术演进之路
  • JavaScript手录07-数组
  • LangChain实现RAG
  • JavaSE-String类
  • Rust赋能智能土木工程革新
  • 【奔跑吧！Linux 内核（第二版）】第5章：内核模块
  • 栈----4.每日温度
  • 2.qt调试日志输出
  • 多智能体系统设计：协作、竞争与涌现行为
  • Day4.AndroidAudio初始化
  • bash的特性-常用的通配符
  • bash的特性-命令和文件自动补全
  • C++ 多线程（一）
  • 第六章 JavaScript 互操（2）.NET调用JS
  • ios UIAppearance 协议
  • 「iOS」————消息传递和消息转发
  • 携带参数的表单文件上传 axios, SpringBoot
  • 深度解读Go 变量指针
  • [每周一更]-(第152期)：Go中的CAS（Compare-And-Swap）锁原理详解
  • iOS安全和逆向系列教程 第20篇：Objective-C运行时机制深度解析与Hook技术
  • 结合Golang语言说明对多线程编程以及 select/epoll等网络模型的使用
  • goland编写go语言导入自定义包出现： package xxx is not in GOROOT (/xxx/xxx) 的解决方案
  • 学习Python中Selenium模块的基本用法（1：简介）
  • Day06–哈希表–242. 有效的字母异位词，349. 两个数组的交集，202. 快乐数，1. 两数之和
  • 仓库管理系统-2-后端之基于继承基类的方式实现增删改查
  • 7.25 C/C++蓝桥杯 |排序算法【下】
  • macOS 安装 Homebrew
  • JavaScript事件（event）对象方法与属性
  • mac配置多版本jdk
  • C#中Visual Studio平台按照OfficeOpenXml步骤