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 lower_bound (a type of binary search) takes a range of iterators, and must declare a local variable whose type is the iterators' distance type. It uses distance type, and an auxiliary function, so that it can declare that variable. [3] Note: this is a simplified example. The actual algorithm lower_bound can operate on a range of Random Access Iterators or a range of Forward Iterators. It uses both distance_type and iterator_category.
[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.