Forward Arbitrary Access Container LOGN

Category: containers
Component type: concept

Description

A Forward Arbitrary Access Container LOGN is a Forward Container whose iterator type is a Forward Arbitrary Access Iterator LOGN that can move forward by arbitrary amounts in at most amortized logarithmic time.

A Forward Arbitrary Access Container LOGN provides (at most) logarithmic time access to arbitrary elements.

No specifications on reverse movement is determined here.

Refinement of

Forward Container

Associated types

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

Notation

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

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

See also

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

 All Classes Files Functions Variables Typedefs