【C++】g++のポリシーベースデータ構造とは？特徴と使い方を解説

g++コンパイラは、Linux環境で広く利用されているGNUプロジェクトのC++コンパイラです。

g++には、C++標準ライブラリには存在しない特殊なデータ構造のサポートが追加されています。これらは「ポリシーベースデータ構造」と呼ばれ、競技プログラミングや高効率なアルゴリズム実装の場面で特に重宝します。

ポリシーベースデータ構造は、C++標準ライブラリ（std）が提供する標準的なデータ構造と比べて、より高いパフォーマンス・意味的な安全性・柔軟性を実現できる点が大きな特徴です。

ヘッダファイルの読み込み

これらのデータ構造をプログラムで利用するには、冒頭で次の記述を追加します。

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

サンプルコード

ここでは、代表的な例として「順序統計木」を使ったプログラムを見てみましょう。

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>
#include <iostream>
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> new_data_set;

int main() {
    new_data_set data;
    data.insert(34);
    data.insert(785);
    data.insert(12);
    data.insert(87);

    cout << "The value at index 2 is " << *data.find_by_order(2) << endl;
    cout << "The index of number 87 is " << data.order_of_key(87) << endl;

    return 0;
}

実行結果

The value at index 2 is 87
The index of number 87 is 2

挿入された値 {12, 34, 87, 785} は自動的に昇順にソートされて管理されます。そのため、インデックス2（0始まり）の要素は3番目に小さい「87」となり、「87」より小さい要素は「12」「34」の2つであるため、order_of_key(87) の結果は2になります。

コードの解説

tree構造のテンプレート引数は、それぞれ次のような役割を持っています。

• int：格納するキーの型
• null_type：マッピングする値の型。null_type を指定すると集合（set）として動作します
• less<int>：順序付けポリシー。ここでは昇順ソートを指定しています
• rb_tree_tag：内部で赤黒木（平衡二分探索木）を使用することを示すタグ
• tree_order_statistics_node_update：ノード更新ポリシー。順序統計機能（find_by_order / order_of_key）を有効にします

主なメンバ関数

• find_by_order(k)：k番目（0始まり）に小さい要素へのイテレータを返します
• order_of_key(x)：x より厳密に小さい要素の個数を返します

このように、ポリシーベースデータ構造を活用すると、「指定したインデックスの要素を取得する」「ある要素の順位を調べる」といった操作を O(log N) で高速に行えます。std::set では実現できない柔軟な検索処理が可能になるのが魅力です。

その他のポリシーベースデータ構造

tree 以外にも、ハッシュテーブル（cc_hash_table / gp_hash_table）やトライ木（trie）など、さまざまなデータ構造が用意されています。用途に応じて適切な構造を選択することで、標準ライブラリだけでは実現しにくい高速な処理を簡潔に記述できます。