Category: iterators |
Component type: function |

template <class T, class Distance> inline Distance* distance_type(const input_iterator<T, Distance>&); template <class T, class Distance> inline Distance* distance_type(const forward_iterator<T, Distance>&); template <class T, class Distance> inline Distance* distance_type(const bidirectional_iterator<T, Distance>&); template <class T, class Distance> inline Distance* distance_type(const random_access_iterator<T, Distance>&); template <class T> inline ptrdiff_t* distance_type(const T*);

Although `distance_type` looks like a single function whose
return type depends on its argument type, in reality it is a set
of functions; the name `distance_type` is overloaded.
The function `distance_type` must be overloaded for every iterator type [1].

In practice, ensuring that `distance_type` is defined requires
essentially no work at all. It is already defined for pointers, and
for the base classes `input_iterator`,
`forward_iterator`, `bidirectional_iterator`, and
`random_access_iterator`. If you are implementing a new type of
forward iterator, for example, you can simply derive it from the base
class `forward_iterator`; this means that `distance_type`
(along with `iterator_category` and `value_type`) will
automatically be defined for your iterator. These base classes are
empty: they contain no member functions or member variables, but
only type information. Using them should therefore incur no overhead.

Note that, while the function `distance_type` was present in the
original STL, it is no longer present in the most recent draft C++
standard: it has been replaced by the `iterator_traits` class.
At present both mechanisms are supported [2], but eventually
`distance_type` will be removed.

template <class RandomAccessIterator, class LessThanComparable, class Distance> RandomAccessIterator __lower_bound(RandomAccessIterator first, RandomAccessIterator last, const LessThanComparable& value, Distance*) Distance len = last - first; Distance half; RandomAccessIterator middle; while (len > 0) { half = len / 2; middle = first + half; if (*middle < value) { first = middle + 1; len = len - half - 1; } else len = half; } return first; } template <class RandomAccessIterator, class LessThanComparable> inline RandomAccessIterator lower_bound(RandomAccessIterator first, RandomAccessIterator last, const LessThanComparable& value) { return __lower_bound(first, last, value, distance_type(first)); }The algorithm

[1]
Note that `distance_type` is not defined for Output Iterators
or for Trivial Iterators. There is no meaningful definition of a
distance for either of those concepts, so there is no need for a
distance type.

[2]
The `iterator_traits` class
relies on a C++ feature known as *partial specialization*. Many of
today's compilers don't implement the complete standard; in
particular, many compilers do not support partial specialization. If
your compiler does not support partial specialization, then you will
not be able to use `iterator_traits`, and you will have to
continue using the functions `iterator_category`, `distance_type`,
and `value_type`. This is one reason that those functions have
not yet been removed.

[3]
This use of an auxiliary function is an extremely common idiom:
`distance_type` is almost always used with auxiliary functions, simply
because it returns type information in a form that is hard to use in
any other way. This is one of the reasons that `distance_type`
is so much less convenient than `iterator_traits`.

Copyright © 1999 Silicon Graphics, Inc. All Rights Reserved. TrademarkInformation webmaster@www.sgi.com