C++ STL 容器选型深挖
更新时间：2026-08-27。本文是
languages/cpp/主题高手层第 12 篇。入门篇介绍了各容器的基本用法，这篇聊"什么时候该用哪个"——选错容器，同样的操作可能差出几十倍性能。选型不看"哪个好"，而看你的数据访问模式：是遍历多还是插入多？是顺序访问还是随机访问？是按键查还是按序查？
本文要回答的问题
- vector、list、deque 的核心差异到底在哪？"链表适合插入"是不是错觉？
- 什么场景选 map，什么场景选 unordered_map？
- 为什么"遍历性能"和"插入性能"经常打架？
- 选型时最容易犯的错误是什么？
先看底层：容器 = 数据结构 + 内存布局
容器选型的根本依据是底层数据结构 + 内存布局，这决定了它的时间复杂度和缓存局部性：
| 容器 | 底层结构 | 内存布局 | 随机访问 | 中部插入 |
|---|---|---|---|---|
vector | 动态数组 | 连续 | O(1) | O(n) |
deque | 分块数组 | 分段连续 | O(1) | O(n)（两端 O(1)） |
list | 双向链表 | 节点分散 | O(n) | O(1)（需先找到位置） |
map | 红黑树 | 节点分散 | O(log n) | O(log n) |
unordered_map | 哈希表 | 桶+节点 | O(1) 平均 | O(1) 平均 |
关键认知：list 的 O(1) 插入是"伪优势"——插入前你得先找到那个位置（O(n) 遍历），而且节点分散导致缓存极不友好。
遍历性能：连续内存完胜
一个反直觉的事实：数据量不大时，vector 的遍历比 list 快一个数量级。原因在缓存局部性：
cpp
// 遍历 10 万个元素，vector 远快于 list
std::vector<int> v(100000);
std::list<int> l(100000);
for (int x : v) { /* 顺序读连续内存，缓存命中率高 */ }
for (int x : l) { /* 每次跳到一个新节点，缓存频繁失效 */ }list 的每个节点可能散落在堆的各个角落，遍历是"满内存乱跳"；vector 是"沿着缓存行顺序推进"。现代 CPU 的缓存预取对顺序访问几乎全命中，对链式访问几乎全落空。
| 遍历场景 | 推荐 | 原因 |
|---|---|---|
| 频繁遍历全部元素 | vector / array | 缓存局部性最好 |
| 只遍历、不修改 | vector | 同上 |
| 数据量小（< 几百） | 任意容器差别不大 | 都在 L1/L2 缓存里 |
结论：只要不频繁在中间插入/删除，优先 vector。 很多"链表更灵活"的直觉，在性能数据面前是错的。
插入删除：到底谁快
| 操作场景 | 推荐容器 | 说明 |
|---|---|---|
| 只在尾部插入 | vector | push_back 摊还 O(1)，扩容用 reserve 预分配 |
| 只在一端插入（队列） | deque | 两端 O(1)，且保留随机访问 |
| 频繁在任意位置插入 | list | 但插入前找位置是 O(n)，通常不如 vector+排序 |
| 插入后需要频繁查找 | map | 插入 O(log n) + 查找 O(log n) |
cpp
// 场景：模拟排队系统，只在一端进一端出 → deque
std::deque<Job> queue;
queue.push_back(job); // 队尾进
auto j = queue.front(); // 队头出
queue.pop_front();
// 场景：频繁在中间插入，且数据量小 → 用 vector 未必慢
std::vector<int> v{1, 5, 10};
auto it = std::lower_bound(v.begin(), v.end(), 7); // 找插入点
v.insert(it, 7); // 移动少量元素，缓存友好实践建议：除非你有明确证据需要 list，否则用 vector。 list 的正确场景是"位置已知的中间插入删除 + 迭代器长期稳定（不失效）"，见 迭代器失效。
查找：map vs unordered_map
| 对比项 | map（红黑树） | unordered_map（哈希表） |
|---|---|---|
| 查找复杂度 | O(log n) | O(1) 平均，O(n) 最坏 |
| 元素顺序 | 按键有序 | 无序 |
| 内存 | 每节点 3 指针开销 | 桶数组 + 节点，可能更大 |
| 适用场景 | 需要有序遍历 / 范围查询 | 纯按键查询，不关心顺序 |
| 哈希退化风险 | 无 | 有（见 unordered 入门） |
cpp
// 需要有序输出 → map
std::map<std::string, int> scores;
// 按字母序遍历
for (const auto &[name, score] : scores) { /* 有序 */ }
// 只按 key 查，无顺序需求 → unordered_map（更快）
std::unordered_map<std::string, int> cache;
auto it = cache.find("cpp"); // O(1) 平均口诀：要顺序用 map，只查询用 unordered_map。 数据量很小时（< 100 个），线性查找 vector 反而比两者都快（缓存友好），别急着上树或哈希。
易犯错误清单
- 默认用 list 存大量数据：遍历慢一个数量级，中间插入也未必快。
- 用 map 存一个"只读配置表"：纯查询用 unordered_map 更快。
- 频繁插入 vector 但不 reserve：反复扩容拷贝，见 vector 深入。
- string 拼接用
+循环：产生大量临时对象，用+=或reserve。 - 小集合上比较容器：数据结构差异在规模变大后才显现，用数据说话。
- 存指针到容器：缓存局部性更差，优先存值（对象小）或
unique_ptr。
与本站性能主线衔接
- 缓存局部性：容器选型本质是缓存局部性之争，衔接 L3 缓存 与 内存对齐。
- 对象布局：vector 连续存储与 对象布局 的地址结构呼应。
- 性能剖析：用 perf 的 cache-misses、
perf stat -e cache-misses验证容器选择是否合理。 - 实测对比：demos 里有 list vs vector 对比实验，可亲手验证缓存效应。
一句话总结
容器选型看访问模式：频繁遍历与尾部操作用 vector（缓存局部性碾压），两端操作用 deque，有序查找用 map，纯按键查询用 unordered_map，list 只留给"位置已知的中间插入 + 迭代器稳定"场景；数据量小时线性扫描的 vector 常常胜出。