STL
2026-08-19 21:04:57
发布于：广东
14阅读
0回复
0点赞
信息学竞赛常用 STL 容器讲义
STL（Standard Template Library）是 C++ 标准模板库。
信息学竞赛中，熟练掌握 STL 可以大幅减少代码量。
常用头文件：
#include <bits/stdc++.h>
using namespace std;
一、vector —— 动态数组
1. 定义
vector<int> v;
vector<int> v(n); // n 个元素，初值为 0
vector<int> v(n, 5); // n 个元素，初值为 5
2. 常用操作
v.push_back(x); // 尾部加入 x
v.pop_back(); // 删除最后一个元素
v.front(); // 第一个元素
v.back(); // 最后一个元素
v.size(); // 元素个数
v.empty(); // 是否为空
v.clear(); // 清空
访问：
v[i];
遍历：
for(int x : v){
cout << x << ' ';
}
3. 排序
sort(v.begin(), v.end()); // 从小到大
sort(v.begin(), v.end(), greater<int>()); // 从大到小
4. 常见用途
- 动态数组
- 邻接表
- 存储不确定数量的数据
例如图的邻接表：
vector<int> g[N];
g[u].push_back(v);
g[v].push_back(u);
复杂度
| 操作 | 复杂度 |
|---|---|
v[i] |
O(1) |
push_back() |
均摊 O(1) |
pop_back() |
O(1) |
| 中间插入/删除 | O(n) |
二、string —— 字符串
严格来说 string 不属于 STL 容器，但竞赛中使用非常频繁。
string s;
cin >> s;
常用操作
s.size(); // 长度
s.empty(); // 是否为空
s.push_back('a'); // 尾部加入字符
s.pop_back(); // 删除末尾字符
s.substr(pos, len); // 截取子串
例如：
string s = "abcdef";
cout << s.substr(2, 3);
输出：
cde
字符串拼接：
string a = "abc";
string b = "def";
string c = a + b;
三、stack —— 栈
特点：
后进先出 LIFO
类似一摞盘子，最后放进去的最先拿出来。
stack<int> st;
常用操作
st.push(x); // 入栈
st.pop(); // 出栈
st.top(); // 查看栈顶
st.size(); // 元素数量
st.empty(); // 是否为空
例如：
stack<int> st;
st.push(1);
st.push(2);
st.push(3);
cout << st.top();
输出：
3
注意：
st.pop();
只删除，不返回元素。
所以不能写：
int x = st.pop(); // 错误
应该写：
int x = st.top();
st.pop();
常见用途
- 括号匹配
- 单调栈
- DFS 的非递归实现
- 表达式处理
四、queue —— 队列
特点：
先进先出 FIFO
queue<int> q;
常用操作
q.push(x); // 队尾加入
q.pop(); // 删除队首
q.front(); // 队首
q.back(); // 队尾
q.size();
q.empty();
例如：
queue<int> q;
q.push(1);
q.push(2);
q.push(3);
cout << q.front();
输出：
1
常见用途
最典型：
BFS
例如：
queue<int> q;
q.push(s);
while(!q.empty()){
int u = q.front();
q.pop();
// 扩展 u
}
五、deque —— 双端队列
deque：
Double Ended Queue，双端队列。
两头都可以进行插入和删除。
deque<int> q;
常用操作
q.push_back(x);
q.push_front(x);
q.pop_back();
q.pop_front();
q.front();
q.back();
q.size();
q.empty();
还可以：
q[i];
常见用途
最典型：
- 0-1 BFS
- 单调队列
0-1 BFS：
if(w == 0)
q.push_front(v);
else
q.push_back(v);
六、priority_queue —— 优先队列
普通 queue 按进入顺序取元素。
priority_queue 每次取：
当前优先级最高的元素。
1. 大根堆
默认：
priority_queue<int> q;
最大的元素在顶部：
q.push(3);
q.push(8);
q.push(5);
cout << q.top();
输出：
8
2. 小根堆
priority_queue<
int,
vector<int>,
greater<int>
> q;
此时最小值在顶部。
也可以写成：
priority_queue<int, vector<int>, greater<int>> q;
常用操作
q.push(x);
q.pop();
q.top();
q.empty();
q.size();
复杂度
| 操作 | 复杂度 |
|---|---|
top() |
O(1) |
push() |
O(log n) |
pop() |
O(log n) |
常见用途
- Dijkstra
- 贪心
- 动态维护最大值/最小值
- Top K
Dijkstra 常见写法：
priority_queue<
pair<long long,int>,
vector<pair<long long,int>>,
greater<pair<long long,int>>
> q;
七、set —— 集合
set 的两个重要性质：
自动排序 + 元素不重复
set<int> s;
插入
s.insert(x);
例如：
s.insert(5);
s.insert(2);
s.insert(5);
s.insert(3);
集合中实际上是：
2 3 5
因为：
- 自动排序
- 重复的
5只保留一个
删除
s.erase(x);
查找
s.find(x);
如果没找到：
s.find(x) == s.end()
例如：
if(s.find(x) != s.end()){
cout << "存在";
}
也可以：
s.count(x);
对于 set：
count(x) 只可能是 0 或 1
遍历
for(int x : s){
cout << x << ' ';
}
会按照：
从小到大
输出。
复杂度
插入、删除、查找通常都是：
O(log n)
八、multiset —— 可重复集合
与 set 基本相同，但是：
允许出现重复元素。
multiset<int> s;
例如：
s.insert(5);
s.insert(5);
s.insert(5);
集合中有三个 5。
一个非常重要的坑
s.erase(5);
会把：
所有值为 5 的元素全部删除。
如果只想删除一个：
auto it = s.find(5);
if(it != s.end())
s.erase(it);
竞赛中很容易因为这一点 WA。
九、map —— 映射
map 可以理解为：
下标不一定是整数的数组。
普通数组：
a[10] = 5;
map：
map<string, int> mp;
mp["Alice"] = 100;
mp["Bob"] = 95;
对应关系：
Alice -> 100
Bob -> 95
1. 定义
map<int,int> mp;
map<string,int> mp;
含义：
map<键类型, 值类型>
2. 访问
mp[key]
例如：
mp[5] = 10;
cout << mp[5];
3. 判断是否存在
推荐：
if(mp.find(x) != mp.end()){
// x 存在
}
或者：
if(mp.count(x)){
}
4. 遍历
for(auto [key, value] : mp){
cout << key << ' ' << value << '\n';
}
map 会按照：
key 从小到大排列。
复杂度
查找、插入、删除：
O(log n)
常见用途
- 离散数据统计
- 建立映射关系
- 统计出现次数
例如统计数字出现次数：
map<int,int> cnt;
for(int i = 1; i <= n; i++){
int x;
cin >> x;
cnt[x]++;
}
十、unordered_set / unordered_map
它们与：
set
map
功能类似，但底层使用：
哈希表
unordered_set
unordered_set<int> s;
特点：
不自动排序
元素不重复
平均查找复杂度：
O(1)
unordered_map
unordered_map<int,int> mp;
平均：
插入 O(1)
查找 O(1)
删除 O(1)
但最坏可能退化到：
O(n)
map 和 unordered_map 怎么选？
一般：
需要排序、lower_bound → map
只关心快速查询 → unordered_map
竞赛中如果数据规模没有特别夸张，map 往往更加稳定。
十一、pair —— 二元组
虽然 pair 不是容器，但竞赛中极其常用。
pair<int,int> p;
赋值：
p = {3, 5};
访问：
p.first
p.second
例如：
cout << p.first << ' ' << p.second;
pair 的比较规则
默认：
先比较
first，再比较second。
例如：
pair<int,int> a = {2, 10};
pair<int,int> b = {3, 1};
因为：
2 < 3
所以：
a < b
十二、array —— 定长数组
array<int, 3> a;
例如：
array<int,3> a = {1, 2, 3};
访问：
a[0]
a[1]
a[2]
它和普通数组类似，但可以直接使用 STL 的比较等操作。
竞赛中特别常见：
priority_queue<
array<int,3>,
vector<array<int,3>>,
greater<array<int,3>>
> q;
比如保存：
{距离, 节点, 状态}
十三、bitset —— 位集合
如果只需要记录大量：
0 / 1
状态，可以使用：
bitset<1000> b;
访问：
b[i]
修改：
b.set(i); // 设为 1
b.reset(i); // 设为 0
b.flip(i); // 取反
统计有多少个 1：
b.count();
全部清零：
b.reset();
竞赛中常用于：
- 状态压缩
- 位运算优化
- 集合表示
十四、常用查找函数
lower_bound
lower_bound(a.begin(), a.end(), x);
寻找：
第一个
>= x的位置。
例如：
vector<int> a = {1, 3, 5, 7};
auto it = lower_bound(a.begin(), a.end(), 4);
得到：
5
upper_bound
upper_bound(a.begin(), a.end(), x);
寻找：
第一个
> x的位置。
记忆：
lower_bound → >= x
upper_bound → > x
对于数组下标：
int pos = lower_bound(a.begin(), a.end(), x) - a.begin();
复杂度：
O(log n)
前提通常是：
数据已经有序。
十五、竞赛中最常用容器对照
| 容器 | 特点 | 常见用途 |
|---|---|---|
vector |
动态数组 | 存数据、邻接表 |
stack |
后进先出 | 单调栈、括号 |
queue |
先进先出 | BFS |
deque |
两端操作 | 0-1 BFS、单调队列 |
priority_queue |
自动维护最大/最小值 | Dijkstra、贪心 |
set |
有序、不重复 | 判重、有序集合 |
multiset |
有序、可重复 | 动态维护有序序列 |
map |
有序键值对 | 映射、计数 |
unordered_map |
哈希键值对 | 快速查询 |
bitset |
大量 01 状态 | 位运算优化 |
十六、如何选择？
看到：
需要一个普通动态数组
想到：
vector
看到：
先进先出 / BFS
想到：
queue
看到：
后进先出
想到：
stack
看到：
两边都要加入删除
想到：
deque
看到：
不断取最大值 / 最小值
想到：
priority_queue
看到：
需要自动排序 + 去重
想到：
set
看到：
自动排序，但是允许重复
想到：
multiset
看到：
建立 key → value 的对应关系
想到：
map
十七、最容易出错的地方
1. pop() 不返回元素
错误：
int x = q.pop();
正确：
int x = q.front();
q.pop();
2. 空容器不能直接取元素
例如：
q.front();
st.top();
v.back();
之前最好保证：
!q.empty()
3. multiset.erase(x) 删除全部 x
删除一个：
auto it = s.find(x);
if(it != s.end())
s.erase(it);
4. map[key] 可能自动创建元素
例如：
map<int,int> mp;
cout << mp[100];
即使原本没有 100，也会自动产生：
100 -> 0
如果只想判断是否存在，使用：
mp.find(100)
5. priority_queue 默认是大根堆
priority_queue<int> q;
顶部是：
最大值
想要最小值：
priority_queue<int, vector<int>, greater<int>> q;
十八、必须熟练掌握的部分
信息学竞赛中，建议至少做到看到下面代码可以立即知道含义：
vector<int> v;
stack<int> st;
queue<int> q;
deque<int> q;
priority_queue<int> q;
priority_queue<int, vector<int>, greater<int>> q;
set<int> s;
multiset<int> s;
map<int,int> mp;
unordered_map<int,int> mp;
其中最重要的几个是：
vector
queue
priority_queue
set
map
再结合：
sort
lower_bound
upper_bound
基本可以覆盖大多数基础和提高组竞赛中的 STL 使用场景。
这里空空如也
有帮助，赞一个