# C++ concepts: SequenceContainer

From cppreference.com
< cpp‎ | concept

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

### Requirements

The type `X` satisfies `SequenceContainer` if

- The type `X` satisfies `Container`, and

Given

- `T`, the element type of `X`
- `A`, the allocator type of `X`: X::allocator_type if it exists, otherwise std::allocator<T>
- `a`, rvalue expression of type of type `X`
- `p`, a valid const iterator into `a`
- `q`, a valid dereferenceable const iterator into `a`
- `q1` and `q2`, two const iterators into `a` such that [q1, q2) is a valid range
- `i` and `j`, `InputIterator`s such that [i, j) is a valid range and that the iterators refer to elements implicitly convertible to `value_type`
- `il`, an object of type std::initializer_list<value_type>
- `n`, a value of type X::size_type
- `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 following expressions must be valid and have their specified effects for all sequence containers except std::array:

expression | return type | effects | precondition | postcondition
--- | --- | --- | --- | ---
X(n, t) X a(n, t) |  | Constructs the sequence container holding `n` copies of `t` | `T` `CopyInsertable` into `X` | std::distance(begin(),end()) == n
X(i, j) X a(i, j) |  | Constructs the sequence container equal, element-wise, to the range `[i,j)` | `T` is `EmplaceConstructible` from `*i` into `X` (only for std::vector) If the iterators are not `ForwardIterator`s, T must be `CopyInsertable` | std::distance(begin(),end()) == std::distance(i,j)
X(il) |  | X(il.begin(), il.end()) |  |
a = il | X& | Assigns the range represented by `il` into `a`[1] | T `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` `CopyInsertable` (for std::vector and std::deque) `T` `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` `CopyInsertable` (for std::vector and std::deque) `T` `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` `MoveInsertable` (for std::vector and std::deque) `T` `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` `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 `EmplaceConstructible` and `i` and `j` are not in `a` (only for std::vector) If the iterators are not `ForwardIterator`s, 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(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::deque, std::vector) T `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 `[p,q)` | (std::deque, std::vector) T `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` `EmplaceConstructible` and `i`, `j` not in `a` (std::vector) If not `ForwardIterator`. `T` `MoveInsertable` | Each iterator in `[i,j)` is dereferenced once
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 `CopyInsertable` and `CopyAssignable` |
notes

1. ↑ std::array supports assignment from a braced-init-list, but not from an std::initializer_list

The following expressions must be valid and have their specified effects for the sequence containers named:

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` `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` `EmplaceConstructible` into `X` from `args` (std::vector only) `T` `MoveInsertable` into `X` | std::deque std::list std::vector
a.push_front(t) | `void` | Prepends a copy of `t` | `T` `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` `MoveInsertable` into `X` | std::deque std::forward_list std::list
a.push_back(t) | `void` | Appends a copy of `t` | `T` `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` `MoveInsertable` into `X` | std::basic_string 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 out_of_range is thrown if n>=size() |  | std::basic_string std::array std::deque std::vector

Additionally, for every sequence container, the 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 `InputIterator`.

### SequenceContainers in the standard library

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

#### Trade-offs / usage notes

std::array | Fast access but fixed number of elements
std::vector | Fast access but mostly inefficient insertions/deletions
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

Retrieved from "http://en.cppreference.com/mwiki/index.php?title=cpp/concept/SequenceContainer&oldid=82216"