**Category**: containers

**Component type**: concept

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.

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

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.

`X` | A type that is a model of Arbitrary Access Container LOGN |

`a` | Object of type `X` |

`T` | The value type of `X` |

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. |

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 `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. |

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.

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. |

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

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

Generated on Thu Jan 6 2011 15:52:40 for SkipList Library by 1.7.3