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架构&…...
网络编程(Modbus进阶)
思维导图 Modbus RTU(先学一点理论) 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议,由 Modicon 公司(现施耐德电气)于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...
XML Group端口详解
在XML数据映射过程中,经常需要对数据进行分组聚合操作。例如,当处理包含多个物料明细的XML文件时,可能需要将相同物料号的明细归为一组,或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码,增加了开…...
Leetcode 3577. Count the Number of Computer Unlocking Permutations
Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接:3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯,要想要能够将所有的电脑解锁&#x…...
【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)
可以使用Sqliteviz这个网站免费编写sql语句,它能够让用户直接在浏览器内练习SQL的语法,不需要安装任何软件。 链接如下: sqliteviz 注意: 在转写SQL语法时,关键字之间有一个特定的顺序,这个顺序会影响到…...
重启Eureka集群中的节点,对已经注册的服务有什么影响
先看答案,如果正确地操作,重启Eureka集群中的节点,对已经注册的服务影响非常小,甚至可以做到无感知。 但如果操作不当,可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...
Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析
Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问(基础概念问题) 1. 请解释Spring框架的核心容器是什么?它在Spring中起到什么作用? Spring框架的核心容器是IoC容器&#…...
音视频——I2S 协议详解
I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议,专门用于在数字音频设备之间传输数字音频数据。它由飞利浦(Philips)公司开发,以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...
JavaScript基础-API 和 Web API
在学习JavaScript的过程中,理解API(应用程序接口)和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能,使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...
Bean 作用域有哪些?如何答出技术深度?
导语: Spring 面试绕不开 Bean 的作用域问题,这是面试官考察候选人对 Spring 框架理解深度的常见方式。本文将围绕“Spring 中的 Bean 作用域”展开,结合典型面试题及实战场景,帮你厘清重点,打破模板式回答,…...
解析奥地利 XARION激光超声检测系统:无膜光学麦克风 + 无耦合剂的技术协同优势及多元应用
在工业制造领域,无损检测(NDT)的精度与效率直接影响产品质量与生产安全。奥地利 XARION开发的激光超声精密检测系统,以非接触式光学麦克风技术为核心,打破传统检测瓶颈,为半导体、航空航天、汽车制造等行业提供了高灵敏…...
