Back to Programming techniques
A container data-structure in the C++ Standard Library often provides only two types of iterators: a mutable iterator iterator, and a non-mutable iterator const_iterator. This selection is not convenient for all uses. For example, while an iterator of std::map dereferences to a key-value pair, sometimes it is convenient to dereference to the key, and sometimes it is convenient to dereference to the value. In this section we present a technique for supporting various types of iterators to access the same part of a data-structure in different ways.
In general, a given part of a data-structure is desired to be accessed by an iterator with orthogonal compile-time properties, with the :th property having choices, for a total of possible iterator-types.
The varying types of iterators, for a given part, must interoperate; each of them must be equivalently usable for accessing the same part of a data-structure, except when explicitly disallowed by the data-structure (e.g. no mutation of the value through a const-iterator).
What is the best way to support such varying iterators?
For the RedBlack_Map, (constness, dereferencing), (const, non-const), and (key-value, key, value), for a total of 6 iterator types.
We solve the problem by using internal adaptation for our data-structures, and by using external adaptation for the other data-structures (such as the C++ Standard Library). The internal adaptation is to be used when the adaptation is meaningful only in that data-structure, or when the adaptation is expected to be common. The external adaptation is used for all the other use-cases.
Parametrize the iterator (range) with respect to the orthogonal properties, ensuring interoperability, and choose one parameter combination as the basic version. Use the basic-version in the interface of the data-structure, and provide functions in the iterator (range) to adapt the iterator one property at a time.
dataSet.begin().read().dereferenceData();
dataSet.range().read().dereferenceData();
For compatibility with the C++ Standard Library, also provide the c-prefix functions (e.g. cbegin()) for added constness (corresponding to an implicit .read()).
Create an iterator (range) adaptor which implements the changes by indirection to an underlying base-iterator (base-range).
secondIterator(dataSet.begin());
secondRange(dataSet.range());
For iterators which dereference to std::pair, create an iterator adaptor which dereferences to iter->first or iter->second instead. The latter is provided by the Second_Iterator adaptor. This is a transition-adaptor while waiting for the C++14 support to be implemented in compilers.
In C++14, it is possible to create a generic iterator adaptor which takes in a generic lambda function to transform the dereferencing of the base iterator, with the resulting type deduced by decltype.
Using Boost’s iterator library, it is easy to define more general iterator adaptors, which adapt not only the dereferencing, but also the traversal.