new-iter-concepts.rst

Boost provides free peer-reviewed portable C++ source libraries. We emphasize libraries that work

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

.. image:: traversal.png

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.

.. image:: oldeqnew.png

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.

.. dwa2003/1/2: Note that we are not *requiring* convertibility to
   a new-style traversal tag in order to meet new concepts.
   Old-style iterators still fit, after all.

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

Addition to [lib.iterator.requirements]
=======================================

Iterator Value Access Concepts [lib.iterator.value.access]
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

In the tables below, ``X`` is an iterator type, ``a`` is a constant
object of type ``X``, ``R`` is
``std::iterator_traits<X>::reference``, ``T`` is
``std::iterator_traits<X>::value_type``, and ``v`` is a constant
object of type ``T``.

.. _Readable Iterator:

Readable Iterators [lib.readable.iterators]
-------------------------------------------

A class or built-in type ``X`` models the *Readable Iterator* concept
for value type ``T`` if, in addition to ``X`` being Assignable and
Copy Constructible, the following expressions are valid and respect
the stated semantics. ``U`` is the type of any specified member of
type ``T``.

+-----------------------------------------------------------------------------------------------------------------------------+
|Readable Iterator Requirements (in addition to Assignable and Copy Constructible)                                            |
+-----------------------------------+------------------------+----------------------------------------------------------------+
|Expression                         |Return Type             |Note/Precondition                                               |
+===================================+========================+================================================================+
|``iterator_traits<X>::value_type`` |``T``                   |Any non-reference,                                              |
|                                   |                        |non-cv-qualified type                                           |
+-----------------------------------+------------------------+----------------------------------------------------------------+
|``*a``                             | Convertible to ``T``   |pre: ``a`` is dereferenceable. If ``a == b`` then ``*a``        |
|                                   |                        | is equivalent to ``*b``.                                       |
+-----------------------------------+------------------------+----------------------------------------------------------------+
|``a->m``                           |``U&``                  |pre: ``pre: (*a).m`` is well-defined. Equivalent to ``(*a).m``. |
+-----------------------------------+------------------------+----------------------------------------------------------------+

.. We won't say anything about iterator_traits<X>::reference until the DR is resolved. -JGS

.. _Writable Iterator:

Writable Iterators [lib.writable.iterators]
-------------------------------------------

A class or built-in type ``X`` models the *Writable Iterator* concept
if, in addition to ``X`` being Copy Constructible, the following
expressions are valid and respect the stated semantics.  Writable
Iterators have an associated *set of value types*.

+---------------------------------------------------------------------+
|Writable Iterator Requirements (in addition to Copy Constructible)   |
+-------------------------+--------------+----------------------------+
|Expression               |Return Type   |Precondition                |
+=========================+==============+============================+
|``*a = o``               |              | pre: The type of ``o``     |
|                         |              | is in the set of           |
|                         |              | value types of ``X``       |
+-------------------------+--------------+----------------------------+

Swappable Iterators [lib.swappable.iterators]
---------------------------------------------

A class or built-in type ``X`` models the *Swappable Iterator* concept
if, in addition to ``X`` being Copy Constructible, the following
expressions are valid and respect the stated semantics.

+---------------------------------------------------------------------+
|Swappable Iterator Requirements (in addition to Copy Constructible)  |
+-------------------------+-------------+-----------------------------+
|Expression               |Return Type  |Postcondition                |
+=========================+=============+=============================+
|``iter_swap(a, b)``      |``void``     |the pointed to values are    |
|                         |             |exchanged                    |
+-------------------------+-------------+-----------------------------+

[*Note:* An iterator that is a model of the `Readable Iterator`_ and
`Writable Iterator`_ concepts is also a model of *Swappable
Iterator*.  *--end note*]


Lvalue Iterators [lib.lvalue.iterators]
---------------------------------------

The *Lvalue Iterator* concept adds the requirement that the return
type of ``operator*`` type be a reference to the value type of the
iterator.  

+-------------------------------------------------------------+
| Lvalue Iterator Requirements                                |
+-------------+-----------+-----------------------------------+
|Expression   |Return Type|Note/Assertion                     |
+=============+===========+===================================+
|``*a``       | ``T&``    |``T`` is *cv*                      |
|             |           |``iterator_traits<X>::value_type`` |
|             |           |where *cv* is an optional          |
|             |           |cv-qualification.  pre: ``a`` is   |
|             |           |dereferenceable.                   |
+-------------+-----------+-----------------------------------+

If ``X`` is a `Writable Iterator`_ then ``a == b`` if and only if
``*a`` is the same object as ``*b``.  If ``X`` is a `Readable
Iterator`_ then ``a == b`` implies ``*a`` is the same object as
``*b``.


Iterator Traversal Concepts [lib.iterator.traversal]
++++++++++++++++++++++++++++++++++++++++++++++++++++

In the tables below, ``X`` is an iterator type, ``a`` and ``b`` are
constant objects of type ``X``, ``r`` and ``s`` are mutable objects of
type ``X``, ``T`` is ``std::iterator_traits<X>::value_type``, and
``v`` is a constant object of type ``T``.

Incrementable Iterators [lib.incrementable.iterators]
-----------------------------------------------------

A class or built-in type ``X`` models the *Incrementable Iterator*
concept if, in addition to ``X`` being Assignable and Copy
Constructible, the following expressions are valid and respect the
stated semantics.

+------------------------------------------------------------------------------------+
|Incrementable Iterator Requirements (in addition to Assignable, Copy Constructible) |
|                                                                                    |
+--------------------------------+-------------------------------+-------------------+
|Expression                      |Return Type                    |Assertion          |
+================================+===============================+===================+
|``++r``                         |``X&``                         |``&r == &++r``     |
+--------------------------------+-------------------------------+-------------------+
|``r++``                         |                               |                   |
+--------------------------------+-------------------------------+-------------------+
|``*r++``                        |                               |                   |
+--------------------------------+-------------------------------+-------------------+
|``iterator_traversal<X>::type`` |Convertible to                 |                   |
|                                |``incrementable_traversal_tag``|                   |
+--------------------------------+-------------------------------+-------------------+


If ``X`` is a `Writable Iterator`_ then ``X a(r++);`` is equivalent
to ``X a(r); ++r;`` and ``*r++ = o`` is equivalent
to  ``*r = o; ++r``.
If ``X`` is a `Readable Iterator`_ then ``T z(*r++);`` is equivalent
to ``T z(*r); ++r;``. 

.. TR1: incrementable_iterator_tag changed to
   incrementable_traversal_tag for consistency.

Single Pass Iterators [lib.single.pass.iterators]
-------------------------------------------------

A class or built-in type ``X`` models the *Single Pass Iterator*
concept if the following expressions are valid and respect the stated
semantics.


+----------------------------------------------------------------------------------------------------------------+
|Single Pass Iterator Requirements (in addition to Incrementable Iterator and Equality Comparable)               |
|                                                                                                                |
+----------------------------------------+-----------------------------+-------------+---------------------------+
|Expression                              |Return Type                  | Operational |Assertion/                 | 
|                                        |                             | Semantics   |Pre-/Post-condition        |
+========================================+=============================+=============+===========================+
|``++r``                                 |``X&``                       |             |pre: ``r`` is              |
|                                        |                             |             |dereferenceable; post:     |
|                                        |                             |             |``r`` is dereferenceable or|
|                                        |                             |             |``r`` is past-the-end      |
+----------------------------------------+-----------------------------+-------------+---------------------------+
|``a == b``                              |convertible to ``bool``      |             |``==`` is an equivalence   |
|                                        |                             |             |relation over its domain   |
+----------------------------------------+-----------------------------+-------------+---------------------------+
|``a != b``                              |convertible to ``bool``      |``!(a == b)``|                           |
+----------------------------------------+-----------------------------+-------------+---------------------------+
|``iterator_traits<X>::difference_type`` |A signed integral type       |             |                           |
|                                        |representing the distance    |             |                           |
|                                        |between iterators            |             |                           |
+----------------------------------------+-----------------------------+-------------+---------------------------+
|``iterator_traversal<X>::type``         |Convertible to               |             |                           |
|                                        |``single_pass_traversal_tag``|             |                           |
+----------------------------------------+-----------------------------+-------------+---------------------------+

.. TR1: single_pass_iterator_tag changed to
   single_pass_traversal_tag for consistency


Forward Traversal Iterators [lib.forward.traversal.iterators]
-------------------------------------------------------------

A class or built-in type ``X`` models the *Forward Traversal Iterator*
concept if, in addition to ``X`` meeting the requirements of Default
Constructible and Single Pass Iterator, the following expressions are
valid and respect the stated semantics. 

+--------------------------------------------------------------------------------------------------------+