11 Algorithms library [algorithms]

11.3 Non-modifying sequence operations [alg.nonmodifying]

11.3.12 Is permutation [alg.is_permutation]

template <ForwardIterator I1, Sentinel<I1> S1, ForwardIterator I2, Sentinel<I2> S2, class Pred = equal_to<>, class Proj1 = identity, class Proj2 = identity> requires IndirectlyComparable<I1, I2, Pred, Proj1, Proj2> bool is_permutation(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = Pred{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{}); template <ForwardRange Rng1, ForwardRange Rng2, class Pred = equal_to<>, class Proj1 = identity, class Proj2 = identity> requires IndirectlyComparable<iterator_t<Rng1>, iterator_t<Rng2>, Pred, Proj1, Proj2> bool is_permutation(Rng1&& rng1, Rng2&& rng2, Pred pred = Pred{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});

1

Returns: If last1 - first1 != last2 - first2, return false. Otherwise return true if there exists a permutation of the elements in the range [first2,first2 + (last1 - first1)), beginning with I2 begin, such that equal(first1, last1, begin, pred, proj1, proj2) returns true ; otherwise, returns false.

2

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

  • (2.1)

    SizedSentinel<S1, I1> is satisfied, and

  • (2.2)

    SizedSentinel<S2, I2> is satisfied, and

  • (2.3)

    last1 - first1 != last2 - first2.

Otherwise, exactly last1 - first1 applications of the corresponding predicate and projections if equal(first1, last1, first2, last2, pred, proj1, proj2) would return true; otherwise, at worst Ο(N2), where N has the value last1 - first1.