std::is_permutation
<algorithm>
bool is_permutation( ForwardIt1 first1, ForwardIt1 last1,
(constexpr since C++20)
class BinaryPredicate >
bool is_permutation( ForwardIt1 first1, ForwardIt1 last1,
(constexpr since C++20)
bool is_permutation( ForwardIt1 first1, ForwardIt1 last1,
(constexpr since C++20)
class BinaryPredicate >
bool is_permutation( ForwardIt1 first1, ForwardIt1 last1,
ForwardIt2 first2, ForwardIt2 last2,
(constexpr since C++20)
Checks whether [first1, last1) is a permutation of a range starting from first2:
- For overloads (1,2), the second range has std::distance (first1, last1) elements.
- For overloads (3,4), the second range is
[first2,last2).
If ForwardIt1 and ForwardIt2 have different value types, the program is ill-formed.
If the comparison function is not an equivalence relation, the behavior is undefined.
Contents
[edit] Parameters
The signature of the predicate function should be equivalent to the following:
bool pred(const Type1 &a, const Type2 &b);
While the signature does not need to have const &, the function must not modify the objects passed to it and must be able to accept all values of type (possibly const) Type1 and Type2 regardless of value category (thus, Type1 & is not allowed, nor is Type1 unless for Type1 a move is equivalent to a copy(since C++11)).
The types Type1 and Type2 must be such that objects of types InputIt1 and InputIt2 can be dereferenced and then implicitly converted to Type1 and Type2 respectively.
ForwardIt1, ForwardIt2 must meet the requirements of LegacyForwardIterator.
[edit] Return value
true if the range [first1, last1) is a permutation of the range [first2, last2), false otherwise.
[edit] Complexity
Given \(\scriptsize N\)N as std::distance (first1, last1):
) comparisons in the worst case.
) applications in the worst case.
ForwardIt1 and ForwardIt2 are both LegacyRandomAccessIterator, and last1 - first1 != last2 - first2 is true, no comparison will be made.) comparisons in the worst case.
) applications in the worst case.
[edit] Possible implementation
template<class ForwardIt1, class ForwardIt2> bool is_permutation(ForwardIt1 first, ForwardIt1 last, ForwardIt2 d_first) { // skip common prefix std::tie (first, d_first) = std::mismatch (first, last, d_first); // iterate over the rest, counting how many times each element // from [first, last) appears in [d_first, d_last) if (first != last) { ForwardIt2 d_last = std::next (d_first, std::distance (first, last)); for (ForwardIt1 i = first; i != last; ++i) { if (i != std::find (first, i, *i)) continue; // this *i has been checked auto m = std::count (d_first, d_last, *i); if (m == 0 || std::count (i, last, *i) != m) return false; } } return true; }
[edit] Note
The std::is_permutation can be used in testing, namely to check the correctness of rearranging algorithms (e.g. sorting, shuffling, partitioning). If x is an original range and y is a permuted range then std::is_permutation(x, y) == true means that y consist of "the same" elements, maybe staying at other positions.
[edit] Example
#include <algorithm> #include <iostream> template<typename Os, typename V> Os& operator<<(Os& os, const V& v) { os << "{ "; for (const auto& 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::is_permutation(v1.begin(), v1.end(), v3.begin()) << '\n'; }
Output:
{ 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[edit] See also
(function template) [edit]
(function template) [edit]
(algorithm function object)[edit]