【C++进阶】RBTree封装map与set

1.红黑树的迭代器

1.1 begin()

begin()就是红黑树的开头，那么对于红黑树来说按照中序序列是该树的最左节点。

	Iterator Begin(){Node* leftMin = _root;while (leftMin->_left){leftMin = leftMin->_left;}return Iterator(leftMin);}

1.2 end()

begin()就是红黑树的结尾的下一个，那么对于红黑树来说按照中序序列应该是该树的最右节点的下一个位置，但下一个位置是nullptr（这里库中源码写的是使用了一个哨兵位的头节点作为End,我们可以简单来写，以nullptr作为End）。

Iterator End()
{return Iterator(nullptr);
}

1.3 operator++

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

2.改造红黑树

因为我们之前写的红黑树是不能同时满足set和map的使用，如果需要还必须再写一份来满足另一个，那么我们可不可以把红黑树改造成能同时满足set和map呢？

答案是可以的，我们实质上是偷了个懒，把写另一个的事情交给编译器去做，这也是能体现面向对象中封装的特性的！

#pragma once
#include<vector>enum Color
{RED,BLACK
};
template<class T>
struct RBTreeNode
{RBTreeNode<T>* _left;	//该节点的左孩子RBTreeNode<T>* _right;	//该节点的右孩子RBTreeNode<T>* _parent;	//该节点的双亲Color _col;T _data;	//存放Key或者pairRBTreeNode(const T& data)	//该节点初始化:_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED){}
};template<class T, class Ref, class Ptr>
struct __RBTreeIterator
{typedef RBTreeNode<T> Node;typedef __RBTreeIterator<T, Ref, Ptr> Self;Node* _node;__RBTreeIterator(Node* node):_node(node){}Ref operator*() {return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!=(const Self& s){return _node != s._node;}Self& operator++(){//1.右不为空，下一个是右子树最左节点if (_node->_right){Node* leftMin = _node->_right;while (leftMin->_left){leftMin = leftMin->_left;}_node = leftMin;}//2.右为空，下一个倒着在祖先中找孩子是父亲的左的祖先节点else{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}
};template<class K, class T, class KeyOfT>
class RBTree
{typedef RBTreeNode<T> Node;
public:typedef __RBTreeIterator<T, T&, T*> Iterator;typedef __RBTreeIterator<T, const T&, const T*> ConstIterator;RBTree() = default;//t2(t1)RBTree(const RBTree<K, T, KeyOfT>& t){_root = Copy(t._root);}~RBTree(){Destroy(_root);_root = nullptr;}//t2 = t1RBTree<K, T, KeyOfT>& operator=(const RBTree<K, T, KeyOfT> t){swap(_root, t._root);return *this;}Iterator Begin(){Node* leftMin = _root;while (leftMin->_left){leftMin = leftMin->_left;}return Iterator(leftMin);}Iterator End(){return Iterator(nullptr);}ConstIterator Begin() const{Node* leftMin = _root;while (leftMin->_left){leftMin = leftMin->_left;}return ConstIterator(leftMin);}ConstIterator End() const{return ConstIterator(nullptr);}Iterator Find(const K& key){Node* cur = _root;while (cur){if (cur->_key < key){cur = cur->_right;}else if (cur->_key > key){cur = cur->_left;}else{return Iterator(cur);}}return End();}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;cur->_col = RED;	//新增节点给红色if (kot(parent->_data) < kot(data)){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//父亲节点是红色则需要调整//调整到根节点，根节点是黑色，此时也结束调整while (parent && parent->_col == RED){Node* grandfather = parent->_parent;//爷爷节点//关键看叔叔if (parent == grandfather->_left){Node* uncle = grandfather->_right;//叔叔存在且为红->变色即可if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;//继续往上调整cur = grandfather;parent = cur->_parent;}else //叔叔不存在/叔叔存在且为黑 -->旋转操作{if (cur == parent->_left){//      g//    p   u//  cRotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//      g//    p   u//      cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else{Node* uncle = grandfather->_left;//叔叔存在且为红->变色即可if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;//继续往上调整cur = grandfather;parent = cur->_parent;}else //叔叔不存在/叔叔存在且为黑 -->旋转操作{if (cur == parent->_right){//     g//   u   p //         cRotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//      g//    u   p//      cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;//无论是否调整到根节点都让根节点始终是黑色return make_pair(Iterator(newnode), true);}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)	//subLR有可能为空，不为空时才能调整subLR的父节点subLR->_parent = parent;subL->_right = parent;//parent不一定就是根节点，也可能是子树，所以要设置一个ppNode来标记parent的父节点Node* ppNode = parent->_parent;parent->_parent = subL;if (parent == _root){_root = subL;_root->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)	//subRL有可能为空，不为空时才能调整subRL的父节点subRL->_parent = parent;subR->_left = parent;//parent不一定就是根节点，也可能是子树，所以要设置一个ppNode来标记parent的父节点Node* ppNode = parent->_parent;parent->_parent = subR;if (parent == _root){_root = subR;_root->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subR;}else{ppNode->_right = subR;}subR->_parent = ppNode;}}void InOrder(){_InOrder(_root);cout << endl;}bool IsBalance(){//检查规则1if (_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:Node* Copy(Node* root){if (root == nullptr)return nullptr;Node* newroot = new Node(root->_data);newroot->_col = root->_col;newroot->_left = Copy(root->_left);if (newroot->_left)newroot->_left->_parent = newroot;newroot->_right = Copy(root->_right);if (newroot->_right)newroot->_right->_parent = newroot;return newroot;}void Destroy(Node* root){if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;root = nullptr;}bool Check(Node* root, int blackNum, const int refNum){if (root == nullptr){//检查规则4if (blackNum != refNum){cout << "存在黑色节点不相等的路径" << endl;return false;}return true;}//检查规则3if (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 _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}Node* _root = nullptr;//size_t size = 0;	//可以用来记录节点个数
};

3.set的模拟实现

set的底层为红黑树，因此只需在set内部封装一棵红黑树，即可将该容器实现出来。

#pragma oncenamespace bit
{template<class K>class set{struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:typedef typename RBTree<K, const K, SetKeyOfT>::Iterator iterator;typedef typename RBTree<K, const K, SetKeyOfT>::ConstIterator 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();}iterator find(const K& key){return _t.Find(key);}pair<iterator, bool> insert(const K& key){return _t.Insert(key);}private:RBTree<K, const K, SetKeyOfT> _t;};void PrintSet(const set<int>& s){for (auto e : s){cout << e << endl;}}void test_set(){set<int> s;s.insert(4);s.insert(2);s.insert(5);set<int>::iterator it = s.begin();while (it != s.end()){//*it += 5;cout << *it << " ";++it;}cout << endl;for (auto e : s){cout << e << endl;}PrintSet(s);}
}

4.map的模拟实现

map的底层结构就是红黑树，因此在map中直接封装一棵红黑树，然后将其接口包装下即可

#pragma oncenamespace bit
{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>::ConstIterator 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();}iterator find(const K& key){return _t.Find(key);}pair<iterator, bool> insert(const pair<K, V>& kv){return _t.Insert(kv);}V& operator[](const K& key){pair<iterator, bool> ret = _t.Insert(make_pair(key, V()));return ret.first->second;}private:RBTree<K, pair<const K, V>, MapKeyOfT> _t;};void test_map1(){map<string, int> m;m.insert({"苹果", 1});m.insert({ "香蕉", 2});m.insert({ "梨子",3});map<string, int>::iterator it = m.begin();while (it != m.end()){//it->first += 'x';it->second += 1;//cout << it.operator->()->first << ":" << it->second << endl;cout << it->first << ":" << it->second << endl;++it;}cout << endl;}void test_map2(){string arr[] = { "草莓", "香蕉", "梨子", "苹果", "梨子", "苹果", "香蕉",
"草莓", "苹果", "苹果", "梨子","梨子","草莓", "苹果","苹果" };map<string, int> countMap;for (auto& e : arr){countMap[e]++;}for (auto& kv : countMap){cout << kv.first << ":" << kv.second << endl;}cout << endl;}
}

5.test.cpp

#include<iostream>
using namespace std;#include"RBTree.h"
#include"Myset.h"
#include"Mymap.h"int main()
{bit::test_map1();bit::test_set();bit::test_map2();return 0;
}

 依次展开头文件就可正常使用set与map了。

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

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

相关文章

【启明智显分享】个位数价格工业HMI芯片：720P@60fps，配备2D加速

【启明智显分享】个位数价格工业HMI芯片：720P@60fps，配备2D加速

我们生活在一个“屏”的时代&#xff0c;工业自动化、智能生活的实现都离不开屏幕的帮助&#xff0c;而对于消费者而言&#xff0c;最大的痛点就是显示屏的画质&#xff0c;一个优质的人机交互界面影响着用户体验&#xff0c;流畅清晰的图像呈现与屏幕的分辨率、刷新率都息息相…
阅读更多...
VScode ssh远程连接代码开发XHR failed

VScode ssh远程连接代码开发XHR failed

一、问题描述 在vscode下载插件Remote-SSH远程连接进行代码开发时&#xff0c;提示 XHR failed 无法建立连接。 二、解决方案 1. 离线下载vscode-server 第一步&#xff1a;vscode菜单栏----帮助----关于----提交后面的一串数字字母即为vscode的 commit_id 第二步&#xff…
阅读更多...
uniapp地图导航

uniapp地图导航

我们只需要给图标加一个点击事件 我这里的数据都是动态的&#xff0c;想测试的朋友可以写固定值 然后跳转之后首先会调到选择软件导航 点击导航之后会显示使用哪个app 最后我们选择之后将会直接跳转到app进行导航
阅读更多...
Git基础指令（图文详解）

Git基础指令（图文详解）

目录 Git概述Git基础指令Linux系统操作指令 Git软件指令1.配置信息2.名称和邮箱3.初始化版本库4.向版本库中添加文件5.修改版本库文件6. 查看版本库文件历史 7.删除文件8.恢复历史文件 Git概述 Git基础指令 Linux系统操作指令 Git是一款免费、开源的分布式版本控制系统&…
阅读更多...
028、工具_Pipeline

028、工具_Pipeline

Redis客户端执行一条命令分为如下四个过程： 1）发送命令 2）命令排队 3）命令执行 4）返回结果 其中1）+4）称为Round Trip Time（RTT，往返时间）。 Pipeline（它能将一组Redis命令进 行组装，通过一次RTT传输给Redis，再将这组Redis命令的执行结果按顺序返回给客户端，图3-…
阅读更多...
早知 121私人导航升级新版本, 第一次使用原生dialog标签。

早知 121私人导航升级新版本, 第一次使用原生dialog标签。

早知121项目介绍说明 早知121 - 一个快速创建私人导航网站。 用途&#xff1a; 创建个人的工作导航&#xff0c;收集常用网址&#xff0c;可贡献给同事。创建个人垂直领域导航 优点&#xff1a; - 不需懂技术&#xff0c;不用维护服务器&#xff0c;维护私人导航收藏站。 网…
阅读更多...
express入门03增删改查

express入门03增删改查

目录 1 搭建服务器2 静态文件托管3 引入bootstrap4 引入jquery5 编写后端接口5.1 添加列表查询方法5.2 添加路由5.3 添加数据表格 总结 我们前两篇介绍了如何利用express搭建服务器&#xff0c;如何实现静态资源托管。那利用这两篇的知识点&#xff0c;我们就可以实现一个小功能…
阅读更多...
公司面试题总结（五）

公司面试题总结（五）

25.谈一谈箭头函数与普通函数的区别&#xff0c;箭头函数主要解决什么问题&#xff1f; 箭头函数与普通函数的区别&#xff1a; ⚫ 语法简洁性&#xff1a; ◼ 箭头函数使用>符号定义&#xff0c;省略了 function 关键字&#xff0c;使得语法更为紧凑。 ◼ 对于单行函…
阅读更多...
事件、方法实现 on_radioGreen_clicked ，on_chkBoxUnder_clicked，Qfont，QPalette

事件、方法实现 on_radioGreen_clicked ，on_chkBoxUnder_clicked，Qfont，QPalette

Vertical Layout 、Horizontal Layout 实验窗体自适应布局 接上篇界面布局&#xff0c; 实验checkBox、radioBox 的事件槽&#xff0c; 使用Qfont组件变更纯文本框QPlainTextEdit中字体的下划线、加粗、斜体效果 使用调色板组QPalette变更纯文本框QPlainTextEdit中文本颜色 UI…
阅读更多...
三、网络服务协议

三、网络服务协议

目录 一、FTP&#xff1a;文件传输协议 二、Telnet&#xff1a;远程登录协议 三、AAA认证 四、DHCP 五、DNS 六、PPP协议 七、ISIS协议 一、FTP&#xff1a;文件传输协议 C/S架构&#xff0c;现多用于企业内部的资料共享和网络设备的文件传输&#xff0c;企业内部搭建一…
阅读更多...
element table 点击某一行中按钮加载

element table 点击某一行中按钮加载

在Element UI中&#xff0c;实现表格&#xff08;element-table&#xff09;中的这种功能通常涉及到数据处理和状态管理。当你点击某一行的按钮时&#xff0c;其他行的按钮需要动态地切换为加载状态&#xff0c;这可以通过以下步骤实现&#xff1a; 1.表格组件&#xff1a;使用…
阅读更多...
手机流畅运行470亿参数大模型，上交大发布PowerInfer-2推理框架，性能提升29倍

手机流畅运行470亿参数大模型，上交大发布PowerInfer-2推理框架，性能提升29倍

苹果一出手&#xff0c;在手机等移动设备上部署大模型迅速成为行业焦点。 目前&#xff0c;移动设备上运行的模型相对较小&#xff08;苹果的是3B&#xff0c;谷歌的是2B&#xff09;&#xff0c;并且消耗大量内存&#xff0c;这在很大程度上限制了其应用场景。 即使是苹果&…
阅读更多...
【西瓜书】9.聚类

【西瓜书】9.聚类

聚类任务是无监督学习的一种用于分类等其他任务的前驱过程&#xff0c;作为数据清洗&#xff0c;基于聚类结果训练分类模型 1.聚类性能度量&#xff08;有效性指标&#xff09; 分类任务的性能度量有错误率、精度、准确率P、召回率R、F1度量(P-R的调和平均)、TPR、FPR、AUC回归…
阅读更多...
20240613解决飞凌的OK3588-C的核心板的USB3.0接口不读U盘的问题

20240613解决飞凌的OK3588-C的核心板的USB3.0接口不读U盘的问题

20240613解决飞凌的OK3588-C的核心板的USB3.0接口不读U盘的问题 2024/6/13 15:21 缘起&#xff0c;由于USB3.0的CC芯片在飞凌的OK3588-C的开发板的底板上&#xff0c;一切正常。 如果你单独使用核心板&#xff0c;很容易出现这个问题【省成本没有使用CC芯片】&#xff1a;不读U…
阅读更多...
LabVIEW开发CAN通讯协议

LabVIEW开发CAN通讯协议

在LabVIEW中开发CAN&#xff08;Controller Area Network&#xff09;通讯协议时&#xff0c;需要全面考虑硬件选择、驱动安装、通信配置、错误处理、数据解析和实时性等多个方面。本文详细介绍了在LabVIEW中实现CAN通讯时的关键点和最佳实践&#xff0c;确保系统的稳定性、可靠…
阅读更多...
JFrame.setDefaultLookAndFeelDecorated

JFrame.setDefaultLookAndFeelDecorated

在java Swing编程中，作为窗体，我们经常编写类继承JFrame,在main方法中进行加载，如下 有一种方法，不用继承JFrame也可以弹窗，代码如下 但是这个跟我们今天的setDefaultLookAndFeelDecorated有什么关系呢，这个设置，必须在new 对象前进行调用，才有装饰效果，如下 说白了…
阅读更多...
Java中Transactional在不同方法间的穿透性，rollbackFor参数含义

Java中Transactional在不同方法间的穿透性，rollbackFor参数含义

哈喽&#xff0c;大家好&#xff0c;我是木头左&#xff01; 在Java开发中&#xff0c;经常会遇到需要在一个事务中执行多个操作的场景。为了确保这些操作的原子性&#xff0c;可以使用Spring框架提供的Transactional注解来实现事务管理。然而&#xff0c;在实际开发过程中&…
阅读更多...
【Intel CVPR 2024】通过图像扩散模型生成高质量360度场景，只需要一个语言模型

【Intel CVPR 2024】通过图像扩散模型生成高质量360度场景，只需要一个语言模型

在当前人工智能取得突破性进展的时代&#xff0c;从单一输入图像生成全景场景仍是一项关键挑战。大多数现有方法都使用基于扩散的迭代或同步多视角内绘。然而&#xff0c;由于缺乏全局场景布局先验&#xff0c;导致输出结果存在重复对象&#xff08;如卧室中的多张床&#xff0…
阅读更多...
JVM性能优化案例：减少对象频繁创建

JVM性能优化案例：减少对象频繁创建

JVM性能优化案例&#xff1a;减少对象频繁创建 案例背景 某金融应用系统在处理大量并发交易时&#xff0c;响应时间过长&#xff0c;并且有时出现内存溢出&#xff08;OutOfMemoryError&#xff09;的问题。经过分析&#xff0c;发现问题主要出在频繁的对象创建和较差的内存管…
阅读更多...
如何降低pcdn的延迟？

如何降低pcdn的延迟？

要降低P2P CDN的延迟&#xff0c;可以采取以下操作&#xff1a; 一&#xff0e;优化网络连接&#xff1a; 1、使用有线网络连接替代无线连接&#xff0c;因为有线连接通常提供更稳定的数据传输。 2、升级家庭或企业路由器&#xff0c;选择性能更好的路由器以提高网络传输速度…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023