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 Type(s): 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 Guarantee(s): 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.

Type(s) Modeling this Concept

Vector
List
Deque

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.

See Also: Container, Sequence, FrontInsertionSequence, Vector, Deque, List