N4068, Toward More Expressive Iterator Tags

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());
}