//标题很高级吧?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?

分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注