C++ In a Nutshell

Name

distance function template — Counts elements between two iterators

Synopsis

template<typename InputIterator>
  typename iterator_traits<InputIterator>::difference_type
    distance(InputIterator first, InputIterator last);

The distance function returns the number of elements between first and last. The function is specialized for random access iterators to use the - operator; for other input iterators, the function applies the ++ operator to first until first == last. The behavior is undefined if first and last refer to different containers or if last points to an element earlier than first.

Example 13-19 shows a simple implementation of the distance function. The first specialized implementation works for any iterator (except output iterators, which do not support comparison with the != operator). The second one works only with random access iterators and uses the subtraction operator to compute the distance in constant time. The compiler picks the more specialized function when it can, so random access iterators can compute distances in constant time, compared to linear time for other iterators.

Example

Example 13-19. A simple implementation of distance

namespace std { template<typename InputIter> typename iterator_traits<InputIter>::difference_type specialize_distance(InputIter first, InputIter last, ...) { typename iterator_traits<InputIter>::difference_type n; for (n = 0; first != last; ++first) ++n; return n; } template<typename InputIter> typename iterator_traits<InputIter>::difference_type ...