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 排序：

std::sort(A.begin(), A.end());

如果从 A_l 到 A_r 排序（这里 l 和 r 从 0 开始）：

std::sort(&A.begin() + l, &A[r] + 1);

如果是一般数组，没有现成的迭代器，但是用指针一样可以，如将 A_1 到 A_n 排序：

std::sort(&A[1], &A[n] + 1);

如果从 A_l 到 A_r 排序：

std::sort(&A[l], &A[r] + 1);

有几点要注意的：

因为是左闭右开区间所以右端点要 + 1！+ 1！ + 1！
& 是取地址符，我只到大家都爱写成 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】【模板】普通平衡树 - 洛谷：

#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 扩展，所以她们的用法如下：

/* 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 系列赛编程语言使用限制的规定是不能使用的，但是据说有人用了没事，这个大家自行取舍。

优先队列

pb_ds 库中的优先队列 gnu_pbds::priority_queue 定义在 <ext/pb_ds/priority_queue.hpp> 头文件中，模板参数如下：

数据类型，不解释。
比较器，默认为 std::less，从大到小，如果需要从小到大需要传入 std:greater。
堆类型，提供 __gnu_pbds::binary_hrap_tag（普通二叉堆，默认）、__gnu_pbds::thin_heap_tag（斐波那契堆）、__gnu_pbds::pairing_heap_tag（配对堆，最常用）。

例如，声明一个 int 类型，从小到大比较，使用配对堆的优先队列 Q，需要这么写：

#include <ext/pb_ds/priority_queue.hpp>

__gnu_pbds::priority_queue< int, std::greater<int>, __gnu_pbds::pairing_heap_tag > Q;

该优先队列大部分操作与 std::priority_queue 相同，但是多了一些操作：

遍历，该优先队列提供 point_iterator 类型（push 操作会返回）和 begin 和 end 迭代器，所以可以像这样遍历：
```
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 代替。）
修改，提供 modify 函数，但是只能凭迭代器修改，实际运用价值并不高。
合并，使用 A.join(B) 将 B 合并到 A 中。

平衡树

pb_ds 库中的平衡树 __gnu_pbds::tree 定义在 <ext/pb_ds/tree_policy.hpp> 头文件中，并需要一并包含 <ext/pb_ds/assoc_container.hpp> 头文件，模板参数如下：

第一个类型，和 std::map 中意义相同。
第二个类型，同样和 std::map 中意义相同，如果要当成 set 来使用可以写成 __gnu_pbds::null_type（较老的 GCC 版本如 Lydsy Online Judge 需要改成 __gnu__pbds::null_mapped_type）。
比较器，默认为 std::less，从小到大，如果需要从大到小需要传入 std:greater（别问我为什么和优先队列相反）。
平衡树类型，提供 __gnu_pbds::rb_tree_tag（红黑树，默认），__gnu_pbds::splay_tree_tag（Splay）等，
Node_Update，默认为空，需要传入 __gnu_pbds::tree_order_statistics_node_update 解锁高级功能，也可以自己写 Node_Update，详情请自行查阅相关资料。

例如，声明一个使用 int 类型、类 set，从大到小比较，使用 Splay，解锁高级功能的平衡树 T，需要这么写：

#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 多了两个函数：

find_by_order(k)：查找第 k 大的元素的迭代器（k 从 0 开始），如果未找到返回 T.end()。
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，更不要当「手写原教旨主义者」。

STL 奇技淫巧食用指南

说在前面：STL 中的函数调用的一般方式

<algorithm> 中各种你想不到的函数

蜜汁快的 std::vector::insert

unordered 系列：用哈希表实现的 map 和 set

神奇的数据结构库：pb_ds：

优先队列

平衡树

结束语

`<algorithm>` 中各种你想不到的函数

蜜汁快的 `std::vector::insert`

`unordered` 系列：用哈希表实现的 `map` 和 `set`

神奇的数据结构库：`pb_ds`：