//标题很高级吧?233333
很好的一个相关pdf(建议右键另存为,不然打开慢的死(或者开蓝灯= ̄ω ̄=)):点击下载

1. 哈希表

需要:

可能还需要(我试过不需要,但pdf上说需要):

使用命名空间:

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

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

访问对应元素,如访问元素1对应的值:

反正和map一模一样

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

2. 树

头文件:

使用命名空间:

例子:建立一棵红黑树

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

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

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

这个代码返回的是树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?