目录
1. 引言
在 C++ STL（标准模板库）中，map 和 set 是两种非常重要的关联容器，它们基于 红黑树（Red-Black Tree） 实现，提供了高效的查找、插入和删除操作。本文将深入探讨它们的 底层原理、使用方法、性能分析，并结合 实际代码示例 进行讲解。
2. Map 详解
2.1 Map 的基本概念
map 是一种 键值对（Key-Value） 存储结构，其中：
- Key 是唯一的，不能重复。
- Value 可以重复。
- 默认按 Key 升序 排序（基于
<运算符）。
2.2 Map 的底层实现
map 的底层通常采用 红黑树（RB-Tree），保证：
- 插入、删除、查找 的时间复杂度均为 O(log N)。
- 自动维护 Key 的有序性。
2.3 Map 的基本操作
（1）声明与初始化
#include <map>
using namespace std;
map<string, int> studentScores; // Key: string, Value: int
studentScores["Alice"] = 95;
studentScores["Bob"] = 88;
（2）插入元素
studentScores.insert({"Charlie", 90}); // C++11 方式
（3）查找元素
auto it = studentScores.find("Alice");
if (it != studentScores.end()) {
cout << "Alice's score: " << it->second << endl;
}
（4）遍历 Map
for (const auto& pair : studentScores) {
cout << pair.first << ": " << pair.second << endl;
}
（5）删除元素
studentScores.erase("Bob"); // 按 Key 删除
auto it = studentScores.find("Charlie");
if (it != studentScores.end()) {
studentScores.erase(it); // 按迭代器删除
}
3. Set 详解
3.1 Set 的基本概念
set 是一种 唯一元素集合，特点：
- 元素唯一，不允许重复。
- 默认按 升序 排序。
3.2 Set 的底层实现
set 同样基于 红黑树，保证：
- 插入、删除、查找 的时间复杂度为 O(log N)。
- 自动去重并排序。
3.3 Set 的基本操作
（1）声明与初始化
#include <set>
using namespace std;
set<int> numbers = {3, 1, 4, 1, 5}; // 自动去重并排序：{1, 3, 4, 5}
（2）插入元素
numbers.insert(2); // {1, 2, 3, 4, 5}
numbers.emplace(6); // 更高效
（3）查找元素
auto it = numbers.find(3);
if (it != numbers.end()) {
cout << "Found: " << *it << endl;
}
（4）遍历 Set
for (int num : numbers) {
cout << num << " ";
}
（5）删除元素
numbers.erase(4); // 按值删除
auto it = numbers.find(2);
if (it != numbers.end()) {
numbers.erase(it); // 按迭代器删除
}
4. Map 和 Set 的对比
| 特性 | map |
set |
|---|---|---|
| 存储方式 | Key-Value 键值对 | 仅存储 Key |
| 查找方式 | 按 Key 查找 Value | 直接查找元素 |
| 去重 | Key 唯一 | 元素唯一 |
| 排序 | 默认按 Key 升序 | 默认按元素升序 |
| 底层结构 | 红黑树（RB-Tree） | 红黑树（RB-Tree） |