C++ Notes: STL Iterators - Introduction

An iterator is used to move thru the elements an STL container (vector, list, set, map, ...).

Each type of container has an underlying implementation (eg, vector or linked list) for which there is a "natural" way to get to the next element (incrementing a pointer for vectors, following the next or prev pointer for lists, ...). Iterators are defined within each of the container classes to work specifically with that type of container. An iterator may be as simple as a pointer, or may be defined as a class. Regardless of the implementation, the same operators are defined.

Why iterators are so useful

• Uniform access. Iterators can be used with all containers, and also with arrays. If you start with a vector, but later decide a list would be more efficient, iterator code will not have to change.
• Algorithms for all containers. The algorithms in the STL <algorithm> library work on iterators. This means that they operator on the standard containers.
• New containers can use existing algorithms. Not only do the library algorithms work with the STL containers, but they will work with any new data structures (containers) you define, if iterators are defined for the new container.
• New algorithms can use existing containers. When a new algorithm is written based on iterators, it applies to all existing containers for which there are iterators.
• Iterators for arrays. In addition to the STL containers, pointers to arrays act as iterators.

Kinds of iterators

There are several types of iterators, but most often you will use either bidirectional (list) or random iterators (vector, deque, array), which have all the operations of bidirectional iterators and more. Because so many algorithms only require bidirectional access, they can be applied to all containers.

Some of the other types are as follows. Forward iterators move only forward over the elements of a container. Input iterators that move only in a forward direction, at most one time, and can only access values. Output iterators that move only in a forward direction, at most one time, and can only write values.

Constant iterators

To preserve constantness there are both non-constant and constant versions of iterators