C++ named requirements: 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 X satisfies Container, and
Given
T
, the element type of XA
, the allocator type of X:X::allocator_type
if it exists, otherwisestd::allocator
<T>a
, an rvalue expression of type Xp
, a valid const iterator intoa
q
, a valid dereferenceable const iterator intoa
q1
andq2
, two const iterators into a such that[q1, q2)
is a valid rangei
andj
, LegacyInputIterators such that[i, j)
is a valid range and that the iterators refer to elements implicitly convertible to value_typeil
, an object of typestd::initializer_list<value_type>
n
, a value of typeX::size_type
t
, an lvalue or const rvalue of typeX::value_type
rv
, a non-const rvalue of typeX::value_type
Args
, a template parameter packargs
, a function parameter pack with the patternArg&&
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()) | |
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, T must be CopyInsertable | std::distance(begin(), end()) | |
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) 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 (for std::vector and 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 (for std::vector and 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 (only for 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(p, il) | iterator | a.insert(p, | 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. T is MoveInsertable | Each iterator in [i, j) is dereferenced once |
a.assign(il) | void | a.assign(il.begin(), | ||
a.assign(n, t) | void | Replaces elements in a with n copies of t | T is CopyInsertable and CopyAssignable |
Notes
1 std::array supports assignment from a braced-init-list, but not from an std::initializer_list
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 const_reference for const a | Equivalent to *a.begin() | (all) | |
a.back() | reference const_reference for const a | Equivalent to { | 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) 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.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 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 |
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.
Sequence containers in the standard library
pub | basic_string | stores and manipulates sequences of characters |
pub | array(C++11) | static contiguous array |
pub | vector | dynamic contiguous array |
pub | deque | double-ended queue |
pub | forward_list(C++11) | singly-linked list |
pub | list | doubly-linked list |
Trade-offs / usage notes
pub | std::vector | Fast access but mostly inefficient insertions/deletions |
pub | std::array | Fast access but fixed number of elements |
pub | std::list std::forward_list | Efficient insertion/deletion in the middle of the sequence |
pub | 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.