[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++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<

C++包装器

包装器 在 C++ 中,“包装器”通常指的是一种设计模式或编程技巧,用于封装其他代码或对象,使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍,可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型: 1. 函数包装器 函数包装器用于封装一个或多个函数,使其接口更统一或更便于调用。例如,std::function 是一个通用的函数包装器,它可以存储任意可调用对象(函数、函数

C++11第三弹:lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页: 南桥几晴秋 🌈C++专栏: 南桥谈C++ 🌈C语言专栏: C语言学习系列 🌈Linux学习专栏: 南桥谈Linux 🌈数据结构学习专栏: 数据结构杂谈 🌈数据库学习专栏: 南桥谈MySQL 🌈Qt学习专栏: 南桥谈Qt 🌈菜鸡代码练习: 练习随想记录 🌈git学习: 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

06 C++Lambda表达式

lambda表达式的定义 没有显式模版形参的lambda表达式 [捕获] 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 有显式模版形参的lambda表达式 [捕获] <模版形参> 模版约束 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 含义 捕获:包含零个或者多个捕获符的逗号分隔列表 模板形参:用于泛型lambda提供个模板形参的名

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

poj 3050 dfs + set的妙用

题意: 给一个5x5的矩阵,求由多少个由连续6个元素组成的不一样的字符的个数。 解析: dfs + set去重搞定。 代码: #include <iostream>#include <cstdio>#include <set>#include <cstdlib>#include <algorithm>#include <cstring>#include <cm

【C++高阶】C++类型转换全攻略:深入理解并高效应用

📝个人主页🌹:Eternity._ ⏩收录专栏⏪:C++ “ 登神长阶 ” 🤡往期回顾🤡:C++ 智能指针 🌹🌹期待您的关注 🌹🌹 ❀C++的类型转换 📒1. C语言中的类型转换📚2. C++强制类型转换⛰️static_cast🌞reinterpret_cast⭐const_cast🍁dynamic_cast 📜3. C++强制类型转换的原因📝

C++——stack、queue的实现及deque的介绍

目录 1.stack与queue的实现 1.1stack的实现  1.2 queue的实现 2.重温vector、list、stack、queue的介绍 2.1 STL标准库中stack和queue的底层结构  3.deque的简单介绍 3.1为什么选择deque作为stack和queue的底层默认容器  3.2 STL中对stack与queue的模拟实现 ①stack模拟实现