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

发表评论

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

你是机器人吗? =。= *