Does std::distance interate over its range?

[Alan Johnson]

24.1.1.3 says about InputIterators:
Algorithms on input iterators should never attempt to pass through the
same iterator twice. They should be single pass algorithms.

In 24.3.4.4 summarizes the effects of std::distance as:
Effects: Returns the number of increments or decrements needed to get
from first to last.

The wording of the latter seems somewhat ambiguous. Does it mean that
it actually performs the necessary increments or decrements, or that it
determines (by some unspecified means) the necessary number, and
returns it?

One of the following must then be true:
1) We assume that it does perform the necessary increments, in which
case std::distance is useless when writing algorithms for
InputIterators. If you determine the distance, you can no longer use
the range for which the distance was determined.
2) We assume that it determines the distance without performing the
increments. I can't prove it rigorously, but I suspect that this
really isn't possible to implement.

Unless my suspicion in #2 is incorrect, it seems that std::distance
should only be defined for ForwardIterators. Either way, the wording
for 24.3.4.4 is insufficient.

 

[JE]

Alan Johnson wrote:

2) We assume that it determines the distance without performing the
increments. I can't prove it rigorously, but I suspect that this
really isn't possible to implement.

For random access iterators, you don't need to iterate to calculate
distance.
- -
JE

 

[Alan Johnson]

For random access iterators, you don't need to iterate to calculate
distance.

True, but that doesn't prove the possibility of implementing
std::distance without performing increments. You can specialize it for
random access iterators, but you still have to handle input iterators
(without any refinements) in some manner.

 

[Nate Barney]

24.1.1.3 says about InputIterators:
Algorithms on input iterators should never attempt to pass through the
same iterator twice. They should be single pass algorithms.

In 24.3.4.4 summarizes the effects of std::distance as:
Effects: Returns the number of increments or decrements needed to get
from first to last.

The wording of the latter seems somewhat ambiguous. Does it mean that
it actually performs the necessary increments or decrements, or that it
determines (by some unspecified means) the necessary number, and
returns it?

One of the following must then be true:
1) We assume that it does perform the necessary increments, in which
case std::distance is useless when writing algorithms for
InputIterators. If you determine the distance, you can no longer use
the range for which the distance was determined.
2) We assume that it determines the distance without performing the
increments. I can't prove it rigorously, but I suspect that this
really isn't possible to implement.

Unless my suspicion in #2 is incorrect, it seems that std::distance
should only be defined for ForwardIterators. Either way, the wording
for 24.3.4.4 is insufficient.

I believe that #1 is correct. However, that doesn't mean that
std::distance should only be defined for ForwardIterators. It may well
be the case that all one needs from an InputIterator range is the
distance between the two iterators, and std::distance can do that. If
you need the size of the range before you start doing something with the
elements, then you probably will have ForwardIterators anyway.

Nate

 

[Salt_Peter]

24.1.1.3 says about InputIterators:
Algorithms on input iterators should never attempt to pass through the
same iterator twice. They should be single pass algorithms.

Input iterators have read only access to the elements.
The best analogy i've found so far to explain forward iterators is a
keyboard's input (standard input).
It can only be read once an element at a time.

In 24.3.4.4 summarizes the effects of std::distance as:

So > Effects: Returns the number of increments or decrements needed to
get

from first to last.

The wording of the latter seems somewhat ambiguous. Does it mean that
it actually performs the necessary increments or decrements, or that it
determines (by some unspecified means) the necessary number, and
returns it?

The distance() function uses iter2 - iter1 to calculate distance for
*random* iterators. For non-random iterators, iter1 is incremented
until iter2 is reached and that count or Dist is returned based on an
iterator trait:
iterator_traits<InputIterator>::difference_type

So its saying that for distance(iter1, iter2)...
a) iter1 and iter2 must be from the same container (obviously).
b) If the iterators are *not* random iterators, iter2 must be reachable
from iter1 (think: direction). If iter2 is found before iter1 and the
iterators are input iterators, for example, the behaviour is undefined.

One of the following must then be true:
1) We assume that it does perform the necessary increments, in which
case std::distance is useless when writing algorithms for
InputIterators. If you determine the distance, you can no longer use
the range for which the distance was determined.
2) We assume that it determines the distance without performing the
increments. I can't prove it rigorously, but I suspect that this
really isn't possible to implement.

Unless my suspicion in #2 is incorrect, it seems that std::distance
should only be defined for ForwardIterators. Either way, the wording
for 24.3.4.4 is insufficient.

You can still use the distance returned from input iterators, although
distance() is slower on such containers. Its just telling you that the
way you calculate that distance has to be respected.
Consider using advance(input_iter&, dist) if you need to increment the
position of an input iterator.

I hope this is helpfull in some way.

 

[Alan Johnson]

The distance() function uses iter2 - iter1 to calculate distance for
*random* iterators. For non-random iterators, iter1 is incremented
until iter2 is reached and that count or Dist is returned based on an
iterator trait:
iterator_traits<InputIterator>::difference_type

I agree that this might be a possible implementation, depending on how
you interpret the standard, but I don't see where the standard requires
this implementation. In fact, that was sort of my point. One possible
interpretation is that this would NOT be a valid implementation.

Consider the following program:

#include <iostream>
#include <iterator>
#include <algorithm>

int main()
{
std::istream_iterator<char> begin(std::cin) ;
std::istream_iterator<char> end ;
std:stream_iterator<char> out(std::cout, "") ;

std::cout << "Distance: " << std::distance(begin, end) << std::endl
;
std::copy(begin, end, out) ;
std::cout << std::endl ;
}


What should it print when executed with the input "Hello, world!\n"?

Under one interpretation it should print:
Distance: 12
Hello,world!

Under another it is undefined behavior, because you are using a range
of input iterators more than once, which is forbidden by 24.1.1.3.

Probably it is impossible to implement std::distance such that the
first interpretation is possible, and the second indicates to me that
std::distance should not even be defined for anything less than a
forward iterator.

 

[JE]

True, but that doesn't prove the possibility of implementing
std::distance without performing increments. You can specialize it for
random access iterators, but you still have to handle input iterators
(without any refinements) in some manner.

If you look at the input iterator concept, it is possible to write a
distance algorithm in terms of a subset of the operations available in
that concept (increment, comparison, and copy). Anything that models
the concept of an input iterator provides enough of an interface to
write a distance algorithm. That doesn't say that it's efficient or
makes sense for everything that models an input iterator, but that the
_necessary operations_ are there for the distance algorithm.

 

[JE]

I agree that this might be a possible implementation, depending on how
you interpret the standard, but I don't see where the standard requires
this implementation. In fact, that was sort of my point. One possible
interpretation is that this would NOT be a valid implementation.

Consider the following program:

#include <iostream>
#include <iterator>
#include <algorithm>

int main()
{
std::istream_iterator<char> begin(std::cin) ;
std::istream_iterator<char> end ;
std:stream_iterator<char> out(std::cout, "") ;

std::cout << "Distance: " << std::distance(begin, end) << std::endl
;
std::copy(begin, end, out) ;
std::cout << std::endl ;
}


What should it print when executed with the input "Hello, world!\n"?

Under one interpretation it should print:
Distance: 12
Hello,world!

Under another it is undefined behavior, because you are using a range
of input iterators more than once, which is forbidden by 24.1.1.3.

Probably it is impossible to implement std::distance such that the
first interpretation is possible, and the second indicates to me that
std::distance should not even be defined for anything less than a
forward iterator.

You're confusing the restrictions imposed by the requirements of the
input iterator concept on the algorithm (distance, or your code) with
restrictions on types that model input iterator. You can only read an
input iterator _once_, and only traverse _once_. Your code traverses
_twice_, and requires more than just an input iterator. distance
algorithm only traverses _once_, and doesn't do any reading or
dereferencing at all.

 

[Alan Johnson]

You're confusing the restrictions imposed by the requirements of the
input iterator concept on the algorithm (distance, or your code) with
restrictions on types that model input iterator.

I don't think I've mentioned anything about restrictions on types. The
code sample I gave was mere an example, chosen because the type was an
input iterator (rather than a refinement thereof).

You can only read an input iterator _once_, and only traverse _once_.

We agree here. "Algorithms on input iterators should never attempt to
pass through the
same iterator twice. They should be single pass algorithms." I quoted
that from the standard in my original post.

I've reordered some of the rest of your statements so that I can
address them more clearly.

distance algorithm only traverses _once_, and doesn't do any reading or
dereferencing at all.

Show me where in the standard the implementation is required to
traverse the range. This is in fact the whole point of this thread.
I'm arguing that the standard is too ambiguous about that.

You probably assume that std::distance must traverse the given range
because you can't think of any other way to implement it. And neither
can I, but unless you can rigorously prove that there isn't another way
(and probably even if you can) then the standard should be more clear.

In my reading of the standard, the effects of std::distance are not
very well defined for (strict) input iterators.

Your code traverses _twice_, and requires more than just an input iterator.

This depends on whether you interpret the effects of std::distance as
traversing the range. I would argue that in the most literal reading
of the standard, my code only traverses the given range once.

 

[Noah Roberts]

I believe that #1 is correct.

That is also my guess.

 

[JE]

I don't think I've mentioned anything about restrictions on types. The
code sample I gave was mere an example, chosen because the type was an
input iterator (rather than a refinement thereof).


We agree here. "Algorithms on input iterators should never attempt to
pass through the
same iterator twice. They should be single pass algorithms." I quoted
that from the standard in my original post.

I've reordered some of the rest of your statements so that I can
address them more clearly.


Show me where in the standard the implementation is required to
traverse the range. This is in fact the whole point of this thread.
I'm arguing that the standard is too ambiguous about that.

You probably assume that std::distance must traverse the given range
because you can't think of any other way to implement it. And neither
can I, but unless you can rigorously prove that there isn't another way
(and probably even if you can) then the standard should be more clear.

In my reading of the standard, the effects of std::distance are not
very well defined for (strict) input iterators.


This depends on whether you interpret the effects of std::distance as
traversing the range. I would argue that in the most literal reading
of the standard, my code only traverses the given range once.

OK - I think I see where you're coming from.

If you use an algorithm for input iterators, there is no guarantee
that the algorithm has _not_ used iteration. Therefore, it behooves you
to pass in a refinement of input iterators that supports re-iteration,
if you intend to re-iterate.