Random Access Container LOGN

Category: containers
Component type: concept

Description

A Random Access Container LOGN is a Reversible Container, a Forward Arbitrary Access Container LOGN and a Reverse Arbitrary Access Container LOGN whose iterator type is a Random Access Iterator LOGN. It provides amortized logorithmic time access to arbitrary elements while retaining constant time access to adjacent elements.

Iterator movement performance.

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

Refinement of

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

Associated types

No additional types beyond those defined in Reversible Container, 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 Random 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, 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 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: constant 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

• IndexedSkipList
• AutoSkipList
• AutoKeyedSkipList
• MultiAutoSkipList
• MultiAutoKeyedSkipList
• XIndexedSkipList
• XMultiAutoSkipList
• AutoAccessSkipList
• MultiAutoAccessSkipList
• XMultiAutoAccessSkipList

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