GeezerVison

The World Wide Web, restored to 800 pixels of glory.

GeezerVison is showing cpprefjp.github.io — std::is_permutation - cpprefjp C++日本語リファレンス

リファレンス
algorithm
is_permutation

最終更新日時: 2026年09月19日 21時31分51秒 (JST)
rotarymars が更新

履歴編集

function template

std::is_permutation(C++11)

namespace std {
  template <class ForwardIterator1, class ForwardIterator2>
  bool is_permutation(ForwardIterator1 first1,
                      ForwardIterator1 last1,
                      ForwardIterator2 first2);           // (1) C++11

  template <class ForwardIterator1, class ForwardIterator2>
  constexpr bool is_permutation(ForwardIterator1 first1,
                                ForwardIterator1 last1,
                                ForwardIterator2 first2); // (1) C++20

  template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
  bool is_permutation(ForwardIterator1 first1,
                      ForwardIterator1 last1,
                      ForwardIterator2 first2,
                      BinaryPredicate pred);              // (2) C++11

  template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
  constexpr bool is_permutation(ForwardIterator1 first1,
                                ForwardIterator1 last1,
                                ForwardIterator2 first2,
                                BinaryPredicate pred);    // (2) C++20

  template <class ForwardIterator1, class ForwardIterator2>
  bool is_permutation(ForwardIterator1 first1,
                      ForwardIterator1 last1,
                      ForwardIterator2 first2,
                      ForwardIterator2 last2);            // (3) C++14

  template <class ForwardIterator1, class ForwardIterator2>
  constexpr bool is_permutation(ForwardIterator1 first1,
                                ForwardIterator1 last1,
                                ForwardIterator2 first2,
                                ForwardIterator2 last2);  // (3) C++20

  template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
  bool is_permutation(ForwardIterator1 first1,
                      ForwardIterator1 last1,
                      ForwardIterator2 first2,
                      ForwardIterator2 last2,
                      BinaryPredicate pred);              // (4) C++14

  template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
  constexpr bool is_permutation(ForwardIterator1 first1,
                                ForwardIterator1 last1,
                                ForwardIterator2 first2,
                                ForwardIterator2 last2,
                                BinaryPredicate pred);    // (4) C++20
}

概要

first2 で始まる範囲を並べ替えたものが、イテレータ範囲[first1, last1)と一致するか判定する。

テンプレートパラメータ制約

decltype(*first1) と decltype(*first2) の型が同じであること。
BinaryPredicate は同値関係を持っていること。

戻り値

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 が与えられている形式の場合、ForwardIterator1 と ForwardIterator2 がどちらもランダムアクセスイテレータの要件を満たし、かつ 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::is_permutation(v.begin(), v.end(), good.begin()) << std::endl;
  std::cout << std::is_permutation(v.begin(), v.end(), bad.begin()) << std::endl;
}

出力

true
false

実装例

template <class ForwardIterator1, class ForwardIterator2>
bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
                    ForwardIterator2 first2)
{
  std::tie(first1, first2) = std::mismatch(first1, last1, first2);
  if (first1 == last1)
    return true;
  auto last2 = std::next(first2, std::distance(first1, last1));

  for (; first1 != last1; ++first1) {
    auto count2 = std::count(first2, last2, *first1);
    if (count2 == 0 || std::count(std::next(first1), last1, *first1) >= count2)
      return false;
  }
  return true;
}

template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
                    ForwardIterator2 first2, BinaryPredicate pred)
{
  std::tie(first1, first2) = std::mismatch(first1, last1, first2, pred);
  if (first1 == last1)
    return true;
  auto last2 = std::next(first2, std::distance(first1, last1));

  using value_type = typename std::iterator_traits<ForwardIterator1>::value_type;
  auto upred = [&pred, &first1](const value_type& x) { return pred(*first1, x); };
  for (; first1 != last1; ++first1) {
    auto count2 = std::count_if(first2, last2, upred);
    if (count2 == 0 || std::count_if(std::next(first1), last1, upred) >= count2)
      return false;
  }
  return true;
}

#if __cplusplus >= 201402L

template <class RandomAccessIterator1, class RandomAccessIterator2, class BinaryPredicate>
bool is_permutation_impl(RandomAccessIterator1 first1, RandomAccessIterator1 last1,
                         RandomAccessIterator2 first2, RandomAccessIterator2 last2,
                         BinaryPredicate pred,
                         std::random_access_iterator_tag, std::random_access_iterator_tag)
{
  if (last1 - first1 != last2 - first2)
    return false;
  return std::is_permutation(first1, last1, first2, pred);
}

template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
bool is_permutation_impl(ForwardIterator1 first1, ForwardIterator1 last1,
                         ForwardIterator2 first2, ForwardIterator2 last2,
                         BinaryPredicate pred,
                         std::forward_iterator_tag, std::forward_iterator_tag)
{
  std::tie(first1, first2) = std::mismatch(first1, last1, first2, last2, pred);
  if (first1 == last1 || first2 == last2)
    return first1 == last1 && first2 == last2;
  if (std::distance(first1, last1) != std::distance(first2, last2))
    return false;

  auto upred = [&pred, &first1](const auto& x) { return pred(*first1, x); };
  for (; first1 != last1; ++first1) {
    auto count2 = std::count_if(first2, last2, upred);
    if (count2 == 0 || std::count_if(std::next(first1), last1, upred) >= count2)
      return false;
  }
  return true;
}

template <class ForwardIterator1, class ForwardIterator2>
bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
                    ForwardIterator2 first2, ForwardIterator2 last2)
{
  return is_permutation_impl(first1, last1, first2, last2, std::equal_to<>(),
                             typename std::iterator_traits<ForwardIterator1>::iterator_category(),
                             typename std::iterator_traits<ForwardIterator2>::iterator_category());
}


template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
                    ForwardIterator2 first2, ForwardIterator2 last2,
                    BinaryPredicate pred)
{
  return is_permutation_impl(first1, last1, first2, last2, pred,
                             typename std::iterator_traits<ForwardIterator1>::iterator_category(),
                             typename std::iterator_traits<ForwardIterator2>::iterator_category());
}

#endif

バージョン

言語

C++11
C++14: 2つ目の終端のイテレータlast2を実引数に取るオーバーロードの追加。

処理系

Clang: 9.0.1 ✅
GCC: 4.7.0 ✅
Visual C++: 2010 ✅, 2012 ✅, 2013 ✅, 2015 ✅
- C++14で追加されたオーバーロードは2015から実装されている。

参照

N3671 Making non-modifying sequence operations more robust: Revision 2
- C++14から追加された、last2を受け取るオーバーロードの提案文書
P0202R3 Add Constexpr Modifiers to Functions in <algorithm> and <utility> Headers
LWG Issue 1431. is_permutation must be more restrictive
- C++11で、2つのイテレータ範囲の値型が同じであり、比較関数が同値関係であることが要件に追加された。それ以外の場合は仕様として意味が定まらないため

You are visitor 01402503 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.

GeezerVison

std::is_permutation(C++11)

概要

テンプレートパラメータ制約

戻り値

計算量

例

出力

実装例

バージョン

言語

処理系

関連項目

参照