Category: containers
Component type: concept
A Back Insertion Sequence LOGN is a Sequence where it is possible to append an element to the end, or to access the last element, in amortized logarithmic time. Back Insertion Sequences LOGN have special member functions as a shorthand for those operations.
Identical to Back Insertion Sequence except for the logarithmic runtime complexity.
None, except for those of Sequence.
X | A type that is a model of Back Insertion Sequence LOGN |
a | Object of type X |
T | The value type of X |
t | Object of type T |
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 |
| 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. |
Back, push back, and pop back are amortized logarithmic time. [1]
| Symmetry of push and pop | push_back() followed by pop_back() is a null operation. |
[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.
Container, Sequence, Front Insertion Sequence, Back Insertion Sequence.
1.7.3
