Back Insertion Sequence


Category: containers	Component type: concept

Description

A Back Insertion Sequence is a Sequence where it is possible to append an element to the end, or to access the last element, in amortized constant time. Back 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 Back 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
Back	`a.back()`		`reference` if `a` is mutable, otherwise `const_reference`.
Push back	`a.push_back(t)`	`a` is mutable.	`void`
Pop back	`a.pop_back()`	`a` is mutable.	`void`

Expression semantics

Name	Expression	Precondition	Semantics	Postcondition
Back	`a.back()`	`!a.empty()`	Equivalent to `*(--a.end())`.
Push back	`a.push_back(t)`		Equivalent to `a.insert(a.end(), t)`	`a.size` is incremented by 1. `a.back()` is a copy of `t`.
Pop back	`a.pop_back()`	`!a.empty()`	Equivalent to `a.erase(--a.end())`	`a.size()` is decremented by 1.

Complexity guarantees

Back, push back, and pop back are amortized constant time. [1]

Invariants

Symmetry of push and pop push_back() followed by pop_back() is a null operation.

Models

Notes

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