摘要
本文详细介绍了基于红黑树实现的 Set 和 Map 容器，包括其底层设计原理、插入和删除操作的实现细节、性能分析与优化策略，以及实际应用场景和未来发展方向。通过采用红黑树的数据结构，Set 和 Map 容器能够高效地处理有序数据，保持 O(log n) 的时间复杂度，适用于各种数据存储和检索需求。文中还对如何提升容器性能、实现多线程并发优化，以及未来在分布式系统和硬件加速方面的发展进行了探讨，为读者提供了全面的技术视角和实践指导。
本篇博客所涉及的所有代码均可从我的代码仓库获得：https://git.lenyiin.com/Lenyiin/Set_Map
也可以从 CSDN 下载区下载
1、引言
在数据结构与算法的学习与实践中，关联容器（associative containers）是不可忽视的重要工具。作为高效管理数据的一类容器，C++ 标准库中的 set 和 map 在现代软件开发中扮演着关键角色。这两个容器通过平衡二叉搜索树（如红黑树）的底层实现，能够在 O(log n) 的时间复杂度下完成插入、查找、删除等操作，因此被广泛应用于需要有序存储、快速检索和动态调整的数据集场景中。
set 容器作为一种不允许重复元素的集合类型，在许多涉及集合操作的应用中具有优势，比如对数据的去重处理、集合的并集和交集等。由于它保证元素的唯一性和自动排序，set 是实现有序集合、去重列表等场景下不可或缺的工具。同时，set 容器具有多种变体，如 multiset，允许重复元素的存储，提供了更大的灵活性。
相比之下，map 容器则是以键值对的形式存储数据的关联容器。通过基于键的快速查找，map 在需要频繁检索、插入或更新数据的场景下表现出色。其键值对的存储结构不仅确保键的唯一性，同时自动按键的顺序进行排序，因此在实现字典、哈希表、数据库索引等应用时尤为高效。此外，C++ 标准库中还提供了 multimap，允许键重复，以满足不同场景下的需求。
这两种容器的底层实现通常依赖于平衡二叉搜索树，尤其是红黑树。红黑树是一种能够在插入、删除过程中始终保持平衡的自平衡二叉搜索树，这使得 set 和 map 能够在任何操作中维持较低的时间复杂度。理解红黑树的结构与性质，是深入理解 set 和 map 内部实现机制的关键。
本博客的目的在于通过技术深度的分析与代码实现，深入讲解 C++ 中 set 和 map 容器的理论与实际应用。在接下来的章节中，我们将首先介绍 set 和 map 的数据结构与性质，分析其基本操作的实现原理。然后，我们会结合具体代码，**讲解这些容器的底层实现方式，重点探讨红黑树在 set 和 map 中的核心作用。**最后，我们还将探讨 set 和 map 在实际项目中的应用场景及优化策略，为读者提供实践中的参考依据。
通过这篇博客，您将不仅能够掌握 set 和 map 的基本用法，还能对其内部工作原理有深入理解，并且学会在不同场景下灵活运用这些容器，以实现更高效、可扩展的数据结构解决方案。
如果你对 二叉搜索树 还不够了解，我的这篇关于 二叉搜索树 的博客请一定不要错过：《 C++ 修炼全景指南：九 》打破编程瓶颈！掌握二叉搜索树的高效实现与技巧
如果你对 AVL 树 还不够了解，我的这篇关于 AVL 树 的博客请一定不要错过：《 C++ 修炼全景指南：十 》自平衡的艺术：深入了解 AVL 树的核心原理与实现
如果你对 红黑树 还不够了解，我的这篇关于 红黑树 的博客请一定不要错过：《 C++ 修炼全景指南：十一 》穿越数据的红与黑：掌握数据平衡的极致艺术
2、容器的基础概念与使用
C++ 标准库中的 set 和 map 是两种常见的关联容器，均使用自平衡二叉搜索树——通常是**红黑树（Red-Black Tree）**作为其底层数据结构。红黑树的平衡性保证了这些容器的操作时间复杂度始终维持在 O(log n)，无论是插入、删除还是查找操作。因此，set 和 map 容器在大量数据场景下具备良好的性能表现。接下来，我们将通过详细的代码示例，展示 set 和 map 的常见操作，并结合技术深度探讨其背后的实现原理和应用场景。
2.1、容器
在讨论 set 和 map 之前，有必要先了解 C++ 标准库中的容器分类。这些容器分为 序列式容器（Sequence Containers） 和 关联式容器（Associative Containers），它们各自有不同的结构、实现原理以及适用场景。通过理解它们的特性，能够帮助我们更好地选择合适的容器来解决特定问题。
2.1.1、序列式容器（Sequence Containers）
序列式容器是一类用于存储和管理数据元素的线性数据结构，它们主要提供了按照顺序存储元素的功能。在这些容器中，元素的排列顺序与其插入顺序保持一致。序列式容器支持随机访问，允许我们根据元素的存储位置进行高效的插入、删除、修改和访问。
序列式容器主要包括以下几类：
-
string：std::string是C++中处理字符串的标准容器，基于动态数组实现，并提供了一系列字符串相关的操作。- 时间复杂度：
- 随机访问：O(1)
- 尾部插入/删除：摊还复杂度 O(1)
- 中间插入/删除：O(n)
- 使用场景：与传统的
C风格字符串（使用char数组和空字符\0作为结束符）相比，std::string提供了更方便、安全的接口，并具备动态扩展能力，能够自动管理内存。 - 《 C++ 修炼全景指南：二 》告别平庸！实现一个比标准库更强的 C++ String 类
- 时间复杂度：
-
vector：
vector是一种动态数组容器，能够根据需要动态扩展或缩小容量。它提供了高效的随机访问和尾部插入、删除操作，但在数组中间或开头插入和删除元素的效率较低（因为会涉及元素的移动）。- 时间复杂度：
- 随机访问：O(1)
- 尾部插入/删除：摊还复杂度 O(1)
- 中间插入/删除：O(n)
- 使用场景：适用于需要频繁随机访问或尾部操作的场景，如动态数组管理、临时存储等。
- 《 C++ 修炼全景指南：三 》如何实现标准库般强大的 C++ Vector？：从动态扩容到移动语义到迭代器全覆盖
- 时间复杂度：
-
list：
list是双向链表，支持高效地在任何位置进行插入和删除操作，但不支持随机访问。由于链表的元素不连续存储，访问元素的时间复杂度较高，因此不适用于需要频繁随机访问的场景。- 时间复杂度：
- 插入/删除：O(1)
- 随机访问：O(n)
- 使用场景：适用于需要频繁插入和删除元素，但不需要随机访问的场景，如任务队列、事件调度等。
- 《 C++ 修炼全景指南：四 》揭秘 C++ List 容器背后的实现原理，带你构建自己的双向链表
- 时间复杂度：
-
deque：
deque是双端队列，支持在头部和尾部高效地插入和删除元素。与vector相比，它在两端插入和删除元素的性能要更好，但在中间插入或删除元素时，效率与vector类似。-
时间复杂度：
- 随机访问：O(1)
- 头部/尾部插入/删除：O(1)
- 中间插入/删除：O(n)
-
使用场景：适用于双端队列操作，如需要频繁从头部和尾部进行插入和删除操作的场景。
-
《 C++ 修炼全景指南：五 》实现媲美 C++ 标准库的 stack 和 queue 容器 —— 模板、动态扩容、迭代器与线程安全详解
-
序列式容器的特点：
- 支持元素按照插入顺序存储，保证顺序一致。
- 提供灵活的内存管理和高效的线性操作。
string、vector和deque支持随机访问，而list不支持。
2.1.2、关联式容器（Associative Containers）
与序列式容器不同，关联式容器使用的是基于特定规则进行元素存储和管理的树结构或哈希表结构。关联式容器通过键值对来管理数据，自动为插入的元素进行排序或管理，支持高效的查找、插入和删除操作。
关联式容器主要包括两类：
- 有序关联式容器：
使用 红黑树 作为底层数据结构，确保所有元素按照某种规则排序。在有序关联式容器中，元素之间有明确的顺序，查找和操作的时间复杂度通常为O(log n)。包括：set：元素唯一且自动排序的集合容器。map：以键值对存储数据，键是唯一的，并且按键排序。multiset：允许重复元素的集合，其他特性与set类似。multimap：允许重复键的键值对容器，其他特性与map类似。
- 无序关联式容器：
使用 哈希表 作为底层数据结构，通过哈希函数来管理数据。无序关联式容器不保证元素的顺序，但在大多数情况下，查找、插入和删除操作的平均时间复杂度为O(1)。包括：unordered_set：基于哈希表实现的集合，不保证顺序，元素唯一。unordered_map：基于哈希表实现的键值对容器，键是唯一的。unordered_multiset：基于哈希表实现的集合，允许重复元素。unordered_multimap：基于哈希表实现的键值对容器，允许重复键。
2.1.3、键值对
在 C++ 标准库中，键值对数据结构的代表性容器主要是 std::map 和 std::unordered_map。这两种容器广泛用于需要存储和管理键值对的场景。键值对**用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量 key 和 value ，key 代表键值， value 表示与 key 对应的信息。**键值对的数据结构通常用于需要根据某个键快速查找到对应值的场景。C++ 标准库中的 std::map 和 std::unordered_map 正是为这一需求而设计的。
- 键（Key）：通常是一个唯一的标识符，用来访问关联的值。在一个键值对容器中，键不能重复。
- 值（Value）：与键相关联的数据，可以是任何类型，包括基础数据类型或自定义类型。
键值对容器的目标是提供高效的键查找、插入和删除操作，且在查找键时能够保证键的唯一性。比如：现在要建立一个英汉互译的字典，那该字典中必然有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即通过该单词，在词典中就可以找到与其对应的中文含义。
SGI-STL 中关于键值对的定义：
template <class T1, class T2>
struct pair
{
typedef T1 first_type;
typedef T2 second_type;
T1 _first;
T2 _second;
pair()
: _first(T1())
, _second(T2())
{}
pair(const T1& a, const T2& b)
: _first(a)
, _second(b)
{}
};
2.2、set 的定义与实现原理
2.2.1、set 的定义
set 是一种无重复元素的集合容器，通常用于存储需要保证唯一性的元素。它通过维护一个内部有序的结构，确保元素插入时的顺序是基于元素的排序规则的。C++ 中的 set 默认基于 < 运算符的排序规则排列元素，因此在迭代访问时，set 中的元素总是按照升序排列。
set 的底层实现基于红黑树，利用红黑树的平衡性来保证查找、插入、删除操作的时间复杂度始终为 O(log n)。每次插入新元素时，set 会根据其排序规则判断该元素在树中的位置，如果发现重复元素，插入操作会被拒绝，从而确保元素的唯一性。
三万字详解，真的值得一看喔！《 C++ 修炼全景指南：十一 》穿越数据的红与黑：掌握数据平衡的极致艺术
2.2.2、set 的常用操作
红黑树作为 set 容器的底层数据结构，其插入、删除、查找等操作均是通过红黑树的基本操作来实现的。
1、set 的模板参数列表
template < class T, // set::key_type/value_type
class Compare = less<T>, // set::key_compare/value_compare
class Alloc = allocator<T> // set::allocator_type
> class set;
T:set中存放元素的类型，实际在底层存储<value, value>的键值对
Compare:set中元素默认按照小于来比较
Alloc:set中元素空间的管理方式，使用STL提供的空间配置器管理
2、set 的构造
// 构造空的 set
explicit set (const key_compare& comp = key_compare(),
const allocator_type& alloc = allocator_type());
// 用 (first, last) 区间中的元素构造 set
template <class InputIterator>
set (InputIterator first, InputIterator last,
const key_compare& comp = key_compare(),
const allocator_type& alloc = allocator_type());
// 拷贝构造
set (const set& x);
3、set 的迭代器
函数声明 功能介绍
iterator begin() // 返回 set 中起始位置元素的迭代器
iterator end() // 返回 set 中最后一个元素后面的选代器
const iterator cbegin() const // 返回 set 中起始位置元素的 const 迭代器
const iterator cend() const // 返回 set 中最后一个元素后面的 const 迭代器
reverse_iterator rbegin() // 返回 set 第一个元素的反向选代器，即 end
reverse iterator rend() // 返回 set 最后一个元素下一个位置的反向选代器, 即 begin
const reverse iterator crbegin() const // 返回 set 第一个元素的反向const选代器, 即 cend
const reverse iterator crend() const // 返回 set 最后一个元素下一个位置的反向 const 选代器, 即 cbegin
4、set 的容量
函数声明 功能介绍
bool empty( ) const // 检测 set 是否为空, 空返回 true, 否则返回 true
size_type size() const // 返回 set 中有效元素的个数
5、set 的修改操作
函数声明 功能介绍
// 在 set 中插入元素 x, 实际插入的是 <x, x> 构成的键值对, 如果插入成功, 返回 <该元素在 set 中的位置, true>, 如果插入失败, 说明 x 在 set 中已经存在, 返回 <x 在 set 中的位置, false>
pair<iterator,bool> insert(const value_type& x);
// 删除 set 中 position 位置上的元素
void erase (iterator position );
// 删除 set 中值为 x 的元素, 返回删除的元素的个数
size_type erase (const key_type& x);
// 删除 set 中 [first, last) 区间中的元素
void erase (iterator first, iterator last);
// 交换 set 中的元素
void swap(set<Key, Compare, Allocator>& st);
// 将 set 中的元素清空
void clear ( );
// 返回 set 中值为 x 的元素的位置
iterator find (const key_type& x)const
// 返回 set 中值为 x 的元素的个数
size _type count (const key_type& x)const
- 插入操作
在
set中插入元素时，系统会首先通过比较元素的大小来确定其在红黑树中的插入位置。如果待插入的元素与树中的某个节点相等，插入操作会终止，因为set容器要求所有元素唯一。若插入成功，红黑树的平衡性可能会被打破，因此插入操作完成后可能需要进行颜色调整和旋转操作，以维持树的平衡。
- 删除操作
删除操作与插入类似，首先需要找到要删除的元素，随后将其从红黑树中移除。由于删除某个节点可能会破坏红黑树的平衡，删除操作完成后通常需要重新调整树的颜色，或者通过左旋、右旋操作恢复平衡。
- 查找操作
在
set中查找某个元素时，系统会根据红黑树的性质，沿树路径依次进行元素比较。如果找到与目标元素相等的节点，则查找成功。由于红黑树的高度始终保持在 O(log n)，因此查找操作的时间复杂度同样为 O(log n)。
2.2.3、set 使用举例
void test_set1()
{
set<int> s1; // set默认排序为从小到大 set底层是搜索树
s1.insert(10);
s1.insert(20);
s1.insert(5);
s1.insert(2);
s1.insert(1);
s1.insert(8);
s1.insert(14);
s1.insert(44);
s1.insert(23);
s1.insert(0);
s1.insert(2);
s1.insert(1);
s1.insert(8);
s1.insert(14);
// 排序 + 去重
set<int>::iterator it = s1.begin();
while (it != s1.end())
{
//*it = 100; // set中的元素是只读的，不能修改
cout << *it << " ";
it++;
}
cout << endl;
// 范围for
for (auto e : s1)
{
cout << e << " ";
}
cout << endl;
// 拷贝构造 底层默认是一个深拷贝
set<int> s2(s1);
for (auto e : s2)
{
cout << e << " ";
}
cout << endl;
// 删除
// find()是成员函数，只能用于set/multiset/map/multimap
// set<int>::iterator pos = s2.find(5);
auto pos = s2.find(5);
// find()是泛型算法，可以用于所有容器
// s.find() O(logN) s.begin() O(1) s.end() O(1)
// find(s.begin(), s.end(), 5) O(N) 效率会低不少
// auto pos = find(s2.begin(), s2.end(), 5);
if (pos != s2.end())
{
s2.erase(pos);
}
for (auto e : s2)
{
cout << e << " ";
}
cout << endl;
// 或者直接删
s2.erase(8);
s2.erase(80); // 和迭代器的区别在于：删除不存在的元素，不会报错
for (auto e : s2)
{
cout << e << " ";
}
cout << endl;
}
保证唯一性的机制
set 容器的独特性质在于它保证集合中的每个元素都是唯一的。为了实现这一点，set 在插入元素时总是会首先查找该元素是否已存在。如果待插入的元素已存在于树中，插入操作将被拒绝。红黑树的这种有序存储结构在维持树的平衡性的同时，能够在 O(log n) 的时间内完成重复元素的检测和插入决策。
以下是 set 容器的插入操作示例代码：
#include <set>
#include <iostream>
int main() {
std::set<int> s;
// 插入元素
s.insert(10);
s.insert(5);
s.insert(15);
// 插入重复元素，不会成功
auto result = s.insert(10);
if (!result.second)
{
std::cout << "元素 10 已存在" << std::endl;
}
return 0;
}
在这个示例中，set 容器成功插入了 10、5、15 三个元素，但在尝试插入第二个 10 时，插入操作被拒绝，保证了集合的唯一性。
2.3、map 的定义与实现原理
2.3.1、map 的定义
map 是一种键值对（key-value pair）容器，其每个元素都是由唯一的**键（key）和与其对应的值（value）**组成的。与 set 类似，map 中的键是有序存储的，但不同之处在于，map 允许通过键查找其对应的值。C++ 标准库中的 map 默认也基于红黑树实现，因此其查找、插入和删除操作的时间复杂度为 O(log n)。
map 的核心工作机制是通过键来管理数据，键的唯一性是 map 容器的关键属性。这意味着在 map 中，不能有两个元素具有相同的键。当向 map 插入新元素时，如果该键已存在，则新元素不会插入，但其值会被更新。
2.3.2、map 的常用操作
与 set 相同，map 容器的插入、删除和查找操作均依赖于红黑树的平衡性来保持高效性。每个操作的本质与 set 类似，只不过 map 的每个节点不仅存储键，还存储与之相关联的值。
1、map 的模板参数说明
template < class Key, // map::key_type
class T, // map::mapped_type
class Compare = less<Key>, // map::key_compare
class Alloc = allocator<pair<const Key,T> > // map::allocator_type
> class map;
key：键值对中 key 的类型
T：键值对中 value 的类型
Compare：比较器的类型，map中的元素是按照key来比较的，缺省情况下按照小于来比较，一般情况下（内置类型元素）该参数不需要传递，如果无法比较时（自定义类型），需要用户自己显式传递比较规则（一般情况下按照函数指针或者仿函数来传递）
Alloc：通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的空间配置器注意：在使用
map时，需要包含头文件
2、map 的构造
函数声明 功能介绍
map() // 构造一个空的 map
3、map 的迭代器
函数声明 功能介绍
begin() 和 end() // begin: 首元素的位置, end 最后一个元素的下一个位置
cbegin() 和 cend() // 与 begin 和 end 意义相同, 但 cbegin 和 cend 所指向的元素不能修改
rbegin() 和 rend() // // 反向迭代器, rbegin 在 end 位置, rend 在 begin 位置，其 ++ 和 -- 操作与 begin 和 end 操作移动相反
crbegin() 和 crend() // 与 rbegin 和 rend 位置相同, 操作相同, 但 crbegin 和 crend 所指向的元素不能修改
4、map 的容量与元素访问
函数声明 功能简介
bool empty( ) const // 检测 map 中的元素是否为空, 是返回 true, 否则返回 false
size_type size() const // 返回 map 中有效元素的个数
mapped type& operator[](const key_type& k) // 返回去 key 对应的 value
问题：当 key 不在 map 中时，通过 operator 获取对应 value 时会发生什么问题？
注意：在元素访问时，有一个与 operator[] 类似的操作 at() (该函数不常用)函数，都是通过 key 找到与 key 对应的 value 然后返回其引用，不同的是：当 key 不存在时，operator[] 用默认 value 与 key 构建键值对然后插入，返回该默认 value ，at() 函数直接抛异常。
// map/multimap的下标运算符, 返回值是mapped_type&, 如果key不存在, 就插入一个新的节点, value初始化为0
mapped_type& operator[](const key_type& key)
{
return (*((this->insert(make_pair(key, mapped_type()))).first)).second;
}
5、map 的修改操作
// 函数声明 功能简介
// 在 map 中插入键值对 x, 注意 x 是一个键值对, 返回值也是键值对: iterator 代表新插入元素的位置, bool代表释放插入成功
pair<iterator,bool> insert(const value_type& x);
// 删除 position 位置上的元索
void erase (iterator position);
// 删除键值为 x 的元素
size_type erase( const key_type& x);
// 删除 [first, last) 区间中的元素
void erase(iterator first, iterator last);
// 交换两个 map 中的元素
void swap(map<Key,T,Compare, Allocator>& mp);
// 将 map 中的元素清空
void clear();
// 在 map 中插入 key 为 x 的元素, 找到返回该元素的位置的迭代器, 否则返回 end
iterator find(const key_type& x);
// 在 map 中插入 key 为 x 的元素, 找到返回该元素的位置的 const 迭代器, 否则返回 cend
const iterator find (const key_type& x) const
// 返回 key 为 x 的键值在 map 中的个数, 注意 map 中 key 是唯一的, 因此该函数的返回值要么为 0, 要么为 1, 因此也可以用该函数来检测一个 key 是否在 map 中
size_type count(const key_type& x) const
1. 插入操作
当
map中插入新的键值对时，系统首先会查找该键是否已存在。如果键存在，则插入失败，但会更新与该键相关联的值。若键不存在，则红黑树根据键的大小来确定新键值对的插入位置，并按照红黑树的规则进行颜色调整和旋转操作，以确保树的平衡性。2. 删除操作
删除操作与
set类似，首先需要找到对应的键，然后删除对应的键值对。删除完成后，红黑树的平衡性可能会被破坏，因此系统需要通过调整颜色或旋转操作来恢复平衡。3. 查找操作
map中的查找操作是通过键进行的。由于map是基于红黑树实现的，查找过程遵循二叉搜索树的查找方式，能够在 O(log n) 的时间复杂度下找到与目标键匹配的键值对。
2.3.3、map 使用举例
void test_map1()
{
map<int, int> m1;
m1.insert(pair<int, int>(1, 1)); // pair是一个模板类，可以用来创建pair对象
m1.insert(pair<int, int>(3, 3));
m1.insert(pair<int, int>(2, 2));
m1.insert(pair<int, int>(5, 5));
m1.insert(pair<int, int>(6, 6));
m1.insert(pair<int, int>(4, 4)); // pair构造函数，构造一个匿名对象，然后插入到map中
// 日常大家喜欢用make_pair()来构造pair对象，因为他不用声明模板参数，编译器自动推
m1.insert(make_pair(7, 7)); // 函数模板构造一个pair对象
map<int, int>::iterator it = m1.begin();
while (it != m1.end())
{
// cout << *it << " "; // C++不支持返回两个数
cout << (*it).first << " " << (*it).second << endl; // operator*()返回的是节点中值的引用
cout << it->first << " " << it->second << endl; // operator->()返回的是节点的指针 也就是pair<k, v>的指针
it++;
}
cout << endl;
// 范围for
for (auto &e : m1)
{
cout << e.first << " " << e.second << endl;
}
cout << endl;
}
void test_map2()
{
std::map<std::string, std::string> dirt;
dirt.insert(pair<std::string, std::string>("sort", "排序"));
dirt.insert(make_pair("string", "字符串"));
dirt.insert(make_pair("left", "左边")); // 按照ASCII码排序
std::map<std::string, std::string>::iterator it = dirt.begin();
while (it != dirt.end())
{
cout << it->first << " " << it->second << endl;
it++;
}
cout << endl;
}
void test_map3()
{
// 统计单词出现的次数
string strArr[] = {"西瓜", "苹果", "西瓜", "苹果", "西瓜", "香蕉", "西瓜", "樱桃", "西瓜", "苹果",
"西瓜", "苹果", "西瓜", "香蕉", "西瓜", "樱桃", "西瓜", "苹果", "西瓜", "苹果", "西瓜", "香蕉",
"西瓜", "樱桃", "西瓜", "苹果", "西瓜", "苹果", "西瓜", "香蕉", "西瓜", "樱桃", "西瓜", "苹果",
"西瓜", "苹果", "西瓜", "香蕉", "西瓜", "樱桃", "西瓜", "苹果", "西瓜", "苹果", "西瓜", "香蕉"};
map<string, int> countMap;
// 第一种方法
for (auto &str : strArr)
{
map<string, int>::iterator pos = countMap.find(str);
if (pos != countMap.end())
{
pos->second++;
}
else
{
countMap.insert(make_pair(str, 1));
}
}
for (auto &e : countMap)
{
cout << e.first << " " << e.second << endl;
}
cout << endl;
// 第二种方法
for (auto &str : strArr)
{
pair<map<string, int>::iterator, bool> ret = countMap.insert(make_pair(str, 1));
if (ret.second == false) // 插入失败，说明已经存在
{
ret.first->second++; // 迭代器指向的是插入的元素
}
}
for (auto &e : countMap)
{
cout << e.first << " " << e.second << endl;
}
cout << endl;
// 第三种方法
for (auto &str : strArr)
{
// 1、如果水果不在map中，则[]会插入pair<str, 0>, 返回映射对象（次数）的引用进行++
// 2、如果水果在map中，则[]会返回水果对应的映射对象（次数）的引用，对它进行++
countMap[str]++;
}
countMap["葡萄"]; // 插入 一般不这么用
countMap["葡萄"] = 100; // 修改
cout << countMap["葡萄"] << endl; // 查找
countMap["哈密瓜"] = 5; // 插入 + 修改
// 一般使用operator[]去
// 1、插入 + 修改
// 2、修改
// 一般不会用他去做查找，因为如果key不在，会插入数据。
for (auto &e : countMap)
{
cout << e.first << " " << e.second << endl;
}
cout << endl;
}
int main()
{
// test_set1();
test_map1();
// test_map2();
// test_map3();
return 0;
}
2.4、multiset && multimap 的介绍
在 C++ 标准库中，除了 set 和 map，还有两种关联容器——multiset 和 multimap，它们允许存储多个相同的键。与 set 和 map 不同的是，multiset 和 multimap 允许键重复，因此在特定应用场景中，如处理不唯一的集合或键值对，它们非常有用。接下来，我们将详细探讨 multiset 和 multimap 的理论基础、常见操作以及实际应用。
multimap是关联式容器，它是按照特定顺序，存储右key和value映射成的键值对<key, value>，其中多个键值对之间的key是可以重复的。在
multimap中，通常按照key排序和唯一地标识元素，而映射的value存储与key关联的内容。key和value的类型可能不同，通过multimap内部成员类型value_type组合在一起，value_type是组合key和value的键值对：
typedef pair<const Key, T> value_type;在内部，
multimap中的元素总是通过其内部比较对象，按照指定的特定严格弱排序标准对key进行排序的
multimap通过key访问单个元素的速度通常比unordered_multimap容器慢，但是使用迭代器直接遍历multimap中的元素可以得到关于key有序的序列
multimap在底层用二叉搜索树（红黑树）来实现注意：
multimap和map的唯一不同就是：map中的key是唯一的，而multimap中key是可以重复的
multimap 中的接口可以参考 map ，功能都是类似的
注意：
- multimap 中的 key 是可以重复的
- multimap 中的元素默认将 key 按照小于来比较
- multimap 中没有重载 operator[] 操作
- 使用时与 map 包含的头文件相同
multiset && multimap 使用举例
void test_multi()
{
// multiset根set的区别就是允许键值冗余
multiset<int> s1; // 使用和set一样，只是multiset可以存放重复的元素
s1.insert(10);
s1.insert(20);
s1.insert(5);
s1.insert(2);
s1.insert(1);
s1.insert(8);
s1.insert(8);
s1.insert(14);
s1.insert(44);
s1.insert(23);
s1.insert(0);
s1.insert(2);
s1.insert(1);
s1.insert(8);
s1.insert(8);
s1.insert(14);
for (auto e : s1)
{
cout << e << " ";
}
cout << endl;
auto pos = s1.find(8); // 查找到的是重复元素的第一个元素地址
cout << *pos << endl;
pos++;
cout << *pos << endl;
pos++;
cout << *pos << endl;
pos++;
cout << *pos << endl;
pos++;
cout << *pos << endl;
// multimap和map的区别和上面是一样的
multimap<string, int> mm;
mm.insert(make_pair("苹果", 1));
mm.insert(make_pair("苹果", 1));
mm.insert(make_pair("苹果", 3));
mm.insert(make_pair("西瓜", 2));
mm.insert(make_pair("西瓜", 1));
for (auto &e : mm)
{
cout << e.first << " " << e.second << endl;
}
cout << endl;
}
3、红黑树的封装
在这章中，我们将从底层的红黑树设计开始，逐步深入到 set 和 map 的封装与实现。但是本章不会对红黑树讲解的那么细致，如果你对红黑树还不够细致，这篇三万字详解红黑树的博客请一定不要错过：《 C++ 修炼全景指南：十一 》穿越数据的红与黑：掌握数据平衡的极致艺术
我们的目标是通过代码和理论结合，详尽介绍红黑树的结构、迭代器的设计、平衡树的旋转与修正、键值对的存储及其复杂度分析，最终展现如何通过这些基础实现 C++ 标准库中重要的 set 和 map 容器。
3.1、红黑树节点的设计
红黑树的每个节点不仅要存储数据，还必须包含颜色信息（红或黑），并通过指针链接至父节点、左子节点和右子节点。这些额外的信息使红黑树能够在插入和删除操作后保持平衡，并保证操作的时间复杂度为 O(log n)。
3.1.1、节点结构
我们为红黑树设计的节点结构如下：
namespace Lenyiin
{
enum Colour
{
RED,
BLACK
};
template <class T>
struct RBTreeNode
{
RBTreeNode<T> *_left; // 左子节点
RBTreeNode<T> *_right; // 右子节点
RBTreeNode<T> *_parent; // 父节点
T _data; // 节点存储的数据
Colour _colour; // 节点的颜色（红色或黑色）
// 节点的构造函数，默认为红色节点
RBTreeNode(const T &data)
: _left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _colour(RED)
{
}
};
}
3.1.2、节点结构详解
在这个节点设计中，我们使用模板参数 T 来支持不同的数据类型。每个节点包含五个成员变量：
- _left: 指向左子节点的指针。
- _right: 指向右子节点的指针。
- _parent: 指向父节点的指针。这允许我们在树中进行向上回溯操作。
- _data: 存储的数据，可以是任意类型。
- _colour: 表示节点的颜色，枚举类型
Colour包含红色和黑色两个值。
在红黑树中，根节点的颜色始终是黑色，新插入的节点初始为红色。当红黑树进行插入或删除操作时，节点颜色可能会发生变化，以维持红黑树的平衡性。
3.1.3、节点颜色的重要性
红黑树的平衡特性依赖于节点的颜色以及颜色的相关规则：
- 每个节点要么是红色，要么是黑色。
- 根节点必须是黑色。
- 所有叶子节点（NIL 节点，通常用空节点表示）必须是黑色。
- 如果一个节点是红色的，那么它的两个子节点必须是黑色的（即不能有两个连续的红色节点）。
- 从任一节点到其所有叶子节点的路径上，必须包含相同数量的黑色节点。
这些规则的目的在于保持树的近似平衡，即红黑树的高度不会超过 O(log n)，从而保证其高效性。
3.1.4、节点内存管理
在实际实现中，红黑树的节点通常是动态分配的。每次插入新元素时，会创建一个新的节点对象并插入到树中。而在删除节点时，则需要负责释放相应的内存空间。
为避免内存泄漏，我们需要在红黑树的析构函数中处理节点的删除和内存释放操作。为了简化操作，可以设计一个递归的删除函数：
// 删除整个红黑树
void DeleteTree(Node *root)
{
if (root == nullptr)
{
return;
}
// 递归删除左子树
DeleteTree(root->_left);
// 递归删除右子树
DeleteTree(root->_right);
// 删除当前节点
delete root;
}
这样，当红黑树析构时，我们只需调用 DeleteTree(_root) 即可销毁整棵树。
3.2、红黑树的迭代器设计
在 STL 标准库中，容器类的迭代器被设计为一种通用接口，允许用户以统一的方式访问容器的元素。C++ 标准库中 set 和 map 容器都提供了迭代器接口，允许用户像操作数组一样方便地遍历容器中的元素。因此，我们的红黑树封装也需要提供类似的迭代器。
设计原则：
- 双向遍历：迭代器需要支持从当前节点向前或向后移动，确保可以顺序遍历容器中的元素。
- 中序遍历顺序：对于有序关联容器如
set和map，迭代器应确保以中序遍历的顺序访问元素，使得节点的遍历顺序与键值的升序或降序一致。 - 稳定性与高效性：迭代器操作应尽可能高效，避免无谓的计算和内存占用，并保持稳定的时间复杂度。
- 内存安全：在迭代器使用过程中应避免悬空指针等错误。
3.2.1、迭代器的基本结构
迭代器的设计通常是基于指针的，它持有一个指向树节点的指针，并通过重载运算符来实现对树节点的遍历操作。为了实现双向迭代器，我们需要重载增量（++）和减量（--）运算符，保证用户能够顺利进行正向和反向的遍历。首先，我们定义迭代器的结构如下：
namespace Lenyiin
{
template <class T, class Ref, class Ptr>
struct __TreeIterator
{
typedef RBTreeNode<T> Node;
typedef __TreeIterator<T, Ref, Ptr> Self;
Node *_node; // 当前迭代器指向的节点
// 构造函数
__TreeIterator(Node *node)
: _node(node)
{
}
// 解引用操作符
Ref operator*()
{
return _node->data;
}
// 访问成员操作符
Ptr operator->()
{
return &_node->_data;
}
// 前置递增运算符
Self &operator++()
{
// 1. 如果右不为空, 中序的下一个就是右子树的最左节点
if (_node->_right)
{
Node *subLeft = _node->_right;
while (subLeft->_left)
{
subLeft = subLeft->_left;
}
_node = subLeft;
}
// 2. 如果右为空, 表示 _node 所在的子树已经完成, 下一个节点在他祖先中去找, 沿着路径往上找孩子使它的左的那个祖先
else
{
Node *cur = _node;
Node *parent = cur->_parent;
while (parent && cur == parent->_right)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}
// 后置递增运算符
Self operator++(int)
{
Node *tmp = _node;
++(*this);
return Self(tmp);
}
// 前置递减运算符
Self &operator--()
{
// 1. 如果左不为空, 中序的上一个就是左树的最右节点
if (_node->_left)
{
Node *subRight = _node->left;
while (subRight->_right)
{
subRight = subRight->_right;
}
_node = subRight;
}
// 2. 如果左为空, 表示 _node 所在的子树已经完成, 上一个节点在他祖先中去找, 沿着路径往上找孩子是它的右的那个祖先
else
{
Node *cur = _node;
Node *parent = cur->_parent;
while (parent && cur == parent->_left)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}
// 后置递减运算符
Self operator--(int)
{
Node *tmp = _node;
--(*this);
return Self(tmp);
}
bool operator!=(const Self &n)
{
return _node != n._node;
}
bool operator==(const Self &n)
{
return _node == n._node;
}
};
}
3.2.2、迭代器 ++ – 详解
红黑树是一种二叉搜索树，迭代器的遍历应该遵循二叉搜索树的中序遍历规则。中序遍历的顺序为左子树 -> 当前节点 -> 右子树，这确保了迭代器访问节点时的顺序是按键值升序排列的。
例如，给定如下结构的红黑树：
20
/ \
10 30
/ \ \
5 15 40
中序遍历的结果应该是：5 -> 10 -> 15 -> 20 -> 30 -> 40。
在迭代器的实现中，++ 运算符用于实现正向的中序遍历，而 -- 运算符用于实现逆向遍历。我们分别介绍这两个操作的细节。
1、前置递增运算符 (operator++)
为了从当前节点移动到树中的下一个节点（即中序遍历中的下一个节点），我们需要找到中序后继。如果当前节点有右子节点，那么下一个节点应该是其右子树的最左节点；否则，我们需要向上移动，直到找到一个节点，它是其父节点的左子树。
// 前置递增运算符
Self &operator++()
{
// 1. 如果右不为空, 中序的下一个就是右子树的最左节点
if (_node->_right)
{
Node *subLeft = _node->_right;
while (subLeft->_left)
{
subLeft = subLeft->_left;
}
_node = subLeft;
}
// 2. 如果右为空, 表示 _node 所在的子树已经完成, 下一个节点在他祖先中去找, 沿着路径往上找孩子使它的左的那个祖先
else
{
Node *cur = _node;
Node *parent = cur->_parent;
while (parent && cur == parent->_right)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}
这个函数逻辑可以分为两种情况：
- 如果当前节点有右子节点，则它的后继节点是右子树中最左的那个节点。
- 如果当前节点没有右子节点，则需要沿着父指针向上移动，直到找到一个节点，它是其父节点的左子节点，那么这个父节点就是当前节点的后继。
2、前置递减运算符 (operator--)
类似地，前置递减运算符需要找到中序前驱。如果当前节点有左子节点，则前驱节点是左子树中的最右节点；否则，沿着父指针向上移动，直到找到一个节点，它是其父节点的右子节点。
// 前置递减运算符
Self &operator--()
{
// 1. 如果左不为空, 中序的上一个就是左树的最右节点
if (_node->_left)
{
Node *subRight = _node->left;
while (subRight->_right)
{
subRight = subRight->_right;
}
_node = subRight;
}
// 2. 如果左为空, 表示 _node 所在的子树已经完成, 上一个节点在他祖先中去找, 沿着路径往上找孩子是它的右的那个祖先
else
{
Node *cur = _node;
Node *parent = cur->_parent;
while (parent && cur == parent->_left)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}
类似地，这个函数逻辑也可以分为两种情况：
- 如果当前节点有左子节点，则它的前驱节点是左子树中最右的那个节点。
- 如果当前节点没有左子节点，则需要沿着父指针向上移动，直到找到一个节点，它是其父节点的右子节点，那么这个父节点就是当前节点的前驱。
3.2.3、迭代器的边界处理
为了确保迭代器的健壮性，特别是在处理树的边界情况时（例如到达叶子节点的末尾），我们需要额外处理end()和begin()的位置：
end()：当迭代器超出红黑树的最后一个节点时，迭代器应该指向树中的“虚拟末尾”位置，即nullptr。这意味着如果调用++运算符使迭代器越过树的最后一个节点，_node应该被设置为nullptr。begin()：同理，调用--运算符使迭代器超出第一个节点时，也应当触发相应的边界处理，确保访问第一个节点之前的位置时指向nullptr。
3.3、旋转操作
在红黑树中，旋转操作是保持红黑树性质的核心步骤之一。在执行插入或删除操作时，红黑树可能会违反其性质，这时候通过旋转操作可以重新调整树的结构，使其满足红黑树的平衡要求。旋转操作主要分为两种：左旋和右旋。通过这两种操作，我们可以在局部调整树的形状，使得其符合红黑树的性质。
3.3.1、左旋
左旋操作是将节点向左旋转，使其右子节点上升为其父节点，而原节点下降为其右子节点的左子节点。这种旋转主要用于调整在右孩子方向上失衡的情况。
场景：当新节点插入到某个节点的右子树的右子节点时，可能导致该节点失衡。此时，需要进行左旋操作来恢复平衡。
旋转过程：
- 假设不平衡节点为
A，其右子节点为B。 B的左子树BL将成为A的右子树。B成为新的子树根节点，而A成为B的左子节点。
示例图：
插入导致的结构：
A
\
B
\
C
单左旋后的结构：
B
/ \
A C
代码实现：
// 左旋
void RotateL(Node* parent)
{
Node* ppNode = parent->_parent;
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
{
subRL->_parent = parent;
}
subR->_left = parent;
parent->_parent = subR;
// 1. 原来 parent 是这棵树的根, 现在 subR 是根
if (parent == _root)
{
_root = subR;
subR->_parent = nullptr;
}
// 2. parent 为根的树只是整棵树中的子树, 改变链接关系, 那么 subR 要顶替他的位置
else
{
if (ppNode->_left == parent)
{
ppNode->_left = subR;
}
else
{
ppNode->_right = subR;
}
subR->_parent = ppNode;
}
}
解释：
subR指向A的右子节点B。B的左子树subRL被挂接到A的右子树。B成为新的根节点，A成为B的左子节点。
3.3.2、右旋
右旋操作是左旋的镜像操作。它将节点向右旋转，使其左子节点上升为其父节点，而原节点下降为其左子节点的右子节点。右旋主要用于调整在左孩子方向上失衡的情况。
场景：当新节点插入到某个节点的左子树的左子节点时，可能导致该节点失衡。此时，需要进行右单旋操作来恢复平衡。
旋转过程：
- 假设不平衡节点为
A，其左子节点为B。 B的右子树BR将成为A的左子树。B成为新的子树根节点，而A成为B的右子节点。
示例图：
插入导致的结构：
A
/
B
/
C
单右旋后的结构：
B
/ \
C A
代码实现
// 右旋
void RotateR(Node* parent)
{
Node* ppNode = parent->_parent;
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
{
subLR->_parent = parent;
}
subL->_right = parent;
parent->_parent = subL;
if (parent == _root)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (ppNode->_left == parent)
{
ppNode->_left = subL;
}
else
{
ppNode->_right = subL;
}
subL->_parent = ppNode;
}
}
详细解释：
parent是节点AsubL指向A的左子节点B。B的右子树subLR被挂接到A的左子树。B成为新的根节点，A成为B的右子节点。
3.3.3、旋转操作的技术细节
在红黑树的插入和删除操作中，我们使用旋转操作来调整树的平衡。具体来说，旋转操作的目的是减少树的高度，或者说是重新分配子树的高度，使得整个树的结构更加平衡。在红黑树中，执行旋转操作不会破坏二叉搜索树的性质，即中序遍历的顺序仍然保持不变。
- 左旋与右旋的对称性：左旋和右旋是对称操作，左旋将节点的右子树移至父节点，而右旋将节点的左子树移至父节点。两者的实现过程是对称的，这也使得在红黑树的调整中可以灵活运用两者来维护树的平衡。
- 复杂度：单次旋转操作的时间复杂度为
O(1)。旋转操作只涉及指针的改变，不需要遍历树的节点，因此是一个非常高效的操作。 - 调整树的高度：通过左旋或右旋，红黑树可以减少某个子树的高度，或者在某个方向上增加子树的高度。这样就能在插入或删除节点后，通过旋转调整，保持红黑树的高度平衡，进而保证操作的时间复杂度为
O(logn)。
3.3.4、旋转操作在插入和删除中的作用
在红黑树的插入和删除操作中，我们主要通过旋转操作来维护红黑树的性质：
- 插入调整：在插入操作中，可能会出现连续的红色节点违背红黑树的性质。通过旋转和重新着色，可以确保红黑树的平衡。例如，在插入一个节点后，如果出现 “红-红” 冲突，则根据叔叔节点的颜色不同，我们需要执行左旋或者右旋，或者双旋操作来调整树的结构。
- 删除调整：删除操作可能会破坏红黑树的平衡，特别是当删除一个黑色节点时，可能导致黑高不平衡。这时候通过旋转和重新着色，可以重新平衡红黑树。例如，在删除节点后，如果当前节点的兄弟节点是黑色的且其子节点中有一个是红色，则我们可以通过旋转和重新着色，使得整棵树重新满足红黑树的性质。
通过上述两种旋转操作和调整逻辑，红黑树能够在插入和删除操作后，依然保持其性质，从而确保查找、插入、删除操作的时间复杂度始终保持在 O(logn) 。这就是红黑树高效性和实用性的重要原因之一。
3.4、插入操作
为了实现更好的封装，并且适应迭代器，我们可以将红黑树的插入操作做一些改进，并且为后续的 set 和 map 容器提供接口。
3.4.1、插入节点的基本逻辑
首先，插入的第一步仍然是按照二叉搜索树的方式进行，找到合适的位置插入节点。为了更好地封装，我们需要在插入时检查是否已经存在相同的键（对于 set 和 map 而言，键必须是唯一的）。
std::pair<iterator, bool> Insert(const T &data)
{
// 按照搜索树的规则进行插入
// 如果树为空，新节点直接作为根节点
if (_root == nullptr)
{
_root = new Node(data);
_root->_colour = BLACK; // 根节点是黑色的
return std::make_pair(iterator(_root), true);
}
// 插入时使用比较器来比较键的大小，以支持不同的数据类型
KOfT koft;
Node *parent = nullptr;
Node *cur = _root;
while (cur)
{
if (koft(cur->_data) > koft(data))
{
parent = cur;
cur = cur->_left;
}
else if (koft(cur->_data) < koft(data))
{
parent = cur;
cur = cur->_right;
}
else
{
// 如果键已经存在, 插入无效, 返回 false, 并且返回该键的迭代器
return std::make_pair(iterator(cur), false);
}
}
// 找到位置, 根据父节点插入新节点
cur = new Node(data);
Node *newnode = cur;
if (koft(parent->_data) > koft(cur->_data))
{
parent->_left = cur;
cur->_parent = parent;
}
else
{
parent->_right = cur;
cur->_parent = parent;
}
// 插入后需要修复红黑树的性质
InsertFixUp(parent, cur);
return std::make_pair(iterator(newnode), true);
}
解释：
- 插入逻辑：和之前的插入逻辑类似，首先找到合适的父节点，然后将新节点插入到父节点的左子树或右子树中。
- 唯一性检查：在插入时，我们使用
KOfT仿函数来获取键值大小大小，以作比较。如果键已经存在，则返回false表示插入无效。 - 插入后修复：插入完成后，需要调用
InsertFixUp函数来修复红黑树的平衡性。
3.4.2、插入后修复红黑树的性质
插入后，我们需要对红黑树进行调整，以确保其仍然满足红黑树的五个性质。我们继续使用颜色翻转和旋转操作来修复红黑树的平衡。
void InsertFixUp(Node *parent, Node *cur)
{
// 调整结点颜色
// 新结点给红的还是黑的? 红色
// 1. 空树。插入结点做根, 把他变黑。
// 2. 插入红色节点, 他的父亲是黑色的, 结束。
// 3. 插入红色节点, 他的父亲是红色的, 可以推断他的祖父存在且一定为黑色。关键看叔叔
// a. 如果叔叔存在且为红, 把父亲和叔叔变黑, 祖父变红, 继续往上处理。
// b. 如果叔叔存在且为黑, 或者不存在。旋转（单旋 or 双旋）+ 变色
while (parent && parent->_colour == RED)
{
// 关键看叔叔
Node *grandfather = parent->_parent;
// 父节点是祖父节点的左子节点
if (grandfather->_left == parent)
{
Node *uncle = grandfather->_right;
// 情况1: uncle 存在, 且为红
if (uncle && uncle->_colour == RED)
{
parent->_colour = uncle->_colour = BLACK;
grandfather->_colour = RED;
// 继续向上处理
cur = grandfather;
parent = cur->_parent;
}
// 情况 2 or 情况 3 : uncle 不存在 or uncle 存在且为黑
else
{
// 情况 3 : 双旋 -> 变单旋
if (cur == parent->_right)
{
RotateL(parent);
std::swap(parent, cur);
}
// 第二种情况 (ps: 有可能是第三种情况变过来的)
RotateR(grandfather);
grandfather->_colour = RED;
parent->_colour = BLACK;
break;
}
}
// 父节点是祖父节点的右子节点
else
{
Node *uncle = grandfather->_left;
// 情况1: uncle 存在, 且为红
if (uncle && uncle->_colour == RED)
{
parent->_colour = uncle->_colour = BLACK;
grandfather->_colour = RED;
// 继续向上调整
cur = grandfather;
parent = cur->_parent;
}
// 情况 2 or 情况 3 : uncle 不存在 or uncle 存在且为黑
else
{
// 情况 3 : 双旋 -> 变单旋
if (cur == parent->_left)
{
RotateR(parent);
std::swap(parent, cur);
}
// 第二种情况 (ps: 有可能是第三种情况变过来的)
RotateL(grandfather);
grandfather->_colour = RED;
parent->_colour = BLACK;
break;
}
}
}
// 保证根节点为黑
_root->_colour = BLACK;
}
3.4.3、插入调整的细节分析
红黑树插入的调整过程，包含颜色变换和旋转。每当插入一个新节点时，需要仔细判断红黑树的结构，并通过相应的调整来保持其平衡性。我们可以将插入调整过程进一步分为多个情况，并通过每个情况的详细分析，理解红黑树的自平衡过程。
1、情况1: 父节点和叔叔节点都是红色
当插入一个新节点时，如果该节点的父节点和叔叔节点都是红色，那么根据红黑树的性质，需要将父节点和叔叔节点变为黑色，而祖父节点则变为红色。此时，由于祖父节点可能与更高层的祖先发生冲突，需要继续向上调整。
if (uncle && uncle->_colour == RED)
{
parent->_colour = uncle->_colour = BLACK;
grandfather->_colour = RED;
// 继续向上处理
cur = grandfather;
parent = cur->_parent;
}
在这种情况下，整个子树的黑色节点数保持不变，因此不会影响路径的黑色节点数。但是需要注意，祖父节点变为红色可能会破坏红黑树的性质，因此需要递归调整祖父节点。
2、情况2: 父节点是红色，叔叔节点是黑色，且当前节点是父节点的右子节点
当父节点是红色而叔叔节点是黑色时，如果新插入的节点是父节点的右子节点，此时会形成“Z”形的结构。为了使树保持平衡，我们需要先对父节点进行左旋，使当前节点成为父节点，再通过右旋调整整体结构。
if (cur == parent->_right)
{
RotateL(parent);
std::swap(parent, cur);
}
3、情况3: 父节点是红色，叔叔节点是黑色，且当前节点是父节点的左子节点
如果新插入的节点是父节点的左子节点，此时会形成“直线”形结构。此时，我们需要对祖父节点进行右旋，同时交换父节点和祖父节点的颜色，以保持红黑树的平衡。
RotateR(grandfather);
grandfather->_colour = RED;
parent->_colour = BLACK;
在右旋后，父节点成为新的根节点，而祖父节点则变为父节点的右子节点，红黑树的性质得到修复。
4、特殊情况：根节点的颜色调整
无论是哪种情况，在插入调整完成后，都需要确保红黑树的根节点始终为黑色。这是红黑树的一个基本性质，保证了从根节点到叶子节点的路径中至少包含一个黑色节点。
_root->_color = BLACK;
这样可以避免根节点成为红色，从而破坏红黑树的平衡性。
3.5、删除操作
红黑树删除操作相较于插入更加复杂，原因在于：删除节点后可能会破坏红黑树的平衡性和性质（即根节点是黑色、红节点不能有红色子节点、每个路径黑节点数相同等）。因此在删除节点后，必须进行相应的调整来修复红黑树的性质。
红黑树删除通常分为以下几步：
- 寻找要删除的节点：通过红黑树的搜索性质，找到要删除的节点。
- 删除节点并调整树结构：根据删除节点的子节点情况，调整树的链接。
- 修复红黑树的性质：若删除的是黑色节点，可能会破坏红黑树的性质，因此需要通过
DeleteFixUp函数进行颜色调整和旋转操作。
3.5.1、常规BST删除
首先，我们按照 BST 的规则找到并删除指定的节点。红黑树的删除操作可以分为以下几种情况：
- 节点没有子节点：直接删除该节点。
- 节点只有一个子节点：删除该节点，并将其子节点与其父节点连接。
- 节点有两个子节点：找到该节点的中序后继，用中序后继的值替换该节点，然后删除中序后继。
// 删除操作
bool Erase(const K &key)
{
Node *nodeToDelete = _root;
KOfT koft;
// 1. 寻找要删除的节点
while (nodeToDelete)
{
if (koft(nodeToDelete->_data) > key)
{
nodeToDelete = nodeToDelete->_left;
}
else if (koft(nodeToDelete->_data) < key)
{
nodeToDelete = nodeToDelete->_right;
}
else
{
break; // 找到了要删除的节点
}
}
// 节点若不存在, 直接返回 false
if (nodeToDelete == nullptr)
{
return false;
}
// 执行删除操作
Node *parent, *child;
// 保存原节点的颜色，以便后续调整
Colour originalColour = nodeToDelete->_colour;
// 2. 处理删除节点的各种情况
if (nodeToDelete->_left == nullptr)
{
// 情况 1：没有左子节点
child = nodeToDelete->_right;
parent = nodeToDelete->_parent;
Transplant(nodeToDelete, nodeToDelete->_right);
}
else if (nodeToDelete->_right == nullptr)
{
// 情况 2：没有右子节点
child = nodeToDelete->_left;
parent = nodeToDelete->_parent;
Transplant(nodeToDelete, nodeToDelete->_left);
}
else
{
// 情况 3：有两个子节点
// 找到右子树中的最小节点（后继节点）
Node *successor = Minimum(nodeToDelete->_right);
originalColour = successor->_colour;
child = successor->_right;
if (successor->_parent == nodeToDelete)
{
parent = successor;
}
else
{
// 后继节点有右子节点，用它的右子节点替换它
Transplant(successor, successor->_right);
successor->_right = nodeToDelete->_right;
successor->_right->_parent = successor;
parent = successor->_parent;
}
// 用后继节点替换删除节点
Transplant(nodeToDelete, successor);
successor->_left = nodeToDelete->_left;
successor->_left->_parent = successor;
successor->_colour = nodeToDelete->_colour; // 保持颜色不变
}
// 删除节点
delete nodeToDelete;
// 3. 修复红黑树的性质
// 如果删除的节点是黑色, 需要进行调整
if (originalColour == BLACK)
{
EraseFixUp(child, parent);
}
return true;
}
代码详解
- 寻找要删除的节点：
- 使用红黑树的搜索性质，依次比较要删除的键值
key与当前节点的数据做对比，找到对应的节点。 - 如果节点不存在，则返回
false。
- 使用红黑树的搜索性质，依次比较要删除的键值
- 处理删除节点的情况：
- 若要删除的节点没有左子节点，直接用右子节点替换删除的节点。
- 若没有右子节点，则用左子节点替换删除的节点。
- 如果有两个子节点，找到右子树中的最小节点（即后继节点），用后继节点替换要删除的节点。
- 调用
Transplant函数来实现节点的替换。
- 修复红黑树的性质：
- 如果删除的节点是黑色，可能会破坏红黑树的性质，因此需要调用
EraseFixUp函数来进行颜色调整和旋转，恢复红黑树的平衡。
- 如果删除的节点是黑色，可能会破坏红黑树的性质，因此需要调用
3.5.4、辅助函数 Minimum
该函数用于找到指定节点的子树中的最小节点，即左子树中的最左节点。
Node *Minimum(Node *node)
{
while (node->_left != nullptr)
{
node = node->_left; // 一直向左走，直到找到最左节点
}
return node;
}
3.5.3、辅助函数 Transplant
Transplant函数用于在删除节点时，将一个子树替换为另一个子树。
void Transplant(Node *u, Node *v)
{
// 如果u是根节点，v成为新的根节点
if (u->_parent == nullptr)
{
_root = v;
}
// u是左子节点，用v替换它
else if (u == u->_parent->_left)
{
u->_parent->_left = v;
}
// u是右子节点，用v替换它
else
{
u->_parent->_right = v;
}
// 连接v与u的父节点
if (v != nullptr)
{
v->_parent = u->_parent;
}
}
代码详解
Transplant函数用于将节点u替换为节点v，并且将v与u的父节点连接起来。- 若
u是根节点，则直接将v设为根节点，否则根据u是左子节点还是右子节点，分别替换其位置。
3.5.4、删除调整函数 EraseFixUp
void EraseFixUp(Node *child, Node *parent)
{
while (child != _root && (child == nullptr || child->_colour == BLACK))
{
if (child == parent->_left)
{
Node *brother = parent->_right;
// 情况1: child 的兄弟节点 brother 是红色的
if (brother->_colour == RED)
{
brother->_colour = BLACK;
parent->_colour = RED;
RotateL(parent);
brother = parent->_right;
}
// 情况2: child 的兄弟节点 brother 是黑色的, 且 brother 的两个节点都是黑色的
if ((brother->_left == nullptr || brother->_left->_colour == BLACK) &&
(brother->_right == nullptr || brother->_right->_colour == BLACK))
{
brother->_colour = RED;
child = parent;
parent = child->_parent;
}
else
{
// 情况3: brother 是黑色的, 并且 brother 的左子节点是红色, 右子节点是黑色
if (brother->_right == nullptr || brother->_right->_colour == BLACK)
{
if (brother->_left)
{
brother->_left->_colour = BLACK;
}
brother->_colour = RED;
RotateR(brother);
brother = parent->_right;
}
// 情况4: brother 是黑色的, 并且 brother 的右子节点是红色
if (brother)
{
brother->_colour = parent->_colour;
parent->_colour = BLACK;
if (brother->_right)
{
brother->_right->_colour = BLACK;
}
RotateL(parent);
}
child = _root;
break;
}
}
else
{
Node *brother = parent->_left;
// 情况1: child 的兄弟节点 brother 是红色的
if (brother->_colour == RED)
{
brother->_colour = BLACK;
parent->_colour = RED;
RotateR(parent);
brother = parent->_left;
}
// 情况2: child 的兄弟节点 parent 是黑色的, 且 brother 的两个节点都是黑色的
if ((brother->_left == nullptr || brother->_left->_colour == BLACK) &&
(brother->_right == nullptr || brother->_right->_colour == BLACK))
{
brother->_colour = RED;
child = parent;
parent = child->_parent;
}
else
{
// 情况3: brother 是黑色的, 并且 brother 的右子节点是红色, 左子节点是黑色
if (brother->_left == nullptr || brother->_left->_colour == BLACK)
{
if (brother->_right)
{
brother->_right->_colour = BLACK;
}
brother->_colour = RED;
RotateL(brother);
brother = parent->_left;
}
// 情况4: brother 是黑色的, 并且 brother 的左子节点是红色
if (brother)
{
brother->_colour = parent->_colour;
parent->_colour = BLACK;
if (brother->_left)
{
brother->_left->_colour = BLACK;
}
RotateR(parent);
}
child = _root;
break;
}
}
}
if (child)
{
child->_colour = BLACK;
}
}
EraseFixUp 代码解析
- 该函数通过旋转和颜色调整来修复红黑树的平衡。
- 关键在于处理被删除节点的兄弟节点，根据兄弟节点的颜色及其子节点的情况，决定是进行旋转还是颜色调整，确保红黑树
3.6、查找操作
红黑树不仅在插入和删除操作上表现优异，其查找操作同样高效。查找的复杂度为 O(log n)，这得益于红黑树的平衡特性。接下来，我们将详细介绍红黑树的查找过程，包括基本步骤、实现代码以及相关的性质分析。
在红黑树中查找一个键值的过程与在普通二叉搜索树中查找相似。查找时，我们从根节点开始，按照以下步骤进行：
- 比较键值：首先将待查找的键值与当前节点的键值进行比较。
- 如果相等，则找到该节点，返回该节点的迭代器。
- 如果待查找的键值小于当前节点的键值，则向左子树查找。
- 如果待查找的键值大于当前节点的键值，则向右子树查找。
- 继续查找：根据比较结果，继续在相应的子树中查找，直到找到该键值或者遍历到叶子节点（即指向空指针）。
以下是红黑树查找操作的实现代码：
// 查找节点
iterator &Find(const K &key)
{
KOfT koft;
Node *cur = _root;
while (cur)
{
if (koft(cur->_data) > key)
{
cur = cur->_left;
}
else if (koft(cur->_data) < key)
{
cur = cur->_right;
}
else
{
return iterator(cur);
}
}
return iterator(nullptr);
}
代码解析
- 起始节点：我们从根节点开始查找。
- 循环条件：只要当前节点不为空，就持续进行比较。
- 条件判断：通过判断键值的大小关系来决定下一步的查找方向。
- 返回结果：找到节点后返回其对应的迭代器，如果未找到则返回树的结束迭代器（通常为
nullptr）。
查找操作的时间复杂度为 O(log n)。这是因为红黑树的高度是对数级别的，插入和删除操作后，红黑树仍然保持相对平衡，因此查找过程中经过的节点数量是相对较少的。此外，红黑树的性质确保了节点的分布是较为均匀的，避免了出现链式结构的情况，从而保持了高效的查找性能。
3.7、判断是否是红黑树
判断一个二叉树是否为红黑树，需要验证红黑树的所有性质。红黑树有以下五个基本性质：
- 节点颜色性质： 每个节点要么是红色，要么是黑色。
- 根节点性质： 根节点必须是黑色。
- 叶子节点性质： 每个叶子节点（NIL或空节点）必须是黑色。
- 红色节点性质： 如果一个节点是红色，则它的两个子节点必须是黑色（即红色节点不能有红色的子节点）。
- 黑色高度性质： 从任何节点到其每个叶子节点的所有路径都包含相同数量的黑色节点。
判断是否为红黑树的步骤：
- 检查节点颜色： 确保所有节点的颜色合法。
- 检查根节点颜色： 确保根节点是黑色。
- 检查叶子节点颜色： 确保所有叶子节点是黑色。
- 检查红色节点性质： 确保所有红色节点的子节点是黑色。
- 检查黑色高度： 确保从根节点到每个叶子节点的路径上包含相同数量的黑色节点。
检测是否是红黑树的代码实现：
// 判断是否是红黑树
bool IsRBTree()
{
Node *root = _root;
// 空树也是红黑树
if (root == nullptr)
{
return true;
}
// 1. 判断跟是否是黑色的
if (root->_colour != BLACK)
{
std::cout << "根节点不是黑色" << std::endl;
return false;
}
// 获取任意一条路径上黑色节点的数量
size_t blackCount = 0;
Node *cur = _root;
while (cur)
{
if (cur->_colour == BLACK)
{
blackCount++;
}
cur = cur->_left;
}
// 判断是否满足红黑树的性质, k 用来记录路径中黑色节点的个数
size_t k = 0;
return _IsRBTree(_root, k, blackCount);
}
bool _IsRBTree(Node *root, size_t k, size_t blackCount)
{
// 走到 nullptr 之后, 判断 k 和 blackCount 是否相等
if (root == nullptr)
{
// 最终黑色节点个数
if (blackCount != k)
{
std::cout << "违反性质四: 每条路径中黑色节点的个数必须相等" << std::endl;
return false;
}
return true;
}
// 统计黑色节点个数
if (root->_colour == BLACK)
{
k++;
}
// 检测当前节点与其父亲节点是否都为红色
Node *parent = root->_parent;
if (parent && parent->_colour == RED && root->_colour == RED)
{
std::cout << "违反了性质三: 红色节点的孩子必须是黑色" << std::endl;
return false;
}
return _IsRBTree(root->_left, k, blackCount) && _IsRBTree(root->_right, k, blackCount);
}
判断一个二叉树是否为红黑树需要验证其是否满足红黑树的所有基本性质。通过递归地检查节点的颜色、根节点颜色、红色节点性质以及黑色高度，可以有效地判断一个二叉树是否符合红黑树的要求。这个检查过程确保了红黑树在插入和删除操作后能够保持其平衡特性，从而保证了其优良的时间复杂度性能。
4、set 和 map 容器的实现
4.1、Set 容器的实现
set 的底层为红黑树，因此只需在 set 内部直接封装一颗红黑树，即可将该容器实现出来。这个 Set 容器利用了第三章封装的红黑树 (RBTree) 来实现底层的有序集合存储，其中元素唯一并且按升序排列。
4.1.1、获取键值的仿函数 SetKeyOfT
// 用于从节点中获取键值的仿函数
struct SetKeyOfT
{
const K &operator()(const K &k)
{
return k;
}
};
这个结构体是一个仿函数，用于提取红黑树中元素的键。在 set 中，键和值是相同的，operator() 返回元素本身的引用。
4.1.2、迭代器类型定义
这里定义了两个迭代器类型：
iterator：用于遍历集合中的元素，支持修改元素。const_iterator：只读迭代器，不能修改元素。
迭代器类型来自于第三章讲解的 RBTree 的迭代器封装：
typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;
typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;
由于 RBTree<K, K, SetKeyOfT> 还没有实例化，因此需要使用 typename 关键字来指示编译器推迟解析这些类型。
4.1.3、构造函数与基本接口
提供了一些常见的集合操作，如 Insert 插入、Erase 删除、Find 查找等。
1、插入元素
Insert 方法将一个新元素插入到 set 中，利用第三章封装的红黑树的 Insert 方法。返回值是一个 std::pair，第一个值是插入位置的迭代器，第二个值是布尔值，表示插入是否成功（即该元素是否已存在）：
// 插入元素，返回插入结果
std::pair<iterator, bool> Insert(const K &key)
{
return _tree.Insert(key);
}
2、删除元素
Erase 方法从集合中删除指定的元素，返回 true 表示删除成功，false 表示该元素不存在：
// 删除元素，返回是否删除成功
bool Erase(const K &key)
{
return _tree.Erase(key);
}
3、查找元素
Find 方法用于查找指定元素，返回指向该元素的迭代器。如果元素不存在，返回 end()：
// 查找元素，返回指向该元素的迭代器
iterator &Find(const K &key)
{
return _tree.Find(key);
}
4、迭代器
提供了 begin() 和 end() 方法用于遍历 set 容器。begin() 返回指向第一个元素的迭代器，end() 返回指向尾后位置的迭代器：
// 返回指向第一个元素的迭代器
iterator begin()
{
return _tree.begin();
}
// 返回指向尾后位置的迭代器
iterator end()
{
return _tree.end();
}
// const 版本的迭代器
const_iterator begin() const
{
return _tree.begin();
}
const_iterator end() const
{
return _tree.end();
}
5、校验红黑树属性
IsRBTree 方法用于校验底层红黑树的合法性（即是否符合红黑树的性质）：
// 校验红黑树的合法性
bool IsRBTree()
{
return _tree.IsRBTree();
}
4.1.4、私有成员变量
_tree 是 Set 的核心数据结构，一个红黑树实例：
// 底层红黑树实例
RBTree<K, K, SetKeyOfT> _tree;
4.1.5、完整的 Set 容器实现代码
#pragma once
#include "RBTree.hpp"
namespace Lenyiin
{
// Set 容器的实现，依赖于红黑树
template <class K>
class Set
{
// 用于从节点中获取键值的仿函数
struct SetKeyOfT
{
const K &operator()(const K &k)
{
return k;
}
};
public:
// 定义迭代器类型，支持遍历和访问集合中的元素
// 这里RBTree<K, K, SetKeyOfT>::iterator还没有实例化, 系统找不到, typename告诉编译器现在先不着急找
typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;
typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;
// 返回指向第一个元素的迭代器
iterator begin()
{
return _tree.begin();
}
// 返回指向尾后位置的迭代器
iterator end()
{
return _tree.end();
}
// const 版本的迭代器
const_iterator begin() const
{
return _tree.begin();
}
const_iterator end() const
{
return _tree.end();
}
// 插入元素，返回插入结果
std::pair<iterator, bool> Insert(const K &key)
{
return _tree.Insert(key);
}
// 删除元素，返回是否删除成功
bool Erase(const K &key)
{
return _tree.Erase(key);
}
// 查找元素，返回指向该元素的迭代器
iterator Find(const K &key)
{
return _tree.Find(key);
}
// 校验红黑树的合法性
bool IsRBTree()
{
return _tree.IsRBTree();
}
private:
// 底层红黑树实例
RBTree<K, K, SetKeyOfT> _tree;
};
}
4.1.6、Set 容器的使用示例
int main()
{
Set<int> s;
s.Insert(3);
s.Insert(4);
s.Insert(1);
s.Insert(2);
s.Insert(2);
s.Insert(5);
// 迭代器遍历
Set<int>::iterator it = s.begin();
while (it != s.end())
{
cout << *it << " ";
++it;
}
cout << endl;
// 删除
s.Erase(4);
// for
for (const auto &k : s)
{
cout << k << " ";
}
cout << endl;
cout << "IsRBTree? " << (s.IsRBTree() ? "true" : "false") << endl;
return 0;
}
测试结果：
4.2、Map 容器的实现
Map 容器是一种关联式容器，它基于红黑树的实现，能够高效地支持按键值对 (key-value) 的插入、删除、查找等操作。其背后的核心数据结构为红黑树（RBTree），通过自平衡的特性，确保 Map 容器在最坏情况下仍能保持 O(log n) 的时间复杂度。
在 Map 容器的实现中，键值对（std::pair<K, V>）是红黑树中的元素，每个节点包含一个键 K 和一个值 V。红黑树根据键 K 进行排序，这意味着 Map 能够根据键快速查找对应的值。
map 的底层为红黑树，因此只需在 map 内部直接封装一颗红黑树，即可将该容器实现出来。
4.2.1、Map 容器的基本设计
struct MapKeyOfT
{
const K &operator()(const std::pair<K, V> &kv)
{
return kv.first; // 返回键作为红黑树的比较依据
}
};
这里的 MapKeyOfT 是一个仿函数，用来从键值对中提取出键 K，以便红黑树能够根据键进行排序。红黑树 RBTree 需要一个键提取策略，而这里正是通过这个仿函数来实现的。
4.2.2、迭代器设计
迭代器是遍历容器的关键。在 Map 容器中，迭代器实际上是红黑树的迭代器。我们通过 typedef 来简化定义，使其支持 const 和普通迭代器。
typedef typename RBTree<K, std::pair<K, V>, MapKeyOfT>::iterator iterator;
typedef typename RBTree<K, std::pair<K, V>, MapKeyOfT>::const_iterator const_iterator;
这里使用了 typename 来告诉编译器 RBTree<K, std::pair<K, V>, MapKeyOfT>::iterator 是一个类型，而不是静态成员函数或者变量。这是因为 RBTree 是一个模板类，在模板上下文中，需要显式指明 iterator 是类型。
4.2.3、Map 基本接口的实现
1、begin() 和 end() 函数
这些函数提供对 Map 容器的遍历支持。begin() 返回指向容器第一个元素的迭代器，end() 返回指向容器末尾（后一个位置）的迭代器。
iterator begin()
{
return _tree.begin();
}
iterator end()
{
return _tree.end();
}
const_iterator begin() const
{
return _tree.begin();
}
const_iterator end() const
{
return _tree.end();
}
2、Insert 函数
Insert 函数用于向 Map 中插入一个键值对。如果键已经存在，插入操作会失败，并返回已存在键的迭代器；否则，将键值对插入到红黑树中。
std::pair<iterator, bool> Insert(const std::pair<K, V> &kv)
{
return _tree.Insert(kv);
}
这里使用了 std::pair<iterator, bool> 作为返回值，iterator 用于指向插入的位置，而 bool 用于指示插入是否成功。
3、Erase 函数
Erase 函数用于根据给定的键删除对应的键值对。返回值为布尔类型，指示删除操作是否成功。
bool Erase(const K &key)
{
return _tree.Erase(key);
}
4、operator[]
operator[] 是 Map 容器中的常用操作符，用于根据键来访问或插入键值对。如果键不存在，operator[] 会插入一个键对应的默认值 V()。
V &operator[](const K &key)
{
std::pair<iterator, bool> ret = _tree.Insert(std::make_pair(key, V()));
return ret.first->second;
}
operator[] 通过插入默认构造的 V() 来实现“懒惰插入”（即在查找键时，如果键不存在，则创建该键，并赋值一个默认构造的值）。这里的 Insert 操作确保了键值对的唯一性。
5、IsRBTree 函数
这是一个用于调试和验证红黑树合法性的函数，通常用于确认红黑树的结构是否满足红黑树的性质。
bool IsRBTree()
{
return _tree.IsRBTree();
}
4.2.4、私有成员
_tree 是 Map 容器中的核心数据结构，即红黑树 RBTree，它负责存储所有键值对。
RBTree<K, std::pair<K, V>, MapKeyOfT> _tree;
红黑树的模板参数分别为：
K：键的类型。std::pair<K, V>：红黑树节点存储的类型（即键值对）。MapKeyOfT：从键值对中提取键的策略。
4.2.5、完整的 Map 容器实现代码
#pragma once
#include "RBTree.hpp"
namespace Lenyiin
{
// Map 容器的实现，依赖于红黑树
template <class K, class V>
class Map
{
// 用于从节点中获取键值的仿函数
struct MapKeyOfT
{
const K &operator()(const std::pair<K, V> &kv)
{
return kv.first; // 返回键作为红黑树的比较依据
}
};
public:
// 定义迭代器类型，支持遍历和访问集合中的元素
typedef typename RBTree<K, std::pair<K, V>, MapKeyOfT>::iterator iterator;
typedef typename RBTree<K, std::pair<K, V>, MapKeyOfT>::const_iterator const_iterator;
// 返回指向第一个元素的迭代器
iterator begin()
{
return _tree.begin();
}
// 返回指向尾后位置的迭代器
iterator end()
{
return _tree.end();
}
// const 版本的迭代器
const_iterator begin() const
{
return _tree.begin();
}
const_iterator end() const
{
return _tree.end();
}
// 插入元素，返回插入结果
std::pair<iterator, bool> Insert(const std::pair<K, V> &kv)
{
return _tree.Insert(kv);
}
// 删除元素，返回是否删除成功
bool Erase(const K &key)
{
return _tree.Erase(key);
}
// 查找元素，返回指向该元素的迭代器
iterator Find(const K &key)
{
return _tree.Find(key);
}
// [] 下标运算符
V &operator[](const K &key)
{
std::pair<iterator, bool> ret = _tree.Insert(std::make_pair(key, V()));
return ret.first->second;
}
// 校验红黑树的合法性
bool IsRBTree()
{
return _tree.IsRBTree();
}
private:
RBTree<K, std::pair<K, V>, MapKeyOfT> _tree;
};
}
4.2.5、Map 容器的使用示例
int main()
{
Lenyiin::Map<int, std::string> map;
// 插入键值对
map.Insert(std::make_pair(1, "one"));
map.Insert(std::make_pair(2, "two"));
map.Insert(std::make_pair(3, "three"));
// 通过 operator[] 访问或插入
map[4] = "four";
std::cout << "Key 4: " << map[4] << std::endl;
// 查找元素
auto it = map.Find(2);
if (it != map.end())
{
std::cout << "Found: " << it->first << " -> " << it->second << std::endl;
}
// 删除元素
map.Erase(1);
// 验证红黑树
cout << "IsRBTree? " << (map.IsRBTree() ? "true" : "false") << endl;
return 0;
}
示例结果：
5、完整实现代码和测试
5.1、RBTree.hpp
#pragma once
#include <iostream>
namespace Lenyiin
{
enum Colour
{
RED,
BLACK
};
template <class T>
struct RBTreeNode
{
RBTreeNode<T> *_left; // 左子节点
RBTreeNode<T> *_right; // 右子节点
RBTreeNode<T> *_parent; // 父节点
T _data; // 节点存储的数据
Colour _colour; // 节点的颜色（红色或黑色）
// 节点的构造函数，默认为红色节点
RBTreeNode(const T &data)
: _left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _colour(RED)
{
}
};
template <class T, class Ref, class Ptr>
struct __TreeIterator
{
typedef RBTreeNode<T> Node;
typedef __TreeIterator<T, Ref, Ptr> Self;
Node *_node; // 当前迭代器指向的节点
// 构造函数
__TreeIterator(Node *node)
: _node(node)
{
}
// 解引用操作符
Ref operator*()
{
return _node->_data;
}
// 访问成员操作符
Ptr operator->()
{
return &_node->_data;
}
// 前置递增运算符
Self &operator++()
{
// 1. 如果右不为空, 中序的下一个就是右子树的最左节点
if (_node->_right)
{
Node *subLeft = _node->_right;
while (subLeft->_left)
{
subLeft = subLeft->_left;
}
_node = subLeft;
}
// 2. 如果右为空, 表示 _node 所在的子树已经完成, 下一个节点在他祖先中去找, 沿着路径往上找孩子使它的左的那个祖先
else
{
Node *cur = _node;
Node *parent = cur->_parent;
while (parent && cur == parent->_right)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}
// 后置递增运算符
Self operator++(int)
{
Node *tmp = _node;
++(*this);
return Self(tmp);
}
// 前置递减运算符
Self &operator--()
{
// 1. 如果左不为空, 中序的上一个就是左树的最右节点
if (_node->_left)
{
Node *subRight = _node->left;
while (subRight->_right)
{
subRight = subRight->_right;
}
_node = subRight;
}
// 2. 如果左为空, 表示 _node 所在的子树已经完成, 上一个节点在他祖先中去找, 沿着路径往上找孩子是它的右的那个祖先
else
{
Node *cur = _node;
Node *parent = cur->_parent;
while (parent && cur == parent->_left)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}
// 后置递减运算符
Self operator--(int)
{
Node *tmp = _node;
--(*this);
return Self(tmp);
}
bool operator!=(const Self &n)
{
return _node != n._node;
}
bool operator==(const Self &n)
{
return _node == n._node;
}
};
template <class K, class T, class KOfT>
class RBTree
{
private:
typedef RBTreeNode<T> Node;
// 左单旋
void RotateL(Node *parent)
{
Node *ppNode = parent->_parent;
Node *subR = parent->_right;
Node *subRL = subR->_left;
parent->_right = subRL;
if (subRL)
{
subRL->_parent = parent;
}
subR->_left = parent;
parent->_parent = subR;
// 1. 原来 parent 是这棵树的根, 现在 subR 是根
if (_root == parent)
{
_root = subR;
subR->_parent = nullptr;
}
// 2. parent 为根的树只是整棵树中的子树, 改变链接关系, 那么 subR 要顶替他的位置
else
{
if (ppNode->_left == parent)
{
ppNode->_left = subR;
}
else
{
ppNode->_right = subR;
}
subR->_parent = ppNode;
}
}
// 右单旋
void RotateR(Node *parent)
{
Node *ppNode = parent->_parent;
Node *subL = parent->_left;
Node *subLR = subL->_right;
parent->_left = subLR;
if (subLR)
{
subLR->_parent = parent;
}
subL->_right = parent;
parent->_parent = subL;
if (_root == parent)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (ppNode->_left == parent)
{
ppNode->_left = subL;
}
else
{
ppNode->_right = subL;
}
subL->_parent = ppNode;
}
}
// 删除整个红黑树
void DeleteTree(Node *root)
{
if (root == nullptr)
{
return;
}
// 递归删除左子树
DeleteTree(root->_left);
// 递归删除右子树
DeleteTree(root->_right);
// 删除当前节点
delete root;
}
public:
typedef __TreeIterator<T, T &, T *> iterator;
typedef __TreeIterator<T, const T &, const T *> const_iterator;
iterator begin()
{
Node *cur = _root;
while (cur && cur->_left)
{
cur = cur->_left;
}
return iterator(cur);
}
iterator end()
{
return iterator(nullptr);
}
const_iterator begin() const
{
Node *cur = _root;
while (cur && cur->_left)
{
cur = cur->_left;
}
return const_iterator(cur);
}
const_iterator end() const
{
return const_iterator(nullptr);
}
RBTree(Node *root = nullptr)
: _root(root)
{
}
~RBTree()
{
DeleteTree(_root);
}
// 插入
// 1. 空树。插入结点做根，把他变黑。
// 2. 插入红色节点，他的父亲是黑色的，结束。
// 3. 插入红色节点，他的父亲是红色的，可以推断他的祖父存在且一定为黑色。关键看叔叔
// a. 如果叔叔存在且为红，把父亲和叔叔变黑，祖父变红，继续往上处理。
// b. 如果叔叔存在且为黑，或者不存在。旋转（单旋 or 双旋）+ 变色
std::pair<iterator, bool> Insert(const T &data)
{
// 按照搜索树的规则进行插入
// 如果树为空，新节点直接作为根节点
if (_root == nullptr)
{
_root = new Node(data);
_root->_colour = BLACK; // 根节点是黑色的
return std::make_pair(iterator(_root), true);
}
// 插入时使用比较器来比较键的大小，以支持不同的数据类型
KOfT koft;
Node *parent = nullptr;
Node *cur = _root;
while (cur)
{
if (koft(cur->_data) > koft(data))
{
parent = cur;
cur = cur->_left;
}
else if (koft(cur->_data) < koft(data))
{
parent = cur;
cur = cur->_right;
}
else
{
// 如果键已经存在, 插入无效, 返回 false, 并且返回该键的迭代器
return std::make_pair(iterator(cur), false);
}
}
// 找到位置, 根据父节点插入新节点
cur = new Node(data);
Node *newnode = cur;
if (koft(parent->_data) > koft(cur->_data))
{
parent->_left = cur;
cur->_parent = parent;
}
else
{
parent->_right = cur;
cur->_parent = parent;
}
// 插入后需要修复红黑树的性质
InsertFixUp(parent, cur);
return std::make_pair(iterator(newnode), true);
}
void InsertFixUp(Node *parent, Node *cur)
{
// 调整结点颜色
// 新结点给红的还是黑的? 红色
// 1. 空树。插入结点做根, 把他变黑。
// 2. 插入红色节点, 他的父亲是黑色的, 结束。
// 3. 插入红色节点, 他的父亲是红色的, 可以推断他的祖父存在且一定为黑色。关键看叔叔
// a. 如果叔叔存在且为红, 把父亲和叔叔变黑, 祖父变红, 继续往上处理。
// b. 如果叔叔存在且为黑, 或者不存在。旋转（单旋 or 双旋）+ 变色
while (parent && parent->_colour == RED)
{
// 关键看叔叔
Node *grandfather = parent->_parent;
// 父节点是祖父节点的左子节点
if (grandfather->_left == parent)
{
Node *uncle = grandfather->_right;
// 情况1: uncle 存在, 且为红
if (uncle && uncle->_colour == RED)
{
parent->_colour = uncle->_colour = BLACK;
grandfather->_colour = RED;
// 继续向上处理
cur = grandfather;
parent = cur->_parent;
}
// 情况 2 or 情况 3 : uncle 不存在 or uncle 存在且为黑
else
{
// 情况 3 : 双旋 -> 变单旋
if (cur == parent->_right)
{
RotateL(parent);
std::swap(parent, cur);
}
// 第二种情况 (ps: 有可能是第三种情况变过来的)
RotateR(grandfather);
grandfather->_colour = RED;
parent->_colour = BLACK;
break;
}
}
// 父节点是祖父节点的右子节点
else
{
Node *uncle = grandfather->_left;
// 情况1: uncle 存在, 且为红
if (uncle && uncle->_colour == RED)
{
parent->_colour = uncle->_colour = BLACK;
grandfather->_colour = RED;
// 继续向上调整
cur = grandfather;
parent = cur->_parent;
}
// 情况 2 or 情况 3 : uncle 不存在 or uncle 存在且为黑
else
{
// 情况 3 : 双旋 -> 变单旋
if (cur == parent->_left)
{
RotateR(parent);
std::swap(parent, cur);
}
// 第二种情况 (ps: 有可能是第三种情况变过来的)
RotateL(grandfather);
grandfather->_colour = RED;
parent->_colour = BLACK;
break;
}
}
}
// 保证根节点为黑
_root->_colour = BLACK;
}
// 删除操作
bool Erase(const K &key)
{
Node *nodeToDelete = _root;
KOfT koft;
// 1. 寻找要删除的节点
while (nodeToDelete)
{
if (koft(nodeToDelete->_data) > key)
{
nodeToDelete = nodeToDelete->_left;
}
else if (koft(nodeToDelete->_data) < key)
{
nodeToDelete = nodeToDelete->_right;
}
else
{
break; // 找到了要删除的节点
}
}
// 节点若不存在, 直接返回 false
if (nodeToDelete == nullptr)
{
return false;
}
// 执行删除操作
Node *parent, *child;
// 保存原节点的颜色，以便后续调整
Colour originalColour = nodeToDelete->_colour;
// 2. 处理删除节点的各种情况
if (nodeToDelete->_left == nullptr)
{
// 情况 1：没有左子节点
child = nodeToDelete->_right;
parent = nodeToDelete->_parent;
Transplant(nodeToDelete, nodeToDelete->_right);
}
else if (nodeToDelete->_right == nullptr)
{
// 情况 2：没有右子节点
child = nodeToDelete->_left;
parent = nodeToDelete->_parent;
Transplant(nodeToDelete, nodeToDelete->_left);
}
else
{
// 情况 3：有两个子节点
// 找到右子树中的最小节点（后继节点）
Node *successor = Minimum(nodeToDelete->_right);
originalColour = successor->_colour;
child = successor->_right;
if (successor->_parent == nodeToDelete)
{
parent = successor;
}
else
{
// 后继节点有右子节点，用它的右子节点替换它
Transplant(successor, successor->_right);
successor->_right = nodeToDelete->_right;
successor->_right->_parent = successor;
parent = successor->_parent;
}
// 用后继节点替换删除节点
Transplant(nodeToDelete, successor);
successor->_left = nodeToDelete->_left;
successor->_left->_parent = successor;
successor->_colour = nodeToDelete->_colour; // 保持颜色不变
}
// 删除节点
delete nodeToDelete;
// 3. 修复红黑树的性质
// 如果删除的节点是黑色, 需要进行调整
if (originalColour == BLACK)
{
EraseFixUp(child, parent);
}
return true;
}
Node *Minimum(Node *node)
{
while (node->_left != nullptr)
{
node = node->_left; // 一直向左走，直到找到最左节点
}
return node;
}
void Transplant(Node *u, Node *v)
{
// 如果u是根节点，v成为新的根节点
if (u->_parent == nullptr)
{
_root = v;
}
// u是左子节点，用v替换它
else if (u == u->_parent->_left)
{
u->_parent->_left = v;
}
// u是右子节点，用v替换它
else
{
u->_parent->_right = v;
}
// 连接v与u的父节点
if (v != nullptr)
{
v->_parent = u->_parent;
}
}
void EraseFixUp(Node *child, Node *parent)
{
while (child != _root && (child == nullptr || child->_colour == BLACK))
{
if (child == parent->_left)
{
Node *brother = parent->_right;
// 情况1: child 的兄弟节点 brother 是红色的
if (brother->_colour == RED)
{
brother->_colour = BLACK;
parent->_colour = RED;
RotateL(parent);
brother = parent->_right;
}
// 情况2: child 的兄弟节点 brother 是黑色的, 且 brother 的两个节点都是黑色的
if ((brother->_left == nullptr || brother->_left->_colour == BLACK) &&
(brother->_right == nullptr || brother->_right->_colour == BLACK))
{
brother->_colour = RED;
child = parent;
parent = child->_parent;
}
else
{
// 情况3: brother 是黑色的, 并且 brother 的左子节点是红色, 右子节点是黑色
if (brother->_right == nullptr || brother->_right->_colour == BLACK)
{
if (brother->_left)
{
brother->_left->_colour = BLACK;
}
brother->_colour = RED;
RotateR(brother);
brother = parent->_right;
}
// 情况4: brother 是黑色的, 并且 brother 的右子节点是红色
if (brother)
{
brother->_colour = parent->_colour;
parent->_colour = BLACK;
if (brother->_right)
{
brother->_right->_colour = BLACK;
}
RotateL(parent);
}
child = _root;
break;
}
}
else
{
Node *brother = parent->_left;
// 情况1: child 的兄弟节点 brother 是红色的
if (brother->_colour == RED)
{
brother->_colour = BLACK;
parent->_colour = RED;
RotateR(parent);
brother = parent->_left;
}
// 情况2: child 的兄弟节点 parent 是黑色的, 且 brother 的两个节点都是黑色的
if ((brother->_left == nullptr || brother->_left->_colour == BLACK) &&
(brother->_right == nullptr || brother->_right->_colour == BLACK))
{
brother->_colour = RED;
child = parent;
parent = child->_parent;
}
else
{
// 情况3: brother 是黑色的, 并且 brother 的右子节点是红色, 左子节点是黑色
if (brother->_left == nullptr || brother->_left->_colour == BLACK)
{
if (brother->_right)
{
brother->_right->_colour = BLACK;
}
brother->_colour = RED;
RotateL(brother);
brother = parent->_left;
}
// 情况4: brother 是黑色的, 并且 brother 的左子节点是红色
if (brother)
{
brother->_colour = parent->_colour;
parent->_colour = BLACK;
if (brother->_left)
{
brother->_left->_colour = BLACK;
}
RotateR(parent);
}
child = _root;
break;
}
}
}
if (child)
{
child->_colour = BLACK;
}
}
// 查找节点
iterator Find(const K &key)
{
KOfT koft;
Node *cur = _root;
while (cur)
{
if (koft(cur->_data) > key)
{
cur = cur->_left;
}
else if (koft(cur->_data) < key)
{
cur = cur->_right;
}
else
{
return iterator(cur);
}
}
return iterator(nullptr);
}
// 判断是否是红黑树
bool IsRBTree()
{
Node *root = _root;
// 空树也是红黑树
if (root == nullptr)
{
return true;
}
// 1. 判断跟是否是黑色的
if (root->_colour != BLACK)
{
std::cout << "根节点不是黑色" << std::endl;
return false;
}
// 获取任意一条路径上黑色节点的数量
size_t blackCount = 0;
Node *cur = _root;
while (cur)
{
if (cur->_colour == BLACK)
{
blackCount++;
}
cur = cur->_left;
}
// 判断是否满足红黑树的性质, k 用来记录路径中黑色节点的个数
size_t k = 0;
return _IsRBTree(_root, k, blackCount);
}
bool _IsRBTree(Node *root, size_t k, size_t blackCount)
{
// 走到 nullptr 之后, 判断 k 和 blackCount 是否相等
if (root == nullptr)
{
// 最终黑色节点个数
if (blackCount != k)
{
std::cout << "违反性质四: 每条路径中黑色节点的个数必须相等" << std::endl;
return false;
}
return true;
}
// 统计黑色节点个数
if (root->_colour == BLACK)
{
k++;
}
// 检测当前节点与其父亲节点是否都为红色
Node *parent = root->_parent;
if (parent && parent->_colour == RED && root->_colour == RED)
{
std::cout << "违反了性质三: 红色节点的孩子必须是黑色" << std::endl;
return false;
}
return _IsRBTree(root->_left, k, blackCount) && _IsRBTree(root->_right, k, blackCount);
}
private:
Node *_root;
};
}
5.2、Set.hpp
#pragma once
#include "RBTree.hpp"
namespace Lenyiin
{
// Set 容器的实现，依赖于红黑树
template <class K>
class Set
{
// 用于从节点中获取键值的仿函数
struct SetKeyOfT
{
const K &operator()(const K &k)
{
return k;
}
};
public:
// 定义迭代器类型，支持遍历和访问集合中的元素
// 这里RBTree<K, K, SetKeyOfT>::iterator还没有实例化, 系统找不到, typename告诉编译器现在先不着急找
typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;
typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;
// 返回指向第一个元素的迭代器
iterator begin()
{
return _tree.begin();
}
// 返回指向尾后位置的迭代器
iterator end()
{
return _tree.end();
}
// const 版本的迭代器
const_iterator begin() const
{
return _tree.begin();
}
const_iterator end() const
{
return _tree.end();
}
// 插入元素，返回插入结果
std::pair<iterator, bool> Insert(const K &key)
{
return _tree.Insert(key);
}
// 删除元素，返回是否删除成功
bool Erase(const K &key)
{
return _tree.Erase(key);
}
// 查找元素，返回指向该元素的迭代器
iterator Find(const K &key)
{
return _tree.Find(key);
}
// 校验红黑树的合法性
bool IsRBTree()
{
return _tree.IsRBTree();
}
private:
// 底层红黑树实例
RBTree<K, K, SetKeyOfT> _tree;
};
}
5.3、Map.hpp
#pragma once
#include "RBTree.hpp"
namespace Lenyiin
{
// Map 容器的实现，依赖于红黑树
template <class K, class V>
class Map
{
// 用于从节点中获取键值的仿函数
struct MapKeyOfT
{
const K &operator()(const std::pair<K, V> &kv)
{
return kv.first; // 返回键作为红黑树的比较依据
}
};
public:
// 定义迭代器类型，支持遍历和访问集合中的元素
typedef typename RBTree<K, std::pair<K, V>, MapKeyOfT>::iterator iterator;
typedef typename RBTree<K, std::pair<K, V>, MapKeyOfT>::const_iterator const_iterator;
// 返回指向第一个元素的迭代器
iterator begin()
{
return _tree.begin();
}
// 返回指向尾后位置的迭代器
iterator end()
{
return _tree.end();
}
// const 版本的迭代器
const_iterator begin() const
{
return _tree.begin();
}
const_iterator end() const
{
return _tree.end();
}
// 插入元素，返回插入结果
std::pair<iterator, bool> Insert(const std::pair<K, V> &kv)
{
return _tree.Insert(kv);
}
// 删除元素，返回是否删除成功
bool Erase(const K &key)
{
return _tree.Erase(key);
}
// 查找元素，返回指向该元素的迭代器
iterator Find(const K &key)
{
return _tree.Find(key);
}
// [] 下标运算符
V &operator[](const K &key)
{
std::pair<iterator, bool> ret = _tree.Insert(std::make_pair(key, V()));
return ret.first->second;
}
// 校验红黑树的合法性
bool IsRBTree()
{
return _tree.IsRBTree();
}
private:
RBTree<K, std::pair<K, V>, MapKeyOfT> _tree;
};
}
5.4、Main.cc
#include <iostream>
#include <set>
#include <map>
#include "Set.hpp"
#include "Map.hpp"
using namespace std;
using namespace Lenyiin;
// 序列式容器: vector/list/string/deque/array/forward_list
// 关联式容器: set/multiset/map/multimap/unordered_set/unordered_multiset/unordered_map/unordered_multimap
void test_set()
{
set<int> s1; // set默认排序为从小到大 set底层是搜索树
s1.insert(10);
s1.insert(20);
s1.insert(5);
s1.insert(2);
s1.insert(1);
s1.insert(8);
s1.insert(14);
s1.insert(44);
s1.insert(23);
s1.insert(0);
s1.insert(2);
s1.insert(1);
s1.insert(8);
s1.insert(14);
// 排序 + 去重
set<int>::iterator it = s1.begin();
while (it != s1.end())
{
//*it = 100; // set中的元素是只读的，不能修改
cout << *it << " ";
it++;
}
cout << endl;
// 范围for
for (auto e : s1)
{
cout << e << " ";
}
cout << endl;
// 拷贝构造 底层默认是一个深拷贝
set<int> s2(s1);
for (auto e : s2)
{
cout << e << " ";
}
cout << endl;
// 删除
// find()是成员函数，只能用于set/multiset/map/multimap
// set<int>::iterator pos = s2.find(5);
auto pos = s2.find(5);
// find()是泛型算法，可以用于所有容器
// s.find() O(logN) s.begin() O(1) s.end() O(1)
// find(s.begin(), s.end(), 5) O(N) 效率会低不少
// auto pos = find(s2.begin(), s2.end(), 5);
if (pos != s2.end())
{
s2.erase(pos);
}
for (auto e : s2)
{
cout << e << " ";
}
cout << endl;
// 或者直接删
s2.erase(8);
s2.erase(80); // 和迭代器的区别在于：删除不存在的元素，不会报错
for (auto e : s2)
{
cout << e << " ";
}
cout << endl;
}
void test_map1()
{
map<int, int> m1;
m1.insert(pair<int, int>(1, 1)); // pair是一个模板类，可以用来创建pair对象
m1.insert(pair<int, int>(3, 3));
m1.insert(pair<int, int>(2, 2));
m1.insert(pair<int, int>(5, 5));
m1.insert(pair<int, int>(6, 6));
m1.insert(pair<int, int>(4, 4)); // pair构造函数，构造一个匿名对象，然后插入到map中
// 日常大家喜欢用make_pair()来构造pair对象，因为他不用声明模板参数，编译器自动推
m1.insert(make_pair(7, 7)); // 函数模板构造一个pair对象
map<int, int>::iterator it = m1.begin();
while (it != m1.end())
{
// cout << *it << " "; // C++不支持返回两个数
cout << (*it).first << " " << (*it).second << endl; // operator*()返回的是节点中值的引用
cout << it->first << " " << it->second << endl; // operator->()返回的是节点的指针 也就是pair<k, v>的指针
it++;
}
cout << endl;
// 范围for
for (auto &e : m1)
{
cout << e.first << " " << e.second << endl;
}
cout << endl;
}
void test_map2()
{
std::map<std::string, std::string> dirt;
dirt.insert(pair<std::string, std::string>("sort", "排序"));
dirt.insert(make_pair("string", "字符串"));
dirt.insert(make_pair("left", "左边")); // 按照ASCII码排序
std::map<std::string, std::string>::iterator it = dirt.begin();
while (it != dirt.end())
{
cout << it->first << " " << it->second << endl;
it++;
}
cout << endl;
}
void test_map3()
{
// 统计单词出现的次数
string strArr[] = {"西瓜", "苹果", "西瓜", "苹果", "西瓜", "香蕉", "西瓜", "樱桃", "西瓜", "苹果",
"西瓜", "苹果", "西瓜", "香蕉", "西瓜", "樱桃", "西瓜", "苹果", "西瓜", "苹果", "西瓜", "香蕉",
"西瓜", "樱桃", "西瓜", "苹果", "西瓜", "苹果", "西瓜", "香蕉", "西瓜", "樱桃", "西瓜", "苹果",
"西瓜", "苹果", "西瓜", "香蕉", "西瓜", "樱桃", "西瓜", "苹果", "西瓜", "苹果", "西瓜", "香蕉"};
map<string, int> countMap;
// 第一种方法
for (auto &str : strArr)
{
map<string, int>::iterator pos = countMap.find(str);
if (pos != countMap.end())
{
pos->second++;
}
else
{
countMap.insert(make_pair(str, 1));
}
}
for (auto &e : countMap)
{
cout << e.first << " " << e.second << endl;
}
cout << endl;
// 第二种方法
for (auto &str : strArr)
{
pair<map<string, int>::iterator, bool> ret = countMap.insert(make_pair(str, 1));
if (ret.second == false) // 插入失败，说明已经存在
{
ret.first->second++; // 迭代器指向的是插入的元素
}
}
for (auto &e : countMap)
{
cout << e.first << " " << e.second << endl;
}
cout << endl;
// 第三种方法
for (auto &str : strArr)
{
// 1、如果水果不在map中，则[]会插入pair<str, 0>, 返回映射对象（次数）的引用进行++
// 2、如果水果在map中，则[]会返回水果对应的映射对象（次数）的引用，对它进行++
countMap[str]++;
}
countMap["葡萄"]; // 插入 一般不这么用
countMap["葡萄"] = 100; // 修改
cout << countMap["葡萄"] << endl; // 查找
countMap["哈密瓜"] = 5; // 插入 + 修改
// 一般使用operator[]去
// 1、插入 + 修改
// 2、修改
// 一般不会用他去做查找，因为如果key不在，会插入数据。
for (auto &e : countMap)
{
cout << e.first << " " << e.second << endl;
}
cout << endl;
}
void test_multi()
{
// multiset根set的区别就是允许键值冗余
multiset<int> s1; // 使用和set一样，只是multiset可以存放重复的元素
s1.insert(10);
s1.insert(20);
s1.insert(5);
s1.insert(2);
s1.insert(1);
s1.insert(8);
s1.insert(8);
s1.insert(14);
s1.insert(44);
s1.insert(23);
s1.insert(0);
s1.insert(2);
s1.insert(1);
s1.insert(8);
s1.insert(8);
s1.insert(14);
for (auto e : s1)
{
cout << e << " ";
}
cout << endl;
auto pos = s1.find(8); // 查找到的是重复元素的第一个元素地址
cout << *pos << endl;
pos++;
cout << *pos << endl;
pos++;
cout << *pos << endl;
pos++;
cout << *pos << endl;
pos++;
cout << *pos << endl;
// multimap和map的区别和上面是一样的
multimap<string, int> mm;
mm.insert(make_pair("苹果", 1));
mm.insert(make_pair("苹果", 1));
mm.insert(make_pair("苹果", 3));
mm.insert(make_pair("西瓜", 2));
mm.insert(make_pair("西瓜", 1));
for (auto &e : mm)
{
cout << e.first << " " << e.second << endl;
}
cout << endl;
}
// 自己实现的 Set Map 测试
void test_Set()
{
Set<int> s;
s.Insert(3);
s.Insert(4);
s.Insert(1);
s.Insert(2);
s.Insert(2);
s.Insert(5);
// 迭代器遍历
Set<int>::iterator it = s.begin();
while (it != s.end())
{
cout << *it << " ";
++it;
}
cout << endl;
// 删除
s.Erase(4);
// for
for (const auto &k : s)
{
cout << k << " ";
}
cout << endl;
cout << "IsRBTree? " << (s.IsRBTree() ? "true" : "false") << endl;
}
void test_Map1()
{
// int a[] = {16, 3, 7, 11, 9, 26, 18, 14, 15};
int a[] = {4, 2, 6, 1, 3, 5, 15, 7, 16, 14};
Map<int, int> m;
for (const auto &e : a)
{
m.Insert(make_pair(e, e));
}
// 迭代器遍历
Map<int, int>::iterator it = m.begin();
while (it != m.end())
{
cout << it->first << ":" << it->second << endl;
++it;
}
cout << endl;
// 删除
m.Erase(4);
// 范围for遍历 for_each 底层也是调用的迭代器实现的遍历
for (const auto &kv : m)
{
cout << kv.first << ":" << kv.second << endl;
}
cout << endl;
cout << "IsRBTree? " << (m.IsRBTree() ? "true" : "false") << endl;
}
void test_Map2()
{
// 统计单词出现的次数
string strArr[] = {"西瓜", "苹果", "西瓜", "苹果", "西瓜", "香蕉", "西瓜", "樱桃", "西瓜", "苹果",
"西瓜", "苹果", "西瓜", "香蕉", "西瓜", "樱桃", "西瓜", "苹果", "西瓜", "苹果", "西瓜", "香蕉",
"西瓜", "樱桃", "西瓜", "苹果", "西瓜", "苹果", "西瓜", "香蕉", "西瓜", "樱桃", "西瓜", "苹果",
"西瓜", "苹果", "西瓜", "香蕉", "西瓜", "樱桃", "西瓜", "苹果", "西瓜", "苹果", "西瓜", "香蕉"};
Map<string, int> countMap;
for (auto &str : strArr)
{
countMap[str]++;
}
// 迭代器遍历
Map<string, int>::iterator it = countMap.begin();
while (it != countMap.end())
{
cout << it->first << ":" << it->second << endl;
++it;
}
cout << endl;
// 删除
countMap.Erase("苹果");
for (const auto &kv : countMap)
{
cout << kv.first << ":" << kv.second << endl;
}
cout << endl;
cout << "IsRBTree? " << (countMap.IsRBTree() ? "true" : "false") << endl;
}
void test_Map3()
{
Lenyiin::Map<int, std::string> map;
// 插入键值对
map.Insert(std::make_pair(1, "one"));
map.Insert(std::make_pair(2, "two"));
map.Insert(std::make_pair(3, "three"));
// 通过 operator[] 访问或插入
map[4] = "four";
std::cout << "Key 4: " << map[4] << std::endl;
// 查找元素
auto it = map.Find(2);
if (it != map.end())
{
std::cout << "Found: " << it->first << " -> " << it->second << std::endl;
}
// 删除元素
map.Erase(1);
// 验证红黑树
cout << "IsRBTree? " << (map.IsRBTree() ? "true" : "false") << endl;
}
int main()
{
// test_set();
// test_map1();
// test_map2();
// test_map3();
// test_multi();
test_Set();
test_Map1();
test_Map2();
test_Map3();
return 0;
}
5.5、测试结果
6、拓展
在深入理解了 Set 和 Map 容器的基本实现之后，我们可以探讨一些与其相关的高级话题，帮助提升对这些容器底层机制和性能优化的理解。以下是几个关键的拓展话题：
6.1、红黑树与哈希表的比较
Set 和 Map 容器的底层实现基于红黑树（RBTree），而 C++ 标准库还提供了基于哈希表的 unordered_set 和 unordered_map。了解红黑树和哈希表的特性差异，对于选择合适的数据结构非常重要。
6.1.1、时间复杂度比较
- 红黑树：红黑树是一种平衡二叉搜索树，
Set和Map基于红黑树实现的容器在最坏情况下的查找、插入和删除操作的时间复杂度均为O(log n)。这是因为红黑树通过自动平衡机制，保证树的高度不会超过O(log n)。 - 哈希表：哈希表是一种基于哈希函数的散列结构，
unordered_set和unordered_map容器的查找、插入和删除操作在平均情况下的时间复杂度为O(1)，但在最坏情况下可能退化到O(n)，这通常发生在哈希冲突过多的情况下。
6.1.2、内存开销比较
- 红黑树：红黑树的节点存储了键值对和用于平衡的额外信息（如节点的颜色等），因此相较于哈希表，红黑树的内存开销较大。同时，红黑树需要维护指针来存储左右子节点。
- 哈希表：哈希表的内存主要用于存储键值对和哈希桶，当负载因子过高时，哈希表可能需要进行重新哈希（rehashing），这会导致额外的内存开销和性能开销。
6.1.3、适用场景比较
- 红黑树的适用场景：当需要有序的数据存储时，
Set和Map容器基于红黑树实现的特性使得它们可以保持键的顺序。在一些需要频繁进行范围查询（如查找某个区间范围内的元素）或需要对数据进行排序的场景下，红黑树是理想的选择。 - 哈希表的适用场景：当只需要快速查找、插入和删除元素时，
unordered_set和unordered_map提供了常数时间复杂度的操作，适用于数据无序且不需要排序的场景。
6.2、C++ Set 和 Map 的内存管理优化
内存管理是容器设计中的一个重要话题。对于 Set 和 Map，因为它们基于红黑树实现，内存管理的效率直接影响容器的性能。以下是一些常见的内存管理优化策略：
6.2.1、自定义分配器（Allocator）
C++ 标准库的 set 和 map 容器都支持自定义分配器。分配器用于控制容器在内存中分配和释放节点的方式。对于大多数应用场景，默认的分配器 std::allocator 就足够了，但在高性能应用场景中，特别是内存频繁分配和释放的情况下，自定义分配器可以极大提高性能。例如，基于内存池(memory pool)的分配器可以减少内存分配和释放的系统调用次数，从而提高效率。
示例：
template <typename T>
class CustomAllocator {
// 自定义分配器实现
};
将自定义分配器应用于 Set 和 Map 的方式：
std::set<int, std::less<int>, CustomAllocator<int>> customSet;
std::map<int, std::string, std::less<int>, CustomAllocator<std::pair<const int, std::string>>> customMap;
通过减少系统调用次数，自定义内存池可以显著提升 Set 和 Map 的内存分配效率，特别是在大量节点插入和删除的场景下。
6.2.2、自定义比较器与哈希函数
红黑树的插入、删除和查找操作依赖于节点之间的比较。在默认情况下，Set 和 Map 使用的是默认的 < 运算符进行比较。如果我们能够根据实际数据特点自定义比较器，便能提高比较效率，进而提升整体性能。
例如，在处理复合数据类型（如 std::pair）时，通常会先比较第一个元素 (key)，如果相同，再比较第二个元素 (value)。在这种情况下，如果我们可以预先判断某些键值对是不需要比较的，可以优化比较器的逻辑。
通过自定义比较器，特别是针对复杂类型的对象，可以减少不必要的比较开销，从而提升性能。
6.2.3、节点内存布局优化
在红黑树的实现中，每个节点通常包含左右子节点的指针、父节点的指针、节点的颜色信息以及实际存储的键值对数据。通过优化节点的内存布局，可以有效减少节点占用的内存空间。
一种常见的优化方式是将节点的颜色信息嵌入指针中（通过最低位存储颜色信息），从而减少额外的内存开销。此外，可以通过缓存局部性优化节点的存储顺序，减少在树遍历过程中缓存失效的情况。
6.3、Map 的延迟更新与高并发场景优化
在高并发场景中，Map 作为共享数据结构的性能瓶颈常常受到关注。传统的红黑树实现的 Map 容器在并发修改时需要加锁，从而可能导致性能下降。为了解决这个问题，可以引入延迟更新(lazy update)和细粒度锁等优化手段。
6.3.1、延迟删除（Lazy Deletion）
在高性能场景中，我们可以通过延迟删除 (lazy deletion) 来优化删除操作的性能。在延迟删除的策略中，删除操作并不立即从红黑树中移除节点，而是将节点标记为 “已删除” ，并在树的后续操作中（如树的遍历或插入新节点时）实际执行删除操作。
延迟删除可以减少树的频繁重构（即减少颜色调整和旋转操作），从而优化删除操作的性能。
struct Node {
bool isDeleted; // 用于标记节点是否已删除
// 其他节点数据
};
在这种优化策略下，我们可以将删除操作的时间开销分散到后续操作中，实现更平滑的性能表现。
延迟更新是一种优化策略，它允许在读操作时暂时不进行更新，只有在需要访问或修改数据时才执行更新操作。例如，当多个线程并发插入和查找数据时，可以使用一个暂存区暂时保存插入的数据，避免立即更新红黑树结构，等到后续的批量操作时再执行合并更新。这可以显著减少锁竞争，提高并发性能。
6.3.2、并发优化
当 Set 和 Map 容器在多线程环境中使用时，锁的使用会显著影响性能。默认情况下，红黑树在插入、删除和查找操作时需要进行全树锁定，保证线程安全。然而，全树锁定会导致严重的性能瓶颈，特别是在高并发场景中。
一种优化方式是使用细粒度锁，即只对红黑树的局部区域进行锁定，而不是锁住整个树。例如，对于红黑树，可以将锁粒度从全树锁细化到单节点锁，从而允许多个线程同时对树的不同部分进行修改。同时，一些无锁数据结构(lock-free data structures) 也可以在并发场景中替代传统的加锁机制，以提高性能。
另一种方案是采用读写锁（读者-写者锁），允许多个线程同时进行读操作，而在写操作时仍然使用排他锁。这样可以在读操作较多、写操作较少的场景下大幅提升性能。
6.3.3、增强缓存局部性
红黑树的节点分布通常较为分散，因此在访问节点时，可能会触发较多的缓存未命中(cache misses)，从而影响性能。通过优化节点的内存布局，可以增强缓存局部性，减少缓存未命中的发生。
一种优化策略是将相邻节点尽可能存储在连续的内存区域中。例如，使用数组模拟二叉树结构，虽然增加了内存管理的复杂度，但可以大幅提高树的遍历和查询效率。
struct RBTreeNode {
RBTreeNode* left;
RBTreeNode* right;
// 其他成员
};
RBTreeNode nodeArray[1000]; // 将节点存储在连续的内存中
6.4、技术展望
6.4.1、支持更高性能的并行与并发操作
随着多核处理器的普及，如何更好地支持并行和并发操作，将是 Set 和 Map 容器发展的重要方向之一。当前基于红黑树的实现是单线程操作的，尽管可以通过细粒度锁或者读写锁进行优化，但在高并发场景中，性能依然存在瓶颈。未来的发展可能包括以下几个方向：
- 无锁结构：通过乐观并发控制或者无锁（lock-free）算法来避免线程之间的竞争，从而提高并发性能。这类结构通常依赖于复杂的原子操作和CAS（Compare-And-Swap）指令，可以极大提升
Set和Map在多线程环境下的性能。 - 事务内存：事务内存（Transactional Memory）是一种硬件和软件结合的技术，可以为并发操作提供更高的抽象层次，使容器的并发控制更加高效且易于维护。通过事务内存，多个线程可以同时执行插入、删除等操作，而无需手动管理锁。
- 分区并行化（Sharding）：未来的
Set和Map容器可以通过分区将数据分散到多个子树上，并发操作仅限于某个分区，减少全局锁的使用，从而提升并行性能。类似技术在分布式数据库和NoSQL系统中已有成熟应用，可以借鉴应用到容器设计中。
6.4.2、与新硬件的结合
当前的容器实现主要是基于传统的内存访问模型，然而随着硬件技术的演进，特别是非易失性内存（NVM）和存储级内存（SCM）的出现，Set 和 Map 容器有望得到进一步的性能提升。
- 非易失性内存（NVM）：NVM结合了内存的速度和硬盘的持久性。在未来的容器实现中，
Set和Map可以利用NVM来实现持久化存储而无需频繁的磁盘IO操作。这将极大提升存储密集型应用的性能，并降低数据恢复的复杂度。 - 异构计算与加速器支持：未来
Set和Map容器可以结合GPU、FPGA等硬件加速器，优化大量数据并行处理的效率。例如，某些并行插入、批量查找等操作可以通过GPU加速完成，而FPGA则可以针对特定应用场景进行定制化优化。
6.4.3、动态数据结构与自适应优化
未来的容器可以更加智能和自适应，以适应不同的数据规模和访问模式。传统的红黑树结构在插入和删除操作频繁时性能良好，但在大量顺序数据的插入场景中，仍可能会出现局部性能瓶颈。因此，自适应数据结构将成为未来容器优化的重要方向。
- 跳表（Skip List）与红黑树的混合结构：跳表在顺序插入时的性能通常优于红黑树，而红黑树在不均匀分布的数据下表现更好。未来容器可以结合跳表和红黑树的优点，在运行时根据数据特点动态调整底层的数据结构，实现性能的自适应优化。
- 自平衡与缓存优化：容器可以根据运行时数据的访问模式，动态地进行结构优化和缓存调整。例如，热数据（访问频繁的数据）可以被缓存到快速访问的层级，而冷数据则被缓存在较慢的存储中。这种分层结构将有助于在数据规模急剧增长的情况下，保持容器的高效性。
6.4.4、更智能的泛型编程与概念化设计
C++20 引入了 Concepts（概念）机制，这为泛型编程带来了新的设计思路。未来的 Set 和 Map 容器可以进一步利用 Concepts，使得容器在编译时就能检查输入数据的类型约束，并在不同的数据类型和算法需求下自动选择最优的实现。
- 智能类型推断与优化：通过 Concepts，
Set和Map可以在编译期根据传入的数据类型进行推断和优化。例如，对于浮点型数据，可以自动选择更适合处理浮点数的比较器和存储策略；对于字符串型数据，容器可以自动选择字符串压缩算法，减少内存占用。 - 领域特定优化：未来的容器可以根据不同的应用领域进行定制优化。例如，在处理金融数据时，可以集成专门优化时间序列数据的结构；在处理网络数据时，可以结合Bloom Filter等高效过滤算法进行优化。
6.4.5、分布式与跨节点容器实现
随着云计算和分布式系统的发展，未来 Set 和 Map 容器将不再局限于单机内存的操作，而是扩展到跨节点、跨数据中心的分布式操作。对于分布式容器的设计，以下方向可能成为未来的主流：
- 分布式哈希表（DHT）与红黑树结合：分布式哈希表（如Chord, Pastry等）在分布式存储中表现优秀，但其并不保证数据的顺序性。未来的
Set和Map容器可以结合DHT和红黑树，将数据分布在多个节点上，同时保持全局的有序性。 - 跨节点事务一致性：为了支持分布式事务，
Set和Map容器可以结合现代的分布式一致性协议（如Paxos, Raft等），实现跨节点的强一致性存储。通过引入事务性操作，容器可以保证在多节点插入、删除操作中的数据一致性，满足高可用性的需求。
7、总结
通过对基于红黑树实现的 Set 和 Map 容器进行详细分析和实现，我们深入探讨了关联容器在 C++ 中的核心原理、设计模式、以及性能优化的方向。这两个容器都是标准库中非常重要的工具，在实际应用中广泛用于高效地存储和检索有序数据。基于红黑树的数据结构，Set 和 Map 保持了良好的时间复杂度，能够在 O(log n) 的时间内完成插入、删除和查找操作，保证了较高的运行效率。
7.1、基于红黑树的设计
我们通过红黑树作为底层数据结构，确保了 Set 和 Map 的平衡性，避免了数据操作过程中出现最坏情况。红黑树在插入和删除操作后，能够通过自平衡机制（旋转和颜色调整）确保树的高度始终保持在 O(log n)。这一点对于大规模数据的处理尤为重要，避免了线性时间的退化。
在 Set 容器中，我们使用了模板类 RBTree 进行封装，并通过函数对象 SetKeyOfT 来定义键的获取方式，使得 Set 能够存储任意类型的唯一键。在 Map 容器中，通过类似的方式，我们设计了 MapKeyOfT 来从键值对中提取键，从而实现了键值对的存储和操作。
7.2、插入与删除操作的细节
红黑树的插入和删除操作是容器设计的核心部分。在插入时，InsertFixUp 通过颜色调整和旋转来维持红黑树的五条性质，确保新节点插入后树依然保持平衡。在删除操作中，DeleteFixUp 同样通过类似的机制恢复树的平衡。通过这些操作，我们保证了 Set 和 Map 的数据结构不会退化为线性结构，从而提升了查找和更新操作的效率。
7.3、性能分析与优化
我们在实现过程中分析了 Set 和 Map 的性能。在理论上，红黑树的查找、插入和删除操作都能够保持 O(log n) 的时间复杂度。然而，在具体实现中，红黑树的性能也会受到许多因素的影响，包括树的高度、节点的存储布局、以及内存访问的局部性等。
为进一步优化 Set 和 Map 的性能，我们可以采取一些措施：
- 缓存优化：通过合理布局节点的数据结构，可以提升缓存命中率，从而加快内存访问速度。
- 并行化操作：在多线程环境下，我们可以引入读写锁或无锁结构，允许并发地进行插入和查找操作，从而提高并发性能。
- 减少旋转次数：在插入和删除操作中，通过优化红黑树的旋转逻辑，减少不必要的旋转次数，从而提升整体性能。
7.4、实际应用场景
Set 和 Map 容器在许多实际场景中都有广泛的应用。例如，在数据库系统中，Map 容器可以用来快速检索键值对，实现索引查找。在编译器设计中，Set 容器可以用来维护符号表，存储唯一的标识符。在许多算法中，Set 和 Map 都可以用来高效地存储和处理动态数据，保持数据的有序性和唯一性。
7.5、未来发展方向
Set 和 Map 容器未来的发展方向可以结合新兴的硬件技术和软件需求进行扩展：
- 硬件加速：随着硬件的发展，诸如
NVM（非易失性内存）和持久化内存等新型存储介质的引入，容器的数据存储和检索性能将会得到极大提升。Set和Map容器可以结合这些新型硬件进行优化，实现持久化数据结构。 - 分布式系统中的扩展：在分布式环境下，我们可以将
Set和Map容器扩展为支持分布式哈希表的形式，实现跨节点的数据存储和查找。这对于大规模数据处理和云计算平台上的分布式应用将是非常重要的功能。 - 泛型编程的增强：随着
C++20引入Concepts概念，未来的Set和Map容器可以通过Concepts进行更为灵活的泛型约束，提升编译时类型检查的精确性，进一步增强代码的可读性和鲁棒性。
7.6、总结
Set 和 Map 容器作为关联容器的代表，结合了红黑树这一高效的平衡二叉树结构，提供了稳定的 O(log n) 时间复杂度。通过合理的设计和优化，我们能够确保容器在大规模数据处理场景下的高效性和可靠性。未来的 Set 和 Map 容器将不断适应新技术的变化，朝着更高性能、更强安全性以及更广泛的应用场景发展。
希望这篇博客对您有所帮助，也欢迎您在此基础上进行更多的探索和改进。如果您有任何问题或建议，欢迎在评论区留言，我们可以共同探讨和学习。更多知识分享可以访问我的个人博客网站 ： https://blog.lenyiin.com/ 。本博客所涉及的代码也可以访问我的 git 仓库获取 ：https://git.lenyiin.com/Lenyiin/Set_Map 。也可以从 CSDN 下载区下载
标签：黑树,Set,const,cur,parent,C++,插入,红黑树,节点 From： https://blog.csdn.net/mmlhbjk/article/details/142470727