.. Iterators/Concepts//Random Access Iterator |30

Random Access Iterator
======================

Description
-----------

A |Random Access Iterator| is a |Bidirectional Iterator| that provides 
constant-time guarantees on moving the iterator an arbitrary number of positions
forward or backward and for measuring the distance to another iterator in the 
same sequence.

Refinement of
-------------

|Bidirectional Iterator|


Expression requirements
-----------------------

In addition to the requirements defined in |Bidirectional Iterator|, 
the following requirements must be met. 

+---------------------------+-------------------------------------------+---------------------------+
| Expression                | Type                                      | Complexity                |
+===========================+===========================================+===========================+
| ``next<i>::type``         | |Random Access Iterator|                  | Amortized constant time   |
+---------------------------+-------------------------------------------+---------------------------+
| ``prior<i>::type``        | |Random Access Iterator|                  | Amortized constant time   |
+---------------------------+-------------------------------------------+---------------------------+
| ``i::category``           | |Integral Constant|, convertible          | Constant time             |
|                           | to ``random_access_iterator_tag``         |                           |
+---------------------------+-------------------------------------------+---------------------------+
| ``advance<i,n>::type``    | |Random Access Iterator|                  | Amortized constant time   |
+---------------------------+-------------------------------------------+---------------------------+
| ``distance<i,j>::type``   | |Integral Constant|                       | Amortized constant time   |
+---------------------------+-------------------------------------------+---------------------------+


Expression semantics
--------------------

.. parsed-literal::

    typedef advance<i,n>::type j;

:Semantics:
    See ``advance`` specification
    

.. ..........................................................................

.. parsed-literal::

    typedef distance<i,j>::type n;

:Semantics:
    See ``distance`` specification


Invariants
----------

For any random access iterators ``i`` and ``j`` the following invariants always 
hold: 

* If ``advance<i,n>::type`` is well-defined, then 
  ``advance< advance<i,n>::type, negate<n>::type >::type`` is a null operation. 


See also
--------

|Iterators|, |Bidirectional Iterator|, |Random Access Sequence|, |advance|, |distance|