 

Category: iterators   Component type: concept 
Description
A Random Access Iterator is an iterator that provides both increment and decrement (just like a BidirectionalIterator), and that also provides constanttime methods for moving forward and backward in arbitrarysized steps. Random Access Iterators provide essentially all of the operations of ordinary C pointer arithmetic.
Refinement of
BidirectionalIterator, LessThanComparable
Associated types
The same as for BidirectionalIterator
Notation
X  A type that is a model of Random Access Iterator 
T  The value type of X 
Distance  The distance type of X 
i , j  Object of type X 
t  Object of type T 
n  Object of type Distance 
Definitions
Valid expressions
In addition to the expressions defined in BidirectionalIterator, the following expressions must be valid.
Name  Expression  Type requirements  Return type 
Iterator addition  i += n   X& 
Iterator addition  i + n or n + i   X 
Iterator subtraction  i = n   X& 
Iterator subtraction  i  n   X 
Difference  i  j   Distance 
Element operator  i[n]   Convertible to T 
Element assignment  i[n] = t  X is mutable  Convertible to T 
Expression semantics
Semantics of an expression is defined only where it differs from, or is not defined in, BidirectionalIterator or LessThanComparable.
Name  Expression  Precondition  Semantics  Postcondition 
Forward motion  i += n  Including i itself, there must be n dereferenceable or pasttheend iterators following or preceding i , depending on whether n is positive or negative.  If n > 0 , equivalent to executing ++i n times. If n < 0 , equivalent to executing i n times. If n == 0 , this is a null operation. [1]  i is dereferenceable or pasttheend. 
Iterator addition  i + n or n + i  Same as for i += n  Equivalent to { X tmp = i; return tmp += n; } . The two forms i + n and n + i are identical.  Result is dereferenceable or pasttheend 
Iterator subtraction  i = n  Including i itself, there must be n dereferenceable or pasttheend iterators preceding or following i , depending on whether n is positive or negative.  Equivalent to i += (n) .  i is dereferenceable or pasttheend. 
Iterator subtraction  i  n  Same as for i = n  Equivalent to { X tmp = i; return tmp = n; } .  Result is dereferenceable or pasttheend 
Difference  i  j  Either i is reachable from j or j is reachable from i , or both.  Returns a number n such that i == j + n  
Element operator  i[n]  i + n exists and is dereferenceable.  Equivalent to *(i + n) [2]  
Element assignment  i[n] = t  i + n exists and is dereferenceable.  Equivalent to *(i + n) = t [2]  i[n] is a copy of t . 
Less  i < j  Either i is reachable from j or j is reachable from i , or both. [3]  As described in LessThanComparable [4]  
Complexity guarantees
All operations on Random Access Iterators are amortized constant time. [5]
Invariants
Symmetry of addition and subtraction  If i + n is welldefined, then i += n; i = n; and (i + n)  n are null operations. Similarly, if i  n is welldefined, then i = n; i += n; and (i  n) + n are null operations. 
Relation between distance and addition  If i  j is welldefined, then i == j + (i  j) . 
Reachability and distance  If i is reachable from j , then i  j >= 0 . 
Ordering  operator < is a strict weak ordering, as defined in LessThanComparable. 
Models
Notes
[1] "Equivalent to" merely means that i += n
yields the same iterator as if i
had been incremented (decremented) n
times. It does not mean that this is how operator+=
should be implemented; in fact, this is not a permissible implementation. It is guaranteed that i += n
is amortized constant time, regardless of the magnitude of n
. [5]
[2] One minor syntactic oddity: in C, if p
is a pointer and n
is an int, then p[n]
and n[p]
are equivalent. This equivalence is not guaranteed, however, for Random Access Iterators: only i[n]
need be supported. This isn't a terribly important restriction, though, since the equivalence of p[n]
and n[p]
has essentially no application except for obfuscated C contests.
[3] The precondition defined in LessThanComparable is that i
and j
be in the domain of operator <
. Essentially, then, this is a definition of that domain: it is the set of pairs of iterators such that one iterator is reachable from the other.
[4] All of the other comparison operators have the same domain and are defined in terms of operator <
, so they have exactly the same semantics as described in LessThanComparable.
[5] This complexity guarantee is in fact the only reason why Random Access Iterator exists as a distinct concept. Every operation in iterator arithmetic can be defined for BidirectionalIterator; in fact, that is exactly what the algorithms advance
and distance
do. The distinction is simply that the BidirectionalIterator implementations are linear time, while Random Access Iterators are required to support random access to elements in amortized constant time. This has major implications for the sorts of algorithms that can sensibly be written using the two types of iterators.
See also
LessThanComparable, trivial, BidirectionalIterator, Iterators