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
#
In this subclause,
  • (2.1)
    X denotes a sequence container class,
  • (2.2)
    a denotes a value of type X containing elements of type T,
  • (2.3)
    u denotes the name of a variable being declared,
  • (2.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,
  • (2.5)
    i and j denote iterators that meet the Cpp17InputIterator requirements and refer to elements implicitly convertible to value_type,
  • (2.6)
    [i, j) denotes a valid range,
  • (2.7)
    rg denotes a value of a type R that models container-compatible-range<T>,
  • (2.8)
    il designates an object of type initializer_list<value_type>,
  • (2.9)
    n denotes a value of type X​::​size_type,
  • (2.10)
    p denotes a valid constant iterator to a,
  • (2.11)
    q denotes a valid dereferenceable constant iterator to a,
  • (2.12)
    [q1, q2) denotes a valid range of constant iterators in a,
  • (2.13)
    t denotes an lvalue or a const rvalue of X​::​value_type, and
  • (2.14)
    rv denotes a non-const rvalue of X​::​value_type.
  • (2.15)
    Args denotes a template parameter pack;
  • (2.16)
    args denotes a function parameter pack with the pattern Args&&.
3
#
The complexities of the expressions are sequence dependent.
4
#
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);
5
#
Preconditions: T is Cpp17CopyInsertable into X.
6
#
Effects: Constructs a sequence container with n copies of t.
7
#
Postconditions: distance(u.begin(), u.end()) == n is true.
🔗
X u(i, j);
8
#
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.
9
#
Effects: Constructs a sequence container equal to the range [i, j).
Each iterator in the range [i, j) is dereferenced exactly once.
10
#
Postconditions: distance(u.begin(), u.end()) == distance(i, j) is true.
🔗
X(from_range, rg)
11
#
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.
12
#
Effects: Constructs a sequence container equal to the range rg.
Each iterator in the range rg is dereferenced exactly once.
13
#
Postconditions: distance(begin(), end()) == ranges​::​distance(rg) is true.
14
#
Effects: Equivalent to X(il.begin(), il.end()).
🔗
a = il
15
#
Result: X&.
16
#
Preconditions: T is Cpp17CopyInsertable into X and Cpp17CopyAssignable.
17
#
Effects: Assigns the range [il.begin(), il.end()) into a.
All existing elements of a are either assigned to or destroyed.
18
#
Returns: *this.
🔗
a.emplace(p, args)
19
#
Result: iterator.
20
#
Preconditions: T is Cpp17EmplaceConstructible into X from args.
For vector and deque, T is also Cpp17MoveInsertable into X and Cpp17MoveAssignable.
21
#
Effects: Inserts an object of type T constructed with std​::​forward<Args>(args)... before p.
[Note 1: 
args can directly or indirectly refer to a value in a.
— end note]
22
#
Returns: An iterator that points to the new element constructed from args into a.
🔗
a.insert(p, t)
23
#
Result: iterator.
24
#
Preconditions: T is Cpp17CopyInsertable into X.
For vector and deque, T is also Cpp17CopyAssignable.
25
#
Effects: Inserts a copy of t before p.
26
#
Returns: An iterator that points to the copy of t inserted into a.
🔗
a.insert(p, rv)
27
#
Result: iterator.
28
#
Preconditions: T is Cpp17MoveInsertable into X.
For vector and deque, T is also Cpp17MoveAssignable.
29
#
Effects: Inserts a copy of rv before p.
30
#
Returns: An iterator that points to the copy of rv inserted into a.
🔗
a.insert(p, n, t)
31
#
Result: iterator.
32
#
Preconditions: T is Cpp17CopyInsertable into X and Cpp17CopyAssignable.
33
#
Effects: Inserts n copies of t before p.
34
#
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)
35
#
Result: iterator.
36
#
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.
37
#
Effects: Inserts copies of elements in [i, j) before p.
Each iterator in the range [i, j) shall be dereferenced exactly once.
38
#
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)
39
#
Result: iterator.
40
#
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.
41
#
Effects: Inserts copies of elements in rg before p.
Each iterator in the range rg is dereferenced exactly once.
42
#
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)
43
#
Effects: Equivalent to a.insert(p, il.begin(), il.end()).
🔗
a.erase(q)
44
#
Result: iterator.
45
#
Preconditions: For vector and deque, T is Cpp17MoveAssignable.
46
#
Effects: Erases the element pointed to by q.
47
#
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)
48
#
Result: iterator.
49
#
Preconditions: For vector and deque, T is Cpp17MoveAssignable.
50
#
Effects: Erases the elements in the range [q1, q2).
51
#
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()
52
#
Result: void
53
#
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.
54
#
Postconditions: a.empty() is true.
55
#
Complexity: Linear.
🔗
a.assign(i, j)
56
#
Result: void
57
#
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.
58
#
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)
59
#
Result: void
60
#
Mandates: assignable_from<T&, ranges​::​range_reference_t<R>> is modeled.
61
#
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.
62
#
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)
63
#
Effects: Equivalent to a.assign(il.begin(), il.end()).
🔗
a.assign(n, t)
64
#
Result: void
65
#
Preconditions: T is Cpp17CopyInsertable into X and Cpp17CopyAssignable.
t is not a reference into a.
66
#
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.
67
#
For every sequence container defined in this Clause and in [strings]:
  • (67.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.
  • (67.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.
  • (67.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.
68
#
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()
69
#
Result: reference; const_reference for constant a.
70
#
Returns: *a.begin()
71
#
Remarks: Required for basic_string, array, deque, forward_list, list, and vector.
🔗
a.back()
72
#
Result: reference; const_reference for constant a.
73
#
Effects: Equivalent to: auto tmp = a.end(); --tmp; return *tmp;
74
#
Remarks: Required for basic_string, array, deque, list, and vector.
🔗
a.emplace_front(args)
75
#
Result: reference
76
#
Preconditions: T is Cpp17EmplaceConstructible into X from args.
77
#
Effects: Prepends an object of type T constructed with std​::​forward<Args>(args)....
78
#
Returns: a.front().
79
#
Remarks: Required for deque, forward_list, and list.
🔗
a.emplace_back(args)
80
#
Result: reference
81
#
Preconditions: T is Cpp17EmplaceConstructible into X from args.
For vector, T is also Cpp17MoveInsertable into X.
82
#
Effects: Appends an object of type T constructed with std​::​forward<Args>(args)....
83
#
Returns: a.back().
84
#
Remarks: Required for deque, list, and vector.
🔗
a.push_front(t)
85
#
Result: void
86
#
Preconditions: T is Cpp17CopyInsertable into X.
87
#
Effects: Prepends a copy of t.
88
#
Remarks: Required for deque, forward_list, and list.
🔗
a.push_front(rv)
89
#
Result: void
90
#
Preconditions: T is Cpp17MoveInsertable into X.
91
#
Effects: Prepends a copy of rv.
92
#
Remarks: Required for deque, forward_list, and list.
🔗
a.prepend_range(rg)
93
#
Result: void
94
#
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.
95
#
Effects: Inserts copies of elements in rg before begin().
Each iterator in the range rg is dereferenced exactly once.
[Note 2: 
The order of elements in rg is not reversed.
— end note]
96
#
Remarks: Required for deque, forward_list, and list.
🔗
a.push_back(t)
97
#
Result: void
98
#
Preconditions: T is Cpp17CopyInsertable into X.
99
#
Effects: Appends a copy of t.
100
#
Remarks: Required for basic_string, deque, list, and vector.
🔗
a.push_back(rv)
101
#
Result: void
102
#
Preconditions: T is Cpp17MoveInsertable into X.
103
#
Effects: Appends a copy of rv.
104
#
Remarks: Required for basic_string, deque, list, and vector.
🔗
a.append_range(rg)
105
#
Result: void
106
#
Preconditions: T is Cpp17EmplaceConstructible into X from *ranges​::​begin(rg).
For vector, T is also Cpp17MoveInsertable into X.
107
#
Effects: Inserts copies of elements in rg before end().
Each iterator in the range rg is dereferenced exactly once.
108
#
Remarks: Required for deque, list, and vector.
🔗
a.pop_front()
109
#
Result: void
110
#
Preconditions: a.empty() is false.
111
#
Effects: Destroys the first element.
112
#
Remarks: Required for deque, forward_list, and list.
🔗
a.pop_back()
113
#
Result: void
114
#
Preconditions: a.empty() is false.
115
#
Effects: Destroys the last element.
116
#
Remarks: Required for basic_string, deque, list, and vector.
117
#
Result: reference; const_reference for constant a
118
#
Effects: Equivalent to: return *(a.begin() + n);
119
#
Remarks: Required for basic_string, array, deque, and vector.
🔗
a.at(n)
120
#
Result: reference; const_reference for constant a
121
#
Returns: *(a.begin() + n)
122
#
Throws: out_of_range if n >= a.size().
123
#
Remarks: Required for basic_string, array, deque, and vector.