Iterator Categories of the Standard Template Library

A key factor in the design of STL is the consistent use of iterators, which generalize C++ pointers, as intermediaries between algorithms and containers. A precise classification of iterators into five categories is the basis for determining which algorithms can be used with which containers, and is the main guide to extension of the library to include new algorithms that work with STL containers, or new containers to which many STL generic algorithms can be applied.

The scheme used to determine which algorithms and containers can be combined consists of three parts:

iterators are classified into five categories: forward, bidirectional, random access, input, and output.
the description of container classes includes the category of the iterator types they provide
the description of generic algorithms includes the iterator categories they work with

Iterator categories

Forward iterators provide for one-directional traversal of a sequence, expressed with ++.
Bidirectional iterators provide for traversal in both directions, expressed with ++ and --.
Random access iterators provide for bidirectional traversal, plus
- bidirectional "long jumps", expressed with r += n and r -= n (where r is a random access iterator and n is an integer)
- addition and subtraction of an integer, expressed with r + n and r - n
- iterator subtraction, expresses as r - s (where s is another random access iterator), producing an integer value.
- comparisons, expressed as r < s, r > s, r <=; s, r >=; s, producing bool values.
All three categories also provide for
- testing for equality, with ==, and inequality, with !=
- dereferencing, which means obtaining the data object at the position the iterator refers to, expressed with *.
In addition to the requirements about how these operations are expressed, there are laws that they must obey. Without going into the full statement of the laws here, let us note that
Any C++ pointer type, T*, obeys all the laws of the random access iterator category.
There are two other categories, input iterators and output iterators, which are like forward iterators except not all properties of forward iterators are guaranteed.
It is not guaranteed that an input or output iterator can be saved and used to start advancing from the position it holds a second time
It is not guaranteed to be possible to assign to the object obtained by applying * to an input iterator
It is not guaranteed to be possible to read from the object obtained by applying * to an output iterator
It is not guaranteed to be possible to test two output iterators for equality or inequality (== and != may not be defined)

Category of iterators provided by each STL container type

vector<T>::iterator and deque<T>::iterator are random access iterator types
list<T>::iterator is a bidirectional iterator type
All the iterator types of the associative containers are bidirectional

musser@procyon.cs.rpi.edu