STL 性能陷阱

是什么 / 解决什么问题

STL 容器不是慢，但默认选择不一定适合低延迟热路径。面试重点不是否定 STL，而是知道每种容器的内存布局、复杂度和失效规则。

常见容器取舍

容器	优点	风险
vector	连续内存，cache-friendly	扩容导致移动和引用失效
deque	两端插入稳定	分段内存，局部性弱于 vector
list	节点稳定	pointer chasing，cache miss 多
map	有序	红黑树节点分散
unordered_map	平均 O(1)	rehash、hash 成本、内存分散

实用原则

1. vector 优先，配合 reserve。
2. 热路径避免 std::string 频繁构造和格式化。
3. unordered_map 要预估容量并设置 reserve。
4. 节点型容器不适合 cache 敏感路径。
5. 明确迭代器和引用失效规则。

示例

std::vector<Order> orders;
orders.reserve(1 << 20);

提前 reserve 可以避免扩容抖动，但也要评估内存占用。

面试高频问题

unordered_map 一定是 O(1) 吗

不是。平均 O(1) 依赖 hash 分布和负载因子；rehash 会造成明显抖动；节点分配也可能影响 cache locality。