Standard Template Library Programmer's Guide

(Again, note that base classes are provided solely for the convenience of people who define iterators. If you define a class Iter that is a new kind of Bidirectional Iterator, you do not have to derive it from the base class bidirectional_iterator . You do, however, have to make sure that iterator_category , value_type , and distance_type are defined correctly for arguments of type Iter , and deriving Iter from bidirectional_iterator is usually the most convenient way to do that.)

This example uses the value_type iterator tag function in order to declare a temporary variable of an iterator's value type. Note the use of an auxiliary function, __iter_swap . This is a very common idiom: most uses of iterator tags involve auxiliary functions.

template

inline void __iter_swap(ForwardIterator1 a, ForwardIterator2 b, ValueType*) {

ValueType tmp = *a;

*a = *b;

*b = tmp;

}

template

inline void iter_swap(ForwardIterator1 a, ForwardIterator2 b) {

__iter_swap(a, b, value_type(a));

}

This example does exactly the same thing, using iterator_traits instead. Note how much simpler it is: the auxiliary function is no longer required.

template

inline void iter_swap(ForwardIterator1 a, ForwardIterator2 b) {

iterator_traits ::value_type tmp = *a;

*a = *b;

*b = tmp;

}

This example uses the iterator_category iterator tag function: reverse can be implemented for either Bidirectional Iterator s or for Random Access Iterators , but the algorithm for Random Access Iterators is more efficient. Consequently, reverse is written to dispatch on the iterator category. 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));

}

In this case, iterator_traits would not be different in any substantive way: it would still be necessary to use auxiliary functions to dispatch on the iterator category. The only difference is changing the top-level function to

template

inline void reverse(BidirectionalIterator first, BidirectionalIterator last) {

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

}

• output_iterator

• input_iterator

• forward_iterator

• bidirectional_iterator

• random_access_iterator

• output_iterator_tag

• input_iterator_tag

• forward_iterator_tag

• bidirectional_iterator_tag

• random_access_iterator_tag

• iterator_traits

• iterator_category

• value_type

• distance_type

[1] Output Iterators have neither a distance type nor a value type; in many ways, in fact, Output Iterators aren't really iterators. Output iterators do not have a value type, because it is impossible to obtain a value from an output iterator but only to write a value through it. They do not have a distance type, similarly, because it is impossible to find the distance from one output iterator to another. Finding a distance requires a comparison for equality, and output iterators do not support operator== .

[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 to use the older iterator tag functions.

[3] Note that Trivial Iterator does not appear in this list. The Trivial Iterator concept is introduced solely for conceptual clarity; the STL does not actually define any Trivial Iterator types, so there is no need for a Trivial Iterator tag. There is, in fact, a strong reason not to define one: the C++ type system does not provide any way to distinguish between a pointer that is being used as a trivial iterator (that is, a pointer to an object that isn't part of an array) and a pointer that is being used as a Random Access Iterator into an array.

Input Iterator, Output Iterator, Forward Iterator, Bidirectional Iterator, Random Access Iterator, iterator_traits , Iterator Overview

Category: iterators

Component type: type

As described in the Iterator Overview, one of the most important facts about iterators is that they have associated types. An iterator type, for example, has an associated value type : the type of object that the iterator points to. It also has an associated distance type , or difference type , a signed integral type that can be used to represent the distance between two iterators.

(Pointers, for example, are iterators; the value type of int* is int . Its distance type is ptrdiff_t , because, if p1 and p2 are pointers, the expression p1 – p2 has type ptrdiff_t .)

Generic algorithms often need to have access to these associated types; an algorithm that takes a range of iterators, for example, might need to declare a temporary variable whose type is the iterators' value type. The class iterator_traits is a mechanism that allows such declarations.

The most obvious way to allow declarations of that sort would be to require that all iterators declare nested types; an iterator I 's value type, for example, would be I::value_type . That can't possibly work, though. Pointers are iterators, and pointers aren't classes; if I is (say) int* , then it's impossible to define I::value_type to be int . Instead, I 's value type is written iterator_traits::value_type . iterator_traits is a template class that contains nothing but nested typedef s; in addition to value_type , iterator_traits defines the nested types iterator_category , difference_type , pointer , and reference .