24 Containers library [containers]

24.2 Requirements [container.requirements]

24.2.4 Sequence containers [sequence.reqmts]

1
#
A sequence container organizes a finite set of objects, all of the same type, into a strictly linear arrangement.
The library provides four basic kinds of sequence containers: vector, forward_list, list, and deque.
In addition, array is provided as a sequence container which provides limited sequence operations because it has a fixed number of elements.
The library also provides container adaptors that make it easy to construct abstract data types, such as stacks, queues, flat_maps, flat_multimaps, flat_sets, or flat_multisets, out of the basic sequence container kinds (or out of other program-defined sequence containers).
2
#
[Note 1: 
The sequence containers offer the programmer different complexity trade-offs.
vector is appropriate in most circumstances.
array has a fixed size known during translation.
list or forward_list support frequent insertions and deletions from the middle of the sequence.
deque supports efficient insertions and deletions taking place at the beginning or at the end of the sequence.
When choosing a container, remember vector is best; leave a comment to explain if you choose from the rest!
— end note]
3
#
In this subclause,
  • (3.1)
    X denotes a sequence container class,
  • (3.2)
    a denotes a value of type X containing elements of type T,
  • (3.3)
    u denotes the name of a variable being declared,
  • (3.4)
    A denotes X​::​allocator_type if the qualified-id X​::​allocator_type is valid and denotes a type ([temp.deduct]) and allocator<T> if it doesn't,
  • (3.5)
    i and j denote iterators that meet the Cpp17InputIterator requirements and refer to elements implicitly convertible to value_type,
  • (3.6)
    [i, j) denotes a valid range,
  • (3.7)
    rg denotes a value of a type R that models container-compatible-range<T>,
  • (3.8)
    il designates an object of type initializer_list<value_type>,
  • (3.9)
    n denotes a value of type X​::​size_type,
  • (3.10)
    p denotes a valid constant iterator to a,
  • (3.11)
    q denotes a valid dereferenceable constant iterator to a,
  • (3.12)
    [q1, q2) denotes a valid range of constant iterators in a,
  • (3.13)
    t denotes an lvalue or a const rvalue of X​::​value_type, and
  • (3.14)
    rv denotes a non-const rvalue of X​::​value_type.
  • (3.15)
    Args denotes a template parameter pack;
  • (3.16)
    args denotes a function parameter pack with the pattern Args&&.
4
#
The complexities of the expressions are sequence dependent.
5
#
A type X meets the sequence container requirements if X meets the container requirements and the following statements and expressions are well-formed and have the specified semantics.
🔗
X u(n, t);
6
#
Preconditions: T is Cpp17CopyInsertable into X.
7
#
Effects: Constructs a sequence container with n copies of t.
8
#
Postconditions: distance(u.begin(), u.end()) == n is true.
🔗
X u(i, j);
9
#
Preconditions: T is Cpp17EmplaceConstructible into X from *i.
For vector, if the iterator does not meet the Cpp17ForwardIterator requirements ([forward.iterators]), T is also Cpp17MoveInsertable into X.
10
#
Effects: Constructs a sequence container equal to the range [i, j).
Each iterator in the range [i, j) is dereferenced exactly once.
11
#
Postconditions: distance(u.begin(), u.end()) == distance(i, j) is true.
🔗
X(from_range, rg)
12
#
Preconditions: T is Cpp17EmplaceConstructible into X from *ranges​::​begin(rg).
For vector, if R models neither ranges​::​sized_range nor ranges​::​forward_range, T is also Cpp17MoveInsertable into X.
13
#
Effects: Constructs a sequence container equal to the range rg.
Each iterator in the range rg is dereferenced exactly once.
14
#
Postconditions: distance(begin(), end()) == ranges​::​distance(rg) is true.
🔗
X(il)
15
#
Effects: Equivalent to X(il.begin(), il.end()).
🔗
a = il
16
#
Result: X&.
17
#
Preconditions: T is Cpp17CopyInsertable into X and Cpp17CopyAssignable.
18
#
Effects: Assigns the range [il.begin(), il.end()) into a.
All existing elements of a are either assigned to or destroyed.
19
#
Returns: *this.
🔗
a.emplace(p, args)
20
#
Result: iterator.
21
#
Preconditions: T is Cpp17EmplaceConstructible into X from args.
For vector and deque, T is also Cpp17MoveInsertable into X and Cpp17MoveAssignable.
22
#
Effects: Inserts an object of type T constructed with std​::​forward<Args>(args)... before p.
[Note 2: 
args can directly or indirectly refer to a value in a.
— end note]
23
#
Returns: An iterator that points to the new element constructed from args into a.
🔗
a.insert(p, t)
24
#
Result: iterator.
25
#
Preconditions: T is Cpp17CopyInsertable into X.
For vector and deque, T is also Cpp17CopyAssignable.
26
#
Effects: Inserts a copy of t before p.
27
#
Returns: An iterator that points to the copy of t inserted into a.
🔗
a.insert(p, rv)
28
#
Result: iterator.
29
#
Preconditions: T is Cpp17MoveInsertable into X.
For vector and deque, T is also Cpp17MoveAssignable.
30
#
Effects: Inserts a copy of rv before p.
31
#
Returns: An iterator that points to the copy of rv inserted into a.
🔗
a.insert(p, n, t)
32
#
Result: iterator.
33
#
Preconditions: T is Cpp17CopyInsertable into X and Cpp17CopyAssignable.
34
#
Effects: Inserts n copies of t before p.
35
#
Returns: An iterator that points to the copy of the first element inserted into a, or p if n == 0.
🔗
a.insert(p, i, j)
36
#
Result: iterator.
37
#
Preconditions: T is Cpp17EmplaceConstructible into X from *i.
For vector and deque, T is also Cpp17MoveInsertable into X, and T meets the Cpp17MoveConstructible, Cpp17MoveAssignable, and Cpp17Swappable ([swappable.requirements]) requirements.
Neither i nor j are iterators into a.
38
#
Effects: Inserts copies of elements in [i, j) before p.
Each iterator in the range [i, j) shall be dereferenced exactly once.
39
#
Returns: An iterator that points to the copy of the first element inserted into a, or p if i == j.
🔗
a.insert_range(p, rg)
40
#
Result: iterator.
41
#
Preconditions: T is Cpp17EmplaceConstructible into X from *ranges​::​begin(rg).
For vector and deque, T is also Cpp17MoveInsertable into X, and T meets the Cpp17MoveConstructible, Cpp17MoveAssignable, and Cpp17Swappable ([swappable.requirements]) requirements.
rg and a do not overlap.
42
#
Effects: Inserts copies of elements in rg before p.
Each iterator in the range rg is dereferenced exactly once.
43
#
Returns: An iterator that points to the copy of the first element inserted into a, or p if rg is empty.
🔗
a.insert(p, il)
44
#
Effects: Equivalent to a.insert(p, il.begin(), il.end()).
🔗
a.erase(q)
45
#
Result: iterator.
46
#
Preconditions: For vector and deque, T is Cpp17MoveAssignable.
47
#
Effects: Erases the element pointed to by q.
48
#
Returns: An iterator that points to the element immediately following q prior to the element being erased.
If no such element exists, a.end() is returned.
🔗
a.erase(q1, q2)
49
#
Result: iterator.
50
#
Preconditions: For vector and deque, T is Cpp17MoveAssignable.
51
#
Effects: Erases the elements in the range [q1, q2).
52
#
Returns: An iterator that points to the element pointed to by q2 prior to any elements being erased.
If no such element exists, a.end() is returned.
🔗
a.clear()
53
#
Result: void
54
#
Effects: Destroys all elements in a.
Invalidates all references, pointers, and iterators referring to the elements of a and may invalidate the past-the-end iterator.
55
#
Postconditions: a.empty() is true.
56
#
Complexity: Linear.
🔗
a.assign(i, j)
57
#
Result: void
58
#
Preconditions: T is Cpp17EmplaceConstructible into X from *i and assignable from *i.
For vector, if the iterator does not meet the forward iterator requirements ([forward.iterators]), T is also Cpp17MoveInsertable into X.
Neither i nor j are iterators into a.
59
#
Effects: Replaces elements in a with a copy of [i, j).
Invalidates all references, pointers and iterators referring to the elements of a.
For vector and deque, also invalidates the past-the-end iterator.
Each iterator in the range [i, j) is dereferenced exactly once.
🔗
a.assign_range(rg)
60
#
Result: void
61
#
Mandates: assignable_from<T&, ranges​::​range_reference_t<R>> is modeled.
62
#
Preconditions: T is Cpp17EmplaceConstructible into X from *ranges​::​begin(rg).
For vector, if R models neither ranges​::​sized_range nor ranges​::​forward_range, T is also Cpp17MoveInsertable into X.
rg and a do not overlap.
63
#
Effects: Replaces elements in a with a copy of each element in rg.
Invalidates all references, pointers, and iterators referring to the elements of a.
For vector and deque, also invalidates the past-the-end iterator.
Each iterator in the range rg is dereferenced exactly once.
🔗
a.assign(il)
64
#
Effects: Equivalent to a.assign(il.begin(), il.end()).
🔗
a.assign(n, t)
65
#
Result: void
66
#
Preconditions: T is Cpp17CopyInsertable into X and Cpp17CopyAssignable.
t is not a reference into a.
67
#
Effects: Replaces elements in a with n copies of t.
Invalidates all references, pointers and iterators referring to the elements of a.
For vector and deque, also invalidates the past-the-end iterator.
68
#
For every sequence container defined in this Clause and in [strings]:
  • (68.1)
    If the constructor template<class InputIterator> X(InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type()); is called with a type InputIterator that does not qualify as an input iterator, then the constructor shall not participate in overload resolution.
  • (68.2)
    If the member functions of the forms: template<class InputIterator> return-type F(const_iterator p, InputIterator first, InputIterator last); // such as insert template<class InputIterator> return-type F(InputIterator first, InputIterator last); // such as append, assign template<class InputIterator> return-type F(const_iterator i1, const_iterator i2, InputIterator first, InputIterator last); // such as replace are called with a type InputIterator that does not qualify as an input iterator, then these functions shall not participate in overload resolution.
  • (68.3)
    A deduction guide for a sequence container shall not participate in overload resolution if it has an InputIterator template parameter and a type that does not qualify as an input iterator is deduced for that parameter, or if it has an Allocator template parameter and a type that does not qualify as an allocator is deduced for that parameter.
69
#
The following operations are provided for some types of sequence containers but not others.
Operations other than prepend_range and append_range are implemented so as to take amortized constant time.
🔗
a.front()
70
#
Result: reference; const_reference for constant a.
71
#
Returns: *a.begin()
72
#
Remarks: Required for basic_string, array, deque, forward_list, list, and vector.
🔗
a.back()
73
#
Result: reference; const_reference for constant a.
74
#
Effects: Equivalent to: auto tmp = a.end(); --tmp; return *tmp;
75
#
Remarks: Required for basic_string, array, deque, list, and vector.
🔗
a.emplace_front(args)
76
#
Result: reference
77
#
Preconditions: T is Cpp17EmplaceConstructible into X from args.
78
#
Effects: Prepends an object of type T constructed with std​::​forward<Args>(args)....
79
#
Returns: a.front().
80
#
Remarks: Required for deque, forward_list, and list.
🔗
a.emplace_back(args)
81
#
Result: reference
82
#
Preconditions: T is Cpp17EmplaceConstructible into X from args.
For vector, T is also Cpp17MoveInsertable into X.
83
#
Effects: Appends an object of type T constructed with std​::​forward<Args>(args)....
84
#
Returns: a.back().
85
#
Remarks: Required for deque, list, and vector.
🔗
a.push_front(t)
86
#
Result: void
87
#
Preconditions: T is Cpp17CopyInsertable into X.
88
#
Effects: Prepends a copy of t.
89
#
Remarks: Required for deque, forward_list, and list.
🔗
a.push_front(rv)
90
#
Result: void
91
#
Preconditions: T is Cpp17MoveInsertable into X.
92
#
Effects: Prepends a copy of rv.
93
#
Remarks: Required for deque, forward_list, and list.
🔗
a.prepend_range(rg)
94
#
Result: void
95
#
Preconditions: T is Cpp17EmplaceConstructible into X from *ranges​::​begin(rg).
For deque, T is also Cpp17MoveInsertable into X, and T meets the Cpp17MoveConstructible, Cpp17MoveAssignable, and Cpp17Swappable ([swappable.requirements]) requirements.
96
#
Effects: Inserts copies of elements in rg before begin().
Each iterator in the range rg is dereferenced exactly once.
[Note 3: 
The order of elements in rg is not reversed.
— end note]
97
#
Remarks: Required for deque, forward_list, and list.
🔗
a.push_back(t)
98
#
Result: void
99
#
Preconditions: T is Cpp17CopyInsertable into X.
100
#
Effects: Appends a copy of t.
101
#
Remarks: Required for basic_string, deque, list, and vector.
🔗
a.push_back(rv)
102
#
Result: void
103
#
Preconditions: T is Cpp17MoveInsertable into X.
104
#
Effects: Appends a copy of rv.
105
#
Remarks: Required for basic_string, deque, list, and vector.
🔗
a.append_range(rg)
106
#
Result: void
107
#
Preconditions: T is Cpp17EmplaceConstructible into X from *ranges​::​begin(rg).
For vector, T is also Cpp17MoveInsertable into X.
108
#
Effects: Inserts copies of elements in rg before end().
Each iterator in the range rg is dereferenced exactly once.
109
#
Remarks: Required for deque, list, and vector.
🔗
a.pop_front()
110
#
Result: void
111
#
Preconditions: a.empty() is false.
112
#
Effects: Destroys the first element.
113
#
Remarks: Required for deque, forward_list, and list.
🔗
a.pop_back()
114
#
Result: void
115
#
Preconditions: a.empty() is false.
116
#
Effects: Destroys the last element.
117
#
Remarks: Required for basic_string, deque, list, and vector.
🔗
a[n]
118
#
Result: reference; const_reference for constant a
119
#
Returns: *(a.begin() + n)
120
#
Remarks: Required for basic_string, array, deque, and vector.
🔗
a.at(n)
121
#
Result: reference; const_reference for constant a
122
#
Returns: *(a.begin() + n)
123
#
Throws: out_of_range if n >= a.size().
124
#
Remarks: Required for basic_string, array, deque, and vector.