![]() |
![]() |
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*);
Distance_type is an iterator tag function: it is used to determine the distance type associated with an iterator. An Input Iterator, Forward Iterator, Bidirectional Iterator, or Random Access Iterator [1] must have associated with it some signed integral type that is used to represent the distance between two iterators of that type. In some cases (such as an algorithm that must declare a local variable that represents the size of a range), it is necessary to find out an iterator's distance type. Accordingly, distance_type(Iter) returns (Distance*) 0, where Distance is Iter's distance type.
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.
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. [2] 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] 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. You can't just declare a variable by writing something like distance_type(Iter) dist;, since distance_type(Iter) is a value rather than a type. An alternative technique called iterator traits, which is described in the Iterator Tags overview, will render the use of auxiliary functions unnecessary in most cases. Iterator traits, however, rely on a C++ feature known as partial specialization. Partial specialization is part of the C++ standard, but no compilers currently (as of September 1996) support it. Once compilers that support partial specialization become available, future releases of the STL will use iterator traits.