|
| |
|
| Category: iterators | | Component type: function |
Prototype
Distance_type is overloaded; it is in fact five different functions.
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*);
Description
Distance_type is an iterator_tags function: it is used to determine the distance type associated with an iterator. An InputIterator, ForwardIterator, BidirectionalIterator, or RandomAccessIterator [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.
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.
Definition
Defined in the standard header iterator, and in the nonstandard backward-compatibility header iterator.h. This function is no longer part of the C++ standard, although it was present in early drafts of the standard. It is retained in this implementation for backward compatibility.
Requirements on types
The argument of distance_type must be an InputIterator, ForwardIterator, BidirectionalIterator, or RandomAccessIterator. [1]
Preconditions
None. Distance_type's argument is even permitted to be a singular iterator.
Complexity
At most amortized constant time. In many cases, a compiler should be able to optimize away distance_type entirely.
Example
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 RandomAccessIterator or a range of ForwardIterator. It uses both distance_type and iterator_category.
Notes
[1] Note that distance_type is not defined for OutputIterator or for trivial. 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.
See also
The iterator_tags overview, iterator_traits, iterator_category, value_type, output_iterator_tag, input_iterator_tag, forward_iterator_tag, bidirectional_iterator_tag, random_access_iterator_tag
