An iterator is an object which allows traversal and protected node access in a graph data structure. Iterators are important in the design of data structures because they allow to separate the data structure from the algorithms that use that data structure. Iterators are an essential component of the C++ Standard Library, where their meaning is strictly defined. While the C++ iterators are always restricted to sequences, we shall adopt the more general definition.
While the iterator concept is appropriate for traversing trees and graphs, it is not well suited for sequential traversal. The problems associated with sequential iterators are as follows:
Two separate objects are needed to define a range in a sequence. This disables functional composition on ranges and opens up a possibility for pairing iterators erroneously.
For many data structures, it is not possible for iterators to be both efficient and error-safe. For example, without incurring non-trivial penalties, it is not possible to check whether two iterators form a valid range (e.g. linked list), or if a given iterator is in a legal range or not.
A partial solution to these problems is to combine the iterators into a single object called an iterator range. This instantly solves the problem of composition and significantly aids in the problem of incorrect pairing. However, because the individual iterators must still be accessed at some point, the problems are merely pushed deeper, rather than fundamentally solved.
A complete solution to the presented problems would be to take a sequence of elements as the primary abstraction. However, this solution is impractical, since all the algorithms in the C++ Standard Library are built around the iterator concept.
Pastel uses the iterator range solution, which has been elegantly implemented in the Boost.Range library. This library lifts the abstraction level of the C++ Standard Library algorithms to iterator ranges, and offers ways to compose and filter ranges.
A constant value iterator
An iterator adapter for dereferencing the adapted iterator
An iterator for sending data into oblivion.
An iterator adapter for a larger step size.