set和map的封装

目录

介绍

红黑树代码 

set

insert的迭代器转换问题

为什么会有这样的问题?

如何解决

代码 

map

注意点

代码

介绍

set和map的底层都是红黑树,所以我们可以在自己实现的红黑树(简易版)的基础上,进行封装,成为简易的set和map

红黑树代码 

#pragma once#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <cassert>
#include <cstdlib>
#include <utility>// 有迭代器的红黑树
namespace my_RB_Tree
{enum colour{black,red};template <class T>struct RBTreeNode // 结点{RBTreeNode(const T& data): _left(nullptr),_right(nullptr),_parent(nullptr),_col(red),_data(data){}RBTreeNode* _left;RBTreeNode* _right;RBTreeNode* _parent;colour _col;T _data;};template <class T, class Ptr, class Ref> // T是元素类型,ptr是指针类型,ref是引用类型(后两种会有const类型)struct RBTreeIterator                    // 迭代器{typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, Ptr, Ref> Self;//为了可以能让普通迭代器初始化const迭代器,需要来一个普通迭代器对象typedef RBTreeIterator<T, T*, T&> iterator;Node* _pNode;RBTreeIterator(Node* pNode): _pNode(pNode){}RBTreeIterator(const iterator& it) // const迭代器时,它是一个初始化;普通迭代器时,它是一个拷贝: _pNode(it._pNode){}// 让迭代器具有类似指针的行为Ref operator*(){return _pNode->_data;}Ptr operator->(){return &(_pNode->_data);}// 让迭代器可以移动：前置/后置++Self& operator++(){Increament();return *this;}Self operator++(int){Self tmp(*this);Increament();return tmp;}// 让迭代器可以移动：前置/后置--Self& operator--(){DeIncreament();return *this;}Self operator--(int){Self tmp(*this);DeIncreament();return tmp;}// 让迭代器可以比较bool operator!=(const Self& s) const{return _pNode != s._pNode;}bool operator==(const Self& s) const{return _pNode == s._pNode;}private:void Increament();void DeIncreament();};// 为了后序封装map和set，本代码的红黑树会有一个作为哨兵位的头结点template <class K, class T, class KeyOfT> // K是关键字的类型,T是元素类型(区分这两个的原因:会用该红黑树封装成set和map,而map是key_value的)// keyofT是返回关键字类型的值(否则map无法返回)class RBTree                              // 红黑树{public:typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, T*, T&> iterator;typedef RBTreeIterator<T, const T*, const T&> const_iterator;public:RBTree(){_pHead = new Node(T());_pHead->_left = _pHead;_pHead->_parent = nullptr;_pHead->_right = _pHead;}// 在红黑树中插入值为data的节点，插入成功返回true，否则返回falsestd::pair<iterator, bool> Insert(const T& data);// 检测红黑树中是否存在值为data的节点，存在返回该节点的地址，否则返回nullptrNode* Find(const K& data);// 获取红黑树最左侧节点Node* LeftMost() const;// 获取红黑树最右侧节点Node* RightMost() const;iterator begin(){return iterator(LeftMost());}iterator end(){return iterator(_pHead);}const_iterator begin() const{return const_iterator(LeftMost());}const_iterator end() const{return const_iterator(_pHead);}// 检测红黑树是否为有效的红黑树，注意：其内部主要依靠_IsValidRBTRee函数检测bool IsValidRBTRee(){Node* root = _pHead->_parent;if (root->_col == red){return false;}int count = 0;find_blacknode(count, _pHead->_parent);return _IsValidRBTRee(_pHead->_parent, count, 0);}private:bool _IsValidRBTRee(Node* pRoot, size_t blackCount, size_t pathBlack);// 左单旋void RotateL(Node* pParent);// 右单旋void RotateR(Node* pParent);// 为了操作树简单起见：获取根节点Node*& GetRoot(){return _pHead->_parent;}void find_blacknode(int& count, Node* root){if (root == nullptr){return;}if (root->_col == black){++count;}find_blacknode(count, root->_left);find_blacknode(count, root->_right);}private:Node* _pHead = nullptr;};template <class K, class T, class KeyOfT>void RBTree<K, T, KeyOfT>::RotateL(Node* pParent){Node* cur = pParent->_right, * curleft = cur->_left;// 连接p和cur左树,因为该位置被p占据pParent->_right = curleft;if (curleft){curleft->_parent = pParent;}// 连接父结点if (pParent->_parent != _pHead){Node* ppnode = pParent->_parent;if (ppnode->_left == pParent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}else{_pHead->_parent = cur;cur->_parent = _pHead;}// 连接p和curpParent->_parent = cur;cur->_left = pParent;}template <class K, class T, class KeyOfT>void RBTree<K, T, KeyOfT>::RotateR(Node* pParent){Node* cur = pParent->_left, * curright = cur->_right;// 连接p和cur右树,因为该位置被p占据pParent->_left = curright;if (curright){curright->_parent = pParent;}// 连接父结点if (pParent->_parent != _pHead){Node* ppnode = pParent->_parent;if (ppnode->_left == pParent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}else{_pHead->_parent = cur;cur->_parent = _pHead;}// 连接p和curpParent->_parent = cur;cur->_right = pParent;}template <class K, class T, class KeyOfT>typename RBTree<K, T, KeyOfT>::Node* RBTree<K, T, KeyOfT>::LeftMost() const{Node* cur = _pHead->_parent;while (cur->_left){cur = cur->_left;}return cur;}template <class K, class T, class KeyOfT>typename RBTree<K, T, KeyOfT>::Node* RBTree<K, T, KeyOfT>::RightMost() const{Node* cur = _pHead->_parent;while (cur->_right){cur = cur->_right;}return cur;}template <class K, class T, class KeyOfT>typename RBTree<K, T, KeyOfT>::Node* RBTree<K, T, KeyOfT>::Find(const K& data) // 注意这里,{Node* cur = _pHead->_parent;KeyOfT kot;while (cur){if (data > kot(cur->_data)){cur = cur->_right;}else if (data < kot(cur->_data)){cur = cur->_left;}else{return cur;}}return nullptr;}template <class K, class T, class KeyOfT>std::pair<typename RBTree<K, T, KeyOfT>::iterator, bool> RBTree<K, T, KeyOfT>::Insert(const T& data) // 为了和map适配,要返回pair类型//(first是插入元素所在的迭代器,second是bool值,判断是否成功插入){KeyOfT kot;Node* newnode = nullptr;if (_pHead->_parent == nullptr){newnode = new Node(data);newnode->_col = black;_pHead->_parent = newnode;newnode->_parent = _pHead;return std::make_pair(iterator(newnode), true);}else{Node* cur = _pHead->_parent, * parent = cur;while (cur){if (kot(data) > kot(cur->_data)){parent = cur;cur = cur->_right;}else if (kot(data) < kot(cur->_data)){parent = cur;cur = cur->_left;}else{return std::make_pair((iterator)cur, false);}}newnode = new Node(data);cur = newnode;cur->_parent = parent;if (kot(parent->_data) > kot(cur->_data)){parent->_left = cur;}else{parent->_right = cur;}Node* grandfather = nullptr;while (parent != _pHead && parent->_col == red){grandfather = parent->_parent; // 因为父结点是红色,所以肯定有爷爷结点(注意红黑树规则:根结点必须是黑色)if (grandfather->_left == parent) // 确定父亲位置{Node* uncle = grandfather->_right; // 也就能确定叔叔位置if (uncle && uncle->_col == red){parent->_col = uncle->_col = black;grandfather->_col = red;}else // 如果uncle不存在/为黑,就需要旋转+变色了{// 需要先判断旋转类型(也就是判断 -- parent和cur的相对位置)if (parent->_left == cur){// 一条偏右的直线,需要右旋RotateR(grandfather);// 旋转完后parent成为根结点// 更改完结点指向后,就可以改颜色了(都是根结点为黑,另外两个为红)parent->_col = black;cur->_col = grandfather->_col = red; // 和cur一层}else{// 拐角在左边,也就是先左旋,再右旋RotateL(parent);RotateR(grandfather);// cur成为根结点// 改颜色cur->_col = black;parent->_col = grandfather->_col = red;}break;}}else // parent在grandfather的右树{Node* uncle = grandfather->_left;if (uncle && uncle->_col == red){parent->_col = uncle->_col = black;grandfather->_col = red;}else // 如果uncle不存在/为黑,就需要旋转+变色了{// 需要先判断旋转类型(也就是判断 -- parent和cur的相对位置)if (parent->_right == cur){// 一条偏左的直线,需要左旋RotateL(grandfather);parent->_col = black;cur->_col = grandfather->_col = red; // 和cur一层}else{// 拐角在右边,也就是先右旋,再左旋RotateR(parent);RotateL(grandfather);// 改颜色cur->_col = black;parent->_col = grandfather->_col = red;}break;}}cur = grandfather; // 注意,这里会改cur的指向,但返回值需要返回插入位置的迭代器,所以需要另外保存parent = cur->_parent;}(_pHead->_parent)->_col = black; // 根结点必须为黑(防止它在上面的循环中被修改)}_pHead->_left = LeftMost();_pHead->_right = RightMost();//std::cout << (_pHead->_left)->_data << " " << (_pHead->_right)->_data << std::endl;return std::make_pair(iterator(newnode), true);}template <class K, class T, class KeyOfT>bool RBTree<K, T, KeyOfT>::_IsValidRBTRee(Node* cur, size_t blackCount, size_t pathBlack){if (cur == nullptr){// 到空结点后,就说明一条路径已经走通了,可以用得到的黑色结点数与基准数对比,不一样就说明红黑树错误if (pathBlack != blackCount){return false;}else{return true;}}if (cur->_parent){Node* ppnode = cur->_parent;if (cur->_col == red && ppnode->_col == red){return false;}}if (cur->_col == black){++pathBlack;}return _IsValidRBTRee(cur->_left, blackCount, pathBlack) && _IsValidRBTRee(cur->_right, blackCount, pathBlack);}template <class T, class Ptr, class Ref>void RBTreeIterator<T, Ptr, Ref>::Increament(){Node* cur = _pNode, * parent = _pNode->_parent;if (cur->_right){// 找到右子树的最小结点Node* curright = cur->_right;while (curright->_left){curright = curright->_left;}_pNode = curright;}else{while (parent->_parent != cur && parent->_right == cur) // 找到cur是parent的左结点的位置,这样parent的位置就是下一个位置{cur = parent;parent = parent->_parent;}_pNode = parent;}}template <class T, class Ptr, class Ref>void RBTreeIterator<T, Ptr, Ref>::DeIncreament(){Node* cur = _pNode, * parent = _pNode->_parent;if (cur->_left){// 找到左子树的最大结点Node* curleft = cur->_left;while (curleft->_right){curleft = curleft->_right;}_pNode = curleft;}else{while (parent->_parent != cur && parent->_left == cur) // 找到cur是parent的左结点的位置,这样parent的位置就是下一个位置{cur = parent;parent = parent->_parent;}_pNode = parent;}}
}

set

set我们只实现它的插入和迭代器部分,大概可以看到效果就行

insert的迭代器转换问题

不考虑别的,因为insert返回的都是pair类型的,都是迭代器+布尔值,所以set直接调用红黑树的插入即可

但是,编译过不去!

大概就是说,普通迭代器无法转换为const迭代器

为什么会有这样的问题?

注意,set中,无论是普通迭代器还是const迭代器,其实都封装的是红黑树的const迭代器

stl源码中就是这么定义的:

  • 但是,tree的insert返回的是普通迭代器,而set的insert要返回的是const迭代器
  • 这就存在一个普通迭代器向const迭代器转换的过程

如何解决

所以我们需要在红黑树的迭代器类中增加这一功能

typedef RBTreeNode<T> Node;
typedef RBTreeIterator<T, Ptr, Ref> Self;
//为了可以能让普通迭代器初始化const迭代器,需要来一个普通迭代器对象
typedef RBTreeIterator<T, T*, T&> iterator;
Node* _pNode;RBTreeIterator(Node* pNode): _pNode(pNode)
{}
RBTreeIterator(const iterator& it) // const迭代器时,它是一个初始化;普通迭代器时,它是一个拷贝: _pNode(it._pNode)
{}

代码 

#include "RB_Tree.hpp"namespace my_set
{template <class K>class set{struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:typedef typename my_RB_Tree::RBTree<K, K, SetKeyOfT>::const_iterator iterator;typedef typename my_RB_Tree::RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;const_iterator begin() const{return _t.begin();}const_iterator end() const{return _t.end();}std::pair<iterator, bool> insert(const K& data) {//return _t.Insert(data);//这里在构建时,set的insert调用tree的insert//而tree中insert的返回值,返回的pair中,第一个成员是tree的普通迭代器//然后回到该函数,该函数返回的pair的第一个成员是set中的普通迭代器(实质上是tree中的const迭代器)//所以我们本质上是用不同类型的pair在赋值//所以要先转换std::pair<typename my_RB_Tree::RBTree<K, K, SetKeyOfT>::iterator, bool> ret = _t.Insert(data); //这里是tree的普通迭代器iterator it(ret.first);return std::pair<iterator, bool>(it,ret.second); //这里是要用普通迭代器初始化一个const迭代器,所以需要在tree迭代器中增加这个功能}private:my_RB_Tree::RBTree<K, K, SetKeyOfT> _t;};
}

map

注意点

map的重点就在insert和[ ]的重载上

也没啥别的了,就需要自己先构建一个pair类型,其他的就注意返回值和接收值到底是谁

K:key值类型    V:value类型     T:map的元素类型

代码

#include "RB_Tree.hpp"namespace my_map
{template <class K, class V>class map{public:typedef std::pair<const K, V> T; // map中key不能变，value可以变struct MapKeyOfT{const V &operator()(const T &data){return data.second;}};typedef typename my_RB_Tree::RBTree<K, T, MapKeyOfT>::iterator iterator;typedef typename my_RB_Tree::RBTree<K, T, MapKeyOfT>::const_iterator const_iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}const_iterator begin() const{return _t.begin();}const_iterator end() const{return _t.end();}std::pair<iterator, bool> insert(const T &data){return _t.Insert(data);}V &operator[](const K &data){auto ret = insert(std::make_pair(data,V()));return (ret.first)->second;}private:my_RB_Tree::RBTree<K, T, MapKeyOfT> _t;};
}

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

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

GEE16: 区域日均降水量计算

GEE16: 区域日均降水量计算

Precipitation 1. 区域日均降水量计算2. 降水时间序列3. 降水数据年度时间序列对比分析 1. 区域日均降水量计算 今天分析一个计算区域日均降水量的方法&#xff1a; 数据信息&#xff1a;   Climate Hazards Group InfraRed Precipitation with Station data (CHIRPS) is a…
阅读更多...
嵌入式软件架构基础设施设计方法

嵌入式软件架构基础设施设计方法

大家好&#xff0c;今天分享一篇嵌入式软件架构设计相关的文章。 软件架构这东西&#xff0c;众说纷纭&#xff0c;各有观点。在我看来&#xff0c;软件架构是软件系统的基本结构&#xff0c;包含其组件、组件之间的关系、组件设计与演进的规则&#xff0c;以及体现这些规则的基…
阅读更多...
图像处理与计算机视觉--第五章-图像分割-Canny算子

图像处理与计算机视觉--第五章-图像分割-Canny算子

文章目录 1.边缘检测算子分类2.Canny算子核心理论2.1.Canny算子简单介绍2.2.Canny算子边缘检测指标2.3.Canny算子基本原理 3.Canny算子处理流程3.1.高斯滤波去噪声化3.2.图像梯度搜寻3.3.非极大值抑制处理3.4.双阈值边界处理3.5.边界滞后技术跟踪3.6.Canny算子边缘检测的特点 4…
阅读更多...
MySQL 索引的作用、索引结构及执行流程介绍（索引篇 一）

MySQL 索引的作用、索引结构及执行流程介绍（索引篇 一）

索引介绍 MySQL索引&#xff08;index&#xff09;是一种用于加快数据库中数据搜索和查询的数据结构。它类似于书籍的目录&#xff0c;可以帮助数据库快速定位和访问特定数据&#xff0c;而无需扫描整个数据表。 索引的作用和缺点 1. 加快数据搜索&#xff1a;通过使用索引&…
阅读更多...
Linux——指令初识

Linux——指令初识

Linux下基本指令 前言一、 ls 指令二、 pwd命令三、cd 指令四、 touch指令五、mkdir指令六、rmdir指令 && rm 指令七、man指令八、cp指令九、mv指令十、cat指令十一、.more指令十二、less指令十三、head指令十四、tail指令总结 前言 linux的学习开始啦&#xff01; 今…
阅读更多...
我的创作纪念日-第1024天

我的创作纪念日-第1024天

文章目录 一、机缘二、收获三、日常四、憧憬 一、机缘 不知不觉&#xff0c;已经加入CSDN这个大家庭5年多了&#xff0c;回想起3年前发布第一篇博客的时候&#xff0c;那时我记得很清楚&#xff0c;我在做项目时遇到报错&#xff0c;解决问题之后&#xff0c;然后想起了好多人…
阅读更多...
SpringCloud（二）Docker、Spring AMQP、ElasticSearch

SpringCloud（二）Docker、Spring AMQP、ElasticSearch

文章目录 DockerDocker与虚拟机Docker架构镜像、容器、镜像托管平台Docker架构Docker实践 Spring AMQP简单使用案例工作队列- WorkQueue发布订阅服务FanoutExchangeDirectExchangeTopicExchange 消息转换器 ElasticSearch倒排索引IK分词器IK分词拓展与停用字典 操作索引库mappi…
阅读更多...
c#基础逻辑练习案例

c#基础逻辑练习案例

第二章综合练习小游戏 练习内容 向控制台输出“这是学号姓名的C#基础小游戏”。向控制台换行再输出“请输入你的游戏昵称&#xff1a;”。向控制台输入你的游戏昵称&#xff0c;赋给一个字符串变量。向控制台换行再输出“请输入你的性别&#xff1a;”。向控制台输入你的性别…
阅读更多...
创建vue3工程

创建vue3工程

一、新建工程目录E:\vue\projectCode\npm-demo用Visual Studio Code 打开目录 二、点击新建文件夹按钮&#xff0c;新建vue3-01-core文件夹 三、右键vue3-01-core文件夹点击在集成终端中打开 四、初始化项目&#xff0c;输入npm init 一直敲回车直到创建成功如下图 npm init 五…
阅读更多...
Spring5应用之Cglib动态代理

Spring5应用之Cglib动态代理

作者简介&#xff1a;☕️大家好&#xff0c;我是Aomsir&#xff0c;一个爱折腾的开发者&#xff01; 个人主页&#xff1a;Aomsir_Spring5应用专栏,Netty应用专栏,RPC应用专栏-CSDN博客 当前专栏&#xff1a;Spring5应用专栏_Aomsir的博客-CSDN博客 文章目录 前言Cglib动态代理…
阅读更多...
uCOSIII实时操作系统 二 同步与通信

uCOSIII实时操作系统 二 同步与通信

目录 同步概念&#xff1a; 互斥概念&#xff1a; 临界区概念&#xff1a; 任务时间概念&#xff1a; 信号量概念&#xff1a; 互斥信号量概念&#xff1a; 事件标志组概念&#xff1a; 消息邮箱和消息梯队概念&#xff1a; 内存管理概念&#xff1a; 如何从裸机开发…
阅读更多...
矢量图形编辑软件illustrator 2023 mac特点介绍

矢量图形编辑软件illustrator 2023 mac特点介绍

illustrator 2023 mac是一款矢量图形编辑软件&#xff0c;用于创建和编辑排版、图标、标志、插图和其他类型的矢量图形。 illustrator mac软件特点 矢量图形&#xff1a;illustrator创建的图形是矢量图形&#xff0c;可以无限放大而不失真&#xff0c;这与像素图形编辑软件&am…
阅读更多...
六、vpp 流表+负载均衡

六、vpp 流表+负载均衡

草稿&#xff01;&#xff01;&#xff01; vpp node其实就是三个部分 1、plugin init 2、set command 3、function 实现功能&#xff0c;比如这里的流表 今天我们再用VPP实现一个流表的功能 一、流表 1.1流表----plugin init VLIB_REGISTER_NODE 注册流表节点 // 注册流…
阅读更多...
纯css实现3D鼠标跟随倾斜

纯css实现3D鼠标跟随倾斜

老规矩先上图 为什么今天会想起来整这个呢?这是因为和我朋友吵架, 就是关于这个效果的,就是这个 卡片懸停毛玻璃效果, 我朋友认为纯css也能写, 我则坦言他就是在放狗屁,这种跟随鼠标的3D效果要怎么可能能用纯css写, 然后吵着吵着发现,欸,好像真能用css写哦,我以前还写过这种…
阅读更多...
去雨去雪去雾数据集构建

去雨去雪去雾数据集构建

在进行去雨去雪去雾算法的学习过程中&#xff0c;需要构建去雨去雪去雾数据集&#xff0c;本文参考Learning Multiple Adverse Weather Removal via Two-stage Knowledge Learning and Multi-contrastive Regularization: Toward a Unified Model论文中的数据集设定&#xff0c…
阅读更多...
面试题 17.24. 最大子矩阵

面试题 17.24. 最大子矩阵

链接&#xff1a; 面试题 17.24. 最大子矩阵 题解&#xff1a; 这样我们就将二维问题转化为了一维问题&#xff0c;现在另一个问题就是怎么把所有情况都遍历到呢&#xff1f; 我们以第i行为第一行&#xff0c;向下延申&#xff0c;设最后一行为第j行&#xff0c;我们就i在这么…
阅读更多...
【AI视野·今日NLP 自然语言处理论文速览 第四十七期】Wed, 4 Oct 2023

【AI视野·今日NLP 自然语言处理论文速览 第四十七期】Wed, 4 Oct 2023

AI视野今日CS.NLP 自然语言处理论文速览 Wed, 4 Oct 2023 Totally 73 papers &#x1f449;上期速览✈更多精彩请移步主页 Daily Computation and Language Papers Contrastive Post-training Large Language Models on Data Curriculum Authors Canwen Xu, Corby Rosset, Luc…
阅读更多...
手机或者电脑连接局域网内的虚拟机（网桥）

手机或者电脑连接局域网内的虚拟机（网桥）

手机或者电脑连接局域网内的虚拟机&#xff08;网桥&#xff09; 手机软件&#xff1a;ConnectBot&#xff0c;Termius&#xff0c;JuiceSSH … 1.虚拟机vmware中添加桥接网卡 这里桥接网卡选择的是自动&#xff0c;是自动生成动态IP&#xff0c;如果不需要动态生成&#xff…
阅读更多...
MySQL：数据库的物理备份和恢复-冷备份（3）

MySQL：数据库的物理备份和恢复-冷备份（3）

介绍 物理备份&#xff1a; 直接复制数据文件进行的备份 优点&#xff1a;不需要其他的工具&#xff0c;直接复制就好&#xff0c;恢复直接复制备份文件即可 缺点&#xff1a;与存储引擎有关&#xff0c;跨平台能力较弱 逻辑备份&#xff1a; 从数据库中导出数据另存而进行的备…
阅读更多...
性能测试工具 - LoadRunner

性能测试工具 - LoadRunner

什么是性能测试&#xff1f; 性能测试就是测试人员利用性能测试工具模拟系统在不同情况下的性能指标是否正常。 性能测试工具 - LoadRunner 接下来介绍LoadRunner的作用和使用。 LoadRunner 就是一个很常见的性能测试工具&#xff0c;它有三个部分组成&#xff1a; 这三个组…
阅读更多...
最新文章

Copyright @ 2022~2023