算法竞赛向 C++ Standard Library 使用速查

2.1 pair

• operator= ：重载了赋值运算符用于拷贝。
• first / second ：访问第一项或第二项。
• std::make_pair(a,b) ：新建元素对，自动检测类型。
• operator ：重载了各种比较运算符，按第一关键字、第二关键字顺序比较。

2.2 tuple

• operator= ：重载了赋值运算符用于拷贝。
• std::get(tp) ：获取元组的第 i 项。
• std::get(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 判断该字符串小于 / 等于 / 大于参数字符串。
• 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 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.1 迭代器

声明：形如 vector::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.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() ：调整为恰好长度。

4.2 deque

• push_front(x), pop_front()

其余与 vector 类似。

4.3 list

• 无随机访问接口。
• insert(iter, val) / erase(iter) ：插入与删除变为常数时间复杂度，参见 vector。
• sort(cmp) ：为链表特殊设计的
  $O(n\log n)$

  稳定排序算法。

其余与 deque 类似。

5.1 set / multiset

set：类似 priority_queue，可自定义比较方式。

Find：

• crbegin()
• count(x) ：返回值为 x 的元素数量。
• lower_bound(x) / upper_bound(x) ：为 set 特殊定制的对数时间复杂度 lower_bound 和 upper_bound。

Modify:

• insert(x) ：插入元素 x。返回 pair，表示插入元素的迭代器与插入是否成功。 对于 multiset，由于插入不会失败，insert 只返回迭代器。
• erase(x) ：删除所有值为 x 的元素，返回删除元素的个数。 erase(iter) ：删除迭代器指向的元素，(C++11) 返回指向被删除元素的后一个元素的迭代器。 erase(first, last)：左闭右开区间删除，(C++11) 返回指向被删除元素的后一个元素的迭代器。

auto it = s.find(x);
s.erase(it);

5.2 map / multimap

map：可自定义比较方式。

• 对迭代器解引用得到 pair。
• insert(pair)
• at[key] / operator[key]：前者会做越界检查，抛出异常。

其余与 set 类似。