Motivation

The standard iterator categories and requirements are flawed because they use a single hierarchy of concepts to address two orthogonal issues: iterator traversal and value access. As a result, many algorithms with requirements expressed in terms of the iterator categories are too strict. Also, many real-world iterators can not be accurately categorized. A proxy-based iterator with random-access traversal, for example, may only legally have a category of "input iterator", so generic algorithms are unable to take advantage of its random-access capabilities. The current iterator concept hierarchy is geared towards iterator traversal (hence the category names), while requirements that address value access sneak in at various places. The following table gives a summary of the current value access requirements in the iterator categories.

Because iterator traversal and value access are mixed together in a single hierarchy, many useful iterators can not be appropriately categorized. For example, vector<bool>::iterator is almost a random access iterator, but the return type is not bool& (see issue 96 and Herb Sutter's paper J16/99-0008 = WG21 N1185). Therefore, the iterators of vector<bool> only meet the requirements of input iterator and output iterator. This is so nonintuitive that the C++ standard contradicts itself on this point. In paragraph 23.2.4/1 it says that a vector is a sequence that supports random access iterators.

Another difficult-to-categorize iterator is the transform iterator, an adaptor which applies a unary function object to the dereferenced value of the some underlying iterator (see transform_iterator). For unary functions such as times, the return type of operator* clearly needs to be the result_type of the function object, which is typically not a reference. Because random access iterators are required to return lvalues from operator*, if you wrap int* with a transform iterator, you do not get a random access iterator as might be expected, but an input iterator.

A third example is found in the vertex and edge iterators of the Boost Graph Library. These iterators return vertex and edge descriptors, which are lightweight handles created on-the-fly. They must be returned by-value. As a result, their current standard iterator category is input_iterator_tag, which means that, strictly speaking, you could not use these iterators with algorithms like min_element(). As a temporary solution, the concept Multi-Pass Input Iterator was introduced to describe the vertex and edge descriptors, but as the design notes for the concept suggest, a better solution is needed.

In short, there are many useful iterators that do not fit into the current standard iterator categories. As a result, the following bad things happen:

• Iterators are often mis-categorized.
• Algorithm requirements are more strict than necessary, because they cannot separate the need for random access or bidirectional traversal from the need for a true reference return type.

Impact on the Standard

This proposal for TR1 is a pure extension. Further, the new iterator concepts are backward-compatible with the old iterator requirements, and old iterators are forward-compatible with the new iterator concepts. That is to say, iterators that satisfy the old requirements also satisfy appropriate concepts in the new system, and iterators modeling the new concepts will automatically satisfy the appropriate old requirements.

Design

The iterator requirements are to be separated into two groups. One set of concepts handles the syntax and semantics of value access:

• Readable Iterator
• Writable Iterator
• Swappable Iterator
• Lvalue Iterator

The access concepts describe requirements related to operator* and operator->, including the value_type, reference, and pointer associated types.

The other set of concepts handles traversal:

• Incrementable Iterator
• Single Pass Iterator
• Forward Traversal Iterator
• Bidirectional Traversal Iterator
• Random Access Traversal Iterator

The refinement relationships for the traversal concepts are in the following diagram.

In addition to the iterator movement operators, such as operator++, the traversal concepts also include requirements on position comparison such as operator== and operator<. The reason for the fine grain slicing of the concepts into the Incrementable and Single Pass is to provide concepts that are exact matches with the original input and output iterator requirements.

This proposal also includes a concept for specifying when an iterator is interoperable with another iterator, in the sense that int* is interoperable with int const*.

• Interoperable Iterators

The relationship between the new iterator concepts and the old are given in the following diagram.

Like the old iterator requirements, we provide tags for purposes of dispatching based on the traversal concepts. The tags are related via inheritance so that a tag is convertible to another tag if the concept associated with the first tag is a refinement of the second tag.

Our design reuses iterator_traits<Iter>::iterator_category to indicate an iterator's traversal capability. To specify capabilities not captured by any old-style iterator category, an iterator designer can use an iterator_category type that is convertible to both the the most-derived old iterator category tag which fits, and the appropriate new iterator traversal tag.

We do not provide tags for the purposes of dispatching based on the access concepts, in part because we could not find a way to automatically infer the right access tags for old-style iterators. An iterator's writability may be dependent on the assignability of its value_type and there's no known way to detect whether an arbitrary type is assignable. Fortunately, the need for dispatching based on access capability is not as great as the need for dispatching based on traversal capability.

A difficult design decision concerned the operator[]. The direct approach for specifying operator[] would have a return type of reference; the same as operator*. However, going in this direction would mean that an iterator satisfying the old Random Access Iterator requirements would not necessarily be a model of Readable or Writable Lvalue Iterator. Instead we have chosen a design that matches the preferred resolution of issue 299: operator[] is only required to return something convertible to the value_type (for a Readable Iterator), and is required to support assignment i[n] = t (for a Writable Iterator).

Proposed Text

{
   X tmp = r;
   ++r;
   return tmp;
}

{
  X tmp = r;
  --r;
  return tmp;
}

{
  Distance m = n;
  if (m >= 0)
    while (m--)
      ++r;
  else
    while (m++)
      --r;
  return r;
}

// lib.iterator.traits, traits and tags
template <class Iterator> struct is_readable_iterator;
template <class Iterator> struct iterator_traversal;

struct incrementable_traversal_tag { };
struct single_pass_traversal_tag : incrementable_traversal_tag { };
struct forward_traversal_tag : single_pass_traversal_tag { };
struct bidirectional_traversal_tag : forward_traversal_tag { };
struct random_access_traversal_tag : bidirectional_traversal_tag { };

category-to-traversal(iterator_traits<X>::iterator_category) 

category-to-traversal(C) =
    if (C is convertible to incrementable_traversal_tag)
        return C;
    else if (C is convertible to random_access_iterator_tag)
        return random_access_traversal_tag;
    else if (C is convertible to bidirectional_iterator_tag)
        return bidirectional_traversal_tag;
    else if (C is convertible to forward_iterator_tag)
        return forward_traversal_tag;
    else if (C is convertible to input_iterator_tag)
        return single_pass_traversal_tag;
    else if (C is convertible to output_iterator_tag)
        return incrementable_traversal_tag;
    else
        the program is ill-formed

Footnotes

The UnaryTypeTrait concept is defined in n1519; the LWG is considering adding the requirement that specializations are derived from their nested ::type.