|
Iterator definitions
In C++, an iterator is any object that, pointing to some element in a range of elements (such as an array or a container), has the ability to iterate through the elements of that range using a set of operators (at least, the increment (++) and dereference (*) operators).
The most obvious form of iterator is a pointer: A pointer can point to elements in an array, and can iterate through them using the increment operator (++). But other forms of iterators exist. For example, each container type (such as a vector) has a specific iterator type designed to iterate through its elements in an efficient way.
Notice that while a pointer is a form of iterator, not all iterators have the same functionality a pointer has; To distinguish between the requirements an iterator shall have for a specific algorithm, five different iterator categories exist:
Iterator categories
Iterators are classified in five categories depending on the functionality they implement:
In this graph, each iterator category implements the functionalities of all categories to its right:
Input and output iterators are the most limited types of iterators, specialized in performing only sequential input or ouput operations.
Forward iterators have all the functionality of input and output iterators, although they are limited to one direction in which to iterate through a range.
Bidirectional iterators can be iterated through in both directions. All standard containers support at least bidirectional iterators types.
Random access iterators implement all the functionalities of bidirectional iterators, plus, they have the ability to access ranges non-sequentially: offsets can be directly applied to these iterators without iterating through all the elements in between. This provides these iterators with the same functionality as standard pointers (pointers are iterators of this category).
The characteristics of each category of iterators are:
| category | characteristic | valid expressions |
|---|
| all categories | Can be copied and copy-constructed | X b(a);
b = a; |
| Can be incremented | ++a
a++
*a++ |
| Random Access | Bidirectional | Forward | Input | Accepts equality/inequality comparisons | a == b
a != b |
| Can be dereferenced as an rvalue | *a
a->m |
| Output | Can be dereferenced to be the left side of an assignment operation | *a = t
*a++ = t |
| Can be default-constructed | X a;
X() |
| Can be decremented | --a
a--
*a-- |
| Supports arithmetic operators + and - | a + n
n + a
n - a
a - b |
| Supports inequality comparisons (<, >, <= and >=) between iterators | a < b
a > b
a <= b
a >= b |
| Supports compound assignment operations += and -= | a += n
a -= n |
| Supports offset dereference operator ([]) | a[n] |
Where X is an iterator type, a and b are objects of this iterator type, t is an object of the type pointed by the iterator type, and n is an integer value.
Random access iterators have all characteristics. Bidirectional iterators have a subset of random access iterators's. Forward iterators have a subset of bidirectional iterators's. And input and output have each their own subset of forward iterator's.
Base
| iterator | Iterator base class (class template) |
Functions
Iterator operations:
| advance | Advance iterator (function template) |
| distance | Return distance between iterators (function template) |
Inserters:
| back_inserter | Construct a back insert iterator (function template) |
| inserter | Construct an insert iterator (function template) |
Predefined iterators
Inserter iterators
Input/Output iterators
|
