Standard Template Library Programmer's Guide

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.

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.

The argument of distance_type must be an Input Iterator, Forward Iterator, Bidirectional Iterator, or Random Access Iterator. [1]

None. Distance_type 's argument is even permitted to be a singular iterator.

At most amortized constant time. In many cases, a compiler should be able to optimize away distance_type entirely.

template

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

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 .

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

Category: iterators

Component type: function

Value_type is overloaded; it is in fact five different functions.

template

inline T* value_type(const input_iterator&);

template

inline T* value_type(const forward_iterator&);

template

inline T* value_type(const bidirectional_iterator&);

template

inline T* value_type(const random_access_iterator&);

template

inline T* value_type(const T*);

Value_type is an iterator tag function: it is used to determine the value type associated with an iterator. An iterator's value type is the type of object returned when the iterator is dereferenced; Output Iterators do not have value types (Output Iterators may only be used for storing values, not for accessing values), but Input Iterators, Forward Iterators, Bidirectional Iterators, and Random Access Iterators do. [1]

In some cases, such as an algorithm that must declare a local variable that holds a value returned from dereferencing an iterator, it is necessary to find out an iterator's value type. Accordingly, value_type(Iter) returns (T*)0 , where T is Iter 's value type.

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

In practice, ensuring that value_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 value_type (along with iterator_category and distance_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 value_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 value_type will be removed.

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.

The argument of value_type must be an Input Iterator, Forward Iterator, Bidirectional Iterator, or Random Access Iterator. [1]

None. Value_type 's argument is even permitted to be a singular iterator.

At most amortized constant time. In many cases, a compiler should be able to optimize away value_type entirely.