From Jason Turner

[deque]

C++20 → C++23 10.3 KB 93 lines
Current Draft | LaTeX Source
Archived: C++20 | C++23
Markdown: C++20 | C++23
Explore in Adventure Game

Diff to HTML by rtfpessoa

Files changed (1) hide show
  1. tmp/tmpy2_7xq56/{from.md → to.md} +54 -28
tmp/tmpy2_7xq56/{from.md → to.md} RENAMED
@@ -7,17 +7,18 @@ A `deque` is a sequence container that supports random access iterators
7
  insert and erase operations at the beginning or the end; insert and
8
  erase in the middle take linear time. That is, a deque is especially
9
  optimized for pushing and popping elements at the beginning and end.
10
  Storage management is handled automatically.
11
 
12
- A `deque` meets all of the requirements of a container, of a reversible
13
- container (given in tables in  [[container.requirements]]), of a
14
- sequence container, including the optional sequence container
15
- requirements [[sequence.reqmts]], and of an allocator-aware container (
16
- [[container.alloc.req]]). Descriptions are provided here only for
17
- operations on `deque` that are not described in one of these tables or
18
- for operations where there is additional semantic information.
 
19
 
20
  ``` cpp
21
  namespace std {
22
  template<class T, class Allocator = allocator<T>>
23
  class deque {
@@ -27,12 +28,12 @@ namespace std {
27
  using allocator_type = Allocator;
28
  using pointer = typename allocator_traits<Allocator>::pointer;
29
  using const_pointer = typename allocator_traits<Allocator>::const_pointer;
30
  using reference = value_type&;
31
  using const_reference = const value_type&;
32
- using size_type = implementation-defined; // see [container.requirements]
33
- using difference_type = implementation-defined; // see [container.requirements]
34
  using iterator = implementation-defined // type of deque::iterator; // see [container.requirements]
35
  using const_iterator = implementation-defined // type of deque::const_iterator; // see [container.requirements]
36
  using reverse_iterator = std::reverse_iterator<iterator>;
37
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
38
 
@@ -41,23 +42,27 @@ namespace std {
41
  explicit deque(const Allocator&);
42
  explicit deque(size_type n, const Allocator& = Allocator());
43
  deque(size_type n, const T& value, const Allocator& = Allocator());
44
  template<class InputIterator>
45
  deque(InputIterator first, InputIterator last, const Allocator& = Allocator());
 
 
46
  deque(const deque& x);
47
  deque(deque&&);
48
- deque(const deque&, const Allocator&);
49
- deque(deque&&, const Allocator&);
50
  deque(initializer_list<T>, const Allocator& = Allocator());
51
 
52
  ~deque();
53
  deque& operator=(const deque& x);
54
  deque& operator=(deque&& x)
55
  noexcept(allocator_traits<Allocator>::is_always_equal::value);
56
  deque& operator=(initializer_list<T>);
57
  template<class InputIterator>
58
  void assign(InputIterator first, InputIterator last);
 
 
59
  void assign(size_type n, const T& t);
60
  void assign(initializer_list<T>);
61
  allocator_type get_allocator() const noexcept;
62
 
63
  // iterators
@@ -98,18 +103,24 @@ namespace std {
98
  template<class... Args> reference emplace_back(Args&&... args);
99
  template<class... Args> iterator emplace(const_iterator position, Args&&... args);
100
 
101
  void push_front(const T& x);
102
  void push_front(T&& x);
 
 
103
  void push_back(const T& x);
104
  void push_back(T&& x);
 
 
105
 
106
  iterator insert(const_iterator position, const T& x);
107
  iterator insert(const_iterator position, T&& x);
108
  iterator insert(const_iterator position, size_type n, const T& x);
109
  template<class InputIterator>
110
  iterator insert(const_iterator position, InputIterator first, InputIterator last);
 
 
111
  iterator insert(const_iterator position, initializer_list<T>);
112
 
113
  void pop_front();
114
  void pop_back();
115
 
@@ -122,14 +133,13 @@ namespace std {
122
 
123
  template<class InputIterator, class Allocator = allocator<iter-value-type<InputIterator>>>
124
  deque(InputIterator, InputIterator, Allocator = Allocator())
125
  -> deque<iter-value-type<InputIterator>, Allocator>;
126
 
127
- // swap
128
- template<class T, class Allocator>
129
- void swap(deque<T, Allocator>& x, deque<T, Allocator>& y)
130
- noexcept(noexcept(x.swap(y)));
131
  }
132
  ```
133
 
134
  #### Constructors, copy, and assignment <a id="deque.cons">[[deque.cons]]</a>
135
 
@@ -143,26 +153,26 @@ explicit deque(const Allocator&);
143
 
144
  ``` cpp
145
  explicit deque(size_type n, const Allocator& = Allocator());
146
  ```
147
 
 
 
148
  *Effects:* Constructs a `deque` with `n` default-inserted elements using
149
  the specified allocator.
150
 
151
- *Preconditions:* `T` is *Cpp17DefaultInsertable* into `*this`.
152
-
153
  *Complexity:* Linear in `n`.
154
 
155
  ``` cpp
156
  deque(size_type n, const T& value, const Allocator& = Allocator());
157
  ```
158
 
 
 
159
  *Effects:* Constructs a `deque` with `n` copies of `value`, using the
160
  specified allocator.
161
 
162
- *Preconditions:* `T` is *Cpp17CopyInsertable* into `*this`.
163
-
164
  *Complexity:* Linear in `n`.
165
 
166
  ``` cpp
167
  template<class InputIterator>
168
  deque(InputIterator first, InputIterator last, const Allocator& = Allocator());
@@ -171,10 +181,20 @@ template<class InputIterator>
171
  *Effects:* Constructs a `deque` equal to the range \[`first`, `last`),
172
  using the specified allocator.
173
 
174
  *Complexity:* Linear in `distance(first, last)`.
175
 
 
 
 
 
 
 
 
 
 
 
176
  #### Capacity <a id="deque.capacity">[[deque.capacity]]</a>
177
 
178
  ``` cpp
179
  void resize(size_type sz);
180
  ```
@@ -226,39 +246,45 @@ iterator insert(const_iterator position, const T& x);
226
  iterator insert(const_iterator position, T&& x);
227
  iterator insert(const_iterator position, size_type n, const T& x);
228
  template<class InputIterator>
229
  iterator insert(const_iterator position,
230
  InputIterator first, InputIterator last);
 
 
231
  iterator insert(const_iterator position, initializer_list<T>);
232
 
233
  template<class... Args> reference emplace_front(Args&&... args);
234
  template<class... Args> reference emplace_back(Args&&... args);
235
  template<class... Args> iterator emplace(const_iterator position, Args&&... args);
236
  void push_front(const T& x);
237
  void push_front(T&& x);
 
 
238
  void push_back(const T& x);
239
  void push_back(T&& x);
 
 
240
  ```
241
 
242
  *Effects:* An insertion in the middle of the deque invalidates all the
243
  iterators and references to elements of the deque. An insertion at
244
  either end of the deque invalidates all the iterators to the deque, but
245
  has no effect on the validity of references to elements of the deque.
246
 
 
 
 
 
 
 
247
  *Remarks:* If an exception is thrown other than by the copy constructor,
248
  move constructor, assignment operator, or move assignment operator of
249
  `T` there are no effects. If an exception is thrown while inserting a
250
  single element at either end, there are no effects. Otherwise, if an
251
  exception is thrown by the move constructor of a
252
  non-*Cpp17CopyInsertable* `T`, the effects are unspecified.
253
 
254
- *Complexity:* The complexity is linear in the number of elements
255
- inserted plus the lesser of the distances to the beginning and end of
256
- the deque. Inserting a single element at either the beginning or end of
257
- a deque always takes constant time and causes a single call to a
258
- constructor of `T`.
259
-
260
  ``` cpp
261
  iterator erase(const_iterator position);
262
  iterator erase(const_iterator first, const_iterator last);
263
  void pop_front();
264
  void pop_back();
@@ -274,19 +300,19 @@ invalidates the past-the-end iterator and all iterators and references
274
  to all the elements of the deque.
275
 
276
  [*Note 1*: `pop_front` and `pop_back` are erase
277
  operations. — *end note*]
278
 
 
 
 
279
  *Complexity:* The number of calls to the destructor of `T` is the same
280
  as the number of elements erased, but the number of calls to the
281
  assignment operator of `T` is no more than the lesser of the number of
282
  elements before the erased elements and the number of elements after the
283
  erased elements.
284
 
285
- *Throws:* Nothing unless an exception is thrown by the assignment
286
- operator of `T`.
287
-
288
  #### Erasure <a id="deque.erasure">[[deque.erasure]]</a>
289
 
290
  ``` cpp
291
  template<class T, class Allocator, class U>
292
  typename deque<T, Allocator>::size_type
 
7
  insert and erase operations at the beginning or the end; insert and
8
  erase in the middle take linear time. That is, a deque is especially
9
  optimized for pushing and popping elements at the beginning and end.
10
  Storage management is handled automatically.
11
 
12
+ A `deque` meets all of the requirements of a container
13
+ [[container.reqmts]], of a reversible container
14
+ [[container.rev.reqmts]], of an allocator-aware container
15
+ [[container.alloc.reqmts]], and of a sequence container, including the
16
+ optional sequence container requirements [[sequence.reqmts]].
17
+ Descriptions are provided here only for operations on `deque` that are
18
+ not described in one of these tables or for operations where there is
19
+ additional semantic information.
20
 
21
  ``` cpp
22
  namespace std {
23
  template<class T, class Allocator = allocator<T>>
24
  class deque {
 
28
  using allocator_type = Allocator;
29
  using pointer = typename allocator_traits<Allocator>::pointer;
30
  using const_pointer = typename allocator_traits<Allocator>::const_pointer;
31
  using reference = value_type&;
32
  using const_reference = const value_type&;
33
+ using size_type = implementation-defined // type of deque::size_type; // see [container.requirements]
34
+ using difference_type = implementation-defined // type of deque::difference_type; // see [container.requirements]
35
  using iterator = implementation-defined // type of deque::iterator; // see [container.requirements]
36
  using const_iterator = implementation-defined // type of deque::const_iterator; // see [container.requirements]
37
  using reverse_iterator = std::reverse_iterator<iterator>;
38
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
39
 
 
42
  explicit deque(const Allocator&);
43
  explicit deque(size_type n, const Allocator& = Allocator());
44
  deque(size_type n, const T& value, const Allocator& = Allocator());
45
  template<class InputIterator>
46
  deque(InputIterator first, InputIterator last, const Allocator& = Allocator());
47
+ template<container-compatible-range<T> R>
48
+ deque(from_range_t, R&& rg, const Allocator& = Allocator());
49
  deque(const deque& x);
50
  deque(deque&&);
51
+ deque(const deque&, const type_identity_t<Allocator>&);
52
+ deque(deque&&, const type_identity_t<Allocator>&);
53
  deque(initializer_list<T>, const Allocator& = Allocator());
54
 
55
  ~deque();
56
  deque& operator=(const deque& x);
57
  deque& operator=(deque&& x)
58
  noexcept(allocator_traits<Allocator>::is_always_equal::value);
59
  deque& operator=(initializer_list<T>);
60
  template<class InputIterator>
61
  void assign(InputIterator first, InputIterator last);
62
+ template<container-compatible-range<T> R>
63
+ void assign_range(R&& rg);
64
  void assign(size_type n, const T& t);
65
  void assign(initializer_list<T>);
66
  allocator_type get_allocator() const noexcept;
67
 
68
  // iterators
 
103
  template<class... Args> reference emplace_back(Args&&... args);
104
  template<class... Args> iterator emplace(const_iterator position, Args&&... args);
105
 
106
  void push_front(const T& x);
107
  void push_front(T&& x);
108
+ template<container-compatible-range<T> R>
109
+ void prepend_range(R&& rg);
110
  void push_back(const T& x);
111
  void push_back(T&& x);
112
+ template<container-compatible-range<T> R>
113
+ void append_range(R&& rg);
114
 
115
  iterator insert(const_iterator position, const T& x);
116
  iterator insert(const_iterator position, T&& x);
117
  iterator insert(const_iterator position, size_type n, const T& x);
118
  template<class InputIterator>
119
  iterator insert(const_iterator position, InputIterator first, InputIterator last);
120
+ template<container-compatible-range<T> R>
121
+ iterator insert_range(const_iterator position, R&& rg);
122
  iterator insert(const_iterator position, initializer_list<T>);
123
 
124
  void pop_front();
125
  void pop_back();
126
 
 
133
 
134
  template<class InputIterator, class Allocator = allocator<iter-value-type<InputIterator>>>
135
  deque(InputIterator, InputIterator, Allocator = Allocator())
136
  -> deque<iter-value-type<InputIterator>, Allocator>;
137
 
138
+ template<ranges::input_range R, class Allocator = allocator<ranges::range_value_t<R>>>
139
+ deque(from_range_t, R&&, Allocator = Allocator())
140
+ -> deque<ranges::range_value_t<R>, Allocator>;
 
141
  }
142
  ```
143
 
144
  #### Constructors, copy, and assignment <a id="deque.cons">[[deque.cons]]</a>
145
 
 
153
 
154
  ``` cpp
155
  explicit deque(size_type n, const Allocator& = Allocator());
156
  ```
157
 
158
+ *Preconditions:* `T` is *Cpp17DefaultInsertable* into `*this`.
159
+
160
  *Effects:* Constructs a `deque` with `n` default-inserted elements using
161
  the specified allocator.
162
 
 
 
163
  *Complexity:* Linear in `n`.
164
 
165
  ``` cpp
166
  deque(size_type n, const T& value, const Allocator& = Allocator());
167
  ```
168
 
169
+ *Preconditions:* `T` is *Cpp17CopyInsertable* into `*this`.
170
+
171
  *Effects:* Constructs a `deque` with `n` copies of `value`, using the
172
  specified allocator.
173
 
 
 
174
  *Complexity:* Linear in `n`.
175
 
176
  ``` cpp
177
  template<class InputIterator>
178
  deque(InputIterator first, InputIterator last, const Allocator& = Allocator());
 
181
  *Effects:* Constructs a `deque` equal to the range \[`first`, `last`),
182
  using the specified allocator.
183
 
184
  *Complexity:* Linear in `distance(first, last)`.
185
 
186
+ ``` cpp
187
+ template<container-compatible-range<T> R>
188
+ deque(from_range_t, R&& rg, const Allocator& = Allocator());
189
+ ```
190
+
191
+ *Effects:* Constructs a `deque` with the elements of the range `rg`,
192
+ using the specified allocator.
193
+
194
+ *Complexity:* Linear in `ranges::distance(rg)`.
195
+
196
  #### Capacity <a id="deque.capacity">[[deque.capacity]]</a>
197
 
198
  ``` cpp
199
  void resize(size_type sz);
200
  ```
 
246
  iterator insert(const_iterator position, T&& x);
247
  iterator insert(const_iterator position, size_type n, const T& x);
248
  template<class InputIterator>
249
  iterator insert(const_iterator position,
250
  InputIterator first, InputIterator last);
251
+ template<container-compatible-range<T> R>
252
+ iterator insert_range(const_iterator position, R&& rg);
253
  iterator insert(const_iterator position, initializer_list<T>);
254
 
255
  template<class... Args> reference emplace_front(Args&&... args);
256
  template<class... Args> reference emplace_back(Args&&... args);
257
  template<class... Args> iterator emplace(const_iterator position, Args&&... args);
258
  void push_front(const T& x);
259
  void push_front(T&& x);
260
+ template<container-compatible-range<T> R>
261
+ void prepend_range(R&& rg);
262
  void push_back(const T& x);
263
  void push_back(T&& x);
264
+ template<container-compatible-range<T> R>
265
+ void append_range(R&& rg);
266
  ```
267
 
268
  *Effects:* An insertion in the middle of the deque invalidates all the
269
  iterators and references to elements of the deque. An insertion at
270
  either end of the deque invalidates all the iterators to the deque, but
271
  has no effect on the validity of references to elements of the deque.
272
 
273
+ *Complexity:* The complexity is linear in the number of elements
274
+ inserted plus the lesser of the distances to the beginning and end of
275
+ the deque. Inserting a single element at either the beginning or end of
276
+ a deque always takes constant time and causes a single call to a
277
+ constructor of `T`.
278
+
279
  *Remarks:* If an exception is thrown other than by the copy constructor,
280
  move constructor, assignment operator, or move assignment operator of
281
  `T` there are no effects. If an exception is thrown while inserting a
282
  single element at either end, there are no effects. Otherwise, if an
283
  exception is thrown by the move constructor of a
284
  non-*Cpp17CopyInsertable* `T`, the effects are unspecified.
285
 
 
 
 
 
 
 
286
  ``` cpp
287
  iterator erase(const_iterator position);
288
  iterator erase(const_iterator first, const_iterator last);
289
  void pop_front();
290
  void pop_back();
 
300
  to all the elements of the deque.
301
 
302
  [*Note 1*: `pop_front` and `pop_back` are erase
303
  operations. — *end note*]
304
 
305
+ *Throws:* Nothing unless an exception is thrown by the assignment
306
+ operator of `T`.
307
+
308
  *Complexity:* The number of calls to the destructor of `T` is the same
309
  as the number of elements erased, but the number of calls to the
310
  assignment operator of `T` is no more than the lesser of the number of
311
  elements before the erased elements and the number of elements after the
312
  erased elements.
313
 
 
 
 
314
  #### Erasure <a id="deque.erasure">[[deque.erasure]]</a>
315
 
316
  ``` cpp
317
  template<class T, class Allocator, class U>
318
  typename deque<T, Allocator>::size_type