27 Algorithms library [algorithms]

27.6 Non-modifying sequence operations [alg.nonmodifying]

27.6.14 Is permutation [alg.is.permutation]

template<class ForwardIterator1, class ForwardIterator2>
  constexpr bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
                                ForwardIterator2 first2);
template<class ForwardIterator1, class ForwardIterator2,
         class BinaryPredicate>
  constexpr bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
                                ForwardIterator2 first2, BinaryPredicate pred);
template<class ForwardIterator1, class ForwardIterator2>
  constexpr bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
                                ForwardIterator2 first2, ForwardIterator2 last2);
template<class ForwardIterator1, class ForwardIterator2,
         class BinaryPredicate>
  constexpr bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
                                ForwardIterator2 first2, ForwardIterator2 last2,
                                BinaryPredicate pred);

Let last2 be first2 + (last1 - first1) for the overloads with no parameter named last2, and let pred be equal_to{} for the overloads with no parameter pred.

Mandates: ForwardIterator1 and ForwardIterator2 have the same value type.

Preconditions: The comparison function is an equivalence relation.

Returns: If last1 - first1 != last2 - first2, return false.

Otherwise return true if there exists a permutation of the elements in the range [first2, last2), beginning with ForwardIterator2 begin, such that equal(first1, last1, begin, pred) returns true; otherwise, returns false.

Complexity: No applications of the corresponding predicate if ForwardIterator1 and ForwardIterator2 meet the requirements of random access iterators and last1 - first1 != last2 - first2.

Otherwise, exactly last1 - first1 applications of the corresponding predicate if equal(first1, last1, first2, last2, pred) would return true; otherwise, at worst

O (N^{2})

, where N has the value last1 - first1.

🔗

template<forward_iterator I1, sentinel_for<I1> S1, forward_iterator I2,
         sentinel_for<I2> S2, class Proj1 = identity, class Proj2 = identity,
         indirect_equivalence_relation<projected<I1, Proj1>,
                                       projected<I2, Proj2>> Pred = ranges::equal_to>
  constexpr bool ranges::is_permutation(I1 first1, S1 last1, I2 first2, S2 last2,
                                        Pred pred = {},
                                        Proj1 proj1 = {}, Proj2 proj2 = {});
template<forward_range R1, forward_range R2,
         class Proj1 = identity, class Proj2 = identity,
         indirect_equivalence_relation<projected<iterator_t<R1>, Proj1>,
                                       projected<iterator_t<R2>, Proj2>> Pred = ranges::equal_to>
  constexpr bool ranges::is_permutation(R1&& r1, R2&& r2, Pred pred = {},
                                        Proj1 proj1 = {}, Proj2 proj2 = {});

Returns: If last1 - first1 != last2 - first2, return false.

Otherwise return true if there exists a permutation of the elements in the range [first2, last2), bounded by [pfirst, plast), such that ranges::equal(first1, last1, pfirst, plast, pred, proj1, proj2) returns true; otherwise, returns false.

Complexity: No applications of the corresponding predicate and projections if:

(7.1)
for the first overload,
- (7.1.1)
  S1 and I1 model sized_sentinel_for<S1, I1>,
- (7.1.2)
  S2 and I2 model sized_sentinel_for<S2, I2>, and
- (7.1.3)
  last1 - first1 != last2 - first2;
(7.2)
for the second overload, R1 and R2 each model sized_range, and ranges::distance(r1) != ranges::distance(r2).

Otherwise, exactly last1 - first1 applications of the corresponding predicate and projections if ranges::equal(first1, last1, first2, last2, pred, proj1, proj2) would return true; otherwise, at worst

O (N^{2})

, where N has the value last1 - first1.