第3章 STL容器与算法面试剖析
STL是C++面试中的必考模块，考察点集中在底层实现机制、迭代器失效场景和算法复杂度权衡。掌握容器选型背后的设计哲学，能帮你从“会用”进阶到“懂原理”。本章聚焦三大核心问题，每道题都配有回答框架与追问预判。
📌 面试问题1：vector 与 list 底层实现区别？插入/删除操作后哪些迭代器会失效？
- 面试官考察点：是否理解连续内存 vs 链表的内存模型；能否准确说出不同操作下的失效范围；是否具备在生产中选型的意识。
- 回答框架：
- 底层实现：vector 是动态数组（连续内存），list 是双向链表（节点非连续）。
- 迭代器失效：vector 插入/删除可能导致所有迭代器失效（重新分配）；list 插入/删除仅使被操作元素的迭代器失效。
- 典型场景：频繁中间插入→list；随机访问+尾部操作→vector。
- 简短示例回答：“vector 底层是连续内存，插入/删除可能触发重新分配，导致所有迭代器失效；list 是双向链表，插入/删除只影响当前节点的迭代器。例如，vec.insert(it, val) 后原 it 及之后都失效，而 lst.erase(it) 仅 it 失效。”
- 可能追问：
- deque 的迭代器失效情况如何？
- 如果 vector 在插入前已 reserve 足够空间，迭代器还会失效吗？
- 什么场景下你会选择 deque 而不是 vector？
- 避坑提醒：不要笼统说“list 插入不会失效”，要强调仅被删除节点失效。另外，vector 的 insert 若未导致重分配，则只使插入点之后失效。
📌 面试问题2：map 与 unordered_map 的底层数据结构及迭代器失效规则？
- 面试官考察点：是否清楚红黑树与哈希表的实现差异；迭代器失效与容器重组的关系；极端场景下的退化处理。
- 回答框架：
- 底层结构：map 基于红黑树（平衡二叉树），unordered_map 基于哈希表（桶+链表/红黑树）。
- 迭代器失效：map 插入/删除非当前节点不影响其他迭代器；unordered_map 插入可能触发 rehash 导致所有迭代器失效，删除仅影响被删元素。
- 复杂度对比：map O(log n)，unordered_map 平均 O(1)，最坏 O(n)。
- 简短示例回答：“map 底层红黑树，插入操作不会使已存在元素的迭代器失效；unordered_map 插入若触发 rehash，所有迭代器全失效。例如 umap.rehash(n) 后原迭代器不可用。”
- 可能追问：
- C++11之后 unordered_map 的桶结构如何优化？
- 如何避免 unordered_map 的 rehash？
- map 的迭代器在 erase 后还能使用吗？
- 避坑提醒：不要混淆“迭代器失效”与“引用失效”。map 的 insert 和 erase 不会使其他节点的引用失效，但 vector 的 insert 会使引用失效。
📌 面试问题3：STL 常用算法（std::sort、std::find、std::lower_bound）的复杂度及适用容器？
- 面试官考察点：是否熟悉算法复杂度；能否根据容器特性选择正确算法；是否理解迭代器类别对算法的约束。
- 回答框架：
- 复杂度：sort O(n log n)，find O(n)，lower_bound O(log n)（要求有序随机迭代器）。
- 容器适配：sort 需要随机迭代器（vector/deque）；lower_bound 适合 vector/set（但 set 有自己的成员函数）；find 适用于任意迭代器。
- 最佳实践：有序唯一键用 set 的成员 find（O(log n)）；频繁查找用 unordered_set。
- 简短示例回答：“std::sort 仅支持随机迭代器，vector 用最好；std::find 线性 O(n)，list 也能用；lower_bound 要求有序随机迭代器，通常搭配 vector+二分查找。”
- 可能追问：
- std::list 为什么不能使用 std::sort？
- 什么情况下 std::stable_sort 比 std::sort 更合适？
- 如果对 deque 进行 sort，迭代器会怎样？
- 避坑提醒：不要对 list 使用 std::sort（迭代器不满足要求），应使用 list::sort 成员函数。另外，vector 排序后迭代器不变，但顺序变了。
| 容器 | 底层结构 | 插入/删除迭代器失效 | 查找复杂度 | 适用算法 |
|---|---|---|---|---|
| vector | 动态数组 | 可能导致全部失效 | O(n) | sort, lower_bound |
| list | 双向链表 | 仅操作点失效 | O(n) | 成员函数 sort |
| deque | 分段连续 | 非端部插入部分失效 | O(n) | sort, 双端操作 |
| map | 红黑树 | 仅被删除节点失效 | O(log n) | 成员 find |
| unordered_map | 哈希表 | rehash时全部失效 | O(1)平均 | 成员 find |