iterator interface¶

Writing iterators is necessary to implement custom ranges to take advantage of their ease of use and composability. However, satisfying all the standard iterator requirements is too tedious and error-prone, there’s a good example in the std::iterator_interface proposal.

To address this problem, we provide utilities that are similar to the proposed std::iterator_interface, which is based on Boost.STLInterfaces, but with multiple improvements over both of them listed in the Design section.

Examples of using them include:

linked list iterators for forward and bidirectional iterators;
integer_iterator for random access iterator;
filtered_range iterator for ac::iterator_adaptor usage.

Specifically, it’s enough to manually specify only a couple of nested types and implement the following core operations, and the rest will be correctly derived from them.

Operation	Return Type	Semantics
`*i`	reference	Returns dereferenced `i`
`i == j`	Convertible to `bool`	Returns true if and only if `i` and `j` refererence the same value
`i - j`	Convertible to `difference_type`	Returns offset between `i` and `j`
`++i`	`Iterator&`	Increments `i`
`--i`	`Iterator&`	Decrements `i`
`i += offset`	`Iterator&`	Increments `i` `offset` times, decrements if `offset < 0`

It’s never necessary to implement all of them, here’s the requirements for each iterator concept:

Concept	Operations	Nested types
std::output_iterator	`*i` `++i`	value_type
std::input_iterator	`*i` `++i`	value_type difference_type
std::forward_iterator	`*i` `++i` `i == j`	value_type difference_type
std::bidirectional_iterator	`*i` `++i` `i == j` `--i`	value_type difference_type
std::random_access_iterator	`*i` `i += offset` `i - j`	value_type

Note

If some of the derived operations don’t have the most efficient implementations, it’s always possible to manually override them.

Reference¶

#include <actl/range/iterator/interface/basic_iterator_interface.hpp>

template<typename DerivedIterator> class basic_iterator_interface¶: Avoids boilerplate needed to satisfy full requirements of std::input_or_output_iterator.

#include <actl/range/iterator/interface/output_iterator_interface.hpp>

template<typename DerivedIterator> class output_iterator_interface : public ac::basic_iterator_interface<DerivedIterator>¶: Avoids boilerplate needed to satisfy full requirements of std::output_iterator.

#include <actl/range/iterator/interface/input_iterator_interface.hpp>

template<typename DerivedIterator> class input_iterator_interface : public ac::basic_iterator_interface<DerivedIterator>¶: Avoids boilerplate needed to satisfy full requirements of std::input_iterator.

#include <actl/range/iterator/interface/forward_iterator_interface.hpp>

template<typename DerivedIterator> class forward_iterator_interface : public ac::input_iterator_interface<DerivedIterator>¶: Avoids boilerplate needed to satisfy full requirements of std::forward_iterator.

#include <actl/range/iterator/interface/bidirectional_iterator_interface.hpp>

template<typename DerivedIterator> class bidirectional_iterator_interface : public ac::forward_iterator_interface<DerivedIterator>¶: Avoids boilerplate needed to satisfy full requirements of std::bidirectional_iterator.

#include <actl/range/iterator/interface/random_access_iterator_interface.hpp>

template<typename DerivedIterator> class random_access_iterator_interface : public ac::bidirectional_iterator_interface<DerivedIterator>¶: Avoids boilerplate needed to satisfy full requirements of std::random_access_iterator.

#include <actl/range/iterator/interface/iterator_interface_selector.hpp>

template<typename DerivedIterator, typename Category> using ac::iterator_interface_selector_t = typename iterator_interface_selector<DerivedIterator, Category>::type¶: When the iterator category isn’t fixed but instead deduced by some expression, this selector can be used to select the correct iterator_interface template.

#include <actl/range/iterator/interface/iterator_adaptor.hpp>

template<typename DerivedIterator, typename AdaptedIterator, typename Category = iter_category_t<AdaptedIterator>> class iterator_adaptor : public iterator_interface_selector_t<DerivedIterator, iter_category_t<AdaptedIterator>>¶

iterator_adaptor helps to implement a new DerivedIterator that needs to reuse most of the existing AdaptedIterator implementation while overriding only a couple of operations.

Operations should be overridden in DerivedIterator by accessing the AdaptedIterator via base() and base_ref() methods for const and non-const access respectively.

For example, see filtered_range iterator.

Note

The idea is adopted from Boost: http://www.boost.org/doc/libs/latest/libs/iterator/doc/iterator_adaptor.html

See tests at tests/range/iterator/interface/

Design¶

Practical experience with using std::iterator_interface surfaced multiple usabiliy improvements that we implemented:

Hierarchy of interfaces instead of a single std::iterator_interface.

We consider this important becuase:
- Iterator concepts form a natural hierarchy, which we can just follow here.
- It’s easier to see which operations exactly are added for each concept compared to reading a huge combined single list with all the conditionally enabled operations.
- Doxygen is unable to determince which of the conditionally enabled operations are actually relevant for a particular iterator, for example, a forward iterator. Deriving from a class in the hierarchy with just the relevant operations solves this problem.
Note

we still provide ac::iterator_interface_selector_t as a single class entry point when it’s necessary.

Named nested types instead of template parameters.

Just compare the clarity between our implementation and the standard proposal:

struct repeated_chars_iterator
    : ac::random_access_iterator_interface<repeated_chars_iterator> {
    using value_type = char;
    ...

struct repeated_chars_iterator :
    std::iterator_interface<
        std::random_access_iterator_tag,
        char,
        char>
{
    ...

How would a reader guess what these two char template parameters mean without navigating to the std::iterator_interface declaration? In our case, it’s obvious by just looking at the code (and there’s no need to manually specify the second char as a reference).

Even more noticeable, see how many unnecessary type specifications we avoid when a custom difference_type is needed:

struct my_forward_iterator
    : ac::forward_iterator_interface<my_forward_iterator> {
    using value_type = char;
    using difference_type = int;
    ...

struct my_forward_iterator :
    std::iterator_interface<
        std::random_access_iterator_tag,
        char,
        char&,
        char*,
        int>
{
    ...

Note

ac::basic_iterator_interface constructor provides clear error messages when the necessary nested types are not specified.

There’s no proxy_iterator_interface.

We can automatically detect if the reference type is not a built-in reference, so there seems to be no benefit in forcing the user to know about a different interface type for this.
Separate ac::iterator_adaptor class instead of merging it into std::iterator_interface.

Adapting an iterator requires exposing all of its core operations and allowing to override the necessary ones. Which is conceptually quite different from providing all the core operations needed by the iterator interface. For this reason, we consider it confusing to provide all of this functionality in a single std::iterator_interface class.
Post-increment and post-decrement are implemented as friend functions instead of methods.

As a result, the user code doesn’t have to include this confusing code for forward iterators
```
using base_type = std::iterator_interface<std::forward_iterator_tag, T>;
using base_type::operator++;
```
and this for bidirectional iterators
```
using base_type::operator--;
```
There’s a whole section in Boost.STLInterfaces discussing this problem, which we don’t have to worry about.
operator==(T const&) = default; definition is supported for forward and bidirectional iterators intead of forcing users to manually implement it.
DifferenceType is a template parameter in all the operations where it’s used.

This allows to support cases like aligned iterators, where the alignment can change if the DifferenceType isn’t guaranteed to be a multiple of alignment.