在信息学竞赛中，熟练使用 STL 可以大幅提升编码效率。本文详细介绍竞赛高频使用的 STL 容器和算法。
1. vector（动态数组）
vector<int> v = {1, 2, 3};
v.push_back(4); // 尾部插入 O(1) 均摊
v.pop_back(); // 尾部删除 O(1)
sort(v.begin(), v.end()); // 排序
v.erase(unique(v.begin(), v.end()), v.end()); // 去重支持随机访问，是竞赛中使用频率最高的容器。
2. pair / tuple
pair<int, int> p = {1, 2};
// 用于需要同时存储两个值的情况，比如坐标、优先级+值
vector<pair<int, int>> v; // 常用于多关键字排序3. set / map（有序关联容器）
- 基于红黑树实现，操作 O(log n)
- set：有序集合，元素唯一
- multiset：可重复的有序集合
- map：键值对映射
- 支持 lower_bound / upper_bound
4. unordered_set / unordered_map（哈希容器）
- 基于哈希表，均摊 O(1)
- 注意：可能被卡哈希（CF 上有些题专门卡 unordered_map）
5. priority_queue（优先队列）
- 默认大根堆
- 小根堆：priority_queue<int, vector<int>, greater<int>>
- 用于 Dijkstra、贪心等算法
6. stack / queue / deque
- stack：栈（DFS 非递归）
- queue：队列（BFS）
- deque：双端队列（滑动窗口最值）
7. string 常用操作
- substr, find, replace
- to_string / stoi / stoll 类型转换
8. algorithm 常用函数
- sort, stable_sort
- lower_bound, upper_bound, binary_search
- next_permutation（全排列）
- nth_element（第k小）
- unique, reverse, rotate, shuffle
暂无评论，快来抢沙发吧~ 🛋️