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.
See also
Container, Sequence, Front Insertion Sequence,
vector, deque, list
STL Home