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

4055. §[iterator.operations] std::distance is missing a precondition

Section: 24.4.3 [iterator.operations] Status: New Submitter: Jan Schultke Opened: 2024-02-25 Last modified: 2024-03-12

Priority: 4

View other active issues in [iterator.operations].

View all other issues in [iterator.operations].

View all issues with New status.

Discussion:

std::distance for random access iterators is defined in terms of (last - first) (24.4.3 [iterator.operations] p5) for Cpp17RandomAccessIterators.

However, this subtraction is not guaranteed to be well-defined (24.3.5.7 [random.access.iterators], Table [tab:randomaccessiterator]):

Table 91: Cpp17RandomAccessIterator requirements (in addition to Cpp17BidirectionalIterator) [tab:randomaccessiterator]
Expression Return type Operational semantics Assertion/note
pre-/post-condition
[…]
b - a difference_type return n; Preconditions: there exists a
value n of type difference_type
such that a + n == b.
b == a + (b - a).

For example, pointer subtraction is undefined if the result isn't representable as std::ptrdiff_t, and user-defined types with random access iterators aren't required to have a difference which is always representable by difference_type.

std::distance(&a, &b) can't be well-defined when &b - &a is not, so std::distance is missing a precondition.

[2024-03-12; Reflector poll]

Set priority to 4 after reflector poll.

The proposed change is wrong, the new wording only associates with the second condition, but should also apply when "last is reachable from first".

Previous resolution [SUPERSEDED]

This wording is relative to N4971.

  1. Modify 24.4.3 [iterator.operations] as indicated:

    template<class InputIterator>
  constexpr typename iterator_traits<InputIterator>::difference_type
    distance(InputIterator first, InputIterator last);

    -4-Preconditions: last is reachable from first, or InputIterator meets the Cpp17RandomAccessIterator requirements, and first is reachable from last , and typename iterator_traits<InputIterator>::difference_type can represent the result of this function call.

    -5- Effects: If InputIterator meets the Cpp17RandomAccessIterator requirements, returns (last - first); otherwise, increments first until last is reached and returns the number of increments.

[2024-03-12; Jonathan provides improved wording]

Proposed resolution:

This wording is relative to N4971.

  1. Modify 24.4.3 [iterator.operations] as indicated:

    template<class InputIterator>
  constexpr typename iterator_traits<InputIterator>::difference_type
    distance(InputIterator first, InputIterator last);

    -4-Preconditions: last is reachable from first, or InputIterator meets the Cpp17RandomAccessIterator requirements and first is reachable from last. The return type can represent the result.

    -5- Effects: If InputIterator meets the Cpp17RandomAccessIterator requirements, returns (last - first); otherwise, increments first until last is reached and returns the number of increments.