标准库容器是 C++ 日常 80% 工作的载体，但很多人对它们的认知停留在"vector 快、list 能随便插"。真正决定选型的，是三件事：内存布局（连续 or 节点）、迭代器失效规则、各操作的复杂度保证。这篇把这三件事讲透，给一张能照着选的决策表。容器的内存分配细节见 C++ STL Allocator，这里聚焦容器本身。

容器的分类

STL 容器按组织方式分三大类：

类别成员底层结构
序列容器array vector deque list forward_list数组 / 链表
关联容器set map multiset multimap红黑树
无序关联容器unordered_set/map/multiset/multimap哈希表
容器适配器stack queue priority_queue包装 deque/vector

另外有两个"准容器"：std::string（连续字符）、std::span（不持有数据的视图）。std::array 是固定大小的真容器，std::vector 是默认选择。

序列容器

std::vector：默认选择

连续内存、动态数组。99% 的场景都该先用它。

1
2
3
4
std::vector<int> v;
v.push_back(1);          // amortized O(1)
v[0];                    // O(1) random access
v.size();

内存布局：一块连续内存。内部维护三个指针——begin（已用起点）、end（已用终点）、capacity_end（已分配终点）。size() = end - begin，capacity() = capacity_end - begin。

扩容机制：push_back 在 size == capacity 时触发扩容：分配更大的新内存（通常翻倍）、逐个移动/拷贝旧元素、释放旧内存。均摊 O(1)，但单次扩容是 O(n) 且可能触发整体搬移。

关键操作：reserve(n) 预留容量（不改 size，避免后续多次扩容）、shrink_to_fit() 请求释放多余容量（非强制）、resize(n) 改 size。

1
2
3
4
std::vector<int> v;
v.reserve(1000);          // one allocation, no reallocs for next 1000 push_backs
for (int i = 0; i < 1000; ++i) v.push_back(i);
v.shrink_to_fit();        // hint to release spare capacity

如果元素类型已知且 size 编译期固定，用 std::array——零开销、无扩容、栈上分配。

std::deque：双端队列

分段连续（一组定长块 + 一个中控数组），支持两端 O(1) 插入删除。

1
2
3
4
std::deque<int> dq;
dq.push_back(1);          // O(1)
dq.push_front(0);         // O(1) — vector 做不到
dq[0];                    // O(1) 随机访问，但比 vector 慢（多一次间接）

适合两端都要进出的场景（滑动窗口、工作队列）。中间插入 O(n)，随机访问虽 O(1) 但常数大于 vector。deque 的迭代器失效规则比 vector 宽松（见下）。

std::list / forward_list：链表

list 是双向链表，forward_list 是单向链表（更省内存，C++11 引入，对标 C 的手写单链表）。

1
2
3
4
std::list<int> l;
l.push_back(1);
auto it = std::find(l.begin(), l.end(), 5);
l.insert(it, 99);         // O(1) once you have the iterator
  • 没有随机访问（无 operator[]，list 的迭代器是双向非随机）。
  • 任意位置插入/删除 O(1)（前提是已有迭代器；找位置仍是 O(n)）。
  • 链表节点分散，cache 不友好——这是它实际跑不过 vector 的根本原因：现代 CPU 上 vector 的 O(n) 搬移常常比 list 的 O(1) 节点操作还快，因为连续内存吃满了缓存。

经验：需要频繁中间插入删除时，先问"能不能用 vector + erase"。多数情况下 vector 更快。list 的杀手锏是插入删除不失效其他迭代器——当这点真有用（如 LRU 缓存、事件队列）才上 list。

std::array：固定大小数组

1
2
3
std::array<int, 5> a = {1, 2, 3, 4, 5};   // size is part of type
a.size();               // 5, constexpr
a[0];                   // O(1)

栈上分配、零开销、size 是类型的一部分（编译期已知）。它就是 C 数组的"标准库皮肤"——有 begin()/end()、size()、边界检查的 at()，却没有任何额外开销。能确定大小就别用 C 数组，用 std::array。

关联容器：红黑树

set/map/multiset/multimap 底层都是平衡二叉搜索树（红黑树）。

  • 元素始终有序（按 key 升序，可用自定义比较器）。
  • 查找/插入/删除均 O(log n)。
  • map 的 operator[] 在 key 不存在时会插入默认值，所以它不是纯查询——查询用 find 或 contains(C++20)。
1
2
3
4
std::map<std::string, int> m;
m["a"] = 1;                  // inserts {a,0} then assigns if absent
auto it = m.find("a");       // pure lookup, no insertion
if (m.contains("a")) { /* C++20 */ }

multimap 允许重复 key，且没有 operator[]（一对多，没法返回单个引用）。

无序容器：哈希表

unordered_set/map/multiset/multimap 底层是哈希表（拉链法，桶 + 链表/节点）。

  • 平均 O(1) 查找/插入/删除，最坏 O(n)（哈希冲突 / rehash）。
  • 元素无序。
  • 需要 key 类型有 std::hash<Key> 特化和 operator==。
  • rehash 触发条件类似 vector 扩容：load_factor > max_load_factor 时重建桶数组。
1
2
3
4
5
6
7
8
9
std::unordered_map<std::string, int> um;
um["a"] = 1;                 // average O(1)
// custom key needs hash + equality
struct Point { int x, y; };
struct PointHash { size_t operator()(const Point& p) const noexcept {
    return size_t(p.x) * 31 + p.y; } };
struct PointEq  { bool operator()(const Point& a, const Point& b) const noexcept {
    return a.x == b.x && a.y == b.y; } };
std::unordered_map<Point, int, PointHash, PointEq> grid;

自定义类型作 key 必须提供哈希函数和相等判断——这是 unordered 容器最常踩的坑。reserve(n) 能预分配桶避免 rehash。

选 map 还是 unordered_map？需要有序遍历 / 范围查询 / 最坏性能可控 → map；只要平均最快查找、不在乎顺序 → unordered_map。多数"按 key 查表"场景后者更合适。

迭代器失效规则

这是容器使用中最隐蔽、最致命的一类 bug：对容器的修改可能让已有的迭代器、引用、指针失效，再用就是 UB。规则按容器分：

容器插入删除
vector / string扩容则全部失效；不扩容则插入点之后失效删除点及之后全部失效（含 end）
deque两端插入：仅 end 失效；中间插入：全部失效两端删除：仅被删和 end 失效；中间删除：全部失效
list / forward_list不失效任何其他迭代器仅被删元素的迭代器失效
set / map 等不失效仅被删元素的迭代器失效
unordered_*rehash 则全部失效；否则不失效仅被删元素失效（rehash 期间除外）

经典坑：边遍历边删除。直接 for + erase 会让被删迭代器失效，下一次 ++it 是 UB：

1
2
3
4
5
6
7
8
9
10
11
12
13
std::vector<int> v = {1, 2, 3, 4, 5};

// 错误：erase 后 it 失效，++it 是 UB
for (auto it = v.begin(); it != v.end(); ++it)
    if (*it % 2 == 0) it = v.erase(it);   // still wrong: skips next element after erase

// 正确：erase 返回下一个有效迭代器
for (auto it = v.begin(); it != v.end(); )
    if (*it % 2 == 0) it = v.erase(it);
    else ++it;

// 更好（C++20）：erase_if 一次搞定
std::erase_if(v, [](int x) { return x % 2 == 0; });

std::erase_if(container, pred)（C++20，对所有容器都有重载）是删除满足条件元素的正确且高效写法——vector 会用 erase-remove 思路一次性搬移，list 直接拆节点，无需手写循环。

关联/无序容器的 erase 也有"返回下一个迭代器"的版本（C++11 起），但 std::erase_if 依然更简洁。

复杂度速查

操作vectordequelistset/mapunordered_*
随机访问 []O(1)O(1)———
头部插入O(n)O(1)O(1)——
尾部插入均摊 O(1)O(1)O(1)——
中间插入O(n)O(n)O(1)*O(log n)均摊 O(1)
按 key 查找O(n)O(n)O(n)O(log n)均摊 O(1)
排序O(n log n)——已序—

* list 中间插入 O(1) 仅指"已知位置插入"——找到位置仍是 O(n)。

选型决策表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
要随机访问 / 连续内存？
├─ 大小编译期已知 → array
├─ 默认 → vector
└─ 两端都要进出 → deque

要按键查找？
├─ 需要有序 / 范围查询 → map / set
└─ 只要平均最快 → unordered_map / unordered_set

要在已知位置频繁增删，且不能失效其他迭代器？
└─ list / forward_list

要栈/队列/优先队列？
└─ stack / queue / priority_queue（适配器，默认基于 deque/vector）

几条经验法则：

  1. 默认 vector，除非有明确理由换别的。它的连续内存对缓存友好，多数"看似该用 list"的场景 vector 都更快。
  2. 要按键查表，默认 unordered_map，需要有序或范围查询才换 map。
  3. 大小编译期已知，用 array 替代 C 数组和"已知上限的 vector"。
  4. 避免 list，除非真的需要"增删不失效其他迭代器"。CPU 缓存让链表在现代硬件上常常是反优化。
  5. 批量操作用 assign/insert(range)/append_range(C++23) 而非循环 push_back——前者能一次性 reserve，避免多次扩容。

一句话总结

容器的选择本质是在内存布局（连续 vs 节点，决定 cache 友好性）、迭代器失效规则（决定能否边遍历边改）、复杂度保证（决定规模上去后的表现）三者间权衡。记住连续内存的 vector 在现代 CPU 上常常打败理论更优的 list、记住 erase 会失效迭代器所以用 std::erase_if、记住 unordered 容器需要自定义 key 的 hash 和 ==——这三条能避开日常 90% 的容器坑。