C++ STL 竞赛常用容器详解

1. queue（队列，FIFO）

常用用法

• BFS（广度优先搜索）：处理层级遍历，如图的最短路径。
• 模拟队列过程：如滑动窗口、任务调度。
• 时间复杂度：push/pop O(1)，front/back O(1)。
• 注意：不支持随机访问，只能从头/尾操作。

详细例子

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维护待访问节点，按层推进，确保最短路径。

2. 滑动窗口最大值（用deque实现，但queue可模拟简单窗口）：
   queue常结合deque用于单调队列，但纯queue用于FIFO模拟，如进程调度。

经典题目（3~5道）

• 洛谷 P1443 马的遍历（BFS遍历棋盘）：https://www.luogu.com.cn/problem/P1443
• 力扣 994. 腐烂的橘子（BFS模拟扩散）：https://leetcode.cn/problems/rotting-oranges/
• 洛谷 P3957 跳房子（BFS + 二分）：https://www.luogu.com.cn/problem/P3957
• 力扣 542. 01 矩阵（多源BFS）：https://leetcode.cn/problems/01-matrix/
• 洛谷 P1339 [USACO09OCT] Heat Wave G（Dijkstra变体，可BFS实现）：https://www.luogu.com.cn/problem/P1339

2. priority_queue（优先队列，堆）

常用用法

• 贪心算法：快速取最大/最小元素，如Dijkstra最短路。
• 维护Top-K：如找第K大元素。
• 时间复杂度：push/pop O(log N)，top O(1)。
• 注意：默认大根堆，小根堆需priority_queue<T, vector<T>, greater<T>>；支持自定义比较器。

详细例子

1. Dijkstra最短路（带权图）：

   priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;  // {距离, 节点} 小根堆
   vector<ll> dist(n, INF); dist[start] = 0;
   pq.push({0, start});
   while(!pq.empty()) {
       auto [d, u] = pq.top(); pq.pop();
       if(d > dist[u]) continue;  // 松弛优化
       for(auto [v, w] : adj[u]) {
           if(dist[v] > dist[u] + w) {
               dist[v] = dist[u] + w;
               pq.push({dist[v], v});
           }
       }
   }
   

   解释：优先处理最小距离节点，实现贪心选择。

2. Huffman编码模拟（合并最小元素）：
   用小根堆反复合并两个最小频率，计算总代价。

经典题目（3~5道）

• 力扣 23. 合并 K 个升序链表（小根堆维护链表头）：https://leetcode.cn/problems/merge-k-sorted-lists/
• 洛谷 P1631 序列合并（堆维护最小和）：https://www.luogu.com.cn/problem/P1631
• 力扣 295. 数据流的中位数（双堆维护）：https://leetcode.cn/problems/find-median-from-data-stream/
• 洛谷 P1090 合并果子（贪心堆合并）：https://www.luogu.com.cn/problem/P1090
• 力扣 347. 前 K 个高频元素（堆或map+sort）：https://leetcode.cn/problems/top-k-frequent-elements/

3. stack（栈，LIFO）

常用用法

• 单调栈：求下一个更大/更小元素。
• 括号匹配/表达式求值：模拟后缀表达式。
• DFS模拟：用栈实现递归替代。
• 时间复杂度：push/pop O(1)，top O(1)。

详细例子

1. 下一个更大元素（单调栈）：

   vector<int> nextGreater(vector<int>& nums) {
       int n = nums.size();
       vector<int> res(n, -1);
       stack<int> stk;  // 存下标
       for(int i = n-1; i >= 0; i--) {
           while(!stk.empty() && nums[stk.top()] <= nums[i]) stk.pop();
           if(!stk.empty()) res[i] = nums[stk.top()];
           stk.push(i);
       }
       return res;
   }
   

   解释：从右到左维护递减栈，弹出小于当前元素的，找到下一个更大。

2. 括号匹配：
   遍历字符串，遇左括号push，遇右检查top并pop，不匹配返回false。

经典题目（3~5道）

• 力扣 20. 有效的括号（栈匹配）：https://leetcode.cn/problems/valid-parentheses/
• 洛谷 P1739 表达式括号匹配（简单栈）：https://www.luogu.com.cn/problem/P1739
• 力扣 739. 每日温度（单调栈求下一个更高）：https://leetcode.cn/problems/daily-temperatures/
• 洛谷 P2947 [USACO09MAR]Look Up G（单调栈求后缀最大）：https://www.luogu.com.cn/problem/P2947
• 力扣 84. 柱状图中最大的矩形（单调栈求左右边界）：https://leetcode.cn/problems/largest-rectangle-in-histogram/

4. set（有序唯一集合）

常用用法

• 去重并排序：维护唯一有序元素。
• 快速查找前后继：lower_bound/upper_bound。
• 动态插入/删除：如最近邻差值。
• 时间复杂度：insert/erase/find O(log N)。

详细例子

1. 营业额统计（求每个数与最近数的差）：

   set<int> s;
   long long ans = 0;
   int first; cin >> first; s.insert(first); ans += first;  // 初始
   for(int i = 1; i < n; i++) {
       int x; cin >> x;
       auto it = s.lower_bound(x);
       int min_diff = INF;
       if(it != s.end()) min_diff = min(min_diff, *it - x);
       if(it != s.begin()) min_diff = min(min_diff, x - *prev(it));
       ans += min_diff;
       s.insert(x);
   }
   

   解释：用lower_bound找插入位置，计算与前后元素的差最小值。

2. 去重输出：插入所有元素，遍历输出有序唯一序列。

经典题目（3~5道）

• 洛谷 P2234 [HNOI2002]营业额统计（如上例）：https://www.luogu.com.cn/problem/P2234
• 力扣 220. 存在重复元素 III（set维护窗口）：https://leetcode.cn/problems/contains-duplicate-iii/
• 洛谷 P5250 【深基17.例5】木材仓库（set/multiset查询）：https://www.luogu.com.cn/problem/P5250
• 力扣 414. 第三大的数（set维护Top3）：https://leetcode.cn/problems/third-maximum-number/
• 洛谷 P1102 A-B 数对（set判存在）：https://www.luogu.com.cn/problem/P1102

5. multiset（有序可重复集合）

常用用法

• 允许重复的有序维护：如多重频率统计。
• 动态中位数：双multiset平衡。
• erase需注意：erase(val)删所有，erase(it)删单个。
• 时间复杂度：同set，O(log N)。

详细例子

1. 动态中位数（数据流中位数）：

   multiset<int> low, high;  // low大根，high小根
   void add(int x) {
       if(low.empty() || x <= *low.rbegin()) low.insert(x);
       else high.insert(x);
       // 平衡：low.size() >= high.size()，low多1
       if(low.size() > high.size() + 1) {
           high.insert(*low.rbegin()); low.erase(prev(low.end()));
       } else if(high.size() > low.size()) {
           low.insert(*high.begin()); high.erase(high.begin());
       }
   }
   int median() { return *low.rbegin(); }  // 奇数在low
   

   解释：两个multiset维护下半和上半，确保中位数在low顶。

2. 滑动窗口中位数：multiset维护窗口元素，erase删除。

经典题目（3~5道）

• 力扣 295. 数据流的中位数（双堆，但可用multiset）：https://leetcode.cn/problems/find-median-from-data-stream/
• 洛谷 P1168 中位数（multiset平衡）：https://www.luogu.com.cn/problem/P1168
• 力扣 480. 滑动窗口中位数（multiset维护）：https://leetcode.cn/problems/sliding-window-median/
• 洛谷 P1632 序列合并（multiset维护最小）：https://www.luogu.com.cn/problem/P1632
• 力扣 2208. 将数组和减半的最少操作次数（multiset贪心）：https://leetcode.cn/problems/minimum-operations-to-halve-array-sum/

6. map（有序键值对）

常用用法

• 频率统计：map<int, int> cnt; cnt[x]++。
• 离散化：映射值到排名。
• 自定义排序键：键自动有序。
• 时间复杂度：[]/insert/erase O(log N)。

详细例子

1. 词频统计（高频元素）：

   map<string, int> freq;
   for(string word : words) freq[word]++;
   // 找最大：用priority_queue或sort
   vector<pair<int, string>> vec;
   for(auto& p : freq) vec.push_back({-p.second, p.first});  // 降序
   sort(vec.begin(), vec.end());
   

   解释：map自动按键排序，适合有序输出；但竞赛中常转vector sort。

2. 离散化坐标：收集所有值，sort unique，map到1~N。

经典题目（3~5道）

• 力扣 1. 两数之和（map存下标）：https://leetcode.cn/problems/two-sum/
• 洛谷 P1908 逆序对（map离散 + 树状数组）：https://www.luogu.com.cn/problem/P1908
• 力扣 451. 根据字符出现频率排序（map + sort）：https://leetcode.cn/problems/sort-characters-by-frequency/
• 洛谷 P3810 【模板】三维偏序（map离散 + CDQ）：https://www.luogu.com.cn/problem/P3810
• 力扣 219. 存在重复元素 II（map存最近下标）：https://leetcode.cn/problems/contains-duplicate-ii/

7. unordered_set（无序唯一集合）

常用用法

• 快速判重：O(1)平均查找/插入。
• 哈希去重：如唯一子串。
• 注意：可能哈希碰撞（CF需自定义hash），无序。

详细例子

1. 两数之和判存在：

   unordered_set<int> seen;
   for(int num : nums) {
       if(seen.count(target - num)) return true;
       seen.insert(num);
   }
   

   解释：O(1)检查补数是否存在，高效于set。

2. 滑动窗口唯一字符：unordered_set维护窗口，erase/insert。

经典题目（3~5道）

• 力扣 217. 存在重复元素（unordered_set判重）：https://leetcode.cn/problems/contains-duplicate/
• 洛谷 P3370 【模板】字符串哈希（unordered_set存哈希）：https://www.luogu.com.cn/problem/P3370
• 力扣 3. 无重复字符的最长子串（unordered_set窗口）：https://leetcode.cn/problems/longest-substring-without-repeating-characters/
• 洛谷 P4305 [JLOI2011]不重复数字（unordered_set去重）：https://www.luogu.com.cn/problem/P4305
• 力扣 128. 最长连续序列（unordered_set判连续）：https://leetcode.cn/problems/longest-consecutive-sequence/

8. unordered_map（无序键值对）

常用用法

• 快速映射：O(1)平均访问，如频率、下标。
• 哈希表：替代数组当键范围大。
• 注意：同unordered_set，防碰撞；键可自定义。

详细例子

1. 子数组和为K：

   unordered_map<int, int> prefix;  // {前缀和, 次数}
   prefix[0] = 1;
   int sum = 0, ans = 0;
   for(int num : nums) {
       sum += num;
       if(prefix.count(sum - k)) ans += prefix[sum - k];
       prefix[sum]++;
   }
   

   解释：用前缀和哈希，快速找sum - k。

2. LRU缓存模拟：unordered_map + list（但竞赛中常简用）。

经典题目（3~5道）

• 力扣 1. 两数之和（unordered_map存下标）：https://leetcode.cn/problems/two-sum/
• 洛谷 P3369 【模板】普通平衡树（unordered_map模拟，但推荐splay）：https://www.luogu.com.cn/problem/P3369
• 力扣 560. 和为 K 的子数组（如上例）：https://leetcode.cn/problems/subarray-sum-equals-k/
• 洛谷 P2580 于是他错误的点名开始了（unordered_map查名）：https://www.luogu.com.cn/problem/P2580
• 力扣 146. LRU 缓存（unordered_map + 双链表）：https://leetcode.cn/problems/lru-cache/