当前位置: 首页 > news >正文

C++之map和set的模拟实现

目录

引言

红黑树迭代器实现

红黑树元素的插入

map模拟实现 

set模拟实现


之前我们已经学习了map和set的基本使用,但是因为map和set的底层都是用红黑树进行封装实现的,上期我们已经学习了红黑树的模拟实现,所以本期我们在红黑树模拟实现的基础之上,对红黑树进行进一步封装,实现map和set的模拟实现。

引言

首先大家思考一个问题,map和set既然它们底层都是使用红黑树进行模拟实现的,我们知道map是搜索二叉树中的kv模型,set是搜索二叉树中的k模型,那么两种模型难道使用两颗红黑树实现吗?

当然不是,map和set底层都是使用同一颗红黑树实现的,我们通过使用模板达到这一目的,这也体现了泛式编程的重要性。

我们对上期红黑树模拟实现的代码进行一点点改造,基于下述代码来进行map和set的模拟实现。

红黑树迭代器实现

template<class T,class Ref,class Ptr>
struct RBTreeIterator
{typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, Ref, Ptr> Self;RBTreeIterator(Node* node){_node = node;}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}Self& operator++(){Node* cur = _node;if (cur->_right){cur = cur->_right;while (cur->_left){cur = cur->_left;}_node = cur;}else{Node* parent = cur->_parent;while (parent){if (cur == parent->_left){_node = parent;break;}else{while (parent && cur == parent->_right){cur = parent;parent = cur->_parent;}_node = parent;break;}}}return *this;}Self& operator--(){Node* cur = _node;if (cur->_left){cur = cur->_left;while (cur->_left){cur = cur->_right;}_node = cur;}else{Node* parent = cur->_parent;while (parent){if (cur == parent->_right){_node = parent;break;}else{while (cur == parent->_left){cur = parent;parent = cur->_parent;}_node = parent;break;}}}return *this;}bool operator!=(const Self& s) const{return _node != s._node;}bool operator==(const Self& s)  const{return _node == s._node;}Node* _node;
};

 上述代码有两个难点,分别是迭代器的++和迭代器的--。迭代器的++和迭代器的--操作。

搜索二叉树的遍历,++和--操作,一般是按照搜索二叉树的中序遍历为基础来进行进一步封装的。++操作要去判断当前节点是否有右孩子,--操作得先去判断是否有左孩子。

红黑树元素的插入

pair<iterator,bool> Insert(const T& data){//如果当前红黑树为空,则直接插入即可if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return make_pair(iterator(_root),true);}//如果当前红黑树不为空,就要先找到合适的位置,然后进行节点的插入Node* cur = _root;Node* parent = _root->_parent;KeyOfT kot;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;cur->_col = RED;cur->_parent = parent;if ( kot(cur->_data) > kot(parent->_data)){parent->_right = cur;}else{parent->_left = cur;}//调整平衡while (parent && parent->_col == RED){Node* grandfather = parent->_parent;//1.叔叔节点都存在,且都为红色节点,就要进行颜色平衡if (parent == grandfather->_right){Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{//2.叔叔节点不存在//3.叔叔节点的颜色为黑色if (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else{Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{//2.叔叔节点不存在//3.叔叔节点的颜色为黑色if (cur == parent->_left){RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}//强制性的让根节点为黑色,符合红黑树的性质_root->_col = BLACK;return make_pair(iterator(newnode),true);}

在进行元素的插入时,我们需要注意,插入函数的返回值,返回值是一个pair类型的对象,first为迭代器(插入成功返回新插入的元素所对应的节点的迭代器,插入失败,返回已经存在的元素所对应的节点的迭代器),second为一个bool值(插入成功为true,插入失败为false)。

map模拟实现 

#pragma once
#include"RBTree.h"
namespace yjd 
{template<class K,class V >class map{public:struct MapKeyOfT{const K& operator()(const pair<K,V>& pair ){return pair.first;}};typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator;iterator begin(){return _rbt.begin();}iterator end(){return _rbt.end();}iterator find(){return _rbt.Find();}pair<iterator, bool> insert(const pair<K,V>& pair){return _rbt.Insert(pair);}V& operator[](const K& key){auto ret = _rbt.Insert(make_pair(key, V()));return ret.first->second;}private:RBTree<K, pair<K, V>, MapKeyOfT> _rbt;};void MapTest(){map<string, string> dict;dict.insert(make_pair("sort", "排序"));dict.insert(make_pair("string", "字符串"));dict.insert(make_pair("map", "地图"));dict["left"];dict["left"] = "左边";dict["map"] = "地图、映射";auto it = dict.begin();while (it != dict.end()){cout << it->first << ":" << it->second << endl;++it;}cout << endl;}}

通过代码不难发现,map的模拟实现基本上还是套用红黑树的接口,唯一需要注意的就是operator[]这个函数接口,第一步是先转化为元素的插入,第二步通过第一步的返回值,来进一步访问插入元素的元素所对应的pair对象的second成员。简单来说operator[]的返回值就是括号内部key值所对应的pair对象的第二个second成员的引用。

在进行元素的插入时,我们先要找到元素合适的位置,然后再进行元素的插入,但是因为map元素的大小我们是根据pair对象的first成员进行比较的,所以我们使用到了仿函数MapKeyOfT,获取到了pair对象的第一个first成员去进行比较。

运行截图如下。

运行结果符合预期。

set模拟实现

#pragma once
#include"RBTree.h"
namespace yjd
{template<class K>class set{public:struct SetKeyOfT{const K& operator()(const K& key){return key;}};typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;iterator begin(){return _rbt.begin();}iterator end(){return _rbt.end();}iterator find(const K& key){return _rbt.Find(key);}pair<iterator, bool> insert(const K& k){return _rbt.Insert(k);}private:RBTree<K, K, SetKeyOfT> _rbt;};void test_set(){set<int> s;s.insert(1);s.insert(4);s.insert(2);s.insert(24);s.insert(2);s.insert(12);s.insert(6);set<int>::iterator it = s.begin();while (it != s.end()){cout << *it <<" ";++it;}}}

set的模拟实现也是基于红黑树的接口,是对红黑树接口的进一步封装。相比较map的模拟实现,更简单一些。 

运行结果如下。

运行结果符合预期。 

 

相关文章:

C++之map和set的模拟实现

目录 引言 红黑树迭代器实现 红黑树元素的插入 map模拟实现 set模拟实现 之前我们已经学习了map和set的基本使用&#xff0c;但是因为map和set的底层都是用红黑树进行封装实现的&#xff0c;上期我们已经学习了红黑树的模拟实现&#xff0c;所以本期我们在红黑树模拟实现…...

判断一个单链表是否是回文结构 要求O(N)时间复杂度 O(1)空间复杂度

没做出来 看了解析 但是思路想到了 就是只能调整链表顺序&#xff0c;正确答案是 把链表变成两条单链表&#xff0c;分别从两侧走向中间拿两个指针 分别指向两头 &#xff0c;往中间走 中途有不一样的就返回false, private static boolean handle(Node head){int size size…...

Kafka 快速实战及基本原理详解解析-01

一、Kafka 介绍 1. MQ 的作用 消息队列&#xff08;Message Queue&#xff0c;简称 MQ&#xff09;是一种用于跨进程通信的技术&#xff0c;核心功能是通过异步消息的方式实现系统之间的解耦。它在现代分布式系统中有着广泛的应用&#xff0c;主要作用体现在以下三个方面&…...

wujie无界微前端框架初使用

先说一下项目需求&#xff1a;将单独的四套系统的登录操作统一放在一个入口页面进行登录&#xff0c;所有系统都使用的是vue3&#xff0c;&#xff08;不要问我为啥会这样设计&#xff0c;产品说的客户要求&#xff09; 1.主系统下载wujie 我全套都是vue3&#xff0c;所以直接…...

C++ 设计模式:职责链模式(Chain of Responsibility)

链接&#xff1a;C 设计模式 链接&#xff1a;C 设计模式 - 组合模式 链接&#xff1a;C 设计模式 - 迭代器模式 职责链模式&#xff08;Chain of Responsibility Pattern&#xff09;是一种行为型设计模式&#xff0c;它允许多个对象都有机会处理请求&#xff0c;从而避免请求…...

Yocto项目 - 详解PACKAGECONFIG机制

引言 Yocto项目是一个强大的嵌入式Linux开发工具&#xff0c;广泛应用于创建定制的嵌入式Linux发行版。在Yocto中&#xff0c;配置和定制化构建系统、软件包、以及生成适用于特定硬件的平台镜像是非常重要的。PACKAGECONFIG是Yocto项目中用于灵活启用或禁用软件包特性的强大工…...

Linux下部署ElasticSearch集群

Elasticsearch7.17.8集群的搭建 节点host名称节点ip节点部署内容k8s-m192.168.40.142主节点 数据节点k8s-w1192.168.40.141主节点 数据节点k8s-w2192.168.40.140数据节点 一、准备安装环境 1.下载安装包 官网 www.elastic.co 下载所有版本地址 点击跳转 下载elasticsearch-7.…...

超高分辨率 图像 分割处理

文章大纲 制造业半导体领域高分辨率图像半导体数据集开源的高分辨率晶圆图像数据集1. WM-811K数据集2. Kaggle上的WM-811K Clean Subset数据集医疗 病理领域高分辨率图像1. Camelyon+2. CAMELYON173. CPIA Dataset4. UCF-WSI-Dataset航拍 遥感中的高分辨率 图像航拍遥感领域高分…...

【含文档+PPT+源码】基于springboot的农贸菜市场租位管理系统的设计与实现

开题报告 本文旨在探讨基于SpringBoot框架构建的农贸菜市场租位管理系统的设计与实现。系统结合了现代化信息技术与农贸市场管理需求&#xff0c;为用户提供了注册登录、查看系统公告、分类搜索店铺、查看店铺详情、填写租赁信息、在线租赁、我的订单管理以及用户信息和密码修…...

信息科技伦理与道德1:绪论

1 问题描述 1.1 信息科技的进步给人类生活带来的是什么呢&#xff1f; 功能&#xff1f;智能&#xff1f;陪伴&#xff1f;乐趣&#xff1f;幸福&#xff1f; 基于GPT-3的对话Demo DeepFake 深伪技术&#xff1a;通过神经网络技术进行大样本学习&#xff0c;将个人的声音、面…...

Linux实验报告15-添加系统调用

目录 一&#xff1a;实验目的 二&#xff1a;实验内容 &#xff08;1&#xff09;查看系统内核版本 &#xff08;2&#xff09;安装内核版本源码 &#xff08;3&#xff09;修改注册表 &#xff08;4&#xff09;添加系统调用头文件 &#xff08;5&#xff09;实现系统调…...

logback之配置文件使用详解

目录 &#xff08;一&#xff09;配置文件的加载 &#xff08;二&#xff09;使用介绍 1、configuration&#xff1a;配置文件的跟元素 2、contextName&#xff1a;设置日志上下文名称 3、contextListener&#xff1a;设置上下文监听事件 4、property/variable/substituti…...

壁纸样机神器,这个工具适合专业设计师用吗?

壁纸样机神器在一定程度上适合专业设计师使用&#xff0c;但是否适合具体取决于设计师的需求和使用场景&#xff1a; 适合专业设计师的方面 快速实现设计想法&#xff1a;专业设计师在创作过程中&#xff0c;有时需要快速将设计想法变为可视化的效果图&#xff0c;以便进行初…...

MySQL秘籍之索引与查询优化实战指南

MySQL秘籍之索引与查询优化实战指南 目录 MySQL秘籍之索引与查询优化实战指南相关阅读索引相关EXPLAIN 版本 1. 初级篇1.1 【练体术】基础1.1.1 库操作1.1.1 表操作创建一个表增加表字段 1.1.2 增删改插入一条数据删除一条数据更新一条数据库 1.1.3 查询查询所有数据条件查询&a…...

【AI日记】25.01.03 kaggle 比赛 3-2 未来的命运

【AI论文解读】【AI知识点】【AI小项目】【AI战略思考】【AI日记】 工作 参加&#xff1a;kaggle 比赛 Forecasting Sticker Sales时间&#xff1a;8 小时 读书 书名&#xff1a;秦制两千年时间&#xff1a;1.5 小时评估&#xff1a;读完&#xff0c;非常不错&#xff0c;很…...

Linux(Centos 7.6)命令详解:ls

1.命令作用 列出目录内容(list directory contents) 2.命令语法 Usage: ls [OPTION]... [FILE]... 3.参数详解 OPTION: -l&#xff0c;long list 使用长列表格式-a&#xff0c;all 不忽略.开头的条目&#xff08;打印所有条目&#xff0c;包括.开头的隐藏条目&#xff09…...

【Unity3D】UGUI Canvas画布渲染流程

参考文档&#xff1a;画布 - Unity 手册 Canvas组件&#xff1a;画布组件是进行 UI 布局和渲染的抽象空间。所有 UI 元素都必须是附加了画布组件的游戏对象的子对象。 参数&#xff1a; Render Mode 渲染模式&#xff1a;Screen Space - Overlay、Screen Spa…...

minikube安装k8s

一、安装k8s版本 export REGISTRY_MIRRORhttps://registry.cn-hangzhou.aliyuncs.com curl -sSL https://kuboard.cn/install-script/v1.30.x/install_kubelet.sh | sh -s 1.30.0 二、安装docker及minikube useradd docker passwd docker 密码也设置为docker #创建docker组…...

Docker图形化界面工具Portainer最佳实践

前言 安装Portainer 实践-基于Portainer安装redis-sentinel部署 Spring Boot集成Redis Sentinel 前言 本篇文章笔者推荐一个笔者最常用的docker图形化管理工具——Portainer。 安装Portainer 编写docker-compose文件 Portainer部署的步骤比较简单&#xff0c;我们还是以…...

借助 FinClip 跨端技术探索鸿蒙原生应用开发之旅

在当今数字化浪潮汹涌澎湃的时代&#xff0c;移动应用开发领域正经历着深刻的变革与创新。鸿蒙操作系统的崛起&#xff0c;以其独特的分布式架构和强大的性能表现&#xff0c;吸引了众多开发者的目光。而FinClip 跨端技术的出现&#xff0c;为开发者涉足鸿蒙原生应用开发提供了…...

UE5 学习系列(二)用户操作界面及介绍

这篇博客是 UE5 学习系列博客的第二篇&#xff0c;在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下&#xff1a; 【Note】&#xff1a;如果你已经完成安装等操作&#xff0c;可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作&#xff0c;重…...

生成xcframework

打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式&#xff0c;可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

CTF show Web 红包题第六弹

提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框&#xff0c;很难让人不联想到SQL注入&#xff0c;但提示都说了不是SQL注入&#xff0c;所以就不往这方面想了 ​ 先查看一下网页源码&#xff0c;发现一段JavaScript代码&#xff0c;有一个关键类ctfs…...

Docker 运行 Kafka 带 SASL 认证教程

Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明&#xff1a;server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...

线程与协程

1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指&#xff1a;像函数调用/返回一样轻量地完成任务切换。 举例说明&#xff1a; 当你在程序中写一个函数调用&#xff1a; funcA() 然后 funcA 执行完后返回&…...

【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)

升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点&#xff0c;但无自动故障转移能力&#xff0c;Master宕机后需人工切换&#xff0c;期间消息可能无法读取。Slave仅存储数据&#xff0c;无法主动升级为Master响应请求&#xff…...

VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP

编辑-虚拟网络编辑器-更改设置 选择桥接模式&#xff0c;然后找到相应的网卡&#xff08;可以查看自己本机的网络连接&#xff09; windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置&#xff0c;选择刚才配置的桥接模式 静态ip设置&#xff1a; 我用的ubuntu24桌…...

比较数据迁移后MySQL数据库和OceanBase数据仓库中的表

设计一个MySQL数据库和OceanBase数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...

十九、【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建

【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建 前言准备工作第一部分:回顾 Django 内置的 `User` 模型第二部分:设计并创建 `Role` 和 `UserProfile` 模型第三部分:创建 Serializers第四部分:创建 ViewSets第五部分:注册 API 路由第六部分:后端初步测…...

沙箱虚拟化技术虚拟机容器之间的关系详解

问题 沙箱、虚拟化、容器三者分开一一介绍的话我知道他们各自都是什么东西&#xff0c;但是如果把三者放在一起&#xff0c;它们之间到底什么关系&#xff1f;又有什么联系呢&#xff1f;我不是很明白&#xff01;&#xff01;&#xff01; 就比如说&#xff1a; 沙箱&#…...