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架构&…...
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...
R语言AI模型部署方案:精准离线运行详解
R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...
Spring Boot 实现流式响应(兼容 2.7.x)
在实际开发中,我们可能会遇到一些流式数据处理的场景,比如接收来自上游接口的 Server-Sent Events(SSE) 或 流式 JSON 内容,并将其原样中转给前端页面或客户端。这种情况下,传统的 RestTemplate 缓存机制会…...
Oracle查询表空间大小
1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...
线程同步:确保多线程程序的安全与高效!
全文目录: 开篇语前序前言第一部分:线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分:synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分ÿ…...
镜像里切换为普通用户
如果你登录远程虚拟机默认就是 root 用户,但你不希望用 root 权限运行 ns-3(这是对的,ns3 工具会拒绝 root),你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案:创建非 roo…...
数据链路层的主要功能是什么
数据链路层(OSI模型第2层)的核心功能是在相邻网络节点(如交换机、主机)间提供可靠的数据帧传输服务,主要职责包括: 🔑 核心功能详解: 帧封装与解封装 封装: 将网络层下发…...
Unity UGUI Button事件流程
场景结构 测试代码 public class TestBtn : MonoBehaviour {void Start(){var btn GetComponent<Button>();btn.onClick.AddListener(OnClick);}private void OnClick(){Debug.Log("666");}}当添加事件时 // 实例化一个ButtonClickedEvent的事件 [Formerl…...
从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障
关键领域软件测试的"安全密码":Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力,从金融交易到交通管控,这些关乎国计民生的关键领域…...
论文阅读笔记——Muffin: Testing Deep Learning Libraries via Neural Architecture Fuzzing
Muffin 论文 现有方法 CRADLE 和 LEMON,依赖模型推理阶段输出进行差分测试,但在训练阶段是不可行的,因为训练阶段直到最后才有固定输出,中间过程是不断变化的。API 库覆盖低,因为各个 API 都是在各种具体场景下使用。…...
