Title
ranges::equal and ranges::is_permutation should short-circuit for sized_ranges
Status
c++23
Section
[alg.equal][alg.is.permutation]
Submitter
Tim Song

Created on 2021-06-03.00:00:00 last changed 4 months ago

Messages

Date: 2021-10-14.09:56:08

Proposed resolution:

This wording is relative to N4885.

  1. Modify [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 ([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 ([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 [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.

Date: 2021-10-14.00:00:00

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

Date: 2021-06-15.00:00:00

[ 2021-06-23; Reflector poll ]

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

Date: 2021-06-03.00:00:00

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.

History
Date User Action Args
2023-11-22 15:47:43adminsetstatus: wp -> c++23
2021-10-14 09:56:08adminsetmessages: + msg12126
2021-10-14 09:56:08adminsetstatus: voting -> wp
2021-09-29 12:57:28adminsetstatus: ready -> voting
2021-06-23 14:16:45adminsetmessages: + msg11961
2021-06-23 14:16:45adminsetstatus: new -> ready
2021-06-05 21:37:32adminsetmessages: + msg11868
2021-06-03 00:00:00admincreate