Whole document tree

www.fifi.org
    Documentation
        Manpages
        GNU Info
        Debian document tree
        Whole document tree
    Trigance web page
    Public services
    User info
    Mailing lists
    Secure server
    Multilingual usage

Whole document tree

Front Insertion Sequence


Category: containers	Component type: concept

Description

A Front Insertion Sequence is a Sequence where it is possible to insert an element at the beginning, or to access the first element, in amortized constant time. Front Insertion Sequences have special member functions as a shorthand for those operations.

Refinement of

Sequence

Associated types

None, except for those of Sequence.

Notation

`X`	A type that is a model of Front Insertion Sequence
`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 Sequence, the following expressions must be valid.

Name	Expression	Type requirements	Return type
Front	`a.front()` [1]		`reference` if `a` is mutable, otherwise `const_reference`.
Push front	`a.push_front(t)`	`a` is mutable.	`void`
Pop front	`a.pop_front()`	`a` is mutable.	`void`

Expression semantics

Name	Expression	Precondition	Semantics	Postcondition
Front	`a.front()` [1]	`!a.empty()`	Equivalent to `*(a.begin())`.
Push front	`a.push_front(t)`		Equivalent to `a.insert(a.begin(), t)`	`a.size` is incremented by 1. `a.front()` is a copy of `t`.
Pop front	`a.pop_front()`	`!a.empty()`	Equivalent to `a.erase(a.begin())`	`a.size()` is decremented by 1.

Complexity guarantees

Front, push front, and pop front are amortized constant time. [2]

Invariants

Symmetry of push and pop push_front() followed by pop_front() is a null operation.

Models

Notes

[1] Front is actually defined in Sequence, since it is always possible to implement it in amortized constant time. Its definition is repeated here, along with push front and pop front, in the interest of clarity.

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