算法竞赛向 C++ Standard Library 使用速查
本文旨在对算法竞赛所需 C++ Standard Library 做一个全面而相对严谨的总结。
全文主要参考以下文档:
如有能力,阅读原文可获得更深入的了解。
1 STL 算法
均在 #include<algorithm>
定义。
std::sort(first,last,cmp)
排序为不降序列。
接受随机访问迭代器。可自定义比较函数。
平均时间复杂度 \(O(n \log n)\),C++11 后严格 \(O(n \log n)\)。
std::stable_sort(first,last,cmp)
排序为不降序列,且保持相等元素的顺序。
std::lower_bound(first,last,val,cmp)
返回指向首个不小于
val
的元素的迭代器,如无,返回last
。要求小于
val
的值和大于等于val
的值分居区间两侧。可自定义比较函数。若迭代器支持随机访问,对数时间复杂度,否则为线性。
std::upper_bound(first,last,val,cmp)
返回指向首个大于
val
的元素的迭代器,如无,返回last
。std::unique(first,last,cmp)
保留区间中所有连续等值区间的首个元素组成新序列,返回处理后序列的尾迭代器。
接受前向迭代器,可自定义判断相等的函数。
线性时间复杂度。
2 基本或特殊容器
注:C++11 新引入的容器,大部分头文件名与容器名一致。
pair
#include<utility>
:元素对。tuple
(C++11) :元组。bitset
#include<bitset>
:定长压缩 01 串,可在 \(O(\frac N K)\) 的时空复杂度内完成常见运算,\(K\) 对应操作系统位数。string
#include<string>
:字符串。
2.1 pair
operator=
:重载了赋值运算符用于拷贝。first
/second
:访问第一项或第二项。std::make_pair(a,b)
:新建元素对,自动检测类型。operator<=>
:重载了各种比较运算符,按第一关键字、第二关键字顺序比较。
2.2 tuple
operator=
:重载了赋值运算符用于拷贝。std::get<i>(tp)
:获取元组的第 i 项。std::get<T>(tp)
:获取元组中类型为 T 的项。std::tie(a,b,...)
:构造一个变量引用构成的元组.用于在赋值时将等号右侧的元组解包到左侧的a,b,...
等变量中。std::make_tuple(a,b,c,...)
:新建元组,自动检测类型。operator<=>
:重载比较运算符,同样是顺序关键字比较。
下面是一个应用 C++11 新引入的元组和列表初始化的 ExGCD 实现。
typedef tuple<ll,ll,ll> Tuple;
(ll a,ll b){
Tuple exgcdif(b==0) return {1,0,a};
,y1,d; tie(x1,y1,d)=exgcd(b,a%b);
ll x1return {y1,x1-(a/b)*y1,d};
}
2.3 string
与 vector
类似。其余重要特性如下:
c_str()
:生成一个 C 风格字符串(尾部置 0)并返回其头部指针。length()
:size()
的同义函数。append(str)
:后方追加字符串,返回*this
。append(first, last)
:区间插入版本。operator+
:连接两个字符串。compare(str)
:字典序比较。返回一个int
,用<0
/==0
/>0
判断该字符串小于 / 等于 / 大于参数字符串。operator<=>
:字典序比较的运算符重载。substr(pos=0, count)
:返回[pos, min(pos+count, size()))
的子串。时间复杂度与count
成线性。pop_back()
(C++11)find(str)
/rfind(str)
/find_first_of(c)
/find_first_not_of(c)
/find_last_of(c)
/find_last_not_of(c)
:找字符串或字符,返回位置。若无,返回npos=-1
。无时间复杂度保证,不建议使用。
2.4 bitset
bitset<N> bs(val / str)
:声明一个长度为 N 的 bitset
并设定初值。
& / ! / ^ / ~ / >> / <<
:支持 AND / OR / XOR / NOT / 右移 / 左移等位运算系列。operator==
:判断两个bitset
是否相同。test(idx) / operator[idx]
:前者会做越界检查,抛出异常。size()
count()
:返回 1 的个数。all()
(C++11) :检查是否全为 1。any() / none()
:检查是否存在 1 / 没有 1。set() / reset()
:所有位赋 1 / 0。flip()
:翻转 0 / 1。
3 STL 容器概览
以下部分均为 STL 容器相关内容。
3.1 迭代器
声明:形如 vector<int>::iterator iter = xxx.begin()
。C++11 后可用 auto
代替类型声明。
*iter
取值,iter++
后继。
双向迭代器可 iter--
,随机访问迭代器支持加减、比较运算。
begin()
,end()
:返回迭代器。end()
常作为 NULL 使用。cbegin()
,cend()
(C++11) :部分容器支持,返回只读迭代器。rbegin()
,rend()
:部分容器支持,返回反向迭代器。crbegin()
,crend()
:部分容器支持,返回只读反向迭代器。
3.2 公共性质
[first, last)
式迭代器构造,拷贝构造等。operator=
:重载了赋值运算符用于拷贝。empty()
:返回容器是否为空,即v.begin() == v.end()
。size()
:返回容器内元素个数。clear()
:清空容器。
4 序列式容器或容器适配器
序列式容器:
array
(C++11) :定长顺序表,常数随机访问。vector
#include<vector>
:顺序表,常数后段插入,常数随机访问。deque
#include<deque>
:顺序表,常数双端插入,常数随机访问。list
#include<list>
:链表,常数插入删除,双向迭代器。forward_list
(C++11) :单向版本。
容器适配器(均不支持迭代器):
queue
#include<queue>
:队列(FIFO)。适配双向变长序列式容器,即deque
(默认)或list
。stack
#include<stack>
:栈(LIFO)。适配变长序列式容器,即deque
(默认)、vector
或list
。priority_queue
#include<queue>
:大根堆。适配随机访问变长序列式容器,即vector
(默认)或deque
。
4.1 vector
Construct:
vector<T>(count,value)
:初始化时放count
个value
的拷贝在里面。
Access:
crbegin()
at(idx)
/operator[idx]
:前者会做越界检查,抛出异常。front()
,back()
:返回首尾元素引用。
Modify:
push_back(x)
/pop_back()
:均摊常数复杂度。insert(iter, val)
:于迭代器iter
前插入,返回指向被插入元素的迭代器。insert(iter, first, last)
:左闭右开区间插入,返回指向首个被插入元素的迭代器。 注意,此操作非常数时间复杂度。erase(iter)
:于迭代器iter
处删除,返回指向被删除元素的后一个元素的迭代器。erase(first, last)
:左闭右开区间删除,返回指向被删除元素的后一个元素的迭代器。 注意,此操作非常数时间复杂度。
Size:
resize(n)
:改变长度,可指定补充元素默认值。shrink_to_fit()
:调整为恰好长度。
vector<bool>
被特殊定义,使用方式较为复杂,不建议使用。
4.2 deque
push_front(x)
,pop_front()
其余与 vector
类似。
stack
top()
push(x)
pop()
queue
front()
push(x)
pop()
priority_queue
std::priority_queue<TypeName>
:Compare
默认使用std::less<T>
,即以operator <
作为大根堆的比较依据。std::priority_queue<TypeName, Container, Compare>
:亦可自行指定底层容器和比较函数对象。
例如,传入 std::greater<T>
将使用 >
作为比较符号,进而构造出小根堆。
自定义比较函数对象,可仿照以下代码:
#include<iostream>
#include<queue>
#include<vector>
typedef long long ll;
struct Vec{
,y;
ll x(){}
Vec(ll x,ll y){
Vecthis->x=x;this->y=y;
}
};
struct vecCompare{
bool operator () (const Vec& a,const Vec& b) const {
return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
};
int main(){
std::priority_queue< Vec, std::vector<Vec>, vecCompare > H;
.push(Vec(1,2));
H.push(Vec(2,1));
H=H.top();
Vec tstd::cout<<t.x<<","<<t.y;
}
用法基本同 queue
,但 push() / pop()
为对数时间复杂度。
4.3 list
- 无随机访问接口。
insert(iter, val)
/erase(iter)
:插入与删除变为常数时间复杂度,参见vector
。sort(cmp)
:为链表特殊设计的 \(O(n \log n)\) 稳定排序算法。
其余与 deque
类似。
5 关联式容器
不支持随机访问,双向迭代器,大部分操作为对数时间复杂度,红黑树实现。
set
/multiset
#include<set>
:元素有序。后者支持同值多元素。map
/multimap
#include<map>
:键有序。后者支持同键值多元素。
5.1 set / multiset
set<Key>
:默认使用operator <
比较(升序)。set<Key, Compare>
:也可使用类似priority_queue
的方法自定义比较函数对象Compare
。
Access:
crbegin()
count(x)
:返回值为x
的元素数量。lower_bound(x)
/upper_bound(x)
:为set
特殊定制的对数时间复杂度lower_bound
和upper_bound
。
没有 nth_element()
,对数时间复杂度查询第 k 大需自行手写平衡树或使用 pbds 库。
Modify:
insert(x)
:插入元素 x。返回pair<iterator, bool>
,表示插入元素的迭代器与插入是否成功。 对于multiset
,由于插入不会失败,insert
只返回迭代器。erase(x)
:删除所有值为 x 的元素,返回删除元素的个数。erase(iter)
:删除迭代器指向的元素,(C++11) 返回指向被删除元素的后一个元素的迭代器。erase(first, last)
:左闭右开区间删除,(C++11) 返回指向被删除元素的后一个元素的迭代器。
删除单个值为 x 的元素,可按如下方法进行:
auto it = s.find(x);
.erase(it); s
5.2 map / multimap
map<Key, T, Compare>
:可自定义比较方式。
- 对迭代器解引用得到
pair<Key, T>
。 insert(pair<Key, T>)
at[key]
/operator[key]
:前者会做越界检查,抛出异常。
其余与 set
类似。
6 无序关联式容器 (C++11)
单向迭代器,平均常数时间复杂度,Hash 实现。
若不支持 c++11,使用时需引入 TR1 扩展。例如,使用 unordered_map
需引入 #include<tr1/unordered_map>
头文件,使用时需写为 std::tr1::unordered_map
。
unordered_set
/unordered_multiset
#include<unordered_set>
:元素无序。unorderep_map
/unordered_multimap
#include<unordered_map>
:键无序。
只有单向迭代器,其余特性与有序版本类似。
此外,还可自行指定相等判定方式和 Hash 函数。
unordered_set<Key, Hash, KeyEqual>
unordered_map<Key, T, Hash, KeyEqual>
Hash 函数的自定义方法也与 priority_queue
中的方法类似:
#include<iostream>
#include<unordered_set>
typedef long long ll;
struct Vec{
,y;
ll x(){}
Vec(ll x,ll y){
Vecthis->x=x;this->y=y;
}
};
bool operator == (const Vec& a,const Vec& b){
return a.x==b.x&&a.y==b.y;
}
struct vecHash{
size_t operator () (const Vec& v) const {
return (v.x*ll(1E9)+v.y)%107897;
}
};
int main(){
std::unordered_set<Vec,vecHash> S;
.insert(Vec(1,2));
S.insert(Vec(2,3));
Sstd::cout<<S.count(Vec(1,2));
}