C++ 使用红黑树的实现及迭代器完成对set和map的封装
一、红黑树的实现以及迭代器
#pragma once
// 要实现完整的迭代器需要对红黑树进行改造,有兴趣可参考侯捷《STL源码剖析》
enum Colour
{RED,BLACK
};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(RED){}
};template<class T, class Ref, class Ptr>
struct RBTreeIterator
{typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, Ref, Ptr> Self;Node* _node;RBTreeIterator(Node* node):_node(node){}// 迭代器的++操作,让迭代器可以移动// 左根右,当右没有访问完,就要继续访问Self& operator++(){if (_node->_right){// 下一个就是右子树的最左节点Node* cur = _node->_right;while (cur->_left){cur = cur->_left;}_node = cur;}else{// 左子树 根 右子树// 右为空,找孩子是父亲左的那个祖先Node* cur = _node;Node* parent = _node->_parent;while (parent && cur == parent->_right){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}self& operator--(){//如果左子树存在if (_node->left){//找左子树的最右节点Node* right = _node->_left;while (right->_right){right = right->_right;}_node = rihgt;}//如果左子树不存在else{//找孩子不是父亲左节点的节点Node* parent = _node->parent;Node* cur = _node;while (parent->_left == cur){cur = cur->_parent;parent = parent->_parent;if (parent == nullptr){break;}}_node = parent;}return *this;}// 下面两个操作,让迭代器可以像指针一样操作T& operator*(){return _node->_data;}T* operator->(){return &_node->_data;}// 下面两个操作,让迭代器能够支持比较bool operator!=(const Self& s)const{return _node != s._node;}bool operator==(const Self& s)const{return _node == s._node;}
};template<class K, class T, class KeyOfT>
class RBTree
{typedef RBTreeNode<T> Node;
public:typedef RBTreeIterator<T, T&, T*> Iterator;typedef RBTreeIterator<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->_left)cur = cur->_left;return const_Iterator(cur);}const_Iterator End() const{return const_Iterator(nullptr);}~RBTree(){Destroy(_root);_root = nullptr;}pair<Node*, bool> Insert(const T& data){if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return make_pair(_root,true);}KeyOfT kot;Node* parent = nullptr;Node* cur = _root;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 make_pair(cur, false);}}cur = new Node(data);Node* newnode = cur;// 新增节点。颜色红色给红色cur->_col = RED;if (kot(parent->_data) < kot(data)){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;while (parent && parent->_col == RED){Node* grandfather = parent->_parent;// g// p uif (parent == grandfather->_left){Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED){// u存在且为红 -》变色再继续往上处理parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{// u存在且为黑或不存在 -》旋转+变色if (cur == parent->_left){// g// p u//c//单旋RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{// g// p u// c//双旋RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else{// g// u pNode* uncle = grandfather->_left;// 叔叔存在且为红,-》变色即可if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续往上处理cur = grandfather;parent = cur->_parent;}else // 叔叔不存在,或者存在且为黑{// 情况二:叔叔不存在或者存在且为黑// 旋转+变色// g// u p// cif (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{// g// u p// cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return make_pair(newnode, true);}bool empty()const{if (_root == nullptr)return true;return false;}Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_kv.first < key){cur = cur->_right;}else if (cur->_kv.first > key){cur = cur->_left;}else{return cur;}}return nullptr;}size_t Size() const{return _Size(_root);}private:size_t _Size(Node* root) const{if (root == nullptr)return 0;return _Size(root->_left)+ _Size(root->_right) + 1;}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;Node* parentParent = 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;}}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* parentParent = 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 Destroy(Node* root){if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;}private:Node* _root = nullptr;
};
二、set
#pragma once
#include"RBTree_iterator.h"namespace XY
{template<class K>class set{typedef K ValueType;struct KeyOfValue{const K& operator()(const ValueType& data){return data;}};public:// 这里加typename的原因是告诉编译器这是模板不是类型// 还没实例化typedef typename RBTree<ValueType, ValueType,KeyOfValue>::const_Iterator iterator;typedef typename RBTree<ValueType, ValueType,KeyOfValue>::const_Iterator const_iterator;iterator begin() const{return t.Begin();}iterator end() const{return t.End();}bool empty()const{return t.empty();}size_t size()const{return t.Size();}pair<iterator, bool> insert(const ValueType& data){return t.Insert(data);}void clear(){t.Destroy();}iterator find(const K& key){t.Find(key);}private:RBTree<ValueType, ValueType, KeyOfValue> t;};
}
三、map
#pragma once#include"RBTree_iterator.h"namespace XY
{template<class K, class V>class map{typedef pair<K, V> ValueType;struct KeyOfValue{const K& operator()(const ValueType& data){return data.first;}};public:// 这里加typename的原因是告诉编译器这是模板不是类型// 还没实例化typedef typename RBTree<ValueType, pair<const K, V>, KeyOfValue>::Iterator iterator;typedef typename RBTree<ValueType, pair<const K, V>, KeyOfValue>::const_Iterator const_iterator;iterator begin(){return t.Begin();}iterator end(){return t.End();}const_iterator cbegin() const{return t.Begin();}const_iterator cend() const{return t.End();}bool empty()const{return t.empty();}size_t size()const{return t.Size();}V& operator[](const K& key){pair<iterator, bool> ret = insert(make_pair(key, V()));return ret.first->second;}pair<iterator, bool> insert(const ValueType& data){return t.Insert(data);}void clear(){t.Destroy();}iterator find(const K& key){t.Find(key);}private:RBTree<ValueType, pair<const K, V>, KeyOfValue> t;};
}相关文章:
C++ 使用红黑树的实现及迭代器完成对set和map的封装
一、红黑树的实现以及迭代器 #pragma once // 要实现完整的迭代器需要对红黑树进行改造,有兴趣可参考侯捷《STL源码剖析》 enum Colour {RED,BLACK };template<class T> struct RBTreeNode {RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeN…...
【Java从入门到起飞】面向对象编程(高级)
文章目录 1. 抽象类1.1 概述1.1.1 抽象类引入 1.2 abstract使用格式1.2.1 抽象方法1.2.2 抽象类1.2.3 抽象类的使用 1.3 抽象类的特征1.4 抽象类的细节1.5 抽象类存在的意义 2. 接口2.1 概述2.2 定义格式2.3 接口成分的特点2.3.1.抽象方法2.3.2 常量2.3.3 案例演示 2.4 基本的实…...
内网安全-横向移动PTH 哈希PTT 票据PTK 密匙Kerberos密码喷射
一.域横向pth,mimkatz,NTLM windwos server 2012 R2之前可能是NTLM和LM,之后为NTLM 1.mimkatz ptk 使用mimkatz进行横向移动 mimikatz sekurlsa::pth /user:administrator(目标本地用户名) /domain:192.168.3.32&a…...
【VMware安装Ubuntu实战分享】
在当今数字化时代,虚拟机技术已成为许多开发者、系统管理员以及技术爱好者的得力助手。VMware作为一款功能强大且广泛应用的虚拟化软件,为我们提供了便捷的环境来运行各种操作系统,而Ubuntu凭借其开源、稳定和易用性,深受广大用户…...
【推荐项目】 043-停车管理系统
043-停车管理系统 介绍 使用 springboot vuejs mysql 技术搭建框架。 智能停车管理系统描述 后端框架:采用Spring Boot与MySQL的强强联合,为系统提供稳健、高效的服务支撑。 前端框架:前端选用Vue.js,打造流畅、美观的用户交…...
【深入解析 epoll 的底层实现原理】
IO多路复用的简介select的工作原理和缺点epoll的引入和底层实现(数据结构、系统调用)epoll的优势和改进epoll的工作模式(LT和ET)在Java中的应用或相关API 需要确保每个部分逻辑清晰,逐步深入,帮助用户建立…...
Ubuntu 22.04 官方下载安装 Gradle 记录
Ubuntu 22.04 官方下载安装 Gradle 记录 Gradle 是一个强大的自动化构建工具,广泛用于 Java、Android 等项目的构建中。下面详细介绍如何在 Ubuntu 22.04 中使用官网下载安装 Gradle。 一、准备工作 首先,确保你的系统已安装 Java JDK(推荐…...
HTTPS加密原理详解
目录 HTTPS是什么 加密是什么 HTTPS的工作流程 1.使用对称加密 2.引入非对称加密 3.引入证书机制 客户端验证证书真伪的过程 签名的加密流程 整体工作流程 总结 HTTPS是什么 HTTPS协议也是一个应用程协议,是在HTTP的基础上加入了一个加密层,由…...
无公网IP也能远程控制Windows:Linux rdesktop内网穿透实战
文章目录 前言1. Windows 开启远程桌面2. Linux安装rdesktop工具3. Win安装Cpolar工具4. 配置远程桌面地址5. 远程桌面连接测试6. 设置固定远程地址7. 固定地址连接测试 前言 如今远程办公已经从一种选择变成了许多企业和个人的必修课,而如何在Linux系统上高效地访…...
Unity入门学习笔记(Day01)
一.认识unity工作面板 1.1.project window(项目面板) 显示当前项目中的所有文件和目录,包含了项目里面所有的资源文件 1.2.console window(输出面板) 显示当前游戏开发中生成的警告错误 1.3.hierarchy window&…...
HTML中的块元素与行内元素
1.块级标签 块级元素会独占一行,通常用于构建页面的结构。常见的块级元素包括: <div>:通用的块级容器。没有任何语意。可以创建网页的不同部分,导航栏侧边栏等。 <body><div class"nav"><a hre…...
postgreSQL window function高级用法
正常使用:相当于对每个row做一次子查询 SELECT depname, empno, salary, avg(salary) OVER (PARTITION BY depname) FROM empsalary;order by 区别window frame and partition 没有order by, window function是对整个partition起作用, part…...
当中国“智算心跳”与全球共振:九章云极DataCanvas首秀MWC 2025
3月3日,西班牙巴塞罗那,全球通信与科技领域的盛会“2025世界移动通信大会(MWC 2025)”正式拉开帷幕。中国人工智能基础设施领军企业九章云极DataCanvas公司以全球化战略视野与硬核技术实力,全方位、多维度地展示了在智…...
机器视觉检测显卡与工控机选型指南
在机器视觉检测项目中,深度学习显卡和工控机的选择直接影响算法性能、系统稳定性和长期维护成本。以下是关键注意事项及建议: 一、深度学习显卡选择 核心需求分析 任务类型:检测任务复杂度(如YOLO、ResNet等模型的参数量)决定显存需求。 高分辨率图像(如4K以上)需大显存…...
配置安全网站
配置网站 确定是Debian系统 更新索引:apt update 安装包:apt upgrade -y 查看nginx状态:systemctl status nginx 安装:nginx:apt install nginx 启动:systemctl start nginx 在/var/www/里面创建一个…...
ds回答 什么是数据召回
数据召回(Data Recall)在不同领域有不同的具体含义,但核心都指向“从大量信息中筛选出相关数据”的过程。以下是其在不同场景下的定义和关键要点: 一、技术领域的定义(信息检索与推荐系统) 1. 基本概念 数…...
复现无人机的项目,项目名称为Evidential Detection and Tracking Collaboration
项目名称为Evidential Detection and Tracking Collaboration,主要用于强大的反无人机系统,涉及新问题、基准和算法研究。下面介绍项目的复现步骤: 安装环境:使用Anaconda创建并激活名为edtc的虚拟环境,Python版本为3…...
mac本地部署Qwq-32b记录
导语 昨天看到阿里开源了Qwq-32b,号称性能可以媲美Deepseek-R1。今天晚上有空就在Mac上折腾了一下,使用ollma进行了部署,效果感觉还不错,特此记录。 环境 硬件 型号:Macbook M1 Pro 14寸内存:512G 环境…...
实验三 Python 数据可视化 Python 聚类-K-means(CQUPT)
一、实验目的 Python 数据可视化: 1、学习使用 jieba、wordcloud 等类库生成词云图。 2、学习使用 Matplotlib 库进行数据可视化。 Python 聚类-K-means: 1、理解聚类非监督学习方法的基本原理。 2、掌握 Python、numpy、pandas、sklearn 实现聚类…...
通义万相2.1:开启视频生成新时代
摘要:文章开篇便点明了通义万相2.1在视频生成领域的重大突破,强调其作为阿里云通义系列AI模型的重要成员,不仅是简单的模型升级,更是视频生成技术迈向更智能、高效、精准的重要里程碑。其核心技术包括自研的高效VAE和DiT架构&…...
JavaSec-RCE
简介 RCE(Remote Code Execution),可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景:Groovy代码注入 Groovy是一种基于JVM的动态语言,语法简洁,支持闭包、动态类型和Java互操作性,…...
基于FPGA的PID算法学习———实现PID比例控制算法
基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容:参考网站: PID算法控制 PID即:Proportional(比例)、Integral(积分&…...
基于Flask实现的医疗保险欺诈识别监测模型
基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施,由雇主和个人按一定比例缴纳保险费,建立社会医疗保险基金,支付雇员医疗费用的一种医疗保险制度, 它是促进社会文明和进步的…...
UDP(Echoserver)
网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法:netstat [选项] 功能:查看网络状态 常用选项: n 拒绝显示别名&#…...
Nginx server_name 配置说明
Nginx 是一个高性能的反向代理和负载均衡服务器,其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机(Virtual Host)。 1. 简介 Nginx 使用 server_name 指令来确定…...
Java 加密常用的各种算法及其选择
在数字化时代,数据安全至关重要,Java 作为广泛应用的编程语言,提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景,有助于开发者在不同的业务需求中做出正确的选择。 一、对称加密算法…...
【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)
升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点,但无自动故障转移能力,Master宕机后需人工切换,期间消息可能无法读取。Slave仅存储数据,无法主动升级为Master响应请求ÿ…...
Map相关知识
数据结构 二叉树 二叉树,顾名思义,每个节点最多有两个“叉”,也就是两个子节点,分别是左子 节点和右子节点。不过,二叉树并不要求每个节点都有两个子节点,有的节点只 有左子节点,有的节点只有…...
Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?
在大数据处理领域,Hive 作为 Hadoop 生态中重要的数据仓库工具,其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式,很多开发者常常陷入选择困境。本文将从底…...
【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看
文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...
