使用方法
引入头文件，有万能头用：
1
#include <bits/extc++.h>pb_ds的容器和算法定义在另外两个命名空间中，而非std：
1
2
using namespace __gnu_cxx;
using namespace __gnu_pbds;哈希表
pb_ds中有两种哈希表：
1
2
__gnu_pbds::gp_hash_table <T1, T2> h1;
__gnu_pbds::cc_hash_table <T1, T2> h2;前者为探察法解决哈希冲突，速度更快，一般使用第一个
后者为拉链法解决哈希冲突，速度更慢，比umap还慢
pb_ds中的哈希表很快，比map和umap还要快，且更难被hack
支持pair
一般的哈希表不能以pair作为key值，我们需要显式的template重载一下hash
1
2
3
4
5
6
7
template <class T1, class T2>
struct std::tr1::hash <std::pair <T1, T2> > {
size_t operator() (std::pair <T1, T2> x) const {
std::tr1::hash <T1> H1; std::tr1::hash <T2> H2;
return H1(x.first) ^ H2(x.second); // 自定义的 hash 函数
}
};平衡树
哈希表的定义如下：
1
2
3
__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：储存的元素类型，如果要存储多个相同的Key元素，则需要使用类似于pair和struct方法，并配合使用lower_bound和upper_bound成员函数查找
- Mapped：映射规则类型，若指示关联容器是集合，类似set，则填入
null_type，若是带值的集合，类似于map，则填入类似std::map<Key, Value>的值类型 - Cmp_Fn：关键字比较函子，如
std::less<Key> - Tag：选择使用何种底层数据类型，默认是
rb_tree_tag，库里提供了三种不同平衡树：rb_tree_tag：红黑树，一般用这个splay_tree_tag：splay树ov_tree_tag：有序向量树
- Node_Update：更新节点策略，默认使用
null_node_update，如果想使用order_of_key和find_by_order方法，需要使用tree_order_statistics_node_update Allocator：空间分配器类型
构造方式
1
2
3
4
__gnu_pbds::tree<std::pair<int, int>, __gnu_pbds::null_type,
std::less<std::pair<int, int>>, __gnu_pbds::rb_tree_tag,
__gnu_pbds::tree_order_statistics_node_update>
tr;成员函数
insert(x)：树中插入一个元素erase(x)：从树中删除一个元素/迭代器，若x是迭代器，则返回指向下一个的迭代器；如果x是key，则返回是否删除成功order_of_key(x)：返回严格小于x的元素个数，即从0开始的排名lower_bound(x)：返回第一个不小于x的元素所对应的迭代器upper_bound(x)：返回第一个严格大于x的元素所对应的迭代器join(x)：将x树并入当前数，x树清空（保证比较函数和元素类型相同）split(x,b)：以Cmp_Fn比较，小于等于x的属于当前树，其余的属于b树empty()：返回是否为空size()：返回大小