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) ,则不应用谓词。
排列关系是等价关系。
注解
std::is_permutation 能用于按照其名称地测试重排算法(例如排序、打乱、划分)的正确性。若 x
为原范围而 y
是重排后范围则 std::is_permutation(x, y) == true 表示 y
由可能位于其他位置的“相同”元素组成。
可能的实现
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 <iostream> #include <algorithm> template<typename Os, typename V> Os& operator<< (Os& os, V const& v) { os << "{ "; for (auto const& e : v) os << e << ' '; return os << "}"; } int main() { static constexpr auto v1 = {1,2,3,4,5}; static constexpr auto v2 = {3,5,4,1,2}; static constexpr auto v3 = {3,5,4,1,1}; std::cout << v2 << " is a permutation of " << v1 << ": " << std::boolalpha << std::is_permutation(v1.begin(), v1.end(), v2.begin()) << '\n' << v3 << " is a permutation of " << v1 << ": " << 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
参阅
产生某个元素范围的按字典顺序的下一个较大的排列 (函数模板) | |
产生某个元素范围的按字典顺序的下一个较小的排列 (函数模板) | |
(C++20) |
指定 relation 施加等价关系 (概念) |
(C++20) |
确定一个序列是否为另一序列的重排 (niebloid) |