Standard Template Library Programmer's Guide

• 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

Functions

• iterator_category
• value_type
• distance_type

Notes

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

See also

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

iterator_traits<Iterator>

Category: iterators

Component type: type

Description

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<I>::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.

The library contains two definitions of iterator_traits: a fully generic one, and a specialization that is used whenever the template argument is a pointer type [1]. The fully generic version defines iterator_traits<I>::value_type as a synonym for I::value_type, iterator_traits<I>::difference_type as a synonym for I::difference_type, and so on. Since pointers don't have nested types, iterator_traits<T*> has a different definition.

The implementation of iterator_traits is actually simpler than this discussion.

template <class Iterator>
struct iterator_traits {
 typedef typename Iterator::iterator_category iterator_category;
 typedef typename Iterator::value_type value_type;
 typedef typename Iterator::difference_type difference_type;
 typedef typename Iterator::pointer pointer;
 typedef typename Iterator::reference reference;
};
template <class T>
struct iterator_traits<T*> {
 typedef random_access_iterator_tag iterator_category;
 typedef T value_type;
 typedef ptrdiff_t difference_type;
 typedef T* pointer;
 typedef T& reference;
};

If you are defining a new iterator type I, then you must ensure that iterator_traits<I> is defined properly. There are two ways to do this. First, you can define your iterator so that it has nested types I::value_type, I::difference_type, and so on. Second, you can explicitly specialize iterator_traits for your type. The first way is almost always more convenient, however, especially since you can easily ensure that your iterator has the appropriate nested types just by inheriting from one of the base classes input_iterator, output_iterator, forward_iterator, bidirectional_iterator, or random_access_iterator.

Note that iterator_traits is new; it was added to the draft C++ standard relatively