distance function template — Counts elements between two iterators
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 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
specialize_distance(InputIter first, InputIter last,
random_access_iterator_tag)
{
return last - first;
}
template<typename InputIter>
typename iterator_traits<InputIter>::difference_typedistance(InputIter first, InputIter last)
{
return specialize_distance(first, last,
iterator_traits<InputIter>::iterator_category( ));
}
}