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. 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


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