boost_1_45_0/libs/iterator/doc/RandomAccessTraversal.rst

.. Copyright David Abrahams 2006. Distributed under the Boost
.. Software License, Version 1.0. (See accompanying
.. file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)

Random Access Traversal Concept
...............................

A class or built-in type ``X`` models the *Random Access Traversal*
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)                            |
+-------------------------------+---------------------------------+-------------------------+----------------------+
|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``  |                         |                      |
+-------------------------------+---------------------------------+-------------------------+----------------------+