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.
See also
Container,
Sequence,
Back Insertion Sequence,
deque,
list,
slist