[C++][数据结构]用红黑树封装map和set(包含红黑树迭代器)

2024-05-09 21:36

本文主要是介绍[C++][数据结构]用红黑树封装map和set(包含红黑树迭代器),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

引入

官方文档中,我们可以看到map和set都是用一个红黑树来实现的,那set不给出value、map给出了value,这两个不一样,是如何用一个红黑树来实现的呢?

基本结构

节点的定义

代码中,将pair换成了data

template<class T>
struct RBTreeNode`在这里插入代码片`
{RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;Colour _col;T _data;RBTreeNode(const T& data):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED){}
};

树的修改

然后将树的模板参数修改了一下

// KeyOfT:lambda/仿函数 取出T对象中的key
template<class K, class T, class KeyOfT>
  • K是key(用于查找)
  • T是data
  • KeyOfT是取出T中key的lambda(后面在比较key的时候会用到)

那么set和map的实现其实这样的

 set->RBTree<K, K, SetKeyOfT>map->RBTree<K, pair<K, V>, MapKeyOfT>

所以就是通过第二个参数来控制给出的是set还是map了

迭代器

源码给出的迭代器:
在这里插入图片描述本质上还是根据给出的data是pair<K, V>还是value来判断生成哪种指针

先看一些老生常谈的内容吧
operator* -> != ==

template<class T>
struct RBTreeIterator
{using Node = RBTreeNode<T>;using Self = RBTreeIterator<T>;Node* _node;RBTreeIterator(Node* node):_node(node){}T& operator*(){return _node->_data;}T* operator->(){return &_node->_data;}bool operator!=(const Self& s){return _node != s._node;}bool operato == (const Self & s){return _node == s._node;}
};

需要说明的是节点的++和–

++

并不是对于data的value++
而是该节点的后继节点

  • 如果节点有右子树,则节点的后继节点是其右子树中最左边的节点。
  • 如果节点没有右子树,那么就向上找父节点,直到找到一个节点,它是其父节点的左子节点,这个父节点就是要找的前驱节点。
Self& operator++(){if (_node->_right){// 右子树的中序第一个(最左节点)Node* subLeft = _node->_right;while (subLeft->_left){subLeft = subLeft->_left;}_node = subLeft;}else{// 祖先里面孩子是父亲左的那个Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}

–就是该节点的前驱节点

  • 如果节点有左子树,则节点的前驱节点是其左子树中最右边的节点。
  • 如果节点没有左子树,那么就向上找父节点,直到找到一个节点,它是其父节点的右子节点,这个父节点就是要找的前驱节点。
    (找的方法一样,只不过左右换了一下)

比较

我们不能用data直接进行比较,因为set里data是value,map里data是pair。
所以,我们需要将data中的key取出来,再进行比较
(可以用仿函数、lambda)
我们用lambda(当然,也会给出仿函数的代码)

lambda

代码如下

// 使用 Lambda 表达式作为键值提取器
auto keyOfT = [](const T& obj) { return obj.key; };// 使用模板并传入 Lambda 表达式作为参数
RBTree<int, MyClass, decltype(keyOfT)> tree;

那么在调用的时候就直接在类里写

KeyOfT kot;
if(kot(node->_data) < kot(data)
{}

operator()

struct KeyOfT {template <typename T>const K& operator()(const T& obj) const {return obj.key;}
};

结语

那么对于map和set的介绍到这里就结束了,希望你有所收获,我们下次见~~

这篇关于[C++][数据结构]用红黑树封装map和set(包含红黑树迭代器)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/974559

相关文章

C++如何通过Qt反射机制实现数据类序列化

《C++如何通过Qt反射机制实现数据类序列化》在C++工程中经常需要使用数据类,并对数据类进行存储、打印、调试等操作,所以本文就来聊聊C++如何通过Qt反射机制实现数据类序列化吧... 目录设计预期设计思路代码实现使用方法在 C++ 工程中经常需要使用数据类,并对数据类进行存储、打印、调试等操作。由于数据类

Linux下如何使用C++获取硬件信息

《Linux下如何使用C++获取硬件信息》这篇文章主要为大家详细介绍了如何使用C++实现获取CPU,主板,磁盘,BIOS信息等硬件信息,文中的示例代码讲解详细,感兴趣的小伙伴可以了解下... 目录方法获取CPU信息:读取"/proc/cpuinfo"文件获取磁盘信息:读取"/proc/diskstats"文

C++使用printf语句实现进制转换的示例代码

《C++使用printf语句实现进制转换的示例代码》在C语言中,printf函数可以直接实现部分进制转换功能,通过格式说明符(formatspecifier)快速输出不同进制的数值,下面给大家分享C+... 目录一、printf 原生支持的进制转换1. 十进制、八进制、十六进制转换2. 显示进制前缀3. 指

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a

C++ vector的常见用法超详细讲解

《C++vector的常见用法超详细讲解》:本文主要介绍C++vector的常见用法,包括C++中vector容器的定义、初始化方法、访问元素、常用函数及其时间复杂度,通过代码介绍的非常详细,... 目录1、vector的定义2、vector常用初始化方法1、使编程用花括号直接赋值2、使用圆括号赋值3、ve

MySQL中FIND_IN_SET函数与INSTR函数用法解析

《MySQL中FIND_IN_SET函数与INSTR函数用法解析》:本文主要介绍MySQL中FIND_IN_SET函数与INSTR函数用法解析,本文通过实例代码给大家介绍的非常详细,感兴趣的朋友一... 目录一、功能定义与语法1、FIND_IN_SET函数2、INSTR函数二、本质区别对比三、实际场景案例分

Python 迭代器和生成器概念及场景分析

《Python迭代器和生成器概念及场景分析》yield是Python中实现惰性计算和协程的核心工具,结合send()、throw()、close()等方法,能够构建高效、灵活的数据流和控制流模型,这... 目录迭代器的介绍自定义迭代器省略的迭代器生产器的介绍yield的普通用法yield的高级用法yidle

鸿蒙中Axios数据请求的封装和配置方法

《鸿蒙中Axios数据请求的封装和配置方法》:本文主要介绍鸿蒙中Axios数据请求的封装和配置方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1.配置权限 应用级权限和系统级权限2.配置网络请求的代码3.下载在Entry中 下载AxIOS4.封装Htt

如何高效移除C++关联容器中的元素

《如何高效移除C++关联容器中的元素》关联容器和顺序容器有着很大不同,关联容器中的元素是按照关键字来保存和访问的,而顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的,本文介绍了如何高效移除C+... 目录一、简介二、移除给定位置的元素三、移除与特定键值等价的元素四、移除满足特android定条件的元

Python获取C++中返回的char*字段的两种思路

《Python获取C++中返回的char*字段的两种思路》有时候需要获取C++函数中返回来的不定长的char*字符串,本文小编为大家找到了两种解决问题的思路,感兴趣的小伙伴可以跟随小编一起学习一下... 有时候需要获取C++函数中返回来的不定长的char*字符串,目前我找到两种解决问题的思路,具体实现如下: