C++·set与map容器(下)

        本节把红黑树封装到set与map容器中去主要就是迭代器的自增自减，封装的大部分内容都展示到最后代码中了

1. 红黑树的改造

        因为set容器只有关键码值，map容器中不仅要存关键码值，还要存关键码值对应的数据。但是红黑树只有一颗，我们如何让一颗树适配两种存储模式。

        答案就是给红黑树两个模板参数，无论是set还是map第一个模板参数都用来表示关键码值，第二个模板参数，如果是set就存关键码值，如果是map就存pair数据。红黑树节点就只给一个模板参数只用来存储数据，也就是树的第二个模板参数。

        如此修改就可以做到set和map同用一颗红黑树了。

        但是因为我们之前红黑树是按map的方案写的，也就是说，插入中对比key值大小从而判断向左还是向右走的逻辑我们都是用 ->_kv.first 的方式访问key值的，但是明显set没办法这么操作。

        因此我们再在set和map容器中添加一个仿函数，用来取节点的关键码值

                

        之后在树中比较关键码值就可以直接用这个KeyofT生成的仿函数来取关键码。

        那树的第一个模板参数的用途就是给搜索和删除，在查找节点时，我们只需要对比关键码值就可以了。

2. 红黑树的迭代器

        关于构建迭代器的思路，我们不在容器上构建迭代器，而是直接在容器的底层，也就是红黑树中构建底层的迭代器，容器的迭代器就封装底层就好了。

        我们将迭代器的框架构建好，并在红黑树中实现好begin和end。这个end可以直接给空指针，因为树结束的下一个节点就是空指针。begin就是中序的第一个，也就是最左节点。

        下一步，我们将begin和end再封装进set和map容器中去。

        然后我们该实现迭代器的自增和自减了

2.1 operator++()

        迭代器的下一位就是中序遍历的下一位，中序遍历的顺序是 左-中-右 那么此时给到中节点了，下面分为两种情况：右树存在或右树不存在。

        当右树存在时右子树的最左节点就是中序的下一位。

        当右树不存在时，说明以该节点为根的子树已经访问完了，然后回到父亲。那如何判断父节点是否也访问完了，就需要看父节点与该节点是不是在同侧，或者说如果该节点是父节点的右孩子，说明父节点也访问完了，只有该节点是父节点的左孩子时说明父节点还未访问。如果父节点为空，说明整棵树已经遍历完了。

                ​​​​​​​        ​​​​​​​        

2.2 operator--()

        自减的逻辑与自增完全相反，或者说自减的遍历顺序是 右-中-左。

        但是我们这里要给end()迭代器做一下特殊处理，因为end()迭代器的上一位在逻辑上是中序遍历的最后一位，但是我们的end()迭代器给的是个空指针，它无法像其他正常节点那样操作。我们的特殊操作就是判断当下的迭代器是否是end()，如果是就直接来到中序遍历的最后一位，也就是最右节点。

                                

        但是这么做特殊处理也有弊端，就是当_root被旋转改变了之后迭代器就失效了。因此在库中，root上面还有一个head节点用来维护树，其中存储了root节点，最左节点和最右节点的信息，这样就不会出现迭代器失效的问题了，同时end()迭代器可以直接给head节点而不用给空了，并且每次找最左节点和最右节点时也非常方便。

        

3. 完整代码

RBTree.h

//节点的颜色
enum color{RED,BLACK};
//红黑树节点的定义
template<class T>
struct RBTNode
{RBTNode(const T& data, color color = RED): _data(data), _left(nullptr), _right(nullptr), _parent(nullptr), _col(color) {}T _data;RBTNode<T>* _left;RBTNode<T>* _right;RBTNode<T>* _parent;	color _col;	//节点颜色
};//红黑树的迭代器
template<class T, class Ref, class Ptr>
struct RBTIterator
{typedef RBTNode<T> Node;typedef RBTIterator<T, Ref, Ptr> Self;Node* _node;Node* _root;//构造RBTIterator(Node* node, Node* root):_node(node),_root(root){}Self& operator++(){if (_node->_right){//右不为空，右子树最左节点就是中序下一个Node* leftmost = _node->_right;while(leftmost->_left){leftmost = leftmost->_left;}_node = leftmost;}else{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 == nullptr)//end(){Node* rightmost = _root;while (rightmost && rightmost->_right){rightmost = rightmost->_right;}_node = rightmost;}else if (_node->_left){//左不为空，左子树最后一个节点就是上一个Node* rightmost = _node->_left;while (rightmost->_right){rightmost = rightmost->_right;}_node = rightmost;}else{//左树为空，同侧父节点遍历完了Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_left){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!=(const Self& s){return _node != s._node;}bool operator==(const Self& s){return _node == s._node;}
};template<class K, class T, class KeyOfT >
class RBTree
{typedef RBTNode<T> Node;public:typedef RBTIterator<T,T&,T*> Iterator;typedef RBTIterator<T, const T&, const T*> Const_Iterator;Iterator Begin(){Node* leftmost = _root;while (leftmost && leftmost->_left){leftmost = leftmost->_left;}return Iterator(leftmost, _root);}Iterator End(){return Iterator(nullptr, _root);}Const_Iterator Begin() const{Node* leftmost = _root;while (leftmost && leftmost->_left){leftmost = leftmost->_left;}return Const_Iterator(leftmost, _root);}Const_Iterator End() const{return Const_Iterator(nullptr, _root);}//构造RBTree() = default;//拷贝构造RBTree(const RBTree<K, T, KeyOfT>& t){_root = Copy(t._root);}//赋值运算符重载void operator=(const RBTree<K, T, KeyOfT>& t){RBTree<K, T> new_t(t);std::swap(new_t._root, _root);}//析构~RBTree(){Destroy(_root);_root = nullptr;}void Destroy(Node* root){if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;}Node* Copy(const Node* root){if (root == nullptr)return nullptr;Node* newnode = new Node(root->kv);newnode->_left = Copy(root->_left);newnode->_right = Copy(root->_right);return newnode;}//插入pair<Iterator,bool> Insert(const T& data);//搜索Iterator Find(const K& key);//中序遍历void InOrder(){_InOrder(_root);cout << endl;}//树的高度int Height(){return _Height(_root);}//统计节点总个数(插入时可能会有重复数据)int Size(){return _Size(_root);}//判断黑节点是否符合规则bool IsBalance(){if (_root == nullptr)return true;if (_root->_col == RED)return false;int refNum = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK){++refNum;}cur = cur->_left;}return Check(_root, 0, refNum);}private:bool Check(Node* root, int blackNum, const int refNum){if (root == nullptr){cout << blackNum << endl;if (refNum != blackNum){cout << "存在黑色节点的数量不相等的路径" << endl;return false;}return true;}if (root->_col == RED && root->_parent->_col == RED){cout << root->_kv.first << "存在连续的红色节点" << endl;return false;}if (root->_col == BLACK){blackNum++;}return Check(root->_left, blackNum, refNum) && Check(root->_right, blackNum, refNum);}//左单旋void RotateL(Node* parent);//右单旋void RotateR(Node* parent);//中序遍历(子函数)void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}//树的高度int _Height(Node* root){if (root == nullptr)return 0;int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}//统计节点总个数(插入时可能会有重复数据)int _Size(Node* root){return root == nullptr ? 0 : _Size(root->_left) + _Size(root->_right) + 1;}private:Node* _root = nullptr;
};//插入
template<class K, class T, class KeyOfT>
pair<typename RBTree<K, T, KeyOfT>::Iterator,bool> RBTree<K, T, KeyOfT>::Insert(const T& data)
{//链表为空特殊处理if (_root == nullptr){_root = new Node(data, BLACK);return make_pair(Iterator(_root, _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;}elsereturn make_pair(Iterator(cur, _root), false);}//需要插入一个新的红色节点cur = new Node(data);Node* newnode = cur;if (kot(cur->_data) < kot(parent->_data)){parent->_left = cur;cur->_parent = parent;}else{parent->_right = cur;cur->_parent = parent;}//判断是否需要对树进行调整while (parent && parent->_col==RED)//如果父节点颜色为红需要调整{Node* grandparent = parent->_parent;if (parent == grandparent->_left)	//叔叔在右{Node* uncle = grandparent->_right;if (uncle && uncle->_col == RED)	//当叔叔存在且为红时{parent->_col = uncle->_col = BLACK;grandparent->_col = RED;cur = grandparent;parent = grandparent->_parent;}else	//叔叔为黑或不存在{if (cur == parent->_left)//三节点同在左，右单旋{RotateR(grandparent);parent->_col = BLACK;grandparent->_col = RED;}else	//p节点在g左，cue节点在p右，左右双旋{RotateL(parent);RotateR(grandparent);cur->_col = BLACK;grandparent->_col = RED;	}break;}}else	//叔叔在左{Node* uncle = grandparent->_left;if (uncle && uncle->_col == RED)	//当叔叔存在且为红时{parent->_col = uncle->_col = BLACK;grandparent->_col = RED;cur = grandparent;parent = grandparent->_parent;}else	//叔叔为黑或不存在{if (cur == parent->_right)//三节点同在右，左单旋{RotateL(grandparent);parent->_col = BLACK;grandparent->_col = RED;}else	//p节点在g右，cue节点在p左，右左双旋{RotateR(parent);RotateL(grandparent);cur->_col = BLACK;grandparent->_col = RED;}break;}}}_root->_col = BLACK;return make_pair(Iterator(newnode, _root), true);
}//搜索
template<class K, class T, class KeyOfT>
typename RBTree<K, T, KeyOfT>::Iterator RBTree<K, T, KeyOfT>::Find(const K& key)
{KeyOfT kot;Node* cur = _root;while (cur){if (kot(cur->_data) < key){cur = cur->_right;}else if (kot(cur->_data) > key){cur = cur->_left;}else{return Iterator(cur,_root);}}return End();
}//左单旋
template<class K, class T, class KeyOfT>
void RBTree<K, T, KeyOfT>::RotateL(Node* parent)
{Node* subR = parent->_right;Node* subRL = parent->_right->_left;//修改向下链接内容parent->_right = subRL;subR->_left = parent;//修改向上链接内容subR->_parent = parent->_parent;parent->_parent = subR;if (subRL)//防止该树点为空{subRL->_parent = parent;}//parent的parent向下链接Node* parentParent = subR->_parent;if (parentParent == nullptr)//整棵树的根{_root = subR;}else{if (parent == parentParent->_right){parentParent->_right = subR;}else{parentParent->_left = subR;}}
}//右单旋
template<class K, class V, class KeyOfT>
void RBTree<K, V, KeyOfT>::RotateR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;//修改向下链接内容parent->_left = subLR;subL->_right = parent;//修改向上链接属性subL->_parent = parent->_parent;parent->_parent = subL;if (subLR){subLR->_parent = parent;}//修改parentParentNode* parentParent = subL->_parent;if (parentParent == nullptr){_root = subL;}else{if (parent == parentParent->_right){parentParent->_right = subL;}else{parentParent->_left = subL;}}
}

Myset.h

#include"RBTree.h"namespace atl
{template <class K>class set{struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:typedef typename RBTree<K, K, SetKeyOfT>::Iterator iterator;typedef typename RBTree<K, K, SetKeyOfT>::Const_Iterator cosnt_iterator;iterator begin(){return _t.Begin();}iterator end(){return _t.End();}cosnt_iterator begin()const{return _t.Begin();}cosnt_iterator end()const{return _t.End();}pair<iterator, bool> insert(const K& key){return _t.Insert(key);}iterator find(const K& key){return _t.Find(key);}private:RBTree<K, K, SetKeyOfT> _t;};}

Mymap.h

#include"RBTree.h"namespace atl
{template <class K,class V>class map{struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};public: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();}const_iterator begin()const{return _t.Begin();}const_iterator end()const{return _t.End();}pair<iterator,bool> insert(const pair<K, V>& kv){return _t.Insert(kv);}iterator find(const K& key){return _t.Find(key);}V& operator[](const K& key){pair<iterator, bool> ret = insert(make_pair(key, V()));return ret.first->second;}private:RBTree<K, pair<const K,V>, MapKeyOfT> _t;};}

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

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

相关文章

【轨物方案】码头卸船机在线监测物联网解决方案

【轨物方案】码头卸船机在线监测物联网解决方案

卸船机是利用连续输送机械制成能提升散粒物料的机头&#xff0c;或兼有自行取料能力&#xff0c;或配以取料、喂料装置&#xff0c;将散粒物料连续不断地提出船舱&#xff0c;然后卸载到臂架或机架并能运至岸边运输的地方送机系统去的专用机械。每年都要安排人员定期去现场巡检…
阅读更多...
搭建DNS正向解析，反向解析+搭建DNS主从架构+搭建DNS多区域+时间同步

搭建DNS正向解析，反向解析+搭建DNS主从架构+搭建DNS多区域+时间同步

主要在局域网中配置&#xff0c;不存在外网 正向解析&#xff1a;域名解析为IP named.conf 解决权限 named.rfc1912.zones 解决解析方式 环境准备&#xff1a;三台机器都做下面的操作 基础配置&#xff1a;网络配置&#xff0c;关闭安全架构&#xff0c;关闭防火墙&#x…
阅读更多...
3D模型可视化引擎HOOPS Luminate功能一览：实时渲染（二）

3D模型可视化引擎HOOPS Luminate功能一览：实时渲染（二）

HOOPS Luminate是一款专为图像可视化设计的C编程工具包。它通过一个统一的集成API&#xff0c;全面覆盖了实时2D、实时3D以及照片级逼真渲染的图形功能。在处理大型数据组件的显示方面&#xff0c;HOOPS Luminate展现出了卓越的性能&#xff0c;并且具备高度的可定制性和灵活性…
阅读更多...
一文带你读懂TCP

一文带你读懂TCP

文章目录 1 TCP协议1.1 TCP 基础1.1.1 TCP 特性1.2.2 TCP连接数 1.2 TCP 头1.2.1 TCP 头格式1.2.2 MTU&#xff0c;MSS&#xff0c;分片传输 1.3 TCP 连接三路握手1.4 TCP 断开四次挥手1.5 SYN攻击和防范1.6 重传机制1.6.1 超时重传1.6.2 快速重传1.6.3 SACK 1.7 滑动窗口1.8 流…
阅读更多...
VScode使用Github Copilot插件时出现read ECONNREST问题的解决方法

VScode使用Github Copilot插件时出现read ECONNREST问题的解决方法

文章目录 read ECONNREST查看是否仍是 Copilot 会员查看控制台输出网络连接问题浏览器设置问题笔者的话 read ECONNREST 最近使用 Copilot 时一直出现 read ECONNREST 问题&#xff0c;这个表示连接被对方重置了&#xff0c;就是说在读取数据时连接被关闭。 我首先怀疑是不是…
阅读更多...
springboo 整合 redis

springboo 整合 redis

springBoot 整合 redis starter启动依赖。—包含自动装配类—完成相应的装配功能。 引入依赖 <!--引入了redis整合springboot 的依赖--> <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-data-redis&…
阅读更多...
PostgreSQL的pg-collector工具

PostgreSQL的pg-collector工具

PostgreSQL的pg-collector工具 pg-collector 是一个用于 PostgreSQL 数据库的监控和数据收集工具。它主要用于收集 PostgreSQL 实例的性能指标、查询统计和日志信息&#xff0c;以便进行数据库性能分析和故障排查。通过收集这些数据&#xff0c;管理员可以更好地了解数据库的运…
阅读更多...
盘点2024年网上很火的4个语音识别转文字工具。

盘点2024年网上很火的4个语音识别转文字工具。

语音识别转文字是一项非常实用的技术&#xff0c;可以帮助我们在会议记录中省去手动记录&#xff0c;在采访中迅速得到文字稿&#xff0c;在学习中快速生成课堂笔...运用十分广泛。但是很多人不知道要怎么转换&#xff0c;在这里我便给大家介绍几款效率非常高的语音转文字的工具…
阅读更多...
python 裁剪图片

python 裁剪图片

情况&#xff1a; 有时候看视频&#xff0c;看到一个漂亮的妹子&#xff0c;按下 Alt PrintScreen 进行截图之后&#xff0c;会把整个屏幕都截图。 需要适当剪裁一下。 每次打开 PS &#xff0c; 也太慢了。 所以写个代码&#xff0c; 快速处理。 效果对比&#xff1a; 原始…
阅读更多...
轨道式智能巡检机器人，助力综合管廊安全运维

轨道式智能巡检机器人，助力综合管廊安全运维

1 引言 当前城市综合管廊建设已经成为世界范围内的发展趋势&#xff0c;2017年5月住建部、发改委联合发布《全国城市市政基础设施建设“十三五”规划》&#xff0c;截至2017年4月底国内地下综合管廊试点项目已开工建设687 km&#xff0c;建成廊体260 km&#xff0c;完成投资40…
阅读更多...
MSSQL注入前置知识

MSSQL注入前置知识

简述 Microsoft SQL server也叫SQL server / MSSQL&#xff0c;由微软推出的关系型数据库&#xff0c;默认端口1433 常见搭配C# / .net IISmssql mssql的数据库文件 数据文件&#xff08;.mdf&#xff09;&#xff1a;主要的数据文件&#xff0c;包含数据表中的数据和对象信息…
阅读更多...
使用update-alternatives管理GCC版本

使用update-alternatives管理GCC版本

使用update-alternatives管理GCC版本 简介操作过程 简介 当操作系统中存在多个版本的GCC时&#xff0c;可以使用使用update-alternatives管理默认使用的编译器版本。 本文使用gcc-9和gcc-11做演示&#xff0c;操作系统为ubuntu-20.04 操作过程 ①使用以下命令确认gcc已正确…
阅读更多...
Ubuntu22.04重装系统+基础配置

Ubuntu22.04重装系统+基础配置

重装系统 note&#xff1a;备份数据&#xff0c;重装系统后home下的文件会丢失&#xff0c;所以先备份一下home的数据到其他的盘/mnt/下里。记住之前系统的DNS&#xff0c;IP和掩码。 先在Ubuntu官网下载22.04桌面版&#xff08;种子链接要用迅雷下载&#xff09;。但是版本还…
阅读更多...
橙单前端项目下载编译遇到的问题与解决

橙单前端项目下载编译遇到的问题与解决

今天下载orange-admin前端项目&#xff0c;不过下载下来运行也出现一些问题。 1、运行出现下面一堆错误&#xff0c;如下&#xff1a; 2、对于下面这个错误 error Expected linebreaks to be LF but found CRLF linebreak-style 这就是eslint的报错了&#xff0c;可能是原作者…
阅读更多...
隆尧县“隆品佳尧”区域公用品牌发布推介会暨地标之都七月选品会成功举办

隆尧县“隆品佳尧”区域公用品牌发布推介会暨地标之都七月选品会成功举办

在国家乡村振兴战略与农业现代化建设的大背景下&#xff0c;隆尧县凭借其得天独厚的地理优势和丰富的自然资源&#xff0c;正在成为区域经济与品牌建设的一颗新星。为了进一步推动隆尧县的农业发展和乡村建设&#xff0c;由隆尧县商务局指导、隆尧县电子商务公共服务中心主办的…
阅读更多...
【leetcode 详解】生成特殊数字的最少操作【中等】(C++思路精析)

【leetcode 详解】生成特殊数字的最少操作【中等】(C++思路精析)

题目见下&#xff1a; 测试数据: 解题思路笔记&#xff1a; 最初拿到这道题是很蒙的&#xff0c;联想不到什么数据结构的模型&#xff08;肯定是笔者积累太少了&#xff09;&#xff0c;甚至惯性地想怎么实现“删除数字”的操作&#xff1a;在原字符串中抽出一个字符然后将剩…
阅读更多...
南非云手机：助力企业在南非的商业活动

南非云手机：助力企业在南非的商业活动

中国企业在南非的商业活动涵盖了多个领域&#xff0c;包括基础设施建设、采矿业、制造业、能源、电信、金融服务等。随着中国企业在南非的不断扩展&#xff0c;如何高效管理业务和保护数据安全成为了重要课题&#xff0c;而南非云手机为企业提供了强大的技术支持和便利的管理工…
阅读更多...
神经网络与注意力机制的权重学习对比：公式探索

神经网络与注意力机制的权重学习对比：公式探索

神经网络与注意力机制的权重学习对比&#xff1a;公式探索 注意力机制与神经网络权重学习的核心差异 在探讨神经网络与注意力机制的权重学习时&#xff0c;一个核心差异在于它们如何处理输入数据的权重。神经网络通常通过反向传播算法学习权重&#xff0c;而注意力机制则通过学…
阅读更多...
使用flutter做圆形进度条 (桌面端)

使用flutter做圆形进度条 (桌面端)

前言 最近收到一个需求&#xff0c;需要使用flutter 来做一个圆形进度条&#xff0c;这可难倒我了&#xff0c;毕竟我是做前端的&#xff0c;flutter 之前接触的也少&#xff0c;但没办法&#xff0c;既然需求有了&#xff0c;也得硬着头皮上了&#xff0c;先来看看做的效果。…
阅读更多...
C语言百分号打印器

C语言百分号打印器

目录 开头程序程序的流程图程序输入与输出的效果例1输入输出 例2输入输出 例3输入输出 结尾 开头 大家好&#xff0c;我叫这是我58。今天&#xff0c;我们来看一下我用C语言编译的百分号打印器和与之相关的一些东西。 程序 #define _CRT_SECURE_NO_WARNINGS 1 #include <…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023