940. std::distance

Section: 24.4.3 [iterator.operations] Status: Resolved Submitter: Thomas Opened: 2008-12-14 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 Resolved status.

Discussion:

Addresses UK 270

Regarding the std::distance - function, 24.4.3 [iterator.operations] p.4 says:

Returns the number of increments or decrements needed to get from first to last.

This sentence is completely silent about the sign of the return value. 24.4.3 [iterator.operations] p.1 gives more information about the underlying operations, but again no inferences about the sign can be made. Strictly speaking, that is taking that sentence literally, I think this sentence even implies a positive return value in all cases, as the number of increments or decrements is clearly a ratio scale variable, with a natural zero bound.

Practically speaking, my implementations did what common sense and knowledge based on pointer arithmetic forecasts, namely a positive sign for increments (that is, going from first to last by operator++), and a negative sign for decrements (going from first to last by operator--).

Here are my two questions:

First, is that paragraph supposed to be interpreted in the way what I called 'common sense', that is negative sign for decrements ? I am fairly sure that's the supposed behavior, but a double-check here in this group can't hurt.

Second, is the present wording (2003 standard version - no idea about the draft for the upcoming standard) worth an edit to make it a bit more sensible, to mention the sign of the return value explicitly ?

[ Daniel adds: ]

My first thought was that resolution 204 would already cover the issue report, but it seems that current normative wording is in contradiction to that resolution:

Referring to N2798, 24.4.3 [iterator.operations]/ p.4 says:

Effects: Returns the number of increments or decrements needed to get from first to last.

IMO the part " or decrements" is in contradiction to p. 5 which says

Requires: last shall be reachable from first.

because "reachable" is defined in 24.3.4 [iterator.concepts]/7 as

An iterator j is called reachable from an iterator i if and only if there is a finite sequence of applications of the expression ++i that makes i == j.[..]

Here is wording that would be consistent with this definition of "reachable":

Change 24.4.3 [iterator.operations] p4 as follows:

Effects: Returns the number of increments or decrements needed to get from first to last.

Thomas adds more discussion and an alternative view point here.

[ Summit: ]

The proposed wording below was verbally agreed to. Howard provided.

[ Batavia (2009-05): ]

Pete reports that a recent similar change has been made for the advance() function.

We agree with the proposed resolution. Move to Tentatively Ready.

[ 2009-07 Frankfurt ]

Moved from Tentatively Ready to Open only because the wording needs to be tweaked for concepts removal.

[ 2009-07 Frankfurt: ]

Leave Open pending arrival of a post-Concepts WD.

[ 2009-10-14 Daniel provided de-conceptified wording. ]

[ 2009-10 Santa Cruz: ]

Move to Ready, replacing the Effects clause in the proposed wording with "If InputIterator meets the requirements of random access iterator then returns (last - first), otherwise returns the number of increments needed to get from first to list.".

[ 2010 Pittsburgh: ]

Moved to NAD EditorialResolved. Rationale added below.

Rationale:

Solved by N3066.

Proposed resolution:

  1. Change 24.3.5.7 [random.access.iterators], Table 105 as indicated [This change is not essential but it simplifies the specification] for the row with expression "b - a" and the column Operational semantics: 

    (a < b) ? distance(a,b)
: -distance(b,a)

  2. Change 24.4.3 [iterator.operations]/4+5 as indicated: 

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

    4 Effects: If InputIterator meets the requirements of random access iterator then returns (last - first), otherwise Rreturns the number of increments or decrements needed to get from first to last.

    5 Requires: If InputIterator meets the requirements of random access iterator then last shall be reachable from first or first shall be reachable from last, otherwise last shall be reachable from first.