Category: iterators
Component type: concept
A Random Access Iterator LOGN is an iterator that provides both increment and decrement (just like a Bidirectional Iterator), and that also provides logarithmic-time methods for moving forward and backward in arbitrary-sized steps. Random Access Iterators LOGN provide essentially all of the operations of ordinary C pointer arithmetic.
A Random Access Iterator LOGN is identical to a Random Access Iterator except that the performance requirement has been changed to logarithmic time for moving forward and backward in arbitrary-sized steps. Incrementing and decrementing remain constant time operations.
Bidirectional Iterator, LessThan Comparable
The same as for Bidirectional Iterator
X | A type that is a model of Random Access Iterator LOGN |
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 |
In addition to the expressions defined in Bidirectional Iterator, 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 |
Semantics of an expression is defined only where it differs from, or is not defined in, Bidirectional Iterator or LessThan Comparable.
Name | Expression | Precondition | Semantics | Postcondition |
---|---|---|---|---|
Forward motion | i += n | Including i itself, there must be n dereferenceable or past-the-end 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 past-the-end. |
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 past-the-end |
Iterator subtraction | i -= n | Including i itself, there must be n dereferenceable or past-the-end iterators preceding or following i , depending on whether n is positive or negative. | Equivalent to i += (-n) . | i is dereferenceable or past-the-end. |
Iterator subtraction | i - n | Same as for i -= n | Equivalent to { X tmp = i; return tmp -= n; } . | Result is dereferenceable or past-the-end |
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 LessThan Comparable [4] |
Incrementing and decrementing are amortized constant time. Moving forward and backward by arbitrary-sized steps are amortized logarithmic time. [5]
Symmetry of addition and subtraction | If i + n is well-defined, then i += n; i -= n; and (i + n) - n are null operations. Similarly, if i - n is well-defined, then i -= n; i += n; and (i - n) + n are null operations. |
Relation between distance and addition | If i - j is well-defined, 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 LessThan Comparable. |
T*
IndexedSkipList< T, R >::iterator
IndexedSkipList< T, R >::const_iterator
AutoSkipList< T, Pr, R >::iterator
AutoSkipList< T, Pr, R >::const_iterator
MultiAutoSkipList< T, Pr, R >::iterator
MultiAutoSkipList< T, Pr, R >::const_iterator
AutoKeyedSkipList< K, T, Pr, R >::iterator
AutoKeyedSkipList< K, T, Pr, R >::const_iterator
MultiAutoKeyedSkipList< K, T, Pr, R >::iterator
MultiAutoKeyedSkipList< K, T, Pr, R >::const_iterator
XIndexedSkipList< X, CT >::iterator
XIndexedSkipList< X, CT >::const_iterator
XMultiAutoSkipList< X, CT, Pr >::iterator
XMultiAutoSkipList< X, CT, Pr >::const_iterator
AutoAccessSkipList< K, T, A, Pr, R >::iterator
AutoAccessSkipList< K, T, A, Pr, R >::const_iterator
MultiAutoAccessSkipList< K, T, A, Pr, R >::iterator
MultiAutoAccessSkipList< K, T, A, Pr, R >::const_iterator
XMultiAutoAccessSkipList< X, K, CT, A, Pr >::iterator
[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 LessThan Comparable 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 LessThan Comparable.
[5] This complexity guarantee is in fact the only reason why Random Access Iterator LOGN exists as a distinct concept. Every operation in iterator arithmetic can be defined for Bidirectional Iterator; in fact, that is exactly what the algorithms advance
and distance
do. The distinction is simply that the Bidirectional Iterator implementations are linear time, while Random Access Iterators LOGN are required to support random access to elements in amortized logarithmic time. This has major implications for the sorts of algorithms that can sensibly be written using the two types of iterators.
AutoSkipList, AutoKeyedSkipList, MultiAutoSkipList, MultiAutoKeyedSkipList, IndexedSkipList, XIndexedSkipList, XMultiAutoSkipList, AutoAccessSkipList, MultiAutoAccessSkipList, XMultiAutoAccessSkipList,
Input Iterator, Output Iterator, Forward Iterator, Bidirectional Iterator, Bidirectional Iterator LOGN, Random Access Iterator, Arbitrary Access Iterator LOGN, Forward Arbitrary Access Iterator, Forward Arbitrary Access Iterator LOGN, Reverse Arbitrary Access Iterator, Reverse Arbitrary Access Iterator LOGN, Iterator Overview