比STL还STL?——平板电视
声明:本文为转载文章,转载自洛谷日报#39,原作者为Chanis。
__gnu_pbds食用教程
●QQ826755370
引入
某P党:“你们C++的STL库真恶心强大,好多数据结构和算法都不用手打。”
C党1:“STL能省下的代码量又不多,平衡树多难调啊。”
C党2:“欸?__gnu_pbds库就可以做到啊,它封装了hash,tree,trie,priority_queue这四种数据结构。”
正文
介绍
什么是__gnu_pbds?Policy based data structures!简称平板电视pbds。在使用pbds前,你需要:
1 |
|
woc,真jb烦,有没有什么简单的方法?当然有:
1 |
|
但是在dev c++里如果这样写,会提示少一个文件,出各种莫名奇妙的锅,其它的IDE请自行尝试,我的linux是deepin的,装了NOI Linux的dalao帮忙测一下。
hash
该引用的头文件和命名空间都讲过了,直接进入正题。
hash_table的用法与map类似,它是这么定义的:
1 | cc_hash_table<int,bool> h; |
其中cc开头为拉链法,gp开头为探测法,个人实测探测法稍微快一些。
啥?操作?其实就和map差不多,支持[ ]和find。
1 |
|
等一等?和map一样,那不如直接用map了。不不不,map的总时间复杂度是O(nlogn)O(nlogn)的,而hash_table的总时间复杂度仅为O(n)O(n)!所以我们可以用这个特性来做洛谷P1333 瑞瑞的木棍。前置知识:并查集 欧拉路。
感谢Great_Influence的代码:
1 |
|
tree
pbds里面的tree都是平衡树,其中有rb_tree,splay_tree,ov_tree(后两种都容易超时,所以请不要用它们)。需要的头文件与命名空间也讲了,下面我们来看它的食用方法:
1 |
|
下面我们来试一试洛谷P3369 普通平衡树(感谢shenben的代码):
1 | //by shenben |
前方高能!前方高能!前方高能!
在看这里之前,你需要熟练地掌握c++的特性。如果看不懂我也没有办法,你可以跳过这一部分。
你以为pbds种的tree只能实现这些功能?不不不,你可以自定义它,我们需要写一个自己的node_update,它是长这样的:
1 | template<class Node_CItr,class Node_Itr,class Cmp_Fn,class _Alloc> |
我们先解释一下这个类是如何工作的。节点更新的tree都会保存一个my_type类型的变量。当我们修改这棵树的时候,会从叶子节点开始修改,并且每次都会调用operator(),我们来看一下这个函数的两个参数:
Node_Itr it为调用该函数的元素的迭代器,Node_CItr end_it可以const到叶子节点的迭代器,Node_Itr有以下的操作:
get_l_child(),返回其左孩子的迭代器,没有则返回node_end;
get_r_child(),同get_l_child();
get_metadata(),返回其在树中维护的数据;
**it可以获取it的信息。
为了详细讲解,我们举一个更新子树大小的例子:
1 | void operator()(Node_Itr it, Node_CItr end_it) |
现在我们学会了更新,那么我们该如何自己写操作呢?node_update所有public方法都会在树中公开。如果我们在node_update中将它们声明为virtual,则可以访问基类中的所有virtual。所以,我们在类里添加以下内容:
1 | virtual Node_CItr node_begin() const=0; |
这样我们就能直接访问树了,还有,node_begin指向树根,node_end指向最后一个叶子节点的后一个地址,下面这个就是查排名的操作:
1 | int myrank(int x) |
下面我们来看CF459D:
1 |
|
trie
trie即为字典树,我们先看如何定义一个trie与它的操作:
1 | typedef trie<string,null_type,trie_string_access_traits<>,pat_trie_tag,trie_prefix_search_node_update> tr; |
现在我们来看Astronomical Database:
1 |
|
priority_queue
priority_queue为优先队列,用堆实现,priority_queue的定义与操作:
1 | priority_queue<int,greater<int>,TAG> Q;//小根堆,大根堆写less<int> |
时间复杂度:
堆优化dijkstra(感谢Great_Influence的代码):
1 |
|
关于rope
sorry,rope属于gnu_cxx,不属于gnu_pbds。下次讲ext中其他的内容时,我会讲rope。
最后
NOIP中可以使用pbds!
完结撒花!★,°:.☆( ̄▽ ̄)/$:.°★ 。
若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏