set / map
更新时间：2026-08-27。本文是
languages/cpp/主题入门层第 36 篇（存量stl-containers拆解迁入）。set是不重复的有序集合，map是键值对的有序字典——底层都是红黑树，查找插入 O(log n)，按键有序遍历。和 C 的qsort+ 手动结构体相比，这是"开箱即用的有序字典"。
本文要回答的问题
set和map分别是什么？怎么用？- 有序容器底层是什么结构？复杂度怎么算？
map的下标访问m["key"]有什么隐藏行为？
一、map：按键找值的有序字典
#include <map>
std::map<std::string, int> scores;
scores["alice"] = 95; // 插入/更新
scores["bob"] = 88;
std::cout << scores["alice"]; // 读取：95
auto it = scores.find("bob"); // 查找
if (it != scores.end()) { /* 找到了 */ }
for (const auto& [name, score] : scores) { // 有序遍历（按键排序）
std::cout << name << ": " << score << "\n";
}map<Key, Value>：键 Key 唯一、值 Value 可重复，按键自动排序（默认升序，比较器可自定义）。常见操作全 O(log n)：插入、删除、查找、遍历有序。
隐藏行为警告：scores["alice"] = 95 看着只是赋值，其实做了两件事——如果 "alice" 不存在，operator[] 会先插入一个默认值（value 是 0/空串），再赋值。所以：
if (scores["nobody"] > 100) { ... } // 副作用：插入了 "nobody"！只想查不想要副作用，用 find 或 at（at 不存在会抛 std::out_of_range）：
auto it = scores.find("nobody");
if (it != scores.end()) { /* 存在 */ }
// scores.at("nobody"); // 不存在会抛异常二、set：不重复的有序集合
#include <set>
std::set<int> s = {5, 1, 3, 1}; // 重复的 1 会被忽略
s.insert(2);
s.erase(1);
s.size(); // 去重后的大小
if (s.count(3)) { /* 在不在集合里 */ }
for (int x : s) { /* 有序遍历：1 2 3 5 */ }set<T>：元素唯一（插入重复的自动忽略）、有序（遍历即升序）。它就是"不需要值的 map"——set<int> 等价于 map<int, bool> 的语义简化版。常用场景：去重、判断存在、保序集合。
三、底层：红黑树
map/set 底层是红黑树（自平衡二叉搜索树）：
- 查找/插入/删除都是 O(log n)，最坏情况也有保证（树保持平衡）；
- 中序遍历天然有序——所以
map遍历就是按键升序； - 代价：每个节点要存颜色标记和树指针，内存开销比
unordered_map略大（37 篇对比）。
四、set/map 与 C 对比
| 对比项 | C | C++ |
|---|---|---|
| 有序字典 | 手写结构体数组 + qsort + 二分 | std::map |
| 去重集合 | 手写逻辑 | std::set |
| 排序 | qsort 要写比较函数 | 容器自动有序 |
| 查找 | bsearch 手动二分 | .find() / .count() |
| 修改后保持有序 | 要重新排序 | 树结构自动维护 |
C 里"存一堆键值对、按键查找"要自己搭结构体、qsort、bsearch，改一个键还要考虑重排。C++ 的 map 把整件事封装成"自动维护平衡、永远有序"的容器。
五、常见用法与坑
| 用法 | 示例 | 注意 |
|---|---|---|
| 插入不覆盖 | m.emplace(k, v) | insert/emplace 已有键时不覆盖 |
| 统计词频 | m[w]++ | 简洁，但第一次会插入 0 |
| 判断存在 | m.count(k) / m.find(k) | count 只有 0/1（map） |
| 遍历 | for (auto& [k, v] : m) | 结构化绑定，41 篇细讲 |
| 自定义排序 | map<int, T, greater<int>> | 比较器可换 |
词频统计是 map 的经典应用（综合练习 61 篇会用到）：
std::map<std::string, int> freq;
for (const auto& w : words) {
freq[w]++; // 第一次插入为 0，再自增
}
// 遍历即按字母序输出词频六、与本站主线衔接
unordered_map：哈希表、平均 O(1)，纯查找场景更快，见 unordered_map / unordered_set；- 红黑树实现细节见高手层容器选型深挖；
- 下一篇对比哈希容器：什么时候 map 让位给 unordered_map。
一句话总结
map 是按键有序的字典（map<K,V>）、set 是有序去重集合，底层红黑树保证查找/插入/删除 O(log n)、遍历自动按键升序；m["key"] 找不到键时会自动插入默认值，只想查用 find/at；需要有序遍历或范围查询用 map，纯快速查找用 unordered_map（下一篇）。