gcc (g++) の policy-based data structure の中にある tree (の競技プログラミングでの利用) に関する記事です．

リンク

まとめ

以下の操作ができる set や map

  • x を指定して，x より小さい要素がいくつあるか数える
  • n を指定して，n 番目に小さい要素へのイテレータを取得する

先頭部分

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

型の定義

例: pair<int, int> の集合

注意: multiset ではない．multiset は PBDS にはない．multiset を使いたいときには pair の set で第2要素でユニークにすることを検討．

using elem_tp = pair<int, int>;   // ここを，要素の型にする
using pbds_set = tree<
  elem_tp,
  null_type,
  less<elem_tp>,
  rb_tree_tag,
  tree_order_statistics_node_update
  >;

例: string から int へのマップ

using key_tp = string;           // ここを，キーの型にする
using val_tp = int;              // ここを，値の型にする
using pbds_map = tree<
  key_tp,
  val_tp,
  less<key_tp>,
  rb_tree_tag,
  tree_order_statistics_node_update
>;

注意: key_t は <sys/types.h> で使われていて衝突する．

機能の呼び出し

  ordered_set os;
  os.insert(pair_t(0,0));
  os.insert(pair_t(1,0));
  os.insert(pair_t(1,1));
  os.insert(pair_t(2,0));
  os.insert(pair_t(2,1));

// order_of_key: 指定した値よりも小さい要素の数
  assert(os.order_of_key(pair_t(-1,0)) == 0);
  assert(os.order_of_key(pair_t(0,0)) == 0);
  assert(os.order_of_key(pair_t(0,1)) == 1);
  assert(os.order_of_key(pair_t(1,0)) == 1);
  assert(os.order_of_key(pair_t(1,1)) == 2);
  assert(os.order_of_key(pair_t(100,0)) == 5);

// find_by_order: 指定した位置の要素へのイテレータ
  assert(*os.find_by_order(0) == pair_t(0,0));
  assert(*os.find_by_order(2) == pair_t(1,1));
  assert(*os.find_by_order(4) == pair_t(2,1));
  assert(os.find_by_order(5) == os.end());

注意

  • 必ずしも速くないらしい．Fenwick tree や segment tree の倍くらい遅いというレポートがある
  • multiset や multimap に相当する機能はない (リンク )