|
| |
|
| Category: iterators | | Component type: type |
Description
As described in the Iterators, 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 typedefs; 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 recently. Both the old iterator_tags mechanism and the new iterator_traits mechanism are currently supported [1], but the old iterator tag functions are no longer part of the standard C++ library and they will eventually be removed.
Example
This generic function returns the last element in a non-empty range. Note that there is no way to define a function with this interface in terms of the old value_type function, because the function's return type must be declared to be the iterator's value type.
template <class InputIterator>
iterator_traits<InputIterator>::value_type
last_value(InputIterator first, InputIterator last) {
iterator_traits<InputIterator>::value_type result = *first;
for (++first; first != last; ++first)
result = *first;
return result;
}
(Note: this is an example of how to use iterator_traits; it is not an example of good code. There are better ways of finding the last element in a range of BidirectionalIterator, or even ForwardIterator.)
Definition
Defined in the standard header iterator, and in the nonstandard backward-compatibility header iterator.h.
Template parameters
| Parameter | Description | Default |
Iterator | The iterator type whose associated types are being accessed. | |
Model of
DefaultConstructible, Assignable
Type requirements
Public base classes
None.
Members
None, except for nested types.
| Member | Description |
iterator_category | One of the types input_iterator_tag, output_iterator_tag, forward_iterator_tag, bidirectional_iterator_tag, or random_access_iterator_tag. An iterator's category is the most specific iterator concept that it is a model of. |
value_type | Iterator's value type, as defined in the trivial requirements. |
difference_type | Iterator's distance type, as defined in the InputIterator requirements. |
pointer | Iterator's pointer type: a pointer to its value type. |
reference | Iterator's reference type: a reference to its value type. |
Notes
[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 old iterator tag functions iterator_category, distance_type, and value_type. This is one reason that those functions have not yet been removed.
See also
The Iterators, iterator_tags, input_iterator_tag, output_iterator_tag, forward_iterator_tag, bidirectional_iterator_tag, random_access_iterator_tag, input_iterator, output_iterator, forward_iterator, bidirectional_iterator, random_access_iterator
