【C++】map和set的封装

回顾：之前我们一起学习了map，set，multimap，multiset的接口和相关介绍map和se详细介绍

还实现了AVL树以及RB树，旋转，旋转+变色相信大家已经很熟悉啦手撕AVL和红黑树

本文将带大家一起封装map和set

目录

1.找到方向

2.迭代器最重要的部分

3.set迭代器和map迭代器 

4.我的实现

5.源码

1.找到方向

首先 我们在实现之前要了解库里面实现的逻辑是什么

 也就是对于set，红黑树的节点模板参数只有K，对于map，红黑树节点的模版参数是pair<const K,V>

第一个模板参数为了拿到单独的K类型（相当于索引）  因为find,erase这些接口函数的参数是K

第二个模版参数决定了树的节点里面存什么——K or KV（索引到的结果）

 所以我们直接把第二个模板参数改成T，对于set T就是K，对于map T就是pair<const K,V>

2.迭代器最重要的部分

begin应该在树中序的第一个，也就是左子树的最后一个节点

end这里我们为了简单 就给成nullptr  但是库里面使用哨兵头节点

库里面的end：对end()位置的迭代器进行--操作，必须要能找最后一个元素，最好的方式是将end()放在头结点的位置

 迭代器的++怎么操作？

Self& operator++() {if (_node->_right) {//1.右不是空 下一个就是右子树的最左节点node* subL = _node->_right;while (subL->_left) {subL = subL->_left;}_node = subL;}else {//2.右为空  当前子树完了 沿着到根的路径 找孩子是父亲左的那个祖先node* cur = _node;node* parent = cur->_parent;while (parent && cur == parent->_right) {cur = parent;parent = parent->_parent;}_node = parent;}return *this;}

 ++要根据中序  左——根——右 

看右子树是不是空 如果是说明当前右子树的根 这一支走完了

要找到这一支的根

只要用一个parent前驱保存一下

--当然是相反的操作

Self& operator--() {if (_node->_left) {//1.左不是空 下一个就是左子树的最右节点node* subR = _node->_left;while (subR->_right) {subR = subR->_right;}_node = subR;}else {//2.左为空  找孩子是父亲的右的那个祖先node* cur = _node;node* parent = cur->_parent;while (parent && cur == parent->_left) {cur = parent;parent = parent->_parent;}_node = parent;}return *this;}

 3.set迭代器和map迭代器 

set的K不能修改 但是现在实现的迭代器居然可以修改！！！

看了库之后发现set的普通迭代器都是const实现的

那么我们跟着改一下啦~~

但是这样报错了 

  • 报错的原因 

_t是一个普通的树 普通对象调用begin返回普通的迭代器

但是在set中我们的普通迭代器都是用const迭代器实现的 

所以出现了问题 根本没有从普通迭代器到const迭代器的构造

报错原因：

编译器看到是一个普通迭代器转换成一个const迭代器 认为这里是类型转换

类型转换可以依赖单参数的构造函数

所以他去匹配

这个构造 没办法把一个普通迭代器转化成node类型

  • 大佬是这样解决

 

这个函数到底实现的拷贝构造还是构造  取决于类模板被实例化成什么

因为被实例化成const迭代器的时候 传入的就是const& const* 也就是Ref接受了const&  Ptr接受了const*

 在set中 类模板中iterator就是被实例化成const迭代器 所以就可以实现从普通迭代器到const迭代器的构造

反观map，应该是k不能改 v可以修改

 因为pair帮我们把K给const 迭代器都是正常的

 

 4.我的实现

仓库里有代码 

RBTree.h

#pragma once
#include "标头.h"
enum Colour {RED,BLACK,
};
template<class T>
struct RBNode {RBNode<T>* _left;RBNode<T>* _right;RBNode<T>* _parent;T _data;Colour _col;RBNode(const T& data):_left(nullptr), _right(nullptr), _parent(nullptr),_col(RED),_data(data){}
};
template <class T,class Ref,class Ptr>
struct __RBTreeIterator {typedef RBNode<T> node;typedef __RBTreeIterator<T, Ref, Ptr> Self;node*  _node;__RBTreeIterator(node* node) :_node(node){}__RBTreeIterator(const __RBTreeIterator<T,T&,T*>& it) //注意这个不是拷贝构造 相当于传入普通迭代器最后返回:_node(it._node){}Ref  operator*(){return _node->_data;}Ptr operator->() {return &_node->_data;}bool operator!=(const Self& s) {return _node != s._node;}Self& operator++() {if (_node->_right) {//1.右不是空 下一个就是右子树的最左节点node* subL = _node->_right;while (subL->_left) {subL = subL->_left;}_node = subL;}else {//2.右为空  当前子树完了 沿着到根的路径 找孩子是父亲左的那个祖先node* cur = _node;node* parent = cur->_parent;while (parent && cur == parent->_right) {cur = parent;parent = parent->_parent;}_node = parent;}return *this;}Self& operator--() {if (_node->_left) {//1.左不是空 下一个就是左子树的最右节点node* subR = _node->_left;while (subR->_right) {subR = subR->_right;}_node = subR;}else {//2.左为空  找孩子是父亲的右的那个祖先node* cur = _node;node* parent = cur->_parent;while (parent && cur == parent->_left) {cur = parent;parent = parent->_parent;}_node = parent;}return *this;}
};template<class K, class T,class KeyofT>
class RBTree
{
public:typedef RBNode<T> node;~RBTree(){_Destroy(_root);_root = nullptr;}
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 && cur->_left) {cur = cur->_left;}return iterator(cur);}const iterator end() const {return iterator(nullptr);}node* Find(const K& key){node* cur = _root;KeyofT kot;while (cur) {if (kot(cur->_data) < key) {cur = cur->_right;}else if (kot(cur->_data) > key) {cur = cur->_left;}else return cur;}return nullptr;}void RotateL(node* pre) {//subR  subRL  pp//pre_bf = 2 && cur_bf  = 1//要注意的是subRL可能是空  pre的pre可能是空（此时检索到根节了）node* subR = pre->_right;node* subRL = subR->_left;pre->_right = subRL;if (subRL) subRL->_parent = pre;node* pp = pre->_parent;subR->_left = pre;pre->_parent = subR;if (pp == nullptr) {_root = subR;_root->_parent = nullptr;}else {if (pp->_left == pre) {pp->_left = subR;}else {pp->_right = subR;}subR->_parent = pp;}}void RotateR(node* pre) {//subL  subLR pp//pre_bf=-2  cur_bf=-1node* subL = pre->_left;node* subLR = subL->_right;pre->_left = subLR;if (subLR) subLR->_parent = pre;node* pp = pre->_parent;subL->_right = pre;pre->_parent = subL;if (pre == _root) {_root = subL;_root->_parent = nullptr;}else {if (pp->_left == pre) pp->_left = subL;else pp->_right = subL;subL->_parent = pp;}}bool IsBalance() {if (_root && _root->_col == RED) {cout << "根节点颜色是红色" << endl;return false;}int benchmark = 0;node* cur = _root;while (cur) {if (cur->_col == BLACK) ++benchmark;cur = cur->_left;}return _Check(_root, 0, benchmark);}int Height(){return _Height(_root);}pair<iterator, bool> Insert(const T& data){if (_root == nullptr){_root = new node(data);_root->_col = BLACK;return make_pair(iterator(_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(iterator(cur), false);}}cur = new node(data);node* newnode = cur;if (kot(parent->_data) > kot(data)){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;while (parent && parent->_col == RED){node* grandfather = parent->_parent;if (grandfather->_left == parent){node* uncle = grandfather->_right;// 情况1：u存在且为红，变色处理，并继续往上处理if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;// 继续往上调整cur = grandfather;parent = cur->_parent;}else // 情况2+3：u不存在/u存在且为黑，旋转+变色{//     g//   p   u// c if (cur == parent->_left){RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//     g//   p   u//     cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;//parent->_col = RED;grandfather->_col = RED;}break;}}else // (grandfather->_right == parent){//    g//  u   p//        cnode* uncle = grandfather->_left;// 情况1：u存在且为红，变色处理，并继续往上处理if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;// 继续往上调整cur = grandfather;parent = cur->_parent;}else // 情况2+3：u不存在/u存在且为黑，旋转+变色{//    g//  u   p//        cif (cur == parent->_right){RotateL(grandfather);grandfather->_col = RED;parent->_col = BLACK;}else{//    g//  u   p//    cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return make_pair(iterator(newnode), true);;}
private:void _Destroy(node* root){if (root == nullptr){return;}_Destroy(root->_left);_Destroy(root->_right);delete root;}int _Height(node* root){if (root == NULL)return 0;int leftH = _Height(root->_left);int rightH = _Height(root->_right);return leftH > rightH ? leftH + 1 : rightH + 1;}bool _Check(node* root, int blacknum, int benchmark){if (root == nullptr) {if (benchmark != blacknum) {cout << "某条路上黑节点数量不等" << endl;return false;}return true;}if (root->_col == BLACK) {++blacknum;}if (root->_col == RED && root->_parent && root->_parent->_col==RED) {cout << "存在连续红色" << endl;return false;}return _Check(root->_left, blacknum, benchmark) && _Check(root->_right, blacknum, benchmark);}private:node* _root=nullptr;
};

map.h

#pragma once
#include "RBTree.h"
namespace wrt {template<class K,class V>class map{public:struct MapKeyofT {const K& operator()(const pair<const K,V>& kv) {return kv.first;}};typedef typename RBTree<K, pair<const K, V>, MapKeyofT>::iterator iterator;typedef typename RBTree<K, pair<const K, V>, MapKeyofT>::const_iterator const_iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}V& operator[](const  K& key){pair<iterator,bool> ret=_t.Insert(make_pair(key, V()));return ret.first->second;}pair<iterator, bool> insert(const pair<const K, V>& kv){return _t.Insert(kv);}private:RBTree<K, pair<const K, V>,MapKeyofT> _t;};void test_map1(){map<string, string> dict;dict.insert(make_pair("sort", "排序"));dict.insert(make_pair("string", "字符串"));dict.insert(make_pair("count", "计数"));dict.insert(make_pair("string", "字符"));//插入失败map<string, string>::iterator it = dict.begin();while (it != dict.end()){cout << it->first << ":" << it->second << endl;it->first = "sdh";it->second = "222";++it;}cout << endl;for (auto& kv : dict){cout << kv.first << ":" << kv.second << endl;}cout << endl;}void test_map2(){string arr[] = { "hello","hello","hi"};map<string, int> countMap;for (auto& e : arr){countMap[e]++;}for (auto& kv : countMap){cout << kv.first << ":" << kv.second << endl;}}}

set.h

#pragma once
#include "RBTree.h"
namespace wrt {template<class K>class set {struct SetKeyofT {const K& operator()(const K& key) {return key;}};public://编译器无法识别RBTree<K, K, SetKeyofT>是一个静态变量还是一个类型//类模板里面取RBTree<K, K, SetKeyofT> 一定要加上typename //目的是告诉编译器这是一个类型 等类模板实例化之后再去取这个类型//由于set不能修改K也就是value 普通迭代器也是用const迭代器实现的typedef typename  RBTree<K, K, SetKeyofT>::const_iterator  iterator;typedef typename  RBTree<K, K, SetKeyofT>::const_iterator  const_iterator;iterator begin(){//但是这里有一个编译错误return _t.begin();}iterator end() {return _t.end();}pair<iterator, bool> insert(const K& key){return _t.Insert(key);}private:RBTree<K,K,SetKeyofT> _t;};void test_set() {set<int> s;int a[] = {4,1,7,88,5,2,6,4,7,8,2,3,0};for (auto e : a) {s.insert(e);}set<int>::iterator it= s.begin();while (it != s.end()) {cout << *it << " ";//*it=1;++it;}cout << endl;}
}

 

5.源码

源码在这里

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

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

相关文章

在海外如何进行应用商店的关键词优化

在海外如何进行应用商店的关键词优化

分析市场&#xff0c;了解我们的应用类别&#xff0c;将我们的应用与竞争对手的优点和缺点进行比较&#xff0c;找到市场上的空白或所谓未满足的需求&#xff0c;并思考如何填补。 1、应用商店关键词优化。 关键词优化的目的是找到最相关的关键词 &#xff0c;并测试应用元数据…
阅读更多...
[保研/考研机试] KY26 10进制 VS 2进制 清华大学复试上机题 C++实现

[保研/考研机试] KY26 10进制 VS 2进制 清华大学复试上机题 C++实现

题目链接&#xff1a; 10进制 VS 2进制http://www.nowcoder.com/share/jump/437195121691738172415 描述 对于一个十进制数A&#xff0c;将A转换为二进制数&#xff0c;然后按位逆序排列&#xff0c;再转换为十进制数B&#xff0c;我们称B为A的二进制逆序数。 例如对于十进制…
阅读更多...
创作的1024天 分享月入5K的副业心得

创作的1024天 分享月入5K的副业心得

机缘 今天早上醒来打开电脑&#xff0c;和往常一样点开csdn&#xff0c;看见有一封私信&#xff0c;原来是系统通知&#xff0c;今天是我成为创作者的1024天&#xff0c;那就趁着这个机会&#xff0c;分享一下目前我月入5K的副业心得。我是一个普通人&#xff0c;最初想成为创…
阅读更多...
ARM 作业1

ARM 作业1

一、思维导图 二、 1. 2. .text 文本段 .globl _start 声明_start:mov r0,#0mov r1,#0fun:cmp r1,#100bhi stopadd r0,r0,r1add r1,r1,#1b fun stop:b stop .end
阅读更多...
【python办公自动化】PysimpleGUI中的popup弹窗中的按钮设置居中

【python办公自动化】PysimpleGUI中的popup弹窗中的按钮设置居中

PysimpleGUI中的popup弹窗中的按钮设置居中 背景问题解决背景 默认的popup弹窗中的OK按钮是在最下面偏左侧一些，有时需要将按钮放置居中 问题解决 首先找到pysimplegui源代码文件中popup的部分 然后定位到19388行，源文件内容如下 关于popup弹窗OK按钮的设置，将pad属性…
阅读更多...
《合成孔径雷达成像算法与实现》Figure3.10

《合成孔径雷达成像算法与实现》Figure3.10

代码复现如下&#xff1a; clc clear close all% 参数设置 TBP 100; % 时间带宽积 T 7.2e-6; % 脉冲持续时间 t_0 1e-6; % 脉冲回波时延% 参数计算 B TBP/T; …
阅读更多...
STM32 cubemx CAN

STM32 cubemx CAN

接收用到的结构体如下&#xff1a;CAN概念&#xff1a; 全称Controller Area Network&#xff0c;是一种半双工&#xff0c;异步通讯。 物理层&#xff1a; 闭环&#xff1a;允许总线最长40m&#xff0c;最高速1Mbps&#xff0c;规定总线两端各有一个120Ω电阻&#xff0c;闭环…
阅读更多...
马上七夕到了，用各种编程语言实现10种浪漫表白方式

马上七夕到了，用各种编程语言实现10种浪漫表白方式

目录 1. 直接表白&#xff1a;2. 七夕节表白&#xff1a;3. 猜心游戏&#xff1a;4. 浪漫诗句&#xff1a;5. 爱的方程式&#xff1a;6. 爱心Python&#xff1a;7. 心形图案JavaScript 代码&#xff1a;8. 心形并显示表白信息HTML 页面&#xff1a;9. Java七夕快乐&#xff1a;…
阅读更多...
Jenkins改造—nginx配置鉴权

Jenkins改造—nginx配置鉴权

先kill掉8082的端口进程 netstat -natp | grep 8082 kill 10256 1、下载nginx nginx安装 EPEL 仓库中有 Nginx 的安装包。如果你还没有安装过 EPEL&#xff0c;可以通过运行下面的命令来完成安装 sudo yum install epel-release 输入以下命令来安装 Nginx sudo yum inst…
阅读更多...
【实战】十一、看板页面及任务组页面开发（二） —— React17+React Hook+TS4 最佳实践，仿 Jira 企业级项目（二十四）

【实战】十一、看板页面及任务组页面开发（二） —— React17+React Hook+TS4 最佳实践，仿 Jira 企业级项目（二十四）

文章目录 一、项目起航&#xff1a;项目初始化与配置二、React 与 Hook 应用&#xff1a;实现项目列表三、TS 应用&#xff1a;JS神助攻 - 强类型四、JWT、用户认证与异步请求五、CSS 其实很简单 - 用 CSS-in-JS 添加样式六、用户体验优化 - 加载中和错误状态处理七、Hook&…
阅读更多...
【C++】STL---list

【C++】STL---list

STL---list 一、list 的介绍二、list 的模拟实现1. list 节点类2. list 迭代器类&#xff08;1&#xff09;前置&#xff08;2&#xff09;后置&#xff08;3&#xff09;前置- -、后置- -&#xff08;4&#xff09;! 和 运算符重载&#xff08;5&#xff09;* 解引用重载 和 …
阅读更多...
科大讯飞星火模型申请与chatgpt 3.5模型以及new bing的对比

科大讯飞星火模型申请与chatgpt 3.5模型以及new bing的对比

科大讯飞星火模型 申请科大讯飞星火认知大模型账号科大讯飞星火认知大模型使用1.界面介绍2. 在编程能力上与chatgpt 3.5对比科大讯飞星火模型chatgpt 3.5模型 3. 在图片生成能力上与new bing对比 总结 申请科大讯飞星火认知大模型账号 注册网址&#xff1a; 科大讯飞星火认知大…
阅读更多...
CW12B-3A-RCWW12B-6A-RCW12B-10A-RCWW12B-20A-RCWW12B-30A-RCWW12B-40A-R导轨式滤波器

CW12B-3A-RCWW12B-6A-RCW12B-10A-RCWW12B-20A-RCWW12B-30A-RCWW12B-40A-R导轨式滤波器

CW4L2-3A-R1 CW4L2-6A-R1 CW4L2-10A-R1 CW4L2-20A-R1 CW4L2-30A-R1导轨式滤波器 CW12B-3A-R CWW12B-6A-R CW12B-10A-R CWW12B-20A-R CWW12B-30A-R CWW12B-40A-R导轨式滤波器 CW12C-3A-R CWW12C-6A-R CWW12C-10A-R CW12C-20A-R CW12C-30A-R导轨式滤波器 CW4L2-3A-R…
阅读更多...
步入React正殿 - State进阶

步入React正殿 - State进阶

目录 扩展学习资料 State进阶知识点 状态更新扩展 shouldComponentUpdate PureComponent 为何使用不变数据【保证数据引用不会出错】 单一数据源 /src/App.js /src/components/listItem.jsx 状态提升 /src/components/navbar.jsx /src/components/listPage.jsx src/A…
阅读更多...
reeds_sheep运动规划算法Python源码分析

reeds_sheep运动规划算法Python源码分析

本文用于记录Python版本zhm-real / PathPlanning运动规划库中reeds_sheep算法的源码分析 关于reeds sheep算法的原理介绍前文已经介绍过了&#xff0c;链接如下所示&#xff1a; 《Reeds-Shepp曲线学习笔记及相关思考》 《Reeds-Shepp曲线基础运动公式推导过程》 正文&#xff…
阅读更多...
防丢器Airtag国产版

防丢器Airtag国产版

Airtag是什么&#xff1f; AirTag是苹果公司设计的一款定位神奇&#xff0c;它通过一款纽扣电池进行供电&#xff0c;即可实现长达1-2年的关键物品的定位、查找的功能。 按照苹果公司自己的话说—— 您“丢三落四这门绝技&#xff0c;要‍失‍传‍了”。 AirTag 可帮你轻松追…
阅读更多...
阿里云与中国中医科学院合作，推动中医药行业数字化和智能化发展

阿里云与中国中医科学院合作，推动中医药行业数字化和智能化发展

据相关媒体消息&#xff0c;阿里云与中国中医科学院的合作旨在推动中医药行业的数字化和智能化发展。随着互联网的进步和相关政策的支持&#xff0c;中医药产业受到了国家的高度关注。这次合作将以“互联网 中医药”为载体&#xff0c;致力于推进中医药文化的传承和创新发展。…
阅读更多...
2023最新红盟云卡个人自动发卡系统源码 全开源

2023最新红盟云卡个人自动发卡系统源码 全开源

​ 简介&#xff1a; 2023最新红盟云卡个人自动发卡系统源码 全开源 该系统完全开源且无任何加密&#xff0c;可商业使用&#xff0c;并支持个人免签多个接口。 ​ 图片&#xff1a;
阅读更多...
总结，由于顺丰的问题，产生了电脑近期一个月死机问题集锦

总结，由于顺丰的问题，产生了电脑近期一个月死机问题集锦

由于我搬家&#xff0c;我妈搞顺丰发回家&#xff0c;但是没有检查有没有坏&#xff0c;并且我自己由于不可抗力因素&#xff0c;超过了索赔时间&#xff0c;反馈给顺丰客服&#xff0c;说超过了造成了无法索赔的情况&#xff0c;现在总结发生了损坏配件有几件&#xff0c;显卡…
阅读更多...
成集云 | 鼎捷ERP采购单同步钉钉 | 解决方案

成集云 | 鼎捷ERP采购单同步钉钉 | 解决方案

源系统成集云目标系统 方案介绍 鼎捷ERP&#xff08;Enterprise Resource Planning&#xff09;是一款综合性的企业管理软件&#xff0c;它包括了多个模块来管理企业的各个方面&#xff0c;其中之一就是采购订单模块。鼎捷ERP的采购订单模块可以帮助企业有效管理和控制采购过程…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023