Arbitrary Access Container LOGN

Category: containers
Component type: concept

Description

An Arbitrary Access Container LOGN is a Reversible Container LOGN, a Forward Arbitrary Access Container LOGN and a Reverse Arbitrary Access Container LOGN whose iterator type is a Arbitrary Access Iterator LOGN. It provides amortized logorithmic time access to arbitrary elements as well as the previous element while retaining constant time access to next element.

Iterator movement performance.

• Increment: constant time.
• Decrement: logarithmic time.
• Arbitrary Forward Element: logarithmic time.
• Arbitrary Reverse Element: logarithmic time.

Refinement of

Reversible Container LOGN, Forward Arbitrary Access Container LOGN, Reverse Arbitrary Access Container LOGN

Associated types

No additional types beyond those defined in Reversible Container LOGN, Forward Arbitrary Access Container LOGN and Reverse Arbitrary Access Container LOGN. However, the requirements for the iterator type are strengthened: it must be a Random Access Iterator LOGN.

Notation

X	A type that is a model of Arbitrary Access Container LOGN
a	Object of type X
T	The value type of X

Definitions

Valid expressions

In addition to the expressions defined in Reversible Container LOGN, Forward Arbitrary Access Container LOGN and Reverse Arbitrary Access Container LOGN, the following expressions must be valid.

Name	Expression	Type requirements	Return type
Element access	a[n]	n is convertible to size_type	reference if a is mutable, const_reference otherwise. With Pair Associative Containers, mapped_type if a is mutable, const mapped_type otherwise.
Element access	a.at(n)	n is convertible to size_type	reference if a is mutable, const_reference otherwise. With Pair Associative Containers, mapped_type if a is mutable, const mapped_type otherwise.

Expression semantics

Semantics of an expression is defined only where it is not defined in Reversible Container LOGN, Forward Arbitrary Access Container LOGN and Reverse Arbitrary Access Container LOGN, or where there is additional information.

Name	Expression	Precondition	Semantics	Postcondition
Element access	a[n]	0 <= n < a.size()	Returns the nth element from the beginning of the container.
Element access	a.at(n)	0 <= n < a.size()	Returns the nth element from the beginning of the container. Throws out_of_range exception if precondition not met.

Complexity guarantees

The run-time complexity of element access is amortized logarithmic time.

Iterator movement performance.

• Increment: constant time.
• Decrement: logarithmic time.
• Arbitrary Forward Element: logarithmic time.
• Arbitrary Reverse Element: logarithmic time.

Invariants

Element access

The element returned by a[n] is the same as the one obtained by incrementing a.begin() n times and then dereferencing the resulting iterator.

Models

• IndexedSSkipList
• IndexedTinySkipList
• AutoSSkipList
• AutoKeyedSSkipList
• MultiAutoSSkipList
• MultiAutoKeyedSSkipList
• AutoAccessSSkipList
• MultiAutoAccessSSkipList

Notes

See also

Iterator Overview, Sequence, Forward Arbitrary Access Container, Forward Arbitrary Access Iterator, Forward Arbitrary Access Container LOGN, Forward Arbitrary Access Iterator 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 Iterator LOGN