Iterators are in fact not a single concept, but six concepts that form a hierarchy: some of them define only a very restricted set of operations, while others define additional functionality. The five concepts that are actually used by algorithms are Input Iterator, Output Iterator, Forward Iterator, Bidirectional Iterator, and Random Access Iterator. A sixth concept, Trivial Iterator, is introduced only to clarify the definitions of the other iterator concepts.
The most restricted sorts of iterators are Input Iterators and Output Iterators, both of which permit "single pass" algorithms but do not necessarily support "multi-pass" algorithms. Input iterators only guarantee read access: it is possible to dereference an Input Iterator to obtain the value it points to, but not it is not necessarily possible to assign a new value through an input iterator. Similarly, Output Iterators only guarantee write access: it is possible to assign a value through an Output Iterator, but not necessarily possible to refer to that value.
Forward Iterators are a refinement of Input Iterators and Output Iterators: they support the Input Iterator and Output Iterator operations and also provide additional functionality. In particular, it is possible to use "multi-pass" algorithms with Forward Iterators. A Forward Iterator may be constant, in which case it is possible to access the object it points to but not to to assign a new value through it, or mutable , in which case it is possible to do both.
Bidirectional Iterators, like Forward Iterators, allow multi-pass algorithms. As the name suggests, they are different in that they support motion in both directions: a Bidirectional Iterator may be incremented to obtain the next element or decremented to obtain the previous element. A Forward Iterator, by contrast, is only required to support forward motion. An iterator used to traverse a singly linked list, for example, would be a Forward Iterator , while an iterator used to traverse a doubly linked list would be a Bidirectional Iterator.
Finally, Random Access Iterators allow the operations of pointer arithmetic: addition of arbitrary offsets, subscripting, subtraction of one iterator from another to find a distance, and so on.
Most algorithms are expressed not in terms of a single iterator but in terms of a range of iterators ; the notation [first, last) refers to all of the iterators from first up to, but not including, last.  Note that a range may be empty, i.e.first and last may be the same iterator. Note also that if there are n iterators in a range, then the notation [first, last) represents n+1 positions. This is crucial: algorithms that operate on n things frequently require n+1 positions. Linear search, for example (find) must be able to return some value to indicate that the search was unsuccessful.
Sometimes it is important to be able to infer some properties of an iterator: the type of object that is returned when it is dereferenced, for example. There are two different mechanisms to support this sort of inferrence: an older mechanism called Iterator Tags, and a newer mechanism called iterator_traits .