C++ STL 容器选择指南：vector、deque、list 与关联容器
选择合适的容器对性能至关重要。
1. 顺序容器对比
| 容器 | 随机访问 | 头部插入 | 尾部插入 | 中间插入 | 适用场景 |
|---|---|---|---|---|---|
vector | O(1) | O(n) | 均摊 O(1) | O(n) | 频繁随机访问，尾部操作 |
deque | O(1) | O(1) | O(1) | O(n) | 头尾操作频繁 |
list | O(n) | O(1) | O(1) | O(1) | 频繁中间插入/删除 |
forward_list | O(n) | O(1) | O(1) | O(1) | 单向链表，节省内存 |
2. 关联容器
- 有序（红黑树）：
set、map、multiset、multimap，按键排序。 - 无序（哈希）：
unordered_set、unordered_map等，平均 O(1) 查找。
3. 选择原则
- 默认用
vector，除非有明确理由。 - 频繁头尾操作用
deque。 - 频繁中间插入用
list。 - 查找密集用
unordered_map，需有序遍历用map。
// 缓存场景：快速查找
std::unordered_map<std::string, User> cache;
// 排行榜：有序遍历
std::map<int, std::string> score_rank;