STL 算法
sort(bg,ed,cmp);//排序，bg ed为指针/迭代器。O(nlogn）
stable_sort(bg,ed,cmp);//稳定排序
nth_element(bg,mid,ed,cmp);//将mid的值替换为第mid-bg+1大的元素，mid左侧的值均小于mid的值，右侧均大于mid的值。O(n)
next_permutation(bg,ed,cmp);//生成下一个排列，不存在则返回0，最坏O(n)，均摊O(1)
prev_permutation(bg,ed,cmp);//生成上一个排列，不存在则返回0
lower_bound(bg,ed,x,cmp);//返回第一个大于等于x的位置，需先排序，O(logn)
upper_bound(bg,ed,x,cmp);//严格大于x的位置
binary_search(bg,ed,x,cmp);//二分查找，返回一个bool表示x是否存在
merge(bg,ed,bg2,ed2,res,cmp);//将[bg,ed)和[bg2,ed2)归并排序，结果存放在[res,res+ed-bg+ed2-bg2)，不破坏原数组的数据，O(n)。注意不能原地归并，要新开一个数组
reverse(bg,ed);//翻转，O(n)
unique(bg,ed,cmp);//去重，需先排序,返回迭代器，指向去重后容器中不重复序列的最后一个元素的下一个元素，O(n)
rotate(bg,mid,ed);//旋转，mid位置放到bg位置，元素相对顺序不变。示例：12345旋转后为34512。O(n)
random_shuffle(bg,ed,gen);//随机打乱顺序,gen为int类型函数，若为空则默认用rand的随机数生成器，O(n)
shuffle(bg,ed,default_random_engine(chrono::steady_clock::now().time_since_epoch().count()));//随机打乱，需要C++11
prev(it),next(it);//获取指针或迭代器it的前驱/后继，prev不能用于单向迭代器，需要C++11
iota(bg,ed,x);//将[bg,ed)依次赋值为x,x+1...x+ed-bg-1，需要C++11
for_each(bg,ed,func);//对[bg,ed)执行函数func
transform(bg,ed,bg2,func);//对[bg,ed)执行函数func，将返回值存入bg2
transform(bg,ed,bg2,bg3,func);//对[bg,ed)和[bg2,bg2+ed-bg)执行二元函数func，将返回值存入bg3
STL 容器
vector
vector 和 basic_string reserve 函数区别
vector<int>v(n);//初始化v中包含n个0
vector<int>v(n,x);//初始化v中包含n个x
vector<int>v(v2.begin(),v2.end());//用[v2.begin(),v2.end())初始化v
vector<int>v(a,a+n);//用数组a的[a,a+n)初始化v
vector<int>v(v2);//用v2初始化v
vector<int>::iterator it;//迭代器定义
vector<bool>v;//bool类型vector进行了特化，空间存储方式类似bitset
++it,--it,it++,it--,it+=n,it-=n;//迭代器自加自减，加n减n
v=v2,v={x,y,z};//赋值，列表赋值（C++11)
v<v2,v>v2,v<=v2,v>=v2,v==v2,v!=v2;
//按字典序比较，可用于vector，deque，list，set，map，queue，stack
//对于set和map按排序后字典序比较（对于map按pair类型比较），其他容器按插入先后顺序字典序比较
for(int o:v)printf("%d ",o);
//遍历，可用于vector，deque，list，set，map，unordered_set/map，需要C++11，o用auto类型定义较为方便
//注意：改变o的值不会改变v中对应元素的值
for(int&o:v)o=1;//将o改为引用类型可以改变v中对应元素的值
v.begin(),v.end();//迭代器iterator
v.rbegin(),v.rend();//反向迭代器reverse_iterator
v.cbegin(),v.cend();//const迭代器const_iterator，需要C++11
v.crbegin(),v.crend();//反向const迭代器const_reverse_iterator，需要C++11
v.push_back(x),v.pop_back();//尾部插入x，删除
v[p],v.at(p);//下标访问。at会检查越界抛出异常，返回为左值支持修改
v.size(),v.capacity();//v的大小，v的容量（实际占用内存），时间复杂度O(1)
v.resize(n),v.resize(n,x);//重设大小为n，并将新增的元素初始化为x，默认初始化为0，O(n)。可以让大小变小
v.reserve(n);//预留大小为n的空间（即重设容量为n），但不改变v的元素和大小，O(n)。若v中原来容量不为0，重设的容量可能大于n，但不大于2n。不会让容量变小（即v中原来容量大于n时无效果）。
v.shrink_to_fit();//将v的容量改为与大小相同，O(n)，C++11
v.empty(),v.clear();//v是否为空，清空
v.front(),v.back();//v的第一个元素，最后一个元素
v.assign(n,x);//将v赋值为n个x，原有元素清空
v.erase(it);//删除it
v.erase(bg,ed);//删除[bg,ed)
v.insert(it,x);//在it位置插入x，原有it及之后元素后移
v.insert(it,n,x);//从it开始插入n个x
v.insert(it,bg,ed);//从it开始插入另一个vector的[bg,ed)
v.emplace_back(x),v.emplace(it,x);//用法分别同push_back和insert，C++11，据说有效率提升但本机实测不明显，其他STL也有类似函数
v.swap(v2),swap(v,v2);//交换v和v2，O(1)
deque
//支持以上vector几乎所有函数，不支持reserve
//push_back和push_front速度和vector相当（机房本地测试），但访问和修改较慢
dq.push_front(x),dp.pop_front();//头部插入x，删除
list/forward_list
//支持以上deque除下标访问和shrink_to_fit以外全部函数
//list迭代器为双向迭代器不支持it+=n
//insert和erase单个元素为O(1)
//forward_list需要c++11，迭代器为单向迭代器，不支持--it和prev(it)
l.splice(it,l2);//从it位置开始插入l2
l.sort(cmp);//按cmp对l排序
l.unique();//将l去重，需先排序
l.merge(l2,cmp);//将l2按cmp顺序并入l，需先排序，l2被清空
set
//支持size，empty，clear，swap以及auto遍历
//迭代器不支持it+=n
set<int>s;//从小到大排序
set<int,greater<int> >s;//从大到小排序
set<int>s(s2.begin(),s2.end());//迭代器初始化
set<int>s(a,a+n);//数组初始化
set<int>s(s2);//将s初始化为s2
s.insert(x);//插入x，对于set返回pair<set<int>::iterator,bool>类型，分别为x的位置和是否插入成功，对于multiset只返回set<int>::iterator
s.erase(it);//删除it，C++11以后返回值为it的下一个位置迭代器
s.erase(x);//删除所有x，返回删除元素个数
s.erase(bg,ed);//删除[bg,ed) bg ed为迭代器
s.find(x);//返回第一个值为x的位置
s.count(x);//返回x的个数，对于multiset，时间复杂度O(logn+x的个数)
s.lower_bound(x),s.upper_bound(x);//返回迭代器，表示第一个值大于等于或大于x的位置
map
//支持以上set各种操作
map<int,int,greater<int> >mp;//从大到小排序
map<int,int>mp(p,p+n);//用pair类型数组p初始化
it->first,it->second;//迭代器相当于pair类型指针
mp[x],mp.at(x);//支持下标访问，at需要C++11
mp.insert({x,y}),mp[x]=y;//插入pair{x,y}，insert函数返回值规则类似set
bitset
//整数，string和char数组可以强制类型转换成bitset
//不支持迭代器
//类似string，可以存入unordered_set/map，可以用cin/cout输入输出
//转化为整数时0为最低位，转化为字符串时顺序与原先顺序相同，输出时从高位到低位输出
bitset<N>b;//定义初始值全为0的bitset，N为整型常量
bitset<N>b(x);//用无符号整型x初始化bitset，不超过unsigned long long范围
bitset<N>b(s);//用s初始化b，s可以是basic_string类型或bitset类型，若为basic_string类型则s中只能包含'0'或'1'
bitset<N>b(s,p);//用s从p位置开始到末尾初始化b，此处s只能为basic_string类型，下同
bitset<N>b(s,p,n);//用s从p开始的n个数初始化b，p和n都是整数
b=b2,b==b2,b!=b2;//b赋值为b2，b与b2是否相等，是否不等
b&b2,b|b2,b^b2,b<<n,b>>n,~b;//位运算，返回bitset类型
b&=b2,b|=b2,b^=b2,b<<=n,b>>=n;//位运算赋值
b[p],b.test(p);//下标访问。test会检查越界抛出异常，但返回为右值不能修改
b.flip(p),b.set(p),b.set(p,x),b.reset(p);//取反第p位，第p位设为1，第p位设为x，第p位设为0，O(1)
b.flip(),b.set(),b.reset();//所有位取反，所有位设为1，所有位设为0，O(n/w)
b.to_ulong(),b.to_ullong();//分别返回unsigned long和unsigned long long类型，表示将bitset转为整数，to_ullong需要C++11
b.to_string();//bitset转字符串
b.size(),b.any(),b.none(),b.all();//b的大小，是否存在1，是否全为0，是否全为1，all需要C++11，复杂度均为O(1)
b.count();//b中1的个数，O(n/w)
b._Find_first(),b._Find_next(p);//返回b中第一个1的位置，返回b中p以后不含p第一个1的位置，若不存在返回b的大小，O(n/w)
priority_queue
//priority_queue，queue，stack均不支持迭代器
priority_queue<int>pq;//大根堆
priority_queue<int,vector<int>,greater<int> >pq;//小根堆
pq.top(),pq.pop(),pq.push(x);//返回堆顶，删除堆顶，插入x
pq.size(),pq.empty();//返回大小，返回是否为空
//自定义比较函数（也适用于set和map）：
//法1：重载运算符
//法2：
struct cmp{bool operator()(int x,int y)const{return x>y;}};
priority_queue<int,vector<int>,cmp>pq;
unordered_set/map
//用法与set/map类似，但内部元素无序，不支持lower_bound/upper_bound
//通常需要c++11
//不需要c++11的方式（不保证比赛可用）：
//#include<tr1/unordered_set>
//#include<tr1/unordered_map>
//using namespace tr1;
//单次复杂度期望O(1)
//可被大量模P相等的数hack，单次复杂度卡到O(n)
//用pbds的hash不能避免被hack
1e7 以内卡哈希模数（不同编译器结果不同）：
#include<bits/stdc++.h>
using namespace std;
int main(){ios::sync_with_stdio(0),cin.tie(0);
unordered_map<int,int>st;
set<int>a;
for(int i=1;i<=10000000;++i)st[i]=1,a.insert(st.bucket_count());
for(auto o:a)cout<<o<<' ';
return 0;
}
(unordered_)multiset/map
//对应容器的可重版本
//(unordered_)multimap不能下标访问
basic_string/string
basic_string 只适用于基本类型或没有构造函数的结构体！不要用 basic_string 嵌套其他 STL！
（以下内容可能有误，需要重新整理）
//basic_string<bool>没有进行类似vector的特化
typedef basic_string<char> string;//string是basic_string模板实例化得到的模板类
//basic_string<unsigned>可以写成u32string
//basic_string支持迭代器，支持所有vector函数
//string可以存入unordered_map，其他类型的basic_string不能
string s;//初始化空串
string s(n,c);//初始化为n个c，c为char类型
string s(s2,p,n);//类似bitset
s=s2,s=s+s2,s+=s2;//赋值，向s后连接s2，s2可以是char类型（或basic_string对应类型）
s<s2,s>s2,s<=s2,s>=s2,s==s2,s!=s2;//比较
cin>>s,cout<<s;//输入输出，只适用于char类型的basic_string（即string）
s.assign(n,c),s.assign(s2,p,n);//赋值
s.size(),s.length();//串长
s.push_back(c);//尾部插入c
s.pop_back();//尾部删除，需要C++11！（vector的pop_back不需要C++11）
s.back(),s.front();//尾部，头部，需要C++11！（vector不需要）
s.append(n,c),s.append(s2,p,n);//向s后连接字符串
s.compare(s2);//比较，相等为0，s大为正，s小为负
s.substr(p),s.substr(p,n);//从p开始到结尾的子串，从p开始n个字符的子串
s.swap(s2);//交换
s.find(s2),s.rfind(s2),s.find(s2,x),s.rfind(s2,x);//从前往后，从后往前，从下标x开始，查找s2第一次出现位置，默认从开头或结尾开始，s2可为string或char，未找到返回string::npos，通常为-1
s.replace(p1,n1,n2,c),s.replace(p1,n1,s2,p2,n2);//子串替换
s.erase(p),s.erase(p,n),s.erase(it);//删除从p开始到结尾的子串，从p开始n个字符的子串，删除位置it
s.insert(p1,n2,c),s.insert(p1,s2,p2,n2);//从p1位置开始插入子串
queue
//支持size，empty
q.push(x),q.pop();//插入队尾，删除队首
q.front(),q.back();//队首，队尾
q={};//不支持clear，但可以这样清空。注意大括号内只能为空，不能有其它元素
stack
//支持size，empty
st.push(x),st.pop(),st.top();//入栈，出栈，返回栈顶
pair/tuple
//tuple需要C++11
//支持大小比较（按字典序）
pair<int,int>p;
tuple<int,int,double>t;//定义
tuple<int,int>t2;
p={x,y},p=pair<int,int>{x,y},t=make_tuple(x,y,z);//赋值，需要C++11，tuple不能用列表赋值
p=make_pair(x,y),p=(pair<int,int>){x,y};//赋值，不需要C++11
p.first,p.second;//访问pair
get<0>(t),get<1>(t),get<2>(t);//访问tuple，注意编号从0开始
t2=p;//可以用pair给同类型的tuple赋值，但不能用tuple给pair赋值
tie(x,y,z)=t,tie(x2,ignore)=t2;//将tuple赋值给变量，可以用ignore忽略某些返回值，对pair也适用