Iterators

Important principles:

·  Iterators can be used to move sequentially through containers

·  These iterators behave like pointers - in fact, think of iterators as generalised pointers

·  Iterator classes are typedef-ed in the container classes themselves 

·  A container's start and end (in fact, 'one past the end') are given by begin() and end() members;

·  There are different classes of iterator - input, output, forward, reverse, bidirectional, random access - which correspond to increasingly flexible usages.

Containers, by themselves, do not provide access to their elements. Instead, iterators are used to traverse the elements within a container. Iterators are very similar to smart pointers and have increment and dereferencing operations. By generalizing access to containers through iterators, the STL makes it possible to interact with containers in a uniform manner. Iterators are the glue that connects algorithms to containers.

Iterators are the cornerstone of the STL design and give the STL its most flexibility. Instead of developing algorithms for a specific container, they are developed for a specific iterator category. This strategy makes it possible to use the same algorithm with a variety of different containers.

Each category forms a set of requirements that must be met by concrete iterator types within that category. Requirements for a given iterator category are specified by a set of of valid expressions for iterators in that category as well as precise semantics describing their usage. In addition, iterators in the STL must satisfy complexity requirements. These requirements ensure that algorithms written in terms of iterators will work correctly and efficiently.

Iterators are classified into five categories: forward, bidirectional, random access, input, and output.  Iterators hierarchy:

• Random access iterator is the most powerful one. It can be used to store and retrieve values, provide for bidirectional traversal, and supports the following operations: ++, --, +, - .  It can also be indexed via the [ ] operator. A random access iterator is the type used by vector.
• Bidirectional iterator provides for traversal in both directions,  can store and retrieve values and supports ++ and --, but not + or -. Bidirectional iterators are used by list.
• Forward iterator provides for one-directional traversal of a sequence.  It can store and retrieve values and supports ++.
• Input iterator can obtain values but not alter them. It can move in a forward direction only and support  ++.
• Output iterator can store values, but not obtain them. It can move in a forward direction only and support ++.

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

Example:

We want to print the contents of an array using a pointer:

int v[10]; 

//... fill v;  

int* i = v;   

while (i != v + 10)    

	cout << *i++; 

The STL code for this is surprisingly similar:

vector<int> v;  

//... fill v   

vector<int>::iterator i = v.begin();  

while (i != v.end())      

	cout << *i++;