C++ named requirements: SequenceContainer
A SequenceContainer is a Container that stores objects of the same type in a linear arrangement.
Contents |
[edit] Requirements
The type X
satisfies SequenceContainer if
- The type
X
satisfies Container, and
Given
-
T
, the element type ofX
-
A
, the allocator type ofX
:X::allocator_type
if it exists, otherwise std::allocator<T> - a, an rvalue expression 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, LegacyInputIterators 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 is 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 LegacyForwardIterators, |
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 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
(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 is 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 is 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 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
(only for std::vector) If the iterators are not LegacyForwardIterators, |
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(), |
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 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::deque, std::vector) 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 not in a
(std::vector) If not LegacyForwardIterator. |
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 is CopyInsertable and CopyAssignable
|
|
notes | ||||
|
[edit] Optional operations
The following expressions must be valid and have their specified effects for the sequence containers named, all operations take amortized constant time:
expression | return type | effects | preconditions | containers |
---|---|---|---|---|
a.front() | reference
|
Equivalent to *a.begin() | (all) | |
a.back() | reference
|
Equivalent to { auto tmp = a.end(); --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 only) |
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.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.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 std::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 LegacyInputIterator.
[edit] Sequence containers in the standard library
stores and manipulates sequences of characters (class template) | |
(C++11) |
static contiguous array (class template) |
dynamic contiguous array (class template) | |
double-ended queue (class template) | |
(C++11) |
singly-linked list (class template) |
doubly-linked list (class template) |
[edit] 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 |
[edit] 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 whilea.insert(p, n, t) and a.insert(p, n, t) returned void |
they all returniterator
|
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
|