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
- 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
All three categories also provide for
- 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.
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
- testing for equality, with ==, and inequality,
- dereferencing, which means obtaining the data object at the
position the iterator refers to, expressed with *.
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