最終更新日時: 2025年07月09日 00時33分39秒 (JST)
Akira Takahashi が更新

履歴 編集

function template
<algorithm>

# std::ranges::is_permutation(C++20)

    namespace std::ranges {
      template <forward_iterator I1,
                sentinel_for<I1> S1,
                forward_iterator I2,
                sentinel_for<I2> S2,
                class Proj1 = identity,
                class Proj2 = identity,
                indirect_equivalence_relation<
                  projected<I1, Proj1>,
                  projected<I2, Proj2>
                > Pred = ranges::equal_to>
      constexpr bool
        is_permutation(I1 first1,
                       S1 last1,
                       I2 first2,
                       S2 last2,
                       Pred pred = {},
                       Proj1 proj1 = {},
                       Proj2 proj2 = {}); // (1) C++20

      template <forward_range R1,
                forward_range R2,
                class Proj1 = identity,
                class Proj2 = identity,
                indirect_equivalence_relation<
                  projected<iterator_t<R1>, Proj1>,
                  projected<iterator_t<R2>, Proj2>
                > Pred = ranges::equal_to>
      constexpr bool
        is_permutation(R1&& r1,
                       R2&& r2,
                       Pred pred = {},
                       Proj1 proj1 = {},
                       Proj2 proj2 = {}); // (2) C++20
    }

## 概要

範囲 `[first2, last2)` を並べ替えたものが、`[first1, last1)` の範囲と一致するか判定する。

- (1): イテレータ範囲を指定する
- (2): Rangeを直接指定する

## 戻り値

`last2` が与えられている形式の場合、`last1 - first1 != last2 - first2` であれば `false` を返す。
そうでなければ、`[first1, last1)` の範囲と `[first2, first2 + (last1 - first1))` の範囲を並び変えたもので、`equal(first1, last1, first2)`、あるいは `equal(first1, last1, first2, pred)` が `true` を返すようなものがあれば `true` を、そうでなければ `false` を返す。
なお、実際に並べ替えが行われるわけではない。

## 計算量

`last2` が与えられている形式の場合、`I1` と `I2` がどちらも`random_access_iterator`のモデルであり、かつ `last1 - first1 != last2 - first2` であれば 1 度も述語の適用を行わない。
そうでなければ、`equal(first1, last1, first2, last2) == true` もしくは `equal(first1, last1, first2, last2, pred) == true` の場合（`last2` が無い形式の場合、`equal` も `last2` の無い形式で置き換える）、`distance(first1, last1)` 回の述語適用で完了する。
そうでなければ、`distance(first1, last1)` をNとした場合に最悪O(N^2)回の述語適用で完了する。

## 例

    #include <iostream>
    #include <vector>
    #include <algorithm>

    int main ()
    {
      std::vector<int> v = {1, 2, 3};

      std::vector<int> good = {2, 3, 1};
      std::vector<int> bad = {2, 3, 4};

      std::cout << std::boolalpha;
      std::cout << std::ranges::is_permutation(v, good) << std::endl;
      std::cout << std::ranges::is_permutation(v, bad) << std::endl;
    }

### 出力

    true
    false

## バージョン

### 言語

- C++20

### 処理系

- Clang: ??
- GCC: 10.1.0 ✅
- ICC: ??
- Visual C++: 2019 Update 10 ✅

## 参照

- N4861 25 Algorithms library