Iterators

In an earlier section when the STL was introduced, it was said that the STL library was separated into three major template constructs: containers, algorithms and iterators. This section looks at iterators more in-depth. Iterators are sometimes called: "smart pointers".

By being a smart pointer is meant the following: traditionally a pointer is used in C++ to move from one place in memory to another in order to access and to change data. We do this by incrementing and decrementing the pointer and thereby going from one place in memory to the next. This works okay for pointers that are accessing continuous memory but what about STL containers and the fact that some of these constructs are not stored in continuous memory. Further as we insert and remove elements from the middle of some containers, a traditional pointer would loose the correct reference to the elements and would no longer be able to move freely from one element to another. As a result, we need "smart pointers" i.e. iterators.

To accomplish these tasks, the developers of the STL have created the iterators as a family of template classes. The class user creates explicit iterators by defining them to be objects of a class as was done in an example above. Implicit iterators are created by connecting a container with an algorithm as was done when we used begin( ) and end( ) in some of the examples above.

Since the containers in the STL are dissimilar, the iterators used for the different containers are different. There are three major types of iterators: forward, bi-directional and random access. On the iterators of each of the three types, the dereference operator: * can be used. Using this operator, it is possible to both read and write to the elements of a container using an iterator.

However, the forward iterators may be used to only move forward through the container using the ++( ) operator. It may not be used to move backward through the container nor may it be used to access an arbitrary element in the middle of the container.

The bi-directional iterator may be used to move both forward and backward through the container by using the ++( ) and the --( ) operators but again it can not be used to access an arbitrary element in the container.

The random access iterator can be used to not only move both forward and backward through the container but it can also be used to access any arbitrary element.

In addition to the three types of iterators discussed above, there are also two specialized types of iterators. These are called the input iterators and the output iterators. These two types of iterators may be used to access an input device and an output device respectively. That is, input iterators would access either cin or a file for input but not for output and an output iterator would access either cout or a file but only for output.

One of the major differences between these two types of iterators is that the input/output iterators may not be stored for future use.

The following table summarizes the operators on the iterators:

Open table as spreadsheet

Iterator	Step Forward using the ++ ( ) operator	Step Backward using the --( ) operator	Random Access using the [ ] operator	Read using the *( ) operator	Write using the *( ) operater
random access iterator	*	*	*	*	*
bi-directional iterator	*	*		*	*
forward iterator	*			*	*
output iterator	*				*
input iterator	*			*

The following table summarizes which STL container works with which iterator:

Open table as spreadsheet

Iterator	vector	list	deque	set	multiset	map	multimap
random access iterator	*		*
bidirectional iterator	*	*	*	*	*	*	*
forward iterator	*	*	*	*	*	*	*
output iterator	*	*	*	*	*	*	*
input iterator	*	*	*	*	*	*	*

An iterator may be used in two ways: (1) as output of a member function or (2) by a definition like the following:

 list<short> list1; list<short>::iterator iterator1; iterator1 = list1.begin(); 

When iterator1 is defined as in the above statement, it is made a bi-directional iterator because that is the only type of iterator that can be defined on a list in this manner. If we use a similar definition for a vector or a deque, then the iterator that is defined is a random access iterator. These iterators are instances of the iterator template class for the specific container. Each of these instances for the specific container are themselves derived from the general iterator template class but modified for the specific container.

The following table shows the relationship between these iterator types and some of the algorithms (a more detailed discussion of these relationships are beyond these lecture notes):

Open table as spreadsheet

Iterator	find()	count()	copy()	unique()	sort()	reverse()	merge()
random access iterator					*
bi-directional iterator						*
forward iterator				*
output iterator			*				*
input iterator	*	*	*				*

For an example using iterators see iterator1.cpp.

In addition to iterators discussed in this lecture, STL has a header file: <iterators> which contain additional iterators than those discussed here. Some of these iterators can be used to better handle I/O.