<iterator>

The <iterator> header declares classes and templates for defining and using iterators. (See Chapter 10.) Iterators are especially important when using the standard algorithms in <algorithm>.

An iterator gives a program access to the contents of a container or other sequence, such as an I/O stream. You can think of an iterator as an abstraction of a pointer; the syntax for using iterators resembles that of pointers. Conceptually, an iterator points to a single element in a container or sequence and can be advanced to the next element with the ++ (increment) operator. The unary * (dereference) operator returns the element that the iterator points to. Iterators (except for output iterators) can be compared: two iterators are equal if they point to the same position in the same sequence, or if they both point to one position past the end of the same sequence.

There are five categories of iterators:

Input iterators

Permit one pass to read a sequence. The increment operator advances to the next element, but there is no decrement operator. The dereference operator does not return an lvalue, so you can read elements but not modify them.

Output iterators

Permit one pass to write a sequence. The increment operator advances to the next element, but there is no decrement operator. You can dereference an element only to assign a value to it. You cannot compare output iterators.

Forward iterators

Are like a combination of an input and an output iterator. You can use a forward iterator anywhere an input iterator is required or where an output iterator is required. A forward iterator, as its name implies, permits unidirectional access to a sequence. You can refer to a single element and modify it multiple times before advancing the iterator.

Bidirectional iterators

Are like forward iterators but also support the decrement operator (--) to move the iterator backward by one position.

Random access iterators

Are like bidirectional iterators but also support the [] (subscript) operator to access any index in the sequence. Also, you can add or subtract an integer to move a random access iterator by more than one position at a time. Subtracting two random access iterators yields an integer distance between them. Thus, a random access iterator is most like a conventional pointer, and, in fact, a pointer can be used as a random access iterator.

An input, forward, bidirectional, or random access iterator can be a const_iterator. Dereferencing a const_iterator yields a constant (an rvalue or a const lvalue). Chapter 10 discusses const_iterators in more depth.

An iterator can point to any element in a sequence or to one position past the end. You cannot dereference an iterator that points to one past the end, but you can compare it with other iterators (provided it is not an output iterator) or, if it is a bidirectional or random access iterator, decrease its position so it points to a valid element of the sequence.

Iterators are often used in ranges. A range has two iterators: a starting point and an ending point. The end iterator typically points to one position past the last element in the range. Thus, a range is often written using the mathematical notation of [first, last), in which the square bracket means first is included in the range, and the parenthesis means last is excluded from the range.

Like ordinary pointers, iterators can be uninitialized or otherwise have invalid values, such as x.begin( ) - 1, in which x is any container. It is your responsibility to ensure that you dereference only valid iterators, that you don't let iterators run past their valid end-points, and so on.

To create your own iterator class, see the iterator class template.