C++ Map 和 Set 详解：从原理到实战应用

目录

1. 引言

2. Map 详解

2.1 Map 的基本概念

2.2 Map 的底层实现

2.3 Map 的基本操作

（1）声明与初始化

（2）插入元素

（3）查找元素

（4）遍历 Map

（5）删除元素

3. Set 详解

3.1 Set 的基本概念

3.2 Set 的底层实现

3.3 Set 的基本操作

（1）声明与初始化

（2）插入元素

（3）查找元素

（4）遍历 Set

（5）删除元素

4. Map 和 Set 的对比

---

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）