SkipList Library: Front Access Container

Category: containers
Component type: concept

Description

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

Refinement of

Forward Container

Associated types

None, except for those of Forward Container.

Notation

`X`	A type that is a model of Front Access Container
`a`	Object of type `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
Front	`a.front()` [1]		`reference` if `a` is mutable, otherwise `const_reference`.
Pop front	`a.pop_front()`	`a` is mutable.	`void`
Destroy front	`a.destroy_front()`	`a` is mutable.	`void`

Expression semantics

Name	Expression	Precondition	Semantics	Postcondition
Front	`a.front()`	`!a.empty()`	Equivalent to `*(a.begin())`.
Pop front	`a.pop_front()`	`!a.empty()`	Equivalent to `a.erase(a.begin())`	`a.size()` is decremented by 1.
Destroy front	`a.destroy_front()`	`!a.empty()`	Equivalent to `delete *(a.begin()); a.erase(a.begin());`	`a.size()` is decremented by 1.

Complexity guarantees

Front, pop front and destroy front are amortized constant time. [1]

Models

Notes

[1] This complexity guarantee is the only reason that front(), pop_front(), and destroy_front() 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.

Front Access Container