Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Does std::distance interate over its range?

Reply
Thread Tools

Does std::distance interate over its range?

 
 
Alan Johnson
Guest
Posts: n/a
 
      11-30-2006
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.

--
Alan Johnson

 
Reply With Quote
 
 
 
 
JE
Guest
Posts: n/a
 
      11-30-2006

> Alan Johnson wrote:

<snip>
> 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

 
Reply With Quote
 
 
 
 
Alan Johnson
Guest
Posts: n/a
 
      11-30-2006

JE wrote:
> > Alan Johnson wrote:

> <snip>
> > 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.


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.

--
Alan Johnson

 
Reply With Quote
 
Nate Barney
Guest
Posts: n/a
 
      11-30-2006
Alan Johnson wrote:
> 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
 
Reply With Quote
 
Salt_Peter
Guest
Posts: n/a
 
      11-30-2006

Alan Johnson wrote:
> 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.

 
Reply With Quote
 
Alan Johnson
Guest
Posts: n/a
 
      11-30-2006
Salt_Peter wrote:
> > 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


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.

--
Alan Johnson

 
Reply With Quote
 
JE
Guest
Posts: n/a
 
      11-30-2006
<snip>
> > > Alan Johnson wrote:

> 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

 
Reply With Quote
 
JE
Guest
Posts: n/a
 
      11-30-2006

Alan Johnson wrote:
> Salt_Peter wrote:
> > > 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

>
> 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.
--
JE

 
Reply With Quote
 
Alan Johnson
Guest
Posts: n/a
 
      11-30-2006
JE wrote:
> 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.

--
Alan Johnson

 
Reply With Quote
 
Noah Roberts
Guest
Posts: n/a
 
      12-01-2006

Nate Barney wrote:

> I believe that #1 is correct.


That is also my guess.

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Its a bird, its a plane, its.. um, an Attribute based System? thunk Ruby 0 04-01-2010 10:25 PM
Its a bird, its a plane, no ummm, its a Ruide thunk Ruby 1 03-30-2010 11:10 AM
VOIP over VPN over TCP over WAP over 3G Theo Markettos UK VOIP 2 02-14-2008 03:27 PM
How to interate map free2cric@yahoo.com C++ 1 05-16-2005 12:43 PM
How to interate over DIVs? brett Javascript 2 02-04-2005 06:49 PM



Advertisments