Policy Based Data Structures
この記事はCompetitive Programming (2) Advent Calendar 2018およびISer Advent Calendar 2018 1日目の記事です。
CodeForcesやTopCoderで海外勢がよくヘッダーに
#include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp>
とかをインクルードしていますが、これのことです。日本語の記事が見当たらなかったので書くか〜と思いましたが、書き始めると普通に見つかってしまいました。
ということでもうちょっと詳しく書くことにします。
Policy Based Data Structures (PBDS)
何ができるか
- k番目の値を高速に取り出せるデータ構造があります
- std::unordered_mapより4倍近く速いhash tableが使えます
- Tagによってpush, modify, erase, joinなどがO(logn)やO(1)でできるpriority_queueが使えます
- trie木が使えます
すごく拡張性のあるデータ構造ですが、標準の機能をそのまま使って得られるオイシイ機能はこのぐらいです（もちろん自作クラスと組合せたりするとこの限りではありません）。実装削減や、いざというときの高速化に役立つかもしれません。
使い方
ここを見ればだいたいのパターンの実装が書かれていますが、GNUのpbdsではないのでコンパイラがGNU G++の場合はnamespaceのところを using namespace __gnu_pbds; に書き換えてあげてから実行してあげてください。
以下ではこれらのメインの機能を軽く紹介します。
tree
std::setの上位互換です。
tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> s;
で宣言できます。tb_tree_tagは内部構造に赤黒木を指定しており、たとえばsplay木を使いたいときは代わりにsplay_tree_tagを指定すればいいです。
insert, erase
setと同じでinsert, erase関数です
k番目の値を取得
find_by_order(k)でk番目の要素のイテレータが返ります
kが何番目か
order_of_key(k)でk以上で最小の数が何番目か、つまりk未満の数が何個あるかわかります。実質lower_boundですね
コードです。 Submission #3643481 - AtCoder Regular Contest 033
hash table
std::unordered_mapは実装の制約上非効率な実装になっているようで*、速度が要求される場合にはgp_hash_tableが良いようです。
gp_hash_table<int, int> m;
で宣言できます。templateの第三引数にHash関数を指定できるので通常のunordered_mapと同様なHack対策が可能です。
使い方はunordered_mapとほぼほぼ同じなので省略します。
priority_queue
std::priority_queueは、内部のヒープにpairing heapを使用しているようですが*、pbdsではいくつかのヒープをタグとして指定できます。各操作の計算量は以下のような感じです。
pairing heapが案外優秀なので基本的にstd::priority_queueでいいような気がしますが、要素のmodifyとかをしたいときはpbdsが活きますね。
Thin Heapでダイクストラを書いてみましたが、std::priority_queueのほうが速かったです、、 Aizu Online Judge
trie
通常のtrieと同様、文字列の挿入、prefixによる検索ができます。実装にパトリシア木を指定することで愚直なtrie木よりも高速な検索が可能です。
trie<string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update> t;
で宣言できます。以下、コード例（#使い方 の部分に貼った実装の中の一例）です。
これも結構便利だとは思うんですが、trie木を使って即終了！ｗみたいな問題はまずないと思いますし、Aho-Corasick等に応用するなら自作クラスや自作policyと組み合わせる必要がありそうです。
性能比較
本家のドキュメンテーションに詳細に記載されています。treeは基本的に赤黒木を指定すれば速いです。
参考文献
C++ STL: Policy based data structures - Codeforces
C++ STL: Order of magnitude faster hash tables with Policy Based Data Structures - Codeforces
Chapter 22. Policy-Based Data Structures
網羅的に読みたい人は３つ目、もう少し細かい機能をざっと確認したい方は４つ目、５つ目の記事をおすすめします。
まとめ
tree, gp_hash_tableは使えそう！それ以外は微妙かなあ、、？
