【STL】算法竞赛常用STL

更新于 分类于 阅读次数： 本文字数： 5k 阅读时长 ≈ 5 分钟

一些常用STL

Algorithm

sort

1
2
sort(a, a + n, &cmp); 
stable_sort(a, a + n, &cmp); //稳定排序

lower_bound/upper_bound

条件：有序序列

默认：lower_bound找序列中第一个大于等于val的数，upper_bound找序列中第一个大于val的数。

1
2
3
4
lower_bound(a, a + n, val);  //返回第一个大于等于val的指针
upper_bound(a, a + n, val);  //返回第一个大于val的指针
lower_bound(a, a + n, val, greater<T>());  //返回第一个小于等于val的指针
upper_bound(a, a + n, val, greater<T>());  //返回第一个小于val的指针

equal_range

条件：有序序列

1
2
3
equal_range(begin, end, val); 
//在[begin, end)区间寻找值为val的区间，begin、end为迭代器或指针
//返回一个pair，值为val的区间两端点迭代器（左闭右开），查找失败时first和second相同

注意返回的是迭代器，如果是数组即pair<int*,int*>，如果是vector即pair<vector<int>::iterator,vector<int>::iterator>

unique

条件：有序序列

1
2
3
unique(begin, end); 
//在[begin, end)区间用不重复元素替代重复元素，begin、end为迭代器
//返回最后一个不重复元素后一位的迭代器

常与erase操作一起用达到改变删去重复元素并改变数组长度的作用

1
a.erase(unique(a.begin(), a.end()), a.end());

注意用在数组时是左闭右开。

next/prev_permutation

获取排列

next_permutation先小后大，prev_permutation先大后小

返回bool值，若有下一排列就返回true，否则返回false，且返回false的同时将数组改变为下一排列（从头开始的第一个排列）

1
2
next_permutation(a, a+n, &cmp); //数组
next_permutation(begin, end, &cmp); //迭代器
  • 在10之后很慢

reverse

翻转数组或迭代器

1
2
reverse(a, a+n);
reverse(begin, end);

array

.begin(), .end(), .size(), .max_size(), .empty(), .at(), .front(), .data()都与vector相同

.fill(n)把数组里的数都赋值为n

声明：array<int, n> a={xx,xx,…}，n个元素，n只能为常数

访问：auto it=a.begin(),it++

array与数组储存在栈中，vector储存在堆中

utility

pair

1
2
3
4
pair<T1, T2> p;
p.first
p.second
make_pair(a,b)

swap

C++11前在algorithm头文件，之后在utility头文件

set/multiset

set无重复元素，multiset元素可重复

声明：

1
2
3
4
5
set<T, &cmp> st;
multiset<T, &cmp> st;
set<T> st(st1); 
set<T> st(st2.begin(), st2.end()); //用另一个set声明
set<T> st(arr, arr+n); //用数组声明

使用：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
set<T>::iterator it; //声明迭代器
st.begin(); st.end(); //获得首、尾迭代器
st.rbegin(); st.rend(); //获得反向首位迭代器

st.empty(); //为空返回1，不空返回0
st.size(); st.max_size(); //返回集合实际大小和最大容量

st.insert(x); //插入x
st.insert(arr, arr+n); //插入数组
st.insert(begin, end); //插入一段数据，可以是别的容器

st.erase(x); //删除x
st.erase(it); //删除迭代器指向的元素，删后迭代器
st.erase(begin, end); //删除一段数据

st.find(x); //查找x元素，找不到返回st.end()，找到返回指向该元素的迭代器
st.count(x); //查询x元素的个数（0或1）

st.clear(); //清空集合

st.swap(st1); //交换

vector

声明：

1
2
3
4
5
6
7
8
9
vector<T> a;
vector<T> a = (n, i); //将前n个赋值为i
//N*M的二维数组
//方法1：
vector<vector<T> > a(N); 
for(int i = 0; i < N; i++)
    a[i].resize(M);
//方法2：
vector<vector<T> > a(N, vector<T>(M));

使用：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
vector<T>::iterator it; //声明迭代器
a.begin(); a.end(); //获得首、尾迭代器
a.rbegin(); a.rend(); //获得反向首位迭代器

a.empty(); //为空返回1，不空返回0
a.size(); a.max_size(); //返回容器实际大小/最大容量
a.capacity(); //已分配内存中最多容纳元素个数
a.resize(x); //将容器大小置为x

a.push_back(); a.pop_back(); //向尾端插入元素/删除尾端元素
a.insert(it, n, i); //在it位置之前插入n个值为i的元素，n省略即插入一个，返回原位置
a.erase(it); a.erase(it, it+n); //删除指定位置/区间位置的元素，返回下一个数据的位置
a.assign(n, i); //将前n个元素赋值i
a.assign(arr, arr+n); //将数组元素赋值给这个容器

a.at(i) = j; a[i] = j; //访问第i个元素（0起始）
a.front(); a.back(); //取最前/最后元素

a.clear(); //清空容器

a.swap(a1); //交换

a.reverse(begin, end); //元素翻转

map/multimap

映射，一一映射和多重映射，键值有序，查询O(n)

声明：

1
2
std::map<T1, T2> mp; //单重映射，允许下标访问
std::multimap<T1, T2> mp; //多重映射，不允许下标访问

使用：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
mp.at(key); mp[key]; //用键值访问
it->first; it->second; //迭代器访问键值、映射值

a.size(); a.max_size(); //返回容器实际大小/最大容量

mp.begin(); mp.end(); //获得首、尾迭代器

st.insert(x); //插入x
st.insert(arr, arr+n); //插入数组
st.insert(begin, end); //插入一段数据，可以是别的容器

st.erase(x); //删除x
st.erase(it); //删除迭代器指向的元素，删后迭代器
st.erase(begin, end); //删除一段数据

unordered_map/unordered_set

无序map和set，查询O(1)，与map、set基本相同，但不支持迭代器遍历

1
2
std::unordered_set<T> st;
std::unordersd_map<T1, T2> mp;

stack

栈，先进后出

声明：

1
stack<T> st;

使用：

1
2
3
4
5
6
st.empty(); //如果栈空返回1，不空返回0

st.pop(); st.push(); //入栈、出栈
st.top(); //取栈顶元素

st.size(); //返回栈的大小
  • 不可用迭代器遍历
  • 没有clear

queue

队列，先进先出/双端队列，前后都可入队、出队

声明：

1
2
3
4
queue<T> q;
queue<T> q(n, i); //初始化为由n个i组成的队列

deque<T> q0;

使用：

1
2
3
4
5
6
q.empty(); //如果队列空返回1，不空返回0

q.pop(); q.push(); //队尾入队、队头出队
q.front(); q.back() //取队头、队尾元素

q.size(); //返回栈的大小
  • 不可用迭代器遍历
  • 没有clear

deque

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
q.begin(); q.end(); //获得首、尾迭代器
q.rbegin(); q.rend(); //获得反向首位迭代器

q.empty(); //为空返回1，不空返回0
q.size(); q.max_size(); //返回容器实际大小/最大容量
q.capacity(); //已分配内存中最多容纳元素个数
q.resize(x); //将容器大小置为x

q.push_back(); q.pop_back(); //向队尾插入元素/删除队尾元素
q.push_front(); q.pop_front(); //向队头插入元素/删除队头元素
q.insert(it, n, i); //在it位置之前插入n个值为i的元素，n省略即插入一个，返回原位置
q.erase(it); q.erase(it, it+n); //删除指定位置/区间位置的元素，返回下一个数据的位置
q.assign(n, i); //将前n个元素赋值i
q.assign(arr, arr+n); //将数组元素赋值给这个容器

q.at(i) = j; q[i] = j; //访问第i个元素（0起始）
q.front(); q.back(); //取最前/最后元素

q.clear(); //清空容器

q.swap(q1); //交换

q.reverse(begin, end); //元素翻转

priority_queue

优先队列，堆结构

声明：

1
2
3
4
5
6
7
priority_queue<T, vector<T> > q; //降序，大根堆
priority_queue<T, vector<T>, greater<T> > q; //升序，小根堆
//非结构体内自定义排序：
priority_queue<T, vector<T>, cmp> q;
struct cmp {
	bool operator() (name y, name z) { return y.x<z.x; }
}

使用：

1
2
3
4
5
6
q.empty(); //如果队列空返回1，不空返回0

q.pop(); q.push(); //队尾入队、队头出队
q.front(); q.back() //取队头、队尾元素

q.size(); //返回栈的大小

list

链表

声明：

1
list<T> ls;

使用：包括迭代器、insert等

bitset

二进制，以数组形式保存

声明：

1
bitset<n> a(string("1010001")); //n为长度，可以直接用a[i]访问

使用：

1
2
3
4
5
6
7
8
9
a.count(); //返回有多少个1
a.test(i); //返回第i个是否为1
a.set(); //全置为1
a.set(x); //第x个置为1
a.set(x,y); //把y赋值给第x个

bitset<M> f[N];
f[n]|=f[k]; //表示按位相与
f[n]<<=k; //表示整体向左k位