From Jason Turner

[list]

C++20 → C++23 14.5 KB 159 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/tmpqdqxz_9v/{from.md → to.md} +87 -60
tmp/tmpqdqxz_9v/{from.md → to.md} RENAMED
@@ -6,19 +6,21 @@ A `list` is a sequence container that supports bidirectional iterators
6
  and allows constant time insert and erase operations anywhere within the
7
  sequence, with storage management handled automatically. Unlike vectors
8
  [[vector]] and deques [[deque]], fast random access to list elements is
9
  not supported, but many algorithms only need sequential access anyway.
10
 
11
- A `list` meets all of the requirements of a container, of a reversible
12
- container (given in two tables in [[container.requirements]]), of a
13
- sequence container, including most of the optional sequence container
14
- requirements [[sequence.reqmts]], and of an allocator-aware container (
15
- [[container.alloc.req]]). The exceptions are the `operator[]` and `at`
16
- member functions, which are not provided.[^2] Descriptions are provided
17
- here only for operations on `list` that are not described in one of
18
- these tables or for operations where there is additional semantic
19
- information.
 
 
20
 
21
  ``` cpp
22
  namespace std {
23
  template<class T, class Allocator = allocator<T>>
24
  class list {
@@ -28,12 +30,12 @@ namespace std {
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; // see [container.requirements]
34
- using difference_type = implementation-defined; // see [container.requirements]
35
  using iterator = implementation-defined // type of list::iterator; // see [container.requirements]
36
  using const_iterator = implementation-defined // type of list::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,22 +44,26 @@ namespace std {
42
  explicit list(const Allocator&);
43
  explicit list(size_type n, const Allocator& = Allocator());
44
  list(size_type n, const T& value, const Allocator& = Allocator());
45
  template<class InputIterator>
46
  list(InputIterator first, InputIterator last, const Allocator& = Allocator());
 
 
47
  list(const list& x);
48
  list(list&& x);
49
- list(const list&, const Allocator&);
50
- list(list&&, const Allocator&);
51
  list(initializer_list<T>, const Allocator& = Allocator());
52
  ~list();
53
  list& operator=(const list& x);
54
  list& operator=(list&& x)
55
  noexcept(allocator_traits<Allocator>::is_always_equal::value);
56
  list& 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
@@ -91,21 +97,27 @@ namespace std {
91
  // [list.modifiers], modifiers
92
  template<class... Args> reference emplace_front(Args&&... args);
93
  template<class... Args> reference emplace_back(Args&&... args);
94
  void push_front(const T& x);
95
  void push_front(T&& x);
 
 
96
  void pop_front();
97
  void push_back(const T& x);
98
  void push_back(T&& x);
 
 
99
  void pop_back();
100
 
101
  template<class... Args> iterator emplace(const_iterator position, Args&&... args);
102
  iterator insert(const_iterator position, const T& x);
103
  iterator insert(const_iterator position, T&& x);
104
  iterator insert(const_iterator position, size_type n, const T& x);
105
  template<class InputIterator>
106
  iterator insert(const_iterator position, InputIterator first, InputIterator last);
 
 
107
  iterator insert(const_iterator position, initializer_list<T> il);
108
 
109
  iterator erase(const_iterator position);
110
  iterator erase(const_iterator position, const_iterator last);
111
  void swap(list&) noexcept(allocator_traits<Allocator>::is_always_equal::value);
@@ -139,14 +151,13 @@ namespace std {
139
 
140
  template<class InputIterator, class Allocator = allocator<iter-value-type<InputIterator>>>
141
  list(InputIterator, InputIterator, Allocator = Allocator())
142
  -> list<iter-value-type<InputIterator>, Allocator>;
143
 
144
- // swap
145
- template<class T, class Allocator>
146
- void swap(list<T, Allocator>& x, list<T, Allocator>& y)
147
- noexcept(noexcept(x.swap(y)));
148
  }
149
  ```
150
 
151
  An incomplete type `T` may be used when instantiating `list` if the
152
  allocator meets the allocator completeness requirements
@@ -192,10 +203,20 @@ template<class InputIterator>
192
 
193
  *Effects:* Constructs a `list` equal to the range \[`first`, `last`).
194
 
195
  *Complexity:* Linear in `distance(first, last)`.
196
 
 
 
 
 
 
 
 
 
 
 
197
  #### Capacity <a id="list.capacity">[[list.capacity]]</a>
198
 
199
  ``` cpp
200
  void resize(size_type sz);
201
  ```
@@ -238,30 +259,36 @@ iterator insert(const_iterator position, const T& x);
238
  iterator insert(const_iterator position, T&& x);
239
  iterator insert(const_iterator position, size_type n, const T& x);
240
  template<class InputIterator>
241
  iterator insert(const_iterator position, InputIterator first,
242
  InputIterator last);
 
 
243
  iterator insert(const_iterator position, initializer_list<T>);
244
 
245
  template<class... Args> reference emplace_front(Args&&... args);
246
  template<class... Args> reference emplace_back(Args&&... args);
247
  template<class... Args> iterator emplace(const_iterator position, Args&&... args);
248
  void push_front(const T& x);
249
  void push_front(T&& x);
 
 
250
  void push_back(const T& x);
251
  void push_back(T&& x);
 
 
252
  ```
253
 
254
- *Remarks:* Does not affect the validity of iterators and references. If
255
- an exception is thrown there are no effects.
256
-
257
  *Complexity:* Insertion of a single element into a list takes constant
258
  time and exactly one call to a constructor of `T`. Insertion of multiple
259
  elements into a list is linear in the number of elements inserted, and
260
  the number of calls to the copy constructor or move constructor of `T`
261
  is exactly equal to the number of elements inserted.
262
 
 
 
 
263
  ``` cpp
264
  iterator erase(const_iterator position);
265
  iterator erase(const_iterator first, const_iterator last);
266
 
267
  void pop_front();
@@ -280,15 +307,18 @@ linear time in the size of the range and the number of calls to the
280
  destructor of type `T` is exactly equal to the size of the range.
281
 
282
  #### Operations <a id="list.ops">[[list.ops]]</a>
283
 
284
  Since lists allow fast insertion and erasing from the middle of a list,
285
- certain operations are provided specifically for them.[^3] In this
286
- subclause, arguments for a template parameter named `Predicate` or
287
- `BinaryPredicate` shall meet the corresponding requirements in
288
- [[algorithms.requirements]]. For `merge` and `sort`, the definitions and
289
- requirements in [[alg.sorting]] apply.
 
 
 
290
 
291
  `list` provides three splice operations that destructively move elements
292
  from one list to another. The behavior of splice operations is undefined
293
  if `get_allocator() !=
294
  x.get_allocator()`.
@@ -363,67 +393,64 @@ the erased elements.
363
  *Returns:* The number of elements erased.
364
 
365
  *Throws:* Nothing unless an exception is thrown by `*i == value` or
366
  `pred(*i) != false`.
367
 
368
- *Remarks:* Stable [[algorithm.stable]].
369
-
370
  *Complexity:* Exactly `size()` applications of the corresponding
371
  predicate.
372
 
 
 
373
  ``` cpp
374
  size_type unique();
375
  template<class BinaryPredicate> size_type unique(BinaryPredicate binary_pred);
376
  ```
377
 
 
 
 
 
378
  *Effects:* Erases all but the first element from every consecutive group
379
- of equal elements referred to by the iterator `i` in the range
380
- \[`first + 1`, `last`) for which `*i == *(i-1)` (for the version of
381
- `unique` with no arguments) or `pred(*i, *(i - 1))` (for the version of
382
- `unique` with a predicate argument) holds. Invalidates only the
383
- iterators and references to the erased elements.
384
 
385
  *Returns:* The number of elements erased.
386
 
387
- *Throws:* Nothing unless an exception is thrown by `*i == *(i-1)` or
388
- `pred(*i, *(i - 1))`
389
 
390
- *Complexity:* If the range `[first, last)` is not empty, exactly
391
- `(last - first) - 1` applications of the corresponding predicate,
392
- otherwise no applications of the predicate.
393
 
394
  ``` cpp
395
  void merge(list& x);
396
  void merge(list&& x);
397
  template<class Compare> void merge(list& x, Compare comp);
398
  template<class Compare> void merge(list&& x, Compare comp);
399
  ```
400
 
401
- *Preconditions:* Both the list and the argument list shall be sorted
402
- with respect to the comparator `operator<` (for the first two overloads)
403
- or `comp` (for the last two overloads), and
404
- `get_allocator() == x.get_allocator()` is `true`.
405
 
406
- *Effects:* If `addressof(x) == this`, does nothing; otherwise, merges
407
- the two sorted ranges `[begin(), end())` and `[x.begin(), x.end())`. The
408
- result is a range in which the elements will be sorted in non-decreasing
409
- order according to the ordering defined by `comp`; that is, for every
410
- iterator `i`, in the range other than the first, the condition
411
- `comp(*i, *(i - 1))` will be `false`. Pointers and references to the
412
- moved elements of `x` now refer to those same elements but as members of
413
- `*this`. Iterators referring to the moved elements will continue to
414
- refer to their elements, but they now behave as iterators into `*this`,
415
- not into `x`.
416
 
417
- *Remarks:* Stable [[algorithm.stable]]. If `addressof(x) != this`, the
418
- range `[x.begin(), x.end())` is empty after the merge. No elements are
419
- copied by this operation.
 
 
 
 
420
 
421
- *Complexity:* At most `size() + x.size() - 1` applications of `comp` if
422
- `addressof(x) != this`; otherwise, no applications of `comp` are
423
- performed. If an exception is thrown other than by a comparison there
424
- are no effects.
 
 
425
 
426
  ``` cpp
427
  void reverse() noexcept;
428
  ```
429
 
@@ -440,14 +467,14 @@ template<class Compare> void sort(Compare comp);
440
  *Effects:* Sorts the list according to the `operator<` or a `Compare`
441
  function object. If an exception is thrown, the order of the elements in
442
  `*this` is unspecified. Does not affect the validity of iterators and
443
  references.
444
 
445
- *Remarks:* Stable [[algorithm.stable]].
446
-
447
  *Complexity:* Approximately N log N comparisons, where `N == size()`.
448
 
 
 
449
  #### Erasure <a id="list.erasure">[[list.erasure]]</a>
450
 
451
  ``` cpp
452
  template<class T, class Allocator, class U>
453
  typename list<T, Allocator>::size_type
 
6
  and allows constant time insert and erase operations anywhere within the
7
  sequence, with storage management handled automatically. Unlike vectors
8
  [[vector]] and deques [[deque]], fast random access to list elements is
9
  not supported, but many algorithms only need sequential access anyway.
10
 
11
+ A `list` meets all of the requirements of a container
12
+ [[container.reqmts]], of a reversible container
13
+ [[container.rev.reqmts]], of an allocator-aware container
14
+ [[container.alloc.reqmts]], and of a sequence container, including most
15
+ of the optional sequence container requirements [[sequence.reqmts]]. The
16
+ exceptions are the `operator[]` and `at` member functions, which are not
17
+ provided.[^2]
18
+
19
+ Descriptions are provided here only for operations on `list` that are
20
+ not described in one of these tables or for operations where there is
21
+ additional semantic information.
22
 
23
  ``` cpp
24
  namespace std {
25
  template<class T, class Allocator = allocator<T>>
26
  class list {
 
30
  using allocator_type = Allocator;
31
  using pointer = typename allocator_traits<Allocator>::pointer;
32
  using const_pointer = typename allocator_traits<Allocator>::const_pointer;
33
  using reference = value_type&;
34
  using const_reference = const value_type&;
35
+ using size_type = implementation-defined // type of list::size_type; // see [container.requirements]
36
+ using difference_type = implementation-defined // type of list::difference_type; // see [container.requirements]
37
  using iterator = implementation-defined // type of list::iterator; // see [container.requirements]
38
  using const_iterator = implementation-defined // type of list::const_iterator; // see [container.requirements]
39
  using reverse_iterator = std::reverse_iterator<iterator>;
40
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
41
 
 
44
  explicit list(const Allocator&);
45
  explicit list(size_type n, const Allocator& = Allocator());
46
  list(size_type n, const T& value, const Allocator& = Allocator());
47
  template<class InputIterator>
48
  list(InputIterator first, InputIterator last, const Allocator& = Allocator());
49
+ template<container-compatible-range<T> R>
50
+ list(from_range_t, R&& rg, const Allocator& = Allocator());
51
  list(const list& x);
52
  list(list&& x);
53
+ list(const list&, const type_identity_t<Allocator>&);
54
+ list(list&&, const type_identity_t<Allocator>&);
55
  list(initializer_list<T>, const Allocator& = Allocator());
56
  ~list();
57
  list& operator=(const list& x);
58
  list& operator=(list&& x)
59
  noexcept(allocator_traits<Allocator>::is_always_equal::value);
60
  list& operator=(initializer_list<T>);
61
  template<class InputIterator>
62
  void assign(InputIterator first, InputIterator last);
63
+ template<container-compatible-range<T> R>
64
+ void assign_range(R&& rg);
65
  void assign(size_type n, const T& t);
66
  void assign(initializer_list<T>);
67
  allocator_type get_allocator() const noexcept;
68
 
69
  // iterators
 
97
  // [list.modifiers], modifiers
98
  template<class... Args> reference emplace_front(Args&&... args);
99
  template<class... Args> reference emplace_back(Args&&... args);
100
  void push_front(const T& x);
101
  void push_front(T&& x);
102
+ template<container-compatible-range<T> R>
103
+ void prepend_range(R&& rg);
104
  void pop_front();
105
  void push_back(const T& x);
106
  void push_back(T&& x);
107
+ template<container-compatible-range<T> R>
108
+ void append_range(R&& rg);
109
  void pop_back();
110
 
111
  template<class... Args> iterator emplace(const_iterator position, Args&&... args);
112
  iterator insert(const_iterator position, const T& x);
113
  iterator insert(const_iterator position, T&& x);
114
  iterator insert(const_iterator position, size_type n, const T& x);
115
  template<class InputIterator>
116
  iterator insert(const_iterator position, InputIterator first, InputIterator last);
117
+ template<container-compatible-range<T> R>
118
+ iterator insert_range(const_iterator position, R&& rg);
119
  iterator insert(const_iterator position, initializer_list<T> il);
120
 
121
  iterator erase(const_iterator position);
122
  iterator erase(const_iterator position, const_iterator last);
123
  void swap(list&) noexcept(allocator_traits<Allocator>::is_always_equal::value);
 
151
 
152
  template<class InputIterator, class Allocator = allocator<iter-value-type<InputIterator>>>
153
  list(InputIterator, InputIterator, Allocator = Allocator())
154
  -> list<iter-value-type<InputIterator>, Allocator>;
155
 
156
+ template<ranges::input_range R, class Allocator = allocator<ranges::range_value_t<R>>>
157
+ list(from_range_t, R&&, Allocator = Allocator())
158
+ -> list<ranges::range_value_t<R>, Allocator>;
 
159
  }
160
  ```
161
 
162
  An incomplete type `T` may be used when instantiating `list` if the
163
  allocator meets the allocator completeness requirements
 
203
 
204
  *Effects:* Constructs a `list` equal to the range \[`first`, `last`).
205
 
206
  *Complexity:* Linear in `distance(first, last)`.
207
 
208
+ ``` cpp
209
+ template<container-compatible-range<T> R>
210
+ list(from_range_t, R&& rg, const Allocator& = Allocator());
211
+ ```
212
+
213
+ *Effects:* Constructs a `list` object with the elements of the range
214
+ `rg`.
215
+
216
+ *Complexity:* Linear in `ranges::distance(rg)`.
217
+
218
  #### Capacity <a id="list.capacity">[[list.capacity]]</a>
219
 
220
  ``` cpp
221
  void resize(size_type sz);
222
  ```
 
259
  iterator insert(const_iterator position, T&& x);
260
  iterator insert(const_iterator position, size_type n, const T& x);
261
  template<class InputIterator>
262
  iterator insert(const_iterator position, InputIterator first,
263
  InputIterator last);
264
+ template<container-compatible-range<T> R>
265
+ iterator insert_range(const_iterator position, R&& rg);
266
  iterator insert(const_iterator position, initializer_list<T>);
267
 
268
  template<class... Args> reference emplace_front(Args&&... args);
269
  template<class... Args> reference emplace_back(Args&&... args);
270
  template<class... Args> iterator emplace(const_iterator position, Args&&... args);
271
  void push_front(const T& x);
272
  void push_front(T&& x);
273
+ template<container-compatible-range<T> R>
274
+ void prepend_range(R&& rg);
275
  void push_back(const T& x);
276
  void push_back(T&& x);
277
+ template<container-compatible-range<T> R>
278
+ void append_range(R&& rg);
279
  ```
280
 
 
 
 
281
  *Complexity:* Insertion of a single element into a list takes constant
282
  time and exactly one call to a constructor of `T`. Insertion of multiple
283
  elements into a list is linear in the number of elements inserted, and
284
  the number of calls to the copy constructor or move constructor of `T`
285
  is exactly equal to the number of elements inserted.
286
 
287
+ *Remarks:* Does not affect the validity of iterators and references. If
288
+ an exception is thrown there are no effects.
289
+
290
  ``` cpp
291
  iterator erase(const_iterator position);
292
  iterator erase(const_iterator first, const_iterator last);
293
 
294
  void pop_front();
 
307
  destructor of type `T` is exactly equal to the size of the range.
308
 
309
  #### Operations <a id="list.ops">[[list.ops]]</a>
310
 
311
  Since lists allow fast insertion and erasing from the middle of a list,
312
+ certain operations are provided specifically for them.[^3]
313
+
314
+ In this subclause, arguments for a template parameter named `Predicate`
315
+ or `BinaryPredicate` shall meet the corresponding requirements in
316
+ [[algorithms.requirements]]. The semantics of `i + n` and `i - n`, where
317
+ `i` is an iterator into the list and `n` is an integer, are the same as
318
+ those of `next(i, n)` and `prev(i, n)`, respectively. For `merge` and
319
+ `sort`, the definitions and requirements in [[alg.sorting]] apply.
320
 
321
  `list` provides three splice operations that destructively move elements
322
  from one list to another. The behavior of splice operations is undefined
323
  if `get_allocator() !=
324
  x.get_allocator()`.
 
393
  *Returns:* The number of elements erased.
394
 
395
  *Throws:* Nothing unless an exception is thrown by `*i == value` or
396
  `pred(*i) != false`.
397
 
 
 
398
  *Complexity:* Exactly `size()` applications of the corresponding
399
  predicate.
400
 
401
+ *Remarks:* Stable [[algorithm.stable]].
402
+
403
  ``` cpp
404
  size_type unique();
405
  template<class BinaryPredicate> size_type unique(BinaryPredicate binary_pred);
406
  ```
407
 
408
+ Let `binary_pred` be `equal_to<>{}` for the first overload.
409
+
410
+ *Preconditions:* `binary_pred` is an equivalence relation.
411
+
412
  *Effects:* Erases all but the first element from every consecutive group
413
+ of equivalent elements. That is, for a nonempty list, erases all
414
+ elements referred to by the iterator `i` in the range \[`begin() + 1`,
415
+ `end()`) for which `binary_pred(*i, *(i - 1))` is `true`. Invalidates
416
+ only the iterators and references to the erased elements.
 
417
 
418
  *Returns:* The number of elements erased.
419
 
420
+ *Throws:* Nothing unless an exception is thrown by the predicate.
 
421
 
422
+ *Complexity:* If `empty()` is `false`, exactly `size() - 1` applications
423
+ of the corresponding predicate, otherwise no applications of the
424
+ predicate.
425
 
426
  ``` cpp
427
  void merge(list& x);
428
  void merge(list&& x);
429
  template<class Compare> void merge(list& x, Compare comp);
430
  template<class Compare> void merge(list&& x, Compare comp);
431
  ```
432
 
433
+ Let `comp` be `less<>` for the first two overloads.
 
 
 
434
 
435
+ *Preconditions:* `*this` and `x` are both sorted with respect to the
436
+ comparator `comp`, and `get_allocator() == x.get_allocator()` is `true`.
 
 
 
 
 
 
 
 
437
 
438
+ *Effects:* If `addressof(x) == this`, there are no effects. Otherwise,
439
+ merges the two sorted ranges \[`begin()`, `end()`) and \[`x.begin()`,
440
+ `x.end()`). The result is a range that is sorted with respect to the
441
+ comparator `comp`. Pointers and references to the moved elements of `x`
442
+ now refer to those same elements but as members of `*this`. Iterators
443
+ referring to the moved elements will continue to refer to their
444
+ elements, but they now behave as iterators into `*this`, not into `x`.
445
 
446
+ *Complexity:* At most `size() + x.size() - 1` comparisons if
447
+ `addressof(x) != this`; otherwise, no comparisons are performed.
448
+
449
+ *Remarks:* Stable [[algorithm.stable]]. If `addressof(x) != this`, `x`
450
+ is empty after the merge. No elements are copied by this operation. If
451
+ an exception is thrown other than by a comparison there are no effects.
452
 
453
  ``` cpp
454
  void reverse() noexcept;
455
  ```
456
 
 
467
  *Effects:* Sorts the list according to the `operator<` or a `Compare`
468
  function object. If an exception is thrown, the order of the elements in
469
  `*this` is unspecified. Does not affect the validity of iterators and
470
  references.
471
 
 
 
472
  *Complexity:* Approximately N log N comparisons, where `N == size()`.
473
 
474
+ *Remarks:* Stable [[algorithm.stable]].
475
+
476
  #### Erasure <a id="list.erasure">[[list.erasure]]</a>
477
 
478
  ``` cpp
479
  template<class T, class Allocator, class U>
480
  typename list<T, Allocator>::size_type