C++ STL 竞赛常用容器详解
1. queue（队列，FIFO）
常用用法
- BFS（广度优先搜索）：处理层级遍历，如图的最短路径。
- 模拟队列过程：如滑动窗口、任务调度。
- 时间复杂度：push/pop O(1)，front/back O(1)。
- 注意：不支持随机访问，只能从头/尾操作。
详细例子
BFS 求最短路径（图中从起点到终点的最短步数）：
queue<pair<int,int>> q; // 存 {节点，距离}
vector<bool> vis(n, false);
q.push({start, 0});
vis[start] = true;
while(!q.empty()) {
auto [u, dist] = q.front();
q.pop();
if(u == target) return dist;
for(int v : adj[u]) { // 邻接表
if(!vis[v]) {
vis[v] = true;
q.push({v, dist + 1});
}
}
}
解释：用 queue 维护待访问节点，按层推进，确保最短路径。
经典题目
- 洛谷 P1443 马的遍历（BFS 遍历棋盘）
- 力扣 994. 腐烂的橘子（BFS 模拟扩散）
- 洛谷 P3957 跳房子（BFS + 二分）
- 力扣 542. 01 矩阵（多源 BFS）
- 洛谷 P1339 Heat Wave G（Dijkstra 变体，可 BFS 实现）
2. priority_queue（优先队列，堆）
常用用法
- 贪心算法：快速取最大/最小元素，如 Dijkstra 最短路。
- 维护 Top-K：如找第 K 大元素。
- 时间复杂度：push/pop O(log N)，top O(1)。
- 注意：默认大根堆，小根堆需
priority_queue<T, vector<T>, greater<T>>；支持自定义比较器。
