BackInsertionSequence [Concepts]

Detailed 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.

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