std::is_permutation
| 定义于头文件 <algorithm>
|
||
| (1) | ||
| template< class ForwardIt1, class ForwardIt2 > bool is_permutation( ForwardIt1 first1, ForwardIt1 last1, |
(C++11 起) (C++20 前) |
|
| template< class ForwardIt1, class ForwardIt2 > constexpr bool is_permutation( ForwardIt1 first1, ForwardIt1 last1, |
(C++20 起) | |
| (2) | ||
| template< class ForwardIt1, class ForwardIt2, class BinaryPredicate > bool is_permutation( ForwardIt1 first1, ForwardIt1 last1, |
(C++11 起) (C++20 前) |
|
| template< class ForwardIt1, class ForwardIt2, class BinaryPredicate > constexpr bool is_permutation( ForwardIt1 first1, ForwardIt1 last1, |
(C++20 起) | |
| (3) | ||
| template< class ForwardIt1, class ForwardIt2 > bool is_permutation( ForwardIt1 first1, ForwardIt1 last1, |
(C++14 起) (C++20 前) |
|
| template< class ForwardIt1, class ForwardIt2 > constexpr bool is_permutation( ForwardIt1 first1, ForwardIt1 last1, |
(C++20 起) | |
| (4) | ||
| template< class ForwardIt1, class ForwardIt2, class BinaryPredicate > bool is_permutation( ForwardIt1 first1, ForwardIt1 last1, |
(C++14 起) (C++20 前) |
|
| template< class ForwardIt1, class ForwardIt2, class BinaryPredicate > constexpr bool is_permutation( ForwardIt1 first1, ForwardIt1 last1, |
(C++20 起) | |
若存在范围 [first1, last1) 中元素的排列，使得该范围等于 [first2,last2) ，则返回 true ，若不给出，则其中 last2 代表 first2 + (last1 - first1) 。
p 比较元素。若它不是等价关系则行为未定义。参数
| first1, last1 | - | 要比较的元素范围 |
| first2, last2 | - | 要比较的第二范围 |
| p | - | 若应把元素当做相等则返回 true 的二元谓词。 谓词函数的签名应等价于如下： bool pred(const Type &a, const Type &b);
|
| 类型要求 | ||
-ForwardIt1, ForwardIt2 必须满足遗留向前迭代器 (LegacyForwardIterator) 的要求。
| ||
-ForwardIt1 与 ForwardIt2 必须拥有相同的值类型。
| ||
返回值
若范围 [first1, last1) 是 [first2, last2) 的排列则为 true 。
复杂度
至多应用 O(N2) 次谓词，或若序列已经相等，则准确应用 N 次，其中 N=std::distance(first1, last1) 。
然而，若 ForwardIt1 和 ForwardIt2 满足遗留随机访问迭代器 (LegacyRandomAccessIterator) 的要求且 std::distance(first1, last1) != std::distance(first2, last2) ，则不应用谓词。
可能的实现
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); // 在 rest 上迭代，计数 [d_first, d_last) 中出现多少次 // 每个来自 [first, last) 的元素 if (first != last) { ForwardIt2 d_last = d_first; std::advance(d_last, 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; } |
示例
#include <algorithm> #include <vector> #include <iostream> int main() { std::vector<int> v1{1,2,3,4,5}; std::vector<int> v2{3,5,4,1,2}; std::cout << "3,5,4,1,2 is a permutation of 1,2,3,4,5? " << std::boolalpha << std::is_permutation(v1.begin(), v1.end(), v2.begin()) << '\n'; std::vector<int> v3{3,5,4,1,1}; std::cout << "3,5,4,1,1 is a permutation of 1,2,3,4,5? " << std::boolalpha << 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
参阅
| 产生某个元素范围的按字典顺序的下一个较大的排列 (函数模板) | |
| 产生某个元素范围的按字典顺序的下一个较小的排列 (函数模板) |
