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