Doc No: | N4068
Date: | 2014-06-28
Reply to: | `stdbill.h@pobox.com`

## Toward More Expressive Iterator Tags

### Bill Seymour
2014-06-28

### Introduction

During the discussion of N3976 in Rapperswil on Tuesday, it was pointed out that certain iterators proposed in the paper claim to be random-access iterators when, in fact, they’re not even forward iterators. A straw poll showed that a majority of those present were in favor of keeping `random_access_iterator_tag` as the iterator category (because the more efficient algorithms would “probably just work”); but there were enough dissenting votes that calling it consensus might be a bit of a stretch.

The problem is probably best solved using concepts; but we already have iterator tags and they’re not going away. This short paper asks whether there’s interest in having more finely-grained iterator tags. At this point, it’s just a partly-baked idea intended to get a discussion started.

### Acknowledgement

Thanks to Stephan T. Lavavej for teaching me the metaprogramming trick that I needed for writing the test code at the end of this paper.

### The basic idea

We’ll start with several new iterator tags that express particular iterator requirements. This is probably not an exhaustive list.

- Whether `*iter` is an actual `value_type&` (not a proxy) and the value is not cached in the iterator itself:

          struct reference_tag { };

- Whether `*iter` is a modifiable lvalue or an rvalue (could be both):

          struct lvalue_tag { };
          struct rvalue_tag { };

- Whether `iter1` `==` `iter2` is well-formed:

          struct equality_comparable_tag { };

- Whether `iter1` `==` `iter2` implies both `++iter1` `==` `++iter2` and `&*iter1` `==` `&*iter2`:

          struct multipass_tag { };

- Whether `--iter` is well-formed:

          struct decrementable_tag { };

- Whether `iter` can be moved an arbitrary distance and is less-than comparable:

          struct random_move_tag { };

We could combine the above as:

        template<class... Tags> struct basic_iterator_tag { };

And then the existing iterator tags that we all know and love could become:

        typedef basic_iterator_tag<lvalue_tag> output_iterator_tag;

        typedef basic_iterator_tag<rvalue_tag, equality_comparable_tag>
                  input_iterator_tag;

        typedef basic_iterator_tag<reference_tag,
                                   lvalue_tag,
                                   rvalue_tag,
                                   equality_comparable_tag,
                                   multipass_tag>
                  forward_iterator_tag;

        typedef basic_iterator_tag<reference_tag,
                                   lvalue_tag,
                                   rvalue_tag,
                                   equality_comparable_tag,
                                   multipass_tag,
                                   decrementable_tag>
                  bidirectional_iterator_tag;

        typedef basic_iterator_tag<reference_tag,
                                   lvalue_tag,
                                   rvalue_tag,
                                   equality_comparable_tag,
                                   multipass_tag,
                                   decrementable_tag,
                                   random_move_tag>
                  random_access_iterator_tag;

### A couple of use cases

- One rather obvious example would seem to be:

          typedef basic_iterator_tag<lvalue_tag,
                                     rvalue_tag,
                                     equality_comparable_tag,
                                     multipass_tag,
                                     decrementable_tag,
                                     random_move_tag>
                    vector_bool_iterator_tag;

  Note that it lacks `reference_tag` in the parameter pack because `*iter` returns a proxy instead of a proper `bool&`.

- And let's say that somebody wants to model as C++ iterators what the database folk call “scrolling cursors”:

          typedef basic_iterator_tag<rvalue_tag,
                                     equality_comparable_tag,
                                     multipass_tag,
                                     decrementable_tag,
                                     random_move_tag>
                    scrolling_cursor_tag;

  A scrolling cursor can move back and forth by arbitrary distances; but it lacks both `reference_tag` and `lvalue_tag` because `*iter` probably returns by `const` reference a value cached in the iterator itself.

### A quick test of the basic idea

    #include <iostream>
    #include <type_traits>

    namespace std {
    namespace experimental {

    //
    // The proposed iterator tags:
    //

    struct reference_tag { };
    struct lvalue_tag { };
    struct rvalue_tag { };
    struct equality_comparable_tag { };
    struct multipass_tag { };
    struct decrementable_tag { };
    struct random_move_tag { };

    template<class... Tags> struct basic_iterator_tag { };

    //
    // The existing iterator tags:
    //

    typedef basic_iterator_tag<lvalue_tag> output_iterator_tag;

    typedef basic_iterator_tag<rvalue_tag, equality_comparable_tag>
              input_iterator_tag;

    typedef basic_iterator_tag<reference_tag,
                               lvalue_tag,
                               rvalue_tag,
                               equality_comparable_tag,
                               multipass_tag>
              forward_iterator_tag;

    typedef basic_iterator_tag<reference_tag,
                               lvalue_tag,
                               rvalue_tag,
                               equality_comparable_tag,
                               multipass_tag,
                               decrementable_tag>
              bidirectional_iterator_tag;

    typedef basic_iterator_tag<reference_tag,
                               lvalue_tag,
                               rvalue_tag,
                               equality_comparable_tag,
                               multipass_tag,
                               decrementable_tag,
                               random_move_tag>
              random_access_iterator_tag;

    //
    // Whether a parameter pack contains a given type
    // (probably an implementation detail in the standard library):
    //

    template <class Required, class... Present> struct _Pack_has_type;

    template <class Required> struct _Pack_has_type<Required> : false_type { };

    template <class Required, class... Rest>
      struct _Pack_has_type<Required, Required, Rest...> : true_type { };

    template <class Required, class First, class... Rest>
      struct _Pack_has_type<Required, First, Rest...>
        : _Pack_has_type<Required, Rest...> { };

    //
    // Whether a basic_iterator_tag (Candidate) has a parameter pack that’s
    // a superset of the pack of some minimum basic_iterator_tag (Required):
    //

    template <class Candidate, class Required> struct has_iterator_tags;

    template <class... Candidates>
      struct has_iterator_tags<basic_iterator_tag<Candidates...>,
                               basic_iterator_tag<>>
        : true_type { };

    template <class... Candidates, class Reqd1, class... ReqdRest>
      struct has_iterator_tags<basic_iterator_tag<Candidates...>,
                               basic_iterator_tag<Reqd1, ReqdRest...>>
        : integral_constant<bool,
            _Pack_has_type<Reqd1, Candidates...>::value &&
            has_iterator_tags<basic_iterator_tag<Candidates...>,
                              basic_iterator_tag<ReqdRest...>>::value> { };

    } // namespace experimental
    } // namespace std

    namespace {

    using std::experimental::has_iterator_tags;
    using std::experimental::basic_iterator_tag;
    using std::experimental::random_move_tag;

    namespace detail
    {
        template<class Iter> void my_algorithm(Iter, std::false_type)
        {
            std::cout << "Less efficient\n";
        }
        template<class Iter> void my_algorithm(Iter, std::true_type)
        {
            std::cout << "More efficient\n";
        }
    }

    template<class Iter> void my_algorithm(Iter first)
    {
        detail::my_algorithm(first,
          has_iterator_tags<typename Iter::iterator_category,
                            basic_iterator_tag<random_move_tag>>());
    }

    struct my_forward_iterator
    {
        typedef std::experimental::forward_iterator_tag iterator_category;
    };

    struct my_random_iterator
    {
        typedef std::experimental::random_access_iterator_tag iterator_category;
    };

    } // anonymous namespace

    int main()
    {
        my_algorithm(my_forward_iterator());
        my_algorithm(my_random_iterator());
    }