簡介Policy-Based Data Structures ( __gnu_pbds )


前言:

__gnu_pbds全名為GNU Policy-Based Data Structures,競賽中俗稱黑魔法,因為其內建了許多強大的工具,例如:可合併堆、伸展樹、紅黑樹、字典樹、hash table...,不過因為他放在一個很奇怪的標頭檔底下,且不是所有編譯器都支援(從名稱就知道那是GNU的東西),所以也沒那麼多人會使用他。

1. 使用方法

要使用其的資料結構時,請先引入ext/pb_ds/assoc_container.hpp,若要使用priority_queue時則還要多引入ext/pb_ds/priority_queue.hpp,而那些東東都包在__gnu_pbds這個namespace底下,所以如果懶的話,可以全部把他倒出來。
p.s不過如果std的也倒出來priority_queue會衝突到,此時建議還是要加個__gnu_pbds::在前面
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

2. priority_queue

可合併堆是我第一個知道的功能,那我們先看看他的type模板到底寫了甚麼吧
template<
    typename Value_Type,
    typename Cmp_Fn = std::less<Value_Type>,
    typename Tag = pairing_heap_tag,
    typename Allocator = std::allocator<char> >
class priority_queue;

這裡最常會動到的大概就是Value_Type跟Cmp_Fn了吧

  • Value_type 顯然是你的資料型別
  • Cmp_Fn 則是一個物件,其必須包含一個bool operator(),他會用來比較你的兩個資料,以知道誰該在你呼叫top時出現
  • 比較神奇的一個東東是Tag,預設為paring_heap_tag,也就是說他預設配對堆,不過他也支援其他種類的堆,以下列出其所有支援的堆的tag及其複雜度
    pushpopmodifyerasejoin
    pairing_heap_tagO(1)worst:Θ(n)
    amortized:Θ(log n)
    worst:Θ(n)
    amortized:Θ(log n)
    worst:Θ(n)
    amortized:Θ(log n)
    O(1)
    binary_heap_tagworst:Θ(n)
    amortized:O(log n)
    worst:Θ(n)
    amortized:Θ(log n)
    Θ(n)Θ(n)Θ(n)
    binomial_heap_tagΘ(log n)Θ(log n)Θ(log n)Θ(log n)Θ(log n)
    rc_binomial_heap_tagO(1)Θ(log n)Θ(log n)Θ(log n)Θ(log n)
    thin_heap_tagO(1)worst:Θ(n)
    amortized:Θ(log n)
    worst:Θ(log n)
    amortized:O(1)
    worst:Θ(n)
    amortized:Θ(log n)
    Θ(n)
  • Allocator則通常不會動到

基本上就看自己需求調參數囉,不過大多時間配對堆還是有在支援所有操作下最少的時間耗用,所以若沒有要特化某個功能,還是建議用預設的就好了。

而其可支援的操作包含了
  • pq.begin() 回傳他最前面的iterator (值得注意的是他的iterator是單向的那種)
  • pq.end() 回傳一個iterator指向一個空的節點
  • pq.empty() 回傳當前的pq是否為空
  • pq.clear() 把整個pq清乾淨
  • pq.size() 回傳當前pq的大小
  • pq.top() 回傳位於pq中的極值
  • pq.push(x) 把x放入priority_queue中,並回傳一個iterator指向那個元素
  • pq.pop() 把當前極值從pq中刪除
  • pq.modify(it,x) 把it指到的元素改成x
  • pq.join(qp) 把qp中的元素都搬到當前這個pq,並清空qp
  • pq.erase(it) 把it指到的元素從pq中移除
剩下詳細的功能可以參見其官方文件

3. tree

同樣,先來看看模板吧XD
template<
    typename Key,
    typename Mapped,
    typename Cmp_Fn = std::less<Key>,
    typename Tag = rb_tree_tag,
    template<
        typename Const_Node_Iterator,
        typename Node_Iterator,
        typename Cmp_Fn_,
        typename Allocator_>
    class Node_Update = null_tree_node_update,
    typename Allocator = std::allocator<char> >
class tree;

他的基本用法跟Map一樣(Map底層也是紅黑樹)

  • Key 就是你鍵值的type,如果less不知原你的type的話,你還要自己寫個Cmp_Fn (跟map一樣)
  • Mapped 就是你要存的資料的型別,如果設為null_type的話你的樹會變成跟set一樣,iterator也會從pair退化回Key,不過速度會有小幅的成長
  • Cmp_Fn 他吃一個class,跟stl::map吃的cmp_fn一樣
  • Tag 也是算有點神奇,只接受rb_tree_tag, ov_tree_tag, splay_tree_tag,不過大多時間用起來還是預設的紅黑樹最快
  • Node_Update是這裡面比較重要的一個,預設是null_tree_update。不過在引入tree_policy.hpp的前提下,當你改成tree_order_statistics_node_update後他會突然出現兩個可以使用的函數: find_by_order跟order_of_key前者可以讓你找到第k小(大)的資料是誰,後者可以讓你知道有多少資料的鍵值小(大)於k,不過更神奇的是他其實是可以自訂的!!
這邊稍微介紹一下該怎麼自訂Node_Update,底下再貼一下tree支援的操作
template < class Node_CItr , class Node_Itr ,
    class Cmp_Fn , class _Alloc  >
struct my_node_update {
    virtual Node_CItr node_begin () const = 0;
    virtual Node_CItr node_end () const = 0;
    typedef int metadata_type;
};
上面那串根據《C++的pb_ds库在OI中的应用》來看似乎是一定要的(當然struct名可以自訂),不過我自己是覺得metadata_type應該是可以自己任意設的(當然int可以改long long是沒差的)

...未完待續

參考資料

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology