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
将范围转换为上一个排列 （函数模板）