Section: 24.4.3 [iterator.operations] Status: NAD Submitter: Rintala Matti Opened: 2000-01-28 Last modified: 2016-01-28
Priority: Not Prioritized
View other active issues in [iterator.operations].
View all other issues in [iterator.operations].
View all issues with NAD status.
Discussion:
Section 24.3.4 describes the function distance(first, last) (where first and last are iterators) which calculates "the number of increments or decrements needed to get from 'first' to 'last'".
The function should work for forward, bidirectional and random access iterators, and there is a requirement 24.3.4.5 which states that "'last' must be reachable from 'first'".
With random access iterators the function is easy to implement as "last - first".
With forward iterators it's clear that 'first' must point to a place before 'last', because otherwise 'last' would not be reachable from 'first'.
But what about bidirectional iterators? There 'last' is reachable from 'first' with the -- operator even if 'last' points to an earlier position than 'first'. However, I cannot see how the distance() function could be implemented if the implementation does not know which of the iterators points to an earlier position (you cannot use ++ or -- on either iterator if you don't know which direction is the "safe way to travel").
The paragraph 24.3.4.1 states that "for ... bidirectional iterators they use ++ to provide linear time implementations". However, the ++ operator is not mentioned in the reachability requirement. Furthermore 24.3.4.4 explicitly mentions that distance() returns the number of increments _or decrements_, suggesting that it could return a negative number also for bidirectional iterators when 'last' points to a position before 'first'.
Is a further requirement is needed to state that for forward and bidirectional iterators "'last' must be reachable from 'first' using the ++ operator". Maybe this requirement might also apply to random access iterators so that distance() would work the same way for every iterator category?
Rationale:
"Reachable" is defined in the standard in 24.3.4 [iterator.concepts] paragraph 6. The definition is only in terms of operator++(). The LWG sees no defect in the standard.