| C++语法 | 相关知识点 | 可以通过点击 | 以下链接进行学习 | 一起加油！ |
|---|---|---|---|---|
| 命名空间 | 缺省参数与函数重载 | C++相关特性 | 类和对象-上篇 | 类和对象-中篇 |
| 类和对象-下篇 | 日期类 | C/C++内存管理 | 模板初阶 | String使用 |
| String模拟实现 | Vector使用及其模拟实现 | List使用及其模拟实现 | 容器适配器Stack与Queue | Priority Queue与仿函数 |
| 模板进阶-模板特化 | 面向对象三大特性-继承机制 | 面向对象三大特性-多态机制 | STL 树形结构容器 | 二叉搜索树 |
| AVL树 | 红黑树 |
大家好，我是店小二。今天我将为大家详细讲解如何基于红黑树封装和实现 Map 和 Set，并深入解析底层逻辑。希望通过这篇文章，能帮助大家在使用 Map 和 Set 类相关接口时更加得心应手。
?个人主页：是店小二呀
?C语言专栏：C语言
?C++专栏： C++
?初阶数据结构专栏： 初阶数据结构
?高阶数据结构专栏： 高阶数据结构
?Linux专栏： Linux
?喜欢的诗句:无人扶我青云志 我自踏雪至山巅 
文章目录
前言一、前往底层初步分析二、map第二个参数2.1 键值对本质2.2 map 的接口设计2.3 不用 V类型作为第二个模板参数2.4 map第二个参数类型不为pair类型 三、红黑树内部(map与set构成模板)3.1 set和map的第一个模板参数会不会多余? 四、修改红黑树实现逻辑4.1 T代替K，V类型 4.2 红黑树的插入4.3 类模板根据传参调用仿函数4.4 直接比较大小,可行？ 五、实现迭代器在红黑树中移动5.1 operator++()5.2 operator--() 六、红黑树实现的类相关默认成员函数的实现6.1 红黑树的析构函数6.2 红黑树的拷贝构造函数
前言
模拟实现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 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;}六、红黑树实现的类相关默认成员函数的实现
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++语言旅途中有所帮助！