STL 奇技淫巧食用指南
STLGirlfriend
2018-08-06 22:31:02
STL 只会用 `std::string`、`std::sort`、`std::queue`、`std::stack`、`std::set`、`std::map`，再不济加个 `std::vector`？No！STL 的精妙不止于此，用好可以帮你省下一大段代码。
# 说在前面：STL 中的函数调用的一般方式
在开始之前，我们要了解一下 STL 中的函数调用的一般方式：传入一个**左闭右开**区间，这里就以 `std::sort` 为例说明一下（假设要操作的东西叫做 $A$）：
如果是 `std::vector` 等 STL 容器的话，多半会给你一个 `begin` 和一个 `end` 函数，代表这个容器左端点和右端点 $+ 1$（因为是左闭右开所以要 $+ 1$）的迭代器（一个类似指针的东西），例如将 $A$ 排序：
```c++
std::sort(A.begin(), A.end());
```
如果从 $A_l$ 到 $A_r$ 排序（这里 $l$ 和 $r$ 从 $0$ 开始）：
```c++
std::sort(&A.begin() + l, &A[r] + 1);
```
如果是一般数组，没有现成的迭代器，但是用指针一样可以，如将 $A_1$ 到 $A_n$ 排序：
```c++
std::sort(&A[1], &A[n] + 1);
```
如果从 $A_l$ 到 $A_r$ 排序：
```c++
std::sort(&A[l], &A[r] + 1);
```
有几点要注意的：
1. 因为是左闭右开区间所以右端点要 $+ 1$！$+ 1$！ $+ 1$！
2. `&` 是取地址符，我只到大家都爱写成 `A + 1, A + n + 1` 但是用 `&` 更加直观（个人认为）。
为方便起见，下文中将这样的区间记为 `[I]` 或 `[I A]`。
# `<algorithm>` 中各种你想不到的函数
如果想求数组最值或者想统计元素的出现次数等一些简单的操作时，还在傻乎乎 `for` 循环？最然手写也只有几行，但是直接使用 STL `<algorithm>` 库里的函数不容易写错，有可能还有优化加成（OS：这种操作能优化多少啊）。
- `std::back_inserter(A)`：返回可以在 $A$ 中插入元素的迭代器（后文会用到）。
- `std::find([I], x)`：在区间中查找是否有元素为 $x$。
- `std::copy([I], std::back_inserter(A))`：拷贝区间内的元素到 $B$。
- `std::fill([I], x)`：将区间全赋值为 $x$。
- `std::transform([I], std::back_inserter(A), f)`：对于区间内每个的元素 $x$，将 $f(x)$ 赋给 $A$。
- `std::reverse([I])`：翻转区间。
- `std::random_shuffle([I])`：使用 `rand()` 函数随机打乱区间。
- `std::unique([I])`：删除相邻的重复元素（只会把元素移到后面，并返回去重后元素的结尾迭代器）。
- `std::is_sort([I])`（C++11）：判断区间是否有序。
- `std::merge([I A], [I B], std::back_inserter(C))`：合并两个有序容器 $A$ 和 $B$，将结果存入 $C$。
- `std::max_element([I])`：区间最大值。
- `std::min_element([I])`：区间最小值。
- `std::next_permutation([I])`：求全排列中的下一个排列，如果已经是最后一个了返回 `false`。
- `std::prev_permutation([A])`：求全排列中的上一个排列，如果已经是第一个了返回 `false`。。
# 蜜汁快的 `std::vector::insert`
在 C++ 官方文档中，`std::vector::insert` 的时间复杂度是 $O(n)$ 的，但是在 GCC 的 STL 实现中非常的快，据说是分块实现的，$O\left(\sqrt{n}\right)$（此处存疑）。
所以运用这个东西，我们可以做一些一般需要平衡树等数据结构才能做的题，就来个模板题吧：[【P3369】【模板】普通平衡树 - 洛谷 ](https://www.luogu.org/problemnew/show/P3369)：
```c++
#include <cstdio>
#include <vector>
#include <algorithm>
int main() {
int n;
scanf("%d", &n);
std::vector<int> v;
while (n--) {
int opt, x;
scanf("%d %d", &opt, &x);
if (opt == 1) {
v.insert(std::upper_bound(v.begin(), v.end(), x), x);
} else if (opt == 2) {
v.erase(std::lower_bound(v.begin(), v.end(), x));
} else if (opt == 3) {
printf("%d\n", std::lower_bound(v.begin(), v.end(), x) - v.begin() + 1);
} else if (opt == 4) {
printf("%d\n", v[x - 1]);
} else if (opt == 5) {
printf("%d\n", *--std::lower_bound(v.begin(), v.end(), x));
} else if (opt == 6) {
printf("%d\n", *std::upper_bound(v.begin(), v.end(), x));
}
}
}
```
# `unordered` 系列：用哈希表实现的 `map` 和 `set`
`std::map` 和 `std::set` 固然好，但是 $O\left(\log n \right)$ 的复杂度有些时候着实不太方便，如果你不需要自动排序，用哈希表实现的 `std::unordered_map` 和 `std::unordered_set` 将是你更好的选择。
`unordered` 系列属于 C++11 新特性，在先前的 C++ 标准中属于 TR1 扩展，所以她们的用法如下：
```c++
/* with C++11 */
#include <unordered_set>
#include <unordered_map>
std::unordered_map<int, int> mp;
std::unordered_set<int> st;
/* without C++11 */
#include <tr1/unordered_set>
#include <tr1/unordered_map>
std::tr1::unordered_map<int, int> mp;
std::tr1::unordered_set<int> st;
```
其余用法与 `std::map` 和 `std::set` 一致。
对于自定义类型，`unordered` 系列需要传入自定义哈希函数，写法比较特别，这里以 `std::pair<int, int>` 为例：
```
#include <unordered_set>
struct Hash {
size_t operator ()(const std::pair<int, int> &p) const {
const size_t h1 = std::hash<int>{}(p.first);
const size_t h2 = std::hash<int>{}(p.second);
return h1 ^ h2;
}
};
std::unordered_set< std::pair<int, int>, Hash > S;
```
同样，也提供支持重复元素的 `std::unordered_multimap` 和 `std::unordered_multiset`。
# 神奇的数据结构库：`pb_ds`：
严格意义上来说，这一部分已不属于标准 STL，而属于 GCC 的扩展。
`pb_ds`，全称 Policy-Based Data Structures（基于策略的数据结构），封装了一些高级数据结构。
注意，因为 `pb_ds` 的命名空间 `__gnu_pbds` 是下划线开头的，根据 [关于 NOI 系列赛编程语言使用限制的规定](http://www.noi.cn/newsview.html?id=229&hash=878FD2&type=6) 是不能使用的，但是据说有人用了没事，这个大家自行取舍。
## 优先队列
`pb_ds` 库中的优先队列 `gnu_pbds::priority_queue` 定义在 `<ext/pb_ds/priority_queue.hpp>` 头文件中，模板参数如下：
1. 数据类型，不解释。
2. 比较器，默认为 `std::less`，从大到小，如果需要从小到大需要传入 `std:greater`。
3. 堆类型，提供 `__gnu_pbds::binary_hrap_tag`（普通二叉堆，默认）、`__gnu_pbds::thin_heap_tag`（斐波那契堆）、`__gnu_pbds::pairing_heap_tag`（配对堆，最常用）。
例如，声明一个 `int` 类型，从小到大比较，使用配对堆的优先队列 `Q`，需要这么写：
```c++
#include <ext/pb_ds/priority_queue.hpp>
__gnu_pbds::priority_queue< int, std::greater<int>, __gnu_pbds::pairing_heap_tag > Q;
```
该优先队列大部分操作与 `std::priority_queue` 相同，但是多了一些操作：
1. 遍历，该优先队列提供 `point_iterator` 类型（`push` 操作会返回）和 `begin` 和 `end` 迭代器，所以可以像这样遍历：
```c++
for (__gnu_pbds::priority_queue< int, std::greater<int>, __gnu_pbds::pairing_heap_tag >::point_iterator it = Q.begin(); it != Q.end(); ++it) {
/* Do something... */
}
```
（这一连串参数让人吐血，有 C++11 的话建议用 `auto` 代替。）
2. 修改，提供 `modify` 函数，但是只能凭迭代器修改，实际运用价值并不高。
3. 合并，使用 `A.join(B)` 将 $B$ 合并到 $A$ 中。
## 平衡树
`pb_ds` 库中的平衡树 `__gnu_pbds::tree` 定义在 `<ext/pb_ds/tree_policy.hpp>` 头文件中，并需要一并包含 `<ext/pb_ds/assoc_container.hpp>` 头文件，模板参数如下：
1. 第一个类型，和 `std::map` 中意义相同。
2. 第二个类型，同样和 `std::map` 中意义相同，如果要当成 `set` 来使用可以写成 `__gnu_pbds::null_type`（较老的 GCC 版本如 Lydsy Online Judge 需要改成 `__gnu__pbds::null_mapped_type`）。
3. 比较器，默认为 `std::less`，从小到大，如果需要从大到小需要传入 `std:greater`（别问我为什么和优先队列相反）。
4. 平衡树类型，提供 `__gnu_pbds::rb_tree_tag`（红黑树，默认），`__gnu_pbds::splay_tree_tag`（Splay）等，
5. `Node_Update`，默认为空，需要传入 `__gnu_pbds::tree_order_statistics_node_update` 解锁高级功能，也可以自己写 `Node_Update`，详情请自行查阅相关资料。
例如，声明一个使用 `int` 类型、类 `set`，从大到小比较，使用 Splay，解锁高级功能的平衡树 `T`，需要这么写：
```c++
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
__gnu_pbds::tree< int, __gnu_pbds::null_type, std::greater<int>, __gnu_pbds::splay_tree_tag, __gnu_pbds::tree_order_statistics_node_update > T;
```
解锁高级功能的该平衡树比一般 `std::map` 和 `std::set` 多了两个函数：
1. `find_by_order(k)`：查找第 $k$ 大的元素的迭代器（$k$ 从 $0$ 开始），如果未找到返回 `T.end()`。
2. `order_of_key(x)`：查找 $x$ 的名次（结果从 $0$ 开始），如果未找到返回……这个不太好说，举个例子，$\{1, 2, 3, 6\}$，`order_of_key(4)` 和 `order_of_key(5)` 返回 $3$，`order_of_key(19260817)` 返回 $4$。
该平衡树不支持重复元素，如果实在需要请自行实现。
# 结束语
其实现在 STL 的效率真心没那么不堪，基本可以比起手写的了，但是仍然具有一定局限性。所以，不要全盘使用 STL，更不要当「手写原教旨主义者」。