c++: iterator --bidir--forward--random

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 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





Assume C is a container class, containing elements of type T.

bool b;
int i;
T value;
C::iterator it, it1, it2;

Result Operator Description
Operators for most iterators. Vectors, lists, arrays, ....
value = *it; Use dereference (*) op to get/set value.
++it; Points to next element. Value after update.
it++; Points to next element. Value before update.
it1 = it2; Assignment
b = it1 == it2; Equality comparison.
b = it1 != it2; Inequality.
Additional operators for bidirectional iterators. Vectors, lists, arrays, ...
--it; Predecrement.
it--; Postdecrement. May be less efficient than predecrement.
Additional operators for random-access iterators. Vectors and arrays, but not lists.
it += i; Increments it by i positions.
it -= i; Decrements it by i positions.
it1 = it2 + i; Increments it by i positions.
it1 = it2 - i; Decrements it by i positions.
value = it[i]; Returns reference to ith element after it.
b = it1 < it2; Comparison.
b = it1 <= it2; Comparison.
b = it1 > it2; Comparison.
b = it1 <= it2; Comparison.





We could loop over this array like this.

for (int* p = &a[0]; p != &a[n]; p++) {
cout << *p << endl;
}

or

for (int* p = a; p != a+n; p++) {
cout << *p << endl;
}

Iterating over a vector with an iterator

//--- Iterating over vector with iterator.
vector v;
. . .
for (vector::iterator it = v.begin(); it!=v.end(); ++it) {
cout << *it << endl;
}

Why use iterators when subscripts work so well
There are several reasons to use iterators.

* Not always possible. Subscripts can not be used on most of the containers (eg, list and map), so you must use iterators in many cases.
* Flexible. It is easily to change underlying container types. For example, you might decide later that the number of insertions and deletions is so high that a list would be more efficient than a vector.
* Member functiuons. Many of the member functions for vector use iterators, for example, assign, insert, or erase.
* Algorithms. The functions use iterators.