SkipList Library: Random Access Container

Category: containers
Component type: concept

Description

A Random Access Container is a Reversible Container whose iterator type is a Random Access Iterator. It provides amortized constant time access to arbitrary elements.

Refinement of

Reversible Container

Associated types

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

Notation

`X`	A type that is a model of Random Access Container
`a`	Object of type `X`
`T`	The value type of `X`

Definitions

Valid expressions

In addition to the expressions defined in Reversible Container, 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, or where there is additional information.

Name	Expression	Precondition	Semantics	Postcondition
Element access	`a[n]`	`0 <= n < a.size()`	Returns the `n`th element from the beginning of the container.
Element access	`a.at(n)`	`0 <= n < a.size()`	Returns the `n`th 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 constant 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.

Random Access Container