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. push_back 与 emplace_back 的区别？
3. map 与 unordered_map 选型？底层各是什么？
4. map 与 set 的区别？
5. 迭代器失效有哪些场景？如何避免？
6. 遍历时删除元素怎么安全做？
7. list/deque 底层实现差异？
8. std::sort 底层用什么排序？
9. 优先级队列 priority_queue 底层原理？
10. 手写 vector、list、shared_ptr。

进阶

• vector<bool> 为什么特殊（位压缩）？
• 移动语义对容器插入的影响？
• reserve vs resize？
• 为什么 deque 能两头 O(1) 插入？
• 红黑树 vs AVL 树的取舍？
• 哈希冲突如何解决 / 哈希表何时扩容、rehash？

子文档

文件	内容
vector.md	动态数组原理、扩容、emplace、手写 vector
list.md	双向链表 + 手写链表
deque.md	双端队列、分段内存
map.md	map/set 红黑树原理
unordered_map.md	哈希表原理
priority_queue.md	堆 + std::sort 内省排序
iterator.md	迭代器失效大全（必考）
string.md	string（SSO）+ 手写 String
optional.md	std::optional 底层与手写思路

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