波奇学C++:用红黑树模拟实现map和set

用同一个树的类模板封装map(key/value)和set(key)

红黑树的Node

template<class T>
struct RBTreeNode
{RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;T _data;Colour _col;RBTreeNode(const T& data):_left(nullptr),_right(nullptr),_parent(nullptr),_data(data),_col(BLACK){}
};

用只有一个data变量来代替map的pair<key,value> 和set的key

template<class key,class T,class KeyOfT>
struct RBTree

看红黑树的模板的我们依然保留key模板,对于Set来说key和T都是value的,对于map来说key 是 key,T是pair<key,value>。

RBTree<K, pair<K, V>,MapKeyOfT> _t;
RBTree<K, K,SetKeyOfT> _t;

由此相当于适配器模式,对于set来说第二个模板参数不是必要的。

由此我们可以思考,我们对两个对象的封装可以先统一起来某种形式,比如都提供两个模板参数。

红黑树的insert返回值由原来的bool变成了pair<iterator,bool>

pair<iterator,bool> Insert(const T& data)
//......
return make_pair(iterator(newnode), true);
//

注意实际上map和set的迭代器属性不一样,但我们返回权限大的普通迭代器,后面再分别进行const限制来适配

typedef __TreeIterator<T,T*,T&> iterator;

写红黑树的迭代器

template<class T, class Ptr, class Ref>
struct __TreeIterator
{typedef RBTreeNode Node;typedef __TreeIterator< T, Ptr, Ref> Self;// Iterator只可能是普通迭代器typedef __TreeIterator< T, T*, T&> Iterator;Node* _node;__TreeIterator(const Iterator& It):_node(It._node){}__TreeIterator(Node* node):_node(node){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}Self& operator++(){//右边不为空if (_node->right){Node* leftmin = _node->_right;while (leftmin->_left){leftmin = leftmin->_left;}_node = leftmin;return *this;}else{// 右树为空Node* parent = _node->_parent;while (parent&&_node == parent->right){_node = parent;parent = _node->_parent;}_node = parent;return *this;}}bool operator!=(const Iterator it)const{return _node != it._node;}bool operator==(const Iterator)const{return _node == it._node;}Self& operator--(){//左不为空if (_node->_left){Node* rightmax = _node->_left;while (rightmax->_right){rightmax = rightmax->_right;}_node = rightmax;return *this;}else{Node* parent = _node->_parent;while (parent && parent->_right == _node){_node = parent;parent = _node->_parent;}_node = parent;return *this;}}};

比较重要的点是拷贝构造函数

__TreeIterator(const Iterator& It):_node(It._node){}

对于普通迭代器,是拷贝构造,同时它也可以接收普通迭代器来构造const 修饰的迭代器。

operate()++的分析

当右树存在时,再右子树的最大值,当右树不存在,找到parent节点向上处理,当cur是parentd1左节点时,parent就是下一个节点。

红黑树的begin(),end()方法 

typedef __TreeIterator<T,T*,T&> iterator;typedef __TreeIterator<T, const T*, const T&> const_iterator;iterator begin(){Node* leftMin = _root;while (leftMin && leftMin->_left){leftMin=leftMin->_left;}return iterator(leftMin);}iterator end(){return iterator(nullptr);}const_iterator begin()const{Node* leftMin = _root;while (leftMin && leftMin->_left){leftMin = leftMin->_left;}return const_iterator(leftMin);}const_iterator end()const{return const_iterator(nullptr);}

这里用了没有直接返回Node*指针而是返回迭代器对象,调用拷贝构造函数。

map和set的迭代器有不同的需求,对于set而言,iterator就是const_iterator。

typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;
typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;

set的begin() 

iterator begin()
{return _t.begin();
}

当begin()调用时 _t.begin()返回的是iterator这是就是可以通过__TreeIterator的拷贝构造实现转换成Iterator,(其实可以直接调用const的begin()修饰的函数)

insert封装

pair<iterator, bool> insert(const K& key){pair<typename RBTree<K, K, SetKeyOfT>::iterator, bool>ret = _t.Insert(key);return pair<iterator, bool>(ret.first, ret.second);}

注意此时的问题,insert规定返回值必须是pair<iterator, bool>,RBTree返回的值实际是iterator,myset返回的iterator实际是const_iterator。不能直接返回会导致权限的缩小,所以要再构造。

而map的迭代器要确保pair<key,value>的key不会改变。方法是给模板参数上const

typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/151866.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

kafka日志文件详解及生产常见问题总结

一、kafka的log日志梳理 日志文件是kafka根目录下的config/server.properties文件&#xff0c;配置log.dirs/usr/local/kafka/kafka-logs&#xff0c;kafka一部分数据包含当前Broker节点的消息数据(在Kafka中称为Log日志)&#xff0c;称为无状态数据&#xff0c;另外一部分存在…

选择适合建筑公司的企业网盘平台

随着城市化进程的加速&#xff0c;越来越多的人开始关注乡村生活品质。Z公司以其标准化产品和优质资源整合&#xff0c;为回乡建房人群提供了一种全新的、高品质的整体解决方案。 Z公司深入调研了10W的回乡建房人群需求&#xff0c;组建了设计、工艺、供应链方面的专家团队&…

【Gradle-10】不可忽视的构建分析

1、前言 构建性能对于生产力至关重要。 随着项目越来越复杂&#xff0c;花费在构建上的时间就越长&#xff0c;开发效率就越低。 通过分析构建过程&#xff0c;可以了解项目构建的时间都花在哪&#xff0c;以及项目存在哪些潜在的问题&#xff0c;找到构建瓶颈&#xff0c;解…

顺序表的简单介绍

目录 前提须知&#xff1a; 数据结构&#xff1a; 什么是数据结构&#xff1f; 数据结构特点&#xff1a; 为什么需要数据结构&#xff1a; 顺序表&#xff1a; 线性表&#xff1a; 与数组区别&#xff1a; 静态顺序表与动态顺序表&#xff1a; 二者之间的区别&#x…

高通camx开源部分简介

camera整体框架 ISP Pipeline diagram Simple Model Camx and chi_cdk 整体框架 CtsVerifier, Camra Formats Topology of Camera Formats. Topology (USECASE: UsecaseVideo) Nodes List Links between nodes Pipeline PreviewVideo Buffer manager Create Destro…

定制自己的 Excel 界面 + 保存 Excel

文章目录 Excel 的界面自定义快速访问工具栏自定义功能区折叠或显示功能区自定义 Excel 的界面保存 Excel Excel 的界面 快速访问工具栏也可以放在功能区下方&#xff1a; 效果&#xff1a; 自定义快速访问工具栏 方法一&#xff1a; S1&#xff1a; S2&#xff1a; 方法二…

(c语言)经典bug

#include<stdio.h> //经典bug int main() { int i 0; int arr[10] {1,2,3,4,5,6,7,8,9,10}; for (i 0; i < 12; i) //越界访问 { arr[i] 0; printf("hehe\n"); } return 0; } 注&#xff1a;输出结果为死循…

geecg-uniapp 源码下载运行 修改端口号 修改tabBar 修改展示数据

APP体验&#xff1a; http://jeecg.com/appIndex技术官网&#xff1a; http://www.jeecg.com安装文档&#xff1a; 快速开始 JeecgBoot 开发文档 看云视频教程&#xff1a; 零基础入门视频官方支持&#xff1a; http://jeecg.com/doc/help 一&#xff0c;下载安装 源码下载…

信创之国产浪潮电脑+统信UOS操作系统体验3:使用 visual studio code搭建Python开发环境

☞ ░ 前往老猿Python博客 ░ https://blog.csdn.net/LaoYuanPython 一、引言 老猿原来在windows下开发python程序&#xff0c;要么使用python自带的IDLE&#xff0c;要么使用pycharm&#xff0c;IDLE用来开发很不方便&#xff0c;而pycharm对开发支持比较好&#xff0c;换成…

Angular学习笔记:路由

本文是自己的学习笔记&#xff0c;主要参考资料如下。 - B站《Angular全套实战教程》&#xff0c;达内官方账号制作&#xff0c;https://www.bilibili.com/video/BV1i741157Fj?https://www.bilibili.com/video/BV1R54y1J75g/?p32&vd_sourceab2511a81f5c634b6416d4cc1067…

【Java】微服务——Nacos配置管理(统一配置管理热更新配置共享Nacos集群搭建)

目录 1.统一配置管理1.1.在nacos中添加配置文件1.2.从微服务拉取配置1.3总结 2.配置热更新2.1.方式一2.2.方式二2.3总结 3.配置共享1&#xff09;添加一个环境共享配置2&#xff09;在user-service中读取共享配置3&#xff09;运行两个UserApplication&#xff0c;使用不同的pr…

大数据概述(林子雨慕课课程)

文章目录 1. 大数据概述1.1 大数据概念和影响1.2 大数据的应用1.3 大数据的关键技术1.4 大数据与云计算和物联网的关系云计算物联网 1. 大数据概述 大数据的四大特点&#xff1a;大量化、快速化、多样化、价值密度低 1.1 大数据概念和影响 大数据摩尔定律 大数据由结构化和非…

Observability:使用 OpenTelemetry 对 Node.js 应用程序进行自动检测

作者&#xff1a;Bahubali Shetti DevOps 和 SRE 团队正在改变软件开发的流程。 DevOps 工程师专注于高效的软件应用程序和服务交付&#xff0c;而 SRE 团队是确保可靠性、可扩展性和性能的关键。 这些团队必须依赖全栈可观察性解决方案&#xff0c;使他们能够管理和监控系统&a…

【面试经典150 | 矩阵】旋转图像

文章目录 写在前面Tag题目来源题目解读解题思路方法一&#xff1a;原地旋转方法二&#xff1a;翻转代替旋转 写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法&#xff0c;两到三天更新一篇文章&#xff0c;欢迎催更…… 专栏内容以分析题目为主&#xff0c;并附带…

Flask实现注册登录模块

&#x1f64c;秋名山码民的主页 &#x1f602;oi退役选手&#xff0c;Java、大数据、单片机、IoT均有所涉猎&#xff0c;热爱技术&#xff0c;技术无罪 &#x1f389;欢迎关注&#x1f50e;点赞&#x1f44d;收藏⭐️留言&#x1f4dd; 获取源码&#xff0c;添加WX 目录 前言1.…

几道web题目

总结几道国庆写的web题目 [ACTF2020 新生赛]Include1 点进去发现就一个flag.php,源代码和抓包都没拿到好东西 结合题目猜是文件包含&#xff0c;构建payload ?filephp://filter/readconvert.base64-encode/resourceflag.php 得到base64编码过的flag&#xff0c;解码即可 此题…

Android---Class 对象在执行引擎中的初始化过程

一个 class 文件被加载到内存中的步骤如下图所示&#xff1a; 装载 装载是指 Java 虚拟机查找 .class 文件并生成字节流&#xff0c;然后根据字节流创建 java.lang.Class 对象的过程。 1. ClassLoader 通过一个类的全限定名&#xff08;包名类名&#xff09;来查找 .class 文件…

Linux多线程

文章目录 多线程多线程概念多线程优点多线程缺点线程和进程 Linux线程控制POSIX线程库线程的创建进程ID获取线程终止线程等待线程分离 总结 多线程 多线程概念 在Linux中&#xff0c;线程是进程内的执行单元。换句话说&#xff0c;线程是进程内部的子任务&#xff0c;它们共享…

入侵防御系统(IPS)网络安全设备介绍

入侵防御系统&#xff08;IPS&#xff09;网络安全设备介绍 1. IPS设备基础 IPS定义 IPS&#xff08;Intrusion Prevention System&#xff09;是一种网络安全设备或系统&#xff0c;用于监视、检测和阻止网络上的入侵尝试和恶意活动。它是网络安全架构中的重要组成部分&…