C++

參考

<algorithm>

函式模板
<algorithm>

std::is_permutation

相等 (1)
template <class ForwardIterator1, class ForwardIterator2>   bool is_permutation (ForwardIterator1 first1, ForwardIterator1 last1,                        ForwardIterator2 first2);
謂詞 (2)
template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>   bool is_permutation (ForwardIterator1 first1, ForwardIterator1 last1,                        ForwardIterator2 first2, BinaryPredicate pred);
測試範圍是否是另一個範圍的排列
比較第一個序列的範圍 [first1,last1) 和第二個序列開始於 first2 的範圍，如果兩個序列中的所有元素都匹配（即使順序不同），則返回 true。

元素使用operator==（或版本(2)中的pred）進行比較。

此函式模板的行為等同於
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
template <class InputIterator1, class InputIterator2>
  bool is_permutation (InputIterator1 first1, InputIterator1 last1,
                       InputIterator2 first2)
{
  std::tie (first1,first2) = std::mismatch (first1,last1,first2);
  if (first1==last1) return true;
  InputIterator2 last2 = first2; std::advance (last2,std::distance(first1,last1));
  for (InputIterator1 it1=first1; it1!=last1; ++it1) {
    if (std::find(first1,it1,*it1)==it1) {
      auto n = std::count (first2,last2,*it1);
      if (n==0 || std::count (it1,last1,*it1)!=n) return false;
    }
  }
  return true;
}

引數

first1, last1
輸入迭代器 指向第一個序列的初始和最終位置。使用的範圍是 [first1,last1)，它包含 first1 和 last1 之間的所有元素，包括 first1 指向的元素，但不包括 last1 指向的元素。
first2
輸入迭代器 指向第二個序列的初始位置。
該函式將考慮此序列中與範圍 [first1,last1) 中元素數量相同的元素。
如果此序列較短，則會導致*未定義行為*。
pred
二元函式，接受兩個元素作為引數（分別來自兩個序列，順序相同），並返回一個可轉換為 bool 的值。返回值指示元素在此函式上下文中是否被視為匹配。
該函式不得修改其任何引數。
這可以是指向函式的指標，也可以是函式物件。

InputIterator1 和 InputIterator2 應指向同一型別。

返回值

如果範圍 [first1,last1) 中的所有元素與從 first2 開始的範圍中的元素以任何順序進行相等比較，則返回 true，否則返回 false。

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
// is_permutation example
#include <iostream>     // std::cout
#include <algorithm>    // std::is_permutation
#include <array>        // std::array

int main () {
  std::array<int,5> foo = {1,2,3,4,5};
  std::array<int,5> bar = {3,1,4,5,2};

  if ( std::is_permutation (foo.begin(), foo.end(), bar.begin()) )
    std::cout << "foo and bar contain the same elements.\n";

  return 0;
}

輸出
foo and bar contain the same elements.


複雜度

如果兩個序列相等（元素順序相同），則複雜度為線性，與 first1 和 last1 之間的距離成正比。
否則，複雜度可達二次：執行最多 N2 次元素比較，直到確定結果（其中 N 是 first1 和 last1 之間的距離）。

資料競爭

兩個範圍中的部分（或全部）物件被訪問（可能多次）。

異常

如果任何元素比較（或pred）引發異常，或者任何迭代器操作引發異常，則丟擲異常。
請注意，無效的引數會導致 *未定義行為*。

另見

equal
測試兩個範圍中的元素是否相等 （函式模板）
mismatch
返回兩個範圍首次出現差異的位置 （函式模板）
next_permutation
將範圍轉換為下一個排列 （函式模板）
prev_permutation
將範圍轉換為上一個排列 （函式模板）