C++ STL 容器性能对比与选用指南
选择合适的容器对程序性能至关重要。
1. 顺序容器
| 容器 | 随机访问 | 插入/删除（中间） | 插入/删除（末尾） | 适用场景 |
|---|---|---|---|---|
vector | O(1) | O(n) | 均摊 O(1) | 频繁随机访问，尾部增删 |
deque | O(1) | O(n) | O(1) 头尾 | 需要头尾操作 |
list | O(n) | O(1) | O(1) | 频繁中间插入/删除 |
2. 关联容器
- 有序（红黑树）：
set,map,multiset,multimap（对数复杂度）。 - 无序（哈希表）：
unordered_set,unordered_map（平均常数复杂度）。
3. 选用原则
- 默认使用
vector，除非有明确理由。 - 频繁在头部插入，用
deque。 - 频繁在中间插入，用
list。 - 需要快速查找，用
unordered_map（注意哈希冲突）。 - 需要有序遍历，用
map。
4. 示例
// 缓存场景：快速查找
std::unordered_map<std::string, User> user_cache;
// 排行榜：有序遍历
std::map<int, std::string> score_rank;