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.rhkb.cn/news/148952.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【逐步剖C】-第十一章-动态内存管理

一、为什么要有动态内存管理 从我们平常的学习经历来看&#xff0c;所开辟的数组一般都为固定长度大小的数组&#xff1b;但从很多现实需求来看需要我们开辟一个长度“可变”的数组&#xff0c;即这个数组的大小不能在建立数组时就指定&#xff0c;需要根据某个变量作为标准。…

创建vue3工程

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

MATLAB 函数签名器

文章目录 MATLAB 函数签名器注释规范模板参数类型 kind数据格式 type选项的支持 使用可执行程序封装为m函数程序输出 编译待办事项推荐阅读附录 MATLAB 函数签名器 MATLAB 函数签名器 (FUNCSIGN) &#xff0c;在规范注释格式的基础上为函数文件或类文件自动生成函数签名&#…

select完成服务器并发

服务器 #include <myhead.h>#define PORT 4399 //端口号 #define IP "192.168.0.191"//IP地址//键盘输入事件 int keybord_events(fd_set readfds); //客户端交互事件 int cliRcvSnd_events(int , struct sockaddr_in*, fd_set *, int *); //客户端连接事件 …

国庆day5

客户端 #include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this);socket new QTcpSocket(this);//此时&#xff0c;已经向服务器发送连接请求了&#xff0c;如果成功连…

第一百六十四回 如何实现NumberPicker

文章目录 1.概念介绍2.使用方法2.1 NumberPicker2.2 CupertinoPicker 3.示例代码4.内容总结 我们在上一章回中介绍了"如何在任意位置显示PopupMenu"相关的内容&#xff0c;本章回中将介绍如何实现NumberPicker.闲话休提&#xff0c;让我们一起Talk Flutter吧。 1.概…

【重拾C语言】四、循环程序设计(后判断条件循环、先判断条件循环、多重循环;典例:计算平均成绩、打印素数、百钱百鸡问题)

目录 前言 四、循环程序设计 4.1 计算平均成绩——循环程序 4.1.1 后判断条件的循环 a. 语法 b. 典例 4.1.2 先判断条件的循环 a. 语法 b. 典例 4.1.3 for语句 a. 语法 b. 典例 4.2 计算全班每人平均成绩—多重循环 4.2.1 打印100以内素数 4.2.2 百钱百…

System Generator学习——使用 AXI 接口和 IP 集成器

文章目录 前言一、目标二、步骤1、检查 AXI 接口2、使用 System Generator IP 创建一个 Vivado 项目3、创建 IP 集成设计&#xff08;IPI&#xff09;4、实现设计 总结 前言 在本节中&#xff0c;将学习如何使用 System Generator 实现 AXI 接口。将以 IP 目录格式保存设计&am…

【MATLAB-基于直方图优化的图像去雾技术】

【MATLAB-基于直方图优化的图像去雾技术】 1 直方图均衡2 程序实现3 局部直方图处理 1 直方图均衡 直方图是图像的一种统计表达形式。对于一幅灰度图像来说&#xff0c;其灰度统计直方图可以反映该图像中不同灰度级出现的统计情况。一般而言&#xff0c;图像的视觉效果和其直方…

HUAWEI悦盒ec6108v9c 如何刷成海纳思系统(家用低功耗服务器,使用Home Assistant服务)

环境&#xff1a; 1.HW悦盒ec6108v9c一套 2.16G U盘 3.格式化软件USB_format.exe 4.固件 mv100-mdmo1g-usb-flash.zip&#xff08;底层是Ubuntu 20.04系统&#xff09; 5.十字螺丝刀 6.翘片/薄铲子 7.有线网络环境 8.镊子/回形针 问题描述&#xff1a; 最近玩智能家居…

OpenCV项目开发实战--使用最先进的方法“F、B、Alpha Matting”进行图像抠图--提供完整代码

示范 让我们对现实生活中的图像启动 FBA Matting 方法。要应用 FBA Matting 算法,我们首先需要生成一个 trimap(我们稍后会介绍它是什么)。在我们的演示中,我们将使用预训练的DeepLabV3生成分割掩模,其中每个像素属于前景类的概率。之后,我们将使用大量膨胀操作将边界像…

面向无线传感器网络WSN的增强型MODLEACH设计与仿真(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…

QT4.8.7安装详细教程

QT4.8.7安装详细教程&#xff08;MinGW 4.8.2和QTCreator4.2.0&#xff09; 1.下载及安装2.配置环境 此文是在下方链接博文的基础上&#xff0c;按自己的理解整理的https://blog.csdn.net/xiaowanzi199009/article/details/104119265 1.下载及安装 这三个文件&#xff0c;顺序是…

微信小程序代驾系统源码(含未编译前端,二开无忧) v2.5

简介&#xff1a; 如今有越来越多的人在网上做代驾&#xff0c;打造一个代驾平台&#xff0c;既可以让司机增加一笔额外的收入&#xff0c;也解决了车主酒后不能开发的问题&#xff0c;代驾系统基于微信小程序开发的代驾系统支持一键下单叫代驾&#xff0c;支持代驾人员保证金…

Elasticsearch安装访问

Elasticsearch 是一个开源的、基于 Lucene 的分布式搜索和分析引擎&#xff0c;设计用于云计算环境中&#xff0c;能够实现实时的、可扩展的搜索、分析和探索全文和结构化数据。它具有高度的可扩展性&#xff0c;可以在短时间内搜索和分析大量数据。 Elasticsearch 不仅仅是一个…

C++ 类和对象篇(四) 构造函数

目录 一、概念 1. 构造函数是什么&#xff1f; 2. 为什么C要引入构造函数&#xff1f; 3. 怎么用构造函数&#xff1f; 3.1 创建构造函数 3.2 调用构造函数 二、构造函数的特性 三、构造函数对成员变量初始化 0. 对构造函数和成员变量分类 1. 带参构造函数对成员变量初始化 2. …

MyBatisPlus(十一)判空查询:in

说明 判空查询&#xff0c;对应SQL语句中的 in 语句&#xff0c;查询参数包含在入参列表之内的数据。 in Testvoid inNonEmptyList() {// 非空列表&#xff0c;作为参数List<Integer> ages Stream.of(18, 20, 22).collect(Collectors.toList());in(ages);}Testvoid in…

Gorsonpy的计算器

Gorsonpy的计算器 0.页面及功能展示1. PSP表格2.解题思路描述3.设计实现过程4.程序性能改进5.异常处理6.单元测试展示7.心路历程和收获 这个作业属于哪个课程https://bbs.csdn.net/forums/ssynkqtd-05这个作业要求在哪里https://bbs.csdn.net/topics/617294583这个作业的目标完…

手边酒店V2独立版小程序 1.0.21 免授权+小程序前端

手边酒店小程序独立版酒店宾馆订房系统支持创建多个小程序&#xff0c;让每一个客户单独管理属于自己的小程序。后台支持一键入住&#xff0c;一键退款、退押金、钟点房支持微信支付、模板消息。客服实时收到新的订单信息&#xff0c;可以在手机端处理订单。支持按日期维护房价…

基于SpringBoot的智能推荐的卫生健康系统

目录 前言 一、技术栈 二、系统功能介绍 用户管理 科室类型管理 医生信息管理 健康论坛管理 我的发布 我的收藏 在线咨询 三、核心代码 1、登录模块 2、文件上传模块 3、代码封装 前言 随着信息技术在管理上越来越深入而广泛的应用&#xff0c;管理信息系统的实施在…