[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

相关文章

SpringBoot中封装Cors自动配置方式

《SpringBoot中封装Cors自动配置方式》:本文主要介绍SpringBoot中封装Cors自动配置方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录SpringBoot封装Cors自动配置背景实现步骤1. 创建 GlobalCorsProperties

C++ 中的 if-constexpr语法和作用

《C++中的if-constexpr语法和作用》if-constexpr语法是C++17引入的新语法特性,也被称为常量if表达式或静态if(staticif),:本文主要介绍C++中的if-c... 目录1 if-constexpr 语法1.1 基本语法1.2 扩展说明1.2.1 条件表达式1.2.2 fa

SpringBoot如何通过Map实现策略模式

《SpringBoot如何通过Map实现策略模式》策略模式是一种行为设计模式,它允许在运行时选择算法的行为,在Spring框架中,我们可以利用@Resource注解和Map集合来优雅地实现策略模式,这... 目录前言底层机制解析Spring的集合类型自动装配@Resource注解的行为实现原理使用直接使用M

Nginx指令add_header和proxy_set_header的区别及说明

《Nginx指令add_header和proxy_set_header的区别及说明》:本文主要介绍Nginx指令add_header和proxy_set_header的区别及说明,具有很好的参考价... 目录Nginx指令add_header和proxy_set_header区别如何理解反向代理?proxy

C++中::SHCreateDirectoryEx函数使用方法

《C++中::SHCreateDirectoryEx函数使用方法》::SHCreateDirectoryEx用于创建多级目录,类似于mkdir-p命令,本文主要介绍了C++中::SHCreateDir... 目录1. 函数原型与依赖项2. 基本使用示例示例 1:创建单层目录示例 2:创建多级目录3. 关键注

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

C++常见容器获取头元素的方法大全

《C++常见容器获取头元素的方法大全》在C++编程中,容器是存储和管理数据集合的重要工具,不同的容器提供了不同的接口来访问和操作其中的元素,获取容器的头元素(即第一个元素)是常见的操作之一,本文将详细... 目录一、std::vector二、std::list三、std::deque四、std::forwa

C++字符串提取和分割的多种方法

《C++字符串提取和分割的多种方法》在C++编程中,字符串处理是一个常见的任务,尤其是在需要从字符串中提取特定数据时,本文将详细探讨如何使用C++标准库中的工具来提取和分割字符串,并分析不同方法的适用... 目录1. 字符串提取的基本方法1.1 使用 std::istringstream 和 >> 操作符示

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.

C++ 各种map特点对比分析

《C++各种map特点对比分析》文章比较了C++中不同类型的map(如std::map,std::unordered_map,std::multimap,std::unordered_multima... 目录特点比较C++ 示例代码 ​​​​​​代码解释特点比较1. std::map底层实现:基于红黑