# C++ named requirements: SequenceContainer

From cppreference.com
< cpp‎ | named req

A SequenceContainer is a Container that stores objects of the same type in a linear arrangement.

### Requirements

##### Legend
`X` | A sequence container class
`T` | The element type of `X`
a | An rvalue expression of type `X`
u | The name of a declared variable
`A` | The allocator type of `X`: `X::allocator_type` if it exists, otherwise std::allocator<T>
`[`i`,` j`)` | LegacyInputIterators such that `[`i`,` j`)` is a valid range and that the iterators refer to elements implicitly convertible to `value_type`
rg (since C++23) | A value of a type `R` that models `container-compatible-range``<T>`
il | An object of type std::initializer_list<value_type>
n | A value of type `X::size_type`
p | A valid const iterator into a
q | A valid dereferenceable const iterator into a
`[`q1`,` q2`)` | Two const iterators into a such that `[`q1`,` q2`)` is a valid range
t | An lvalue or const rvalue of type `X::value_type`
rv | A non-const rvalue of type `X::value_type`
`Args` | A template parameter pack
args | A function parameter pack with the pattern `Arg&&`

The type `X` satisfies SequenceContainer if

- The type `X` satisfies Container, and
- The following expressions must be valid and have their specified effects for all sequence containers except std::array (see notes):

Expression | Return type | Effects | Precondition | Postcondition
--- | --- | --- | --- | ---
X u(n, t) |  | Constructs the sequence container holding n copies of t | `T` is CopyInsertable into `X` | std::distance(u.begin(), u.end()) == n
X u(i, j) |  | Constructs the sequence container equal, element-wise, to the range `[`i`,` j`)` | `T` is EmplaceConstructible from *i into `X` (std::vector) If the iterators are not LegacyForwardIterators, `T` must be CopyInsertable | std::distance(u.begin(), u.end()) == std::distance(i, j)
X(std::from_range, rg) (since C++23) |  | Constructs the sequence container equal, element-wise, to the range rg | `T` is EmplaceConstructible from *ranges::begin(rg) into `X`. (std::vector) If `R` models neither ranges::sized_range nor ranges::forward_range, `T` must be MoveInsertable into `X`. | Each iterator in the range rg is dereferenced once. std::distance(begin(), end()) == ranges::distance(rg)
X(il) |  | X(il.begin(), il.end()) |  |
a = il | `X&` | Assigns the range represented by il into a[1] | `T` is CopyInsertable and CopyAssignable | Existing elements of a are destroyed or assigned to
a.emplace(p, args) | `iterator` | Insert an object of type `T`, constructed with std::forward<Args>(args) before p | `T` is EmplaceConstructible (std::vector, std::deque) `T` is MoveAssignable and MoveInsertable | Returned iterator points at the element constructed from args into a
a.insert(p, t) | `iterator` | Inserts a copy of t before p | `T` is CopyInsertable (std::vector, std::deque) `T` is CopyAssignable or MoveAssignable | Returned iterator points at the copy of t inserted into a
a.insert(p, rv) | `iterator` | Inserts a copy of rv before p, possibly using move semantics | `T` is MoveInsertable (std::vector, std::deque) `T` is MoveAssignable | Returned iterator points at the copy of rv inserted into a
a.insert(p, n, t) | `iterator` | Inserts n copies of t before p | `T` is CopyInsertable and CopyAssignable | Returned iterator points at the copy of the first element inserted into a or is p for n == 0
a.insert(p, i, j) | `iterator` | Inserts copies of elements in `[`i`,` j`)` before p | `T` is EmplaceConstructible and i and j are not in a (std::vector) If the iterators are not LegacyForwardIterators, `T` must be MoveInsertable and MoveAssignable | Each iterator in `[`i`,` j`)` is dereferenced once. Returned iterator points at the copy of the first element inserted into a or is p for i == j
a.insert_range(p, rg) (since C++23) | `iterator` | Inserts copies of elements in rg before p | `T` is EmplaceConstructible into `X` from *ranges::begin(rg). (std::vector, std::deque) `T` is also MoveInsertable into `X`, and `T` is MoveConstructible, MoveAssignable, and Swappable. rg and a do not overlap. | Each iterator in the range rg is dereferenced once. Returned iterator points at the copy of the first element inserted into a or at p if rg is empty
a.insert(p, il) | `iterator` | a.insert(p, il.begin(), il.end()) |  | Returned iterator points at the copy of the first element inserted into a or is p if il is empty.
a.erase(q) | `iterator` | Erases the element pointed to by q | (std::vector, std::deque) `T` is MoveAssignable | Returned iterator points at the element that was immediately following q prior to erasure, or a.end() if no such element exists.
a.erase(q1, q2) | `iterator` | Erases elements in `[`q1`,` q2`)` | (std::vector, std::deque) `T` is MoveAssignable | Returned iterator points at the element that was pointed by q2 prior to any erasure, or a.end() if no such element exists.
a.clear() | void | Destroys all elements in a |  | All references, pointers, and iterators are invalidated, including the end iterator. a.empty() == true
a.assign(i, j) | void | Replaces elements in a with a copy of `[`i`,` j`)` | `T` is EmplaceConstructible and i, j are not in a. (std::vector) If the iterators are not LegacyForwardIterators, `T` must be MoveInsertable. | Each iterator in `[`i`,` j`)` is dereferenced once
a.assign_range(rg) (since C++23) | void | Replaces elements in a with a copy of each element in rg | `T`[2] is EmplaceConstructible into `X` from *ranges::begin(rg). rg and a do not overlap. (std::vector) If `R` models neither ranges::sized_range nor ranges::forward_range, `T` is also MoveInsertable into `X`. | Each iterator in the range rg is dereferenced once. All references, pointers, and iterators are invalidated. (std::vector, std::deque) Also invalidates the end iterator.
a.assign(il) | void | a.assign(il.begin(), il.end()) |  |
a.assign(n, t) | void | Replaces elements in a with n copies of t | `T` is CopyInsertable and CopyAssignable |
Notes
↑ std::array supports assignment from a braced-init-list, but not from an std::initializer_list. ↑ `T` and `R` are such that ranges::assignable_from<T&, ranges::range_reference_t<R>> is modeled.

#### Optional operations

The following expressions must be valid and have their specified effects for the sequence containers named, all operations except `prepend_range` and `append_range` (since C++23) take amortized constant time:

Expression | Return type | Effects | Preconditions | Containers
--- | --- | --- | --- | ---
a.front() | `reference`, `const_reference` for const a | Equivalent to *a.begin() |  | (all)
a.back() | `reference`, `const_reference` for const a | Equivalent to auto tmp = a.end(); --tmp; return *tmp; |  | std::basic_string std::array std::deque std::list std::vector
a.emplace_front(args) | void | Prepends a `T` constructed with std::forward<Args>(args)... | `T` is EmplaceConstructible into `X` from args | std::deque std::forward_list std::list
a.emplace_back(args) | void | Appends a `T` constructed with std::forward<Args>(args)... | `T` is EmplaceConstructible into `X` from args (std::vector) `T` is MoveInsertable into `X` | std::deque std::list std::vector
a.push_front(t) | void | Prepends a copy of t | `T` is CopyInsertable into `X` | std::deque std::forward_list std::list
a.push_front(rv) | void | Prepends a copy of rv, possibly using move semantics | `T` is MoveInsertable into `X` | std::deque std::forward_list std::list
a.prepend_range(rg) (since C++23) | void | Inserts[1] copies of elements in rg before begin() dereferencing each iterator in rg once. | `T` is EmplaceConstructible into `X` from *ranges::begin(rg) (std::deque) `T` is also MoveInsertable into `X`, and `T` is MoveConstructible, MoveAssignable, and Swappable | std::deque std::forward_list std::list
a.push_back(t) | void | Appends a copy of t | `T` is CopyInsertable into `X` | std::basic_string std::deque std::list std::vector
a.push_back(rv) | void | Appends a copy of rv, possibly using move semantics | `T` is MoveInsertable into `X` | std::basic_string std::deque std::list std::vector
a.append_range(rg) (since C++23) | void | Inserts[1] copies of elements in rg before end() dereferencing each iterator in rg once. | `T` is EmplaceConstructible into `X` from *ranges::begin(rg) (std::vector) `T` is also MoveInsertable into `X` | std::deque std::list std::vector
a.pop_front() | void | Destroys the first element. | a.empty() == false | std::deque std::forward_list std::list
a.pop_back() | void | Destroys the last element | a.empty() == false | std::basic_string std::deque std::list std::vector
a[n] | `reference`, `const_reference` for const a | Equivalent to *(n + a.begin()) |  | std::basic_string std::array std::deque std::vector
a.at(n) | `reference`, `const_reference` for const a | Equivalent to *(n + a.begin()), except that std::out_of_range is thrown if n >= size() |  | std::basic_string std::array std::deque std::vector
Notes
↑ 1.0 1.1 Insertion order, relative to order of elements in rg, is non-reversing.

Additionally, for every sequence container:

- A constructor template that takes two input iterators and the member function template overloads of `insert`, `append`, `assign`, `replace` that take two input iterators do not participate in overload resolution if the corresponding template argument does not satisfy LegacyInputIterator.

A deduction guide that has either a LegacyInputIterator or an `Allocator` template parameter does not participate in overload resolution if the type that does not qualify as an input iterator or an allocator respectively is deduced for that parameter. | (since C++17)

### Sequence containers in the standard library

basic_string | stores and manipulates sequences of characters (class template)
array (C++11) | static contiguous array (class template)
vector | dynamic contiguous array (class template)
deque | double-ended queue (class template)
forward_list (C++11) | singly-linked list (class template)
list | doubly-linked list (class template)

#### Trade-offs / usage notes

std::vector | Fast access but mostly inefficient insertions/deletions
std::array | Fast access but fixed number of elements
std::list std::forward_list | Efficient insertion/deletion in the middle of the sequence
std::deque | Efficient insertion/deletion at the beginning and at the end of the sequence

### Defect reports

The following behavior-changing defect reports were applied retroactively to previously published C++ standards.

DR | Applied to | Behavior as published | Correct behavior
--- | --- | --- | ---
LWG 139 | C++98 | the optional operations were not required to be implemented for the designated containers | required with amortized time
LWG 149 | C++98 | a.insert(p, t) returned `iterator` while a.insert(p, n, t) and a.insert(p, n, t) returned void | they all return `iterator`
LWG 151 | C++98 | q1 was dereferenceable[1] | it can be non-dereferenceable
LWG 355 | C++98 | calling a.back() or a.pop_back() would execute --a.end(), which is dangerous[2] | decrements a copy of a.end() instead
LWG 589 | C++98 | the elements that i and j refer to might not be convertible to `value_type` | they are implicitly convertible to `value_type`

1. ↑ It is a defect because it makes the behavior of a.erase(a.begin(), a.end()) undefined is a is an empty container.
2. ↑ If the type of a.end() is a fundamental type, --a.end() is ill-formed. It is dangerous when the type of a is templated, in this case this bug can be difficult to be found.

Retrieved from "https://en.cppreference.com/mwiki/index.php?title=cpp/named_req/SequenceContainer&oldid=154562"