C++の順序集合（ordered set）とは？GNU C++ PBDSの使い方を解説

本記事では、順序集合（ordered set）と GNU C++ PBDS（Policy-Based Data Structures）の基本的な使い方について解説します。

順序集合（ordered set）とは

順序集合は、STLライブラリには含まれていない「ポリシーベース構造」の一つです。すべての要素を常にソートされた状態で保持し、重複する値は許容しません。通常の std::set の機能に加えて、以下のような強力な操作を対数時間 O(log n) で実行できる点が最大の特徴です。

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

これらの操作は標準の std::set では直接サポートされていないため、競技プログラミングなどで非常に重宝されます。

必要なヘッダーファイル

PBDSを使用するには、以下のヘッダーを読み込みます。

• #include <ext/pb_ds/assoc_container.hpp>
• #include <ext/pb_ds/tree_policy.hpp>

サンプルコード

#include <iostream>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
int main(){
    // 順序集合の宣言
    ordered_set o_set;
    o_set.insert(5);
    o_set.insert(1);
    o_set.insert(2);
    cout << *(o_set.find_by_order(1))
       << endl;
    cout << o_set.order_of_key(4)
       << endl;
    cout << o_set.order_of_key(5)
       << endl;
    if (o_set.find(2) != o_set.end())
       o_set.erase(o_set.find(2));
    cout << *(o_set.find_by_order(1))
       << endl;
    cout << o_set.order_of_key(4)
       << endl;
    return 0;
}

出力結果

2
2
2
5
1

出力の解説

最初に 5、1、2 を挿入した時点で、集合は {1, 2, 5} とソートされた状態になっています。

• find_by_order(1)：0始まりで1番目の要素「2」を出力
• order_of_key(4)：4未満の要素は1と2の2個なので「2」を出力
• order_of_key(5)：5未満の要素は1と2の2個なので「2」を出力

その後、値2を削除すると集合は {1, 5} となり、結果は次のように変化します。

• find_by_order(1)：1番目の要素「5」を出力
• order_of_key(4)：4未満の要素は1のみの1個なので「1」を出力

このように、PBDSの順序集合を使うことで、挿入・削除しながら順位に関する情報を効率的に取得できます。要素の順位取得やランク検索が必要な場面でぜひ活用してみてください。