如何优雅地使用 pb_ds

定义头文件

总所周知，dev 年久失修，对这种高端科技并不是很支持，直接背头文件又长又臭。

但如果使用的其他高端编辑器，你可以直接写：

#include<bits/extc++.h>

使用dev的话你也需要先写这个，然后编译会出错。

大概是

点击下面编译错误的加粗的第一行，然后你就进入到

将第 60-66 行复制到你的 cpp 中即可(也就是复制后缀为.hpp)。

这七行代码分别的意思是：

第 60 行是类似于迭代器之类的东西，在你使用 hash,list,tree,trie 时必须带上，否则可能出现神秘错误，priority_queue不需要带上。

第 61 行是priority_queue的专用头文件。

第 62 行是调试差错的工具，能有效的帮你找到的你使用的 pb_ds 在哪个调用哪个函数的时候出锅了，非常良心，建议带上。

第 63 行是 hash 的专用头文件，第 64 行是 list 的专用头文件，第65行是 tree 的专用头文件，第66行是 trie的专用头文件。

如果你想我一样懒的话其实也都不用管，直接无脑复制所有即可。

由于 pb_ds 是封装在一个 namespace 里面的，所以为了方便，加上：

using namespace __gnu_pbds;

所以我的头文件板子为：

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/exception.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/list_update_policy.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/trie_policy.hpp>
using namespace __gnu_pbds;

你只需要背诵 pb_ds 万能头即可。

tree

主要用于替代手写的简单平衡树。

定义变量：

tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>T;

定义一共需要 5 个参数，第一个是你插入进去的数的类型，第二个是一个必要参数，只有死记，第三个是你的比较函数，可以将 less 内部的 int 改为你自己定义的 cmp 函数，第四个是 tag，pbds内部实现了3种tag，分别为 rb_tree_tag，splay_tree_tag，ov_tree_tag，其中第二种 tag 速度较慢，第三种 tag 功能不全，所以建议无脑选 rb_tree_tag 即可，最后那个也是无脑背即可，背不下来咋办？。

按住 ctrl 点击

#include <ext/pb_ds/tree_policy.hpp>

翻到第 146 行复制即可。

功能包括：set 全家桶，以及 order_of_key,find_by_order,join,spilt 函数。

T.order_of_key(x)：查询任意一个数 \(x\) 的排名，返回值为小于这个数的总个数，所以算排名的时候值要加一。

T.find_of_key(x)：查询排名为 \(x\) 的数，由于内部实现是排名是从 \(0\) 开始的，所以查询的时候要减一。

T.join(a)：将 \(a\) 这颗树合并到 \(T\) 中，并将 \(a\) 清空，使用这个函数有个大前提，需要满足一棵树的最小值大于另一颗数的最大值，若不满足此前提只有启发式合并来做，速度略慢。

T.spilt(x,a) ：将 \(T\) 分裂成两颗树，小于等于 \(x\) 的属于 \(T\)，大于 \(x\) 的属于 \(a\)

tree 会自动去重，即相同的数只保留一个，所以要保留多个相同数的时候，建议写结构体或者用 double 扰动（笔者认为前者更优）

priority_queue

主要用于替代可并堆，复杂度比启发式合并优秀。

定于变量：由于 c++ 中有常规的 priority_queue，所以直接定义会重名。

#define heap __gnu_pbds::priority_queue
heap<int>q;

pbds也实现了很多功能，默认的tag为配对堆，在复杂度以及功能完整性上都十分优秀，建议不用更改tag

主要功能包括：常规priority_queue全套，以及 erase,modify,join 函数

q.erase(t) ：删除迭代器 \(t\) 位置的值。

q.modify(t,x)：将迭代器 \(t\) 的值更改为 \(x\)

q.jion(a)：将堆 \(a\) 合并到 \(q\) 中，并将 \(q\) 清空。

hash_table

主要替代 unordered_map，在对卡常中有所作用。

定于变量：

cc_hash_table<int,int>mp;
gp_hash_table<int,int>mp;

一共就这两种tag，网上对这俩的速度谁快一直争论不休。

个人认为 cc 快一下

功能同 unordered_map 一样