SkipList Library: Back Access Container LOGN

Category: containers
Component type: concept

Description

A Back Access Container LOGN is a Forward Container where it is possible to access, pop or destroy the last element in amortized logarithmic time. Back Access Containers LOGN have special member functions as a shorthand for those operations.

A Back Access Container LOGN is the same as a Back Access Container except that the performance requirements have changed to logn time.

Refinement of

Forward Container

Associated types

None, except for those of Forward Container.

Notation

`X`	A type that is a model of Back Access Container LOGN
`a`	Object of type `X`
`T`	The value type of `X`
`t`	Object of type `T`

Definitions

Valid expressions

In addition to the expressions defined in Forward Container, the following expressions must be valid.

Name	Expression	Type requirements	Return type
Back	`a.back()`		`reference` if `a` is mutable, otherwise `const_reference`.
Pop back	`a.pop_back()`	`a` is mutable.	`void`
Destroy back	`a.destroy_back()`	`a` is mutable.	`void`

Expression semantics

Name	Expression	Precondition	Semantics	Postcondition
Back	`a.back()`	`!a.empty()`	Equivalent to `*(--a.end())`.
Pop back	`a.pop_back()`	`!a.empty()`	Equivalent to `a.erase(--a.end())`	`a.size()` is decremented by 1.
Destroy back	`a.destroy_back()`	`!a.empty()`	Equivalent to `delete *(--a.end()); a.erase(--a.end());`	`a.size()` is decremented by 1.

Complexity guarantees

Back, pop back and destroy back are amortized logn time. [1]

Models

Notes

[1] This complexity guarantee is the only reason that back(), pop_back(), and destroy_back() are defined: they provide no additional functionality. Not every sequence must define these operations, but it is guaranteed that they are efficient if they exist at all.

Back Access Container LOGN