Standard Template Library Programmer's Guide

• T*

• vector::iterator

• vector::const_iterator

• deque::iterator

• deque::const_iterator

[1] "Equivalent to" merely means that i += n yields the same iterator as if i had been incremented (decremented) n times. It does not mean that this is how operator+= should be implemented; in fact, this is not a permissible implementation. It is guaranteed that i += n is amortized constant time, regardless of the magnitude of n . [5]

[2] One minor syntactic oddity: in C, if p is a pointer and n is an int, then p[n] and n[p] are equivalent. This equivalence is not guaranteed, however, for Random Access Iterators: only i[n] need be supported. This isn't a terribly important restriction, though, since the equivalence of p[n] and n[p] has essentially no application except for obfuscated C contests.

[3] The precondition defined in LessThan Comparable is that i and j be in the domain of operator< . Essentially, then, this is a definition of that domain: it is the set of pairs of iterators such that one iterator is reachable from the other.

[4] All of the other comparison operators have the same domain and are defined in terms of operator< , so they have exactly the same semantics as described in LessThan Comparable.

[5] This complexity guarantee is in fact the only reason why Random Access Iterator exists as a distinct concept. Every operation in iterator arithmetic can be defined for Bidirectional Iterators; in fact, that is exactly what the algorithms advance and distance do. The distinction is simply that the Bidirectional Iterator implementations are linear time, while Random Access Iterators are required to support random access to elements in amortized constant time. This has major implications for the sorts of algorithms that can sensibly be written using the two types of iterators.

LessThan Comparable, Trivial Iterator, Bidirectional Iterator, Iterator overview

Category: iterators

Component type: overview

Iterator tag functions are a method for accessing information that is associated with iterators. Specifically, an iterator type must, as discussed in the Input Iterator requirements, have an associated distance type and value type . [1] It is sometimes important for an algorithm parameterized by an iterator type to be able to determine the distance type and value type. Iterator tags also allow algorithms to determine an iterator's category, so that they can take different actions depending on whether an iterator is an Input Iterator, Output Iterator, Forward Iterator, Bidirectional Iterator, or Random Access Iterator.

Note that the iterator tag functions distance_type , value_type , and iterator_category are an older method of accessing the type information associated with iterators: they were defined in the original STL. The draft C++ standard, however, defines a different and more convenient mechanism: iterator_traits . Both mechanisms are supported [2], for reasons of backwards compatibility, but the older mechanism will eventually be removed.

The basic idea of the iterator tag functions, and of iterator_traits , is quite simple: iterators have associated type information, and there must be a way to access that information. Specifically, iterator tag functions and iterator_traits are used to determine an iterator's value type, distance type, and iterator category.

An iterator's category is the most specific concept that it is a model of: Input Iterator, Output Iterator, Forward Iterator, Bidirectional Iterator, or Random Access Iterator. This information is expressed in the C++ type system by defining five category tag types, input_iterator_tag , output_iterator_tag , forward_iterator_tag , bidirectional_iterator_tag , and random_access_iterator_tag , each of which corresponds to one of those concepts. [3]

The function iterator_category takes a single argument, an iterator, and returns the tag corresponding to that iterator's category. That is, it returns a random_access_iterator_tag if its argument is a pointer, a bidirectional_iterator_tag if its argument is a list::iterator , and so on. Iterator_traits provides the same information in a slightly different way: if I is an iterator, then iterator_traits::iterator_category is a nested typedef : it is one of the five category tag types.

An iterator's value type is the type of object that is returned when the iterator is dereferenced. (See the discussion in the Input Iterator requirements.) Ideally, one might want value_type to take a single argument, an iterator, and return the iterator's value type. Unfortunately, that's impossible: a function must return an object, and types aren't objects. Instead, value_type returns the value (T*)0 , where T is the argument's value type. The iterator_traits class, however, does not have this restriction: iterator_traits::value_type is a type, not a value. It is a nested typedef , and it can be used in declarations of variables, as an function's argument type or return type, and in any other ways that C++ types can be used.

(Note that the function value_type need not be defined for Output Iterators, since an Output Iterator need not have a value type. Similarly, iterator_traits::value_type is typically defined as void when I is an output iterator)

An iterator's distance type , or difference type (the terms are synonymous) is the type that is used to represent the distance between two iterators. (See the discussion in the Input Iterator requirements.) The function distance_type returns this information in the same form that value_type does: its argument is an iterator, and it returns the value (Distance*)0 , where Distance is the iterator's distance type. Similarly, iterator_traits::difference_type is I 's distance type.

Just as with value_type , the function distance_type need not be defined for Output Iterators, and, if I is an Output Iterator, iterator_traits::difference_type may be defined as void . An Output Iterator need not have a distance type.

The functions iterator_category , value_type , and distance_type must be provided for every type of iterator. (Except, as noted above, that value_type and distance_type need not be provided for Output Iterators.) In principle, this is simply a matter of overloading: anyone who defines a new iterator type must define those three functions for it. In practice, there's a slightly more convenient method. The STL defines five base classes, output_iterator , input_iterator , forward_iterator , bidirectional_iterator , and random_access_iterator . The functions iterator_category , value_type , and distance_type are defined for those base classes. The effect, then, is that if you are defining a new type of iterator you can simply derive it from one of those base classes, and the iterator tag functions will automatically be defined correctly. These base classes contain no member functions or member variables, so deriving from one of them ought not to incur any overhead.