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 を返すtrue の前に来るすべての要素（述語p が false を返すfalse。要素の相対的な順序は保持されません。

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

このオーバーロードは、以下の式の値が true である場合にのみオーバーロード解決に関与します true:

`std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>`	(C++20 まで)
`std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>`	(C++20 から)

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

パラメータ

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

戻り値

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

計算量

与えられた $\scriptsize N$ $N$ を std:: distance ( first, last ) として：

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` は p を満たす1つの要素を p を満たさない1つの要素の前に配置することを要求	要件を修正

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

is_partitioned (C++11)	指定された述語によって範囲が分割されているかどうかを判定する (関数テンプレート & アルゴリズム関数オブジェクト)
ranges::is_partitioned (C++20)	指定された述語によって範囲が分割されているかどうかを判定する (関数テンプレート & アルゴリズム関数オブジェクト)
stable_partition	各グループ内の相対的な順序を保ちながら要素を2つのグループに分割する (関数テンプレート & アルゴリズム関数オブジェクト)
ranges::stable_partition (C++20)
ranges::partition (C++20)	要素の範囲を2つのグループに分割する (アルゴリズム関数オブジェクト)

ja.cppreference.net

Namespaces

Variants

std::partition

目次

パラメータ

戻り値

計算量

例外

実装例

例

不具合報告

関連項目