信息学竞赛常用 STL 容器讲义
> STL(Standard Template Library)是 C++ 标准模板库。
> 信息学竞赛中,熟练掌握 STL 可以大幅减少代码量。
常用头文件:
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
一、VECTOR —— 动态数组
1. 定义
2. 常用操作
访问:
遍历:
3. 排序
4. 常见用途
* 动态数组
* 邻接表
* 存储不确定数量的数据
例如图的邻接表:
复杂度
操作 复杂度 v[i] O(1) push_back() 均摊 O(1) pop_back() O(1) 中间插入/删除 O(n)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
二、STRING —— 字符串
严格来说 string 不属于 STL 容器,但竞赛中使用非常频繁。
常用操作
例如:
输出:
字符串拼接:
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
三、STACK —— 栈
特点:
> 后进先出 LIFO
类似一摞盘子,最后放进去的最先拿出来。
常用操作
例如:
输出:
注意:
只删除,不返回元素。
所以不能写:
应该写:
常见用途
* 括号匹配
* 单调栈
* DFS 的非递归实现
* 表达式处理
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
四、QUEUE —— 队列
特点:
> 先进先出 FIFO
常用操作
例如:
输出:
常见用途
最典型:
例如:
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
五、DEQUE —— 双端队列
deque:
> Double Ended Queue,双端队列。
两头都可以进行插入和删除。
常用操作
还可以:
常见用途
最典型:
* 0-1 BFS
* 单调队列
0-1 BFS:
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
六、PRIORITY_QUEUE —— 优先队列
普通 queue 按进入顺序取元素。
priority_queue 每次取:
> 当前优先级最高的元素。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1. 大根堆
默认:
最大的元素在顶部:
输出:
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. 小根堆
此时最小值在顶部。
也可以写成:
常用操作
复杂度
操作 复杂度 top() O(1) push() O(log n) pop() O(log n)
常见用途
* Dijkstra
* 贪心
* 动态维护最大值/最小值
* Top K
Dijkstra 常见写法:
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
七、SET —— 集合
set 的两个重要性质:
> 自动排序 + 元素不重复
插入
例如:
集合中实际上是:
因为:
* 自动排序
* 重复的 5 只保留一个
删除
查找
如果没找到:
例如:
也可以:
对于 set:
遍历
会按照:
输出。
复杂度
插入、删除、查找通常都是:
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
八、MULTISET —— 可重复集合
与 set 基本相同,但是:
> 允许出现重复元素。
例如:
集合中有三个 5。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
一个非常重要的坑
会把:
> 所有值为 5 的元素全部删除。
如果只想删除一个:
竞赛中很容易因为这一点 WA。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
九、MAP —— 映射
map 可以理解为:
> 下标不一定是整数的数组。
普通数组:
map:
对应关系:
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1. 定义
含义:
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. 访问
例如:
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3. 判断是否存在
推荐:
或者:
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
4. 遍历
map 会按照:
> key 从小到大排列。
复杂度
查找、插入、删除:
常见用途
* 离散数据统计
* 建立映射关系
* 统计出现次数
例如统计数字出现次数:
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
十、UNORDERED_SET / UNORDERED_MAP
它们与:
功能类似,但底层使用:
> 哈希表
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
UNORDERED_SET
特点:
平均查找复杂度:
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
UNORDERED_MAP
平均:
但最坏可能退化到:
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
MAP 和 UNORDERED_MAP 怎么选?
一般:
竞赛中如果数据规模没有特别夸张,map 往往更加稳定。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
十一、PAIR —— 二元组
虽然 pair 不是容器,但竞赛中极其常用。
赋值:
访问:
例如:
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
PAIR 的比较规则
默认:
> 先比较 first,再比较 second。
例如:
因为:
所以:
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
十二、ARRAY —— 定长数组
例如:
访问:
它和普通数组类似,但可以直接使用 STL 的比较等操作。
竞赛中特别常见:
比如保存:
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
十三、BITSET —— 位集合
如果只需要记录大量:
状态,可以使用:
访问:
修改:
统计有多少个 1:
全部清零:
竞赛中常用于:
* 状态压缩
* 位运算优化
* 集合表示
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
十四、常用查找函数
LOWER_BOUND
寻找:
> 第一个 >= x 的位置。
例如:
得到:
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
UPPER_BOUND
寻找:
> 第一个 > x 的位置。
记忆:
对于数组下标:
复杂度:
前提通常是:
> 数据已经有序。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
十五、竞赛中最常用容器对照
容器 特点 常见用途 vector 动态数组 存数据、邻接表 stack 后进先出 单调栈、括号 queue 先进先出 BFS deque 两端操作 0-1 BFS、单调队列 priority_queue 自动维护最大/最小值 Dijkstra、贪心 set 有序、不重复 判重、有序集合 multiset 有序、可重复 动态维护有序序列 map 有序键值对 映射、计数 unordered_map 哈希键值对 快速查询 bitset 大量 01 状态 位运算优化
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
十六、如何选择?
看到:
想到:
看到:
想到:
看到:
想到:
看到:
想到:
看到:
想到:
看到:
想到:
看到:
想到:
看到:
想到:
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
十七、最容易出错的地方
1. POP() 不返回元素
错误:
正确:
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. 空容器不能直接取元素
例如:
之前最好保证:
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3. MULTISET.ERASE(X) 删除全部 X
删除一个:
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
4. MAP[KEY] 可能自动创建元素
例如:
即使原本没有 100,也会自动产生:
如果只想判断是否存在,使用:
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
5. PRIORITY_QUEUE 默认是大根堆
顶部是:
想要最小值:
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
十八、必须熟练掌握的部分
信息学竞赛中,建议至少做到看到下面代码可以立即知道含义:
其中最重要的几个是:
再结合:
基本可以覆盖大多数基础和提高组竞赛中的 STL 使用场景。