std::is_permutation
| Defined in header <algorithm>
|
||
template< class ForwardIt1, class ForwardIt2 >
bool is_permutation( ForwardIt1 first1, ForwardIt1 last1,
ForwardIt2 first2 );
|
(1) | (since C++11) (constexpr since C++20) |
template< class ForwardIt1, class ForwardIt2,
class BinaryPredicate >
bool is_permutation( ForwardIt1 first1, ForwardIt1 last1,
ForwardIt2 first2, BinaryPredicate p );
|
(2) | (since C++11) (constexpr since C++20) |
template< class ForwardIt1, class ForwardIt2 >
bool is_permutation( ForwardIt1 first1, ForwardIt1 last1,
ForwardIt2 first2, ForwardIt2 last2 );
|
(3) | (since C++14) (constexpr since C++20) |
template< class ForwardIt1, class ForwardIt2,
class BinaryPredicate >
bool is_permutation( ForwardIt1 first1, ForwardIt1 last1,
ForwardIt2 first2, ForwardIt2 last2,
BinaryPredicate p );
|
(4) | (since C++14) (constexpr since C++20) |
Checks whether the first target range [first1, last1) is a permutation of the second target range [first2, last2). For overloads without the last2 parameter, last2 is std::next(first2, std::distance(first1, last1)).
operator==.p.If ForwardIt1 and ForwardIt2 have different value types, the program is ill-formed.
If the comparator is not an equivalence relation, the behavior is undefined.
Parameters
| first1, last1 | - | the pair of iterators defining the first target range |
| first2, last2 | - | the pair of iterators defining the second target range |
| p | - | binary predicate which returns true if the elements should be treated as equal. The signature of the predicate function should be equivalent to the following:
While the signature does not need to have |
| Type requirements | ||
-ForwardIt1, ForwardIt2 must meet the requirements of LegacyForwardIterator.
| ||
Return value
true if the first target range is a permutation of the second target range, false otherwise.
Complexity
Given \(\scriptsize N\)N as std::distance(first1, last1):
operator== (or only exactly \(\scriptsize N\)N comparisons if the two target ranges are lexicographically equal).p (or only exactly \(\scriptsize N\)N applications if the two target ranges are lexicographically equal).If both ForwardIt1 and ForwardIt2 meet the requirements of LegacyRandomAccessIterator, and \(\scriptsize N\)N does not equal std::distance(first2, last2), then no comparison will be made.
Note
If the elements are less-than-comparable, sorting both ranges and comparing them for equality has better complexity guarantees.
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.
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;
}
|
Example
#include <algorithm>
#include <initializer_list>
#include <print>
int main()
{
static constexpr auto v1 = {1, 2, 3, 4, 5},
v2 = {3, 5, 4, 1, 2},
v3 = {3, 5, 4, 1, 1};
for (std::print("{} <- reference list\n", v1); const auto& v : {v2, v3})
std::print("{} <- is permutation: {}\n", v,
std::is_permutation(v1.begin(), v1.end(), v.begin()));
}
Output:
[1, 2, 3, 4, 5] <- reference list
[3, 5, 4, 1, 2] <- is permutation: true
[3, 5, 4, 1, 1] <- is permutation: false
See also
(C++20) |
determines if a sequence is a permutation of another sequence (algorithm function object) |
| generates the next greater lexicographic permutation of a range of elements (function template & algorithm function object) | |
(C++20) |
|
| generates the next smaller lexicographic permutation of a range of elements (function template & algorithm function object) | |
(C++20) |
|
(C++20) |
specifies that a relation imposes an equivalence relation (concept) |