Title
ranges::distance() cannot be used on a move-only iterator with a sized sentinel
Status
ready
Section
[range.iter.op.distance]
Submitter
Patrick Palka

Created on 2020-02-07.00:00:00 last changed 3 months ago

Messages

Date: 2021-06-23.14:16:45

Proposed resolution:

This wording is relative to N4885.

  1. Modify [iterator.synopsis], header <iterator> synopsis, as indicated:

    […]
    
    namespace std {
      […]
      // [range.iter.ops], range iterator operations
      namespace ranges {
        […]
        // [range.iter.op.distance], ranges::distance
        template<input_or_output_iterator I, sentinel_for<I> S>
          requires (!sized_sentinel_for<S, I>)
            constexpr iter_difference_t<I> distance(I first, S last);
        template<input_or_output_iterator I, sized_sentinel_for<I> S>
          constexpr iter_difference_t<I> distance(const I& first, const S& last);
        template<range R>
          constexpr range_difference_t<R> distance(R&& r);
        […]
      }
      […]
    }
    
  2. Modify [range.iter.op.distance] as indicated:

    template<input_or_output_iterator I, sentinel_for<I> S>
      requires (!sized_sentinel_for<S, I>)
        constexpr iter_difference_t<I> ranges::distance(I first, S last);
    

    -1- Preconditions: [first, last) denotes a range, or [last, first) denotes a range and S and I model same_as<S, I> && sized_sentinel_for<S, I>.

    -2- Effects: If S and I model sized_sentinel_for<S, I>, returns (last - first); otherwise, returns the Returns: The number of increments needed to get from first to last.

    template<input_or_output_iterator I, sized_sentinel_for<I> S>
      constexpr iter_difference_t<I> ranges::distance(const I& first, const S& last);
    

    -?- Effects: Equivalent to return last - first;

Date: 2021-06-15.00:00:00

[ 2021-06-23; Reflector poll ]

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

Date: 2021-05-19.00:00:00

[ 2021-05-19 Tim updates wording ]

The wording below removes the explicit precondition on the sized_sentinel_for overload of distance, relying instead on the semantic requirements of that concept and the "Effects: Equivalent to:" word of power. This also removes the potentially surprising inconsistency that given a non-empty std::vector<int> v, ranges::distance(v.begin(), v.cend()) is well-defined but ranges::distance(v.cend(), v.begin()) is currently undefined.

Date: 2020-05-15.00:00:00

[ 2020-05-28; LEWG issue reviewing ]

LEWG issue processing voted to accept the direction of 3392. Status change to Open.

Accept the direction of LWG3392

SF F N A SA
14 6 0 0 0

Previous resolution [SUPERSEDED]:

  1. Modify [iterator.synopsis], header <iterator> synopsis, as indicated:

    #include <concepts>
    
    namespace std {
      […]
      // [range.iter.ops], range iterator operations
      namespace ranges {
        […]
        // [range.iter.op.distance], ranges::distance
        template<input_or_output_iterator I, sentinel_for<I> S>
          requires (!sized_sentinel_for<S, I>)
            constexpr iter_difference_t<I> distance(I first, S last);
        template<input_or_output_iterator I, sized_sentinel_for<I> S>
          constexpr iter_difference_t<I> distance(const I& first, const S& last);
        template<range R>
          constexpr range_difference_t<R> distance(R&& r);
        […]
      }
      […]
    }
    
  2. Modify [range.iter.op.distance] as indicated:

    template<input_or_output_iterator I, sentinel_for<I> S>
      requires (!sized_sentinel_for<S, I>)
        constexpr iter_difference_t<I> ranges::distance(I first, S last);
    

    -1- Preconditions: [first, last) denotes a range, or [last, first) denotes a range and S and I model same_as<S, I> && sized_sentinel_for<S, I>.

    -2- Effects: If S and I model sized_sentinel_for<S, I>, returns (last - first); otherwise, rReturns the number of increments needed to get from first to last.

    template<input_or_output_iterator I, sized_sentinel_for<I> S>
      constexpr iter_difference_t<I> ranges::distance(const I& first, const S& last);
    

    -?- Preconditions: S and I model sized_sentinel_for<S, I> and either:

    1. (?.1) — [first, last) denotes a range, or

    2. (?.2) — [last, first) denotes a range and S and I model same_as<S, I>.

    -? Effects: Returns (last - first);

Date: 2020-02-10.19:13:13

[ 2020-02 Prioritized as P3 and LEWG Monday morning in Prague ]

Date: 2020-02-08.18:33:08

One cannot use ranges::distance(I, S) to compute the distance between a move-only counted_iterator and the default_sentinel. In other words, the following is invalid

// iter is a counted_iterator with an move-only underlying iterator
ranges::distance(iter, default_sentinel);

and yet

(default_sentinel - iter);

is valid. The first example is invalid because ranges::distance() takes its first argument by value so when invoking it with an iterator lvalue argument the iterator must be copyable, which a move-only iterator is not. The second example is valid because counted_iterator::operator-() takes its iterator argument by const reference, so it doesn't require copyability of the counted_iterator.

This incongruency poses an inconvenience in generic code which uses ranges::distance() to efficiently compute the distance between two iterators or between an iterator-sentinel pair. Although it's a bit of an edge case, it would be good if ranges::distance() does the right thing when the iterator is a move-only lvalue with a sized sentinel.

If this is worth fixing, one solution might be to define a separate overload of ranges::distance(I, S) that takes its arguments by const reference, as follows.

History
Date User Action Args
2021-06-23 14:16:45adminsetmessages: + msg11954
2021-06-23 14:16:45adminsetstatus: open -> ready
2021-05-19 12:02:15adminsetmessages: + msg11820
2020-05-31 09:54:47adminsetmessages: + msg11320
2020-05-31 09:54:47adminsetstatus: lewg -> open
2020-02-10 19:13:13adminsetmessages: + msg11027
2020-02-10 19:13:13adminsetstatus: new -> lewg
2020-02-08 16:01:02adminsetmessages: + msg11002
2020-02-07 00:00:00admincreate