因网络上 STL 教程大多零散且缺乏严谨性，本文对算法竞赛所需 C++ Standard Library 做了一个较为全面的总结。
全文主要参考以下文档：
Containers library - cppreference.com C++ 标准库简介 - OI Wiki如有能力，阅读原文可获得更深入的了解。
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 ( 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::make_tuple(a,b,c,...) ：新建元组，自动检测类型。 operator<=> ：重载比较运算符，同样是顺序关键字比较。 …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 公共性质
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
Find:
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_queuestd::priority_queue<TypeName, Container, Compare> ：类型名，底层容器，比较类型。
大根堆，默认用 < 比较大小，即 Compare 传入 std::less<T> 。亦可选择传入 std::greater<T> 使用 > 作为比较符号，进而构造出小根堆。
函数同 queue ，但 push() / pop() 为对数时间复杂度。
参照 std::less<T> 的实现，自定义比较方式，需传入一个重载了 operator() 的结构体。
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, Compare> ：类似 priority_queue ，可自定义比较方式。
Find：
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 ); s . erase ( it );
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 函数。
查看更多关于算法竞赛向 C++ Standard Library 使用速查的详细内容...