N4124, Toward More Expressive Iterator Tags

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:

reintroduce existing iterator tag inheritance that got lost in N4068.
use the packer and contains_types templates proposed in N4115. The packer template replaces N4068’s basic_iterator_tag; and the metaprogramming in the test code at the end of that paper, which is something of a distraction, is no longer needed. [Note: N4115 will be revised for the pre-Urbana mailing, N4144; but nothing in that revision affects this paper.]

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.

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 (i.e., *iter1 and *iter2 are the same object):
```
    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 { };
```

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

One rather obvious example would seem to be the iterator we get from vector<bool>, not even a forward iterator because *iter is a proxy instead of a proper bool& (so it lacks reference_tag in its parameter pack); but it still has the random-movement ability for use by altorithms for which the proxy isn’t a problem:

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

    typedef packer<lvalue_tag,
                   rvalue_tag,
                   equality_comparable_tag,
                   multipass_tag,
                   decrementable_tag,
                   random_move_tag>
              random_proxy_iterator_tag;

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

    template<>
    struct packer<rvalue_tag,
                  equality_comparable_tag,
                  multipass_tag,
                  decrementable_tag,
                  random_move_tag>
             : input_iterator_tag { };

    typedef packer<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 is probably a const reference to a value cached in the iterator itself.

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