# 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

- 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, Front Insertion Sequence, `vector`, `deque`, `list`

Copyright © 1999 Silicon Graphics, Inc. All Rights Reserved. TrademarkInformation