C++ concepts: SequenceContainer
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
XsatisfiesContainer, and
Given
-
T, the element type ofX -
A, the allocator type ofX: X::allocator_type if it exists, otherwise std::allocator<T> -
a, rvalue expression of type of typeX -
p, a valid const iterator intoa -
q, a valid dereferenceable const iterator intoa -
q1andq2, two const iterators intoasuch that [q1, q2) is a valid range -
iandj,InputIterators such that [i, j) is a valid range and that the iterators refer to elements implicitly convertible tovalue_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 |
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) |
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) |
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) |
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 |
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 |
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 | ||||
| ||||
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
|
Equivalent to *a.begin() | (all) | |
| a.back() | reference
|
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) |
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
|
Equivalent to *(n + a.begin()) | std::basic_string std::array std::deque std::vector | |
| a.at(n) | reference
|
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
| stores and manipulates sequences of characters (class template) | |
| (since C++11) |
static contiguous array (class template) |
| dynamic contiguous array (class template) | |
| double-ended queue (class template) | |
| (since C++11) |
singly-linked list (class template) |
| 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 |