[Yaml-core] iterator link (for API)

[Clark C . E. <cc...@cl...>]

There is a discussion of iterators on python-dev that was
interesting; someone posted the following link as C++ iterator
category change proposal.   Anyway, this may be releveant to
those who are making sequential-access APIs for YAML.
http://groups.yahoo.com/group/boost/files/iterator-categories.html


Clark


              Improved Iterator Categories and Requirements              

Introduction

The standard iterator categories and requirements are flawed because they
use a single hierarchy of requirements to address two orthogonal issues: 
iterator traversal and dereference return type. The current iterator
requirement hierarchy is mainly geared towards iterator traversal (hence
the category names), while requirements that address dereference return
type sneak in at various places. The following table gives a summary of
the current dereference return type requirements in the iterator
categories.

    Table 1. Summary of current dereference return type requirements.    
+-----------------------------------------------------------------------+
|Output     |*i = a                                                     |
|Iterator   |                                                           |
|-----------+-----------------------------------------------------------|
|Input      |*i is convertible to T                                     |
|Iterator   |                                                           |
|-----------+-----------------------------------------------------------|
|Forward    |*i is T& (or const T& once issue 200 is resolved)          |
|Iterator   |                                                           |
|-----------+-----------------------------------------------------------|
|Random     |i[n] is convertible to T (which is odd because the         |
|Access     |operational semantics say i[n] is equivalent to *(i + n)   |
|Iterator   |which would have a return type of T&)                      |
|-----------+-----------------------------------------------------------|
|           |                                                           |
+-----------------------------------------------------------------------+

Examples of useful iterators that do not ``fit''

Because of the mixing of iterator traversal and dereference return type,
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 only meet the requirements of input
iterator and output iterator. This is so nonintuitive that at least one
implementation erroneously assigns random_access_iterator_tag as its
iterator_category. Also, vector<bool> is not the only example of useful
iterators that do not return true references: there is the often cited
example of disk-based collections.

Another example is a counting iterator, an iterator the returns a
sequence of integers when incremented and dereferenced (see boost::
counting_iterator). There are two ways to implement this iterator, 1)
make the reference type be a true reference (a reference to an integer
data member of the counting iterator) or 2) make the reference type be
the same as the value_type. Option 1) runs into the problems discussed in
Issue 198, the reference will not be valid after the iterator is
destroyed. Option 2) is therefore a better choice, but then we have a
counting iterator that cannot be a random access iterator.

Yet another example is a transform iterator, an iterator adaptor that
applies a unary function object to the dereference value of the wrapped
iterator (see boost::transform_iterator). For unary functions such as
std::times the return type of operator* clearly needs to be the
result_type of the function object, which is typically not a reference.
However, with the current iterator requirements, if you wrap int* with a
transform iterator, you do not get a random access iterator as expected,
but an input iterator.

A fourth 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 std::
input_iterator_tag, which means that, strictly speaking, you could not
use these iterators with algorithms like std::min_element(). As a
temporary solution, we introduced the concept Multi-Pass Input Iterator
to describe the vertex and edge descriptors, but as the design notes for
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 miss-categorized.
  * Algorithm requirements are more strict than necessary, because they
    can not separate out the need for random-access from the need for a
    true reference return type.

Proposal for new iterator categories and requirements

The iterator requirements should be separated into two hierarchies. One
set of concepts handles the return type semantics:

  * Readable Iterator
  * Writable Iterator
  * Swappable Iterator
  * Constant Lvalue Iterator
  * Mutable Lvalue Iterator

The other set of concepts handles iterator traversal:

  * Forward Traversal Iterator
  * Bidirectional Traversal Iterator
  * Random Access Traversal Iterator

The current Input Iterator and Output Iterator requirements will continue
to be used as is. Note that Input Iterator implies Readable Iterator and
Output Iterator implies Writable Iterator.

Note: we considered defining a Single-Pass Iterator, which could be
combined with Readable or Writable Iterator to replace the Input and
Output Iterator requirements. We rejected this idea because there are
several differences between Input and Output Iterators that make it hard
to merge them: Input Iterator requires Equality Comparable while Output
Iterator does not and Input Iterator requires Assignable while Output
Iterator does not.

New categories and traits classes

Each of the new iterator requirements will need a category tag.
namespace std {

  // Return Type Categories
  struct readable_iterator_tag { };
  struct writable_iterator_tag { };
  struct swappable_iterator_tag { };
  struct mutable_lvalue_iterator_tag : virtual public writable_iterator_tag,
    virtual public readable_iterator_tag { };
  struct constant_lvalue_iterator_tag : public readable_iterator_tag { };

  // Traversal Categories
  struct forward_traversal_tag { };
  struct bidirectional_traversal_tag : public forward_traversal_tag { };
  struct random_access_traversal_tag : public bidirectional_traversal_tag { };

}
And there will need to be a way to access these category tags using a
traits mechanism. Adding new typedefs to std::iterator_traits is not an
acceptable solution because that would break every existing iterator.
Instead, we propose two new traits classes. It is important that these
traits classes are backward compatible, that is, they should work with
any iterator for which there is a valid definition of std::
iterator_traits. This can be accomplished by making the default behavior
of the traits classes map the iterator_category of the iterator to the
appropriate return or traversal category. For new iterators, either
specializations of these traits classes can be defined, or the iterator
can provide nested typedefs, and inherit from new_iterator_base (which is
just a signal to the traits class that it is a new iterator). As with
std::iterator_traits, specializations for T* are provided.
namespace std {

  struct new_iterator_base { };

  template <typename Iterator>
  struct return_category
  {
    // Pseudo-code
    if (Iterator inherits from new_iterator_base) {
      typedef typename Iterator::return_category type;
    } else {
      typedef std::iterator_traits<Iterator> OldTraits;
      typedef typename OldTraits::iterator_category Cat;
      if (Cat inherits from std::forward_iterator_tag)
        if (is-const(T))
          typedef boost::constant_lvalue_iterator_tag type;
        else
          typedef boost::mutable_lvalue_iterator_tag type;
      else if (Cat inherits from std::input_iterator_tag)
        typedef boost::readable_iterator_tag type;
      else if (Cat inherits from std::output_iterator_tag)
        typedef boost::writable_iterator_tag type;
    }
  };

  template <typename T>
  struct return_category<T*>
  {
    // Pseudo-code
    if (is-const(T))
      typedef boost::constant_lvalue_iterator_tag type;
    else
      typedef boost::mutable_lvalue_iterator_tag type;
  };

  template <typename Iterator>
  struct traversal_category
  {
    // Pseudo-code
    if (Iterator inherits from new_iterator_base) {
      typedef typename Iterator::traversal_category type;
    } else {
      typedef std::iterator_traits<Iterator> OldTraits;
      typedef typename OldTraits::iterator_category Cat;

      if (Cat inherits from std::random_access_iterator_tag)
        typedef boost::random_access_traversal_tag type;
      else if (Cat inherits from std::bidirectional_iterator_tag)
        typedef boost::bidirectional_traversal_tag type;
      else if (Cat inherits from std::forward_iterator_tag)
        typedef boost::forward_traversal_tag type;
    }
  };

  template <typename T>
  struct traversal_category<T*>
  {
    typedef boost::random_access_traversal_tag type;
  };

}

Impact on the Standard Algorithms

Many of the standard algorithms place more requirements than necessary on
their iterator parameters due to the coarseness of the current iterator
categories. By using the new iterator categories a better fit can be
achieved, thereby increasing the reusability of the algorithms. These
changes will not affect user-code, though they will require changes by
standard implementers: dispatching should be based on the new categories,
and in places return values may need to be handled more carefully. In
particular, uses of std::swap() will need to be replaced with std::
iter_swap(), and std::iter_swap() will need to call std::swap().

          Table 2. Requirement changes for standard algorithms.          
+-----------------------------------------------------------------------+
|   Algorithm    |                  Requirement Change                  |
|----------------+------------------------------------------------------|
|find_end        |                                                      |
|----------------|                                                      |
|find_first_of   |                                                      |
|----------------|                                                      |
|adjacent_find   |                                                      |
|----------------|                                                      |
|search          |                                                      |
|----------------|                                                      |
|search_n        |                                                      |
|----------------|                                                      |
|rotate_copy     |Forward Iterator                                      |
|----------------|-> Forward Traversal Iterator and Readable Iterator   |
|lower_bound     |                                                      |
|----------------|                                                      |
|upper_bound     |                                                      |
|----------------|                                                      |
|equal_range     |                                                      |
|----------------|                                                      |
|binary_search   |                                                      |
|----------------|                                                      |
|min_element     |                                                      |
|----------------|                                                      |
|max_element     |                                                      |
|----------------+------------------------------------------------------|
|iter_swap       |Forward Iterator                                      |
|                |-> Swappable Iterator                                 |
|----------------+------------------------------------------------------|
|fill            |Forward Iterator                                      |
|----------------|-> Forward Traversal Iterator and Writable Iterator   |
|generate        |                                                      |
|----------------+------------------------------------------------------|
|swap_ranges     |Forward Iterator                                      |
|----------------|-> Forward Traversal Iterator and Swappable Iterator  |
|rotate          |                                                      |
|----------------+------------------------------------------------------|
|replace         |                                                      |
|----------------|                                                      |
|replace_if      |                                                      |
|----------------|Forward Iterator                                      |
|remove          |-> Forward Traversal Iterator and                     |
|----------------|Readable Iterator and Writable Iterator               |
|remove_if       |                                                      |
|----------------|                                                      |
|unique          |                                                      |
|----------------+------------------------------------------------------|
|reverse         |Bidirectional Iterator                                |
|----------------|-> Bidirectional Traversal Iterator and Swappable     |
|partition       |Iterator                                              |
|----------------+------------------------------------------------------|
|                |Bidirectional Iterator                                |
|                |-> Bidirectional Traversal Iterator and Readable      |
|copy_backwards  |Iterator                                              |
|                |Bidirectional Iterator                                |
|                |-> Bidirectional Traversal Iterator and Writable      |
|                |Iterator                                              |
|----------------+------------------------------------------------------|
|next_permutation|Bidirectional Iterator                                |
|----------------|-> Bidirectional Traversal Iterator and               |
|prev_permutation|Swappable Iterator and Readable Iterator              |
|----------------+------------------------------------------------------|
|stable_partition|Bidirectional Iterator                                |
|----------------|-> Bidirectional Traversal Iterator and               |
|inplace_merge   |Readable Iterator and Writable Iterator               |
|----------------+------------------------------------------------------|
|                |Bidirectional Iterator                                |
|reverse_copy    |-> Bidirectional Traversal Iterator and Readable      |
|                |Iterator                                              |
|----------------+------------------------------------------------------|
|random_shuffle  |                                                      |
|----------------|                                                      |
|sort            |                                                      |
|----------------|                                                      |
|stable_sort     |                                                      |
|----------------|                                                      |
|partial_sort    |                                                      |
|----------------|Random Access Iterator                                |
|nth_element     |-> Random Access Traversal Iterator and Swappable     |
|----------------|Iterator                                              |
|push_heap       |                                                      |
|----------------|                                                      |
|pop_heap        |                                                      |
|----------------|                                                      |
|make_heap       |                                                      |
|----------------|                                                      |
|sort_heap       |                                                      |
|----------------+------------------------------------------------------|
|                |                                                      |
+-----------------------------------------------------------------------+

The New Iterator Requirements

Notation

X    The iterator type.                                             
T    The value type of X, i.e., std::iterator_traits<X>::value_type.
x, y An object of type X.                                           
t    An object of type T.                                           

-------------------------------------------------------------------------

Readable Iterator

A Readable Iterator is an iterator that dereferences to produce an rvalue
that is convertible to the value_type of the iterator.

Associated Types

+-----------------------------------------------------------------------+
|Value    |std::             |The type of the objects pointed to by the |
|type     |iterator_traits   |iterator.                                 |
|         |<X>::value_type   |                                          |
|---------+------------------+------------------------------------------|
|Reference|std::             |The return type of dereferencing the      |
|type     |iterator_traits   |iterator. This type must be convertible to|
|         |<X>::reference    |T.                                        |
|---------+------------------+------------------------------------------|
|Return   |std::             |A type convertible to std::               |
|Category |return_category   |readable_iterator_tag                     |
|         |<X>::type         |                                          |
+-----------------------------------------------------------------------+

Refinement of

Copy Constructible

Valid expressions

+-----------------------------------------------------------------------+
|   Name    |Expression|     Type     |           Return type           |
|           |          | requirements |                                 |
|-----------+----------+--------------+---------------------------------|
|Dereference|*x        |              |std::iterator_traits<X>::        |
|           |          |              |reference                        |
|-----------+----------+--------------+---------------------------------|
|Member     |          |T is a type   |If m is a data member, the type  |
|access     |x->m      |with a member |of m. If m is a member function, |
|           |          |named m.      |the return type of m.            |
+-----------------------------------------------------------------------+

-------------------------------------------------------------------------

Writable Iterator

A Writable Iterator is an iterator that can be used to store a value
using the dereference-assignment expression.

Definitions

If x is an Writable Iterator of type X, then the expression *x = a;
stores the value a into x. Note that operator=, like other C++ functions,
may be overloaded; it may, in fact, even be a template function. In
general, then, a may be any of several different types. A type A belongs
to the set of value types of X if, for an object a of type A, *x = a; is
well-defined and does not require performing any non-trivial conversions
on a.

Associated Types

+-----------------------------------------------------------------------+
|Return     |std::return_category  |A type convertible to std::         |
|Category   |<X>::type             |writable_iterator_tag               |
+-----------------------------------------------------------------------+

Refinement of

Copy Constructible

Valid expressions

+---------------------------------------------+
|         Name         |Expression|Return type|
|----------------------+----------+-----------|
|Dereference assignment|*x = a    |unspecified|
+---------------------------------------------+

-------------------------------------------------------------------------

Swappable Iterator

A Swappable Iterator is an iterator whose dereferenced values can be
swapped.

Note: the requirements for Swappable Iterator are dependent on the issues
surrounding std::swap() being resolved. Here we assume that the issue
will be resolved by allowing the overload of std::swap() for user-defined
types.

Note: Readable Iterator and Writable Iterator combined implies Swappable
Iterator because of the fully templated std::swap(). However, Swappable
Iterator does not imply Readable Iterator nor Writable Iterator.

Associated Types

+-----------------------------------------------------------------------+
|Return     |std::return_category  |A type convertible to std::         |
|Category   |<X>::type             |swappable_iterator_tag              |
+-----------------------------------------------------------------------+

Valid expressions

Of the two valid expressions listed below, only one OR the other is
required. If std::iter_swap() is overloaded for X then std::swap() is not
required. If std::iter_swap() is not overloaded for X then the default
(fully templated) version is used, which will call std::swap() (this
means changing the current requirements for std::iter_swap()).

+-----------------------------------------------------+
|        Name        |     Expression     |Return type|
|--------------------+--------------------+-----------|
|Iterator Swap       |std::iter_swap(x, y)|void       |
|--------------------+--------------------+-----------|
|Dereference and Swap|std::swap(*x, *y)   |void       |
+-----------------------------------------------------+

-------------------------------------------------------------------------

Constant Lvalue Iterator

A Constant Lvalue Iterator is an iterator that dereferences to produce a
const reference to the pointed-to object, i.e., the associated reference
type is const T&. Changing the value of or destroying an iterator that
models Constant Lvalue Iterator does not invalidate pointers and
references previously obtained from that iterator.

Refinement of

Readable Iterator

Associated Types

+-----------------------------------------------------------------------+
|Reference|std::iterator_traits|The return type of dereferencing the    |
|type     |<X>::reference      |iterator, which must be const T&.       |
|---------+--------------------+----------------------------------------|
|Return   |std::return_category|A type convertible to std::             |
|Category |<X>::type           |constant_lvalue_iterator_tag            |
+-----------------------------------------------------------------------+

-------------------------------------------------------------------------

Mutable Lvalue Iterator

A Mutable Lvalue Iterator is an iterator that dereferences to produce a
reference to the pointed-to object. The associated reference type is T&.
Changing the value of or destroying an iterator that models Mutable
Lvalue Iterator does not invalidate pointers and references previously
obtained from that iterator.

Refinement of

Readable Iterator, Writable Iterator, and Swappable Iterator.

Associated Types

+-----------------------------------------------------------------------+
|Reference|std::iterator_traits |The return type of dereferencing the   |
|type     |<X>::reference       |iterator, which must be T&.            |
|---------+---------------------+---------------------------------------|
|Return   |std::return_category |A type convertible to std::            |
|Category |<X>::type            |mutable_lvalue_iterator_tag            |
+-----------------------------------------------------------------------+

-------------------------------------------------------------------------

Forward Traversal Iterator

The Forward Iterator is an iterator that can be incremented. Also, it is
permissible to make multiple passes through the iterator's range.

Refinement of

Copy Constructible, Assignable, Default Constructible, and Equality
Comparable

Associated types

+-----------------------------------------------------------------------+
|          |std::             |A signed integral type used for          |
|Difference|iterator_traits   |representing distances between iterators |
|Type      |<X>::             |that point into the same range.          |
|          |difference_type   |                                         |
|----------+------------------+-----------------------------------------|
|Traversal |std::             |A type convertible to std::              |
|Category  |traversal_category|forward_traversal_tag                    |
|          |<X>::type         |                                         |
+-----------------------------------------------------------------------+

Valid expressions

+------------------------------------------------------------------+
|    Name     |Expression|Type requirements|      Return type      |
|-------------+----------+-----------------+-----------------------|
|Preincrement |++i       |                 |X&                     |
|-------------+----------+-----------------+-----------------------|
|Postincrement|i++       |                 |convertible to const X&|
+------------------------------------------------------------------+

-------------------------------------------------------------------------

Bidirectional Traversal Iterator

An iterator that can be incremented and decremented.

Refinement of

Forward Traversal Iterator

Associated types

+-----------------------------------------------------------------------+
|Traversal   |std::                |A type convertible to std::         |
|Category    |traversal_category   |bidirectional_traversal_tag         |
|            |<X>::type            |                                    |
+-----------------------------------------------------------------------+

Valid expressions

+------------------------------------------------------------------+
|    Name     |Expression|Type requirements|      Return type      |
|-------------+----------+-----------------+-----------------------|
|Predecrement |--i       |                 |X&                     |
|-------------+----------+-----------------+-----------------------|
|Postdecrement|i--       |                 |convertible to const X&|
+------------------------------------------------------------------+

-------------------------------------------------------------------------

Random Access Traversal Iterator

An iterator that provides constant-time methods for moving forward and
backward in arbitrary-sized steps.

Refinement of

Bidirectional Traversal Iterator and Less Than Comparable where < is a
total ordering

Associated types

+-----------------------------------------------------------------------+
|Traversal   |std::                |A type convertible to std::         |
|Category    |traversal_category   |random_access_traversal_tag         |
|            |<X>::type            |                                    |
+-----------------------------------------------------------------------+

Valid expressions

+-----------------------------------------------------------------------+
|   Name    |Expression|    Type requirements    |     Return type      |
|-----------+----------+-------------------------+----------------------|
|Iterator   |i += n    |                         |X&                    |
|addition   |          |                         |                      |
|-----------+----------+-------------------------+----------------------|
|Iterator   |i + n or n|                         |X                     |
|addition   |+ i       |                         |                      |
|-----------+----------+-------------------------+----------------------|
|Iterator   |i -= n    |                         |X&                    |
|subtraction|          |                         |                      |
|-----------+----------+-------------------------+----------------------|
|Iterator   |i - n     |                         |X                     |
|subtraction|          |                         |                      |
|-----------+----------+-------------------------+----------------------|
|Difference |i - j     |                         |std::iterator_traits  |
|           |          |                         |<X>::difference_type  |
|-----------+----------+-------------------------+----------------------|
|Element    |i[n]      |X must also be a model of|std::iterator_traits  |
|operator   |          |Readable Iterator.       |<X>::reference        |
|-----------+----------+-------------------------+----------------------|
|Element    |i[n] = t  |X must also be a model of|unspecified           |
|assignment |          |Writable Iterator.       |                      |
+-----------------------------------------------------------------------+

-------------------------------------------------------------------------