In programming language design, an iterator identifies an element in a range of elements (such as an array or container), akin to a more generalised pointer. Iterators allow us to progressively access each item in this range.
Depending on what data structure we’re using, we can use similar access syntax as pointers, like dereferencing (*), increments/decrements (++, --), and equality operators (==, !=).
There are certain types of iterators:
- Classified depending on how we interact with them:
- Forward iterators allow increments.
- Bidirectional iterators allow both increments and decrements. If structures have bidirectional iterators, we can use reverse iterators to traverse backwards.
- Random access iterators allow increments, decrements, and random accesses.
- And how they are modified:
- Constant iterators only produce a read-only version of the element when de-referenced.
- Mutable iterators can be changed.
Language-specific
In C++
Each container in the Standard Template Library has its own iterator type (just as each data type has its own pointer type). For example, an int vector iterator type is given by std::vector<int>::iterator. If this returns a mutable iterator, we can force a constant iterator with ::const_iterator.
For a container c:
c.begin()returns an iterator for the first data item in the container.c.end()returns the element after the last item in the container (which is useful to check when we’re done). It isn’t exactly an iterator.- The dereference operator
*returns the element located at the iterator. c.rbegin()returns a safe reverse iterator at the end of the container.c.rend()returns a safe marker for the end of the reversed container.