Standard Template Library Programmer's Guide

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

In practice, ensuring that iterator_category is defined requires essentially no work at all. It is already defined for pointers, and for the base classes input_iterator , output_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 iterator_category (along with distance_type 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 iterator_category 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 [3], but eventually iterator_category 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 iterator_category must be an iterator.

None. Iterator_category '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 iterator_category entirely.

Reverse can be implemented for either Bidirectional Iterators or for Random Access Iterators, but the algorithm for Random Access Iterators is more efficient. Consequently, reverse uses iterator_category to select whichever algorithm is appropriate for the iterator type. This dispatch takes place at compile time, and should not incur any run-time penalty.

template

void __reverse(BidirectionalIterator first, BidirectionalIterator last, bidirectional_iterator_tag ) {

while (true)

if (first == last || first == --last) return;

else iter_swap(first++, last);

}

template

void __reverse(RandomAccessIterator first, RandomAccessIterator last, random_access_iterator_tag ) {

while (first < last) iter_swap(first++, --last);

}

template

inline void reverse(BidirectionalIterator first, BidirectionalIterator last) {

__reverse(first, last, iterator_category(first));

}

[1] The STL also defines one other concept, Trivial Iterator. This concept is introduced only for conceptual clarity, however, in order to separate the axioms related to an object that refers to another object from those related to iteration over a range. In fact, the STL does not define any types that are Trivial Iterators. Although built-in C pointers may be Trivial Iterators, the C type system does not allow a distinction between pointers that are Trivial Iterators and pointers that are Random Access Iterators into C arrays. Consequently, there is no Trivial Iterator category tag.

[2] Any type that is a model of Forward Iterator is also a model of Input Iterator, any type that is a model of Bidirectional Iterator is also a model of Forward Iterator, and any type that is a model of Random Access Iterator is also a model of Bidirectional Iterator. Iterator_category must return a tag representing the most specific concept that its argument is a model of. If its argument is a vector::iterator , for example, then it must return random_access_iterator_tag .

[3] 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.

The Iterator Tags overview, iterator_traits , distance_type , value_type , output_iterator_tag , input_iterator_tag , forward_iterator_tag , bidirectional_iterator_tag , random_access_iterator_tag

Category: iterators

Component type: function

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

template

inline Distance* distance_type(const input_iterator &);

template

inline Distance* distance_type(const forward_iterator &);

template

inline Distance* distance_type(const bidirectional_iterator &);

template

inline Distance* distance_type(const random_access_iterator &);

template 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.