Lesson 14 - Iterators
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 (with 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 kinds of iterators are possible. For example, each container type (such as a list) has a specific iterator type designed to iterate through its elements.
Categories
Iterators are classified into five categories depending on the features they implement:
Input and output iterators are the most limited types of iterators: they can perform sequential single-pass input or output operations.
Forward iterators have all the features of input iterators and (if they are not constant iterators) also the features of output iterators, although they are limited to one direction in which to iterate through a range (forward). All standard containers support at least forward iterator types.
Bidirectional iterators are like forward iterators but can also be iterated through backwards.
Random-access iterators implement all the features of bidirectional iterators, and also have the ability to access ranges non-sequentially: distant elements can be accessed directly by applying an offset value to an iterator without iterating through all the elements in between. These iterators have a similar feature to standard pointers (pointers are iterators of this category).
The properties of each iterator category are:
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.
Rationale
There are two rules for making container-based code general and efficient:
- Never pass containers into a function. Pass iterators instead.
- Never return containers. Return -- or pass -- iterators instead.
Generality
Suppose we wanted to define product() to multiply together the numbers in a container.
We can immediately reject any definition like this:
double product( vector<double> v ) ...
because it is
- not general; it only works for vectors
- inefficient; it copies the container
But we could define it like this:
template <typename Container>
double product( const Container& container )
{
Container::iterator i = container.begin();
double prod = 1;
while ( i != container.end() ) prod *= *i++;
return prod;
}
This definition seems general. It works for any STL container, e.g.,
vector<double> nums;
...
return product( nums );
Unfortunately, it will not work with regular arrays, e.g.,
double nums[] = { 1.2, 3.0, 3.5, 2.8 };
return product( nums );
since there are no begin() or end() funtions for regular C-style arrays. Furthermore, it does not let us calculate the product of a subrange of the container.
The following definition is clearly more general:
template <typename Iter>
double product( Iter start, Iter stop )
{
double prod = 1;
while ( start != stop ) prod *= *start++;
return prod;
}
This works fine with regular arrays:
double nums[] = { 1.2, 3.0, 3.5, 2.8 };
return product( nums, nums + 4 );
as well as with STL containers and subranges.
Recommendation
Prefer the pre-fix form for incrementing/decrementing (or just use std::advance) the iterator. This in general (as for regular loop counter variables) is more efficient since the compiler does not need to return an unnecessary instance of the previous value of the iterator.