Namespaces
Variants

    std::nth_element

    ja.cppreference.net より
     
    C++
    コンパイラサポート
    フリースタンディングとホステッド
    言語
    標準ライブラリ
    標準ライブラリヘッダ
    名前付き要件
    機能テストマクロ (C++20)
    言語サポートライブラリ
    コンセプトライブラリ (C++20)
    診断ライブラリ
    メモリ管理ライブラリ
    メタプログラミングライブラリ (C++11)
    一般ユーティリティライブラリ
    コンテナライブラリ
    イテレータライブラリ
    レンジライブラリ (C++20)
    アルゴリズムライブラリ
    文字列ライブラリ
    テキスト処理ライブラリ
    数値ライブラリ
    日付と時間ライブラリ
    入出力ライブラリ
    ファイルシステムライブラリ (C++17)
    並行処理サポートライブラリ (C++11)
    実行制御ライブラリ (C++26)
    技術仕様書
    シンボルインデックス
    外部ライブラリ
     
    アルゴリズムライブラリ
    制約付きアルゴリズムとレンジ上のアルゴリズム (C++20)
    制約付きアルゴリズム、例: ranges::copy、ranges::sort、...
    ソートおよび関連操作
    分割操作
    (C++11)    
    (C++11)

    ソート操作
    二分探索操作
    (分割された範囲に対して)
    集合操作 (ソート済み範囲に対して)
    マージ操作 (ソート済み範囲に対して)
    ヒープ操作
    最小値/最大値操作
    (C++11)
    (C++17)
    辞書式比較操作
    (C++20)
    順列操作


     
    ヘッダ <algorithm> 
    template< class RandomIt >
void nth_element( RandomIt first, RandomIt nth, RandomIt last );
    		で定義 (1) (C++20 で constexpr) 
    template< class ExecutionPolicy, class RandomIt >
void nth_element( ExecutionPolicy&& policy,
                  RandomIt first, RandomIt nth, RandomIt last );
    		(2) (C++17 以降) 
    template< class RandomIt, class Compare >
void nth_element( RandomIt first, RandomIt nth, RandomIt last,
                  Compare comp );
    		(3) (C++20 で constexpr) 
    template< class ExecutionPolicy, class RandomIt, class Compare >
void nth_element( ExecutionPolicy&& policy,
                  RandomIt first, RandomIt nth, RandomIt last,
                  Compare comp );
    		(4) (C++17 以降)

    nth_element の要素を再配置し、再配置後に次のようになります: [first, last)

    • nth が指す要素は、[first, last) がソートされた場合にその位置に来る要素に変更されます。
    • i 内のすべてのイテレータ [first, nth) および j 内のすべてのイテレータ [nth, last) について、次の条件が満たされます:
    1,2) bool(*j < *i)(C++20 まで)std::less{}(*j, *i)(C++20 以降) は false である。
    3,4) bool(comp(*j, *i)) は false である。


    1) 要素は仮想的に ソート される（operator< に関して）(C++20 まで)std::less{}(C++20 以降)。
    3) 要素は仮想的に comp に関してソートされる。
    2,4) (1,3) と同じだが、 に従って実行される。policy これらのオーバーロードは、以下の式の値が
    である場合にのみオーバーロード解決に参加する: true

    std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>

    		(C++20 まで)

    std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>

    		(C++20 以降)

    次の条件のいずれかが満たされる場合、動作は未定義です:

    (C++11 まで)
    (C++11 以降)

    引数

    first, last - 部分ソートする要素の 範囲 を定義するイテレータのペア
    nth - ソートの分割点を定義するランダムアクセスイテレータ
    policy - 使用する 実行ポリシー
    comp - 比較関数オブジェクト（Compare の要件を満たすオブジェクト）。最初の引数が2番目の引数より true小さい（つまり、順序的に 前 である）場合に を返します。

    比較関数のシグネチャは以下と同等であるべきです:

    bool cmp(const Type1& a, const Type2& b);

    シグネチャに const& を含める必要はありませんが、関数は渡されたオブジェクトを変更してはならず、値カテゴリに関わらず（const の可能性がある）型 Type1 および Type2 のすべての値を受け入れられなければなりません（したがって、値カテゴリ により、Type1& は許可されません。また、Type1 は、Type1 の移動がコピーと同等である場合を除き許可されません(C++11 以降)）。
    型 Type1 および Type2 は、型 RandomIt のオブジェクトを逆参照し、暗黙的に両方に変換できるようにする必要があります。 ​

    型要件
    -
    RandomIt は LegacyRandomAccessIterator の要件を満たすこと。
    -
    Compare は Compare の要件を満たすこと。

    計算量

    N を last - first とする:

    1) O(N) 回の比較（operator< を使用）(C++20 まで)std::less{}(C++20 以降)、平均。
    2) O(N) 回の比較（operator< を使用）(C++20 まで)std::less{}(C++20 以降)、および O(N·log(N)) 回のスワップ。
    3) O(N) 回の比較子 comp の適用、平均。
    4) O(N) 回の比較子 comp の適用、および O(N·log(N)) 回のスワップ。

    例外

    テンプレートパラメータ ExecutionPolicy を持つオーバーロードは、以下のようにエラーを報告します:

    • アルゴリズムの一部として呼び出された関数が例外を送出し、ExecutionPolicy が 標準ポリシー のいずれかである場合、std::terminate が呼ばれます。それ以外の ExecutionPolicy の場合、動作は実装定義です。
    • アルゴリズムがメモリの確保に失敗した場合、std::bad_alloc が送出されます。

    実装例

    libstdc++、libc++、および MSVC STL の実装も参照してください。

    ノート

    通常使用されるアルゴリズムは Introselect ですが、適切な平均ケース計算量を持つ他の 選択アルゴリズム も許容されます。

    例

    このコードを実行
    #include <algorithm>
#include <cassert>
#include <functional>
#include <iostream>
#include <numeric>
#include <vector>

void printVec(const std::vector<int>& vec)
{
    std::cout << "v = {";
    for (char sep[]{0, ' ', 0}; const int i : vec)
        std::cout << sep << i, sep[0] = ',';
    std::cout << "};\n";
}

int main()
{
    std::vector<int> v{5, 10, 6, 4, 3, 2, 6, 7, 9, 3};
    printVec(v);
    
    auto m = v.begin() + v.size() / 2;
    std::nth_element(v.begin(), m, v.end());
    std::cout << "\nThe median is " << v[v.size() / 2] << '\n';
    // The consequence of the inequality of elements before/after the Nth one:
    assert(std::accumulate(v.begin(), m, 0) < std::accumulate(m, v.end(), 0));
    printVec(v);
    
    // Note: comp function changed
    std::nth_element(v.begin(), v.begin() + 1, v.end(), std::greater{});
    std::cout << "\nThe second largest element is " << v[1] << '\n';
    std::cout << "The largest element is " << v[0] << '\n';
    printVec(v);
}

    出力例: 

    v = {5, 10, 6, 4, 3, 2, 6, 7, 9, 3};

The median is 6
v = {3, 2, 3, 4, 5, 6, 10, 7, 9, 6};

The second largest element is 9
The largest element is 10
v = {10, 9, 6, 7, 6, 3, 5, 4, 3, 2};

    欠陥報告

    以下の動作を変更する欠陥報告は、以前に公開されたC++標準に遡って適用されました。

    DR 適用先 公開された動作 正しい動作
    LWG 2150 C++98 再配置後、nth
    の前の1つの要素だけが nth     		の後の1つの要素より大きくないことが要求されていた要件を修正
    要件を修正
    LWG 2163 C++98 オーバーロード (1) が要素の比較に operator> を使用していた operator<
    に変更P0896R4 C++98 [first, nth) と [nth, last)
    が有効な範囲である必要がなかった     		いずれかが無効である場合、動作は未定義
    となる

    関連項目

    		 範囲内の最大の要素を返す
    (関数テンプレート & アルゴリズム関数オブジェクト)
    (C++20)
    		範囲内の最小の要素を返す
    (関数テンプレート & アルゴリズム関数オブジェクト)
    (C++20)
    		範囲の要素をコピーして部分ソートする
    (関数テンプレート & アルゴリズム関数オブジェクト)
    (C++20)
    		等価な要素間の相対順序を保持しながら範囲の要素をソートする
    (関数テンプレート & アルゴリズム関数オブジェクト)
    (C++20)
    		範囲の要素をソートする
    (関数テンプレート & アルゴリズム関数オブジェクト)
    (C++20)
    (C++20)
    		 範囲をソートした場合の N 番目の要素を見つける
    (アルゴリズム関数オブジェクト)