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

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

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

🌈个人主页：是店小二呀
🌈C语言专栏：C语言
🌈C++专栏： C++
🌈初阶数据结构专栏： 初阶数据结构
🌈高阶数据结构专栏： 高阶数据结构
🌈Linux专栏： Linux

🌈喜欢的诗句:无人扶我青云志 我自踏雪至山巅

前言

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

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

一、前往底层初步分析

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

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

二、map第二个参数

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

2.1 键值对本质

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

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

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

2.2 map 的接口设计

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

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

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

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

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

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

int main()
{map<string,string> m;pair<K,V> kv = {"sort"，"排序"}；m.insert(kv);
}

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

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

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

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

这里红黑树节点元素存储了set和map第二个模板参数，这里实例了两个红黑树只是这件事情是由编译器完成的。这样说明了为什么set需要存储<key,key>键值对，是为了跟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<K，V>，对此红黑树不知道这里T代表着谁？

4.2 红黑树的插入

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

红黑树插入实际上没有多大的改动，插入过程中需要通过搜索树按照K比较找到合适的位置进行插入，现在 _date不知道是K还是pair<K, V>类型，如果按照之前 _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 subtreeif (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 childelse{Node* parent = current->parent;while (parent != nullptr && current == parent->left){current = parent;parent = parent->parent;}current = parent;}return current;
}

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

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;
}

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

---

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