pbds 学习笔记

作者：kanate，发表于 Fri Sep 05 2025。

$\text{namespace}$ 是 __gnu_pbds，头文件可以直接 #include<bits/extc++.h> ，不过 devcpp 用不了，只能 #include<ext/pb_ds/assoc_container.hpp> 以及对应的头文件，迭代器都是 $\text{point_iterator}$。

哈希表

根据别人以及自己的 $\text{benchmark}$ 来说 $\text{hash_table}$ 表现很优秀，非构造数据卡点常还是要写的。

1. 头文件： #include<ext/pb_ds/hash_policy.h>
2. 声明：gp_hash_table<int,int>，当 $\text{unordered_set}$ 用的话是 gp_hash_table<int,nulltype>
3. 使用：同 $\text{unordered_map}$ ，直接遍历也是 $O(n)$ 乱序的。

堆

用配对堆，支持 $O(1)\ \text{push join}$，$O(\log)\ \text{erase modify}$ 。

1. 头文件： #include<ext/pb_ds/priority_queue.h>
2. 声明：__gnu_pbds::priority_queue<int,greater<int>,pairing_heap_tag>
3. 使用：$\text{push}$ 会返回迭代器，$\text{join}$ 为 $\text{a.join(b)}$ 且清空 $\text b$ ，$\text{erase}$ 为 $\text{q.erase(it)}$，$\text{modify}$ 为 $\text{q.modify(it,x)}$ ，当 $\text{it}$ 为 $\text{NULL}$ 时就不在堆中，自定义比较同标准库要用 $\text{struct}$ 。

平衡树

用红黑树，相比 $\text{set}$ 支持 $\text{kth rank join split}$ ，和 $\text{fhq_treap}$ 的常数差不多，常数较大。

1. 头文件： #include<ext/pb_ds/tree_policy.h>
2. 声明：tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
3. 使用：同 $\text{set}$ ，实现 $\text{multiset}$ 要用 $\text{pair}$ 通过第二关键字区分，下标从 $0$ 开始，$\text{kth}$ 是 $\text{*t.find_by_order(k-1)}$ ，求排名是 $\text{t.order_of_key(x)+1}$ ，合并是 $\text{a.join(b)}$ 且清空 $\text b$ ，要保证两树值域不交，分裂是 $\text{a.split(x,b)}$ 把 $\text b$ 清空再把 $>x$ 的元素分给 $\text b$ 。

reference：pbds库学习笔记 - 知乎