std::is_permutation

ヘッダ`<algorithm>`
template< class ForwardIt1, class ForwardIt2 > bool is_permutation( ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2 );	で定義 (1)	(C++11 から) (C++20 から constexpr)
template< class ForwardIt1, class ForwardIt2, class BinaryPredicate > bool is_permutation( ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, BinaryPredicate p );	(2)	(C++11 から) (C++20 から constexpr)
template< class ForwardIt1, class ForwardIt2 > bool is_permutation( ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2 );	(3)	(C++14 から) (C++20 から constexpr)
template< class ForwardIt1, class ForwardIt2, class BinaryPredicate > bool is_permutation( ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2, BinaryPredicate p );	(4)	(C++14 から) (C++20 から constexpr)

[first1, last1) が順列であるかどうかをチェックします。範囲は first2 から始まります：

オーバーロード (1,2) では、2番目の範囲は std::distance(first1, last1) 個の要素を持ちます。
オーバーロード (3,4) では、2番目の範囲は [first2, last2) です。

1,3) 要素の比較には operator== が使用されます。

2,4) 要素の比較には、指定された二項述語 p が使用されます。

もし ForwardIt1 と ForwardIt2 の値型が異なる場合、プログラムは不適格 (ill-formed) です。

比較関数が同値関係でない場合、動作は未定義です。

パラメータ

first1, last1	-	比較する最初の要素の範囲を定義するイテレータのペア
first2, last2	-	比較する2番目の要素の範囲を定義するイテレータのペア
p	-	要素が等しいと扱われるべき場合に true を返す二項述語。述語関数のシグネチャは以下と同等であるべき： bool pred ( const Type1 & a, const Type2 & b ) ; シグネチャが const & を持つ必要はないが、関数は渡されたオブジェクトを変更してはならず、値カテゴリに関係なく（したがって、 Type1 & は許可されない、また Type1 `Type1` に対してムーブがコピーと等価でない限り許可されない (C++11以降) ）すべての `Type1` と `Type2` 型の値を受け入れられなければならない。型 Type1 と Type2 は、 InputIt1 と InputIt2 型のオブジェクトが間接参照可能であり、それぞれ Type1 と Type2 に暗黙的に変換可能でなければならない。
型要件
- `ForwardIt1, ForwardIt2` は LegacyForwardIterator の要件を満たさなければならない。

戻り値

true 範囲 [ first1 , last1 ) が範囲 [ first2 , last2 ) の順列である場合、 false それ以外の場合。

計算量

与えられた $\scriptsize N$ $N$ として std::distance(first1, last1):

1) 二つの範囲が等しい場合は正確に

N

回の比較を operator== を用いて行い、そうでない場合は最悪で

O(N 2)

回の比較を行う。

2) 二つの範囲が等しい場合は正確に

N

回の述語の適用を p を用いて行い、そうでない場合は最悪で

O(N 2)

回の適用を行う。

3,4) ForwardIt1 と ForwardIt2 が共に LegacyRandomAccessIterator であり、かつ last1 - first1 != last2 - first2 が true である場合、比較は行われない。

それ以外の場合:

3) 二つの範囲が等しい場合は正確に

N

回の比較を operator== を用いて行い、そうでない場合は最悪で

O(N 2)

回の比較を行う。

4) 二つの範囲が等しい場合は正確に

N

回の述語の適用を p を用いて行い、そうでない場合は最悪で

O(N 2)

回の適用を行う。

実装例

template<class ForwardIt1, class ForwardIt2>
bool is_permutation(ForwardIt1 first, ForwardIt1 last,
                    ForwardIt2 d_first)
{
    // 共通プレフィックスをスキップ
    std::tie(first, d_first) = std::mismatch(first, last, d_first);
    // 残りの要素を反復処理し、[first, last) の各要素が
    // [d_first, d_last) に何回出現するかをカウント
    if (first != last)
    {
        ForwardIt2 d_last = std::next(d_first, std::distance(first, last));
        for (ForwardIt1 i = first; i != last; ++i)
        {
            if (i != std::find(first, i, *i))
                continue; // この *i は既にチェック済み
            auto m = std::count(d_first, d_last, *i);
            if (m == 0 || std::count(i, last, *i) != m)
                return false;
        }
    }
    return true;
}

注記

std::is_permutationは、並べ替えアルゴリズム（例：ソート、シャッフル、パーティショニング）の正確性を検証するためにテストで使用できます。xが元の範囲でyが並べ替えられた範囲の場合、std::is_permutation(x, y)==trueは、yが「同じ」要素で構成されている（異なる位置にある可能性がある）ことを意味します。

例

このコードを実行

#include <algorithm>
#include <iostream>
template<typename Os, typename V>
Os& operator<<(Os& os, const V& v)
{
    os << "{ ";
    for (const auto& e : v)
        os << e << ' ';
    return os << '}';
}
int main()
{
    static constexpr auto v1 = {1, 2, 3, 4, 5};
    static constexpr auto v2 = {3, 5, 4, 1, 2};
    static constexpr auto v3 = {3, 5, 4, 1, 1};
    std::cout << v2 << " is a permutation of " << v1 << ": " << std::boolalpha
              << std::is_permutation(v1.begin(), v1.end(), v2.begin()) << '\n'
              << v3 << " is a permutation of " << v1 << ": "
              << std::is_permutation(v1.begin(), v1.end(), v3.begin()) << '\n';
}

出力:

{ 3 5 4 1 2 } is a permutation of { 1 2 3 4 5 }: true
{ 3 5 4 1 1 } is a permutation of { 1 2 3 4 5 }: false

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

next_permutation	要素範囲の辞書順で次に大きい順列を生成する (関数テンプレート & アルゴリズム関数オブジェクト)
ranges::next_permutation (C++20)	要素範囲の辞書順で次に大きい順列を生成する (関数テンプレート & アルゴリズム関数オブジェクト)
prev_permutation	要素範囲の辞書順で次に小さい順列を生成する (関数テンプレート & アルゴリズム関数オブジェクト)
ranges::prev_permutation (C++20)	要素範囲の辞書順で次に小さい順列を生成する (関数テンプレート & アルゴリズム関数オブジェクト)
equivalence_relation (C++20)	は、`relation` が同値関係を課すことを (コンセプト)
ranges::is_permutation (C++20)	あるシーケンスが別のシーケンスの順列であるかどうかを判定する (アルゴリズム関数オブジェクト)

ja.cppreference.net

Namespaces

Variants

std::is_permutation

目次

パラメータ

戻り値

計算量

実装例

注記

例

関連項目