本文详细解析了 C++ STL 中的 set 和 map 关联式容器。内容涵盖基本概念、底层红黑树实现、常用操作（插入、查找、删除）、自定义排序规则以及 multiset/multimap 的区别。通过代码示例展示了如何求数组交集、构建词频统计及检测链表环等应用场景，并提供了性能优化建议，如使用 unordered 系列容器或 emplace 方法。适合希望深入理解 C++ 标准模板库的开发者阅读。
C++ 标准模板库（STL）中的关联式容器以其强大的功能和高效性成为开发者解决复杂数据组织问题的重要工具。其中， 和 是最常用的两类关联容器。本文从基本特性、底层实现、用法详解、高级案例以及性能优化等多个角度，详细解读它们的设计与使用。
setmap关联式容器是一类根据关键字组织和管理数据的容器。与序列式容器（如 vector 和 list）相比，关联式容器的主要区别如下：
| 特性 | 关联式容器（set/map） | 序列式容器（vector/list） |
|---|---|---|
| 数据存储顺序 | 按关键字排序 | 按插入顺序 |
| 数据访问复杂度 | O(log N) | O(1) 或 O(N) |
| 是否支持随机访问 | 否 | 是 |
| 是否支持按索引访问 | 否 | 是 |
关联式容器分为有序和无序两类：
set 和 map，基于平衡二叉树（红黑树）实现，数据按排序规则组织。unordered_set 和 unordered_map，基于哈希表实现，提供更高效的查找速度，但不保证元素顺序。set 中的关键字即为数据本身，而 map 则以键值对形式存储数据。set 容器详解set 是一种集合数据结构，用于存储唯一且自动排序的元素。它的主要特点如下：
set 支持双向迭代器，不支持随机访问。红黑树是一种平衡二叉搜索树，满足以下性质：
nullptr 或 NIL 节点）是黑色。在 set 和 map 中，红黑树用来高效实现元素的有序存储和快速查找。
set 提供以下几种构造方式：
自定义比较规则：
set<int, greater<int>> s = {3, 1, 4}; // 按降序排序
迭代器区间构造：从其他容器的元素构造集合。
vector<int> v = {1, 2, 3, 4}; set<int> s(v.begin(), v.end());
初始化列表构造：直接用 {} 初始化集合。
set<int> s = {3, 1, 4, 1, 5, 9}; // 重复元素自动去重
默认构造：创建一个空集合。
set<int> s;
| 操作 | 函数 | 复杂度 | 说明 |
|---|---|---|---|
| 插入 | insert(value) | O(log N) | 插入元素，若已存在则插入失败 |
| 删除 | erase(value) | O(log N) | 删除指定元素 |
| 查找 | find(value) | O(log N) | 返回迭代器，指向目标元素 |
| 统计 | count(value) | O(log N) | 判断元素是否存在，结果为 0 或 1 |
| 遍历 | begin(), end() | O(N) | 正向迭代访问所有元素 |
| 下界/上界 | lower_bound()/upper_bound() | O(log N) | 返回 >= / > 某值的第一个元素的迭代器 |
set<int> s; auto res = s.insert(10); // 插入 10 if (res.second) { cout << "插入成功" << endl; } else { cout << "插入失败" << endl; }
if (s.find(20) != s.end()) { cout << "找到元素 20" << endl; }
s.erase(10); // 删除值为 10 的元素
for (int x : s) { cout << x << " "; // 正向遍历 } for (auto it = s.rbegin(); it != s.rend(); ++it) { cout << *it << " "; // 反向遍历 }
set 默认按升序排序，使用仿函数或 std::greater 可修改排序规则：
set<int, greater<int>> s = {3, 1, 4};
删除值在 [low, high) 范围内的所有元素：
s.erase(s.lower_bound(10), s.upper_bound(50));
vector<int> intersection(const vector<int>& nums1, const vector<int>& nums2) { set<int> s1(nums1.begin(), nums1.end()); set<int> s2(nums2.begin(), nums2.end()); vector<int> result; for (int x : s1) { if (s2.count(x)) result.push_back(x); } return result; }
multiset 的区别与应用multiset 与 set 的区别在于：
multiset 允许存储重复元素。set 相同，但返回的结果会包含重复项。multiset<int> ms = {1, 2, 2, 3}; ms.insert(2); // 再次插入 2
map 容器详解map 是一个关联式容器，用于存储键值对（key-value）。与 set 相比，map 不仅存储键（key），还存储与每个键关联的值（value）。
map 的主要特点包括：
map 中都是唯一的。set 不同，map 中存储的键值对支持通过键快速查找对应的值。map<int, string> m; m[1] = "apple"; // 插入键值对 (1, "apple") m[2] = "banana"; // 插入键值对 (2, "banana") m[3] = "cherry"; // 插入键值对 (3, "cherry")
map 使用红黑树存储数据，保证了所有元素按键值自动排序。在 map 中，每个节点存储一个 pair<const Key, T>，其中 const Key 表示键，T 表示值。红黑树的特点确保了查找、插入和删除操作的时间复杂度都为 O(log N)。
map 提供了多种构造方法，以适应不同的使用场景：
自定义比较器：通过传入自定义比较器，指定键的排序方式。
map<int, string, greater<int>> m; // 降序排序 m[2] = "banana"; m[1] = "apple";
范围构造：从另一个容器（如 set、vector 等）构造 map。
vector<pair<int, string>> v = {{1, "apple"}, {2, "banana"}}; map<int, string> m(v.begin(), v.end());
初始化列表构造：通过初始化列表直接创建 map。
map<int, string> m = {{1, "apple"}, {2, "banana"}, {3, "cherry"}};
默认构造：创建一个空 map。
map<int, string> m;
| 操作 | 函数 | 复杂度 | 说明 |
|---|---|---|---|
| 插入 | insert(pair) | O(log N) | 插入一个键值对，若已存在则插入失败 |
| 插入或修改 | operator[] | O(log N) | 插入新元素或修改已有元素的值 |
| 查找 | find(key) | O(log N) | 查找指定键，返回键值对的迭代器 |
| 统计 | count(key) | O(log N) | 查找指定键是否存在（map 中为 0 或 1） |
| 删除 | erase(key) | O(log N) | 删除指定键及其对应的值 |
| 遍历 | begin(), end() | O(N) | 正向遍历所有元素 |
| 下界/上界 | lower_bound(key)/upper_bound(key) | O(log N) | 查找大于等于某值或大于某值的第一个元素 |
查找：find 方法返回一个迭代器，指向指定键的键值对，若未找到则返回 end()。
auto it = m.find(1); if (it != m.end()) { cout << "Found: " << it->second << endl; // 输出 "apple" }
插入：可以通过 insert 方法插入新的键值对，也可以通过 operator[] 插入或修改键值对。
map<int, string> m; m.insert({1, "apple"}); m[2] = "banana"; // 插入或修改
删除某个键值对：
m.erase(1); // 删除键为 1 的元素
map 提供了多种遍历方法：
传统迭代器：
for (auto it = m.begin(); it != m.end(); ++it) { cout << it->first << ": " << it->second << endl; }
范围 for：
for (const auto& [key, value] : m) { cout << key << ": " << value << endl; }
可以通过迭代器直接修改值，operator[] 也支持修改已有键的值：
m[2] = "grape"; // 修改键为 2 的值为 "grape" auto it = m.find(2); if (it != m.end()) { it->second = "orange"; // 通过迭代器修改值 }
通过 lower_bound() 和 upper_bound() 方法，可以获取某个键的下界和上界，常用于区间查找。
lower_bound(key)：返回第一个大于等于 key 的元素。upper_bound(key)：返回第一个大于 key 的元素。map<int, string> m = {{1, "apple"}, {2, "banana"}, {3, "cherry"}}; auto lb = m.lower_bound(2); // 返回键为 2 或大于 2 的第一个元素 cout << lb->second << endl; // 输出 "banana"
如同 set，map 也可以通过自定义比较器来实现不同的排序规则。
map<int, string, greater<int>> m = {{1, "apple"}, {3, "cherry"}, {2, "banana"}}; for (const auto& [key, value] : m) { cout << key << ": " << value << endl; } // 输出：3: cherry 2: banana 1: apple
删除某个键值范围内的元素，常用于清除一段区间：
map<int, string> m = {{1, "apple"}, {2, "banana"}, {3, "cherry"}}; m.erase(m.lower_bound(2), m.upper_bound(3)); // 删除键为 2 和 3 的元素
multimap 的区别与应用multimap 是 map 的扩展，允许相同的键有多个值（即支持键的冗余）。与 map 的区别在于，multimap 在插入重复键时不会丢失数据，而 map 会自动覆盖原有键。
multimap<int, string> mm; mm.insert({1, "apple"}); mm.insert({1, "banana"}); mm.insert({2, "cherry"}); for (const auto& [key, value] : mm) { cout << key << ": " << value << endl; // 输出：1: apple 1: banana 2: cherry }
multimap 在某些场景下非常有用，例如存储学生成绩时，可能有多个学生取得相同的分数。
set 和 map参考 2.5 节中的代码示例。
map<string, int> wordCount(const vector<string>& words) { map<string, int> wordMap; for (const string& word : words) { wordMap[word]++; } return wordMap; }
bool hasCycle(ListNode* head) { set<ListNode*> visited; while (head != nullptr) { if (visited.find(head) != visited.end()) { return true; // 找到环 } visited.insert(head); head = head->next; } return false; }
unordered_map 和 unordered_set在很多查找密集型的应用中，unordered_map 和 unordered_set 基于哈希表实现，提供常数时间复杂度 O(1) 的查找和插入操作。它们的性能优势适用于不需要保持元素顺序的场景。
当插入大量数据时，可以使用 emplace() 来避免不必要的对象拷贝。emplace() 可以直接构造元素，而无需创建临时对象。
map<int, string> m; m.emplace(1, "apple"); // 不会发生拷贝
map 不支持修改键，修改键会导致数据结构破坏。因此，避免频繁修改键，而应使用新的键值对进行插入和删除。
通过本文的详细解析，我们全面了解了 C++ 中 set 和 map 容器的使用、底层实现以及高效操作技巧。掌握这些基本知识后，开发者可以灵活使用 set 和 map 来处理各种复杂的关联数据问题，从而提高程序的效率和可读性。
在实际开发中，选择合适的容器（如 map 与 unordered_map，set 与 unordered_set）可以帮助我们应对不同的数据处理需求，避免性能瓶颈。希望通过本文的学习，你能够深入掌握这些强大的容器，提升 C++ 编程技能。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online