Does std::distance interate over its range?

Discussion in 'C++' started by Alan Johnson, Nov 30, 2006.

  1. Alan Johnson

    Alan Johnson Guest

    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
     
    Alan Johnson, Nov 30, 2006
    #1
    1. Advertising

  2. Alan Johnson

    JE Guest


    > 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
     
    JE, Nov 30, 2006
    #2
    1. Advertising

  3. Alan Johnson

    Alan Johnson Guest

    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
     
    Alan Johnson, Nov 30, 2006
    #3
  4. Alan Johnson

    Nate Barney Guest

    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
     
    Nate Barney, Nov 30, 2006
    #4
  5. Alan Johnson

    Salt_Peter Guest

    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.
     
    Salt_Peter, Nov 30, 2006
    #5
  6. Alan Johnson

    Alan Johnson Guest

    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::eek: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
     
    Alan Johnson, Nov 30, 2006
    #6
  7. Alan Johnson

    JE Guest

    <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
     
    JE, Nov 30, 2006
    #7
  8. Alan Johnson

    JE Guest

    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::eek: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
     
    JE, Nov 30, 2006
    #8
  9. Alan Johnson

    Alan Johnson Guest

    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
     
    Alan Johnson, Nov 30, 2006
    #9
  10. Alan Johnson

    Noah Roberts Guest

    Nate Barney wrote:

    > I believe that #1 is correct.


    That is also my guess.
     
    Noah Roberts, Dec 1, 2006
    #10
  11. Alan Johnson

    JE Guest

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


    ;) 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.

    --
    Best regards, JE
     
    JE, Dec 1, 2006
    #11
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    1
    Views:
    327
    Winbatch
    May 16, 2005
  2. thunk
    Replies:
    1
    Views:
    315
    thunk
    Mar 30, 2010
  3. thunk
    Replies:
    0
    Views:
    489
    thunk
    Apr 1, 2010
  4. thunk
    Replies:
    14
    Views:
    627
    thunk
    Apr 3, 2010
  5. brett

    How to interate over DIVs?

    brett, Feb 4, 2005, in forum: Javascript
    Replies:
    2
    Views:
    102
    brett
    Feb 4, 2005
Loading...

Share This Page