C++のorder_of_key()関数とは?使い方をサンプルコード付きで解説

C++のorder_of_key()関数とは

本記事では、C++におけるorder_of_key()関数の使い方と動作原理について詳しく解説します。

order_of_key()は、GCC拡張ライブラリ「GNU PBDS(Policy-Based Data Structures)」が提供する順序付きセット(ordered_set)のメソッドです。引数としてキーを1つ受け取り、そのセット内に存在する「指定したキーより小さい要素」の個数を返します。

内部的には赤黒木(平衡二分探索木)が使用されており、大量のデータがあってもO(log n)の計算量で高速に処理できる点が大きな特徴です。競技プログラミングなどで順位の判定やランク検索を行う際に頻繁に活用されます。

必要なヘッダーと型定義

order_of_key()を使用するには、以下のヘッダーをインクルードし、__gnu_pbds名前空間のもとで順序付きセットを定義します。

• <ext/pb_ds/assoc_container.hpp>:連結コンテナの定義
• <ext/pb_ds/tree_policy.hpp>:木構造のポリシー(動作仕様)の定義

サンプルコード

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

// 順序付きセットの初期化
typedef tree<int, null_type, less<int>, rb_tree_tag,
      tree_order_statistics_node_update>
    ordered_set;

int main(){
    ordered_set mySet;
    mySet.insert(5);
    mySet.insert(2);
    mySet.insert(6);
    mySet.insert(4);

    cout << "6より小さい要素の個数::" << mySet.order_of_key(6) << endl;
    cout << "7より小さい要素の個数 ::" << mySet.order_of_key(7) << endl;
    return 0;
}

実行結果

6より小さい要素の個数::3
7より小さい要素の個数 ::4

コードの解説

このプログラムでは、順序付きセットmySetに{5, 2, 6, 4}の4つの整数を挿入しています。セット内部では要素が自動的にソートされ、{2, 4, 5, 6}の状態で保持されます。

• order_of_key(6):6より小さい要素は{2, 4, 5}の3つなので「3」が出力されます。
• order_of_key(7):7より小さい要素は{2, 4, 5, 6}の4つすべてなので「4」が出力されます。

また、指定したキーがセット内に存在する場合、戻り値はそのキーの順位(0始まりのインデックス)を意味することにも注目してください。order_of_key(6)の結果「3」は、6がセット内で4番目(インデックス3)の要素であることも示しています。

まとめ

order_of_key()を活用すれば、標準のstd::setでは実現しにくい「特定の値未満の要素数の取得」を効率的に行えます。対となる機能として、インデックスから要素を直接取得するfind_by_order()も併せて覚えておくと便利です。