# pbds 学习记录
pbds库提供了一些常用的数据结构，常数上通常比对应的常用 stl 更快，所以值得整理一下。
## 堆
为了使用 pbds 的堆，我们要使用如下头文件
```cpp #include <ext/pb_ds/priority_queue.hpp> ```
声明如下
```cpp __gnu_pbds :: priority_queue<T, Compare, Tag, Allocator>;
T: 元素类型
Compare: 比较类型，即less(T) / greater(T). 默认大根堆
Tag: __gnu_pbds 共提供了五种堆，默认为 pairing_heap_tag，五种分别为：
    pairing_heap_Tag 配对堆，官方文档认为在非原生元素中表现最好
    binary_heap_tag 二叉堆，官方文档认为在原生元素中表现最好，合并时间复杂度高
    binomail_heap_tag 二项堆
    rc_binomial_heap_tag 冗杂计数二项堆
    thin_heap_tag 查不到中文名，有说是经过改良的斐波那契堆，合并的时间复杂度较高
    以我目前的理解来看，在ACM 竞赛中能用到的只有第一种
    Allocator: 空间配置器，ACM 中大概用不到 */ ```
成员函数跟 std 中基本没有差别，大多数时候可以无缝衔接
    push(T) 插入新节点
    pop() 删除顶端节点
    top() 返回顶端节点的值
    size() 返回堆的大小
    empty() 返回堆是否为空
    motify(point_iterator, key) 将迭代器指向的节点的值改为 key，并维护堆
    erase(point_iterator) 删除迭代器指向的节点，并维护堆
    join(__gnu_pbds :: priority_queue<T> &other) 将 other 合并到 *this 中，并清空 other
在洛谷的 dijkstra 模板题中，我分别使用 stl 和 pbds 的堆提交了一遍，结果如下：
可以看到，在不开 o2 时，pbds 提升很大，而开了 o2 之后 pbds 的效率反而不如 stl。因为现在大部分比赛都默认开 o2，所以我认为在不需要实现堆的合并时没必要使用 pbds 的堆
## hash
hash 的功能和 map 类似，同样支持 find() 和使用 [] 索引，速度比 map 更快，但是不能 upperbound。
所需的头文件及声明方法
```cpp #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp>
__gnu_pbds :: gp_hash_table<T, T1> h1; // 探测法，网上都说这个更快，我的测试结果在下面 __gnu_pbds :: cc_hash_table<T, T1> h2; // 拉链法 ```
除了不支持upperbound，即不会将元素排为有序以外其他地方都和 std :: map 一样，至少 ACM 中可以这么认为。
以一道可以用 map 解决的题目 (luogu P1381) 为例，简单对比一下 map 和 pbds 的差距。
下面这个是gp_hash_table
顺便应直播间要求测试了 unordered_map
## 平衡树
`__gnu_pbds :: tree` 可以实现红黑树和 splay 树等常见平衡树，所以也可以作为 map 和 set 的替代。
头文件和声明方法如下
```cpp #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp>
__gnu_pbds :: tree<Key, Mapped, Cmp_fn = std::less<Key>, Tag = rb_tree_tag, Node_Update = null_tree_node_update, Allocator = std::allocator<char>> /* Key: 储存的元素类型。tree 会自动去重，如果一定要存入重复的数据，可以考虑利用 std::pair 或者 struct
Mapped: 映射规则类型。如果想要实现 set，则填入 null_mapped_type；如果想要实现 map，则填入类似于`std::map<Key, Value>` 的 Value 类型
Cmp_Fn: 关键词比较规则
Tag: 可选共三种：
    rb_tree_tag: 红黑树。Tag 的默认值也是这个，性能也比后两个好
    splay_tree_tag: splay 树         ov_tree_tag: 有序向量树，只是一个由 vector 实现的有序结构，类似于排序的 vector 来实现平衡树，容易被卡
Node_Update: 用于更新节点的策略，默认使用 null_node_update，若要使用 order_of_key 和 find_by_order，则需要改成 tree_order_statistics_node_update
Allocator: 空间分配器类型 */ ```
成员函数如下
insert(Key) erase(Key) lowerbound(Key) upperbound(Key) empty() size() 与常见的用法一致，略
order_of_key(Key) 返回 x 的排名
find——by_order(size_t) 返回排名为 x 的值
join(__gnu_pbds :: tree) 将树合并进 *this 并删除
split(x, b) 将小于等于 x 的元素移入 *this，其余留在 b
## 锐评环节
经过如上体验，堆在开 o2 的情况下不但没有优势，反而会增加时间，不过支持合并；hash 使用方便，甚至比 unorder_map 还要快，但是我在上网冲浪时看到有人讨论说 hash 的哈希函数极其简单，很容易被针对；tree功能强大，并且短小精悍，手写 splay 和使用函数，我相信大部分人都会选择后者，但是跟 map 和 set相比还是更麻烦了点。综上所述，pbds 在时间优化方面并不是极其突出，但是灵活使用可以显著缩短代码长度。在出题人比较邪恶或者存在被 hack 的可能性时要注意谨慎使用。
## 参考资料
[oiwiki_pbds](https://oi-wiki.org/lang/pb-ds/)
[知乎回答_在 OI/ACM 中有哪些 STL 的技巧？ by 秋扇](https://www.zhihu.com/question/64151566/answer/2193178371) 就是因为看了这篇回答我才决定学习 pbds
[PBDS学习笔记(一) by Q1143316492](https://www.cnblogs.com/Q1143316492/p/9536364.html)
[官方文档_堆的复杂度](https://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/pq_performance_tests.html#std_mod1)
[官方文档——平衡树](https://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/tree_based_containers.html)