pb_ds 是 GNU-C++ 自带的一个 C++ 的扩展库，其中实现了很多数据结构，比 STL 里面的功能更强大。

哈希表

需要的头文件:

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace __gnu_pbds;123

两种定义哈希表的方式：

cc_hash_table<string,int>mp1;//拉链法
gp_hash_table<string,int>mp2;//查探法(快一些)12

说明：

在不允许使用 C++11 的时候，pb_ds 库中的两种 hash 函数比 map 的效率大大提高，可以代替 map 作为一个哈希工具，使用方法和 map 完全一样，一般来说查探法的效率更高。

堆

需要的头文件：#include<ext/pb_ds/priority_queue.hpp>

用法和普通的优先队列一样。

#include<ext/pb_ds/priority_queue.hpp>
using namespace __gnu_pbds;
__gnu_pbds::priority_queue<int>q;//因为放置和std重复，故需要带上命名空间
__gnu_pbds::priority_queue<int,greater<int>,pairing_heap_tag> pq;//最快
__gnu_pbds::priority_queue<int,greater<int>,binary_heap_tag> pq;
__gnu_pbds::priority_queue<int,greater<int>,binomial_heap_tag> pq;
__gnu_pbds::priority_queue<int,greater<int>,rc_binomial_heap_tag> pq;
__gnu_pbds::priority_queue<int,greater<int>,thin_heap_tag> pq;
__gnu_pbds::priority_queue<int,greater<int> > pq;123456789
pb_ds`库的堆提供了五种tag，分别是`binary_heap_tag`，`binomal_heap_tag`，`pairing_heap_tag`，`thin_heap_tag`，`rc_binomal_heap_tag` 。 因为重名的原因一定要加上 `__gnu_pbds::

常用操作：

push()  //会返回一个迭代器
top()  //同 stl 
size()  //同 stl 
empty() //同 stl 
clear()  //同 stl 
pop()  //同 stl 
join(priority_queue &other)  //合并两个堆,other会被清空
split(Pred prd,priority_queue &other)  //分离出两个堆
modify(point_iterator it,const key)  //修改一个节点的值123456789

优先队列的迭代器：

__gnu_pbds::priority_queue<int>::point_iterator it;  1

红黑树

所需头文件：

#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;123

定义一棵红黑树：

tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> t;
/*
定义一颗红黑树
int 关键字类型
null_type无映射(低版本g++为null_mapped_type)
less<int>从小到大排序
rb_tree_tag 红黑树（splay_tree_tag）
tree_order_statistics_node_update结点更新
插入t.insert();
删除t.erase();
求k在树中是第几大:t.order_of_key();
求树中的第k大:t.find_by_order();
前驱:t.lower_bound();
后继t.upper_bound();
a.join(b)b并入a 前提是两棵树的key的取值范围不相交
a.split(v,b)key小于等于v的元素属于a，其余的属于b
T.lower_bound(x)   >=x的min的迭代器
T.upper_bound((x)  >x的min的迭代器
T.find_by_order(k) 有k个数比它小的数
*/

第一个参数代表 key的类型
第二个参数表示 value 的类型。这里不需要映射值，也就填 null_type 。
第三个参数表示 key 的排序方式，从小到大。
第四个参数表示使用哪种数据结构，rb_tree_tag 表示红黑树。
第五个参数表示如何更新保存节点信息，填写 tree_order_statistics_node_update 会额外获得 order_of_key() 和 find_by_order() 两个功能。

tree 也使用和 set 类似的迭代器，定义为

tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>::iterator it;1

要保证迭代器类型要和定义的树的类型相同。但是为了方便，在条件允许的情况下，可以用 auto 来自动推断类型。如：

auto it = t.begin();1

当然这个迭代器支持 ++ 和 –- 操作。
功能简介

1、tree 包含 set 的全部功能，如 lower_bound, upper_bound, insert, erase, find, begin, end, rbegin 等。
2、查询第 \(k+1\) 小的数，使用 find_by_order() 函数，返回的为迭代器。

cout << *t.find_by_order(2) << endl;

此时输出的为排名为 \(3\) 的数，注意，查询的是为第 \(k+1\) 小的数。如果传入的 \(k\) 值非法，则会返回 end()。
3、查询比 \(x\) 小的数的个数，注意，是比 \(x\) 小的个数，不是 \(x\) 的排名！查询的出的值是排名 \(-1\)。

cout << t1.order_of_key(2) << endl;1

4、合并两个类型相同的 tree，t1.join(t2)。t2 的内容会全部加入到 t1，t2 被清空。要保证 t1 的值全部小于 t2 或者全部大于 t2，否则会抛出异常。
5、不支持多重值，如果需要多重值，可以再开一个 unordered_map 来记录值出现的次数。将 x<<32 后加上出现的次数后插入 tree。注意此时应该为 long long 类型。

auto it=t.begin();it--;//此时的it==t.end();t.end()不是最后一位，是最后一位的下一位1

参考资料

• pb_ds库的一些常用方法 - riba2534的博客

pb_ds 库简介

原文：https://www.cnblogs.com/Sam2007/p/14339264.html