Defined in header
template<classForwardIt1,classForwardIt2>boolis_permutation(ForwardIt1first1,ForwardIt1last1,ForwardIt2first2); (1) (since C++11)
(constexpr since C++20)template<classForwardIt1,classForwardIt2,classBinaryPredicate>boolis_permutation(ForwardIt1first1,ForwardIt1last1,ForwardIt2first2,BinaryPredicatep); (2) (since C++11)
(constexpr since C++20)template<classForwardIt1,classForwardIt2>boolis_permutation(ForwardIt1first1,ForwardIt1last1,ForwardIt2first2,ForwardIt2last2); (3) (since C++14)
(constexpr since C++20)template<classForwardIt1,classForwardIt2,classBinaryPredicate>boolis_permutation(ForwardIt1first1,ForwardIt1last1,ForwardIt2first2,ForwardIt2last2,BinaryPredicatep); (4) (since C++14)
(constexpr since C++20)Checks whether [first1, last1) is a
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
, the program is ill-formed.
If the comparison function is not an
, the behavior is undefined.
Parameters
first1, last1 - the pair of iterators defining the first
of elements to compare first2, last2 - the pair of iterators defining the second
of elements to compare 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:
boolpred(constType1&a,constType2&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
(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.
Type requirements -ForwardIt1, ForwardIt2 must meet the requirements of
. Return value
true if the range [first1, last1) is a permutation of the range [first2, last2), false otherwise.
Complexity
Given N as std::distance(first1,last1):
1) Exactly N comparisons using operator== if the two ranges are equal, otherwise O(N2
) comparisons in the worst case.
2) Exactly N applications of the predicate p if the two ranges are equal, otherwise O(N2
) applications in the worst case.
3,4) If ForwardIt1 and ForwardIt2 are both
, and last1-first1!=last2-first2 is true, no comparison will be made.
Otherwise:
3) Exactly N comparisons using operator== if the two ranges are equal, otherwise O(N2
) comparisons in the worst case.
4) Exactly N applications of the predicate p if the two ranges are equal, otherwise O(N2
) applications in the worst case.
Possible implementation
template<classForwardIt1,classForwardIt2>boolis_permutation(ForwardIt1first,ForwardIt1last,ForwardIt2d_first){// skip common prefixstd::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){ForwardIt2d_last=std::next(d_first,std::distance(first,last));for(ForwardIt1i=first;i!=last;++i){if(i!=std::find(first,i,*i))continue;// this *i has been checkedautom=std::count(d_first,d_last,*i);if(m==0||std::count(i,last,*i)!=m)returnfalse;}}returntrue;}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.
Example
Run this code
#include<algorithm>#include<iostream>template<typenameOs,typenameV>Os&operator<<(Os&os,constV&v){os<<"{ ";for(constauto&e:v)os<<e<<' ';returnos<<'}';}intmain(){staticconstexprautov1={1,2,3,4,5};staticconstexprautov2={3,5,4,1,2};staticconstexprautov3={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 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
imposes an equivalence relation
(concept)
(C++20)
determines if a sequence is a permutation of another sequence
(algorithm function object)