引言
在算法竞赛中，除了算法本身，数据结构的实现效率和代码编写速度同样至关重要。手写链表、平衡树、哈希表不仅耗时，而且容易出错。C++ 标准模板库（STL）提供了一套高效、成熟、泛型的容器，让选手可以专注于算法逻辑，而非底层细节。
如果把算法比作“武功招式”，那么 STL 容器就是 “十八般兵器”——剑（vector）、盾（set）、钩（map）、绳（queue）……每一样都有其独到之处，选对兵器，事半功倍。
本文将为竞赛选手系统地梳理 STL 中最常用的容器，涵盖其特性、时间复杂度、适用场景、常见操作及注意事项，帮助你快速选择合适的容器，写出简洁高效的代码。
前置知识
-
模板（template）的基本概念。
-
迭代器（iterator）——用于遍历容器的“指针”。
-
C++ 的引用、const 修饰符。
-
时间复杂度分析（O(1)、O(log n)、O(n) 等）。
第一章：序列容器 —— “排队、插队、随机访问”
序列容器维护元素的线性顺序，支持在特定位置插入/删除元素。
1. vector —— 动态数组
特点：连续内存，支持随机访问（O(1)），尾部插入/删除摊销 O(1)，中间插入/删除 O(n)。
适用场景：绝大多数需要动态数组的情况。在竞赛中，vector 是最常用的容器之一。
常用操作：
-
v.push_back(x)：尾部添加元素。
-
v.pop_back()：尾部删除元素。
-
v.size()：返回元素个数。
-
v.empty()：判空。
-
v.clear()：清空（但不释放内存）。
-
v.resize(n)：改变大小。
-
v.reserve(n)：预分配内存，避免多次扩容。
-
v.begin(), v.end()：迭代器。
-
v.front(), v.back()：首尾元素引用。
-
v.insert(pos, x) / v.erase(pos)：插入/删除，O(n)。
注意事项：
-
扩容时重新分配内存会导致迭代器失效。
-
尽量使用 reserve 预分配，提高效率。
-
二维 vector（vector<vector<int>>）常用于邻接矩阵/网格。
记忆口诀
vector 是万金油，随机访问效率高；尾部增删快如飞，中间操作要慎重。
2. deque —— 双端队列
特点：分段连续内存，支持随机访问（O(1)），头尾插入/删除 O(1)，中间插入/删除 O(n)。
适用场景：需要在两端频繁增删，且需要随机访问的情况（如滑动窗口，Monotonic Queue）。
常用操作：与 vector 类似，额外支持 push_front, pop_front。
注意事项：deque 的迭代器比 vector 复杂，但常用于构造单调队列（配合 pop_front / pop_back）。
3. list —— 双向链表
特点：链式存储，不支持随机访问（只能顺序访问），任意位置插入/删除 O(1)（已知位置），但查找 O(n)。
适用场景：需要频繁在中间插入/删除，且不关心随机访问。但在竞赛中，list 使用较少（因为 vector 和 deque 通常足够）。
常用操作：push_back, push_front, pop_back, pop_front, insert, erase, splice（合并链表）。
4. array —— 固定大小数组
特点：C++11 引入的固定大小数组，比 C 风格数组更安全（有 .size()、迭代器），性能相同。
适用场景：编译期确定大小的数组，如存储常量维度数据。
第二章：关联容器 —— “快速查找的利器”
关联容器基于平衡二叉树（红黑树），元素有序，查找/插入/删除 O(log n)。
1. set / multiset
-
set：存储唯一键，自动升序。
-
multiset：允许重复键。
常用操作：
-
s.insert(x)：插入，O(log n)。
-
s.erase(x)：删除所有等于 x 的元素（multiset）或删除指定迭代器。
-
s.find(x)：返回迭代器，找不到返回 end()。
-
s.lower_bound(x) / s.upper_bound(x)：返回第一个 ≥ x / > x 的位置。
-
s.count(x)：元素个数（multiset 中为 O(log n + count)）。
适用场景：需要维护有序集合、去重、求前驱后继、动态中位数等。
注意事项：
-
不可修改键值（若要修改，需先删除再插入）。
-
迭代器双向，但不可随机访问。
2. map / multimap
-
map：键值对，键唯一，按键升序。
-
multimap：允许重复键。
常用操作：
-
m[key] = value：访问/修改，若 key 不存在则插入。
-
m.find(key)、m.erase(key)。
-
m.lower_bound(key)。
适用场景：需要建立某种映射关系（如名称到编号），或需要有序键值对。
注意事项：operator[] 若 key 不存在会插入默认值，可能导致意外行为。用 find 判断存在性更安全。
第三章：无序关联容器 —— “哈希表的极速”
C++11 引入，基于哈希表，查找/插入/删除平均 O(1)，但最坏 O(n)。元素无序。
-
unordered_set / unordered_multiset
-
unordered_map / unordered_multimap
常用操作：同 set/map。
适用场景：需要快速查找，且不关心顺序。竞赛中最常用的是 unordered_map 和 unordered_set。
注意事项：
-
哈希冲突可能导致性能退化。某些数据会故意卡哈希（如特定构造的字符串），导致全部元素挂在同一桶中，退化为 O(n)。解决办法：自定义哈希函数或使用 map 保底。
-
容器内部无顺序，迭代时元素随机排列。
-
reserve 和 max_load_factor 可用于调优。
记忆口诀
set/map 有序慢，红黑树稳；unordered 快但怕卡，哈希防冲突要当心。
第四章：容器适配器 —— “专用接口的封装”
容器适配器是对底层容器的封装，提供特定的接口。
1. stack —— 栈（LIFO）
-
默认底层 deque，也可用 vector 或 list。
-
操作：push, pop, top, empty, size。
-
适用：DFS 的显式栈、括号匹配、表达式求值。
2. queue —— 队列（FIFO）
-
默认底层 deque。
-
操作：push, pop, front, back。
-
适用：BFS、广度遍历。
3. priority_queue —— 优先队列（堆）
-
默认底层 vector，实现为最大堆（less 比较）。
-
操作：push, pop, top, empty, size。
-
定义小根堆：priority_queue<int, vector<int>, greater<int>> pq;
-
适用：Dijkstra、哈夫曼树、动态取极值。
第五章：其他常用工具
1. pair / tuple
-
pair<T1, T2>：两个值的组合，比较按 first 再 second。
-
make_pair / {} 初始化。
-
tuple：C++11 支持多个值，用 get<index>(t) 访问。
2. string
-
本质上类似 vector<char>，但提供字符串专用操作。
-
常用：+ 拼接，substr, find, replace, c_str。
-
注意 string::npos 表示未找到。
-
性能：修改操作可能涉及拷贝，用 append 或 += 避免临时对象。
容器性能对比总览
| vector | O(1) | 尾 O(1) / 其他 O(n) | O(n) | 否 |
| deque | O(1) | 头尾 O(1) / 其他 O(n) | O(n) | 否 |
| list | 无 | O(1)（已知位置） | O(n) | 否 |
| set/map | 无 | O(log n) | O(log n) | 是 |
| unordered_set/map | 无 | 平均 O(1) | 平均 O(1) | 否 |
| priority_queue | 无（只能取顶） | O(log n) | 取顶 O(1) | 否（堆） |
迭代器失效注意事项
-
vector：插入/删除可能导致所有迭代器失效（因重新分配）。
-
deque：插入头尾不影响已有迭代器（但中间操作会使所有迭代器失效）。
-
list：插入/删除不影响其他迭代器（仅被删的元素失效）。
-
关联容器：插入/删除不影响其他迭代器（删除时仅被删元素失效）。
-
无序容器：rehash 可能导致迭代器失效（但引用/指针仍有效）。
决策指南：如何选择容器？
需要随机访问？→ vector / deque。
需要频繁在中间插入/删除？→ list（但很少用，考虑是否可以用 vector + 索引）。
需要快速查找（无序）？→ unordered_set / unordered_map。
需要有序且快速查找？→ set / map（或 multiset / multimap）。
只需按某种顺序存取？→ stack / queue / priority_queue。
键值对映射？→ map 或 unordered_map（看是否需要有序）。
需要去重？→ set / unordered_set。
需要统计频次？→ unordered_map / map（前者更快）。
竞赛中最常见的组合：
-
数组/邻接表 → vector。
-
BFS/队列 → queue。
-
优先队列/Dijkstra → priority_queue。
-
快速查找存在性 → unordered_set。
-
离散化/映射 → unordered_map（注意防卡）。
实战技巧
-
预分配空间：vector 使用 reserve 避免多次扩容。
-
自定义哈希函数（防卡）：
cpp
struct custom_hash {
static uint64_t splitmix64(uint64_t x) { … }
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
unordered_map<int, int, custom_hash> mp;
-
尽量使用 emplace 替代 push_back/insert，避免临时对象拷贝。
-
用 swap 清空 vector 释放内存：vector<int>().swap(v);
-
掌握 auto 和范围 for 简化遍历。
总结
STL 容器是算法竞赛选手的必修课。合理选择容器，不仅缩短代码量，还能保证性能。本文覆盖了所有常用容器，并给出性能对比和选择指南，希望能成为你上机时的快速参考手册。
记住：没有最好的容器，只有最适合的容器。勤加练习，培养对容器特性的直觉，你将能信手拈来，快速应对各种题目需求。
“STL 容器教会我们：合适的工具胜过蛮力。选对容器，事半功倍。”
