红黑树的封装
一、封装思路
在 STL 中 map set 的底层就是封装了一棵红黑树。
其中连接红黑树和容器的是迭代器,map set 暴露出的接口都不是自己写的,而是红黑树写的,外部接口封装红黑树接口。
所以写出红黑树为 map set 写的接口,再在上层的 map set 类中包装一下即可。
之前的红黑树就是单纯的在树上插入节点,为了实现 map set 就需要红黑树再实现迭代器。
二、红黑树细节实现
1、迭代器
本质就是封装了一个节点,用于遍历红黑树找到目标值。
(1)整体设计
与链表迭代器一样,需要迭代器重载解引用和箭头,所以模板依旧设计成:
template<class T, class Ref, class Ptr>
来适应 const 迭代器的复用。
(2)重载解引用
// 解引用迭代器是取数据
Ref operator*()
{return _node->_data;
}
(3)重载箭头
// 取数据的地址
Ptr operator->()
{return &(_node->_data);
}
(4)重载不等于
bool operator!=(const Self& it)
{return _node != it._node;
}
(5)后置++
// 1.如果右子树存在,访问右子树的最左节点
// 2.如果右子树不存在,如果我是父亲的左,那就访问父亲
// 如果我是父亲的右,表示父亲也完了,向上判断,直到是左孩子
Self& operator++()
{if (_node->_right){Node* cur = _node->_right;while (cur->_left)cur = cur->_left;_node = cur;}else{Node* cur = _node;while (cur->_parent && cur == cur->_parent->_right)cur = cur->_parent;_node = cur->_parent;}return *this;
}
(6)后置--
// 1.如果左子树存在,返回左子树的最右节点
// 2.如果左子树不存在,如果是父亲的右孩子,返回根
// 如果是父亲的左孩子,向上找直到是右孩子
Self& operator--()
{Node* cur = _node;if (_node->_left){while (cur->_right)cur = cur->_right;_node = cur;}else{while (cur && cur == cur->_parent->_left)cur = cur->_parent;_node = cur->_parent;}return *this;
}
2、红黑树
到这里迭代器已经实现完毕,要把裸的迭代器实现出不同的形式花样就是在红黑树这一层实现的。
(1)整体设计
从这里开始就要考虑如何把容器与红黑树相关联。
难点一
map 是 kv 模型,set 是 key 模型,类型都不一样,怎么防止在一份红黑树代码中参数的冲突?
库里面的解决办法是:template<class K, class T>
这里的 T 是存放的数据类型,即 map 是 pair<K, V>,set 是 K,这样至少能传入正确的参数了。
但是红黑树主要功能插入删除的比较参数是 key,所以直接传入的参数 T 用于比较(map 的 pair<K, V> 比较逻辑是 K 大的就返回,K 不大就 V 大的返回,显然不符合比较逻辑)是不行的,我们需要都是比较 K,所以还需要一个内部类提取 map set 的 key 值。
所以最终的红黑树模板参数如下:
template<class K, class T, class KeyOfT>
K 是 key 的类型,T 是容器存储的数据类型,KeyOfT 是分别在 map 和 set 中实现的内部类分别提取其中的 key 用于插入删除函数的比较。
难点二
迭代器分为 const 迭代器和非 const 迭代器,所以在红黑树中也要封装。
不用写两份迭代器代码,之前迭代器的模板参数就起作用了:其实 const 和非 const 的区别就是指向的内容不能修改,就是解引用和箭头的重载返回值不能被修改,利用模板实例化就能解决问题:
// 红黑树中定义两个迭代器,模板参数不同即可
typedef __RBTreeIterator<T, T&, T*> Iterator;
typedef __RBTreeIterator<T, const T&, const T*> ConstIterator;
(2)构造析构
由于已经要和容器接轨了,所以要考虑深浅拷贝问题,这里封装了常见的默认成员函数
RBTree() = default; // 由于已经写了拷贝构造,强制生成默认构造// 私有的概念只针对于类外,类内可以访问其他对象的私有成员
RBTree(const RBTree<K, T, KeyOfT>& tree)
{_root = Copy(tree._root);
}RBTree<K, T, KeyOfT>& operator=(RBTree<K, T, KeyOfT> tree)
{swap(_root, tree._root);
}~RBTree()
{Destroy(_root);_root = nullptr;
}
(3)迭代器封装
在迭代器类中已经处理了迭代器的使用逻辑,在红黑树这一层就是封装容器的迭代器常用功能
Iterator begin()
{Node* leftMin = _root;while (leftMin && leftMin->_left)leftMin = leftMin->_left;return leftMin;
}Iterator end()
{return Iterator(nullptr);
}ConstIterator begin() const
{Node* leftMin = _root;while (leftMin && leftMin->_left)leftMin = leftMin->_left;return leftMin;
}ConstIterator end() const
{return ConstIterator(nullptr);
}
注意 const 迭代器函数后面需要加 const 构成函数重载。
(4)insert 改造
和库里面保持一致,插入函数返回插入元素的迭代器和是否插入成功的 pair
为了比较的正确性要利用内部类 KeyOfT 来取出数据的 key 进行比较
pair<Iterator, bool> insert(const T& data)
{if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return {_root, true};}Node* cur = _root;Node* parent = cur;KeyOfT kot;// 1.像搜索二叉树一样插入节点curwhile (cur){if (kot(cur->_data) > kot(data)){parent = cur;cur = cur->_left;}else if (kot(cur->_data) < kot(data)){parent = cur;cur = cur->_right;}elsereturn {cur, false};}cur = new Node(data);Node* newnode = cur;if (kot(parent->_data) < kot(data))parent->_right = cur;elseparent->_left = cur;cur->_parent = parent;// 新插入是红色,如果父亲是黑色就没事while (parent && parent->_col == RED){Node* g = parent->_parent;Node* uncle = parent == g->_left ? g->_right : g->_left;// 情况一:叔叔存在且为红,u p 变黑,g变红,向上if (uncle && uncle->_col == RED){uncle->_col = parent->_col = BLACK;g->_col = RED;cur = g;parent = cur->_parent;}// 情况二:叔叔存在且为黑或叔叔不存在else{// u parent cur 的位置决定的是左右单旋双旋// gB pB// pR u -> cR gR// cR uif (cur == parent->_left && parent == g->_left){RotateR(g);parent->_col = BLACK;g->_col = RED;}// gB gB cB// pR u -> cR u -> pR gR// cR pR uelse if (cur == parent->_right && parent == g->_left){RotateL(parent);RotateR(g);cur->_col = BLACK;g->_col = RED;}// gB pB// u pR -> gR cR// cR u else if (cur == parent->_right && parent == g->_right){RotateL(g);g->_col = RED;parent->_col = BLACK;}// gB gB cB// u pR -> u cR -> gR pR// cR pR u else if (cur == parent->_left && parent == g->_right){RotateR(parent);RotateL(g);cur->_col = BLACK;g->_col = RED;}elseassert(false);break;}}_root->_col = BLACK;return {newnode, true};
}
三、容器细节实现
首先容器的实现共性是 map set 上层确确实实只传入 <K, V> 和 <K>,是底层红黑树为了适应容器,底层红黑树的实例化是 <K, pair<K, V>, KeyOfT> 和 <K, K, KeyOfT>
其次两者都要实现各自的 KeyOfT 内部类来告诉底层红黑树要怎么取到 key 值。
最后容器封装底层红黑树写好的迭代器代码交给外部使用。
1、set 实现
template<class K>
class set
{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 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, SetKeyOfT> _t;
};
2、map 实现
template<class K, class V>
class map
{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 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>, MapKeyOfT> _t;
};
值得一提的是 map 还要重载 [],其实现逻辑已经在博客map和set-CSDN博客解释过。
相关文章:
红黑树的封装
一、封装思路 在 STL 中 map set 的底层就是封装了一棵红黑树。 其中连接红黑树和容器的是迭代器,map set 暴露出的接口都不是自己写的,而是红黑树写的,外部接口封装红黑树接口。 所以写出红黑树为 map set 写的接口,再在上层的…...

25.2.3 【洛谷】作为栈的复习不错(学习记录)
今天学习的东西不算多,放了一个星期假,感觉不少东西都没那么清楚,得复习一下才行。今天搞个栈题写,把栈复习一下,明天进入正轨,边复习边学习新东西,应该会有二叉树的学习等等... 【洛谷】P1449 …...

MFC程序设计(七)运行时类信息机制
运行时类信息机制的作用 我们在创建对象时,自己是清楚对象属于哪个类,但是计算机却不清楚。而MFC运行时类信息机制就是解决这个问题而存在的 运行时类信息机制的使用 我们在创建一个类时,只有满足以上三个条件,该类才能支持运行时…...
fflush的概念和使用案例
fflush() 是C语言标准库中用于控制输入/输出缓冲区的函数,其主要功能是强制刷新缓冲区,确保数据及时写入目标设备(如屏幕、文件)。以下是其概念和典型使用场景: 概念 功能: 刷新指定流的缓冲区。对于输出流…...

嵌入式知识点总结 操作系统 专题提升(四)-上下文
针对于嵌入式软件杂乱的知识点总结起来,提供给读者学习复习对下述内容的强化。 目录 1.上下文有哪些?怎么理解? 2.为什么会有上下文这种概念? 3.什么情况下进行用户态到内核态的切换? 4.中断上下文代码中有哪些注意事项? 5.请问线程需要保存哪些…...
React 封装高阶组件 做路由权限控制
React 高阶组件是什么 官方解释∶ 高阶组件(HOC)是 React 中用于复用组件逻辑的一种高级技巧。HOC 自身不是 React API 的一部分,它是一种基于 React 的组合特性而形成的设计模式。 高阶组件(HOC)就是一个函数&…...

【实践案例】基于大语言模型的海龟汤游戏
文章目录 项目背景提示词构建海龟汤主持人真相判断专家 具体实现流程文心一言大语言模型“海龟汤”插件参考 项目背景 “海龟汤”作为一种聚会类桌游,又称情境推理游戏,是一种猜测情境还原事件真相的智力游戏。其玩法是由出题者提出一个难以理解的事件&…...

NeetCode刷题第20天(2025.2.1)
文章目录 106 Best Time to Buy and Sell Stock with Cooldown 使用 Cooldown 买卖股票的最佳时间107 Coin Change II 换币 II108 Target Sum 目标总和109 Interleaving String 交错字符串110 Edit Distance 编辑距离111 Maximum Subarray 最大子数组112 Jump Game 跳跃游戏113…...
DeepSeek:人工智能领域的革新者与未来展望
在当今这个数据驱动的时代,人工智能(AI)正以前所未有的速度发展,而DeepSeek作为这一领域的先锋,正引领着AI技术的创新与突破。作为一家致力于推动人工智能技术创新与应用的前沿企业,DeepSeek不仅在多语言编…...

Spring Bean 容器
技术成长,是对场景设计细节不断的雕刻! 你觉得自己的技术什么时候得到了快速的提高,是CRUD写的多了以后吗?想都不要想,绝对不可能!CRUD写的再多也只是能满足你作为一个搬砖工具人,敲击少逻辑流…...

Flask代码审计实战
文章目录 Flask代码审计SQL注入命令/代码执行反序列化文件操作XXESSRFXSS其他 审计实战后记reference Flask代码审计 SQL注入 1、正确的使用直白一点就是:使用”逗号”,而不是”百分号” stmt "SELECT * FROM table WHERE id?" connectio…...
springboot启动配置文件-bootstrap.yml常用基本配置
在Spring Boot应用程序中,bootstrap.yml文件通常用于配置应用程序的启动阶段。在这个文件中,你可以配置一些在应用程序启动之前需要加载的属性,例如外部配置源、加密属性等。以下是一些常用的基本配置项: 1. 外部配置源 1.1 配置…...

2月3日星期一今日早报简报微语报早读
2月3日星期一,农历正月初六,早报#微语早读。 1、多个景区发布公告:售票数量已达上限,请游客合理安排行程; 2、2025春节档总票房破70亿,《哪吒之魔童闹海》破31亿; 3、美宣布对中国商品加征10…...

如何确认Linux嵌入式系统的触摸屏对应的是哪个设备文件(/dev/input/event1)?如何查看系统中所有的输入设备?输入设备的设备文件有什么特点?
Linux嵌入式系统的输入设备的设备文件有什么特点? 在 Linux 中,所有的输入设备(如键盘、鼠标、触摸屏等)都会被内核识别为 输入事件设备,并在 /dev/input/ 目录下创建相应的 设备文件,通常是: …...

FFmpeg:多媒体处理的瑞士军刀
FFmpeg:多媒体处理的瑞士军刀 前言 FFmpeg 是一个功能强大且跨平台的开源多媒体框架,广泛应用于音视频处理领域。 它由多个库和工具组成,能够处理各种音视频格式,涵盖编码、解码、转码、流处理等多种操作。 无论是专业视频编辑…...
电控三周速成计划参考
第1周:基础搭建与GPIO控制 学习目标:建立开发环境,掌握最基础的硬件控制能力 每日学习(2-3小时): 环境搭建(2天) 安装Keil MDK-ARM STM32CubeMX使用CubeMX创建第一个工程…...
Ubuntu修改配置文件--编辑操作
例如。 1.打开 /etc/samba/smb.conf 该配置文件: sudo vi /etc/samba/smb.conf 2.当你运行sudo vi /etc/samba/smb.conf命令后,你需要按i键进入插入模式(Insert Mode)。这时,在屏幕底部你应该能看到“-- INSERT --”…...
2021版小程序开发5——小程序项目开发实践(1)
2021版小程序开发5——小程序项目开发实践(1) 学习笔记 2025 使用uni-app开发一个电商项目; Hbuidler 首选uni-app官方推荐工具:https://www.dcloud.io/hbuilderx.htmlhttps://dev.dcloud.net.cn/pages/app/list 微信小程序 管理后台:htt…...
二分/双指针/单调栈队列专题
1.4924. 矩阵 - AcWing题库 一开始打表找规律以为是右上角向左下角递增,但当n很大的时候就不对了,因此我们得去观察 i * i 100000 * (i - j) j * j i * j 这个式子,我们关心的是这个式子的单调性因此我们可以分别将i和j看作常数来对式子进行求导,可以得到 f(i) 2 * i 10…...

XCCL、NCCL、HCCL通信库
XCCL提供的基本能力 XCCL提供的基本能力 不同的XCCL 针对不同的网络拓扑,实现的是不同的优化算法的(不同CCL库最大的区别就是这) 不同CCL库还会根据自己的硬件、系统,在底层上面对一些相对应的改动; 但是对上的API接口…...

XML Group端口详解
在XML数据映射过程中,经常需要对数据进行分组聚合操作。例如,当处理包含多个物料明细的XML文件时,可能需要将相同物料号的明细归为一组,或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码,增加了开…...

docker详细操作--未完待续
docker介绍 docker官网: Docker:加速容器应用程序开发 harbor官网:Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台,用于将应用程序及其依赖项(如库、运行时环…...

K8S认证|CKS题库+答案| 11. AppArmor
目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作: 1)、切换集群 2)、切换节点 3)、切换到 apparmor 的目录 4)、执行 apparmor 策略模块 5)、修改 pod 文件 6)、…...
基于数字孪生的水厂可视化平台建设:架构与实践
分享大纲: 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年,数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段,基于数字孪生的水厂可视化平台的…...

新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案
随着新能源汽车的快速普及,充电桩作为核心配套设施,其安全性与可靠性备受关注。然而,在高温、高负荷运行环境下,充电桩的散热问题与消防安全隐患日益凸显,成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容
目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法,当前调用一个医疗行业的AI识别算法后返回…...

有限自动机到正规文法转换器v1.0
1 项目简介 这是一个功能强大的有限自动机(Finite Automaton, FA)到正规文法(Regular Grammar)转换器,它配备了一个直观且完整的图形用户界面,使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...
大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计
随着大语言模型(LLM)参数规模的增长,推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长,而KV缓存的内存消耗可能高达数十GB(例如Llama2-7B处理100K token时需50GB内存&a…...

SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题
分区配置 (ptab.json) img 属性介绍: img 属性指定分区存放的 image 名称,指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件,则以 proj_name:binary_name 格式指定文件名, proj_name 为工程 名&…...

JVM 内存结构 详解
内存结构 运行时数据区: Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器: 线程私有,程序控制流的指示器,分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 每个线程都有一个程序计数…...