【C++】map和set的封装(红黑树)
map和set的封装
- 一、介绍
- 二、stl源码剖析
- 三、仿函数获取数值
- 四、红黑树的迭代器
- 五、map的[]
- 5.1 普通迭代器转const迭代器
- 六、set源码
- 七、map源码
- 八、红黑树源码
一、介绍
首先要知道map和set的底层都是用红黑树实现的
【数据结构】红黑树
set只需要一个key,但是map既有key也有val。
那么我们怎么同时兼容呢?
二、stl源码剖析
从这张图可以看出红黑树的节点里面存的类型是由Value决定的,跟Key无关。
所以我们实现的时候就可以给RBTree添加一个模板参数
template<class K, class T>
class RBTree
T模板参数我们既可以传K
也可以传pair<k, V>
map
:
template <class K>
class set
{
private:RBTree<K,K> _t;
};
set
:
template <class K, class V>
class map
{
private:RBTree<K, pair<const K,V>> _t;
};
既然通过第二个参数就能确定节点的类型,那么第一个参数有什么用呢?
当我们查找的时候,如果是map,第二个参数就是pair类型,不能使用,所以得加上第一个参数,方便查找。
参照stl的方法定义节点:
template <class T>
struct RBTreeNode
{RBTreeNode(const T& data): _data(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED){}T _data;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;Colour _col;
};
三、仿函数获取数值
我们知道红黑树是搜索树,插入的时候需要比较大小,而我们插入的有可能是K
,也有可能是pair<K, V>
,导致我们无法直接比较。
而stl的做法就是利用仿函数获取我们需要进行比较的元素。
set
:
template <class K>
class set
{struct SetKeyOfT{const K& operator()(const K& k){return k;}};
public:
private:RBTree<K, K, SetKeyOfT> _t;
};
map
:
template <class K, class V>
class map
{struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};
public:
private:RBTree<K, pair<K, V, >, MapKeyOfT> _t;
};
进行大小比较
KeyOfT kot;// 仿函数比较
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{if (kot(cur->_data) < kot(data)){parent = cur;cur = cur->_left;}else if (kot(cur->_data) > kot(data)){parent = cur;cur = cur->_right;}else return false;
}
四、红黑树的迭代器
template <class T, class Ref, class Ptr>
struct RBTIterator
{typedef RBTreeNode<T> Node;typedef RBTIterator<T, Ref, Ptr> self;RBTIterator(Node* node): _node(node){}Node* _node;
};
*
:解引用操作,返回对应结点数据的引用:
Ref operator*()
{return _node->_data;
}
->
:访问成员操作符,返回节点数据的地址
Ptr operator->()
{return &_node->_data;
}
!=、==
比较迭代器是否指向同一节点
bool operator!=(const self& it)
{return _node != it._node;
}bool operator==(const self& it)
{return _node == it._node;
}
begin()
和 end()
begin()
:返回的是最左节点(中序遍历的第一个节点)
end()
:迭代器的end()一般是返回最后一个节点的下一个位置,这里设置为nullptr。
typedef RBTIterator<T, T&, T*> iterator;
typedef RBTIterator<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);
}
map里面的begin()
与end()
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT >::iterator iterator;
iterator begin()
{return _t.begin();
}iterator end()
{return _t.end();
}
这里注意因为编译的时候编译器不知道RBTree<K, pair<const K, V>, MapKeyOfT >::iterator
这是个类型还是静态成员变量,会编译出错,加上typename就是告诉编译器这里是一个类型。
set的begin()
和end()
typedef typename RBTree<K, K, SetKeyOfT >::iterator iterator;
iterator begin()
{return _t.begin();
}iterator end()
{return _t.end();
}
这里重要的是迭代器的++
和--
++
:
寻找中序遍历的下一个节点:
1️⃣ 如果右子树不为空,++
就是找右子树的最左节点。
1️⃣ 如果右子树为空,++
就是找祖先(孩子是父亲的左的那个祖先)
self& operator++()
{if (_node->_right){Node* min = _node->_right;while (min->_left){min = min->_left;}_node = min;}else{Node* cur = _node;Node* parent = cur->_parent;while (parent && parent->_right == cur){cur = parent;parent = parent->_parent;}_node = parent;}return *this;
}
--
:
跟++
刚好是反过来:
1️⃣ 如果左子树不为空,++
就是找左子树的最右节点。
1️⃣ 如果左子树为空,++
就是找祖先(孩子是父亲的右的那个祖先)
self& operator--()
{if (_node->_left){Node* max = _node->_left;while (max && max->_right){max = max->_right;}_node = max;}else{Node* cur = _node;Node* parent = cur->_parent;while (parent && parent->_left == cur){cur = parent;parent = parent->_parent;}_node = parent;}return *this;
}
这里还有一个重要的问题:
如果这么写那么set的值也可以被修改。那么如何保证set不能被修改呢?
可以直接把普通迭代器和const迭代器都变成const_iterator。
此时这里会出现问题:
iterator begin()
{return _t.begin();
}iterator end()
{return _t.end();
}
这里_t是普通对象,会调用普通的迭代器,类型不同,无法返回。
我们只需要在函数后面加上const就可以权限缩小,变成const对象。
iterator begin() const
{return _t.begin();
}iterator end() const
{return _t.end();
}
在红黑树中也要加入对应的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);
}
五、map的[]
当我们想使用map来统计次数的时候,就需要重载[]
。
如果想要支持[],那么insert的返回值就得设置成pair<iterator, bool>
。
如果在bool就是false,iterator返回当前节点。
return make_pair(iterator(cur), false);
不在就插入。
return make_pair(iterator(newnode), true);
map
:
V& operator[](const K& key)
{pair<iterator, bool> ret = insert(make_pair(key, V()));return ret.first->second;
}
这里要注意set:
pair<iterator, bool> insert(const K& k)
{return _t.insert(k);
}
这里的iterator其实是const_iterator,所以导致类型不同。
5.1 普通迭代器转const迭代器
正常情况下普通迭代器不能转化为const迭代器。
为了解决这种情况,我们在迭代器内添加一个拷贝构造即可。
1️⃣ 当传进来的是普通迭代器的时候,iterator是普通迭代器,这个函数相当于拷贝构造
2️⃣ 当传进来的是const迭代器的时候,iterator依然是普通迭代器,此时该函数就相当于构造函数(普通迭代构造const迭代器)。
其实普通迭代器和const的区别就在operator*
和operator->
而set的插入不需要修改:
pair<iterator, bool> insert(const K& k)
{return _t.insert(k);
}
return的时候会调用拷贝构造函数,也就是构造函数,把普通迭代器转化为const迭代器。
六、set源码
#pragma once
#include "RBTree.h"namespace yyh
{template <class K>class set{struct SetKeyOfT{const K& operator()(const K& k){return k;}};public:typedef typename RBTree<K, K, SetKeyOfT >::const_iterator iterator;typedef typename RBTree<K, K, SetKeyOfT >::const_iterator const_iterator;iterator begin() const{return _t.begin();}iterator end() const{return _t.end();}pair<iterator, bool> insert(const K& k){return _t.insert(k);}private:RBTree<K, K, SetKeyOfT> _t;};
}
七、map源码
#pragma once
#include "RBTree.h"namespace yyh
{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 >::const_iterator \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();}pair<iterator, bool> insert(const const pair<K, V>& kv){return _t.insert(kv);}V& operator[](const K& key){pair<iterator, bool> ret = insert(make_pair(key, V()));return ret.first->second;}private:RBTree<K, pair<const K, V>, MapKeyOfT> _t;};
}
八、红黑树源码
#pragma once
#include <iostream>
#include <cstdlib>
#include <cassert>
#include <string>using namespace std;enum Colour
{RED,BLACK,
};template <class T>
struct RBTreeNode
{RBTreeNode(const T& data): _data(data), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED){}T _data;RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;Colour _col;
};template <class T, class Ref, class Ptr>
struct RBTIterator
{typedef RBTreeNode<T> Node;typedef RBTIterator<T, Ref, Ptr> self;typedef RBTIterator<T, T&, T*> iterator;RBTIterator(const iterator& s): _node(s._node){}RBTIterator(Node* node): _node(node){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!=(const self& it){return _node != it._node;}bool operator==(const self& it){return _node == it._node;}self& operator++(){if (_node->_right){Node* min = _node->_right;while (min->_left){min = min->_left;}_node = min;}else{Node* cur = _node;Node* parent = cur->_parent;while (parent && parent->_right == cur){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}self& operator--(){if (_node->_left){Node* max = _node->_left;while (max && max->_right){max = max->_right;}_node = max;}else{Node* cur = _node;Node* parent = cur->_parent;while (parent && parent->_left == cur){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}Node* _node;
};template <class K, class T, class KeyOfT>
class RBTree
{
public:typedef RBTreeNode<T> Node;typedef RBTIterator<T, T&, T*> iterator;typedef RBTIterator<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_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(cur->_data) > kot(data)){parent = cur;cur = cur->_left;}else if (kot(cur->_data) < kot(data)){parent = cur;cur = cur->_right;}else return make_pair(iterator(cur), false);}cur = new Node(data);Node* newnode = cur;if (kot(data) < kot(parent->_data)){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;while (parent && parent->_col == RED){// 找g 与 uNode* g = parent->_parent;if (parent == g->_left){Node* u = g->_right;// 情况一 u存在且为红if (u && u->_col == RED){parent->_col = u->_col = BLACK;g->_col = RED;// 继续往上处理cur = g;parent = cur->_parent;}else // 情况二或情况三{if (cur == parent->_left)// 情况二{// g// p// cRotateR(g);parent->_col = BLACK;g->_col = RED;}else// 情况三{// g// p// cRotateL(parent);RotateR(g);// c// p gcur->_col = BLACK;g->_col = RED;}break;}}else{Node* u = g->_left;// 情况一if (u && u->_col == RED){u->_col = parent->_col = BLACK;g->_col = RED;cur = g;parent = cur->_parent;}else{// 情况二// g// p// cif (cur == parent->_right){RotateL(g);parent->_col = BLACK;g->_col = RED;}else// 情况三{// g// p// cRotateR(parent);RotateL(g);cur->_col = BLACK;g->_col = RED;}break;}}}// 上面有可能把_root的颜色变为红_root->_col = BLACK;return make_pair(iterator(newnode), true);}void RotateL(Node* parent){Node* top = parent->_parent;Node* right = parent->_right;parent->_right = right->_left;if (right->_left) right->_left->_parent = parent;right->_left = parent;parent->_parent = right;if (top)// 子树{if (parent == top->_left) top->_left = right;else top->_right = right;right->_parent = top;}else// 完整的树{_root = right;_root->_parent = nullptr;}}void RotateR(Node* parent){Node* top = parent->_parent;Node* left = parent->_left;Node* leftR = left->_right;parent->_left = leftR;if (leftR) leftR->_parent = parent;left->_right = parent;parent->_parent = left;if (top){if (parent == top->_left) top->_left = left;else top->_right = left;left->_parent = top;}else{_root = left;_root->_parent = nullptr;}}void _Inorder(Node* root){if (root == nullptr)return;_Inorder(root->_left);cout << root->_kv.first << "<=>" << root->_kv.second << endl;_Inorder(root->_right);}void Inorder(){_Inorder(_root);}bool _IsBalance(Node* root, int i, int flag){if (root == nullptr){if (i != flag){cout << "errno: 左右子树黑色节点数目不同" << endl;return false;}return true;}// 红节点时判断父亲if (root->_col == RED){if (root->_parent->_col == RED){cout << "errno: 红-红" << endl;return false;}}if (root->_col == BLACK){i++;}return _IsBalance(root->_left, i, flag) && _IsBalance(root->_right, i, flag);}bool IsBalance(){if (_root == nullptr){return true;}if (_root->_col != BLACK){return false;}// 找标准值Node* cur = _root;int flag = 0;while (cur){if (cur->_col == BLACK){flag++;}cur = cur->_left;}int i = 0;return _IsBalance(_root, i, flag);}private:Node* _root = nullptr;
};
相关文章:

【C++】map和set的封装(红黑树)
map和set的封装一、介绍二、stl源码剖析三、仿函数获取数值四、红黑树的迭代器五、map的[]5.1 普通迭代器转const迭代器六、set源码七、map源码八、红黑树源码一、介绍 首先要知道map和set的底层都是用红黑树实现的 【数据结构】红黑树 set只需要一个key,但是map既…...
【批处理脚本】-1.14-移动文件(夹)命令move
"><--点击返回「批处理BAT从入门到精通」总目录--> 共10页精讲(列举了所有move的用法,图文并茂,通俗易懂) 在从事“嵌入式软件开发”和“Autosar工具开发软件”过程中,经常会在其集成开发环境IDE(CodeWarrior,S32K DS,Davinci,EB Tresos,ETAS…)中,…...

逻辑地址和物理地址转换
在操作系统的学习中,很多抵挡都会涉及虚拟地址转换为物理地址的计算,本篇就简单介绍一下在分页存储管理、分段存储管理、磁盘存储管理中涉及的地址转换问题。 虚拟地址与物理地址 编程一般只有可能和逻辑地址打交道,比如在 C 语言中&#x…...

HyperGBM用4记组合拳提升AutoML模型泛化能力
本文作者:杨健,九章云极 DataCanvas 主任架构师 如何有效提高模型的泛化能力,始终是机器学习领域的重要课题。经过大量的实践证明比较有效的方式包括: 利用Early Stopping防止过拟合通过正则化降低模型的复杂度使用更多的训练数…...

P6软件中的前锋线设置
卷首语 所谓前锋线,是指从评估时刻的时标点出发,用点划线一次连接各项活动的实际进展位置所形成的的线段,其通常为折线。 关键路径法 前锋线比较法,是通过在进度计划中绘制实际进度前锋线以判断活动实际进度与计划进度的偏差&a…...

Spring Boot + Vue3 前后端分离 实战 wiki 知识库系统<二>---后端架构完善与接口开发
数据库准备: 在上一次Spring Boot Vue3 前后端分离 实战 wiki 知识库系统<一>---Spring Boot项目搭建已经将SpringBoot相关的配置环境给搭建好了,接下来则需要为咱们的项目创建一个数据库。 1、mysql的安装: 关于mysql的安装这里就…...

如何在logback.xml中自定义动态属性
原文地址:http://blog.jboost.cn/trick-logback-prop.html 当使用logback来记录Web应用的日志时,我们通过在logback.xml中配置appender来指定日志输出格式及输出文件路径,这在一台主机或一个文件系统上部署单个实例没有问题,但是…...

嵌入式系统硬件设计与实践(第一步下载eda软件)
【 声明:版权所有,欢迎转载,请勿用于商业用途。 联系信箱:feixiaoxing 163.com】 现实生活中,我们经常发现有的人定了很多的目标,但是到最后一个都没有实现。这听上去有点奇怪,但确实是实实在在…...

Portraiture4免费磨皮插件支持PS/LR
Portraiture 4免去了繁琐的手工劳动,选择性的屏蔽和由像素的平滑,以帮助您实现卓越的肖像润色。智能平滑,并删除不完善之处,同时保持皮肤的纹理和其他重要肖像的细节,如头发,眉毛,睫毛等。 一键…...

Python学习笔记202302
1、numpy.empty 作用:根据给定的维度和数值类型返回一个新的数组,其元素不进行初始化。 用法:numpy.empty(shape, dtypefloat, order‘C’) 2、logging.debug 作用:Python 的日志记录工具,这个模块为应用与库实现了灵…...
2023年大数据面试开胃菜
1、kafka的message包括哪些信息一个Kafka的Message由一个固定长度的header和一个变长的消息体body组成,header部分由一个字节的magic(文件格式)和四个字节的CRC32(用于判断body消息体是否正常)构成。当magic的值为1的时候,会在magic和crc32之间多一个字节…...
优雅的controller层设计
controller层设计 Controller 层逻辑 MVC架构下,我们的web工程结构会分为三层,自下而上是dao层,service层和controller层。controller层为控制层,主要处理外部请求。调用service层,一般情况下,contro…...
同步、通信、死锁
基础概念竞争资源引起两个问题死锁:因资源竞争陷入永远等待的状态饥饿:一个可运行程序由于其他进程总是优先于它,而被调用程序总是无限期地拖延而不能执行进程互斥:若干进程因相互争夺独占型资源而产生的竞争关系进程同步…...

【聚类】谱聚类解读、代码示例
【聚类】谱聚类详解、代码示例 文章目录【聚类】谱聚类详解、代码示例1. 介绍2. 方法解读2.1 先验知识2.1.1 无向权重图2.1.2 拉普拉斯矩阵2.2 构建图(第一步)2.2.1 ϵ\epsilonϵ 邻近法2.2.2 k 近邻法2.2.3 全连接法2.3 切图(第二步…...
最牛逼的垃圾回收期ZGC(1),简介
1丶什么是ZGC? ZGC是JDK 11中引入的一种可扩展的、低延迟的垃圾收集器。ZGC最主要的特点是:在非常短的时间内(一般不到10ms),就可以完成一次垃圾回收,而且这个时间是与堆的大小无关的。另外,ZGC支持非常大…...

微服务的Feign到底是什么
Feign是什么 分区是一种数据库优化技术,它可以将大表按照一定的规则分成多个小表,从而提高查询和维护的效率。在分区的过程中,数据库会将数据按照分区规则分配到不同的分区中,并且可以在分区中使用索引和其他优化技术来提高查询效…...

JavaScript 正则表达式
正则表达式(英语:Regular Expression,在代码中常简写为regex、regexp或RE)使用单个字符串来描述、匹配一系列符合某个句法规则的字符串搜索模式。搜索模式可用于文本搜索和文本替换。什么是正则表达式?正则表达式是由一…...
【批处理脚本】-1.15-文件内字符串查找命令find
"><--点击返回「批处理BAT从入门到精通」总目录--> 共7页精讲(列举了所有find的用法,图文并茂,通俗易懂) 在从事“嵌入式软件开发”和“Autosar工具开发软件”过程中,经常会在其集成开发环境IDE(CodeWarrior,S32K DS,Davinci,EB Tresos,ETAS…)中,…...

【手撕面试题】JavaScript(高频知识点二)
目录 面试官:请你谈谈JS的this指向问题 面试官:说一说call apply bind的作用和区别? 面试官:请你谈谈对事件委托的理解 面试官:说一说promise是什么与使用方法? 面试官:说一说跨域是什么&a…...
Web学习1_HTML
在学校期间学的Web知识忘了一些,很多东西摸棱两可,现重新系统的学习一下。 首先下载安装完vsc后并下载拓展文件live server(模拟一个服务器) Auto Rename Tag(在写网页时,自动对齐前后标签)在设…...
在软件开发中正确使用MySQL日期时间类型的深度解析
在日常软件开发场景中,时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志,到供应链系统的物流节点时间戳,时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库,其日期时间类型的…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】
微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来,Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...
生成 Git SSH 证书
🔑 1. 生成 SSH 密钥对 在终端(Windows 使用 Git Bash,Mac/Linux 使用 Terminal)执行命令: ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" 参数说明: -t rsa&#x…...

高危文件识别的常用算法:原理、应用与企业场景
高危文件识别的常用算法:原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件,如包含恶意代码、敏感数据或欺诈内容的文档,在企业协同办公环境中(如Teams、Google Workspace)尤为重要。结合大模型技术&…...
JS设计模式(4):观察者模式
JS设计模式(4):观察者模式 一、引入 在开发中,我们经常会遇到这样的场景:一个对象的状态变化需要自动通知其他对象,比如: 电商平台中,商品库存变化时需要通知所有订阅该商品的用户;新闻网站中࿰…...
C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)
名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...

保姆级【快数学会Android端“动画“】+ 实现补间动画和逐帧动画!!!
目录 补间动画 1.创建资源文件夹 2.设置文件夹类型 3.创建.xml文件 4.样式设计 5.动画设置 6.动画的实现 内容拓展 7.在原基础上继续添加.xml文件 8.xml代码编写 (1)rotate_anim (2)scale_anim (3)translate_anim 9.MainActivity.java代码汇总 10.效果展示 逐帧…...

pgsql:还原数据库后出现重复序列导致“more than one owned sequence found“报错问题的解决
问题: pgsql数据库通过备份数据库文件进行还原时,如果表中有自增序列,还原后可能会出现重复的序列,此时若向表中插入新行时会出现“more than one owned sequence found”的报错提示。 点击菜单“其它”-》“序列”,…...
CppCon 2015 学习:Reactive Stream Processing in Industrial IoT using DDS and Rx
“Reactive Stream Processing in Industrial IoT using DDS and Rx” 是指在工业物联网(IIoT)场景中,结合 DDS(Data Distribution Service) 和 Rx(Reactive Extensions) 技术,实现 …...

HTML版英语学习系统
HTML版英语学习系统 这是一个完全免费、无需安装、功能完整的英语学习工具,使用HTML CSS JavaScript实现。 功能 文本朗读练习 - 输入英文文章,系统朗读帮助练习听力和发音,适合跟读练习,模仿学习;实时词典查询 - 双…...