面向竞赛的 C++ STL 介绍

参考链接：
https://space.bilibili.com/231911980/lists/4220963?type=season
https://space.bilibili.com/498363953/lists/241249?type=season
https://blog.csdn.net/weixin_51797626/article/details/123317216?spm=1001.2014.3001.5501

vector

涉及函数:at,back,push_back,pop_back,size,erase,clear,begin,rbegin,end,resize

  • 创建数组
1
2
3
4
5
vector<int> v//创建int类型的空数组v
v.resize(n)//创建后可随时自定义大小
vector<int> v(10)//创建int类型的数组v，包含10个元素，所有元素默认初始化为0
vector<int> v(10,66)//创建int类型的数组v，包含10个元素，所有元素默认初始化为66
vector<int> v={1,2,3,4}//通过列表初始化创建
  • 访问元素
1
2
int x=v[1];
int y=v.at(1);//会进行边界检查，可以防止越界
  • 修改元素
1
2
3
4
5
v[1]=1;
v.push_back(1);//在数组最后添加元素1
v.pop_back();//删除数组最后一个元素
v.clear();//清空
v.erase(v.begin()+n);//删除第n+1个元素
  • 遍历元素
1
2
3
4
5
6
7
8
9
10
//常规
for(int i=0;i<v.size();i++)
    cout<<v[i]<<' ';
//范围基
for(int num:v)
    cout<<num<<' ';
//pair/结构体
vector<pair<int,int>> v_pair;
for(const auto& [a.b]:v_pair)
    cout<<a<<' '<<b<<' ';
  • 查询大小
1
2
3
int size=v.size()//返回unsigned int，>=0
if(v.empty())...//检查v是否为空
if(v.size())...//检查v是否为空

例题

stack

涉及函数:push,top,pop,size,empty
常用于:单调栈，括号匹配，dfs，tarjan 求强连通分量，波兰表达式(计算器)

  • 初始化
1
2
3
stack <int> stk;//栈不允许列表初始化和填充相同元素
stack <int> stk2(stk);
stack <int> stk3=stk2;
  • 出入栈

    如果你问一个人 push 的反义词是什么，如果 TA 说是 pop，那么 TA 一定是 c 艹选手

1
2
3
4
5
6
7
stk.push(10);//[10(top)]
stk.push(20);//[10,20(top)]
stk.push(50);//[10,20,50(top)]
cout<<stk.top()<<'\n'//50,[10,,20,50(top)]
stk.pop()//[10,20(top)],使用pop前判断非空
if(stk.size())stk.pop();
if(!stk.empty())stk.pop;
  • 清空栈
1
while(stk.size())stk.pop();//时间复杂度O(n)
  • 数组模拟
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//以下标1为栈底，变量top为栈顶
int stk[N],top=0;
//入栈x
stk[++top]=x;
//出栈
top--;
//取出栈顶元素
cout<<stk[top]<<'\n';
//获取大小
cout<<top<<'\n';
//判断是否为空
if(top)...
//遍历栈
for(int i=1;i<=top;i++)...

例题

  • 也可用 vector,但 pop 时时间复杂度为 O(n)

队列

queue

涉及函数:push,pop,front,back,size,empty
常用于:单调队列，模拟，约瑟夫环，bfs，分支限界搜索等

  • 创建队列
1
queue<int> q;
  • 出入队列
1
2
q.push(10);
q.pop(10);//使用pop前判断非空
  • 访问元素
1
2
q.front();
q.back();

例题

  • 检查队列大小/是否为空（同上）

queue和stack一样，不允许遍历

  • 数组模拟
1
2
3
4
5
int q[N]//N为push的最大次数
int qh=1,qt=0;//q_head,q_tail;[qh,qt]为有效区间
q[++qt]=x;//入队
qh++;//出队
qt-qh+1//大小

deque

1
2
3
4
5
6
7
8
9
10
11
//支持遍历，头尾均支持出入队
deque<int> dq;
dq.push_front(1);
dq.push_bacK(1);
int t = dq.front();
t = dq.back();
dq.size();
dq.empty();
//弹出时先判断是否为空
dq.pop_front();
dq.pop_back();

例题

priority_queue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//用于每次提取队列种最大的元素或最小的元素
//自动排序内部数，小到大或大到小，不支持遍历

priority_queue<int, vector<int>, greater<int>> q1; 
//greater是小根堆，用vector装载内部元素
priority_queue<int, vector<int>, less<int>> q2; 
//less是大根堆

q1.push(3), q2.push(2);
int t = q1.size();
while (q1.size())
{
	int t = q1.top();//小根堆所以取出的数是所有数内最小的
	q1.pop();
	cout << t << ' ';
}

例题

string

1
2
3
int t=a.find('x');//获取第一个字符x出现的位置的下标
string g=a.substr(0,3);//从下标0开始(包括0)往后取三个字符
stinrg g=a.substr(3)//从下标3开始到结束

algorithm

next_permutation,prev_permutation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//全排列函数
#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, a[100];
    cin >> n;
    for (int i = 1; i <= n; i++)
        a[i] = i;
    do
    {
        for (int i = 1; i <= n; i++)
            cout << a[i] <<" ";
        cout << endl;
    } while (next_permutation(1 + a, 1 + a + n));
}

lower_bound

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//找大于等于某数的第一个数，查找的数组必须有序

int n = 7;//7个数
int a[] = { 2,4,6,7,9,12,111 };
	
int t = lower_bound(a, a + n, 8) - a;//查询范围：0 ~ 6。数组中大于等于8的第一个数

if (t != n)//找不到会返回边界a+n，即7
	cout << a[t] << endl;

int b[] = { 0,2,4,6,7,9,12,111 };
t = lower_bound(b + 1, b + n + 1, 8) - b;//查询范围：1~8

if (t != n + 1)//找不到会返回边界，边界是 8
	cout << b[t] << endl;

unique

1
2
3
4
5
6
7
8
vector<int> vec = { 1,3,4,5,1,1,9 };
sort(vec.begin(), vec.end());
	
//unique本身的功能是将排序后的数组内的所有重复元素在 O(n) 时间内堆积到数组末端
//同时它会返回一个指针/下标（区别于你传入的是容器还是数组） —— 堆积的第一个重复元素的位置
	
vec.erase(unique(vec.begin(), vec.end()), vec.end());
//我们再利用vector的区间删除功能就能完成去重的过程

set,map

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
//可以自动排序去重
set<int> se;
//关键字 关键值
map<int, int> mp;//map相当于拥有了关键值的set

//插入
se.insert(3);//插入一个 3 关键字

mp.insert({ 1,2 });//插入一个 1 关键字，并给这个关键字的关键值赋值 2
mp.insert({ 1,1 });//因为 1 关键字已经存在，所以把关键值修改成 1

// mp.insert({ 1,2 }) 等价于
mp[1] = 2;

mp[1] += 2;//1 关键字的关键值 + 2


//遍历
for (auto j : se)cout << j << endl;

for (auto j : mp)
	cout << j.first << ' ' << j.second << endl;//两个值

//删除
mp.erase(3); se.erase(3);//删除关键字为 3 的元素

//如果是遍历删除 map 内特定的第 K 个数，跟 vector 删除一样要注意指针衔接
int k = 0;
for (auto it = mp.begin(); it != mp.end();k++) {
	if (k == K)it = mp.erase(it);
	else it++;
}//迭代器方式

int t = mp.count(3);//返回指定元素出现的次数
t = mp.size();//返回map中元素的个数

//查找
auto j = mp.find(3);//查找 3 关键字在 map 内的下标
//如果不存在则 j == mp.end()
if (j != mp.end())cout << (*j).first;

auto g = mp.lower_bound(3);//查找 map 内第一个大于等于 3 的数的下标
//如果不存在则 g == mp.end()
if (g != mp.end())cout << (*g).first;

pair

一个变量携带两个值，可以映射数组中对应元素的下标

1
2
3
pair<int, int> pii;
cin >> pii.first >> pii.second;
cout << pii.first << ' ' << pii.second;

例题