std::partition

ヘッダー `<algorithm>` で定義
template< class ForwardIt, class UnaryPred > ForwardIt partition( ForwardIt first, ForwardIt last, UnaryPred p );	(1)	(C++20 以降 constexpr)
template< class ExecutionPolicy, class ForwardIt, class UnaryPred > ForwardIt partition( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, UnaryPred p );	(2)	(C++17以降)

1) first から last までの範囲の要素を並べ替えます。この並べ替えは、述語 p が true を返すすべての要素が、述語 p が false を返すすべての要素の前に来るように行われます。要素の相対的な順序は保持されません。

2) (1) と同じですが、policy に従って実行されます。

このオーバーロードは、以下のすべての条件が満たされた場合にのみオーバーロード解決に参加します。

std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> が true である。	(C++20まで)
std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>> は true です。	(C++20以降)

もし *first の型が Swappable ではない(C++11まで)ForwardIt が ValueSwappable ではない(C++11以降)場合、動作は未定義です。

first, last	-	並べ替える要素の範囲を定義するイテレータのペア
policy	-	使用する実行ポリシー
p	-	要素が他の要素よりも前に配置されるべき場合に true を返す単項述語。 p(v) の評価結果は、すべての引数 `v`（`VT` は `ForwardIt` の値型、VT は `const` の場合もある）に対して bool に変換可能でなければなりません（値カテゴリに関係なく）。また、`v` を変更してはなりません。したがって、パラメータ型として VT& は許可されません。また、VT も許可されません（ただし、`VT` においてムーブがコピーと同等な場合を除く）(C++11以降)。
型要件
- `ForwardIt` は LegacyForwardIterator の要件を満たさなければなりません。
- `UnaryPred` は Predicate の要件を満たさなければなりません。

[編集] 戻り値

2番目のグループの最初の要素へのイテレータ。

[編集] 計算量

std::distance(first, last) を $\scriptsize N$ $N$ とする

1)

N

回の p の適用。

ForwardIt が LegacyBidirectionalIterator の要件を満たす場合、最大

N/2

回のスワップ。それ以外の場合は最大

N

回のスワップ。

2)

O(N)

回の p の適用。

O(N\cdotlog(N))

回のスワップ。

[編集] 例外

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

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

[編集] 実装例

C++11 との互換性を保ちながら、オーバーロード (1) を実装します。

template<class ForwardIt, class UnaryPred>
ForwardIt partition(ForwardIt first, ForwardIt last, UnaryPred p)
{
    first = std::find_if_not(first, last, p);
    if (first == last)
        return first;
 
    for (auto i = std::next(first); i != last; ++i)
        if (p(*i))
        {
            std::iter_swap(i, first);
            ++first;
        }
 
    return first;
}

[編集] 例

このコードを実行

#include <algorithm>
#include <forward_list>
#include <iostream>
#include <iterator>
#include <vector>
 
template<class ForwardIt>
void quicksort(ForwardIt first, ForwardIt last)
{
    if (first == last)
        return;
 
    auto pivot = *std::next(first, std::distance(first, last) / 2);
    auto middle1 = std::partition(first, last, [pivot](const auto& em)
    {
        return em < pivot;
    });
    auto middle2 = std::partition(middle1, last, [pivot](const auto& em)
    {
        return !(pivot < em);
    });
 
    quicksort(first, middle1);
    quicksort(middle2, last);
}
 
int main()
{
    std::vector<int> v{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    std::cout << "Original vector: ";
    for (int elem : v)
        std::cout << elem << ' ';
 
    auto it = std::partition(v.begin(), v.end(), [](int i) {return i % 2 == 0;});
 
    std::cout << "\nPartitioned vector: ";
    std::copy(std::begin(v), it, std::ostream_iterator<int>(std::cout, " "));
    std::cout << "* ";
    std::copy(it, std::end(v), std::ostream_iterator<int>(std::cout, " "));
 
    std::forward_list<int> fl {1, 30, -4, 3, 5, -4, 1, 6, -8, 2, -5, 64, 1, 92};
    std::cout << "\nUnsorted list: ";
    for (int n : fl)
        std::cout << n << ' ';
 
    quicksort(std::begin(fl), std::end(fl));
    std::cout << "\nSorted using quicksort: ";
    for (int fi : fl)
        std::cout << fi << ' ';
    std::cout << '\n';
}

実行結果の例

Original vector: 0 1 2 3 4 5 6 7 8 9 
Partitioned vector: 0 8 2 6 4 * 5 3 7 1 9 
Unsorted list: 1 30 -4 3 5 -4 1 6 -8 2 -5 64 1 92 
Sorted using quicksort: -8 -5 -4 -4 1 1 1 2 3 5 6 30 64 92

[編集] 不具合報告

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

DR	適用対象	公開された動作	正しい動作
LWG 498	C++98	`std::partition` は first と last を LegacyBidirectionalIterator であることを要求していました。	単に要求していたのは LegacyForwardIterator
LWG 2150	C++98	`std::partition` は、1つの要素を満足する要素の前に配置することを要求していました。	修正されました。要件

[編集] 関連項目

is_partitioned (C++11)	範囲が指定された述語によってパーティション化されているかどうかを判断する (関数テンプレート) [編集]
stable_partition	相対的な順序を維持しながら要素を2つのグループに分割する (関数テンプレート) [編集]
ranges::partition (C++20)	要素の範囲を2つのグループに分割する (アルゴリズム関数オブジェクト)[編集]

コンパイラサポート
フリースタンディングとホスト
言語
標準ライブラリ
標準ライブラリヘッダー
名前付き要件
機能テストマクロ (C++20)
言語サポートライブラリ
コンセプトライブラリ (C++20)
診断ライブラリ
メモリ管理ライブラリ
メタプログラミングライブラリ (C++11)
汎用ユーティリティライブラリ
コンテナライブラリ
イテレータライブラリ
Rangesライブラリ (C++20)
アルゴリズムライブラリ
文字列ライブラリ
テキスト処理ライブラリ
数値ライブラリ
日付と時刻ライブラリ
入出力ライブラリ
ファイルシステムライブラリ (C++17)
並行サポートライブラリ (C++11)
実行制御ライブラリ (C++26)
Technical specifications (技術仕様)
シンボルインデックス
外部ライブラリ

cppreference.com

名前空間

変種

表示

操作