425,710 Members | 1,613 Online
Need help? Post your question and get tips & solutions from a community of 425,710 IT Pros & Developers. It's quick & easy.

# Does std::distance interate over its range?

 P: n/a 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 Nov 30 '06 #1
10 Replies

 P: n/a 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 Nov 30 '06 #2

 P: n/a JE wrote: 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. 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 Nov 30 '06 #3

 P: n/a 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 Nov 30 '06 #4

 P: n/a 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::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. Nov 30 '06 #5

 P: n/a 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::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 #include #include int main() { std::istream_iterator

 P: n/a 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 Nov 30 '06 #7

 P: n/a 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::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 #include #include int main() { std::istream_iterator