//标题很高级吧？233333
很好的一个相关 pdf（建议右键另存为，不然打开慢的死（或者开蓝灯＝￣ω￣＝））：点击下载

1. 哈希表

需要：

#include <ext/pb_ds/assoc_container.hpp>

可能还需要（我试过不需要，但 pdf 上说需要）：

#include <ext/pb_ds/hash_policy.hpp>

使用命名空间：

using namespace __gnu_pbds;

哈希表的复杂度：$O(1)$
最坏会退化成：$O(n)$

1. cc_hash_table
   使用链地址法解决哈希冲突。
   用法：和 map 一模一样。
   比如：

cc_hash_table<int,int> h;

访问对应元素，如访问元素 1 对应的值：

h[1];

反正和 map 一模一样

1. gp_hash_table
   使用探测法解决哈希冲突。
   用法：和 cc_hash_table 一样，不做过多赘述。

2. 树

头文件：

#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

使用命名空间：

using namespace __gnu_pbds;

例子：建立一棵红黑树

tree<int,int,less<int>,rb_tree_tag,tree_order_statistics_node_update>

其中，第一个参数是键值类型 (key)，第二个是数据类型 (data)，第三个是比较函数（伪函数），第四个表示树的类型，如：

splay_tree_tag;
rb_tree_tag;

如果你想用 splay，就把第四个参数改成：splay_tree_tag
至于第五个参数，应该是定义树的更新方式，不是很明白，反正写这个就行了：

tree_order_statistics_node_update

使用方法都和 map 一样，insert 啊 erase 啊都有。
多了一些功能，如寻第 k 小数查询：

tree.find_by_order(k-1)；

这个代码返回的是树 tree 中的第 k 大数的迭代器，是个 pair 的迭代器（除非你定义 tree 的第二个参数为 null_type）。

为什么是 $k−1$而不是 $k$呢？原因在于这个函数其实返回的是树上有 $k-1$个节点比他小的那个节点的迭代器，所以我们要找第 $k$大，那么就有 $k−1$个节点比他小，所以是 $k−1$。

//另外几种见 pdf 吧＝￣ω￣＝我就不讲了

忘了 pb_ds 头文件/变量名/等等… 的解决方法

其实很简单——找到库文件，到文件中去搜关键字不就行了吗=￣ω￣=。
linux 底下，pb_ds 库在这个路径下：
/usr/include/c++/5.4.0/ext/pb_ds
在文件管理器中按 CTRL+L 可以输入路径，按 ESC 可以关闭输入路径。
windows 下的我不讲——谁让你不用 Linux？