Forward Arbitrary Access Iterator LOGN

Category: iterators
Component type: concept

Description

A Forward Arbitrary Access Iterator LOGN is an iterator that provides increment functionality (just like a Forward Iterator) in constant-time, and that also provides logarithmic-time methods for moving forward in arbitrary-sized steps.

Refinement of

Forward Iterator, LessThan Comparable

Associated types

The same as for Forward Iterator

Notation

X A type that is a model of Forward Arbitrary 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

Definitions

Valid expressions

In addition to the expressions defined in Forward 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
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, Forward 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. (n >= 0). 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
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. (n >= 0). Equivalent to *(i + n) [2]  
Element assignment i[n] = t i + n exists and is dereferenceable. (n >= 0). 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]  

Complexity guarantees

Decrementing is performed in amortized constant time and moving forward by arbitrary-sized steps is performed in at most amortized logarithmic time. [5]

Invariants

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.

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 Forward Arbitrary Access Iterators LOGN: 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 Forward Arbitrary Access Iterator LOGN exists as a distinct concept. Every operation in iterator arithmetic can be defined for Forward Iterator; in fact, that is exactly what the algorithms advance and distance do. The distinction is simply that the Forward Iterator implementations are linear time, while Forward Arbitrary 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.

See also

AutoSkipList, AutoSSkipList, AutoKeyedSkipList, AutoKeyedSSkipList, MultiAutoSkipList, MultiAutoSSkipList, MultiAutoKeyedSkipList, MultiAutoKeyedSSkipList, IndexedSkipList, IndexedSSkipList, IndexedTinySkipList, XIndexedSkipList, XMultiAutoSkipList, AutoAccessSkipList, AutoAccessSSkipList, MultiAutoAccessSkipList, MultiAutoAccessSSkipList, XMultiAutoAccessSkipList,

LessThan Comparable, Trivial Iterator, Bidirectional Iterator, Iterator Overview, Sequence, LessThan Comparable, Trivial Iterator, Input Iterator, Output Iterator, Forward Iterator, Bidirectional Iterator, Bidirectional Iterator LOGN, Forward Arbitrary Access Container, Forward Arbitrary Access Iterator, Forward Arbitrary Access Container LOGN, Reverse Arbitrary Access Container, Reverse Arbitrary Access Iterator, Reverse Arbitrary Access Container LOGN, Reverse Arbitrary Access Iterator LOGN, Random Access Container, Random Access Iterator, Random Access Container LOGN, Random Access Iterator LOGN, Arbitrary Access Container LOGN, Arbitrary Access Iterator LOGN

 All Classes Files Functions Variables Typedefs
Generated on Thu Jan 6 2011 15:52:40 for SkipList Library by  doxygen 1.7.3