pbds 学习记录

# 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)