容器选型速查与复杂度总表

面试高频题：「什么时候用 vector？什么时候用 list？deque 和 vector 有什么区别？map 和 unordered_map 怎么选？」 这一页把散落在各子文档里的复杂度与选型集中成一张总表，配合具体页食用。

一、底层数据结构一览

容器	底层结构	内存是否连续	迭代器类别
`std::vector<T>`	动态数组（三指针）	连续	RandomAccess
`std::string`	动态数组（+SSO 小字符串优化）	连续	RandomAccess
`std::deque<T>`	分段连续（中控器 map + 多段 buffer）	段内连续、段间不连续	RandomAccess
`std::array<T, N>`	定长数组（`T[N]` 的容器版）	连续	RandomAccess
`std::list<T>`	双向链表	不连续	Bidirectional
`std::forward_list<T>`	单向链表	不连续	Forward
`std::set` / `std::map`	红黑树	不连续	Bidirectional
`std::unordered_set` / `std::unordered_map`	哈希表（bucket + 链表/开链）	不连续	Forward
`std::stack` / `std::queue`	适配器（默认包 deque）	—	无迭代器
`std::priority_queue`	适配器（默认包 vector + 堆）	—	无迭代器

记忆锚点：连续容器（vector/string/array）靠「搬元素」维护顺序，节点容器（list/红黑树/哈希）靠「改指针」维护结构——这直接决定了迭代器失效规则（见 iterator.md）。

二、复杂度总表

复杂度是选型的根本依据。标「—」表示该操作不受支持或无意义。

容器	头插	尾插	中间插	随机访问	查找	头/尾删
`vector`	O(n)	O(1) 均摊	O(n)	O(1)	O(n)	尾 O(1)
`string`	✗	O(1) 均摊	O(n)	O(1)	O(n)	尾 O(1)
`deque`	O(1)	O(1)	O(n)	O(1)	O(n)	头尾 O(1)
`array`	✗	✗	✗	O(1)	O(n)	✗
`list`	O(1)	O(1)	O(1)（给定位置）	✗（遍历 O(n)）	O(n)	O(1)
`forward_list`	O(1)	✗（只有 insert_after）	O(1)（给定位置）	✗	O(n)	头 O(1)
`set` / `map`	—	—	O(log n)	✗	O(log n)	O(log n)
`multiset` / `multimap`	—	—	O(log n)	✗	O(log n)	O(log n)
`unordered_set` / `unordered_map`	—	—	O(1) 均摊	✗	O(1) 均摊	O(1) 均摊
`stack` / `queue`	—	O(1)	✗	✗	✗	O(1)
`priority_queue`	—	O(log n)（push）	✗	✗	✗	O(log n)（pop）

几个必须讲清的点：

「均摊 O(1)」vs「严格 O(1)」：vector 尾插是均摊（扩容时 O(n)，摊到每次 O(1)）；list 的头尾插是严格 O(1)。面试常追问「vector 为什么均摊，扩容倍率为什么 2 或 1.5」。
list 中间插是 O(1)，但「找到位置」是 O(n)：给定迭代器后指针重链是 O(1)，但你要先 O(n) 遍历过去。所以「任意位置插入」的完整成本仍是 O(n) 定位 + O(1) 插入。
哈希表的 O(1) 是平均/期望值，最坏 O(n)（全部冲突到一个桶）；红黑树的 O(log n) 是最坏保证。这是 map vs unordered_map 的核心取舍。

三、选型决策（什么时候用什么）

按「访问模式 + 是否排序 + 是否稳定节点」选：

1. 需要随机访问 / 下标 / 缓存友好 → 连续容器
   ├─ 只尾部增删 → vector（首选，几乎所有场景默认）
   ├─ 头尾都要快速增删 → deque
   └─ 定长且不退化指针 → array

2. 需要频繁「任意位置」增删、节点地址要稳定 → list / forward_list
   （省空间、只前向 → forward_list）

3. 需要「按键查找 + 自动排序」→ 红黑树
   ├─ 键唯一 → set / map
   └─ 键可重复 → multiset / multimap

4. 需要「按键查找 + 平均 O(1) + 不要排序」→ 哈希表
   ├─ 键唯一 → unordered_set / unordered_map
   └─ 键可重复 → unordered_multiset / unordered_multimap

5. 只要栈/队列/优先队列语义 → 适配器
   ├─ LIFO → stack
   ├─ FIFO → queue
   └─ 每次取最大/最小 → priority_queue（堆）

三组经典对比（面试必答）

① vector vs list

维度	vector	list
内存	连续，缓存友好	节点分散，缓存不友好
随机访问	O(1)	O(n)
中间增删	O(n)（搬元素）	O(1)（改指针，但定位 O(n)）
迭代器失效	扩容全失效	只删谁谁失效
内存开销	无额外指针，但有容量冗余	每个节点 2 个指针
结论	默认首选	只在「节点稳定性」关键时用

经验法则：没有特殊理由就用 vector。现代 CPU 缓存下，list 的缓存不友好往往抵消掉它「插入 O(1)」的理论优势；除非元素很大、且你要长期保存指向元素的指针/引用（节点稳定），才考虑 list。

② deque vs vector

deque 多了头部 O(1) 增删，代价是随机访问慢一点（两次寻址）、内存不连续（不能 &v[0] 给 C 接口）。
vector 内存连续、缓存最优、随机访问最快，但头插 O(n)。
选 deque 的信号：需要「两端插入」的场景（滑动窗口、任务队列、实现 stack/queue 底层）。

③ map vs unordered_map（详见 unordered_map.md）

维度	map（红黑树）	unordered_map（哈希）
复杂度	O(log n)，最坏保证	O(1) 平均，最坏 O(n)
有序性	键有序（可做范围查询）	无序
键要求	需 `operator<`	需 `hash` + `operator==`
内存	较小	较大（bucket + 负载因子）
选型	要稳定最坏复杂度 / 要范围查询 / 键难哈希	只要快、不要序

四、高频追问

「为什么说 STL 容器接口统一，但复杂度天差地别？」 —— 接口统一靠迭代器抽象；复杂度差异来自底层数据结构。同一 push_back，vector 是均摊 O(1) 扩容，deque 是段内游标 +1，list 是改指针。
「节点稳定性」是什么？哪些容器有？ —— 指元素对象创建后地址不变，因此指向它的引用/指针长期有效。list、set、map（及哈希表的节点）有；vector/deque 没有（扩容搬移）。需要长期持有元素地址 → 选节点稳定容器或提前 reserve。
「为什么优先队列不用 list 而用 vector 做底层？」 —— 堆需要随机访问（父/子下标 2i+1/2i+2），list 没有随机访问，vector 连续内存天然适合。
「stack/queue 为什么默认包 deque？」 —— 见 stack-queue.md：deque 两头 O(1)，比 vector 多一个头插能力、比 list 少指针开销。
「连续内存对性能到底多重要？」 —— 数据在内存里相邻 → 命中 CPU cache line、预取友好。这就是「无脑用 vector」的底层原因，也是性能题（见 performance/cache-model.md）的入口。

五、自测

说出 vector/deque/list 三者的头插、尾插、随机访问复杂度。
什么时候必须放弃 vector 选 list？说出至少两个真实场景。
map 与 unordered_map 的复杂度差异是「平均 vs 最坏」吗？分别对应什么场景？
为什么 stack<int> 不直接用 vector<int> 而默认用 deque？

容器选型速查与复杂度总表 ​

一、底层数据结构一览 ​

二、复杂度总表 ​

三、选型决策（什么时候用什么） ​

三组经典对比（面试必答） ​

四、高频追问 ​

五、自测 ​