Doc No:N4124
Date:2014-09-11
Reply to:stdbill.h@pobox.com

Toward More Expressive Iterator Tags

Bill Seymour
2014-09-11


Introduction

During the discussion of N3976 in Rapperswil, 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.


Revision history

This paper revises N4068 to:


Acknowledgement

Thanks to Stephan T. Lavavej for teaching me the metaprogramming trick that I needed for writing the test code at the end of N4068, which eventually led to N4115.


The basic idea

We’ll start with several new iterator tags that express particular iterator requirements. This is probably not an exhaustive list. For the most part, the iterator tags that we all know and love could become typedefs of packers (see N4115):
    typedef packer<lvalue_tag> output_iterator_tag;

    typedef packer<rvalue_tag, equality_comparable_tag> input_iterator_tag;
But to avoid breaking legacy code that depends on iterator tag inheritance, we could apply the inheritance to packer specializations:
    template<>
    struct packer<reference_tag,
                  lvalue_tag,
                  rvalue_tag,
                  equality_comparable_tag,
                  multipass_tag>
             : input_iterator_tag { };
And then (with the same parameter pack):
    typedef packer<reference_tag,
                   lvalue_tag,
                   rvalue_tag,
                   equality_comparable_tag,
                   multipass_tag>
              forward_iterator_tag;
And so on...
    template<>
    struct packer<reference_tag,
                  lvalue_tag,
                  rvalue_tag,
                  equality_comparable_tag,
                  multipass_tag,
                  decrementable_tag>
             : forward_iterator_tag { };

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

    template<>
    struct packer<reference_tag,
                  lvalue_tag,
                  rvalue_tag,
                  equality_comparable_tag,
                  multipass_tag,
                  decrementable_tag,
                  random_move_tag>
             : bidirectional_iterator_tag { };

    typedef packer<reference_tag,
                   lvalue_tag,
                   rvalue_tag,
                   equality_comparable_tag,
                   multipass_tag,
                   decrementable_tag,
                   random_move_tag>
              random_access_iterator_tag;
Note that we could still say, for example,
    template <class T>
    struct iterator_traits<T*>
    {
        // ...
        typedef random_access_iterator_tag iterator_category;
    };
without breaking legacy code.


A couple of use cases


A crude test of the basic idea

The author’s actual code, in the public domain, is available here if you want to try it yourself.
#include <iostream>

//
// Assume that <type_traits> and <iterator> define the new
// templates proposed in N4115 and this paper, respectively,
// in the std::experimental namespace, along with the usual
// iterator_traits template for which the <T*> specialization
// uses the new std::experimental::random_access_iterator_tag.
//
#include <type_traits>
#include <iterator>

namespace {

using std::cout;
using std::experimental::packer;
using std::experimental::contains_types;
using std::experimental::random_move_tag;

namespace detail {

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

typedef packer<random_move_tag> mininum_fast_iterator_tag;

//
// Dispatch on the iterator category:
//
template<class Iter>
void my_algorithm(Iter, std::experimental::forward_iterator_tag)
{
    cout << "Slower legacy code still works\n";
}
template<class Iter>
void my_algorithm(Iter, std::experimental::random_access_iterator_tag)
{
    cout << "Faster legacy code still works\n";
}

} // namespace detail

template<class Iter> void my_algorithm(Iter first)
{
    detail::my_algorithm(first,
      contains_types<
        typename std::experimental::iterator_traits<Iter>::iterator_category,
        detail::mininum_fast_iterator_tag>());
}

template<class Iter> void legacy_algorithm(Iter first)
{
    detail::my_algorithm(first,
      typename std::experimental::iterator_traits<Iter>::iterator_category());
}

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

struct my_bidirectional_iterator
{
    // ...
    typedef std::experimental::bidirectional_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());
    my_algorithm("char*");

    legacy_algorithm(my_forward_iterator());
    legacy_algorithm(my_bidirectional_iterator());

    static int array[] = { 0 };
    legacy_algorithm(array);
}
Expected output:
Less efficient
More efficient
More efficient
Slower legacy code still works
Slower legacy code still works
Faster legacy code still works


Reply to:  stdbill.h@pobox.com