STL 奇技淫巧食用指南

2018-08-06 22:31:02


STL 只会用 std::stringstd::sortstd::queuestd::stackstd::setstd::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$ ! $+ 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】【模板】普通平衡树 - 洛谷

#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 系列:用哈希表实现的 mapset

std::mapstd::set 固然好,但是 $O\left(\log n \right)$ 的复杂度有些时候着实不太方便,如果你不需要自动排序,用哈希表实现的 std::unordered_mapstd::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::mapstd::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_multimapstd::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> 头文件中,模板参数如下:

  1. 数据类型,不解释。
  2. 比较器,默认为 std::less,从大到小,如果需要从小到大需要传入 std:greater
  3. 堆类型,提供 __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 相同,但是多了一些操作:

  1. 遍历,该优先队列提供 point_iterator 类型(push 操作会返回)和 beginend 迭代器,所以可以像这样遍历:
    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,需要这么写:

#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::mapstd::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,更不要当「手写原教旨主义者」。