new-iter-concepts.rst

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

|Forward Traversal Iterator Requirements (in addition to Default Constructible and Single Pass Iterator) |
+---------------------------------------+-----------------------------------+----------------------------+
|Expression                             |Return Type                        |Assertion/Note              |
+=======================================+===================================+============================+
|``X u;``                               |``X&``                             |note: ``u`` may have a      |
|                                       |                                   |singular value.             |
+---------------------------------------+-----------------------------------+----------------------------+
|``++r``                                |``X&``                             |``r == s`` and ``r`` is     |
|                                       |                                   |dereferenceable implies     |
|                                       |                                   |``++r == ++s.``             |
+---------------------------------------+-----------------------------------+----------------------------+
|``iterator_traversal<X>::type``        |Convertible to                     |                            |
|                                       |``forward_traversal_tag``          |                            |
+---------------------------------------+-----------------------------------+----------------------------+



.. TR1: forward_traversal_iterator_tag changed to
   forward_traversal_tag for consistency


Bidirectional Traversal Iterators [lib.bidirectional.traversal.iterators]
-------------------------------------------------------------------------

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

+-----------------------------------------------------------------------------------------------------+
|Bidirectional Traversal Iterator Requirements (in addition to Forward Traversal                      |
|Iterator)                                                                                            |
+--------------------------------+-------------------------------+--------------+---------------------+
|Expression                      |Return Type                    |  Operational |Assertion/           |
|                                |                               |  Semantics   |Pre-/Post-condition  |
+================================+===============================+==============+=====================+
|``--r``                         |``X&``                         |              |pre: there exists    |
|                                |                               |              |``s`` such that ``r  |
|                                |                               |              |== ++s``.  post:     |
|                                |                               |              |``s`` is             |
|                                |                               |              |dereferenceable.     |
|                                |                               |              |                     |
|                                |                               |              |``++(--r) == r``.    |
|                                |                               |              |``--r == --s``       |
|                                |                               |              |implies ``r ==       |
|                                |                               |              |s``. ``&r == &--r``. |
+--------------------------------+-------------------------------+--------------+---------------------+
|``r--``                         |convertible to ``const X&``    |::            |                     |
|                                |                               |              |                     |
|                                |                               | {            |                     |
|                                |                               |   X tmp = r; |                     |
|                                |                               |   --r;       |                     |
|                                |                               |   return tmp;|                     |
|                                |                               | }            |                     |
+--------------------------------+-------------------------------+--------------+---------------------+
|``iterator_traversal<X>::type`` |Convertible to                 |              |                     |
|                                |``bidirectional_traversal_tag``|              |                     |
|                                |                               |              |                     |
+--------------------------------+-------------------------------+--------------+---------------------+

.. TR1: bidirectional_traversal_iterator_tag changed to
   bidirectional_traversal_tag for consistency

Random Access Traversal Iterators [lib.random.access.traversal.iterators]
-------------------------------------------------------------------------

A class or built-in type ``X`` models the *Random Access Traversal
Iterator* concept if the following expressions are valid and respect
the stated semantics.  In the table below, ``Distance`` is
``iterator_traits<X>::difference_type`` and ``n`` represents a
constant object of type ``Distance``.

+------------------------------------------------------------------------------------------------------------------+
|Random Access Traversal Iterator Requirements (in addition to Bidirectional Traversal Iterator)                   |
+-------------------------------+---------------------------------+-------------------------+----------------------+
|Expression                     |Return Type                      |Operational Semantics    |Assertion/            |
|                               |                                 |                         |Precondition          |
+===============================+=================================+=========================+======================+
|``r += n``                     |``X&``                           |::                       |                      |
|                               |                                 |                         |                      |
|                               |                                 | {                       |                      |
|                               |                                 |   Distance m = n;       |                      |
|                               |                                 |   if (m >= 0)           |                      |
|                               |                                 |     while (m--)         |                      |
|                               |                                 |       ++r;              |                      |
|                               |                                 |   else                  |                      |
|                               |                                 |     while (m++)         |                      |
|                               |                                 |       --r;              |                      |
|                               |                                 |   return r;             |                      |
|                               |                                 | }                       |                      |
+-------------------------------+---------------------------------+-------------------------+----------------------+
|``a + n``, ``n + a``           |``X``                            |``{ X tmp = a; return tmp|                      |
|                               |                                 |+= n; }``                |                      |
|                               |                                 |                         |                      |
+-------------------------------+---------------------------------+-------------------------+----------------------+
|``r -= n``                     |``X&``                           |``return r += -n``       |                      |
+-------------------------------+---------------------------------+-------------------------+----------------------+
|``a - n``                      |``X``                            |``{ X tmp = a; return tmp|                      |
|                               |                                 |-= n; }``                |                      |
|                               |                                 |                         |                      |
+-------------------------------+---------------------------------+-------------------------+----------------------+
|``b - a``                      |``Distance``                     |``a < b ?  distance(a,b) |pre: there exists a   |
|                               |                                 |: -distance(b,a)``       |value ``n`` of        |
|                               |                                 |                         |``Distance`` such that|
|                               |                                 |                         |``a + n == b``.  ``b  |
|                               |                                 |                         |== a + (b - a)``.     |
+-------------------------------+---------------------------------+-------------------------+----------------------+
|``a[n]``                       |convertible to T                 |``*(a + n)``             |pre: a is a `Readable |
|                               |                                 |                         |Iterator`_            |
+-------------------------------+---------------------------------+-------------------------+----------------------+
|``a[n] = v``                   |convertible to T                 |``*(a + n) = v``         |pre: a is a `Writable |
|                               |                                 |                         |Iterator`_            |
+-------------------------------+---------------------------------+-------------------------+----------------------+
|``a < b``                      |convertible to ``bool``          |``b - a > 0``            |``<`` is a total      |
|                               |                                 |                         |ordering relation     |
+-------------------------------+---------------------------------+-------------------------+----------------------+
|``a > b``                      |convertible to ``bool``          |``b < a``                |``>`` is a total      |
|                               |                                 |                         |ordering relation     |
+-------------------------------+---------------------------------+-------------------------+----------------------+
|``a >= b``                     |convertible to ``bool``          |``!(a < b)``             |                      |
+-------------------------------+---------------------------------+-------------------------+----------------------+
|``a <= b``                     |convertible to ``bool``          |``!(a > b)``             |                      |
+-------------------------------+---------------------------------+-------------------------+----------------------+
|``iterator_traversal<X>::type``|Convertible to                   |                         |                      |
|                               |``random_access_traversal_tag``  |                         |                      |
+-------------------------------+---------------------------------+-------------------------+----------------------+

.. TR1: random_access_traversal_iterator_tag changed to
   random_access_traversal_tag for consistency


Interoperable Iterators [lib.interoperable.iterators]
-----------------------------------------------------

A class or built-in type ``X`` that models Single Pass Iterator is
*interoperable with* a class or built-in type ``Y`` that also models
Single Pass Iterator if the following expressions are valid and
respect the stated semantics. In the tables below, ``x`` is an object
of type ``X``, ``y`` is an object of type ``Y``, ``Distance`` is
``iterator_traits<Y>::difference_type``, and ``n`` represents a
constant object of type ``Distance``.

+-----------+-----------------------+---------------------------------------------------+
|Expression |Return Type            |Assertion/Precondition/Postcondition               |
+===========+=======================+===================================================+
|``y = x``  |``Y``                  |post: ``y == x``                                   |
+-----------+-----------------------+---------------------------------------------------+
|``Y(x)``   |``Y``                  |post: ``Y(x) == x``                                |
+-----------+-----------------------+---------------------------------------------------+
|``x == y`` |convertible to ``bool``|``==`` is an equivalence relation over its domain. |
+-----------+-----------------------+---------------------------------------------------+
|``y == x`` |convertible to ``bool``|``==`` is an equivalence relation over its domain. |
+-----------+-----------------------+---------------------------------------------------+
|``x != y`` |convertible to ``bool``|``bool(a==b) != bool(a!=b)`` over its domain.      |
+-----------+-----------------------+---------------------------------------------------+
|``y != x`` |convertible to ``bool``|``bool(a==b) != bool(a!=b)`` over its domain.      |
+-----------+-----------------------+---------------------------------------------------+

If ``X`` and ``Y`` both model Random Access Traversal Iterator then
the following additional requirements must be met.

+-----------+-----------------------+---------------------+--------------------------------------+
|Expression |Return Type            |Operational Semantics|Assertion/ Precondition               |
+===========+=======================+=====================+======================================+
|``x < y``  |convertible to ``bool``|``y - x > 0``        |``<`` is a total ordering relation    |
+-----------+-----------------------+---------------------+--------------------------------------+
|``y < x``  |convertible to ``bool``|``x - y > 0``        |``<`` is a total ordering relation    |
+-----------+-----------------------+---------------------+--------------------------------------+
|``x > y``  |convertible to ``bool``|``y < x``            |``>`` is a total ordering relation    |
+-----------+-----------------------+---------------------+--------------------------------------+
|``y > x``  |convertible to ``bool``|``x < y``            |``>`` is a total ordering relation    |
+-----------+-----------------------+---------------------+--------------------------------------+
|``x >= y`` |convertible to ``bool``|``!(x < y)``         |                                      |
+-----------+-----------------------+---------------------+--------------------------------------+
|``y >= x`` |convertible to ``bool``|``!(y < x)``         |                                      |
+-----------+-----------------------+---------------------+--------------------------------------+
|``x <= y`` |convertible to ``bool``|``!(x > y)``         |                                      |
+-----------+-----------------------+---------------------+--------------------------------------+
|``y <= x`` |convertible to ``bool``|``!(y > x)``         |                                      |
+-----------+-----------------------+---------------------+--------------------------------------+
|``y - x``  |``Distance``           |``distance(Y(x),y)`` |pre: there exists a value ``n`` of    |
|           |                       |                     |``Distance`` such that ``x + n == y``.|
|           |                       |                     |``y == x + (y - x)``.                 |
+-----------+-----------------------+---------------------+--------------------------------------+ 
|``x - y``  |``Distance``           |``distance(y,Y(x))`` |pre: there exists a value ``n`` of    |
|           |                       |                     |``Distance`` such that ``y + n == x``.|
|           |                       |                     |``x == y + (x - y)``.                 |
+-----------+-----------------------+---------------------+--------------------------------------+



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


::

  // 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 { };

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

The ``is_readable_iterator`` class
template satisfies the UnaryTypeTrait_ requirements.  

Given an iterator type ``X``, ``is_readable_iterator<X>::value``
yields ``true`` if, for an object ``a`` of type ``X``, ``*a`` is
convertible to ``iterator_traits<X>::value_type``, and ``false``
otherwise.

``iterator_traversal<X>::type`` is 

.. parsed-literal::

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

where *category-to-traversal* is defined as follows

.. _`category-to-traversal`:

.. parsed-literal::

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

.. _UnaryTypeTrait: n1519_

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

.. _n1519: http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/papers/2003/n1519.htm

..
 LocalWords:  Abrahams Siek Witt const bool Sutter's WG int UL LI href Lvalue
 LocalWords:  ReadableIterator WritableIterator SwappableIterator cv pre iter
 LocalWords:  ConstantLvalueIterator MutableLvalueIterator CopyConstructible TR
 LocalWords:  ForwardTraversalIterator BidirectionalTraversalIterator lvalue
 LocalWords:  RandomAccessTraversalIterator dereferenceable Incrementable tmp
 LocalWords:  incrementable xxx min prev inplace png oldeqnew AccessTag struct
 LocalWords:  TraversalTag typename lvalues DWA Hmm JGS mis enum