平板电视与可动态更新的堆

家电下乡高价回收,笔记本、电脑、洗衣机……

嗯……不是那个平板电视。

平板电视介绍

Policy-Based Data Structures,简称平板电视,是C++ STD库函数的一套数据结构的总称。平板电视的功能强大,囊括了以下丰富内容:

  • 基于树规则的数据结构,包括了比STL跑的快到不知道哪里去的红黑树、根本手写不了的斐波那契堆、以及SPLAY TREE 
  • 基于字典树规则的数据结构(主要是Trie树)
  • 基于链表规则的数据结构(没有了解过)
  • 基于Hash规则的数据结构(Hashtable)
  • 还有本篇的重点:支持动态修改的堆(优先队列)

平板电视的使用主要是各种牛逼的树和优先队列。使用平板电视需要注意环境:在程序中引入头文件<bits/extc++.h>,如果编译通过就可以使用平板电视。

  • ACM/ICPC全部支持(理论上)
  • 做不出的OJ题(注意POJ全不支持)
  • 自己写程序爱用就用

我喜欢的是平板电视里的堆

使用平板电视的堆需要注意:PBDS的模板名与STD的完全一致,所以不能同时使用using namespace std; using namespace __gnu_pbds;,只能用一个或者最安全就是不要用整个namespace。

优先队列的模板

优先队列的模板如下:

template<
    typename Value_Type,
    typename Cmp_Fn = std::less<Value_Type>,
    typename Tag = pairing_heap_tag,
    typename Allocator = std::allocator<char> >
class priority_queue;

此处的四个参数分别是:数据类型、比较函数、堆种类和内存分配器。堆的种类共有5种:pairing_heap_tag, binary_heap_tag, binomial_heap_tag, rc_binomial_heap_tag, or thin_heap_tag

优先队列的使用

对于默认的堆,只需要用__gnu_pbds::priority_queue<int> pq;就可以声明了。默认和STD一样是大根堆,有pushtoppopclearemptybeginend等方法,可以和STD的优先队列一样使用。

不同的是,平板电视的优先队列的push方法会返回一个指针迭代器__gnu_pbds::priority_queue< TypeName >::point_iterator。这个指针迭代器会一直指着插入的数据,可以随时访问值,但注意不能直接修改它。

如果要修改某个值,可以调用modify方法,这个方法接受两个参数,第一个参数是指针迭代器,第二个是要更新的值(变大变小都可以)。

参考代码:

// A priority queue of integers.
priority_queue<int> p;

// Insert some values into the priority queue.
priority_queue<int>::point_iterator it = p.push(0);

p.push(1);
p.push(2);

// Now modify a value.
p.modify(it, 3);

assert(p.top() == 3);

可以将位于堆底的0修改成3,并且这个值在修改后冒到堆顶,并且指向它的迭代器也跟着过来了。

需要注意的是,如果指针迭代器对应的值已经被弹出堆,这个时候访问指针迭代器就会造成segment fault。

使用样例

由于GCC的页面出bug了,暂时没法阅读examples文件。链接:https://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/pq_examples.html

跑得非常快

在某道卡时间(其实根本不卡)的题目中使用cin cout读入、输出数据,平板电视优先队列来实现Dijkstra算法,全部跑完只用了572ms,根本没有被卡时间,跑的快的不得了!

(然后由于一些傻逼错误导致WA27%,找了四个多小时都没出错在哪,后来跟别人拍来拍去才知道自己题意没理解对……)