STL 专题

一句话总览

STL（Standard Template Library）由容器、算法、迭代器、仿函数、配接器、空间配置器六大组件组成。面试几乎必问容器底层结构、迭代器失效与手写实现。

组件划分

组件	作用	例子
容器 Container	存储数据	vector/list/deque/map/set…
算法 Algorithm	操作数据	sort/find/copy…
迭代器 Iterator	连接容器与算法	begin()/end()
仿函数 Functor	重载 () 的对象	less/greater
配接器 Adapter	改造接口	stack/queue/priority_queue
空间配置器 Allocator	内存分配	std::allocator

分类

• 序列式容器：vector、deque、list、forward_list、array、string
• 关联式容器（红黑树）：map、set、multimap、multiset
• 无序关联容器（哈希表）：unordered_map、unordered_set 等
• 容器适配器：stack、queue、priority_queue

问题清单（含答案）

高频

1. vector 底层实现与扩容机制？为什么是 2 倍/1.5 倍？

答案

动态数组（连续内存、三指针）。容量不足时新开 2 倍（libstdc++）或 1.5 倍（MSVC）内存、把旧元素 move 过去、释放旧内存；翻倍保证均摊 O(1)。详见 vector.md。

2. push_back 与 emplace_back 的区别？

答案

push_back 先构造临时对象再拷贝/移动进去；emplace_back 用完美转发把参数原地传给构造函数、直接在容器内存构造，省掉临时对象。详见 vector.md。

3. map 与 unordered_map 选型？底层各是什么？

答案

map 红黑树、O(log n) 最坏保证、键有序；unordered_map 哈希表、O(1) 平均、无序、需 hash。要序/稳定最坏复杂度选 map，只要快选 unordered_map。详见 map.md、unordered_map.md。

4. map 与 set 的区别？

答案

map 存键值对 K→V，set 只存 key（可看作无 value 的 map）；底层都是红黑树，键唯一、有序、键不可改。

5. 迭代器失效有哪些场景？如何避免？

答案

vector 扩容/中间增删 → 全部或之后失效；list/map 只删谁谁失效；unordered_* rehash 全失效。避免：reserve 预留、用 erase 返回的下一个、节点稳定容器存引用。详见 iterator.md。

6. 遍历时删除元素怎么安全做？

答案

it = c.erase(it)（erase 返回被删元素后一位置）；或 erase-remove idiom。详见 iterator.md。

7. list/deque 底层实现差异？

答案

list 双向链表、任意位置插删 O(1)、无随机访问；deque 分段连续（中控器 + 多段 buffer）、头尾 O(1)、随机访问 O(1) 略慢于 vector。详见 list.md、deque.md。

8. std::sort 底层用什么排序？

答案

内省排序 IntroSort = 快排为主 + 递归过深换堆排兜底 + 小区间插入排序；O(n log n)、不稳定。详见 priority_queue.md。

9. priority_queue 底层原理？

答案

容器适配器，默认 vector + 二叉堆；push/pop O(log n)、top O(1) 取最大（大顶堆）。详见 priority_queue.md。

10. 手写 vector、list、shared_ptr？

答案

见各页：vector 用原始内存 + placement new + 扩容；list 哨兵节点双向链表；shared_ptr 控制块引用计数。

11. vector/list/deque/map 怎么选？各操作复杂度？

答案

默认 vector；头尾都要快用 deque；节点稳定/任意位置插删用 list；按键查找 + 排序用 map。完整复杂度总表见 container-selection.md。

12. stack/queue 是容器吗？默认底层是什么？为什么？

答案

不是容器，是适配器（组合底层容器 + 限制接口、无迭代器）。默认 deque，因为两头 O(1)、无指针冗余、不必连续。详见 stack-queue.md。

13. 可调用对象有哪几种？std::function 与函数指针、lambda 的区别？

答案

普通函数、函数指针、函数对象（重载 ()）、lambda。std::function 用类型擦除统一存储不同 callable、有间接调用开销；函数指针只能存同签名函数；lambda 是匿名函数对象、可内联最快。详见 function-callable.md。

14. pair/tuple 什么时候该用、什么时候用自定义结构体？

答案

first/second 无语义时优先自定义具名 struct + 结构化绑定；只有临时、局部、一眼能懂的两三个值（或库接口定死如 map::insert）才用 pair/tuple。详见 pair-tuple.md。

进阶

vector<bool> 为什么特殊？

答案

位压缩存储，operator[] 返回代理对象而非 bool&，不能取地址；需真 bool 用 vector<char> 或 deque<bool>。

移动语义对容器插入的影响？

答案

让元素可 move 而非 copy，对昂贵/不可拷贝类型性能提升大；move_if_noexcept 保证扩容异常安全。

reserve vs resize？

答案

reserve 只改 capacity 不改 size、不构造元素；resize 改 size（变大补默认元素、变小析构多余）。

为什么 deque 能两头 O(1) 插入？

答案

分段连续，头尾只动首/尾 buffer 游标，段满在中控器加 buffer。

红黑树 vs AVL 的取舍？

答案

红黑树插入删除旋转少、写友好；AVL 更严格平衡、查找更快但旋转多。STL 选红黑树（读写兼顾）。

哈希冲突 / 何时 rehash？

答案

链地址法（开链）；负载因子超阈值时扩容 bucket 并 rehash 重排所有元素（此时迭代器全失效）。

手写 optional<T> 底层怎么实现？为什么不堆分配？

答案

union{ char dummy; T value; } 把「有值/无值」叠在同一地址 + bool engaged 标志；构造用 placement new（std::construct_at）、析构手动调 ~T()、emplace 先 reset() 再构造。不堆分配是因为标准要求值内联在对象里（nested within）：省一次分配 + 一次间接寻址，代价是 sizeof(optional<T>) == align_up(sizeof(T)+1, alignof(T)) 且 alignof 继承 T（int→8、char→2、string→40）。两个易错点：就位构造模板不加约束会抢走拷贝构造（optional<T> z = y; 编译不过，而 x = y 不受影响）、拷贝赋值要穿透赋值而不是先析构再拷贝构造。详见 optional.md。

std::optional 移动之后源会变空吗？

答案

不会。标准 [optional.ctor]/9：移动构造后 rhs.has_value() 保持不变（源里只是 moved-from 的 T），即移动后 has_value() == 1；要清空得 reset()。这与「手写容器移动把源置空」的直觉相反。另外 C++26 新增 optional<T&>：8 字节（内部就是 T*，nullptr 当空），且 o = b 是重绑定而非穿透赋值。详见 optional.md。

子文档

手写实现（反链）：手写容器（flat_map 有序连续数组 + 动态数组扩容）、 flat hashmap（开放寻址 + 墓碑 + 负载因子）、 手写 optional（堆版 vs union 原地版）。

文件	内容
container-selection.md	容器选型 + 复杂度总表（何时用哪个）
vector.md	动态数组原理、扩容、emplace、手写 vector
vector-realloc.md	vector 扩容到底拷贝还是移动？（noexcept/平凡/异常安全）
list.md	双向链表 + 手写链表
deque.md	双端队列、分段内存
map.md	map/set 红黑树原理
unordered_map.md	哈希表原理
priority_queue.md	堆 + std::sort 内省排序
stack-queue.md	stack/queue 容器适配器
iterator.md	迭代器失效大全（必考）
string.md	string（SSO）+ 手写 String
optional.md	std::optional 底层与手写思路
function-callable.md	std::function 与可调用对象（类型擦除）
pair-tuple.md	pair/tuple/结构化绑定 与最佳实践

智能指针（unique_ptr / shared_ptr / weak_ptr + 手写，见 smart-pointers/）。