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-17

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.