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

Section: 26.6.13 [alg.equal], 26.6.14 [alg.is.permutation] Status: C++23 Submitter: Tim Song Opened: 2021-06-03 Last modified: 2023-11-22

Priority: Not Prioritized

View all other issues in [alg.equal].

View all issues with C++23 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 26.6.13 [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 (24.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 (24.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 26.6.14 [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.