[ moderator's note: forwarded to C++ Committee for handling. -sdc ]

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?

------------ Matti Rintala ----------- bitti@cs.tut.fi ------------
"Well, the way I see it, logic is only a way of being ignorant
 by numbers." (from "Small Gods" by Terry Pratchett)


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Rintala Matti wrote:
>
> [ moderator's note: forwarded to C++ Committee for handling. -sdc ]
>
> 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'".
....
> But what about bidirectional iterators? There 'last' is reachable from
> 'first' with the -- operator even if 'last' points to an earlier

Section 24.1 p6: "An iterator j is called _reachable_ from an iterator
if and only if there is a finite sequence of applications of the
expression ++i that makes i == j."
Notice the assymetry of that definition. The -- operator doesn't make an
iterator reachable.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

James Kuyper <kuyper@wizard.net> writes:
> Rintala Matti wrote:
> > 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'".
>
> Section 24.1 p6: "An iterator j is called _reachable_ from an iterator
> if and only if there is a finite sequence of applications of the
> expression ++i that makes i == j."

Thanks, I didn't notice that paragraph.

But that means that even for random access iterators distance()
should only be called in cases where it returns a positive value.
So why does the standard say that it calculates "the number of
increments or decrements needed" if the reachability requirement makes
sure that 'first' points to a position before 'last' so that
decrements are never an option?

------------ Matti Rintala ----------- bitti@cs.tut.fi ------------
"Well, the way I see it, logic is only a way of being ignorant
 by numbers." (from "Small Gods" by Terry Pratchett)

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]