4.2 Iterators

"Iterators are a generalization of pointers that allow a programmer to work with different data structures (containers) in a uniform manner", [2]. From the short survey in section 4.1.1 we know that iterators are objects that have operator* returning a value of a type called the value type of the iterator.

Since iterators are a generalization of pointers it is assumed that every template function that takes iterators as arguments also works with regular pointers.

There are five categories of iterators. Iterators differ in the operations defined on them. Each iterator is designed to satisfy a well-defined set of requirements. These requirements define what operations can be applied to the iterator. According to these requirements the iterators can be assigned to the five categories. Iterator categories can be arranged from left to right to express that the iterator category on the left satisfies the requirements of all the iterator categories on the right (and so could be called more powerful).

Figure 7: Iterator categories

This arrangement means that a template function wich expects for example a bidirectional iterator can be provided with a random access iterator, but never with a forward iterator. Imagine an algorithm that needs random access to fulfil his task, but is provided with a method that only allows to pass through the elements successively from one to the next. It simply won't work.

Iterators that point past the last element of a range are called past-the-end iterators. Iterators for which the operator* is defined are called dereferenceable. It is never assumed that past-the-end iterators are dereferenceable. An iterator value (i.e. an iterator of a specific iterator type) that isn't associated with a container is called singular (iterator) value. Pointers can also be singular. After the declaration of an uninitialized pointer with

int* x;

x is assumed to be singular. Dereferenceable and past-the-end iterators are always non-singular.

All the categories of iterators have only those functions defined that are realizeable for that category in (amortized) constant time. This underlines the efficiency concern of the library.

Because random access in a linked list doesn't take constant time (but linear time), random access iterators cannot be used with lists. Only input/output iterators up to bidirectional iterators are valid for the use with the container list. The following table shows the iterators that can be used with the containers vector, list and deque (of course all iterators that satisfy the requirements of the listed iterators can be used as well):

Container     Iterator Category

vector        random access         
              iterators             

list          bidirectional         
              iterators             

deque         random access         
              iterators             

Table 5: Most powerful iterator categories that can be used with vector, list and deque

Iterators of these categories are returned when using the member functions begin or end or declaring an iterator with e.g. vector<int>::iterator i;

The iterator categories will be explained starting with the input iterators and output iterators.

Continue with section 4.2.1

Back to index