This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of WP status.

### 3560. `ranges::equal` and `ranges::is_permutation` should short-circuit for `sized_ranges`

Section: 25.6.11 [alg.equal], 25.6.12 [alg.is.permutation] Status: WP Submitter: Tim Song Opened: 2021-06-03 Last modified: 2021-10-14

Priority: Not Prioritized

View all other issues in [alg.equal].

View all issues with WP status.

Discussion:

`ranges::equal` and `ranges::is_permutation` are currently only required to short-circuit on different sizes if the iterator and sentinel of the two ranges pairwise model `sized_sentinel_for`. They should also short-circuit if the ranges are sized.

[2021-06-23; Reflector poll]

Set status to Tentatively Ready after five votes in favour during reflector poll.

[2021-10-14 Approved at October 2021 virtual plenary. Status changed: Voting → WP.]

Proposed resolution:

This wording is relative to N4885.

1. Modify 25.6.11 [alg.equal] as indicated:

   >     template<class InputIterator1, class InputIterator2>
   >       constexpr bool equal(InputIterator1 first1, InputIterator1 last1,
   >                            InputIterator2 first2);
   >     […]
   >     template<class InputIterator1, class InputIterator2,
   >              class BinaryPredicate>
   >       constexpr bool equal(InputIterator1 first1, InputIterator1 last1,
   >                            InputIterator2 first2, InputIterator2 last2,
   >                            BinaryPredicate pred);
   >     […]
   >     template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
   >              class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
   >       requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
   >       constexpr bool ranges::equal(I1 first1, S1 last1, I2 first2, S2 last2,
   >                                    Pred pred = {},
   >                                    Proj1 proj1 = {}, Proj2 proj2 = {});
   >     template<input_range R1, input_range R2, class Pred = ranges::equal_to,
   >              class Proj1 = identity, class Proj2 = identity>
   >       requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
   >       constexpr bool ranges::equal(R1&& r1, R2&& r2, Pred pred = {},
   >                                    Proj1 proj1 = {}, Proj2 proj2 = {});

   > > […]

   > > -3- Complexity: If the types of `first1`, `last1`, `first2`, and `last2`:

   > > 1. (3.1) — the types of `first1`, `last1`, `first2`, and `last2` meet the Cpp17RandomAccessIterator requirements (23.3.5.7 [random.access.iterators]) and `last1 - first1 != last2 - first2` for the overloads in namespace `std`;

   > > 2. (3.2) — the types of `first1`, `last1`, `first2`, and `last2` pairwise model `sized_sentinel_for` (23.3.4.8 [iterator.concept.sizedsentinel]) and `last1 - first1 != last2 - first2` for the first overloads in namespace `ranges`,

   > > 3. (3.3) — `R1` and `R2` each model `sized_range` and `ranges::distance(r1) != ranges::distance(r2)` for the second overload in namespace `ranges`,

   > > and `last1 - first1 != last2 - first2`, then no applications of the corresponding predicate and each projection; otherwise, […]

2. Modify 25.6.12 [alg.is.permutation] as indicated:

   >     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 = {});

   > > […]

   > > -7- Complexity: No applications of the corresponding predicate and projections if:

   > > 1. (7.1) — for the first overload,

   > >    1. (7.1.1) — `S1` and `I1` model `sized_sentinel_for<S1, I1>`,

   > >    2. (7.1.2) — `S2` and `I2` model `sized_sentinel_for<S2, I2>`, and

   > >    3. (7.1.3) — `last1 - first1 != last2 - first2`.;

   > > 2. (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 𝒪(`N2`), where `N` has the value `last1 - first1`.