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.