【C++】基于红黑树的 Map 和 Set 封装及实现过程详述

id="article_content" class="article_content clearfix"> id="content_views" class="markdown_views prism-kimbie-light">

在这里插入图片描述

class="table-box">
C++语法相关知识点可以通过点击以下链接进行学习一起加油！
命名空间缺省参数与函数重载C++相关特性类和对象-上篇类和对象-中篇
类和对象-下篇日期类C/C++内存管理模板初阶String使用
String模拟实现Vector使用及其模拟实现List使用及其模拟实现容器适配器Stack与QueuePriority Queue与仿函数
模板进阶-模板特化面向对象三大特性-继承机制面向对象三大特性-多态机制STL 树形结构容器二叉搜索树
AVL树红黑树

大家好，我是店小二。今天我将为大家详细讲解如何基于红黑树封装和实现 Map 和 Set，并深入解析底层逻辑。希望通过这篇文章，能帮助大家在使用 Map 和 Set 类相关接口时更加得心应手。

请添加图片描述
Alt
🌈个人主页：是店小二呀
🌈C语言专栏：C语言
🌈C++专栏： C++
🌈初阶数据结构专栏： 初阶数据结构
🌈高阶数据结构专栏： 高阶数据结构
🌈Linux专栏： Linux

🌈喜欢的诗句:无人扶我青云志 我自踏雪至山巅 请添加图片描述

class="toc">

文章目录

前言

模拟实现set和map，set和map底层结构都是通过红黑树实现的，因此在set和map中直接分装一棵红黑树，然后将其接口包装下接口。

但是set是属于K搜索模型，而是map是KV搜索模型，对此虽然实现都通过以底层红黑树实现，很明显不是使用同一个红黑树，那么这样子就会很麻烦，而库中的做法是set和map调用同一棵红黑树，那么具体是如何识别set和map的呢？

一、前往底层初步分析

首先，我们去库中找到set和map实现的代码，再将对于讲述这篇内容无关的代码删除，通过画图梳理当前的信息，得到以下这张图片

在这里插入图片描述

从图中可以得到一些信息，_rb这里第二个模板参数，在set类中是以key 作为value_type，而在map是以为pair 作为value_type，那么可以大致猜测红黑树就是通过value_type第二个模板参数去控制set还是map的，需要考虑到红黑树节点储存类型，还有泛型编程等因素，所以map的第二个模板参数为pair类型。

二、map第二个参数

问题:为什么map的第二个模板参数为pair类型，而不是V类型呢？

2.1 键值对本质

std::map 是一个关联容器，通常是一个 有序的二叉搜索树（红黑树实现），其目的是根据键 K 来查找与之对应的值 V。每个元素都由一个键和值组成，因此，map 的元素类型被定义为 std::pair，即一个键值对。

  • 键 (K)：唯一标识值的标记，不能重复。
  • 值 (V)：与键相关联的数据，可以修改。

为了保证键的不可变性，std::pair 中的键类型是 const K，这样可以避免误修改键，因为修改键会破坏 map 的有序性或查找机制。

2.2 map 的接口设计

std::map 的设计是围绕键值对的存储和查找而设计的。它的内部元素是键值对，并且对这些键值对进行操作时需要涉及到两者的关系。因此，std::map 的接口与 pair 紧密相关

  • 插入操作：当你向 map 插入元素时，插入的是一个键值对 std::pair，而不是单独的值。因为要有键才能确定值存储的位置。
  • 查找操作：map.find(key) 会返回一个迭代器，指向的也是一个 std::pair，表示找到的键值对。
  • 迭代操作：当你遍历 map 时，迭代器会指向 pair，使得你可以访问键和对应的值。
  • 就是pair中K是为了跟K取得联系， std::map 中，值 V 与键 K 是独立的实体。通过将键和值一起存储在 std::pair 中，可以有效地让键用于比较和查找操作，而值 V 则保持不变。这种设计保证了当我们执行查找或比较时，只有键会参与这些操作，而不会影响与键关联的值。(理解点在这里了)

2.3 不用 V类型作为第二个模板参数

如果 map 的元素类型只是 V，那么容器将无法保存键和值的关联关系。原因是：

  • V 类型只包含值，没有与之相关联的键。map 需要将键和值配对起来才能进行查找、插入、删除等操作。
  • map 的查找、插入、删除等操作基于键 K，而不仅仅是值 V。pair 才能表示出键和值的完整关系。

2.4 map第二个参数类型不为pair类型

int main()
{
	map<string,string> m;
    pair<K,V> kv = {"sort"，"排序"}；
       m.insert(kv);
}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

在这里插入图片描述

map类中存储元素是pair类型，但是在定义传递给map类类模板参数，由于只要需要K，V是什么，底层存储pair类型元素是进行相对应的处理。

三、红黑树内部(map与set构成模板)

在这里插入图片描述

将set和map与红黑树相关的图拿出来，进行梳理逻辑，可以清楚的发现他们之间的联系是十分的巧妙的，如果存在多个需要使用同一个类，使用类在类型上有所差异可以将这个类写成模板类，提供不同类型进行使用

3.1 set和map的第一个模板参数会不会多余?

在这里插入图片描述

这里红黑树节点元素存储了set和map第二个模板参数，这里实例了两个红黑树只是这件事情是由编译器完成的。这样说明了为什么set需要存储键值对，是为了跟map构成模板。

提出这个问题可能是考虑到第二个人模板参数存在了K，为什么还需要第一个模板参数存在，看起来就很多余，对于set而言也许是多余的，但是map而言不是的。map使用Find()和Erase()接口时，不是使用V而是使用K，至于set为什么需要多余一个K呢？因为需要跟map构成模板。

在这里插入图片描述

四、修改红黑树实现逻辑

了解上面的分析，对此我们需要修改下红黑树的实现逻辑。

先看看我们之前模拟实现的红黑树

在这里插入图片描述

4.1 T代替K，V类型

在节点上通过T来代替了K,V。那么对于红黑树节点以T来接受可能来自set的K或map的pair，对此红黑树不知道这里T代表着谁？
在这里插入图片描述

4.2 红黑树的插入

在这里插入图片描述

这里返回值类型在set和map那篇提及过，如果插入数据存在，为假，返回当前K位置的迭代器，如果插入数据不存，为真，返回插入新K位置的迭代器。

红黑树插入实际上没有多大的改动，插入过程中需要通过搜索树按照K比较找到合适的位置进行插入，现在 _date不知道是K还是pair类型，如果按照之前 _kv.first是不可取的，万一类型是K呢？

既然红黑树内部无法识别类型，但是对于set和map是知道的。这里可以通过使用仿函数其他的用法，之前我们是使用仿函数控制比较大小的逻辑，而这里可以通过使用仿函数来调用对应的数值。

4.3 类模板根据传参调用仿函数

这里仿函数通过一个类来实现，本质也是运算符重载。如果是set的话，就调用set对应的数值，map也是一个道理。但是这里类如何去识别，这里类里面的仿函数是给set还是map使用呢？这里还是十分复杂，可以通过画图来理清楚这里的逻辑**，这里由于想使用对应仿函数，而是仿函数在类中实现，那么可以使用类模板根据传参决定使用哪个类的仿函数。(这里可以由外部进行控制传参)**

在这里插入图片描述

这里set又搞个仿函数出来，得到的还是K。这里是保证泛型编程，也可以理解为同用模板，陪伴太子读书。

4.4 直接比较大小,可行？

问题:这里是不是可以不用这么麻烦，还要设计一个仿函数，为什么需要仿函数去重写行为，直接进行对比，不行吗？，pair不是用比较大小的接口吗？set就K来比较，map就pair调用比较大小的接口不是好了吗?

在这里插入图片描述

这里需要搞清楚pair是支持比较，但是不是单纯的去比较，不符合我们的预期。

五、实现迭代器在红黑树中移动

完成上述工作，接下需要实现迭代器

Begin是返回指向首元素的迭代器，End是返回指向最后元素的下一个位置。如果二叉搜索树，最小或首元素在最左边，而最大或最右元素的下一个位置也是nullptr。

在这里插入图片描述

5.1 operator++()

如果是++逻辑，以某个节点为起点，这个节点左子树所有节点是小于该节点，右子树所有节点是大于该节点的，这里需要重点关注右子树即可。

首先我们创建二叉搜索树的逻辑是根据中序遍历(左子树 根节点 右子树)的规则，这里需要搞懂两张图或两种情况就可以搞懂如何实现++逻辑了

在这里插入图片描述

首先是第一张图:

当前it遍历完了左边，就访问它的父亲。右为空，下一个访问，倒着在祖先里找，找到孩子是父亲左的祖先，也可以这样子想，it这边右子树遍历完了，根据中序遍历(左子树 根节点 右子树)的规则，意味以it父亲节点为根节点的子树全部遍历完了，需要回祖先子树遍历了。

在这里插入图片描述

大白话说明:++逻辑就是找下一个大的节点，那么只需要关注右子树就行了。无非就是在建立以为右子树为中心，不断左子树 根这样子的结构递归下去，左子树搞完了，搞下根，然后进行往下一个右子树，不断重复 左子树 根，左子树和根遍历完了，找下一个右子树进行搞。最后遍历完了，cur就是在parent->right位置，不断退出来。

5.2 operator–()

如果是–逻辑，以某个节点为起点，这个节点左子树所有节点是小于该节点，右子树所有节点是大于该节点的，这里需要重点关注左子树即可。

首先我们创建二叉搜索树的逻辑是根据中序遍历(左子树 根节点 右子树)的规则，这里需要搞懂两张图或两种情况就可以搞懂如何实现–逻辑了

在这里插入图片描述

Node* operator--() 
{
    if (current == nullptr) return nullptr;

    // Case 1: If there is a left child, move to the rightmost node in the left subtree
    if (current->left != nullptr) 
    {
        current = current->left;
        while (current->right != nullptr) {
            current = current->right;
        }
    } 
    // Case 2: If no left child, move up until we find a parent where we are the right child
    else
    {
        Node* parent = current->parent;
        while (parent != nullptr && current == parent->left)
        {
            current = parent;
            parent = parent->parent;
        }
        current = parent;
    }

    return current;
}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
class="hide-preCode-box">

六、红黑树实现的类相关默认成员函数的实现

6.1 红黑树的析构函数

在这里插入图片描述

6.2 红黑树的拷贝构造函数

RBTree(const RBTree<T>& other)
{
    root = copyTree(other.root, nullptr);
}
private:
// 递归地复制树
Node<T>* copyTree(Node<T>* node, Node<T>* parent) 
{
    if (node == nullptr) 
    {
        return nullptr;
    }

    // 创建一个新的节点，并复制数据和颜色
    Node<T>* newNode = new Node<T>(node->data, node->color);
    newNode->parent = parent;

    // 递归复制左子树和右子树
    newNode->left = copyTree(node->left, newNode);
    newNode->right = copyTree(node->right, newNode);

    return newNode;
}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
class="hide-preCode-box">

这是一个递归函数，它从源树的根节点开始，递归地遍历并复制每一个节点。node 是要复制的当前节点，parent 是新节点的父节点指针。而且节点是在堆上开辟的，递归结束不会销毁。

在这里插入图片描述

以上就是本篇文章的所有内容，在此感谢大家的观看！这里是店小二呀C++笔记，希望对你在学习C++语言旅途中有所帮助！

data-report-view="{"mod":"1585297308_001","spm":"1001.2101.3001.6548","dest":"https://blog.csdn.net/2302_79177254/article/details/142124664","extend1":"pc","ab":"new"}">>
注：本文转载自blog.csdn.net的是店小二呀的文章"https://blog.csdn.net/2302_79177254/article/details/142124664"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！