A cursor is an object that allows traversal and protected node access in a graph data structure. An iterator is a cursor which traverses nodes in a sequence.
The cursor is an important concept in the design of data structures because it allows to separate the data structure from the algorithms that use that data structure. Failing to do this results in classes whose interfaces need to be continuously extended to embed new algorithms. Iterators are an essential component of the C++ Standard Library.
While the cursor concept is appropriate for traversing trees and graphs, it is not well suited for sequential traversal (i.e. iterators). The problems associated with 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, or if a given iterator is in a legal range or not.
A partial solution to these problems is to use iterator ranges instead. 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 is to take a sequence of elements as the primary abstraction. This leads to the range concept. The only problem then is that the C++ Standard Library is unable to work with this abstraction.
Despite the problems, PastelSys provides implementations for several iterators. While the given functionality is better encapsulated as ranges (as they are), iterators are needed to be able to work with the algorithms in the C++ Standard Library.
The ConstantIterator represents a sequence which contains the same
constant data everywhere.
A CountingIterator is an adapter that can be used to dereference the
traversed iterator instead of its data. This is useful when you need
to pass a function a set of iterators whose values to apply some
procedure. The NullIterator can be used as a no-op iterator which
sends all the data written to it to oblivion. This is useful when
you have no need for some result from a function.
SparseIterator can be used as an adapter to take multiple steps
instead of one. For example, using SparseIterator in combination
with the CountingIterator with integers, you are able to generate the
integer sequence 3, 5, 7, 9, 11 on the fly.
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.