std::is_permutation

From Cppreference

Jump to: navigation, search
Defined in header <algorithm>

template< class ForwardIterator1, class ForwardIterator2 >

bool is_permutation( ForwardIterator1 first, ForwardIterator1 last,

                     ForwardIterator2 d_first );
(1) (C++11 feature)
template< class ForwardIterator1, class ForwardIterator2, class BinaryPredicate >

bool is_permutation( ForwardIterator1 first, ForwardIterator1 last,

                     ForwardIterator2 d_first, BinaryPredicate p );
(2) (C++11 feature)

Returns true if there exists a permutation of the elements in the range [first1, last1) that makes that range equal to the range beginning at d_first. The first version uses operator== for equality, the second version uses the binary predicate p

Contents

[edit] Parameters

first, last - the range of elements to compare
d_first - the beginning of the second range 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:

bool pred(const Type1 &a, const Type2 &b);

The signature does not need to have const &, but the function must not modify the objects passed to it.
The types Type1 and Type2 must be such that objects of types ForwardIterator1 and ForwardIterator2 can be dereferenced and then implicitly converted to Type1 and Type2 respectively.

[edit] Return value

true if the range [first, last) is a permutation of the range beginning at d_first.

[edit] Complexity

At most O(N2) applications of the predicate, or exactly N if the sequences are already equal, where N=std::distance(first, last).

[edit] Equivalent function

[edit] Example

#include <algorithm>
#include <vector>
#include <iostream>
int main()
{
    std::vector<int> v1{1,2,3,4,5};
    std::vector<int> v2{3,5,4,1,2};
    std::cout << "3,5,4,1,2 is a permutation of 1,2,3,4,5? "
              << std::boolalpha
              << std::is_permutation(v1.begin(), v1.end(), v2.begin()) << '\n';
 
    std::vector<int> v3{3,5,4,1,1};
    std::cout << "3,5,4,1,1 is a permutation of 1,2,3,4,5? "
              << std::boolalpha
              << 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

next_permutation
generates the next greater lexicographic permutation of a range of elements
(function template)
prev_permutation
generates the next smaller lexicographic permutation of a range of elements
(function template)