std::is_permutation(3) C++ Standard Libary std::is_permutation(3) NAME std::is_permutation - std::is_permutation Synopsis Defined in header <algorithm> template< class ForwardIt1, class ForwardIt2 > bool is_permutation( ForwardIt1 first1, ForwardIt1 (1) (since C++11) last1, (constexpr since C++20) ForwardIt2 first2 ); template< class ForwardIt1, class ForwardIt2, class BinaryPredicate > bool is_permutation( ForwardIt1 first1, ForwardIt1 (2) (since C++11) last1, (constexpr since C++20) ForwardIt2 first2, BinaryPredicate p ); template< class ForwardIt1, class ForwardIt2 > bool is_permutation( ForwardIt1 first1, ForwardIt1 (since C++14) last1, (3) (constexpr since C++20) ForwardIt2 first2, ForwardIt2 last2 ); template< class ForwardIt1, class ForwardIt2, class BinaryPredicate > bool is_permutation( ForwardIt1 first1, ForwardIt1 (since C++14) last1, (4) (constexpr since C++20) ForwardIt2 first2, ForwardIt2 last2, BinaryPredicate p ); 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). 1,3) Elements are compared using operator==. 2,4) Elements are compared using the given binary predicate p. 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. Parameters first1, last1 - the range of elements to compare first2, last2 - the second range to compare binary predicate which returns true if the elements should be treated as equal. The signature of the predicate function should be equiv- alent to the following: bool pred(const Type1 &a, const Type2 &b); p - 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 regard- less 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 im- plicitly converted to Type1 and Type2 respectively. Type requirements - ForwardIt1, ForwardIt2 must meet the requirements of LegacyForwardItera- tor. Return value true if the range [first1, last1) is a permutation of the range [first2, last2), false otherwise. Complexity Given \(\scriptsize N\)N as std::distance(first1, last1): 1) Exactly \(\scriptsize N\)N comparisons using operator== if the two ranges are equal, otherwise \(\scriptsize O(N^2)\)O(N2 ) comparisons in the worst case. 2) Exactly \(\scriptsize N\)N applications of the predicate p if the two ranges are equal, otherwise \(\scriptsize O(N^2)\)O(N2 ) applications in the worst case. 3,4) If ForwardIt1 and ForwardIt2 are both LegacyRandomAccessIterator, and last1 - first1 != last2 - first2 is true, no comparison will be made. Otherwise: 3) Exactly \(\scriptsize N\)N comparisons using operator== if the two ranges are equal, otherwise \(\scriptsize O(N^2)\)O(N2 ) comparisons in the worst case. 4) Exactly \(\scriptsize N\)N applications of the predicate p if the two ranges are equal, otherwise \(\scriptsize O(N^2)\)O(N2 ) applications in the worst case. 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; } Note The std::is_permutation can be used in testing, namely to check the cor- rectness 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. Example // Run this code #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 See also generates the next greater lexicographic permuta- tion of a next_permutation range of elements (function template) generates the next smaller lexicographic permuta- tion of a prev_permutation range of elements (function template) equivalence_relation specifies that a relation imposes an equivalence relation (C++20) (concept) ranges::is_permutation determines if a sequence is a permutation of an- other sequence (C++20) (niebloid) http://cppreference.com 2024.06.10 std::is_permutation(3)
NAME | Synopsis | Parameters | Type requirements | Return value | Complexity | Possible implementation | Note | Example | Output: | See also
Want to link to this manual page? Use this URL:
<https://man.FreeBSD.org/cgi/man.cgi?query=std::is_permutation&sektion=3&manpath=FreeBSD+Ports+15.1.quarterly>