From Jason Turner

[sequences]

C++23 → Trunk 142.7 KB 2526 lines
Current Draft | LaTeX Source
Archived: C++23
Markdown: C++23 | Trunk
Explore in Adventure Game
Large diff (142.7 KB) - rendering may be slow on some devices

Diff to HTML by rtfpessoa

Files changed (1) hide show
  1. tmp/tmpubdocvd4/{from.md → to.md} +1873 -587
tmp/tmpubdocvd4/{from.md → to.md} RENAMED
@@ -1,30 +1,31 @@
1
  ## Sequence containers <a id="sequences">[[sequences]]</a>
2
 
3
- ### In general <a id="sequences.general">[[sequences.general]]</a>
4
 
5
- The headers `<array>`, `<deque>`, `<forward_list>`, `<list>`, and
6
- `<vector>` define class templates that meet the requirements for
7
- sequence containers.
8
 
9
  The following exposition-only alias template may appear in deduction
10
  guides for sequence containers:
11
 
12
  ``` cpp
13
  template<class InputIterator>
14
- using iter-value-type = typename iterator_traits<InputIterator>::value_type; // exposition only
15
  ```
16
 
17
  ### Header `<array>` synopsis <a id="array.syn">[[array.syn]]</a>
18
 
19
  ``` cpp
 
20
  #include <compare> // see [compare.syn]
21
  #include <initializer_list> // see [initializer.list.syn]
22
 
23
  namespace std {
24
  // [array], class template array
25
- template<class T, size_t N> struct array;
26
 
27
  template<class T, size_t N>
28
  constexpr bool operator==(const array<T, N>& x, const array<T, N>& y);
29
  template<class T, size_t N>
30
  constexpr synth-three-way-result<T>
@@ -56,166 +57,10 @@ namespace std {
56
  template<size_t I, class T, size_t N>
57
  constexpr const T&& get(const array<T, N>&&) noexcept;
58
  }
59
  ```
60
 
61
- ### Header `<deque>` synopsis <a id="deque.syn">[[deque.syn]]</a>
62
-
63
- ``` cpp
64
- #include <compare> // see [compare.syn]
65
- #include <initializer_list> // see [initializer.list.syn]
66
-
67
- namespace std {
68
- // [deque], class template deque
69
- template<class T, class Allocator = allocator<T>> class deque;
70
-
71
- template<class T, class Allocator>
72
- bool operator==(const deque<T, Allocator>& x, const deque<T, Allocator>& y);
73
- template<class T, class Allocator>
74
- synth-three-way-result<T> operator<=>(const deque<T, Allocator>& x,
75
- \itcorr const deque<T, Allocator>& y);
76
-
77
- template<class T, class Allocator>
78
- void swap(deque<T, Allocator>& x, deque<T, Allocator>& y)
79
- noexcept(noexcept(x.swap(y)));
80
-
81
- // [deque.erasure], erasure
82
- template<class T, class Allocator, class U>
83
- typename deque<T, Allocator>::size_type
84
- erase(deque<T, Allocator>& c, const U& value);
85
- template<class T, class Allocator, class Predicate>
86
- typename deque<T, Allocator>::size_type
87
- erase_if(deque<T, Allocator>& c, Predicate pred);
88
-
89
- namespace pmr {
90
- template<class T>
91
- using deque = std::deque<T, polymorphic_allocator<T>>;
92
- }
93
- }
94
- ```
95
-
96
- ### Header `<forward_list>` synopsis <a id="forward.list.syn">[[forward.list.syn]]</a>
97
-
98
- ``` cpp
99
- #include <compare> // see [compare.syn]
100
- #include <initializer_list> // see [initializer.list.syn]
101
-
102
- namespace std {
103
- // [forward.list], class template forward_list
104
- template<class T, class Allocator = allocator<T>> class forward_list;
105
-
106
- template<class T, class Allocator>
107
- bool operator==(const forward_list<T, Allocator>& x, const forward_list<T, Allocator>& y);
108
- template<class T, class Allocator>
109
- synth-three-way-result<T> operator<=>(const forward_list<T, Allocator>& x,
110
- \itcorr const forward_list<T, Allocator>& y);
111
-
112
- template<class T, class Allocator>
113
- void swap(forward_list<T, Allocator>& x, forward_list<T, Allocator>& y)
114
- noexcept(noexcept(x.swap(y)));
115
-
116
- // [forward.list.erasure], erasure
117
- template<class T, class Allocator, class U>
118
- typename forward_list<T, Allocator>::size_type
119
- erase(forward_list<T, Allocator>& c, const U& value);
120
- template<class T, class Allocator, class Predicate>
121
- typename forward_list<T, Allocator>::size_type
122
- erase_if(forward_list<T, Allocator>& c, Predicate pred);
123
-
124
- namespace pmr {
125
- template<class T>
126
- using forward_list = std::forward_list<T, polymorphic_allocator<T>>;
127
- }
128
- }
129
- ```
130
-
131
- ### Header `<list>` synopsis <a id="list.syn">[[list.syn]]</a>
132
-
133
- ``` cpp
134
- #include <compare> // see [compare.syn]
135
- #include <initializer_list> // see [initializer.list.syn]
136
-
137
- namespace std {
138
- // [list], class template list
139
- template<class T, class Allocator = allocator<T>> class list;
140
-
141
- template<class T, class Allocator>
142
- bool operator==(const list<T, Allocator>& x, const list<T, Allocator>& y);
143
- template<class T, class Allocator>
144
- synth-three-way-result<T> operator<=>(const list<T, Allocator>& x,
145
- \itcorr const list<T, Allocator>& y);
146
-
147
- template<class T, class Allocator>
148
- void swap(list<T, Allocator>& x, list<T, Allocator>& y)
149
- noexcept(noexcept(x.swap(y)));
150
-
151
- // [list.erasure], erasure
152
- template<class T, class Allocator, class U>
153
- typename list<T, Allocator>::size_type
154
- erase(list<T, Allocator>& c, const U& value);
155
- template<class T, class Allocator, class Predicate>
156
- typename list<T, Allocator>::size_type
157
- erase_if(list<T, Allocator>& c, Predicate pred);
158
-
159
- namespace pmr {
160
- template<class T>
161
- using list = std::list<T, polymorphic_allocator<T>>;
162
- }
163
- }
164
- ```
165
-
166
- ### Header `<vector>` synopsis <a id="vector.syn">[[vector.syn]]</a>
167
-
168
- ``` cpp
169
- #include <compare> // see [compare.syn]
170
- #include <initializer_list> // see [initializer.list.syn]
171
-
172
- namespace std {
173
- // [vector], class template vector
174
- template<class T, class Allocator = allocator<T>> class vector;
175
-
176
- template<class T, class Allocator>
177
- constexpr bool operator==(const vector<T, Allocator>& x, const vector<T, Allocator>& y);
178
- template<class T, class Allocator>
179
- constexpr synth-three-way-result<T> operator<=>(const vector<T, Allocator>& x,
180
- \itcorr const vector<T, Allocator>& y);
181
-
182
- template<class T, class Allocator>
183
- constexpr void swap(vector<T, Allocator>& x, vector<T, Allocator>& y)
184
- noexcept(noexcept(x.swap(y)));
185
-
186
- // [vector.erasure], erasure
187
- template<class T, class Allocator, class U>
188
- constexpr typename vector<T, Allocator>::size_type
189
- erase(vector<T, Allocator>& c, const U& value);
190
- template<class T, class Allocator, class Predicate>
191
- constexpr typename vector<T, Allocator>::size_type
192
- erase_if(vector<T, Allocator>& c, Predicate pred);
193
-
194
- namespace pmr {
195
- template<class T>
196
- using vector = std::vector<T, polymorphic_allocator<T>>;
197
- }
198
-
199
- // [vector.bool], specialization of vector for bool
200
- // [vector.bool.pspc], partial class template specialization vector<bool, Allocator>
201
- template<class Allocator>
202
- class vector<bool, Allocator>;
203
-
204
- template<class T>
205
- constexpr bool is-vector-bool-reference = see below; // exposition only
206
-
207
- // hash support
208
- template<class T> struct hash;
209
- template<class Allocator> struct hash<vector<bool, Allocator>>;
210
-
211
- // [vector.bool.fmt], formatter specialization for vector<bool>
212
- template<class T, class charT> requires is-vector-bool-reference<T>
213
- struct formatter<T, charT>;
214
- }
215
- ```
216
-
217
  ### Class template `array` <a id="array">[[array]]</a>
218
 
219
  #### Overview <a id="array.overview">[[array.overview]]</a>
220
 
221
  The header `<array>` defines a class template for storing fixed-size
@@ -234,12 +79,12 @@ object is not empty if `N` > 0. An `array` meets some of the
234
  requirements of a sequence container [[sequence.reqmts]]. Descriptions
235
  are provided here only for operations on `array` that are not described
236
  in one of these tables and for operations where there is additional
237
  semantic information.
238
 
239
- `array<T, N>` is a structural type [[temp.param]] if `T` is a structural
240
- type. Two values `a1` and `a2` of type `array<T, N>` are
241
  template-argument-equivalent [[temp.type]] if and only if each pair of
242
  corresponding elements in `a1` and `a2` are
243
  template-argument-equivalent.
244
 
245
  The types `iterator` and `const_iterator` meet the constexpr iterator
@@ -282,19 +127,19 @@ namespace std {
282
  constexpr const_iterator cend() const noexcept;
283
  constexpr const_reverse_iterator crbegin() const noexcept;
284
  constexpr const_reverse_iterator crend() const noexcept;
285
 
286
  // capacity
287
- [[nodiscard]] constexpr bool empty() const noexcept;
288
  constexpr size_type size() const noexcept;
289
  constexpr size_type max_size() const noexcept;
290
 
291
  // element access
292
  constexpr reference operator[](size_type n);
293
  constexpr const_reference operator[](size_type n) const;
294
- constexpr reference at(size_type n);
295
- constexpr const_reference at(size_type n) const;
296
  constexpr reference front();
297
  constexpr const_reference front() const;
298
  constexpr reference back();
299
  constexpr const_reference back() const;
300
 
@@ -307,17 +152,16 @@ namespace std {
307
  }
308
  ```
309
 
310
  #### Constructors, copy, and assignment <a id="array.cons">[[array.cons]]</a>
311
 
312
- The conditions for an aggregate [[dcl.init.aggr]] shall be met. Class
313
- `array` relies on the implicitly-declared special member functions
314
  [[class.default.ctor]], [[class.dtor]], [[class.copy.ctor]] to conform
315
  to the container requirements table in  [[container.requirements]]. In
316
  addition to the requirements specified in the container requirements
317
- table, the implicit move constructor and move assignment operator for
318
- `array` require that `T` be *Cpp17MoveConstructible* or
319
  *Cpp17MoveAssignable*, respectively.
320
 
321
  ``` cpp
322
  template<class T, class... U>
323
  array(T, U...) -> array<T, 1 + sizeof...(U)>;
@@ -337,11 +181,11 @@ constexpr size_type size() const noexcept;
337
  constexpr T* data() noexcept;
338
  constexpr const T* data() const noexcept;
339
  ```
340
 
341
  *Returns:* A pointer such that \[`data()`, `data() + size()`) is a valid
342
- range. For a non-empty array, `data()` `==` `addressof(front())`.
343
 
344
  ``` cpp
345
  constexpr void fill(const T& u);
346
  ```
347
 
@@ -389,24 +233,24 @@ specification.
389
  ``` cpp
390
  template<class T, size_t N>
391
  constexpr array<remove_cv_t<T>, N> to_array(T (&a)[N]);
392
  ```
393
 
394
- *Mandates:* `is_array_v<T>` is `false` and `is_constructible_v<T, T&>`
395
- is `true`.
396
 
397
  *Preconditions:* `T` meets the *Cpp17CopyConstructible* requirements.
398
 
399
  *Returns:* `{{ a[0], `…`, a[N - 1] }}`.
400
 
401
  ``` cpp
402
  template<class T, size_t N>
403
  constexpr array<remove_cv_t<T>, N> to_array(T (&&a)[N]);
404
  ```
405
 
406
- *Mandates:* `is_array_v<T>` is `false` and `is_move_constructible_v<T>`
407
- is `true`.
408
 
409
  *Preconditions:* `T` meets the *Cpp17MoveConstructible* requirements.
410
 
411
  *Returns:* `{{ std::move(a[0]), `…`, std::move(a[N - 1]) }}`.
412
 
@@ -440,10 +284,45 @@ template<size_t I, class T, size_t N>
440
  *Mandates:* `I < N` is `true`.
441
 
442
  *Returns:* A reference to the `I`ᵗʰ element of `a`, where indexing is
443
  zero-based.
444
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
445
  ### Class template `deque` <a id="deque">[[deque]]</a>
446
 
447
  #### Overview <a id="deque.overview">[[deque.overview]]</a>
448
 
449
  A `deque` is a sequence container that supports random access iterators
@@ -460,121 +339,125 @@ A `deque` meets all of the requirements of a container
460
  optional sequence container requirements [[sequence.reqmts]].
461
  Descriptions are provided here only for operations on `deque` that are
462
  not described in one of these tables or for operations where there is
463
  additional semantic information.
464
 
 
 
 
465
  ``` cpp
466
  namespace std {
467
  template<class T, class Allocator = allocator<T>>
468
  class deque {
469
  public:
470
  // types
471
  using value_type = T;
472
  using allocator_type = Allocator;
473
- using pointer = typename allocator_traits<Allocator>::pointer;
474
- using const_pointer = typename allocator_traits<Allocator>::const_pointer;
475
  using reference = value_type&;
476
  using const_reference = const value_type&;
477
  using size_type = implementation-defined // type of deque::size_type; // see [container.requirements]
478
  using difference_type = implementation-defined // type of deque::difference_type; // see [container.requirements]
479
  using iterator = implementation-defined // type of deque::iterator; // see [container.requirements]
480
  using const_iterator = implementation-defined // type of deque::const_iterator; // see [container.requirements]
481
  using reverse_iterator = std::reverse_iterator<iterator>;
482
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
483
 
484
  // [deque.cons], construct/copy/destroy
485
- deque() : deque(Allocator()) { }
486
- explicit deque(const Allocator&);
487
- explicit deque(size_type n, const Allocator& = Allocator());
488
- deque(size_type n, const T& value, const Allocator& = Allocator());
489
  template<class InputIterator>
490
- deque(InputIterator first, InputIterator last, const Allocator& = Allocator());
491
  template<container-compatible-range<T> R>
492
- deque(from_range_t, R&& rg, const Allocator& = Allocator());
493
- deque(const deque& x);
494
- deque(deque&&);
495
- deque(const deque&, const type_identity_t<Allocator>&);
496
- deque(deque&&, const type_identity_t<Allocator>&);
497
- deque(initializer_list<T>, const Allocator& = Allocator());
498
 
499
- ~deque();
500
- deque& operator=(const deque& x);
501
- deque& operator=(deque&& x)
502
  noexcept(allocator_traits<Allocator>::is_always_equal::value);
503
- deque& operator=(initializer_list<T>);
504
  template<class InputIterator>
505
- void assign(InputIterator first, InputIterator last);
506
  template<container-compatible-range<T> R>
507
- void assign_range(R&& rg);
508
- void assign(size_type n, const T& t);
509
- void assign(initializer_list<T>);
510
- allocator_type get_allocator() const noexcept;
511
 
512
  // iterators
513
- iterator begin() noexcept;
514
- const_iterator begin() const noexcept;
515
- iterator end() noexcept;
516
- const_iterator end() const noexcept;
517
- reverse_iterator rbegin() noexcept;
518
- const_reverse_iterator rbegin() const noexcept;
519
- reverse_iterator rend() noexcept;
520
- const_reverse_iterator rend() const noexcept;
521
 
522
- const_iterator cbegin() const noexcept;
523
- const_iterator cend() const noexcept;
524
- const_reverse_iterator crbegin() const noexcept;
525
- const_reverse_iterator crend() const noexcept;
526
 
527
  // [deque.capacity], capacity
528
- [[nodiscard]] bool empty() const noexcept;
529
- size_type size() const noexcept;
530
- size_type max_size() const noexcept;
531
- void resize(size_type sz);
532
- void resize(size_type sz, const T& c);
533
- void shrink_to_fit();
534
 
535
  // element access
536
- reference operator[](size_type n);
537
- const_reference operator[](size_type n) const;
538
- reference at(size_type n);
539
- const_reference at(size_type n) const;
540
- reference front();
541
- const_reference front() const;
542
- reference back();
543
- const_reference back() const;
544
 
545
  // [deque.modifiers], modifiers
546
- template<class... Args> reference emplace_front(Args&&... args);
547
- template<class... Args> reference emplace_back(Args&&... args);
548
- template<class... Args> iterator emplace(const_iterator position, Args&&... args);
549
 
550
- void push_front(const T& x);
551
- void push_front(T&& x);
552
  template<container-compatible-range<T> R>
553
- void prepend_range(R&& rg);
554
- void push_back(const T& x);
555
- void push_back(T&& x);
556
  template<container-compatible-range<T> R>
557
- void append_range(R&& rg);
558
 
559
- iterator insert(const_iterator position, const T& x);
560
- iterator insert(const_iterator position, T&& x);
561
- iterator insert(const_iterator position, size_type n, const T& x);
562
  template<class InputIterator>
563
- iterator insert(const_iterator position, InputIterator first, InputIterator last);
 
564
  template<container-compatible-range<T> R>
565
- iterator insert_range(const_iterator position, R&& rg);
566
- iterator insert(const_iterator position, initializer_list<T>);
567
 
568
- void pop_front();
569
- void pop_back();
570
 
571
- iterator erase(const_iterator position);
572
- iterator erase(const_iterator first, const_iterator last);
573
- void swap(deque&)
574
  noexcept(allocator_traits<Allocator>::is_always_equal::value);
575
- void clear() noexcept;
576
  };
577
 
578
  template<class InputIterator, class Allocator = allocator<iter-value-type<InputIterator>>>
579
  deque(InputIterator, InputIterator, Allocator = Allocator())
580
  -> deque<iter-value-type<InputIterator>, Allocator>;
@@ -586,87 +469,87 @@ namespace std {
586
  ```
587
 
588
  #### Constructors, copy, and assignment <a id="deque.cons">[[deque.cons]]</a>
589
 
590
  ``` cpp
591
- explicit deque(const Allocator&);
592
  ```
593
 
594
  *Effects:* Constructs an empty `deque`, using the specified allocator.
595
 
596
  *Complexity:* Constant.
597
 
598
  ``` cpp
599
- explicit deque(size_type n, const Allocator& = Allocator());
600
  ```
601
 
602
- *Preconditions:* `T` is *Cpp17DefaultInsertable* into `*this`.
603
 
604
  *Effects:* Constructs a `deque` with `n` default-inserted elements using
605
  the specified allocator.
606
 
607
  *Complexity:* Linear in `n`.
608
 
609
  ``` cpp
610
- deque(size_type n, const T& value, const Allocator& = Allocator());
611
  ```
612
 
613
- *Preconditions:* `T` is *Cpp17CopyInsertable* into `*this`.
614
 
615
  *Effects:* Constructs a `deque` with `n` copies of `value`, using the
616
  specified allocator.
617
 
618
  *Complexity:* Linear in `n`.
619
 
620
  ``` cpp
621
  template<class InputIterator>
622
- deque(InputIterator first, InputIterator last, const Allocator& = Allocator());
623
  ```
624
 
625
  *Effects:* Constructs a `deque` equal to the range \[`first`, `last`),
626
  using the specified allocator.
627
 
628
  *Complexity:* Linear in `distance(first, last)`.
629
 
630
  ``` cpp
631
  template<container-compatible-range<T> R>
632
- deque(from_range_t, R&& rg, const Allocator& = Allocator());
633
  ```
634
 
635
  *Effects:* Constructs a `deque` with the elements of the range `rg`,
636
  using the specified allocator.
637
 
638
  *Complexity:* Linear in `ranges::distance(rg)`.
639
 
640
  #### Capacity <a id="deque.capacity">[[deque.capacity]]</a>
641
 
642
  ``` cpp
643
- void resize(size_type sz);
644
  ```
645
 
646
  *Preconditions:* `T` is *Cpp17MoveInsertable* and
647
- *Cpp17DefaultInsertable* into `*this`.
648
 
649
  *Effects:* If `sz < size()`, erases the last `size() - sz` elements from
650
  the sequence. Otherwise, appends `sz - size()` default-inserted elements
651
  to the sequence.
652
 
653
  ``` cpp
654
- void resize(size_type sz, const T& c);
655
  ```
656
 
657
- *Preconditions:* `T` is *Cpp17CopyInsertable* into `*this`.
658
 
659
  *Effects:* If `sz < size()`, erases the last `size() - sz` elements from
660
  the sequence. Otherwise, appends `sz - size()` copies of `c` to the
661
  sequence.
662
 
663
  ``` cpp
664
- void shrink_to_fit();
665
  ```
666
 
667
- *Preconditions:* `T` is *Cpp17MoveInsertable* into `*this`.
668
 
669
  *Effects:* `shrink_to_fit` is a non-binding request to reduce memory use
670
  but does not change the size of the sequence.
671
 
672
  [*Note 1*: The request is non-binding to allow latitude for
@@ -684,31 +567,31 @@ invalidates all the references, pointers, and iterators referring to the
684
  elements in the sequence, as well as the past-the-end iterator.
685
 
686
  #### Modifiers <a id="deque.modifiers">[[deque.modifiers]]</a>
687
 
688
  ``` cpp
689
- iterator insert(const_iterator position, const T& x);
690
- iterator insert(const_iterator position, T&& x);
691
- iterator insert(const_iterator position, size_type n, const T& x);
692
  template<class InputIterator>
693
- iterator insert(const_iterator position,
694
  InputIterator first, InputIterator last);
695
  template<container-compatible-range<T> R>
696
- iterator insert_range(const_iterator position, R&& rg);
697
- iterator insert(const_iterator position, initializer_list<T>);
698
 
699
- template<class... Args> reference emplace_front(Args&&... args);
700
- template<class... Args> reference emplace_back(Args&&... args);
701
- template<class... Args> iterator emplace(const_iterator position, Args&&... args);
702
- void push_front(const T& x);
703
- void push_front(T&& x);
704
  template<container-compatible-range<T> R>
705
- void prepend_range(R&& rg);
706
- void push_back(const T& x);
707
- void push_back(T&& x);
708
  template<container-compatible-range<T> R>
709
- void append_range(R&& rg);
710
  ```
711
 
712
  *Effects:* An insertion in the middle of the deque invalidates all the
713
  iterators and references to elements of the deque. An insertion at
714
  either end of the deque invalidates all the iterators to the deque, but
@@ -720,20 +603,20 @@ the deque. Inserting a single element at either the beginning or end of
720
  a deque always takes constant time and causes a single call to a
721
  constructor of `T`.
722
 
723
  *Remarks:* If an exception is thrown other than by the copy constructor,
724
  move constructor, assignment operator, or move assignment operator of
725
- `T` there are no effects. If an exception is thrown while inserting a
726
  single element at either end, there are no effects. Otherwise, if an
727
  exception is thrown by the move constructor of a
728
  non-*Cpp17CopyInsertable* `T`, the effects are unspecified.
729
 
730
  ``` cpp
731
- iterator erase(const_iterator position);
732
- iterator erase(const_iterator first, const_iterator last);
733
- void pop_front();
734
- void pop_back();
735
  ```
736
 
737
  *Effects:* An erase operation that erases the last element of a deque
738
  invalidates only the past-the-end iterator and all iterators and
739
  references to the erased elements. An erase operation that erases the
@@ -756,12 +639,12 @@ elements before the erased elements and the number of elements after the
756
  erased elements.
757
 
758
  #### Erasure <a id="deque.erasure">[[deque.erasure]]</a>
759
 
760
  ``` cpp
761
- template<class T, class Allocator, class U>
762
- typename deque<T, Allocator>::size_type
763
  erase(deque<T, Allocator>& c, const U& value);
764
  ```
765
 
766
  *Effects:* Equivalent to:
767
 
@@ -772,11 +655,11 @@ c.erase(it, c.end());
772
  return r;
773
  ```
774
 
775
  ``` cpp
776
  template<class T, class Allocator, class Predicate>
777
- typename deque<T, Allocator>::size_type
778
  erase_if(deque<T, Allocator>& c, Predicate pred);
779
  ```
780
 
781
  *Effects:* Equivalent to:
782
 
@@ -785,10 +668,47 @@ auto it = remove_if(c.begin(), c.end(), pred);
785
  auto r = distance(it, c.end());
786
  c.erase(it, c.end());
787
  return r;
788
  ```
789
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
790
  ### Class template `forward_list` <a id="forward.list">[[forward.list]]</a>
791
 
792
  #### Overview <a id="forward.list.overview">[[forward.list.overview]]</a>
793
 
794
  A `forward_list` is a container that supports forward iterators and
@@ -800,11 +720,11 @@ access to list elements is not supported.
800
  overhead relative to a hand-written C-style singly linked list. Features
801
  that would conflict with that goal have been omitted. — *end note*]
802
 
803
  A `forward_list` meets all of the requirements of a container
804
  [[container.reqmts]], except that the `size()` member function is not
805
- provided and `operator==` has linear complexity, A `forward_list` also
806
  meets all of the requirements for an allocator-aware container
807
  [[container.alloc.reqmts]]. In addition, a `forward_list` provides the
808
  `assign` member functions and several of the optional sequence container
809
  requirements [[sequence.reqmts]]. Descriptions are provided here only
810
  for operations on `forward_list` that are not described in that table or
@@ -814,127 +734,133 @@ for operations where there is additional semantic information.
814
  the first element of interest, but in a `forward_list` there is no
815
  constant-time way to access a preceding element. For this reason,
816
  `erase_after` and `splice_after` take fully-open ranges, not semi-open
817
  ranges. — *end note*]
818
 
 
 
 
819
  ``` cpp
820
  namespace std {
821
  template<class T, class Allocator = allocator<T>>
822
  class forward_list {
823
  public:
824
  // types
825
  using value_type = T;
826
  using allocator_type = Allocator;
827
- using pointer = typename allocator_traits<Allocator>::pointer;
828
- using const_pointer = typename allocator_traits<Allocator>::const_pointer;
829
  using reference = value_type&;
830
  using const_reference = const value_type&;
831
  using size_type = implementation-defined // type of forward_list::size_type; // see [container.requirements]
832
  using difference_type = implementation-defined // type of forward_list::difference_type; // see [container.requirements]
833
  using iterator = implementation-defined // type of forward_list::iterator; // see [container.requirements]
834
  using const_iterator = implementation-defined // type of forward_list::const_iterator; // see [container.requirements]
835
 
836
  // [forward.list.cons], construct/copy/destroy
837
- forward_list() : forward_list(Allocator()) { }
838
- explicit forward_list(const Allocator&);
839
- explicit forward_list(size_type n, const Allocator& = Allocator());
840
- forward_list(size_type n, const T& value, const Allocator& = Allocator());
841
  template<class InputIterator>
842
- forward_list(InputIterator first, InputIterator last, const Allocator& = Allocator());
 
843
  template<container-compatible-range<T> R>
844
- forward_list(from_range_t, R&& rg, const Allocator& = Allocator());
845
- forward_list(const forward_list& x);
846
- forward_list(forward_list&& x);
847
- forward_list(const forward_list& x, const type_identity_t<Allocator>&);
848
- forward_list(forward_list&& x, const type_identity_t<Allocator>&);
849
- forward_list(initializer_list<T>, const Allocator& = Allocator());
850
- ~forward_list();
851
- forward_list& operator=(const forward_list& x);
852
- forward_list& operator=(forward_list&& x)
853
  noexcept(allocator_traits<Allocator>::is_always_equal::value);
854
- forward_list& operator=(initializer_list<T>);
855
  template<class InputIterator>
856
- void assign(InputIterator first, InputIterator last);
857
  template<container-compatible-range<T> R>
858
- void assign_range(R&& rg);
859
- void assign(size_type n, const T& t);
860
- void assign(initializer_list<T>);
861
- allocator_type get_allocator() const noexcept;
862
 
863
  // [forward.list.iter], iterators
864
- iterator before_begin() noexcept;
865
- const_iterator before_begin() const noexcept;
866
- iterator begin() noexcept;
867
- const_iterator begin() const noexcept;
868
- iterator end() noexcept;
869
- const_iterator end() const noexcept;
870
 
871
- const_iterator cbegin() const noexcept;
872
- const_iterator cbefore_begin() const noexcept;
873
- const_iterator cend() const noexcept;
874
 
875
  // capacity
876
- [[nodiscard]] bool empty() const noexcept;
877
- size_type max_size() const noexcept;
878
 
879
  // [forward.list.access], element access
880
- reference front();
881
- const_reference front() const;
882
 
883
  // [forward.list.modifiers], modifiers
884
- template<class... Args> reference emplace_front(Args&&... args);
885
- void push_front(const T& x);
886
- void push_front(T&& x);
887
  template<container-compatible-range<T> R>
888
- void prepend_range(R&& rg);
889
- void pop_front();
890
 
891
- template<class... Args> iterator emplace_after(const_iterator position, Args&&... args);
892
- iterator insert_after(const_iterator position, const T& x);
893
- iterator insert_after(const_iterator position, T&& x);
 
894
 
895
- iterator insert_after(const_iterator position, size_type n, const T& x);
896
  template<class InputIterator>
897
- iterator insert_after(const_iterator position, InputIterator first, InputIterator last);
898
- iterator insert_after(const_iterator position, initializer_list<T> il);
 
899
  template<container-compatible-range<T> R>
900
- iterator insert_range_after(const_iterator position, R&& rg);
901
 
902
- iterator erase_after(const_iterator position);
903
- iterator erase_after(const_iterator position, const_iterator last);
904
- void swap(forward_list&)
905
  noexcept(allocator_traits<Allocator>::is_always_equal::value);
906
 
907
- void resize(size_type sz);
908
- void resize(size_type sz, const value_type& c);
909
- void clear() noexcept;
910
 
911
  // [forward.list.ops], forward_list operations
912
- void splice_after(const_iterator position, forward_list& x);
913
- void splice_after(const_iterator position, forward_list&& x);
914
- void splice_after(const_iterator position, forward_list& x, const_iterator i);
915
- void splice_after(const_iterator position, forward_list&& x, const_iterator i);
916
- void splice_after(const_iterator position, forward_list& x,
917
  const_iterator first, const_iterator last);
918
- void splice_after(const_iterator position, forward_list&& x,
919
  const_iterator first, const_iterator last);
920
 
921
- size_type remove(const T& value);
922
- template<class Predicate> size_type remove_if(Predicate pred);
923
 
924
  size_type unique();
925
- template<class BinaryPredicate> size_type unique(BinaryPredicate binary_pred);
926
 
927
- void merge(forward_list& x);
928
- void merge(forward_list&& x);
929
- template<class Compare> void merge(forward_list& x, Compare comp);
930
- template<class Compare> void merge(forward_list&& x, Compare comp);
931
 
932
- void sort();
933
- template<class Compare> void sort(Compare comp);
934
 
935
- void reverse() noexcept;
936
  };
937
 
938
  template<class InputIterator, class Allocator = allocator<iter-value-type<InputIterator>>>
939
  forward_list(InputIterator, InputIterator, Allocator = Allocator())
940
  -> forward_list<iter-value-type<InputIterator>, Allocator>;
@@ -952,66 +878,66 @@ any member of the resulting specialization of `forward_list` is
952
  referenced.
953
 
954
  #### Constructors, copy, and assignment <a id="forward.list.cons">[[forward.list.cons]]</a>
955
 
956
  ``` cpp
957
- explicit forward_list(const Allocator&);
958
  ```
959
 
960
  *Effects:* Constructs an empty `forward_list` object using the specified
961
  allocator.
962
 
963
  *Complexity:* Constant.
964
 
965
  ``` cpp
966
- explicit forward_list(size_type n, const Allocator& = Allocator());
967
  ```
968
 
969
- *Preconditions:* `T` is *Cpp17DefaultInsertable* into `*this`.
970
 
971
  *Effects:* Constructs a `forward_list` object with `n` default-inserted
972
  elements using the specified allocator.
973
 
974
  *Complexity:* Linear in `n`.
975
 
976
  ``` cpp
977
- forward_list(size_type n, const T& value, const Allocator& = Allocator());
978
  ```
979
 
980
- *Preconditions:* `T` is *Cpp17CopyInsertable* into `*this`.
981
 
982
  *Effects:* Constructs a `forward_list` object with `n` copies of `value`
983
  using the specified allocator.
984
 
985
  *Complexity:* Linear in `n`.
986
 
987
  ``` cpp
988
  template<class InputIterator>
989
- forward_list(InputIterator first, InputIterator last, const Allocator& = Allocator());
990
  ```
991
 
992
  *Effects:* Constructs a `forward_list` object equal to the range
993
  \[`first`, `last`).
994
 
995
  *Complexity:* Linear in `distance(first, last)`.
996
 
997
  ``` cpp
998
  template<container-compatible-range<T> R>
999
- forward_list(from_range_t, R&& rg, const Allocator& = Allocator());
1000
  ```
1001
 
1002
  *Effects:* Constructs a `forward_list` object with the elements of the
1003
  range `rg`.
1004
 
1005
  *Complexity:* Linear in `ranges::distance(rg)`.
1006
 
1007
  #### Iterators <a id="forward.list.iter">[[forward.list.iter]]</a>
1008
 
1009
  ``` cpp
1010
- iterator before_begin() noexcept;
1011
- const_iterator before_begin() const noexcept;
1012
- const_iterator cbefore_begin() const noexcept;
1013
  ```
1014
 
1015
  *Effects:* `cbefore_begin()` is equivalent to
1016
  `const_cast<forward_list const&>(*this).before_begin()`.
1017
 
@@ -1021,59 +947,60 @@ equal to the iterator returned by `begin()`.
1021
  *Remarks:* `before_begin() == end()` shall equal `false`.
1022
 
1023
  #### Element access <a id="forward.list.access">[[forward.list.access]]</a>
1024
 
1025
  ``` cpp
1026
- reference front();
1027
- const_reference front() const;
1028
  ```
1029
 
1030
  *Returns:* `*begin()`
1031
 
1032
  #### Modifiers <a id="forward.list.modifiers">[[forward.list.modifiers]]</a>
1033
 
1034
- None of the overloads of `insert_after` shall affect the validity of
1035
- iterators and references, and `erase_after` shall invalidate only
1036
- iterators and references to the erased elements. If an exception is
1037
- thrown during `insert_after` there shall be no effect. Inserting `n`
1038
- elements into a `forward_list` is linear in `n`, and the number of calls
1039
- to the copy or move constructor of `T` is exactly equal to `n`. Erasing
1040
- `n` elements from a `forward_list` is linear in `n` and the number of
1041
- calls to the destructor of type `T` is exactly equal to `n`.
 
1042
 
1043
  ``` cpp
1044
- template<class... Args> reference emplace_front(Args&&... args);
1045
  ```
1046
 
1047
  *Effects:* Inserts an object of type `value_type` constructed with
1048
  `value_type(std::forward<Args>(args)...)` at the beginning of the list.
1049
 
1050
  ``` cpp
1051
- void push_front(const T& x);
1052
- void push_front(T&& x);
1053
  ```
1054
 
1055
  *Effects:* Inserts a copy of `x` at the beginning of the list.
1056
 
1057
  ``` cpp
1058
  template<container-compatible-range<T> R>
1059
- void prepend_range(R&& rg);
1060
  ```
1061
 
1062
  *Effects:* Inserts a copy of each element of `rg` at the beginning of
1063
  the list.
1064
 
1065
  [*Note 1*: The order of elements is not reversed. — *end note*]
1066
 
1067
  ``` cpp
1068
- void pop_front();
1069
  ```
1070
 
1071
  *Effects:* As if by `erase_after(before_begin())`.
1072
 
1073
  ``` cpp
1074
- iterator insert_after(const_iterator position, const T& x);
1075
  ```
1076
 
1077
  *Preconditions:* `T` is *Cpp17CopyInsertable* into `forward_list`.
1078
  `position` is `before_begin()` or is a dereferenceable iterator in the
1079
  range \[`begin()`, `end()`).
@@ -1081,11 +1008,11 @@ range \[`begin()`, `end()`).
1081
  *Effects:* Inserts a copy of `x` after `position`.
1082
 
1083
  *Returns:* An iterator pointing to the copy of `x`.
1084
 
1085
  ``` cpp
1086
- iterator insert_after(const_iterator position, T&& x);
1087
  ```
1088
 
1089
  *Preconditions:* `T` is *Cpp17MoveInsertable* into `forward_list`.
1090
  `position` is `before_begin()` or is a dereferenceable iterator in the
1091
  range \[`begin()`, `end()`).
@@ -1093,11 +1020,11 @@ range \[`begin()`, `end()`).
1093
  *Effects:* Inserts a copy of `x` after `position`.
1094
 
1095
  *Returns:* An iterator pointing to the copy of `x`.
1096
 
1097
  ``` cpp
1098
- iterator insert_after(const_iterator position, size_type n, const T& x);
1099
  ```
1100
 
1101
  *Preconditions:* `T` is *Cpp17CopyInsertable* into `forward_list`.
1102
  `position` is `before_begin()` or is a dereferenceable iterator in the
1103
  range \[`begin()`, `end()`).
@@ -1107,11 +1034,12 @@ range \[`begin()`, `end()`).
1107
  *Returns:* An iterator pointing to the last inserted copy of `x`, or
1108
  `position` if `n == 0` is `true`.
1109
 
1110
  ``` cpp
1111
  template<class InputIterator>
1112
- iterator insert_after(const_iterator position, InputIterator first, InputIterator last);
 
1113
  ```
1114
 
1115
  *Preconditions:* `T` is *Cpp17EmplaceConstructible* into `forward_list`
1116
  from `*first`. `position` is `before_begin()` or is a dereferenceable
1117
  iterator in the range \[`begin()`, `end()`). Neither `first` nor `last`
@@ -1123,11 +1051,11 @@ are iterators in `*this`.
1123
  *Returns:* An iterator pointing to the last inserted element, or
1124
  `position` if `first == last` is `true`.
1125
 
1126
  ``` cpp
1127
  template<container-compatible-range<T> R>
1128
- iterator insert_range_after(const_iterator position, R&& rg);
1129
  ```
1130
 
1131
  *Preconditions:* `T` is *Cpp17EmplaceConstructible* into `forward_list`
1132
  from `*ranges::begin(rg)`. `position` is `before_begin()` or is a
1133
  dereferenceable iterator in the range \[`begin()`, `end()`). `rg` and
@@ -1138,19 +1066,19 @@ dereferenceable iterator in the range \[`begin()`, `end()`). `rg` and
1138
 
1139
  *Returns:* An iterator pointing to the last inserted element, or
1140
  `position` if `rg` is empty.
1141
 
1142
  ``` cpp
1143
- iterator insert_after(const_iterator position, initializer_list<T> il);
1144
  ```
1145
 
1146
  *Effects:* Equivalent to:
1147
  `return insert_after(position, il.begin(), il.end());`
1148
 
1149
  ``` cpp
1150
  template<class... Args>
1151
- iterator emplace_after(const_iterator position, Args&&... args);
1152
  ```
1153
 
1154
  *Preconditions:* `T` is *Cpp17EmplaceConstructible* into `forward_list`
1155
  from `std::forward<Args>(args)...`. `position` is `before_begin()` or is
1156
  a dereferenceable iterator in the range \[`begin()`, `end()`).
@@ -1160,11 +1088,11 @@ direct-non-list-initialized with `std::forward<Args>(args)...` after
1160
  `position`.
1161
 
1162
  *Returns:* An iterator pointing to the new object.
1163
 
1164
  ``` cpp
1165
- iterator erase_after(const_iterator position);
1166
  ```
1167
 
1168
  *Preconditions:* The iterator following `position` is dereferenceable.
1169
 
1170
  *Effects:* Erases the element pointed to by the iterator following
@@ -1174,11 +1102,11 @@ iterator erase_after(const_iterator position);
1174
  was erased, or `end()` if no such element exists.
1175
 
1176
  *Throws:* Nothing.
1177
 
1178
  ``` cpp
1179
- iterator erase_after(const_iterator position, const_iterator last);
1180
  ```
1181
 
1182
  *Preconditions:* All iterators in the range (`position`, `last`) are
1183
  dereferenceable.
1184
 
@@ -1187,33 +1115,33 @@ dereferenceable.
1187
  *Returns:* `last`.
1188
 
1189
  *Throws:* Nothing.
1190
 
1191
  ``` cpp
1192
- void resize(size_type sz);
1193
  ```
1194
 
1195
- *Preconditions:* `T` is *Cpp17DefaultInsertable* into `*this`.
1196
 
1197
  *Effects:* If `sz < distance(begin(), end())`, erases the last
1198
  `distance(begin(), end()) - sz` elements from the list. Otherwise,
1199
  inserts `sz - distance(begin(), end())` default-inserted elements at the
1200
  end of the list.
1201
 
1202
  ``` cpp
1203
- void resize(size_type sz, const value_type& c);
1204
  ```
1205
 
1206
- *Preconditions:* `T` is *Cpp17CopyInsertable* into `*this`.
1207
 
1208
  *Effects:* If `sz < distance(begin(), end())`, erases the last
1209
  `distance(begin(), end()) - sz` elements from the list. Otherwise,
1210
  inserts `sz - distance(begin(), end())` copies of `c` at the end of the
1211
  list.
1212
 
1213
  ``` cpp
1214
- void clear() noexcept;
1215
  ```
1216
 
1217
  *Effects:* Erases all elements in the range \[`begin()`, `end()`).
1218
 
1219
  *Remarks:* Does not invalidate past-the-end iterators.
@@ -1228,12 +1156,12 @@ iterator into the list and `n` is an integer, are the same as those of
1228
  list and `n` is an integer, means an iterator `j` such that `j + n == i`
1229
  is `true`. For `merge` and `sort`, the definitions and requirements in
1230
  [[alg.sorting]] apply.
1231
 
1232
  ``` cpp
1233
- void splice_after(const_iterator position, forward_list& x);
1234
- void splice_after(const_iterator position, forward_list&& x);
1235
  ```
1236
 
1237
  *Preconditions:* `position` is `before_begin()` or is a dereferenceable
1238
  iterator in the range \[`begin()`, `end()`).
1239
  `get_allocator() == x.get_allocator()` is `true`. `addressof(x) != this`
@@ -1248,12 +1176,12 @@ now behave as iterators into `*this`, not into `x`.
1248
  *Throws:* Nothing.
1249
 
1250
  *Complexity:* 𝑂(`distance(x.begin(), x.end())`)
1251
 
1252
  ``` cpp
1253
- void splice_after(const_iterator position, forward_list& x, const_iterator i);
1254
- void splice_after(const_iterator position, forward_list&& x, const_iterator i);
1255
  ```
1256
 
1257
  *Preconditions:* `position` is `before_begin()` or is a dereferenceable
1258
  iterator in the range \[`begin()`, `end()`). The iterator following `i`
1259
  is a dereferenceable iterator in `x`.
@@ -1269,13 +1197,13 @@ behave as iterators into `*this`, not into `x`.
1269
  *Throws:* Nothing.
1270
 
1271
  *Complexity:* 𝑂(1)
1272
 
1273
  ``` cpp
1274
- void splice_after(const_iterator position, forward_list& x,
1275
  const_iterator first, const_iterator last);
1276
- void splice_after(const_iterator position, forward_list&& x,
1277
  const_iterator first, const_iterator last);
1278
  ```
1279
 
1280
  *Preconditions:* `position` is `before_begin()` or is a dereferenceable
1281
  iterator in the range \[`begin()`, `end()`). (`first`, `last`) is a
@@ -1291,12 +1219,12 @@ continue to refer to their elements, but they now behave as iterators
1291
  into `*this`, not into `x`.
1292
 
1293
  *Complexity:* 𝑂(`distance(first, last)`)
1294
 
1295
  ``` cpp
1296
- size_type remove(const T& value);
1297
- template<class Predicate> size_type remove_if(Predicate pred);
1298
  ```
1299
 
1300
  *Effects:* Erases all the elements in the list referred to by a list
1301
  iterator `i` for which the following conditions hold: `*i == value` (for
1302
  `remove()`), `pred(*i)` is `true` (for `remove_if()`). Invalidates only
@@ -1311,12 +1239,12 @@ comparison or the predicate.
1311
  corresponding predicate.
1312
 
1313
  *Remarks:* Stable [[algorithm.stable]].
1314
 
1315
  ``` cpp
1316
- size_type unique();
1317
- template<class BinaryPredicate> size_type unique(BinaryPredicate binary_pred);
1318
  ```
1319
 
1320
  Let `binary_pred` be `equal_to<>{}` for the first overload.
1321
 
1322
  *Preconditions:* `binary_pred` is an equivalence relation.
@@ -1334,14 +1262,14 @@ only the iterators and references to the erased elements.
1334
  *Complexity:* If `empty()` is `false`, exactly
1335
  `distance(begin(), end()) - 1` applications of the corresponding
1336
  predicate, otherwise no applications of the predicate.
1337
 
1338
  ``` cpp
1339
- void merge(forward_list& x);
1340
- void merge(forward_list&& x);
1341
- template<class Compare> void merge(forward_list& x, Compare comp);
1342
- template<class Compare> void merge(forward_list&& x, Compare comp);
1343
  ```
1344
 
1345
  Let `comp` be `less<>` for the first two overloads.
1346
 
1347
  *Preconditions:* `*this` and `x` are both sorted with respect to the
@@ -1363,12 +1291,12 @@ performed.
1363
  *Remarks:* Stable [[algorithm.stable]]. If `addressof(x) != this`, `x`
1364
  is empty after the merge. No elements are copied by this operation. If
1365
  an exception is thrown other than by a comparison, there are no effects.
1366
 
1367
  ``` cpp
1368
- void sort();
1369
- template<class Compare> void sort(Compare comp);
1370
  ```
1371
 
1372
  *Effects:* Sorts the list according to the `operator<` or the `comp`
1373
  function object. If an exception is thrown, the order of the elements in
1374
  `*this` is unspecified. Does not affect the validity of iterators and
@@ -1378,37 +1306,847 @@ references.
1378
  `distance(begin(), end())`.
1379
 
1380
  *Remarks:* Stable [[algorithm.stable]].
1381
 
1382
  ``` cpp
1383
- void reverse() noexcept;
1384
  ```
1385
 
1386
  *Effects:* Reverses the order of the elements in the list. Does not
1387
  affect the validity of iterators and references.
1388
 
1389
  *Complexity:* Linear time.
1390
 
1391
  #### Erasure <a id="forward.list.erasure">[[forward.list.erasure]]</a>
1392
 
1393
  ``` cpp
1394
- template<class T, class Allocator, class U>
1395
- typename forward_list<T, Allocator>::size_type
1396
  erase(forward_list<T, Allocator>& c, const U& value);
1397
  ```
1398
 
1399
  *Effects:* Equivalent to:
1400
- `return erase_if(c, [&](auto& elem) { return elem == value; });`
 
 
 
1401
 
1402
  ``` cpp
1403
  template<class T, class Allocator, class Predicate>
1404
- typename forward_list<T, Allocator>::size_type
1405
  erase_if(forward_list<T, Allocator>& c, Predicate pred);
1406
  ```
1407
 
1408
  *Effects:* Equivalent to: `return c.remove_if(pred);`
1409
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1410
  ### Class template `list` <a id="list">[[list]]</a>
1411
 
1412
  #### Overview <a id="list.overview">[[list.overview]]</a>
1413
 
1414
  A `list` is a sequence container that supports bidirectional iterators
@@ -1427,137 +2165,143 @@ provided.[^2]
1427
 
1428
  Descriptions are provided here only for operations on `list` that are
1429
  not described in one of these tables or for operations where there is
1430
  additional semantic information.
1431
 
 
 
 
1432
  ``` cpp
1433
  namespace std {
1434
  template<class T, class Allocator = allocator<T>>
1435
  class list {
1436
  public:
1437
  // types
1438
  using value_type = T;
1439
  using allocator_type = Allocator;
1440
- using pointer = typename allocator_traits<Allocator>::pointer;
1441
- using const_pointer = typename allocator_traits<Allocator>::const_pointer;
1442
  using reference = value_type&;
1443
  using const_reference = const value_type&;
1444
  using size_type = implementation-defined // type of list::size_type; // see [container.requirements]
1445
  using difference_type = implementation-defined // type of list::difference_type; // see [container.requirements]
1446
  using iterator = implementation-defined // type of list::iterator; // see [container.requirements]
1447
  using const_iterator = implementation-defined // type of list::const_iterator; // see [container.requirements]
1448
  using reverse_iterator = std::reverse_iterator<iterator>;
1449
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
1450
 
1451
  // [list.cons], construct/copy/destroy
1452
- list() : list(Allocator()) { }
1453
- explicit list(const Allocator&);
1454
- explicit list(size_type n, const Allocator& = Allocator());
1455
- list(size_type n, const T& value, const Allocator& = Allocator());
1456
  template<class InputIterator>
1457
- list(InputIterator first, InputIterator last, const Allocator& = Allocator());
1458
  template<container-compatible-range<T> R>
1459
- list(from_range_t, R&& rg, const Allocator& = Allocator());
1460
- list(const list& x);
1461
- list(list&& x);
1462
- list(const list&, const type_identity_t<Allocator>&);
1463
- list(list&&, const type_identity_t<Allocator>&);
1464
- list(initializer_list<T>, const Allocator& = Allocator());
1465
- ~list();
1466
- list& operator=(const list& x);
1467
- list& operator=(list&& x)
1468
  noexcept(allocator_traits<Allocator>::is_always_equal::value);
1469
- list& operator=(initializer_list<T>);
1470
  template<class InputIterator>
1471
- void assign(InputIterator first, InputIterator last);
1472
  template<container-compatible-range<T> R>
1473
- void assign_range(R&& rg);
1474
- void assign(size_type n, const T& t);
1475
- void assign(initializer_list<T>);
1476
- allocator_type get_allocator() const noexcept;
1477
 
1478
  // iterators
1479
- iterator begin() noexcept;
1480
- const_iterator begin() const noexcept;
1481
- iterator end() noexcept;
1482
- const_iterator end() const noexcept;
1483
- reverse_iterator rbegin() noexcept;
1484
- const_reverse_iterator rbegin() const noexcept;
1485
- reverse_iterator rend() noexcept;
1486
- const_reverse_iterator rend() const noexcept;
1487
 
1488
- const_iterator cbegin() const noexcept;
1489
- const_iterator cend() const noexcept;
1490
- const_reverse_iterator crbegin() const noexcept;
1491
- const_reverse_iterator crend() const noexcept;
1492
 
1493
  // [list.capacity], capacity
1494
- [[nodiscard]] bool empty() const noexcept;
1495
- size_type size() const noexcept;
1496
- size_type max_size() const noexcept;
1497
- void resize(size_type sz);
1498
- void resize(size_type sz, const T& c);
1499
 
1500
  // element access
1501
- reference front();
1502
- const_reference front() const;
1503
- reference back();
1504
- const_reference back() const;
1505
 
1506
  // [list.modifiers], modifiers
1507
- template<class... Args> reference emplace_front(Args&&... args);
1508
- template<class... Args> reference emplace_back(Args&&... args);
1509
- void push_front(const T& x);
1510
- void push_front(T&& x);
1511
  template<container-compatible-range<T> R>
1512
- void prepend_range(R&& rg);
1513
- void pop_front();
1514
- void push_back(const T& x);
1515
- void push_back(T&& x);
1516
  template<container-compatible-range<T> R>
1517
- void append_range(R&& rg);
1518
- void pop_back();
1519
 
1520
- template<class... Args> iterator emplace(const_iterator position, Args&&... args);
1521
- iterator insert(const_iterator position, const T& x);
1522
- iterator insert(const_iterator position, T&& x);
1523
- iterator insert(const_iterator position, size_type n, const T& x);
1524
  template<class InputIterator>
1525
- iterator insert(const_iterator position, InputIterator first, InputIterator last);
 
1526
  template<container-compatible-range<T> R>
1527
- iterator insert_range(const_iterator position, R&& rg);
1528
- iterator insert(const_iterator position, initializer_list<T> il);
1529
 
1530
- iterator erase(const_iterator position);
1531
- iterator erase(const_iterator position, const_iterator last);
1532
- void swap(list&) noexcept(allocator_traits<Allocator>::is_always_equal::value);
1533
- void clear() noexcept;
1534
 
1535
  // [list.ops], list operations
1536
- void splice(const_iterator position, list& x);
1537
- void splice(const_iterator position, list&& x);
1538
- void splice(const_iterator position, list& x, const_iterator i);
1539
- void splice(const_iterator position, list&& x, const_iterator i);
1540
- void splice(const_iterator position, list& x, const_iterator first, const_iterator last);
1541
- void splice(const_iterator position, list&& x, const_iterator first, const_iterator last);
 
 
1542
 
1543
- size_type remove(const T& value);
1544
- template<class Predicate> size_type remove_if(Predicate pred);
1545
 
1546
- size_type unique();
1547
  template<class BinaryPredicate>
1548
- size_type unique(BinaryPredicate binary_pred);
1549
 
1550
- void merge(list& x);
1551
- void merge(list&& x);
1552
- template<class Compare> void merge(list& x, Compare comp);
1553
- template<class Compare> void merge(list&& x, Compare comp);
1554
 
1555
- void sort();
1556
- template<class Compare> void sort(Compare comp);
1557
 
1558
- void reverse() noexcept;
1559
  };
1560
 
1561
  template<class InputIterator, class Allocator = allocator<iter-value-type<InputIterator>>>
1562
  list(InputIterator, InputIterator, Allocator = Allocator())
1563
  -> list<iter-value-type<InputIterator>, Allocator>;
@@ -1574,65 +2318,65 @@ allocator meets the allocator completeness requirements
1574
  any member of the resulting specialization of `list` is referenced.
1575
 
1576
  #### Constructors, copy, and assignment <a id="list.cons">[[list.cons]]</a>
1577
 
1578
  ``` cpp
1579
- explicit list(const Allocator&);
1580
  ```
1581
 
1582
  *Effects:* Constructs an empty list, using the specified allocator.
1583
 
1584
  *Complexity:* Constant.
1585
 
1586
  ``` cpp
1587
- explicit list(size_type n, const Allocator& = Allocator());
1588
  ```
1589
 
1590
- *Preconditions:* `T` is *Cpp17DefaultInsertable* into `*this`.
1591
 
1592
  *Effects:* Constructs a `list` with `n` default-inserted elements using
1593
  the specified allocator.
1594
 
1595
  *Complexity:* Linear in `n`.
1596
 
1597
  ``` cpp
1598
- list(size_type n, const T& value, const Allocator& = Allocator());
1599
  ```
1600
 
1601
- *Preconditions:* `T` is *Cpp17CopyInsertable* into `*this`.
1602
 
1603
  *Effects:* Constructs a `list` with `n` copies of `value`, using the
1604
  specified allocator.
1605
 
1606
  *Complexity:* Linear in `n`.
1607
 
1608
  ``` cpp
1609
  template<class InputIterator>
1610
- list(InputIterator first, InputIterator last, const Allocator& = Allocator());
1611
  ```
1612
 
1613
  *Effects:* Constructs a `list` equal to the range \[`first`, `last`).
1614
 
1615
  *Complexity:* Linear in `distance(first, last)`.
1616
 
1617
  ``` cpp
1618
  template<container-compatible-range<T> R>
1619
- list(from_range_t, R&& rg, const Allocator& = Allocator());
1620
  ```
1621
 
1622
  *Effects:* Constructs a `list` object with the elements of the range
1623
  `rg`.
1624
 
1625
  *Complexity:* Linear in `ranges::distance(rg)`.
1626
 
1627
  #### Capacity <a id="list.capacity">[[list.capacity]]</a>
1628
 
1629
  ``` cpp
1630
- void resize(size_type sz);
1631
  ```
1632
 
1633
- *Preconditions:* `T` is *Cpp17DefaultInsertable* into `*this`.
1634
 
1635
  *Effects:* If `size() < sz`, appends `sz - size()` default-inserted
1636
  elements to the sequence. If `sz <= size()`, equivalent to:
1637
 
1638
  ``` cpp
@@ -1640,14 +2384,14 @@ list<T>::iterator it = begin();
1640
  advance(it, sz);
1641
  erase(it, end());
1642
  ```
1643
 
1644
  ``` cpp
1645
- void resize(size_type sz, const T& c);
1646
  ```
1647
 
1648
- *Preconditions:* `T` is *Cpp17CopyInsertable* into `*this`.
1649
 
1650
  *Effects:* As if by:
1651
 
1652
  ``` cpp
1653
  if (sz > size())
@@ -1662,49 +2406,48 @@ else
1662
  ```
1663
 
1664
  #### Modifiers <a id="list.modifiers">[[list.modifiers]]</a>
1665
 
1666
  ``` cpp
1667
- iterator insert(const_iterator position, const T& x);
1668
- iterator insert(const_iterator position, T&& x);
1669
- iterator insert(const_iterator position, size_type n, const T& x);
1670
  template<class InputIterator>
1671
- iterator insert(const_iterator position, InputIterator first,
1672
- InputIterator last);
1673
  template<container-compatible-range<T> R>
1674
- iterator insert_range(const_iterator position, R&& rg);
1675
- iterator insert(const_iterator position, initializer_list<T>);
1676
 
1677
- template<class... Args> reference emplace_front(Args&&... args);
1678
- template<class... Args> reference emplace_back(Args&&... args);
1679
- template<class... Args> iterator emplace(const_iterator position, Args&&... args);
1680
- void push_front(const T& x);
1681
- void push_front(T&& x);
1682
  template<container-compatible-range<T> R>
1683
- void prepend_range(R&& rg);
1684
- void push_back(const T& x);
1685
- void push_back(T&& x);
1686
  template<container-compatible-range<T> R>
1687
- void append_range(R&& rg);
1688
  ```
1689
 
1690
  *Complexity:* Insertion of a single element into a list takes constant
1691
  time and exactly one call to a constructor of `T`. Insertion of multiple
1692
  elements into a list is linear in the number of elements inserted, and
1693
  the number of calls to the copy constructor or move constructor of `T`
1694
  is exactly equal to the number of elements inserted.
1695
 
1696
  *Remarks:* Does not affect the validity of iterators and references. If
1697
- an exception is thrown there are no effects.
1698
 
1699
  ``` cpp
1700
- iterator erase(const_iterator position);
1701
- iterator erase(const_iterator first, const_iterator last);
1702
-
1703
- void pop_front();
1704
- void pop_back();
1705
- void clear() noexcept;
1706
  ```
1707
 
1708
  *Effects:* Invalidates only the iterators and references to the erased
1709
  elements.
1710
 
@@ -1731,12 +2474,12 @@ those of `next(i, n)` and `prev(i, n)`, respectively. For `merge` and
1731
  from one list to another. The behavior of splice operations is undefined
1732
  if `get_allocator() !=
1733
  x.get_allocator()`.
1734
 
1735
  ``` cpp
1736
- void splice(const_iterator position, list& x);
1737
- void splice(const_iterator position, list&& x);
1738
  ```
1739
 
1740
  *Preconditions:* `addressof(x) != this` is `true`.
1741
 
1742
  *Effects:* Inserts the contents of `x` before `position` and `x` becomes
@@ -1748,12 +2491,12 @@ now behave as iterators into `*this`, not into `x`.
1748
  *Throws:* Nothing.
1749
 
1750
  *Complexity:* Constant time.
1751
 
1752
  ``` cpp
1753
- void splice(const_iterator position, list& x, const_iterator i);
1754
- void splice(const_iterator position, list&& x, const_iterator i);
1755
  ```
1756
 
1757
  *Preconditions:* `i` is a valid dereferenceable iterator of `x`.
1758
 
1759
  *Effects:* Inserts an element pointed to by `i` from list `x` before
@@ -1766,18 +2509,18 @@ element, but now behave as iterators into `*this`, not into `x`.
1766
  *Throws:* Nothing.
1767
 
1768
  *Complexity:* Constant time.
1769
 
1770
  ``` cpp
1771
- void splice(const_iterator position, list& x, const_iterator first,
1772
- const_iterator last);
1773
- void splice(const_iterator position, list&& x, const_iterator first,
1774
- const_iterator last);
1775
  ```
1776
 
1777
- *Preconditions:* `[first, last)` is a valid range in `x`. `position` is
1778
- not an iterator in the range \[`first`, `last`).
1779
 
1780
  *Effects:* Inserts elements in the range \[`first`, `last`) before
1781
  `position` and removes the elements from `x`. Pointers and references to
1782
  the moved elements of `x` now refer to those same elements but as
1783
  members of `*this`. Iterators referring to the moved elements will
@@ -1788,12 +2531,12 @@ into `*this`, not into `x`.
1788
 
1789
  *Complexity:* Constant time if `addressof(x) == this`; otherwise, linear
1790
  time.
1791
 
1792
  ``` cpp
1793
- size_type remove(const T& value);
1794
- template<class Predicate> size_type remove_if(Predicate pred);
1795
  ```
1796
 
1797
  *Effects:* Erases all the elements in the list referred to by a list
1798
  iterator `i` for which the following conditions hold: `*i == value`,
1799
  `pred(*i) != false`. Invalidates only the iterators and references to
@@ -1808,12 +2551,12 @@ the erased elements.
1808
  predicate.
1809
 
1810
  *Remarks:* Stable [[algorithm.stable]].
1811
 
1812
  ``` cpp
1813
- size_type unique();
1814
- template<class BinaryPredicate> size_type unique(BinaryPredicate binary_pred);
1815
  ```
1816
 
1817
  Let `binary_pred` be `equal_to<>{}` for the first overload.
1818
 
1819
  *Preconditions:* `binary_pred` is an equivalence relation.
@@ -1831,14 +2574,14 @@ only the iterators and references to the erased elements.
1831
  *Complexity:* If `empty()` is `false`, exactly `size() - 1` applications
1832
  of the corresponding predicate, otherwise no applications of the
1833
  predicate.
1834
 
1835
  ``` cpp
1836
- void merge(list& x);
1837
- void merge(list&& x);
1838
- template<class Compare> void merge(list& x, Compare comp);
1839
- template<class Compare> void merge(list&& x, Compare comp);
1840
  ```
1841
 
1842
  Let `comp` be `less<>` for the first two overloads.
1843
 
1844
  *Preconditions:* `*this` and `x` are both sorted with respect to the
@@ -1855,14 +2598,14 @@ elements, but they now behave as iterators into `*this`, not into `x`.
1855
  *Complexity:* At most `size() + x.size() - 1` comparisons if
1856
  `addressof(x) != this`; otherwise, no comparisons are performed.
1857
 
1858
  *Remarks:* Stable [[algorithm.stable]]. If `addressof(x) != this`, `x`
1859
  is empty after the merge. No elements are copied by this operation. If
1860
- an exception is thrown other than by a comparison there are no effects.
1861
 
1862
  ``` cpp
1863
- void reverse() noexcept;
1864
  ```
1865
 
1866
  *Effects:* Reverses the order of the elements in the list. Does not
1867
  affect the validity of iterators and references.
1868
 
@@ -1876,33 +2619,87 @@ template<class Compare> void sort(Compare comp);
1876
  *Effects:* Sorts the list according to the `operator<` or a `Compare`
1877
  function object. If an exception is thrown, the order of the elements in
1878
  `*this` is unspecified. Does not affect the validity of iterators and
1879
  references.
1880
 
1881
- *Complexity:* Approximately N log N comparisons, where `N == size()`.
1882
 
1883
  *Remarks:* Stable [[algorithm.stable]].
1884
 
1885
  #### Erasure <a id="list.erasure">[[list.erasure]]</a>
1886
 
1887
  ``` cpp
1888
- template<class T, class Allocator, class U>
1889
  typename list<T, Allocator>::size_type
1890
- erase(list<T, Allocator>& c, const U& value);
1891
  ```
1892
 
1893
  *Effects:* Equivalent to:
1894
- `return erase_if(c, [&](auto& elem) { return elem == value; });`
 
 
 
1895
 
1896
  ``` cpp
1897
  template<class T, class Allocator, class Predicate>
1898
  typename list<T, Allocator>::size_type
1899
- erase_if(list<T, Allocator>& c, Predicate pred);
1900
  ```
1901
 
1902
  *Effects:* Equivalent to: `return c.remove_if(pred);`
1903
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1904
  ### Class template `vector` <a id="vector">[[vector]]</a>
1905
 
1906
  #### Overview <a id="vector.overview">[[vector.overview]]</a>
1907
 
1908
  A `vector` is a sequence container that supports (amortized) constant
@@ -1931,12 +2728,12 @@ namespace std {
1931
  class vector {
1932
  public:
1933
  // types
1934
  using value_type = T;
1935
  using allocator_type = Allocator;
1936
- using pointer = typename allocator_traits<Allocator>::pointer;
1937
- using const_pointer = typename allocator_traits<Allocator>::const_pointer;
1938
  using reference = value_type&;
1939
  using const_reference = const value_type&;
1940
  using size_type = implementation-defined // type of vector::size_type; // see [container.requirements]
1941
  using difference_type = implementation-defined // type of vector::difference_type; // see [container.requirements]
1942
  using iterator = implementation-defined // type of vector::iterator; // see [container.requirements]
@@ -1986,11 +2783,11 @@ namespace std {
1986
  constexpr const_iterator cend() const noexcept;
1987
  constexpr const_reverse_iterator crbegin() const noexcept;
1988
  constexpr const_reverse_iterator crend() const noexcept;
1989
 
1990
  // [vector.capacity], capacity
1991
- [[nodiscard]] constexpr bool empty() const noexcept;
1992
  constexpr size_type size() const noexcept;
1993
  constexpr size_type max_size() const noexcept;
1994
  constexpr size_type capacity() const noexcept;
1995
  constexpr void resize(size_type sz);
1996
  constexpr void resize(size_type sz, const T& c);
@@ -1998,12 +2795,12 @@ namespace std {
1998
  constexpr void shrink_to_fit();
1999
 
2000
  // element access
2001
  constexpr reference operator[](size_type n);
2002
  constexpr const_reference operator[](size_type n) const;
2003
- constexpr const_reference at(size_type n) const;
2004
  constexpr reference at(size_type n);
 
2005
  constexpr reference front();
2006
  constexpr const_reference front() const;
2007
  constexpr reference back();
2008
  constexpr const_reference back() const;
2009
 
@@ -2064,11 +2861,11 @@ constexpr explicit vector(const Allocator&) noexcept;
2064
 
2065
  ``` cpp
2066
  constexpr explicit vector(size_type n, const Allocator& = Allocator());
2067
  ```
2068
 
2069
- *Preconditions:* `T` is *Cpp17DefaultInsertable* into `*this`.
2070
 
2071
  *Effects:* Constructs a `vector` with `n` default-inserted elements
2072
  using the specified allocator.
2073
 
2074
  *Complexity:* Linear in `n`.
@@ -2076,11 +2873,11 @@ using the specified allocator.
2076
  ``` cpp
2077
  constexpr vector(size_type n, const T& value,
2078
  const Allocator& = Allocator());
2079
  ```
2080
 
2081
- *Preconditions:* `T` is *Cpp17CopyInsertable* into `*this`.
2082
 
2083
  *Effects:* Constructs a `vector` with `n` copies of `value`, using the
2084
  specified allocator.
2085
 
2086
  *Complexity:* Linear in `n`.
@@ -2094,13 +2891,13 @@ template<class InputIterator>
2094
  *Effects:* Constructs a `vector` equal to the range \[`first`, `last`),
2095
  using the specified allocator.
2096
 
2097
  *Complexity:* Makes only N calls to the copy constructor of `T` (where N
2098
  is the distance between `first` and `last`) and no reallocations if
2099
- iterators `first` and `last` are of forward, bidirectional, or random
2100
- access categories. It makes order N calls to the copy constructor of `T`
2101
- and order log N reallocations if they are just input iterators.
2102
 
2103
  ``` cpp
2104
  template<container-compatible-range<T> R>
2105
  constexpr vector(from_range_t, R&& rg, const Allocator& = Allocator());
2106
  ```
@@ -2108,14 +2905,21 @@ template<container-compatible-range<T> R>
2108
  *Effects:* Constructs a `vector` object with the elements of the range
2109
  `rg`, using the specified allocator.
2110
 
2111
  *Complexity:* Initializes exactly N elements from the results of
2112
  dereferencing successive iterators of `rg`, where N is
2113
- `ranges::distance(rg)`. Performs no reallocations if `R` models
2114
- `ranges::forward_range` or `ranges::sized_range`; otherwise, performs
2115
- order log N reallocations and order N calls to the copy or move
2116
- constructor of `T`.
 
 
 
 
 
 
 
2117
 
2118
  #### Capacity <a id="vector.capacity">[[vector.capacity]]</a>
2119
 
2120
  ``` cpp
2121
  constexpr size_type capacity() const noexcept;
@@ -2128,11 +2932,11 @@ requiring reallocation.
2128
 
2129
  ``` cpp
2130
  constexpr void reserve(size_type n);
2131
  ```
2132
 
2133
- *Preconditions:* `T` is *Cpp17MoveInsertable* into `*this`.
2134
 
2135
  *Effects:* A directive that informs a `vector` of a planned change in
2136
  size, so that it can manage the storage allocation accordingly. After
2137
  `reserve()`, `capacity()` is greater or equal to the argument of
2138
  `reserve` if reallocation happens; and equal to the previous value of
@@ -2141,16 +2945,15 @@ if the current capacity is less than the argument of `reserve()`. If an
2141
  exception is thrown other than by the move constructor of a
2142
  non-*Cpp17CopyInsertable* type, there are no effects.
2143
 
2144
  *Throws:* `length_error` if `n > max_size()`.[^4]
2145
 
2146
- *Complexity:* It does not change the size of the sequence and takes at
2147
- most linear time in the size of the sequence.
2148
 
2149
- *Remarks:* Reallocation invalidates all the references, pointers, and
2150
- iterators referring to the elements in the sequence, as well as the
2151
- past-the-end iterator.
2152
 
2153
  [*Note 1*: If no reallocation happens, they remain
2154
  valid. — *end note*]
2155
 
2156
  No reallocation shall take place during insertions that happen after a
@@ -2159,21 +2962,21 @@ greater than the value of `capacity()`.
2159
 
2160
  ``` cpp
2161
  constexpr void shrink_to_fit();
2162
  ```
2163
 
2164
- *Preconditions:* `T` is *Cpp17MoveInsertable* into `*this`.
2165
 
2166
  *Effects:* `shrink_to_fit` is a non-binding request to reduce
2167
  `capacity()` to `size()`.
2168
 
2169
  [*Note 2*: The request is non-binding to allow latitude for
2170
  implementation-specific optimizations. — *end note*]
2171
 
2172
  It does not increase `capacity()`, but may reduce `capacity()` by
2173
  causing reallocation. If an exception is thrown other than by the move
2174
- constructor of a non-*Cpp17CopyInsertable* `T` there are no effects.
2175
 
2176
  *Complexity:* If reallocation happens, linear in the size of the
2177
  sequence.
2178
 
2179
  *Remarks:* Reallocation invalidates all the references, pointers, and
@@ -2197,40 +3000,40 @@ of `x`.
2197
  ``` cpp
2198
  constexpr void resize(size_type sz);
2199
  ```
2200
 
2201
  *Preconditions:* `T` is *Cpp17MoveInsertable* and
2202
- *Cpp17DefaultInsertable* into `*this`.
2203
 
2204
  *Effects:* If `sz < size()`, erases the last `size() - sz` elements from
2205
  the sequence. Otherwise, appends `sz - size()` default-inserted elements
2206
  to the sequence.
2207
 
2208
  *Remarks:* If an exception is thrown other than by the move constructor
2209
- of a non-*Cpp17CopyInsertable* `T` there are no effects.
2210
 
2211
  ``` cpp
2212
  constexpr void resize(size_type sz, const T& c);
2213
  ```
2214
 
2215
- *Preconditions:* `T` is *Cpp17CopyInsertable* into `*this`.
2216
 
2217
  *Effects:* If `sz < size()`, erases the last `size() - sz` elements from
2218
  the sequence. Otherwise, appends `sz - size()` copies of `c` to the
2219
  sequence.
2220
 
2221
- *Remarks:* If an exception is thrown there are no effects.
2222
 
2223
  #### Data <a id="vector.data">[[vector.data]]</a>
2224
 
2225
  ``` cpp
2226
  constexpr T* data() noexcept;
2227
  constexpr const T* data() const noexcept;
2228
  ```
2229
 
2230
  *Returns:* A pointer such that \[`data()`, `data() + size()`) is a valid
2231
- range. For a non-empty vector, `data()` `==` `addressof(front())`.
2232
 
2233
  *Complexity:* Constant time.
2234
 
2235
  #### Modifiers <a id="vector.modifiers">[[vector.modifiers]]</a>
2236
 
@@ -2262,17 +3065,29 @@ iterators referring to the elements in the sequence, as well as the
2262
  past-the-end iterator. If no reallocation happens, then references,
2263
  pointers, and iterators before the insertion point remain valid but
2264
  those at or after the insertion point, including the past-the-end
2265
  iterator, are invalidated. If an exception is thrown other than by the
2266
  copy constructor, move constructor, assignment operator, or move
2267
- assignment operator of `T` or by any `InputIterator` operation there are
2268
- no effects. If an exception is thrown while inserting a single element
2269
- at the end and `T` is *Cpp17CopyInsertable* or
2270
  `is_nothrow_move_constructible_v<T>` is `true`, there are no effects.
2271
  Otherwise, if an exception is thrown by the move constructor of a
2272
  non-*Cpp17CopyInsertable* `T`, the effects are unspecified.
2273
 
 
 
 
 
 
 
 
 
 
 
 
 
2274
  ``` cpp
2275
  constexpr iterator erase(const_iterator position);
2276
  constexpr iterator erase(const_iterator first, const_iterator last);
2277
  constexpr void pop_back();
2278
  ```
@@ -2289,11 +3104,11 @@ is called the number of times equal to the number of elements in the
2289
  vector after the erased elements.
2290
 
2291
  #### Erasure <a id="vector.erasure">[[vector.erasure]]</a>
2292
 
2293
  ``` cpp
2294
- template<class T, class Allocator, class U>
2295
  constexpr typename vector<T, Allocator>::size_type
2296
  erase(vector<T, Allocator>& c, const U& value);
2297
  ```
2298
 
2299
  *Effects:* Equivalent to:
@@ -2345,13 +3160,10 @@ namespace std {
2345
  using reverse_iterator = std::reverse_iterator<iterator>;
2346
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
2347
 
2348
  // bit reference
2349
  class reference {
2350
- friend class vector;
2351
- constexpr reference() noexcept;
2352
-
2353
  public:
2354
  constexpr reference(const reference&) = default;
2355
  constexpr ~reference();
2356
  constexpr operator bool() const noexcept;
2357
  constexpr reference& operator=(bool x) noexcept;
@@ -2402,23 +3214,23 @@ namespace std {
2402
  constexpr const_iterator cend() const noexcept;
2403
  constexpr const_reverse_iterator crbegin() const noexcept;
2404
  constexpr const_reverse_iterator crend() const noexcept;
2405
 
2406
  // capacity
2407
- [[nodiscard]] constexpr bool empty() const noexcept;
2408
  constexpr size_type size() const noexcept;
2409
  constexpr size_type max_size() const noexcept;
2410
  constexpr size_type capacity() const noexcept;
2411
  constexpr void resize(size_type sz, bool c = false);
2412
  constexpr void reserve(size_type n);
2413
  constexpr void shrink_to_fit();
2414
 
2415
  // element access
2416
  constexpr reference operator[](size_type n);
2417
  constexpr const_reference operator[](size_type n) const;
2418
- constexpr const_reference at(size_type n) const;
2419
  constexpr reference at(size_type n);
 
2420
  constexpr reference front();
2421
  constexpr const_reference front() const;
2422
  constexpr reference back();
2423
  constexpr const_reference back() const;
2424
 
@@ -2449,11 +3261,11 @@ namespace std {
2449
  };
2450
  }
2451
  ```
2452
 
2453
  Unless described below, all operations have the same requirements and
2454
- semantics as the primary `vector` template, except that operations
2455
  dealing with the `bool` value type map to bit values in the container
2456
  storage and `allocator_traits::construct` [[allocator.traits.members]]
2457
  is not used to construct these values.
2458
 
2459
  There is no requirement that the data be stored as a contiguous
@@ -2537,5 +3349,479 @@ template<class FormatContext>
2537
  format(const T& ref, FormatContext& ctx) const;
2538
  ```
2539
 
2540
  Equivalent to: `return `*`underlying_`*`.format(ref, ctx);`
2541
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1
  ## Sequence containers <a id="sequences">[[sequences]]</a>
2
 
3
+ ### General <a id="sequences.general">[[sequences.general]]</a>
4
 
5
+ The headers `<array>`, `<deque>`, `<forward_list>`, `<hive>`,
6
+ `<inplace_vector>`, `<list>`, and `<vector>` define class templates that
7
+ meet the requirements for sequence containers.
8
 
9
  The following exposition-only alias template may appear in deduction
10
  guides for sequence containers:
11
 
12
  ``` cpp
13
  template<class InputIterator>
14
+ using iter-value-type = iterator_traits<InputIterator>::value_type; // exposition only
15
  ```
16
 
17
  ### Header `<array>` synopsis <a id="array.syn">[[array.syn]]</a>
18
 
19
  ``` cpp
20
+ // mostly freestanding
21
  #include <compare> // see [compare.syn]
22
  #include <initializer_list> // see [initializer.list.syn]
23
 
24
  namespace std {
25
  // [array], class template array
26
+ template<class T, size_t N> struct array; // partially freestanding
27
 
28
  template<class T, size_t N>
29
  constexpr bool operator==(const array<T, N>& x, const array<T, N>& y);
30
  template<class T, size_t N>
31
  constexpr synth-three-way-result<T>
 
57
  template<size_t I, class T, size_t N>
58
  constexpr const T&& get(const array<T, N>&&) noexcept;
59
  }
60
  ```
61
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
62
  ### Class template `array` <a id="array">[[array]]</a>
63
 
64
  #### Overview <a id="array.overview">[[array.overview]]</a>
65
 
66
  The header `<array>` defines a class template for storing fixed-size
 
79
  requirements of a sequence container [[sequence.reqmts]]. Descriptions
80
  are provided here only for operations on `array` that are not described
81
  in one of these tables and for operations where there is additional
82
  semantic information.
83
 
84
+ `array<T, N>` is a structural type [[term.structural.type]] if `T` is a
85
+ structural type. Two values `a1` and `a2` of type `array<T, N>` are
86
  template-argument-equivalent [[temp.type]] if and only if each pair of
87
  corresponding elements in `a1` and `a2` are
88
  template-argument-equivalent.
89
 
90
  The types `iterator` and `const_iterator` meet the constexpr iterator
 
127
  constexpr const_iterator cend() const noexcept;
128
  constexpr const_reverse_iterator crbegin() const noexcept;
129
  constexpr const_reverse_iterator crend() const noexcept;
130
 
131
  // capacity
132
+ constexpr bool empty() const noexcept;
133
  constexpr size_type size() const noexcept;
134
  constexpr size_type max_size() const noexcept;
135
 
136
  // element access
137
  constexpr reference operator[](size_type n);
138
  constexpr const_reference operator[](size_type n) const;
139
+ constexpr reference at(size_type n); // freestanding-deleted
140
+ constexpr const_reference at(size_type n) const; // freestanding-deleted
141
  constexpr reference front();
142
  constexpr const_reference front() const;
143
  constexpr reference back();
144
  constexpr const_reference back() const;
145
 
 
152
  }
153
  ```
154
 
155
  #### Constructors, copy, and assignment <a id="array.cons">[[array.cons]]</a>
156
 
157
+ An `array` relies on the implicitly-declared special member functions
 
158
  [[class.default.ctor]], [[class.dtor]], [[class.copy.ctor]] to conform
159
  to the container requirements table in  [[container.requirements]]. In
160
  addition to the requirements specified in the container requirements
161
+ table, the implicitly-declared move constructor and move assignment
162
+ operator for `array` require that `T` be *Cpp17MoveConstructible* or
163
  *Cpp17MoveAssignable*, respectively.
164
 
165
  ``` cpp
166
  template<class T, class... U>
167
  array(T, U...) -> array<T, 1 + sizeof...(U)>;
 
181
  constexpr T* data() noexcept;
182
  constexpr const T* data() const noexcept;
183
  ```
184
 
185
  *Returns:* A pointer such that \[`data()`, `data() + size()`) is a valid
186
+ range. For a non-empty array, `data() == addressof(front())` is `true`.
187
 
188
  ``` cpp
189
  constexpr void fill(const T& u);
190
  ```
191
 
 
233
  ``` cpp
234
  template<class T, size_t N>
235
  constexpr array<remove_cv_t<T>, N> to_array(T (&a)[N]);
236
  ```
237
 
238
+ *Mandates:* `is_array_v<T>` is `false` and
239
+ `is_constructible_v<remove_cv_t<T>, T&>` is `true`.
240
 
241
  *Preconditions:* `T` meets the *Cpp17CopyConstructible* requirements.
242
 
243
  *Returns:* `{{ a[0], `…`, a[N - 1] }}`.
244
 
245
  ``` cpp
246
  template<class T, size_t N>
247
  constexpr array<remove_cv_t<T>, N> to_array(T (&&a)[N]);
248
  ```
249
 
250
+ *Mandates:* `is_array_v<T>` is `false` and
251
+ `is_constructible_v<remove_cv_t<T>, T>` is `true`.
252
 
253
  *Preconditions:* `T` meets the *Cpp17MoveConstructible* requirements.
254
 
255
  *Returns:* `{{ std::move(a[0]), `…`, std::move(a[N - 1]) }}`.
256
 
 
284
  *Mandates:* `I < N` is `true`.
285
 
286
  *Returns:* A reference to the `I`ᵗʰ element of `a`, where indexing is
287
  zero-based.
288
 
289
+ ### Header `<deque>` synopsis <a id="deque.syn">[[deque.syn]]</a>
290
+
291
+ ``` cpp
292
+ #include <compare> // see [compare.syn]
293
+ #include <initializer_list> // see [initializer.list.syn]
294
+
295
+ namespace std {
296
+ // [deque], class template deque
297
+ template<class T, class Allocator = allocator<T>> class deque;
298
+
299
+ template<class T, class Allocator>
300
+ constexpr bool operator==(const deque<T, Allocator>& x, const deque<T, Allocator>& y);
301
+ template<class T, class Allocator>
302
+ constexpr synth-three-way-result<T>
303
+ operator<=>(const deque<T, Allocator>& x, const deque<T, Allocator>& y);
304
+
305
+ template<class T, class Allocator>
306
+ constexpr void swap(deque<T, Allocator>& x, deque<T, Allocator>& y)
307
+ noexcept(noexcept(x.swap(y)));
308
+
309
+ // [deque.erasure], erasure
310
+ template<class T, class Allocator, class U = T>
311
+ constexpr typename deque<T, Allocator>::size_type
312
+ erase(deque<T, Allocator>& c, const U& value);
313
+ template<class T, class Allocator, class Predicate>
314
+ constexpr typename deque<T, Allocator>::size_type
315
+ erase_if(deque<T, Allocator>& c, Predicate pred);
316
+
317
+ namespace pmr {
318
+ template<class T>
319
+ using deque = std::deque<T, polymorphic_allocator<T>>;
320
+ }
321
+ }
322
+ ```
323
+
324
  ### Class template `deque` <a id="deque">[[deque]]</a>
325
 
326
  #### Overview <a id="deque.overview">[[deque.overview]]</a>
327
 
328
  A `deque` is a sequence container that supports random access iterators
 
339
  optional sequence container requirements [[sequence.reqmts]].
340
  Descriptions are provided here only for operations on `deque` that are
341
  not described in one of these tables or for operations where there is
342
  additional semantic information.
343
 
344
+ The types `iterator` and `const_iterator` meet the constexpr iterator
345
+ requirements [[iterator.requirements.general]].
346
+
347
  ``` cpp
348
  namespace std {
349
  template<class T, class Allocator = allocator<T>>
350
  class deque {
351
  public:
352
  // types
353
  using value_type = T;
354
  using allocator_type = Allocator;
355
+ using pointer = allocator_traits<Allocator>::pointer;
356
+ using const_pointer = allocator_traits<Allocator>::const_pointer;
357
  using reference = value_type&;
358
  using const_reference = const value_type&;
359
  using size_type = implementation-defined // type of deque::size_type; // see [container.requirements]
360
  using difference_type = implementation-defined // type of deque::difference_type; // see [container.requirements]
361
  using iterator = implementation-defined // type of deque::iterator; // see [container.requirements]
362
  using const_iterator = implementation-defined // type of deque::const_iterator; // see [container.requirements]
363
  using reverse_iterator = std::reverse_iterator<iterator>;
364
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
365
 
366
  // [deque.cons], construct/copy/destroy
367
+ constexpr deque() : deque(Allocator()) { }
368
+ constexpr explicit deque(const Allocator&);
369
+ constexpr explicit deque(size_type n, const Allocator& = Allocator());
370
+ constexpr deque(size_type n, const T& value, const Allocator& = Allocator());
371
  template<class InputIterator>
372
+ constexpr deque(InputIterator first, InputIterator last, const Allocator& = Allocator());
373
  template<container-compatible-range<T> R>
374
+ constexpr deque(from_range_t, R&& rg, const Allocator& = Allocator());
375
+ constexpr deque(const deque& x);
376
+ constexpr deque(deque&&);
377
+ constexpr deque(const deque&, const type_identity_t<Allocator>&);
378
+ constexpr deque(deque&&, const type_identity_t<Allocator>&);
379
+ constexpr deque(initializer_list<T>, const Allocator& = Allocator());
380
 
381
+ constexpr ~deque();
382
+ constexpr deque& operator=(const deque& x);
383
+ constexpr deque& operator=(deque&& x)
384
  noexcept(allocator_traits<Allocator>::is_always_equal::value);
385
+ constexpr deque& operator=(initializer_list<T>);
386
  template<class InputIterator>
387
+ constexpr void assign(InputIterator first, InputIterator last);
388
  template<container-compatible-range<T> R>
389
+ constexpr void assign_range(R&& rg);
390
+ constexpr void assign(size_type n, const T& t);
391
+ constexpr void assign(initializer_list<T>);
392
+ constexpr allocator_type get_allocator() const noexcept;
393
 
394
  // iterators
395
+ constexpr iterator begin() noexcept;
396
+ constexpr const_iterator begin() const noexcept;
397
+ constexpr iterator end() noexcept;
398
+ constexpr const_iterator end() const noexcept;
399
+ constexpr reverse_iterator rbegin() noexcept;
400
+ constexpr const_reverse_iterator rbegin() const noexcept;
401
+ constexpr reverse_iterator rend() noexcept;
402
+ constexpr const_reverse_iterator rend() const noexcept;
403
 
404
+ constexpr const_iterator cbegin() const noexcept;
405
+ constexpr const_iterator cend() const noexcept;
406
+ constexpr const_reverse_iterator crbegin() const noexcept;
407
+ constexpr const_reverse_iterator crend() const noexcept;
408
 
409
  // [deque.capacity], capacity
410
+ constexpr bool empty() const noexcept;
411
+ constexpr size_type size() const noexcept;
412
+ constexpr size_type max_size() const noexcept;
413
+ constexpr void resize(size_type sz);
414
+ constexpr void resize(size_type sz, const T& c);
415
+ constexpr void shrink_to_fit();
416
 
417
  // element access
418
+ constexpr reference operator[](size_type n);
419
+ constexpr const_reference operator[](size_type n) const;
420
+ constexpr reference at(size_type n);
421
+ constexpr const_reference at(size_type n) const;
422
+ constexpr reference front();
423
+ constexpr const_reference front() const;
424
+ constexpr reference back();
425
+ constexpr const_reference back() const;
426
 
427
  // [deque.modifiers], modifiers
428
+ template<class... Args> constexpr reference emplace_front(Args&&... args);
429
+ template<class... Args> constexpr reference emplace_back(Args&&... args);
430
+ template<class... Args> constexpr iterator emplace(const_iterator position, Args&&... args);
431
 
432
+ constexpr void push_front(const T& x);
433
+ constexpr void push_front(T&& x);
434
  template<container-compatible-range<T> R>
435
+ constexpr void prepend_range(R&& rg);
436
+ constexpr void push_back(const T& x);
437
+ constexpr void push_back(T&& x);
438
  template<container-compatible-range<T> R>
439
+ constexpr void append_range(R&& rg);
440
 
441
+ constexpr iterator insert(const_iterator position, const T& x);
442
+ constexpr iterator insert(const_iterator position, T&& x);
443
+ constexpr iterator insert(const_iterator position, size_type n, const T& x);
444
  template<class InputIterator>
445
+ constexpr iterator insert(const_iterator position,
446
+ InputIterator first, InputIterator last);
447
  template<container-compatible-range<T> R>
448
+ constexpr iterator insert_range(const_iterator position, R&& rg);
449
+ constexpr iterator insert(const_iterator position, initializer_list<T>);
450
 
451
+ constexpr void pop_front();
452
+ constexpr void pop_back();
453
 
454
+ constexpr iterator erase(const_iterator position);
455
+ constexpr iterator erase(const_iterator first, const_iterator last);
456
+ constexpr void swap(deque&)
457
  noexcept(allocator_traits<Allocator>::is_always_equal::value);
458
+ constexpr void clear() noexcept;
459
  };
460
 
461
  template<class InputIterator, class Allocator = allocator<iter-value-type<InputIterator>>>
462
  deque(InputIterator, InputIterator, Allocator = Allocator())
463
  -> deque<iter-value-type<InputIterator>, Allocator>;
 
469
  ```
470
 
471
  #### Constructors, copy, and assignment <a id="deque.cons">[[deque.cons]]</a>
472
 
473
  ``` cpp
474
+ constexpr explicit deque(const Allocator&);
475
  ```
476
 
477
  *Effects:* Constructs an empty `deque`, using the specified allocator.
478
 
479
  *Complexity:* Constant.
480
 
481
  ``` cpp
482
+ constexpr explicit deque(size_type n, const Allocator& = Allocator());
483
  ```
484
 
485
+ *Preconditions:* `T` is *Cpp17DefaultInsertable* into `deque`.
486
 
487
  *Effects:* Constructs a `deque` with `n` default-inserted elements using
488
  the specified allocator.
489
 
490
  *Complexity:* Linear in `n`.
491
 
492
  ``` cpp
493
+ constexpr deque(size_type n, const T& value, const Allocator& = Allocator());
494
  ```
495
 
496
+ *Preconditions:* `T` is *Cpp17CopyInsertable* into `deque`.
497
 
498
  *Effects:* Constructs a `deque` with `n` copies of `value`, using the
499
  specified allocator.
500
 
501
  *Complexity:* Linear in `n`.
502
 
503
  ``` cpp
504
  template<class InputIterator>
505
+ constexpr deque(InputIterator first, InputIterator last, const Allocator& = Allocator());
506
  ```
507
 
508
  *Effects:* Constructs a `deque` equal to the range \[`first`, `last`),
509
  using the specified allocator.
510
 
511
  *Complexity:* Linear in `distance(first, last)`.
512
 
513
  ``` cpp
514
  template<container-compatible-range<T> R>
515
+ constexpr deque(from_range_t, R&& rg, const Allocator& = Allocator());
516
  ```
517
 
518
  *Effects:* Constructs a `deque` with the elements of the range `rg`,
519
  using the specified allocator.
520
 
521
  *Complexity:* Linear in `ranges::distance(rg)`.
522
 
523
  #### Capacity <a id="deque.capacity">[[deque.capacity]]</a>
524
 
525
  ``` cpp
526
+ constexpr void resize(size_type sz);
527
  ```
528
 
529
  *Preconditions:* `T` is *Cpp17MoveInsertable* and
530
+ *Cpp17DefaultInsertable* into `deque`.
531
 
532
  *Effects:* If `sz < size()`, erases the last `size() - sz` elements from
533
  the sequence. Otherwise, appends `sz - size()` default-inserted elements
534
  to the sequence.
535
 
536
  ``` cpp
537
+ constexpr void resize(size_type sz, const T& c);
538
  ```
539
 
540
+ *Preconditions:* `T` is *Cpp17CopyInsertable* into `deque`.
541
 
542
  *Effects:* If `sz < size()`, erases the last `size() - sz` elements from
543
  the sequence. Otherwise, appends `sz - size()` copies of `c` to the
544
  sequence.
545
 
546
  ``` cpp
547
+ constexpr void shrink_to_fit();
548
  ```
549
 
550
+ *Preconditions:* `T` is *Cpp17MoveInsertable* into `deque`.
551
 
552
  *Effects:* `shrink_to_fit` is a non-binding request to reduce memory use
553
  but does not change the size of the sequence.
554
 
555
  [*Note 1*: The request is non-binding to allow latitude for
 
567
  elements in the sequence, as well as the past-the-end iterator.
568
 
569
  #### Modifiers <a id="deque.modifiers">[[deque.modifiers]]</a>
570
 
571
  ``` cpp
572
+ constexpr iterator insert(const_iterator position, const T& x);
573
+ constexpr iterator insert(const_iterator position, T&& x);
574
+ constexpr iterator insert(const_iterator position, size_type n, const T& x);
575
  template<class InputIterator>
576
+ constexpr iterator insert(const_iterator position,
577
  InputIterator first, InputIterator last);
578
  template<container-compatible-range<T> R>
579
+ constexpr iterator insert_range(const_iterator position, R&& rg);
580
+ constexpr iterator insert(const_iterator position, initializer_list<T>);
581
 
582
+ template<class... Args> constexpr reference emplace_front(Args&&... args);
583
+ template<class... Args> constexpr reference emplace_back(Args&&... args);
584
+ template<class... Args> constexpr iterator emplace(const_iterator position, Args&&... args);
585
+ constexpr void push_front(const T& x);
586
+ constexpr void push_front(T&& x);
587
  template<container-compatible-range<T> R>
588
+ constexpr void prepend_range(R&& rg);
589
+ constexpr void push_back(const T& x);
590
+ constexpr void push_back(T&& x);
591
  template<container-compatible-range<T> R>
592
+ constexpr void append_range(R&& rg);
593
  ```
594
 
595
  *Effects:* An insertion in the middle of the deque invalidates all the
596
  iterators and references to elements of the deque. An insertion at
597
  either end of the deque invalidates all the iterators to the deque, but
 
603
  a deque always takes constant time and causes a single call to a
604
  constructor of `T`.
605
 
606
  *Remarks:* If an exception is thrown other than by the copy constructor,
607
  move constructor, assignment operator, or move assignment operator of
608
+ `T`, there are no effects. If an exception is thrown while inserting a
609
  single element at either end, there are no effects. Otherwise, if an
610
  exception is thrown by the move constructor of a
611
  non-*Cpp17CopyInsertable* `T`, the effects are unspecified.
612
 
613
  ``` cpp
614
+ constexpr iterator erase(const_iterator position);
615
+ constexpr iterator erase(const_iterator first, const_iterator last);
616
+ constexpr void pop_front();
617
+ constexpr void pop_back();
618
  ```
619
 
620
  *Effects:* An erase operation that erases the last element of a deque
621
  invalidates only the past-the-end iterator and all iterators and
622
  references to the erased elements. An erase operation that erases the
 
639
  erased elements.
640
 
641
  #### Erasure <a id="deque.erasure">[[deque.erasure]]</a>
642
 
643
  ``` cpp
644
+ template<class T, class Allocator, class U = T>
645
+ constexpr typename deque<T, Allocator>::size_type
646
  erase(deque<T, Allocator>& c, const U& value);
647
  ```
648
 
649
  *Effects:* Equivalent to:
650
 
 
655
  return r;
656
  ```
657
 
658
  ``` cpp
659
  template<class T, class Allocator, class Predicate>
660
+ constexpr typename deque<T, Allocator>::size_type
661
  erase_if(deque<T, Allocator>& c, Predicate pred);
662
  ```
663
 
664
  *Effects:* Equivalent to:
665
 
 
668
  auto r = distance(it, c.end());
669
  c.erase(it, c.end());
670
  return r;
671
  ```
672
 
673
+ ### Header `<forward_list>` synopsis <a id="forward.list.syn">[[forward.list.syn]]</a>
674
+
675
+ ``` cpp
676
+ #include <compare> // see [compare.syn]
677
+ #include <initializer_list> // see [initializer.list.syn]
678
+
679
+ namespace std {
680
+ // [forward.list], class template forward_list
681
+ template<class T, class Allocator = allocator<T>> class forward_list;
682
+
683
+ template<class T, class Allocator>
684
+ constexpr bool operator==(const forward_list<T, Allocator>& x,
685
+ const forward_list<T, Allocator>& y);
686
+ template<class T, class Allocator>
687
+ constexpr synth-three-way-result<T>
688
+ operator<=>(const forward_list<T, Allocator>& x,
689
+ const forward_list<T, Allocator>& y);
690
+
691
+ template<class T, class Allocator>
692
+ constexpr void swap(forward_list<T, Allocator>& x, forward_list<T, Allocator>& y)
693
+ noexcept(noexcept(x.swap(y)));
694
+
695
+ // [forward.list.erasure], erasure
696
+ template<class T, class Allocator, class U = T>
697
+ constexpr typename forward_list<T, Allocator>::size_type
698
+ erase(forward_list<T, Allocator>& c, const U& value);
699
+ template<class T, class Allocator, class Predicate>
700
+ constexpr typename forward_list<T, Allocator>::size_type
701
+ erase_if(forward_list<T, Allocator>& c, Predicate pred);
702
+
703
+ namespace pmr {
704
+ template<class T>
705
+ using forward_list = std::forward_list<T, polymorphic_allocator<T>>;
706
+ }
707
+ }
708
+ ```
709
+
710
  ### Class template `forward_list` <a id="forward.list">[[forward.list]]</a>
711
 
712
  #### Overview <a id="forward.list.overview">[[forward.list.overview]]</a>
713
 
714
  A `forward_list` is a container that supports forward iterators and
 
720
  overhead relative to a hand-written C-style singly linked list. Features
721
  that would conflict with that goal have been omitted. — *end note*]
722
 
723
  A `forward_list` meets all of the requirements of a container
724
  [[container.reqmts]], except that the `size()` member function is not
725
+ provided and `operator==` has linear complexity. A `forward_list` also
726
  meets all of the requirements for an allocator-aware container
727
  [[container.alloc.reqmts]]. In addition, a `forward_list` provides the
728
  `assign` member functions and several of the optional sequence container
729
  requirements [[sequence.reqmts]]. Descriptions are provided here only
730
  for operations on `forward_list` that are not described in that table or
 
734
  the first element of interest, but in a `forward_list` there is no
735
  constant-time way to access a preceding element. For this reason,
736
  `erase_after` and `splice_after` take fully-open ranges, not semi-open
737
  ranges. — *end note*]
738
 
739
+ The types `iterator` and `const_iterator` meet the constexpr iterator
740
+ requirements [[iterator.requirements.general]].
741
+
742
  ``` cpp
743
  namespace std {
744
  template<class T, class Allocator = allocator<T>>
745
  class forward_list {
746
  public:
747
  // types
748
  using value_type = T;
749
  using allocator_type = Allocator;
750
+ using pointer = allocator_traits<Allocator>::pointer;
751
+ using const_pointer = allocator_traits<Allocator>::const_pointer;
752
  using reference = value_type&;
753
  using const_reference = const value_type&;
754
  using size_type = implementation-defined // type of forward_list::size_type; // see [container.requirements]
755
  using difference_type = implementation-defined // type of forward_list::difference_type; // see [container.requirements]
756
  using iterator = implementation-defined // type of forward_list::iterator; // see [container.requirements]
757
  using const_iterator = implementation-defined // type of forward_list::const_iterator; // see [container.requirements]
758
 
759
  // [forward.list.cons], construct/copy/destroy
760
+ constexpr forward_list() : forward_list(Allocator()) { }
761
+ constexpr explicit forward_list(const Allocator&);
762
+ constexpr explicit forward_list(size_type n, const Allocator& = Allocator());
763
+ constexpr forward_list(size_type n, const T& value, const Allocator& = Allocator());
764
  template<class InputIterator>
765
+ constexpr forward_list(InputIterator first, InputIterator last,
766
+ const Allocator& = Allocator());
767
  template<container-compatible-range<T> R>
768
+ constexpr forward_list(from_range_t, R&& rg, const Allocator& = Allocator());
769
+ constexpr forward_list(const forward_list& x);
770
+ constexpr forward_list(forward_list&& x);
771
+ constexpr forward_list(const forward_list& x, const type_identity_t<Allocator>&);
772
+ constexpr forward_list(forward_list&& x, const type_identity_t<Allocator>&);
773
+ constexpr forward_list(initializer_list<T>, const Allocator& = Allocator());
774
+ constexpr ~forward_list();
775
+ constexpr forward_list& operator=(const forward_list& x);
776
+ constexpr forward_list& operator=(forward_list&& x)
777
  noexcept(allocator_traits<Allocator>::is_always_equal::value);
778
+ constexpr forward_list& operator=(initializer_list<T>);
779
  template<class InputIterator>
780
+ constexpr void assign(InputIterator first, InputIterator last);
781
  template<container-compatible-range<T> R>
782
+ constexpr void assign_range(R&& rg);
783
+ constexpr void assign(size_type n, const T& t);
784
+ constexpr void assign(initializer_list<T>);
785
+ constexpr allocator_type get_allocator() const noexcept;
786
 
787
  // [forward.list.iter], iterators
788
+ constexpr iterator before_begin() noexcept;
789
+ constexpr const_iterator before_begin() const noexcept;
790
+ constexpr iterator begin() noexcept;
791
+ constexpr const_iterator begin() const noexcept;
792
+ constexpr iterator end() noexcept;
793
+ constexpr const_iterator end() const noexcept;
794
 
795
+ constexpr const_iterator cbegin() const noexcept;
796
+ constexpr const_iterator cbefore_begin() const noexcept;
797
+ constexpr const_iterator cend() const noexcept;
798
 
799
  // capacity
800
+ constexpr bool empty() const noexcept;
801
+ constexpr size_type max_size() const noexcept;
802
 
803
  // [forward.list.access], element access
804
+ constexpr reference front();
805
+ constexpr const_reference front() const;
806
 
807
  // [forward.list.modifiers], modifiers
808
+ template<class... Args> constexpr reference emplace_front(Args&&... args);
809
+ constexpr void push_front(const T& x);
810
+ constexpr void push_front(T&& x);
811
  template<container-compatible-range<T> R>
812
+ constexpr void prepend_range(R&& rg);
813
+ constexpr void pop_front();
814
 
815
+ template<class... Args>
816
+ constexpr iterator emplace_after(const_iterator position, Args&&... args);
817
+ constexpr iterator insert_after(const_iterator position, const T& x);
818
+ constexpr iterator insert_after(const_iterator position, T&& x);
819
 
820
+ constexpr iterator insert_after(const_iterator position, size_type n, const T& x);
821
  template<class InputIterator>
822
+ constexpr iterator insert_after(const_iterator position,
823
+ InputIterator first, InputIterator last);
824
+ constexpr iterator insert_after(const_iterator position, initializer_list<T> il);
825
  template<container-compatible-range<T> R>
826
+ constexpr iterator insert_range_after(const_iterator position, R&& rg);
827
 
828
+ constexpr iterator erase_after(const_iterator position);
829
+ constexpr iterator erase_after(const_iterator position, const_iterator last);
830
+ constexpr void swap(forward_list&)
831
  noexcept(allocator_traits<Allocator>::is_always_equal::value);
832
 
833
+ constexpr void resize(size_type sz);
834
+ constexpr void resize(size_type sz, const value_type& c);
835
+ constexpr void clear() noexcept;
836
 
837
  // [forward.list.ops], forward_list operations
838
+ constexpr void splice_after(const_iterator position, forward_list& x);
839
+ constexpr void splice_after(const_iterator position, forward_list&& x);
840
+ constexpr void splice_after(const_iterator position, forward_list& x, const_iterator i);
841
+ constexpr void splice_after(const_iterator position, forward_list&& x, const_iterator i);
842
+ constexpr void splice_after(const_iterator position, forward_list& x,
843
  const_iterator first, const_iterator last);
844
+ constexpr void splice_after(const_iterator position, forward_list&& x,
845
  const_iterator first, const_iterator last);
846
 
847
+ constexpr size_type remove(const T& value);
848
+ template<class Predicate> constexpr size_type remove_if(Predicate pred);
849
 
850
  size_type unique();
851
+ template<class BinaryPredicate> constexpr size_type unique(BinaryPredicate binary_pred);
852
 
853
+ constexpr void merge(forward_list& x);
854
+ constexpr void merge(forward_list&& x);
855
+ template<class Compare> constexpr void merge(forward_list& x, Compare comp);
856
+ template<class Compare> constexpr void merge(forward_list&& x, Compare comp);
857
 
858
+ constexpr void sort();
859
+ template<class Compare> constexpr void sort(Compare comp);
860
 
861
+ constexpr void reverse() noexcept;
862
  };
863
 
864
  template<class InputIterator, class Allocator = allocator<iter-value-type<InputIterator>>>
865
  forward_list(InputIterator, InputIterator, Allocator = Allocator())
866
  -> forward_list<iter-value-type<InputIterator>, Allocator>;
 
878
  referenced.
879
 
880
  #### Constructors, copy, and assignment <a id="forward.list.cons">[[forward.list.cons]]</a>
881
 
882
  ``` cpp
883
+ constexpr explicit forward_list(const Allocator&);
884
  ```
885
 
886
  *Effects:* Constructs an empty `forward_list` object using the specified
887
  allocator.
888
 
889
  *Complexity:* Constant.
890
 
891
  ``` cpp
892
+ constexpr explicit forward_list(size_type n, const Allocator& = Allocator());
893
  ```
894
 
895
+ *Preconditions:* `T` is *Cpp17DefaultInsertable* into `forward_list`.
896
 
897
  *Effects:* Constructs a `forward_list` object with `n` default-inserted
898
  elements using the specified allocator.
899
 
900
  *Complexity:* Linear in `n`.
901
 
902
  ``` cpp
903
+ constexpr forward_list(size_type n, const T& value, const Allocator& = Allocator());
904
  ```
905
 
906
+ *Preconditions:* `T` is *Cpp17CopyInsertable* into `forward_list`.
907
 
908
  *Effects:* Constructs a `forward_list` object with `n` copies of `value`
909
  using the specified allocator.
910
 
911
  *Complexity:* Linear in `n`.
912
 
913
  ``` cpp
914
  template<class InputIterator>
915
+ constexpr forward_list(InputIterator first, InputIterator last, const Allocator& = Allocator());
916
  ```
917
 
918
  *Effects:* Constructs a `forward_list` object equal to the range
919
  \[`first`, `last`).
920
 
921
  *Complexity:* Linear in `distance(first, last)`.
922
 
923
  ``` cpp
924
  template<container-compatible-range<T> R>
925
+ constexpr forward_list(from_range_t, R&& rg, const Allocator& = Allocator());
926
  ```
927
 
928
  *Effects:* Constructs a `forward_list` object with the elements of the
929
  range `rg`.
930
 
931
  *Complexity:* Linear in `ranges::distance(rg)`.
932
 
933
  #### Iterators <a id="forward.list.iter">[[forward.list.iter]]</a>
934
 
935
  ``` cpp
936
+ constexpr iterator before_begin() noexcept;
937
+ constexpr const_iterator before_begin() const noexcept;
938
+ constexpr const_iterator cbefore_begin() const noexcept;
939
  ```
940
 
941
  *Effects:* `cbefore_begin()` is equivalent to
942
  `const_cast<forward_list const&>(*this).before_begin()`.
943
 
 
947
  *Remarks:* `before_begin() == end()` shall equal `false`.
948
 
949
  #### Element access <a id="forward.list.access">[[forward.list.access]]</a>
950
 
951
  ``` cpp
952
+ constexpr reference front();
953
+ constexpr const_reference front() const;
954
  ```
955
 
956
  *Returns:* `*begin()`
957
 
958
  #### Modifiers <a id="forward.list.modifiers">[[forward.list.modifiers]]</a>
959
 
960
+ The member functions in this subclause do not affect the validity of
961
+ iterators and references when inserting elements, and when erasing
962
+ elements invalidate iterators and references to the erased elements
963
+ only. If an exception is thrown by any of these member functions there
964
+ is no effect on the container. Inserting `n` elements into a
965
+ `forward_list` is linear in `n`, and the number of calls to the copy or
966
+ move constructor of `T` is exactly equal to `n`. Erasing `n` elements
967
+ from a `forward_list` is linear in `n` and the number of calls to the
968
+ destructor of type `T` is exactly equal to `n`.
969
 
970
  ``` cpp
971
+ template<class... Args> constexpr reference emplace_front(Args&&... args);
972
  ```
973
 
974
  *Effects:* Inserts an object of type `value_type` constructed with
975
  `value_type(std::forward<Args>(args)...)` at the beginning of the list.
976
 
977
  ``` cpp
978
+ constexpr void push_front(const T& x);
979
+ constexpr void push_front(T&& x);
980
  ```
981
 
982
  *Effects:* Inserts a copy of `x` at the beginning of the list.
983
 
984
  ``` cpp
985
  template<container-compatible-range<T> R>
986
+ constexpr void prepend_range(R&& rg);
987
  ```
988
 
989
  *Effects:* Inserts a copy of each element of `rg` at the beginning of
990
  the list.
991
 
992
  [*Note 1*: The order of elements is not reversed. — *end note*]
993
 
994
  ``` cpp
995
+ constexpr void pop_front();
996
  ```
997
 
998
  *Effects:* As if by `erase_after(before_begin())`.
999
 
1000
  ``` cpp
1001
+ constexpr iterator insert_after(const_iterator position, const T& x);
1002
  ```
1003
 
1004
  *Preconditions:* `T` is *Cpp17CopyInsertable* into `forward_list`.
1005
  `position` is `before_begin()` or is a dereferenceable iterator in the
1006
  range \[`begin()`, `end()`).
 
1008
  *Effects:* Inserts a copy of `x` after `position`.
1009
 
1010
  *Returns:* An iterator pointing to the copy of `x`.
1011
 
1012
  ``` cpp
1013
+ constexpr iterator insert_after(const_iterator position, T&& x);
1014
  ```
1015
 
1016
  *Preconditions:* `T` is *Cpp17MoveInsertable* into `forward_list`.
1017
  `position` is `before_begin()` or is a dereferenceable iterator in the
1018
  range \[`begin()`, `end()`).
 
1020
  *Effects:* Inserts a copy of `x` after `position`.
1021
 
1022
  *Returns:* An iterator pointing to the copy of `x`.
1023
 
1024
  ``` cpp
1025
+ constexpr iterator insert_after(const_iterator position, size_type n, const T& x);
1026
  ```
1027
 
1028
  *Preconditions:* `T` is *Cpp17CopyInsertable* into `forward_list`.
1029
  `position` is `before_begin()` or is a dereferenceable iterator in the
1030
  range \[`begin()`, `end()`).
 
1034
  *Returns:* An iterator pointing to the last inserted copy of `x`, or
1035
  `position` if `n == 0` is `true`.
1036
 
1037
  ``` cpp
1038
  template<class InputIterator>
1039
+ constexpr iterator insert_after(const_iterator position,
1040
+ InputIterator first, InputIterator last);
1041
  ```
1042
 
1043
  *Preconditions:* `T` is *Cpp17EmplaceConstructible* into `forward_list`
1044
  from `*first`. `position` is `before_begin()` or is a dereferenceable
1045
  iterator in the range \[`begin()`, `end()`). Neither `first` nor `last`
 
1051
  *Returns:* An iterator pointing to the last inserted element, or
1052
  `position` if `first == last` is `true`.
1053
 
1054
  ``` cpp
1055
  template<container-compatible-range<T> R>
1056
+ constexpr iterator insert_range_after(const_iterator position, R&& rg);
1057
  ```
1058
 
1059
  *Preconditions:* `T` is *Cpp17EmplaceConstructible* into `forward_list`
1060
  from `*ranges::begin(rg)`. `position` is `before_begin()` or is a
1061
  dereferenceable iterator in the range \[`begin()`, `end()`). `rg` and
 
1066
 
1067
  *Returns:* An iterator pointing to the last inserted element, or
1068
  `position` if `rg` is empty.
1069
 
1070
  ``` cpp
1071
+ constexpr iterator insert_after(const_iterator position, initializer_list<T> il);
1072
  ```
1073
 
1074
  *Effects:* Equivalent to:
1075
  `return insert_after(position, il.begin(), il.end());`
1076
 
1077
  ``` cpp
1078
  template<class... Args>
1079
+ constexpr iterator emplace_after(const_iterator position, Args&&... args);
1080
  ```
1081
 
1082
  *Preconditions:* `T` is *Cpp17EmplaceConstructible* into `forward_list`
1083
  from `std::forward<Args>(args)...`. `position` is `before_begin()` or is
1084
  a dereferenceable iterator in the range \[`begin()`, `end()`).
 
1088
  `position`.
1089
 
1090
  *Returns:* An iterator pointing to the new object.
1091
 
1092
  ``` cpp
1093
+ constexpr iterator erase_after(const_iterator position);
1094
  ```
1095
 
1096
  *Preconditions:* The iterator following `position` is dereferenceable.
1097
 
1098
  *Effects:* Erases the element pointed to by the iterator following
 
1102
  was erased, or `end()` if no such element exists.
1103
 
1104
  *Throws:* Nothing.
1105
 
1106
  ``` cpp
1107
+ constexpr iterator erase_after(const_iterator position, const_iterator last);
1108
  ```
1109
 
1110
  *Preconditions:* All iterators in the range (`position`, `last`) are
1111
  dereferenceable.
1112
 
 
1115
  *Returns:* `last`.
1116
 
1117
  *Throws:* Nothing.
1118
 
1119
  ``` cpp
1120
+ constexpr void resize(size_type sz);
1121
  ```
1122
 
1123
+ *Preconditions:* `T` is *Cpp17DefaultInsertable* into `forward_list`.
1124
 
1125
  *Effects:* If `sz < distance(begin(), end())`, erases the last
1126
  `distance(begin(), end()) - sz` elements from the list. Otherwise,
1127
  inserts `sz - distance(begin(), end())` default-inserted elements at the
1128
  end of the list.
1129
 
1130
  ``` cpp
1131
+ constexpr void resize(size_type sz, const value_type& c);
1132
  ```
1133
 
1134
+ *Preconditions:* `T` is *Cpp17CopyInsertable* into `forward_list`.
1135
 
1136
  *Effects:* If `sz < distance(begin(), end())`, erases the last
1137
  `distance(begin(), end()) - sz` elements from the list. Otherwise,
1138
  inserts `sz - distance(begin(), end())` copies of `c` at the end of the
1139
  list.
1140
 
1141
  ``` cpp
1142
+ constexpr void clear() noexcept;
1143
  ```
1144
 
1145
  *Effects:* Erases all elements in the range \[`begin()`, `end()`).
1146
 
1147
  *Remarks:* Does not invalidate past-the-end iterators.
 
1156
  list and `n` is an integer, means an iterator `j` such that `j + n == i`
1157
  is `true`. For `merge` and `sort`, the definitions and requirements in
1158
  [[alg.sorting]] apply.
1159
 
1160
  ``` cpp
1161
+ constexpr void splice_after(const_iterator position, forward_list& x);
1162
+ constexpr void splice_after(const_iterator position, forward_list&& x);
1163
  ```
1164
 
1165
  *Preconditions:* `position` is `before_begin()` or is a dereferenceable
1166
  iterator in the range \[`begin()`, `end()`).
1167
  `get_allocator() == x.get_allocator()` is `true`. `addressof(x) != this`
 
1176
  *Throws:* Nothing.
1177
 
1178
  *Complexity:* 𝑂(`distance(x.begin(), x.end())`)
1179
 
1180
  ``` cpp
1181
+ constexpr void splice_after(const_iterator position, forward_list& x, const_iterator i);
1182
+ constexpr void splice_after(const_iterator position, forward_list&& x, const_iterator i);
1183
  ```
1184
 
1185
  *Preconditions:* `position` is `before_begin()` or is a dereferenceable
1186
  iterator in the range \[`begin()`, `end()`). The iterator following `i`
1187
  is a dereferenceable iterator in `x`.
 
1197
  *Throws:* Nothing.
1198
 
1199
  *Complexity:* 𝑂(1)
1200
 
1201
  ``` cpp
1202
+ constexpr void splice_after(const_iterator position, forward_list& x,
1203
  const_iterator first, const_iterator last);
1204
+ constexpr void splice_after(const_iterator position, forward_list&& x,
1205
  const_iterator first, const_iterator last);
1206
  ```
1207
 
1208
  *Preconditions:* `position` is `before_begin()` or is a dereferenceable
1209
  iterator in the range \[`begin()`, `end()`). (`first`, `last`) is a
 
1219
  into `*this`, not into `x`.
1220
 
1221
  *Complexity:* 𝑂(`distance(first, last)`)
1222
 
1223
  ``` cpp
1224
+ constexpr size_type remove(const T& value);
1225
+ template<class Predicate> constexpr size_type remove_if(Predicate pred);
1226
  ```
1227
 
1228
  *Effects:* Erases all the elements in the list referred to by a list
1229
  iterator `i` for which the following conditions hold: `*i == value` (for
1230
  `remove()`), `pred(*i)` is `true` (for `remove_if()`). Invalidates only
 
1239
  corresponding predicate.
1240
 
1241
  *Remarks:* Stable [[algorithm.stable]].
1242
 
1243
  ``` cpp
1244
+ constexpr size_type unique();
1245
+ template<class BinaryPredicate> constexpr size_type unique(BinaryPredicate binary_pred);
1246
  ```
1247
 
1248
  Let `binary_pred` be `equal_to<>{}` for the first overload.
1249
 
1250
  *Preconditions:* `binary_pred` is an equivalence relation.
 
1262
  *Complexity:* If `empty()` is `false`, exactly
1263
  `distance(begin(), end()) - 1` applications of the corresponding
1264
  predicate, otherwise no applications of the predicate.
1265
 
1266
  ``` cpp
1267
+ constexpr void merge(forward_list& x);
1268
+ constexpr void merge(forward_list&& x);
1269
+ template<class Compare> constexpr void merge(forward_list& x, Compare comp);
1270
+ template<class Compare> constexpr void merge(forward_list&& x, Compare comp);
1271
  ```
1272
 
1273
  Let `comp` be `less<>` for the first two overloads.
1274
 
1275
  *Preconditions:* `*this` and `x` are both sorted with respect to the
 
1291
  *Remarks:* Stable [[algorithm.stable]]. If `addressof(x) != this`, `x`
1292
  is empty after the merge. No elements are copied by this operation. If
1293
  an exception is thrown other than by a comparison, there are no effects.
1294
 
1295
  ``` cpp
1296
+ constexpr void sort();
1297
+ template<class Compare> constexpr void sort(Compare comp);
1298
  ```
1299
 
1300
  *Effects:* Sorts the list according to the `operator<` or the `comp`
1301
  function object. If an exception is thrown, the order of the elements in
1302
  `*this` is unspecified. Does not affect the validity of iterators and
 
1306
  `distance(begin(), end())`.
1307
 
1308
  *Remarks:* Stable [[algorithm.stable]].
1309
 
1310
  ``` cpp
1311
+ constexpr void reverse() noexcept;
1312
  ```
1313
 
1314
  *Effects:* Reverses the order of the elements in the list. Does not
1315
  affect the validity of iterators and references.
1316
 
1317
  *Complexity:* Linear time.
1318
 
1319
  #### Erasure <a id="forward.list.erasure">[[forward.list.erasure]]</a>
1320
 
1321
  ``` cpp
1322
+ template<class T, class Allocator, class U = T>
1323
+ constexpr typename forward_list<T, Allocator>::size_type
1324
  erase(forward_list<T, Allocator>& c, const U& value);
1325
  ```
1326
 
1327
  *Effects:* Equivalent to:
1328
+
1329
+ ``` cpp
1330
+ return erase_if(c, [&](const auto& elem) -> bool { return elem == value; });
1331
+ ```
1332
 
1333
  ``` cpp
1334
  template<class T, class Allocator, class Predicate>
1335
+ constexpr typename forward_list<T, Allocator>::size_type
1336
  erase_if(forward_list<T, Allocator>& c, Predicate pred);
1337
  ```
1338
 
1339
  *Effects:* Equivalent to: `return c.remove_if(pred);`
1340
 
1341
+ ### Header `<hive>` synopsis <a id="hive.syn">[[hive.syn]]</a>
1342
+
1343
+ ``` cpp
1344
+ #include <initializer_list> // see [initializer.list.syn]
1345
+ #include <compare> // see [compare.syn]
1346
+
1347
+ namespace std {
1348
+ struct hive_limits {
1349
+ size_t min;
1350
+ size_t max;
1351
+ constexpr hive_limits(size_t minimum, size_t maximum) noexcept
1352
+ : min(minimum), max(maximum) {}
1353
+ };
1354
+
1355
+ // \ref {hive}, class template hive
1356
+ template<class T, class Allocator = allocator<T>> class hive;
1357
+
1358
+ template<class T, class Allocator>
1359
+ void swap(hive<T, Allocator>& x, hive<T, Allocator>& y)
1360
+ noexcept(noexcept(x.swap(y)));
1361
+
1362
+ template<class T, class Allocator, class U = T>
1363
+ typename hive<T, Allocator>::size_type
1364
+ erase(hive<T, Allocator>& c, const U& value);
1365
+
1366
+ template<class T, class Allocator, class Predicate>
1367
+ typename hive<T, Allocator>::size_type
1368
+ erase_if(hive<T, Allocator>& c, Predicate pred);
1369
+
1370
+ namespace pmr {
1371
+ template<class T>
1372
+ using hive = std::hive<T, polymorphic_allocator<T>>;
1373
+ }
1374
+ }
1375
+ ```
1376
+
1377
+ ### Class template `hive` <a id="hive">[[hive]]</a>
1378
+
1379
+ #### Overview <a id="hive.overview">[[hive.overview]]</a>
1380
+
1381
+ A `hive` is a type of sequence container that provides constant-time
1382
+ insertion and erasure operations. Storage is automatically managed in
1383
+ multiple memory blocks, referred to as *element blocks*. Insertion
1384
+ position is determined by the container, and insertion may re-use the
1385
+ memory locations of erased elements.
1386
+
1387
+ Element blocks which contain elements are referred to as *active
1388
+ blocks*, those which do not are referred to as *reserved blocks*. Active
1389
+ blocks which become empty of elements are either deallocated or become
1390
+ reserved blocks. Reserved blocks become active blocks when they are used
1391
+ to store elements. A user can create additional reserved blocks by
1392
+ calling `reserve`.
1393
+
1394
+ Erasures use unspecified techniques of constant time complexity to
1395
+ identify the memory locations of erased elements, which are subsequently
1396
+ skipped during iteration, as opposed to relocating subsequent elements
1397
+ during erasure.
1398
+
1399
+ Active block capacities have an *implementation-defined* growth factor
1400
+ (which need not be integral), for example a new active block’s capacity
1401
+ could be equal to the summed capacities of the pre-existing active
1402
+ blocks.
1403
+
1404
+ Limits can be placed on both the minimum and maximum element capacities
1405
+ of element blocks, both by users and implementations.
1406
+
1407
+ - The minimum limit shall be no larger than the maximum limit.
1408
+ - When limits are not specified by a user during construction, the
1409
+ implementation’s default limits are used.
1410
+ - The default limits of an implementation are not guaranteed to be the
1411
+ same as the minimum and maximum possible capacities for an
1412
+ implementation’s element blocks. \[*Note 1*: To allow latitude for
1413
+ both implementation-specific and user-directed
1414
+ optimization. — *end note*] The latter are defined as hard limits.
1415
+ The maximum hard limit shall be no larger than
1416
+ `std::allocator_traits<Allocator>::max_size()`.
1417
+ - If user-specified limits are not within hard limits, or if the
1418
+ specified minimum limit is greater than the specified maximum limit,
1419
+ the behavior is undefined.
1420
+ - An element block is said to be *within the bounds* of a pair of
1421
+ minimum/maximum limits when its capacity is greater-or-equal-to the
1422
+ minimum limit and less-than-or-equal-to the maximum limit.
1423
+
1424
+ A `hive` conforms to the requirements for containers
1425
+ [[container.reqmts]], with the exception of operators `==` and `!=`. A
1426
+ `hive` also meets the requirements of a reversible container
1427
+ [[container.rev.reqmts]], of an allocator-aware container
1428
+ [[container.alloc.reqmts]], and some of the requirements of a sequence
1429
+ container [[sequence.reqmts]]. Descriptions are provided here only for
1430
+ operations on `hive` that are not described in that table or for
1431
+ operations where there is additional semantic information.
1432
+
1433
+ The iterators of `hive` meet the *Cpp17BidirectionalIterator*
1434
+ requirements but also model `three_way_comparable<strong_ordering>`.
1435
+
1436
+ ``` cpp
1437
+ namespace std {
1438
+ template<class T, class Allocator = allocator<T>>
1439
+ class hive {
1440
+ public:
1441
+ // types
1442
+ using value_type = T;
1443
+ using allocator_type = Allocator;
1444
+ using pointer = allocator_traits<Allocator>::pointer;
1445
+ using const_pointer = allocator_traits<Allocator>::const_pointer;
1446
+ using reference = value_type&;
1447
+ using const_reference = const value_type&;
1448
+ using size_type = implementation-defined; // see [container.requirements]
1449
+ using difference_type = implementation-defined; // see [container.requirements]
1450
+ using iterator = implementation-defined; // see [container.requirements]
1451
+ using const_iterator = implementation-defined; // see [container.requirements]
1452
+ using reverse_iterator = std::reverse_iterator<iterator>; // see [container.requirements]
1453
+ using const_reverse_iterator = std::reverse_iterator<const_iterator>; // see [container.requirements]
1454
+
1455
+ // [hive.cons], construct/copy/destroy
1456
+ constexpr hive() noexcept(noexcept(Allocator())) : hive(Allocator()) {}
1457
+ constexpr explicit hive(const Allocator&) noexcept;
1458
+ constexpr explicit hive(hive_limits block_limits) : hive(block_limits, Allocator()) {}
1459
+ constexpr hive(hive_limits block_limits, const Allocator&);
1460
+ explicit hive(size_type n, const Allocator& = Allocator());
1461
+ hive(size_type n, hive_limits block_limits, const Allocator& = Allocator());
1462
+ hive(size_type n, const T& value, const Allocator& = Allocator());
1463
+ hive(size_type n, const T& value, hive_limits block_limits, const Allocator& = Allocator());
1464
+ template<class InputIterator>
1465
+ hive(InputIterator first, InputIterator last, const Allocator& = Allocator());
1466
+ template<class InputIterator>
1467
+ hive(InputIterator first, InputIterator last, hive_limits block_limits,
1468
+ const Allocator& = Allocator());
1469
+ template<container-compatible-range<T> R>
1470
+ hive(from_range_t, R&& rg, const Allocator& = Allocator());
1471
+ template<container-compatible-range<T> R>
1472
+ hive(from_range_t, R&& rg, hive_limits block_limits, const Allocator& = Allocator());
1473
+ hive(const hive& x);
1474
+ hive(hive&&) noexcept;
1475
+ hive(const hive& x, const type_identity_t<Allocator>& alloc);
1476
+ hive(hive&&, const type_identity_t<Allocator>& alloc);
1477
+ hive(initializer_list<T> il, const Allocator& = Allocator());
1478
+ hive(initializer_list<T> il, hive_limits block_limits, const Allocator& = Allocator());
1479
+ ~hive();
1480
+
1481
+ hive& operator=(const hive& x);
1482
+ hive& operator=(hive&& x) noexcept(see below);
1483
+ hive& operator=(initializer_list<T>);
1484
+ template<class InputIterator>
1485
+ void assign(InputIterator first, InputIterator last);
1486
+ template<container-compatible-range<T> R>
1487
+ void assign_range(R&& rg);
1488
+ void assign(size_type n, const T& t);
1489
+ void assign(initializer_list<T>);
1490
+ allocator_type get_allocator() const noexcept;
1491
+
1492
+ // iterators
1493
+ iterator begin() noexcept;
1494
+ const_iterator begin() const noexcept;
1495
+ iterator end() noexcept;
1496
+ const_iterator end() const noexcept;
1497
+ reverse_iterator rbegin() noexcept;
1498
+ const_reverse_iterator rbegin() const noexcept;
1499
+ reverse_iterator rend() noexcept;
1500
+ const_reverse_iterator rend() const noexcept;
1501
+ const_iterator cbegin() const noexcept;
1502
+ const_iterator cend() const noexcept;
1503
+ const_reverse_iterator crbegin() const noexcept;
1504
+ const_reverse_iterator crend() const noexcept;
1505
+
1506
+ // [hive.capacity], capacity
1507
+ bool empty() const noexcept;
1508
+ size_type size() const noexcept;
1509
+ size_type max_size() const noexcept;
1510
+ size_type capacity() const noexcept;
1511
+ void reserve(size_type n);
1512
+ void shrink_to_fit();
1513
+ void trim_capacity() noexcept;
1514
+ void trim_capacity(size_type n) noexcept;
1515
+ constexpr hive_limits block_capacity_limits() const noexcept;
1516
+ static constexpr hive_limits block_capacity_default_limits() noexcept;
1517
+ static constexpr hive_limits block_capacity_hard_limits() noexcept;
1518
+ void reshape(hive_limits block_limits);
1519
+
1520
+ // [hive.modifiers], modifiers
1521
+ template<class... Args> iterator emplace(Args&&... args);
1522
+ template<class... Args> iterator emplace_hint(const_iterator hint, Args&&... args);
1523
+ iterator insert(const T& x);
1524
+ iterator insert(T&& x);
1525
+ iterator insert(const_iterator hint, const T& x);
1526
+ iterator insert(const_iterator hint, T&& x);
1527
+ void insert(initializer_list<T> il);
1528
+ template<container-compatible-range<T> R>
1529
+ void insert_range(R&& rg);
1530
+ template<class InputIterator>
1531
+ void insert(InputIterator first, InputIterator last);
1532
+ void insert(size_type n, const T& x);
1533
+
1534
+ iterator erase(const_iterator position);
1535
+ iterator erase(const_iterator first, const_iterator last);
1536
+ void swap(hive&) noexcept(see below);
1537
+ void clear() noexcept;
1538
+
1539
+ // [hive.operations], hive operations
1540
+ void splice(hive& x);
1541
+ void splice(hive&& x);
1542
+ template<class BinaryPredicate = equal_to<T>>
1543
+ size_type unique(BinaryPredicate binary_pred = BinaryPredicate());
1544
+
1545
+ template<class Compare = less<T>>
1546
+ void sort(Compare comp = Compare());
1547
+
1548
+ iterator get_iterator(const_pointer p) noexcept;
1549
+ const_iterator get_iterator(const_pointer p) const noexcept;
1550
+
1551
+ private:
1552
+ hive_limits current-limits = implementation-defined; // exposition only
1553
+ };
1554
+
1555
+ template<class InputIterator, class Allocator = allocator<iter-value-type<InputIterator>>>
1556
+ hive(InputIterator, InputIterator, Allocator = Allocator())
1557
+ -> hive<iter-value-type<InputIterator>, Allocator>;
1558
+
1559
+ template<class InputIterator, class Allocator = allocator<iter-value-type<InputIterator>>>
1560
+ hive(InputIterator, InputIterator, hive_limits, Allocator = Allocator())
1561
+ -> hive<iter-value-type<InputIterator>, Allocator>;
1562
+
1563
+ template<ranges::input_range R, class Allocator = allocator<ranges::range_value_t<R>>>
1564
+ hive(from_range_t, R&&, Allocator = Allocator())
1565
+ -> hive<ranges::range_value_t<R>, Allocator>;
1566
+
1567
+ template<ranges::input_range R, class Allocator = allocator<ranges::range_value_t<R>>>
1568
+ hive(from_range_t, R&&, hive_limits, Allocator = Allocator())
1569
+ -> hive<ranges::range_value_t<R>, Allocator>;
1570
+ }
1571
+ ```
1572
+
1573
+ #### Constructors, copy, and assignment <a id="hive.cons">[[hive.cons]]</a>
1574
+
1575
+ ``` cpp
1576
+ constexpr explicit hive(const Allocator&) noexcept;
1577
+ ```
1578
+
1579
+ *Effects:* Constructs an empty `hive`, using the specified allocator.
1580
+
1581
+ *Complexity:* Constant.
1582
+
1583
+ ``` cpp
1584
+ constexpr hive(hive_limits block_limits, const Allocator&);
1585
+ ```
1586
+
1587
+ *Effects:* Constructs an empty `hive`, using the specified allocator.
1588
+ Initializes *current-limits* with `block_limits`.
1589
+
1590
+ *Complexity:* Constant.
1591
+
1592
+ ``` cpp
1593
+ explicit hive(size_type n, const Allocator& = Allocator());
1594
+ hive(size_type n, hive_limits block_limits, const Allocator& = Allocator());
1595
+ ```
1596
+
1597
+ *Preconditions:* `T` is *Cpp17DefaultInsertable* into `hive`.
1598
+
1599
+ *Effects:* Constructs a `hive` with `n` default-inserted elements, using
1600
+ the specified allocator. If the second overload is called, also
1601
+ initializes *current-limits* with `block_limits`.
1602
+
1603
+ *Complexity:* Linear in `n`.
1604
+
1605
+ ``` cpp
1606
+ hive(size_type n, const T& value, const Allocator& = Allocator());
1607
+ hive(size_type n, const T& value, hive_limits block_limits, const Allocator& = Allocator());
1608
+ ```
1609
+
1610
+ *Preconditions:* `T` is *Cpp17CopyInsertable* into `hive`.
1611
+
1612
+ *Effects:* Constructs a `hive` with `n` copies of `value`, using the
1613
+ specified allocator. If the second overload is called, also initializes
1614
+ *current-limits* with `block_limits`.
1615
+
1616
+ *Complexity:* Linear in `n`.
1617
+
1618
+ ``` cpp
1619
+ template<class InputIterator>
1620
+ hive(InputIterator first, InputIterator last, const Allocator& = Allocator());
1621
+ template<class InputIterator>
1622
+ hive(InputIterator first, InputIterator last, hive_limits block_limits,
1623
+ const Allocator& = Allocator());
1624
+ ```
1625
+
1626
+ *Effects:* Constructs a `hive` equal to the range \[`first`, `last`),
1627
+ using the specified allocator. If the second overload is called, also
1628
+ initializes *current-limits* with `block_limits`.
1629
+
1630
+ *Complexity:* Linear in `distance(first, last)`.
1631
+
1632
+ ``` cpp
1633
+ template<container-compatible-range<T> R>
1634
+ hive(from_range_t, R&& rg, const Allocator& = Allocator());
1635
+ template<container-compatible-range<T> R>
1636
+ hive(from_range_t, R&& rg, hive_limits block_limits, const Allocator& = Allocator());
1637
+ ```
1638
+
1639
+ *Effects:* Constructs a `hive` object with the elements of the range
1640
+ `rg`, using the specified allocator. If the second overload is called,
1641
+ also initializes *current-limits* with `block_limits`.
1642
+
1643
+ *Complexity:* Linear in `ranges::distance(rg)`.
1644
+
1645
+ ``` cpp
1646
+ hive(const hive& x);
1647
+ hive(const hive& x, const type_identity_t<Allocator>& alloc);
1648
+ ```
1649
+
1650
+ *Preconditions:* `T` is *Cpp17CopyInsertable* into `hive`.
1651
+
1652
+ *Effects:* Constructs a `hive` object with the elements of `x`. If the
1653
+ second overload is called, uses `alloc`. Initializes *current-limits*
1654
+ with `x.`*`current-limits`*.
1655
+
1656
+ *Complexity:* Linear in `x.size()`.
1657
+
1658
+ ``` cpp
1659
+ hive(hive&& x) noexcept;
1660
+ hive(hive&& x, const type_identity_t<Allocator>& alloc);
1661
+ ```
1662
+
1663
+ *Preconditions:* For the second overload, when
1664
+ `allocator_traits<alloc>::is_always_equal::value` is `false`, `T` meets
1665
+ the *Cpp17MoveInsertable* requirements.
1666
+
1667
+ *Effects:* When the first overload is called, or the second overload is
1668
+ called and `alloc == x.get_allocator()` is `true`, *current-limits* is
1669
+ set to `x.`*`current-limits`* and each element block is moved from `x`
1670
+ into `*this`. Pointers and references to the elements of `x` now refer
1671
+ to those same elements but as members of `*this`. Iterators referring to
1672
+ the elements of `x` will continue to refer to their elements, but they
1673
+ now behave as iterators into `*this`.
1674
+
1675
+ If the second overload is called and `alloc == x.get_allocator()` is
1676
+ `false`, each element in `x` is moved into `*this`. References, pointers
1677
+ and iterators referring to the elements of `x`, as well as the
1678
+ past-the-end iterator of `x`, are invalidated.
1679
+
1680
+ *Ensures:* `x.empty()` is `true`.
1681
+
1682
+ *Complexity:* If the second overload is called and
1683
+ `alloc == x.get_allocator()` is `false`, linear in `x.size()`. Otherwise
1684
+ constant.
1685
+
1686
+ ``` cpp
1687
+ hive(initializer_list<T> il, const Allocator& = Allocator());
1688
+ hive(initializer_list<T> il, hive_limits block_limits, const Allocator& = Allocator());
1689
+ ```
1690
+
1691
+ *Preconditions:* `T` is *Cpp17CopyInsertable* into `hive`.
1692
+
1693
+ *Effects:* Constructs a `hive` object with the elements of `il`, using
1694
+ the specified allocator. If the second overload is called, also
1695
+ initializes *current-limits* with `block_limits`.
1696
+
1697
+ *Complexity:* Linear in `il.size()`.
1698
+
1699
+ ``` cpp
1700
+ hive& operator=(const hive& x);
1701
+ ```
1702
+
1703
+ *Preconditions:* `T` is *Cpp17CopyInsertable* into `hive` and
1704
+ *Cpp17CopyAssignable*.
1705
+
1706
+ *Effects:* All elements in `*this` are either copy-assigned to, or
1707
+ destroyed. All elements in `x` are copied into `*this`.
1708
+
1709
+ [*Note 1*: *current-limits* is unchanged. — *end note*]
1710
+
1711
+ *Complexity:* Linear in `size() + x.size()`.
1712
+
1713
+ ``` cpp
1714
+ hive& operator=(hive&& x)
1715
+ noexcept(allocator_traits<Allocator>::propagate_on_container_move_assignment::value ||
1716
+ allocator_traits<Allocator>::is_always_equal::value);
1717
+ ```
1718
+
1719
+ *Preconditions:* When
1720
+
1721
+ ``` cpp
1722
+ (allocator_traits<Allocator>::propagate_on_container_move_assignment::value ||
1723
+ allocator_traits<Allocator>::is_always_equal::value)
1724
+ ```
1725
+
1726
+ is `false`, `T` is *Cpp17MoveInsertable* into `hive` and
1727
+ *Cpp17MoveAssignable*.
1728
+
1729
+ *Effects:* Each element in `*this` is either move-assigned to, or
1730
+ destroyed. When
1731
+
1732
+ ``` cpp
1733
+ (allocator_traits<Allocator>::propagate_on_container_move_assignment::value ||
1734
+ get_allocator() == x.get_allocator())
1735
+ ```
1736
+
1737
+ is `true`, *current-limits* is set to `x.`*`current-limits`* and each
1738
+ element block is moved from `x` into `*this`. Pointers and references to
1739
+ the elements of `x` now refer to those same elements but as members of
1740
+ `*this`. Iterators referring to the elements of `x` will continue to
1741
+ refer to their elements, but they now behave as iterators into `*this`,
1742
+ not into `x`.
1743
+
1744
+ When
1745
+
1746
+ ``` cpp
1747
+ (allocator_traits<Allocator>::propagate_on_container_move_assignment::value ||
1748
+ get_allocator() == x.get_allocator())
1749
+ ```
1750
+
1751
+ is `false`, each element in `x` is moved into `*this`. References,
1752
+ pointers and iterators referring to the elements of `x`, as well as the
1753
+ past-the-end iterator of `x`, are invalidated.
1754
+
1755
+ *Ensures:* `x.empty()` is `true`.
1756
+
1757
+ *Complexity:* Linear in `size()`. If
1758
+
1759
+ ``` cpp
1760
+ (allocator_traits<Allocator>::propagate_on_container_move_assignment::value ||
1761
+ get_allocator() == x.get_allocator())
1762
+ ```
1763
+
1764
+ is `false`, also linear in `x.size()`.
1765
+
1766
+ #### Capacity <a id="hive.capacity">[[hive.capacity]]</a>
1767
+
1768
+ ``` cpp
1769
+ size_type capacity() const noexcept;
1770
+ ```
1771
+
1772
+ *Returns:* The total number of elements that `*this` can hold without
1773
+ requiring allocation of more element blocks.
1774
+
1775
+ *Complexity:* Constant.
1776
+
1777
+ ``` cpp
1778
+ void reserve(size_type n);
1779
+ ```
1780
+
1781
+ *Effects:* If `n <= capacity()` is `true`, there are no effects.
1782
+ Otherwise increases `capacity()` by allocating reserved blocks.
1783
+
1784
+ *Ensures:* `capacity() >= n` is `true`.
1785
+
1786
+ *Throws:* `length_error` if `n > max_size()`, as well as any exceptions
1787
+ thrown by the allocator.
1788
+
1789
+ *Complexity:* Linear in the number of reserved blocks allocated.
1790
+
1791
+ *Remarks:* The size of the sequence is not changed. All references,
1792
+ pointers, and iterators referring to elements in `*this`, as well as the
1793
+ past-the-end iterator, remain valid.
1794
+
1795
+ ``` cpp
1796
+ void shrink_to_fit();
1797
+ ```
1798
+
1799
+ *Preconditions:* `T` is *Cpp17MoveInsertable* into `hive`.
1800
+
1801
+ *Effects:* `shrink_to_fit` is a non-binding request to reduce
1802
+ `capacity()` to be closer to `size()`.
1803
+
1804
+ [*Note 1*: The request is non-binding to allow latitude for
1805
+ implementation-specific optimizations. — *end note*]
1806
+
1807
+ It does not increase `capacity()`, but may reduce `capacity()`. It may
1808
+ reallocate elements. If `capacity()` is already equal to `size()`, there
1809
+ are no effects. If an exception is thrown during allocation of a new
1810
+ element block, `capacity()` may be reduced and reallocation may occur.
1811
+ Otherwise if an exception is thrown, the effects are unspecified.
1812
+
1813
+ *Complexity:* If reallocation happens, linear in the size of the
1814
+ sequence.
1815
+
1816
+ *Remarks:* If reallocation happens, the order of the elements in `*this`
1817
+ may change and all references, pointers, and iterators referring to the
1818
+ elements in `*this`, as well as the past-the-end iterator, are
1819
+ invalidated.
1820
+
1821
+ ``` cpp
1822
+ void trim_capacity() noexcept;
1823
+ void trim_capacity(size_type n) noexcept;
1824
+ ```
1825
+
1826
+ *Effects:* For the first overload, all reserved blocks are deallocated,
1827
+ and `capacity()` is reduced accordingly. For the second overload,
1828
+ `capacity()` is reduced to no less than `n`.
1829
+
1830
+ *Complexity:* Linear in the number of reserved blocks deallocated.
1831
+
1832
+ *Remarks:* All references, pointers, and iterators referring to elements
1833
+ in `*this`, as well as the past-the-end iterator, remain valid.
1834
+
1835
+ ``` cpp
1836
+ constexpr hive_limits block_capacity_limits() const noexcept;
1837
+ ```
1838
+
1839
+ *Returns:* *current-limits*.
1840
+
1841
+ *Complexity:* Constant.
1842
+
1843
+ ``` cpp
1844
+ static constexpr hive_limits block_capacity_default_limits() noexcept;
1845
+ ```
1846
+
1847
+ *Returns:* A `hive_limits` struct with the `min` and `max` members set
1848
+ to the implementation’s default limits.
1849
+
1850
+ *Complexity:* Constant.
1851
+
1852
+ ``` cpp
1853
+ static constexpr hive_limits block_capacity_hard_limits() noexcept;
1854
+ ```
1855
+
1856
+ *Returns:* A `hive_limits` struct with the `min` and `max` members set
1857
+ to the implementation’s hard limits.
1858
+
1859
+ *Complexity:* Constant.
1860
+
1861
+ ``` cpp
1862
+ void reshape(hive_limits block_limits);
1863
+ ```
1864
+
1865
+ *Preconditions:* `T` is *Cpp17MoveInsertable* into `hive`.
1866
+
1867
+ *Effects:* For any active blocks not within the bounds of
1868
+ `block_limits`, the elements within those active blocks are reallocated
1869
+ to new or existing element blocks which are within the bounds. Any
1870
+ element blocks not within the bounds of `block_limits` are deallocated.
1871
+ If an exception is thrown during allocation of a new element block,
1872
+ `capacity()` may be reduced, reallocation may occur, and
1873
+ *current-limits* may be assigned a value other than `block_limits`.
1874
+ Otherwise `block_limits` is assigned to *current-limits*. If any other
1875
+ exception is thrown the effects are unspecified.
1876
+
1877
+ *Ensures:* `size()` is unchanged.
1878
+
1879
+ *Complexity:* Linear in the number of element blocks in `*this`. If
1880
+ reallocation happens, also linear in the number of elements reallocated.
1881
+
1882
+ *Remarks:* This operation may change `capacity()`. If reallocation
1883
+ happens, the order of the elements in `*this` may change. Reallocation
1884
+ invalidates all references, pointers, and iterators referring to the
1885
+ elements in `*this`, as well as the past-the-end iterator.
1886
+
1887
+ [*Note 2*: If no reallocation happens, they remain
1888
+ valid. — *end note*]
1889
+
1890
+ #### Modifiers <a id="hive.modifiers">[[hive.modifiers]]</a>
1891
+
1892
+ ``` cpp
1893
+ template<class... Args> iterator emplace(Args&&... args);
1894
+ template<class... Args> iterator emplace_hint(const_iterator hint, Args&&... args);
1895
+ ```
1896
+
1897
+ *Preconditions:* `T` is *Cpp17EmplaceConstructible* into `hive` from
1898
+ `args`.
1899
+
1900
+ *Effects:* Inserts an object of type `T` constructed with
1901
+ `std::forward<Args>(args)...`. The `hint` parameter is ignored. If an
1902
+ exception is thrown, there are no effects.
1903
+
1904
+ [*Note 1*: `args` can directly or indirectly refer to a value in
1905
+ `*this`. — *end note*]
1906
+
1907
+ *Returns:* An iterator that points to the new element.
1908
+
1909
+ *Complexity:* Constant. Exactly one object of type `T` is constructed.
1910
+
1911
+ *Remarks:* Invalidates the past-the-end iterator.
1912
+
1913
+ ``` cpp
1914
+ iterator insert(const T& x);
1915
+ iterator insert(const_iterator hint, const T& x);
1916
+ iterator insert(T&& x);
1917
+ iterator insert(const_iterator hint, T&& x);
1918
+ ```
1919
+
1920
+ *Effects:* Equivalent to:
1921
+ `return emplace(std::forward<decltype(x)>(x));`
1922
+
1923
+ [*Note 2*: The `hint` parameter is ignored. — *end note*]
1924
+
1925
+ ``` cpp
1926
+ void insert(initializer_list<T> rg);
1927
+ template<container-compatible-range<T> R>
1928
+ void insert_range(R&& rg);
1929
+ ```
1930
+
1931
+ *Preconditions:* `T` is *Cpp17EmplaceInsertable* into `hive` from
1932
+ `*ranges::begin(rg)`. `rg` and `*this` do not overlap.
1933
+
1934
+ *Effects:* Inserts copies of elements in `rg`. Each iterator in the
1935
+ range `rg` is dereferenced exactly once.
1936
+
1937
+ *Complexity:* Linear in the number of elements inserted. Exactly one
1938
+ object of type `T` is constructed for each element inserted.
1939
+
1940
+ *Remarks:* If an element is inserted, invalidates the past-the-end
1941
+ iterator.
1942
+
1943
+ ``` cpp
1944
+ void insert(size_type n, const T& x);
1945
+ ```
1946
+
1947
+ *Preconditions:* `T` is *Cpp17CopyInsertable* into `hive`.
1948
+
1949
+ *Effects:* Inserts `n` copies of `x`.
1950
+
1951
+ *Complexity:* Linear in `n`. Exactly one object of type `T` is
1952
+ constructed for each element inserted.
1953
+
1954
+ *Remarks:* If an element is inserted, invalidates the past-the-end
1955
+ iterator.
1956
+
1957
+ ``` cpp
1958
+ template<class InputIterator>
1959
+ void insert(InputIterator first, InputIterator last);
1960
+ ```
1961
+
1962
+ *Effects:* Equivalent to `insert_range(ranges::subrange(first, last))`.
1963
+
1964
+ ``` cpp
1965
+ iterator erase(const_iterator position);
1966
+ iterator erase(const_iterator first, const_iterator last);
1967
+ ```
1968
+
1969
+ *Complexity:* Linear in the number of elements erased. Additionally, if
1970
+ any active blocks become empty of elements as a result of the function
1971
+ call, at worst linear in the number of element blocks.
1972
+
1973
+ *Remarks:* Invalidates references, pointers and iterators referring to
1974
+ the erased elements. An erase operation that erases the last element in
1975
+ `*this` also invalidates the past-the-end iterator.
1976
+
1977
+ ``` cpp
1978
+ void swap(hive& x)
1979
+ noexcept(allocator_traits<Allocator>::propagate_on_container_swap::value ||
1980
+ allocator_traits<Allocator>::is_always_equal::value);
1981
+ ```
1982
+
1983
+ *Effects:* Exchanges the contents, `capacity()`, and *current-limits* of
1984
+ `*this` with that of `x`.
1985
+
1986
+ *Complexity:* Constant.
1987
+
1988
+ #### Operations <a id="hive.operations">[[hive.operations]]</a>
1989
+
1990
+ In this subclause, arguments for a template parameter named `Predicate`
1991
+ or `BinaryPredicate` shall meet the corresponding requirements in
1992
+ [[algorithms.requirements]]. The semantics of `i + n` and `i - n`, where
1993
+ `i` is an iterator into the `hive` and `n` is an integer, are the same
1994
+ as those of `next(i, n)` and `prev(i, n)`, respectively. For `sort`, the
1995
+ definitions and requirements in [[alg.sorting]] apply.
1996
+
1997
+ ``` cpp
1998
+ void splice(hive& x);
1999
+ void splice(hive&& x);
2000
+ ```
2001
+
2002
+ *Preconditions:* `get_allocator() == x.get_allocator()` is `true`.
2003
+
2004
+ *Effects:* If `addressof(x) == this` is `true`, the behavior is
2005
+ erroneous and there are no effects. Otherwise, inserts the contents of
2006
+ `x` into `*this` and `x` becomes empty. Pointers and references to the
2007
+ moved elements of `x` now refer to those same elements but as members of
2008
+ `*this`. Iterators referring to the moved elements continue to refer to
2009
+ their elements, but they now behave as iterators into `*this`, not into
2010
+ `x`.
2011
+
2012
+ *Throws:* `length_error` if any of `x`’s active blocks are not within
2013
+ the bounds of *current-limits*.
2014
+
2015
+ *Complexity:* Linear in the sum of all element blocks in `x` plus all
2016
+ element blocks in `*this`.
2017
+
2018
+ *Remarks:* Reserved blocks in `x` are not transferred into `*this`. If
2019
+ `addressof(x) == this` is `false`, invalidates the past-the-end iterator
2020
+ for both `x` and `*this`.
2021
+
2022
+ ``` cpp
2023
+ template<class BinaryPredicate = equal_to<T>>
2024
+ size_type unique(BinaryPredicate binary_pred = BinaryPredicate());
2025
+ ```
2026
+
2027
+ *Preconditions:* `binary_pred` is an equivalence relation.
2028
+
2029
+ *Effects:* Erases all but the first element from every consecutive group
2030
+ of equivalent elements. That is, for a nonempty `hive`, erases all
2031
+ elements referred to by the iterator `i` in the range \[`begin() + 1`,
2032
+ `end()`) for which `binary_pred(*i, *(i - 1))` is `true`.
2033
+
2034
+ *Returns:* The number of elements erased.
2035
+
2036
+ *Throws:* Nothing unless an exception is thrown by the predicate.
2037
+
2038
+ *Complexity:* If `empty()` is `false`, exactly `size() - 1` applications
2039
+ of the corresponding predicate, otherwise no applications of the
2040
+ predicate.
2041
+
2042
+ *Remarks:* Invalidates references, pointers, and iterators referring to
2043
+ the erased elements. If the last element in `*this` is erased, also
2044
+ invalidates the past-the-end iterator.
2045
+
2046
+ ``` cpp
2047
+ template<class Compare = less<T>>
2048
+ void sort(Compare comp = Compare());
2049
+ ```
2050
+
2051
+ *Preconditions:* `T` is *Cpp17MoveInsertable* into `hive`,
2052
+ *Cpp17MoveAssignable*, and *Cpp17Swappable*.
2053
+
2054
+ *Effects:* Sorts `*this` according to the `comp` function object. If an
2055
+ exception is thrown, the order of the elements in `*this` is
2056
+ unspecified.
2057
+
2058
+ *Complexity:* 𝑂(N log N) comparisons, where N is `size()`.
2059
+
2060
+ *Remarks:* May allocate. References, pointers, and iterators referring
2061
+ to elements in `*this`, as well as the past-the-end iterator, may be
2062
+ invalidated.
2063
+
2064
+ [*Note 1*: Not required to be
2065
+ stable [[algorithm.stable]]. — *end note*]
2066
+
2067
+ ``` cpp
2068
+ iterator get_iterator(const_pointer p) noexcept;
2069
+ const_iterator get_iterator(const_pointer p) const noexcept;
2070
+ ```
2071
+
2072
+ *Preconditions:* `p` points to an element in `*this`.
2073
+
2074
+ *Returns:* An `iterator` or `const_iterator` pointing to the same
2075
+ element as `p`.
2076
+
2077
+ *Complexity:* Linear in the number of active blocks in `*this`.
2078
+
2079
+ #### Erasure <a id="hive.erasure">[[hive.erasure]]</a>
2080
+
2081
+ ``` cpp
2082
+ template<class T, class Allocator, class U = T>
2083
+ typename hive<T, Allocator>::size_type
2084
+ erase(hive<T, Allocator>& c, const U& value);
2085
+ ```
2086
+
2087
+ *Effects:* Equivalent to:
2088
+
2089
+ ``` cpp
2090
+ return erase_if(c, [&](const auto& elem) -> bool { return elem == value; });
2091
+ ```
2092
+
2093
+ ``` cpp
2094
+ template<class T, class Allocator, class Predicate>
2095
+ typename hive<T, Allocator>::size_type
2096
+ erase_if(hive<T, Allocator>& c, Predicate pred);
2097
+ ```
2098
+
2099
+ *Effects:* Equivalent to:
2100
+
2101
+ ``` cpp
2102
+ auto original_size = c.size();
2103
+ for (auto i = c.begin(), last = c.end(); i != last; ) {
2104
+ if (pred(*i)) {
2105
+ i = c.erase(i);
2106
+ } else {
2107
+ ++i;
2108
+ }
2109
+ }
2110
+ return original_size - c.size();
2111
+ ```
2112
+
2113
+ ### Header `<list>` synopsis <a id="list.syn">[[list.syn]]</a>
2114
+
2115
+ ``` cpp
2116
+ #include <compare> // see [compare.syn]
2117
+ #include <initializer_list> // see [initializer.list.syn]
2118
+
2119
+ namespace std {
2120
+ // [list], class template list
2121
+ template<class T, class Allocator = allocator<T>> class list;
2122
+
2123
+ template<class T, class Allocator>
2124
+ constexpr bool operator==(const list<T, Allocator>& x, const list<T, Allocator>& y);
2125
+ template<class T, class Allocator>
2126
+ constexpr synth-three-way-result<T>
2127
+ operator<=>(const list<T, Allocator>& x, const list<T, Allocator>& y);
2128
+
2129
+ template<class T, class Allocator>
2130
+ constexpr void swap(list<T, Allocator>& x, list<T, Allocator>& y)
2131
+ noexcept(noexcept(x.swap(y)));
2132
+
2133
+ // [list.erasure], erasure
2134
+ template<class T, class Allocator, class U = T>
2135
+ constexpr typename list<T, Allocator>::size_type
2136
+ erase(list<T, Allocator>& c, const U& value);
2137
+ template<class T, class Allocator, class Predicate>
2138
+ constexpr typename list<T, Allocator>::size_type
2139
+ erase_if(list<T, Allocator>& c, Predicate pred);
2140
+
2141
+ namespace pmr {
2142
+ template<class T>
2143
+ using list = std::list<T, polymorphic_allocator<T>>;
2144
+ }
2145
+ }
2146
+ ```
2147
+
2148
  ### Class template `list` <a id="list">[[list]]</a>
2149
 
2150
  #### Overview <a id="list.overview">[[list.overview]]</a>
2151
 
2152
  A `list` is a sequence container that supports bidirectional iterators
 
2165
 
2166
  Descriptions are provided here only for operations on `list` that are
2167
  not described in one of these tables or for operations where there is
2168
  additional semantic information.
2169
 
2170
+ The types `iterator` and `const_iterator` meet the constexpr iterator
2171
+ requirements [[iterator.requirements.general]].
2172
+
2173
  ``` cpp
2174
  namespace std {
2175
  template<class T, class Allocator = allocator<T>>
2176
  class list {
2177
  public:
2178
  // types
2179
  using value_type = T;
2180
  using allocator_type = Allocator;
2181
+ using pointer = allocator_traits<Allocator>::pointer;
2182
+ using const_pointer = allocator_traits<Allocator>::const_pointer;
2183
  using reference = value_type&;
2184
  using const_reference = const value_type&;
2185
  using size_type = implementation-defined // type of list::size_type; // see [container.requirements]
2186
  using difference_type = implementation-defined // type of list::difference_type; // see [container.requirements]
2187
  using iterator = implementation-defined // type of list::iterator; // see [container.requirements]
2188
  using const_iterator = implementation-defined // type of list::const_iterator; // see [container.requirements]
2189
  using reverse_iterator = std::reverse_iterator<iterator>;
2190
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
2191
 
2192
  // [list.cons], construct/copy/destroy
2193
+ constexpr list() : list(Allocator()) { }
2194
+ constexpr explicit list(const Allocator&);
2195
+ constexpr explicit list(size_type n, const Allocator& = Allocator());
2196
+ constexpr list(size_type n, const T& value, const Allocator& = Allocator());
2197
  template<class InputIterator>
2198
+ constexpr list(InputIterator first, InputIterator last, const Allocator& = Allocator());
2199
  template<container-compatible-range<T> R>
2200
+ constexpr list(from_range_t, R&& rg, const Allocator& = Allocator());
2201
+ constexpr list(const list& x);
2202
+ constexpr list(list&& x);
2203
+ constexpr list(const list&, const type_identity_t<Allocator>&);
2204
+ constexpr list(list&&, const type_identity_t<Allocator>&);
2205
+ constexpr list(initializer_list<T>, const Allocator& = Allocator());
2206
+ constexpr ~list();
2207
+ constexpr list& operator=(const list& x);
2208
+ constexpr list& operator=(list&& x)
2209
  noexcept(allocator_traits<Allocator>::is_always_equal::value);
2210
+ constexpr list& operator=(initializer_list<T>);
2211
  template<class InputIterator>
2212
+ constexpr void assign(InputIterator first, InputIterator last);
2213
  template<container-compatible-range<T> R>
2214
+ constexpr void assign_range(R&& rg);
2215
+ constexpr void assign(size_type n, const T& t);
2216
+ constexpr void assign(initializer_list<T>);
2217
+ constexpr allocator_type get_allocator() const noexcept;
2218
 
2219
  // iterators
2220
+ constexpr iterator begin() noexcept;
2221
+ constexpr const_iterator begin() const noexcept;
2222
+ constexpr iterator end() noexcept;
2223
+ constexpr const_iterator end() const noexcept;
2224
+ constexpr reverse_iterator rbegin() noexcept;
2225
+ constexpr const_reverse_iterator rbegin() const noexcept;
2226
+ constexpr reverse_iterator rend() noexcept;
2227
+ constexpr const_reverse_iterator rend() const noexcept;
2228
 
2229
+ constexpr const_iterator cbegin() const noexcept;
2230
+ constexpr const_iterator cend() const noexcept;
2231
+ constexpr const_reverse_iterator crbegin() const noexcept;
2232
+ constexpr const_reverse_iterator crend() const noexcept;
2233
 
2234
  // [list.capacity], capacity
2235
+ constexpr bool empty() const noexcept;
2236
+ constexpr size_type size() const noexcept;
2237
+ constexpr size_type max_size() const noexcept;
2238
+ constexpr void resize(size_type sz);
2239
+ constexpr void resize(size_type sz, const T& c);
2240
 
2241
  // element access
2242
+ constexpr reference front();
2243
+ constexpr const_reference front() const;
2244
+ constexpr reference back();
2245
+ constexpr const_reference back() const;
2246
 
2247
  // [list.modifiers], modifiers
2248
+ template<class... Args> constexpr reference emplace_front(Args&&... args);
2249
+ template<class... Args> constexpr reference emplace_back(Args&&... args);
2250
+ constexpr void push_front(const T& x);
2251
+ constexpr void push_front(T&& x);
2252
  template<container-compatible-range<T> R>
2253
+ constexpr void prepend_range(R&& rg);
2254
+ constexpr void pop_front();
2255
+ constexpr void push_back(const T& x);
2256
+ constexpr void push_back(T&& x);
2257
  template<container-compatible-range<T> R>
2258
+ constexpr void append_range(R&& rg);
2259
+ constexpr void pop_back();
2260
 
2261
+ template<class... Args> constexpr iterator emplace(const_iterator position, Args&&... args);
2262
+ constexpr iterator insert(const_iterator position, const T& x);
2263
+ constexpr iterator insert(const_iterator position, T&& x);
2264
+ constexpr iterator insert(const_iterator position, size_type n, const T& x);
2265
  template<class InputIterator>
2266
+ constexpr iterator insert(const_iterator position,
2267
+ InputIterator first, InputIterator last);
2268
  template<container-compatible-range<T> R>
2269
+ constexpr iterator insert_range(const_iterator position, R&& rg);
2270
+ constexpr iterator insert(const_iterator position, initializer_list<T> il);
2271
 
2272
+ constexpr iterator erase(const_iterator position);
2273
+ constexpr iterator erase(const_iterator position, const_iterator last);
2274
+ constexpr void swap(list&) noexcept(allocator_traits<Allocator>::is_always_equal::value);
2275
+ constexpr void clear() noexcept;
2276
 
2277
  // [list.ops], list operations
2278
+ constexpr void splice(const_iterator position, list& x);
2279
+ constexpr void splice(const_iterator position, list&& x);
2280
+ constexpr void splice(const_iterator position, list& x, const_iterator i);
2281
+ constexpr void splice(const_iterator position, list&& x, const_iterator i);
2282
+ constexpr void splice(const_iterator position, list& x,
2283
+ const_iterator first, const_iterator last);
2284
+ constexpr void splice(const_iterator position, list&& x,
2285
+ const_iterator first, const_iterator last);
2286
 
2287
+ constexpr size_type remove(const T& value);
2288
+ template<class Predicate> constexpr size_type remove_if(Predicate pred);
2289
 
2290
+ constexpr size_type unique();
2291
  template<class BinaryPredicate>
2292
+ constexpr size_type unique(BinaryPredicate binary_pred);
2293
 
2294
+ constexpr void merge(list& x);
2295
+ constexpr void merge(list&& x);
2296
+ template<class Compare> constexpr void merge(list& x, Compare comp);
2297
+ template<class Compare> constexpr void merge(list&& x, Compare comp);
2298
 
2299
+ constexpr void sort();
2300
+ template<class Compare> constexpr void sort(Compare comp);
2301
 
2302
+ constexpr void reverse() noexcept;
2303
  };
2304
 
2305
  template<class InputIterator, class Allocator = allocator<iter-value-type<InputIterator>>>
2306
  list(InputIterator, InputIterator, Allocator = Allocator())
2307
  -> list<iter-value-type<InputIterator>, Allocator>;
 
2318
  any member of the resulting specialization of `list` is referenced.
2319
 
2320
  #### Constructors, copy, and assignment <a id="list.cons">[[list.cons]]</a>
2321
 
2322
  ``` cpp
2323
+ constexpr explicit list(const Allocator&);
2324
  ```
2325
 
2326
  *Effects:* Constructs an empty list, using the specified allocator.
2327
 
2328
  *Complexity:* Constant.
2329
 
2330
  ``` cpp
2331
+ constexpr explicit list(size_type n, const Allocator& = Allocator());
2332
  ```
2333
 
2334
+ *Preconditions:* `T` is *Cpp17DefaultInsertable* into `list`.
2335
 
2336
  *Effects:* Constructs a `list` with `n` default-inserted elements using
2337
  the specified allocator.
2338
 
2339
  *Complexity:* Linear in `n`.
2340
 
2341
  ``` cpp
2342
+ constexpr list(size_type n, const T& value, const Allocator& = Allocator());
2343
  ```
2344
 
2345
+ *Preconditions:* `T` is *Cpp17CopyInsertable* into `list`.
2346
 
2347
  *Effects:* Constructs a `list` with `n` copies of `value`, using the
2348
  specified allocator.
2349
 
2350
  *Complexity:* Linear in `n`.
2351
 
2352
  ``` cpp
2353
  template<class InputIterator>
2354
+ constexpr list(InputIterator first, InputIterator last, const Allocator& = Allocator());
2355
  ```
2356
 
2357
  *Effects:* Constructs a `list` equal to the range \[`first`, `last`).
2358
 
2359
  *Complexity:* Linear in `distance(first, last)`.
2360
 
2361
  ``` cpp
2362
  template<container-compatible-range<T> R>
2363
+ constexpr list(from_range_t, R&& rg, const Allocator& = Allocator());
2364
  ```
2365
 
2366
  *Effects:* Constructs a `list` object with the elements of the range
2367
  `rg`.
2368
 
2369
  *Complexity:* Linear in `ranges::distance(rg)`.
2370
 
2371
  #### Capacity <a id="list.capacity">[[list.capacity]]</a>
2372
 
2373
  ``` cpp
2374
+ constexpr void resize(size_type sz);
2375
  ```
2376
 
2377
+ *Preconditions:* `T` is *Cpp17DefaultInsertable* into `list`.
2378
 
2379
  *Effects:* If `size() < sz`, appends `sz - size()` default-inserted
2380
  elements to the sequence. If `sz <= size()`, equivalent to:
2381
 
2382
  ``` cpp
 
2384
  advance(it, sz);
2385
  erase(it, end());
2386
  ```
2387
 
2388
  ``` cpp
2389
+ constexpr void resize(size_type sz, const T& c);
2390
  ```
2391
 
2392
+ *Preconditions:* `T` is *Cpp17CopyInsertable* into `list`.
2393
 
2394
  *Effects:* As if by:
2395
 
2396
  ``` cpp
2397
  if (sz > size())
 
2406
  ```
2407
 
2408
  #### Modifiers <a id="list.modifiers">[[list.modifiers]]</a>
2409
 
2410
  ``` cpp
2411
+ constexpr iterator insert(const_iterator position, const T& x);
2412
+ constexpr iterator insert(const_iterator position, T&& x);
2413
+ constexpr iterator insert(const_iterator position, size_type n, const T& x);
2414
  template<class InputIterator>
2415
+ constexpr iterator insert(const_iterator position,
2416
+ InputIterator first, InputIterator last);
2417
  template<container-compatible-range<T> R>
2418
+ constexpr iterator insert_range(const_iterator position, R&& rg);
2419
+ constexpr iterator insert(const_iterator position, initializer_list<T>);
2420
 
2421
+ template<class... Args> constexpr reference emplace_front(Args&&... args);
2422
+ template<class... Args> constexpr reference emplace_back(Args&&... args);
2423
+ template<class... Args> constexpr iterator emplace(const_iterator position, Args&&... args);
2424
+ constexpr void push_front(const T& x);
2425
+ constexpr void push_front(T&& x);
2426
  template<container-compatible-range<T> R>
2427
+ constexpr void prepend_range(R&& rg);
2428
+ constexpr void push_back(const T& x);
2429
+ constexpr void push_back(T&& x);
2430
  template<container-compatible-range<T> R>
2431
+ constexpr void append_range(R&& rg);
2432
  ```
2433
 
2434
  *Complexity:* Insertion of a single element into a list takes constant
2435
  time and exactly one call to a constructor of `T`. Insertion of multiple
2436
  elements into a list is linear in the number of elements inserted, and
2437
  the number of calls to the copy constructor or move constructor of `T`
2438
  is exactly equal to the number of elements inserted.
2439
 
2440
  *Remarks:* Does not affect the validity of iterators and references. If
2441
+ an exception is thrown, there are no effects.
2442
 
2443
  ``` cpp
2444
+ constexpr iterator erase(const_iterator position);
2445
+ constexpr iterator erase(const_iterator first, const_iterator last);
2446
+ constexpr void pop_front();
2447
+ constexpr void pop_back();
2448
+ constexpr void clear() noexcept;
 
2449
  ```
2450
 
2451
  *Effects:* Invalidates only the iterators and references to the erased
2452
  elements.
2453
 
 
2474
  from one list to another. The behavior of splice operations is undefined
2475
  if `get_allocator() !=
2476
  x.get_allocator()`.
2477
 
2478
  ``` cpp
2479
+ constexpr void splice(const_iterator position, list& x);
2480
+ constexpr void splice(const_iterator position, list&& x);
2481
  ```
2482
 
2483
  *Preconditions:* `addressof(x) != this` is `true`.
2484
 
2485
  *Effects:* Inserts the contents of `x` before `position` and `x` becomes
 
2491
  *Throws:* Nothing.
2492
 
2493
  *Complexity:* Constant time.
2494
 
2495
  ``` cpp
2496
+ constexpr void splice(const_iterator position, list& x, const_iterator i);
2497
+ constexpr void splice(const_iterator position, list&& x, const_iterator i);
2498
  ```
2499
 
2500
  *Preconditions:* `i` is a valid dereferenceable iterator of `x`.
2501
 
2502
  *Effects:* Inserts an element pointed to by `i` from list `x` before
 
2509
  *Throws:* Nothing.
2510
 
2511
  *Complexity:* Constant time.
2512
 
2513
  ``` cpp
2514
+ constexpr void splice(const_iterator position, list& x,
2515
+ const_iterator first, const_iterator last);
2516
+ constexpr void splice(const_iterator position, list&& x,
2517
+ const_iterator first, const_iterator last);
2518
  ```
2519
 
2520
+ *Preconditions:* \[`first`, `last`) is a valid range in `x`. `position`
2521
+ is not an iterator in the range \[`first`, `last`).
2522
 
2523
  *Effects:* Inserts elements in the range \[`first`, `last`) before
2524
  `position` and removes the elements from `x`. Pointers and references to
2525
  the moved elements of `x` now refer to those same elements but as
2526
  members of `*this`. Iterators referring to the moved elements will
 
2531
 
2532
  *Complexity:* Constant time if `addressof(x) == this`; otherwise, linear
2533
  time.
2534
 
2535
  ``` cpp
2536
+ constexpr size_type remove(const T& value);
2537
+ template<class Predicate> constexpr size_type remove_if(Predicate pred);
2538
  ```
2539
 
2540
  *Effects:* Erases all the elements in the list referred to by a list
2541
  iterator `i` for which the following conditions hold: `*i == value`,
2542
  `pred(*i) != false`. Invalidates only the iterators and references to
 
2551
  predicate.
2552
 
2553
  *Remarks:* Stable [[algorithm.stable]].
2554
 
2555
  ``` cpp
2556
+ constexpr size_type unique();
2557
+ template<class BinaryPredicate> constexpr size_type unique(BinaryPredicate binary_pred);
2558
  ```
2559
 
2560
  Let `binary_pred` be `equal_to<>{}` for the first overload.
2561
 
2562
  *Preconditions:* `binary_pred` is an equivalence relation.
 
2574
  *Complexity:* If `empty()` is `false`, exactly `size() - 1` applications
2575
  of the corresponding predicate, otherwise no applications of the
2576
  predicate.
2577
 
2578
  ``` cpp
2579
+ constexpr void merge(list& x);
2580
+ constexpr void merge(list&& x);
2581
+ template<class Compare> constexpr void merge(list& x, Compare comp);
2582
+ template<class Compare> constexpr void merge(list&& x, Compare comp);
2583
  ```
2584
 
2585
  Let `comp` be `less<>` for the first two overloads.
2586
 
2587
  *Preconditions:* `*this` and `x` are both sorted with respect to the
 
2598
  *Complexity:* At most `size() + x.size() - 1` comparisons if
2599
  `addressof(x) != this`; otherwise, no comparisons are performed.
2600
 
2601
  *Remarks:* Stable [[algorithm.stable]]. If `addressof(x) != this`, `x`
2602
  is empty after the merge. No elements are copied by this operation. If
2603
+ an exception is thrown other than by a comparison, there are no effects.
2604
 
2605
  ``` cpp
2606
+ constexpr void reverse() noexcept;
2607
  ```
2608
 
2609
  *Effects:* Reverses the order of the elements in the list. Does not
2610
  affect the validity of iterators and references.
2611
 
 
2619
  *Effects:* Sorts the list according to the `operator<` or a `Compare`
2620
  function object. If an exception is thrown, the order of the elements in
2621
  `*this` is unspecified. Does not affect the validity of iterators and
2622
  references.
2623
 
2624
+ *Complexity:* Approximately N log N comparisons, where N is `size()`.
2625
 
2626
  *Remarks:* Stable [[algorithm.stable]].
2627
 
2628
  #### Erasure <a id="list.erasure">[[list.erasure]]</a>
2629
 
2630
  ``` cpp
2631
+ template<class T, class Allocator, class U = T>
2632
  typename list<T, Allocator>::size_type
2633
+ constexpr erase(list<T, Allocator>& c, const U& value);
2634
  ```
2635
 
2636
  *Effects:* Equivalent to:
2637
+
2638
+ ``` cpp
2639
+ return erase_if(c, [&](const auto& elem) -> bool { return elem == value; });
2640
+ ```
2641
 
2642
  ``` cpp
2643
  template<class T, class Allocator, class Predicate>
2644
  typename list<T, Allocator>::size_type
2645
+ constexpr erase_if(list<T, Allocator>& c, Predicate pred);
2646
  ```
2647
 
2648
  *Effects:* Equivalent to: `return c.remove_if(pred);`
2649
 
2650
+ ### Header `<vector>` synopsis <a id="vector.syn">[[vector.syn]]</a>
2651
+
2652
+ ``` cpp
2653
+ #include <compare> // see [compare.syn]
2654
+ #include <initializer_list> // see [initializer.list.syn]
2655
+
2656
+ namespace std {
2657
+ // [vector], class template vector
2658
+ template<class T, class Allocator = allocator<T>> class vector;
2659
+
2660
+ template<class T, class Allocator>
2661
+ constexpr bool operator==(const vector<T, Allocator>& x, const vector<T, Allocator>& y);
2662
+ template<class T, class Allocator>
2663
+ constexpr synth-three-way-result<T>
2664
+ operator<=>(const vector<T, Allocator>& x, const vector<T, Allocator>& y);
2665
+
2666
+ template<class T, class Allocator>
2667
+ constexpr void swap(vector<T, Allocator>& x, vector<T, Allocator>& y)
2668
+ noexcept(noexcept(x.swap(y)));
2669
+
2670
+ // [vector.erasure], erasure
2671
+ template<class T, class Allocator, class U = T>
2672
+ constexpr typename vector<T, Allocator>::size_type
2673
+ erase(vector<T, Allocator>& c, const U& value);
2674
+ template<class T, class Allocator, class Predicate>
2675
+ constexpr typename vector<T, Allocator>::size_type
2676
+ erase_if(vector<T, Allocator>& c, Predicate pred);
2677
+
2678
+ namespace pmr {
2679
+ template<class T>
2680
+ using vector = std::vector<T, polymorphic_allocator<T>>;
2681
+ }
2682
+
2683
+ // [vector.bool], specialization of vector for bool
2684
+ // [vector.bool.pspc], partial class template specialization vector<bool, Allocator>
2685
+ template<class Allocator>
2686
+ class vector<bool, Allocator>;
2687
+
2688
+ template<class T>
2689
+ constexpr bool is-vector-bool-reference = see below; // exposition only
2690
+
2691
+ // hash support
2692
+ template<class T> struct hash;
2693
+ template<class Allocator> struct hash<vector<bool, Allocator>>;
2694
+
2695
+ // [vector.bool.fmt], formatter specialization for vector<bool>
2696
+ template<class T, class charT> requires is-vector-bool-reference<T>
2697
+ struct formatter<T, charT>;
2698
+ }
2699
+ ```
2700
+
2701
  ### Class template `vector` <a id="vector">[[vector]]</a>
2702
 
2703
  #### Overview <a id="vector.overview">[[vector.overview]]</a>
2704
 
2705
  A `vector` is a sequence container that supports (amortized) constant
 
2728
  class vector {
2729
  public:
2730
  // types
2731
  using value_type = T;
2732
  using allocator_type = Allocator;
2733
+ using pointer = allocator_traits<Allocator>::pointer;
2734
+ using const_pointer = allocator_traits<Allocator>::const_pointer;
2735
  using reference = value_type&;
2736
  using const_reference = const value_type&;
2737
  using size_type = implementation-defined // type of vector::size_type; // see [container.requirements]
2738
  using difference_type = implementation-defined // type of vector::difference_type; // see [container.requirements]
2739
  using iterator = implementation-defined // type of vector::iterator; // see [container.requirements]
 
2783
  constexpr const_iterator cend() const noexcept;
2784
  constexpr const_reverse_iterator crbegin() const noexcept;
2785
  constexpr const_reverse_iterator crend() const noexcept;
2786
 
2787
  // [vector.capacity], capacity
2788
+ constexpr bool empty() const noexcept;
2789
  constexpr size_type size() const noexcept;
2790
  constexpr size_type max_size() const noexcept;
2791
  constexpr size_type capacity() const noexcept;
2792
  constexpr void resize(size_type sz);
2793
  constexpr void resize(size_type sz, const T& c);
 
2795
  constexpr void shrink_to_fit();
2796
 
2797
  // element access
2798
  constexpr reference operator[](size_type n);
2799
  constexpr const_reference operator[](size_type n) const;
 
2800
  constexpr reference at(size_type n);
2801
+ constexpr const_reference at(size_type n) const;
2802
  constexpr reference front();
2803
  constexpr const_reference front() const;
2804
  constexpr reference back();
2805
  constexpr const_reference back() const;
2806
 
 
2861
 
2862
  ``` cpp
2863
  constexpr explicit vector(size_type n, const Allocator& = Allocator());
2864
  ```
2865
 
2866
+ *Preconditions:* `T` is *Cpp17DefaultInsertable* into `vector`.
2867
 
2868
  *Effects:* Constructs a `vector` with `n` default-inserted elements
2869
  using the specified allocator.
2870
 
2871
  *Complexity:* Linear in `n`.
 
2873
  ``` cpp
2874
  constexpr vector(size_type n, const T& value,
2875
  const Allocator& = Allocator());
2876
  ```
2877
 
2878
+ *Preconditions:* `T` is *Cpp17CopyInsertable* into `vector`.
2879
 
2880
  *Effects:* Constructs a `vector` with `n` copies of `value`, using the
2881
  specified allocator.
2882
 
2883
  *Complexity:* Linear in `n`.
 
2891
  *Effects:* Constructs a `vector` equal to the range \[`first`, `last`),
2892
  using the specified allocator.
2893
 
2894
  *Complexity:* Makes only N calls to the copy constructor of `T` (where N
2895
  is the distance between `first` and `last`) and no reallocations if
2896
+ `InputIterator` meets the *Cpp17ForwardIterator* requirements. It makes
2897
+ order N calls to the copy constructor of `T` and order log N
2898
+ reallocations if they are just input iterators.
2899
 
2900
  ``` cpp
2901
  template<container-compatible-range<T> R>
2902
  constexpr vector(from_range_t, R&& rg, const Allocator& = Allocator());
2903
  ```
 
2905
  *Effects:* Constructs a `vector` object with the elements of the range
2906
  `rg`, using the specified allocator.
2907
 
2908
  *Complexity:* Initializes exactly N elements from the results of
2909
  dereferencing successive iterators of `rg`, where N is
2910
+ `ranges::distance(rg)`.
2911
+
2912
+ Performs no reallocations if:
2913
+
2914
+ - `R` models `ranges::approximately_sized_range`, and
2915
+ `ranges::distance(rg) <= ranges::reserve_hint(rg)` is `true`, or
2916
+ - `R` models `ranges::forward_range` and `R` does not model
2917
+ `ranges::approximately_sized_range`.
2918
+
2919
+ Otherwise, performs order log N reallocations and order N calls to the
2920
+ copy or move constructor of `T`.
2921
 
2922
  #### Capacity <a id="vector.capacity">[[vector.capacity]]</a>
2923
 
2924
  ``` cpp
2925
  constexpr size_type capacity() const noexcept;
 
2932
 
2933
  ``` cpp
2934
  constexpr void reserve(size_type n);
2935
  ```
2936
 
2937
+ *Preconditions:* `T` is *Cpp17MoveInsertable* into `vector`.
2938
 
2939
  *Effects:* A directive that informs a `vector` of a planned change in
2940
  size, so that it can manage the storage allocation accordingly. After
2941
  `reserve()`, `capacity()` is greater or equal to the argument of
2942
  `reserve` if reallocation happens; and equal to the previous value of
 
2945
  exception is thrown other than by the move constructor of a
2946
  non-*Cpp17CopyInsertable* type, there are no effects.
2947
 
2948
  *Throws:* `length_error` if `n > max_size()`.[^4]
2949
 
2950
+ *Complexity:* Linear in the size of the sequence.
 
2951
 
2952
+ *Remarks:* The size of the sequence is not changed. Reallocation
2953
+ invalidates all the references, pointers, and iterators referring to the
2954
+ elements in the sequence, as well as the past-the-end iterator.
2955
 
2956
  [*Note 1*: If no reallocation happens, they remain
2957
  valid. — *end note*]
2958
 
2959
  No reallocation shall take place during insertions that happen after a
 
2962
 
2963
  ``` cpp
2964
  constexpr void shrink_to_fit();
2965
  ```
2966
 
2967
+ *Preconditions:* `T` is *Cpp17MoveInsertable* into `vector`.
2968
 
2969
  *Effects:* `shrink_to_fit` is a non-binding request to reduce
2970
  `capacity()` to `size()`.
2971
 
2972
  [*Note 2*: The request is non-binding to allow latitude for
2973
  implementation-specific optimizations. — *end note*]
2974
 
2975
  It does not increase `capacity()`, but may reduce `capacity()` by
2976
  causing reallocation. If an exception is thrown other than by the move
2977
+ constructor of a non-*Cpp17CopyInsertable* `T`, there are no effects.
2978
 
2979
  *Complexity:* If reallocation happens, linear in the size of the
2980
  sequence.
2981
 
2982
  *Remarks:* Reallocation invalidates all the references, pointers, and
 
3000
  ``` cpp
3001
  constexpr void resize(size_type sz);
3002
  ```
3003
 
3004
  *Preconditions:* `T` is *Cpp17MoveInsertable* and
3005
+ *Cpp17DefaultInsertable* into `vector`.
3006
 
3007
  *Effects:* If `sz < size()`, erases the last `size() - sz` elements from
3008
  the sequence. Otherwise, appends `sz - size()` default-inserted elements
3009
  to the sequence.
3010
 
3011
  *Remarks:* If an exception is thrown other than by the move constructor
3012
+ of a non-*Cpp17CopyInsertable* `T`, there are no effects.
3013
 
3014
  ``` cpp
3015
  constexpr void resize(size_type sz, const T& c);
3016
  ```
3017
 
3018
+ *Preconditions:* `T` is *Cpp17CopyInsertable* into `vector`.
3019
 
3020
  *Effects:* If `sz < size()`, erases the last `size() - sz` elements from
3021
  the sequence. Otherwise, appends `sz - size()` copies of `c` to the
3022
  sequence.
3023
 
3024
+ *Remarks:* If an exception is thrown, there are no effects.
3025
 
3026
  #### Data <a id="vector.data">[[vector.data]]</a>
3027
 
3028
  ``` cpp
3029
  constexpr T* data() noexcept;
3030
  constexpr const T* data() const noexcept;
3031
  ```
3032
 
3033
  *Returns:* A pointer such that \[`data()`, `data() + size()`) is a valid
3034
+ range. For a non-empty vector, `data() == addressof(front())` is `true`.
3035
 
3036
  *Complexity:* Constant time.
3037
 
3038
  #### Modifiers <a id="vector.modifiers">[[vector.modifiers]]</a>
3039
 
 
3065
  past-the-end iterator. If no reallocation happens, then references,
3066
  pointers, and iterators before the insertion point remain valid but
3067
  those at or after the insertion point, including the past-the-end
3068
  iterator, are invalidated. If an exception is thrown other than by the
3069
  copy constructor, move constructor, assignment operator, or move
3070
+ assignment operator of `T` or by any `InputIterator` operation, there
3071
+ are no effects. If an exception is thrown while inserting a single
3072
+ element at the end and `T` is *Cpp17CopyInsertable* or
3073
  `is_nothrow_move_constructible_v<T>` is `true`, there are no effects.
3074
  Otherwise, if an exception is thrown by the move constructor of a
3075
  non-*Cpp17CopyInsertable* `T`, the effects are unspecified.
3076
 
3077
+ For the declarations taking a range `R`, performs at most one
3078
+ reallocation if:
3079
+
3080
+ - `R` models `ranges::approximately_sized_range` and
3081
+ `ranges::distance(rg) <= ranges::reserve_hint(rg)` is `true`, or
3082
+ - `R` models `ranges::forward_range` and `R` does not model
3083
+ `ranges::approximately_sized_range`.
3084
+
3085
+ For the declarations taking a pair of `InputIterator`, performs at most
3086
+ one reallocation if `InputIterator` meets the *Cpp17ForwardIterator*
3087
+ requirements.
3088
+
3089
  ``` cpp
3090
  constexpr iterator erase(const_iterator position);
3091
  constexpr iterator erase(const_iterator first, const_iterator last);
3092
  constexpr void pop_back();
3093
  ```
 
3104
  vector after the erased elements.
3105
 
3106
  #### Erasure <a id="vector.erasure">[[vector.erasure]]</a>
3107
 
3108
  ``` cpp
3109
+ template<class T, class Allocator, class U = T>
3110
  constexpr typename vector<T, Allocator>::size_type
3111
  erase(vector<T, Allocator>& c, const U& value);
3112
  ```
3113
 
3114
  *Effects:* Equivalent to:
 
3160
  using reverse_iterator = std::reverse_iterator<iterator>;
3161
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
3162
 
3163
  // bit reference
3164
  class reference {
 
 
 
3165
  public:
3166
  constexpr reference(const reference&) = default;
3167
  constexpr ~reference();
3168
  constexpr operator bool() const noexcept;
3169
  constexpr reference& operator=(bool x) noexcept;
 
3214
  constexpr const_iterator cend() const noexcept;
3215
  constexpr const_reverse_iterator crbegin() const noexcept;
3216
  constexpr const_reverse_iterator crend() const noexcept;
3217
 
3218
  // capacity
3219
+ constexpr bool empty() const noexcept;
3220
  constexpr size_type size() const noexcept;
3221
  constexpr size_type max_size() const noexcept;
3222
  constexpr size_type capacity() const noexcept;
3223
  constexpr void resize(size_type sz, bool c = false);
3224
  constexpr void reserve(size_type n);
3225
  constexpr void shrink_to_fit();
3226
 
3227
  // element access
3228
  constexpr reference operator[](size_type n);
3229
  constexpr const_reference operator[](size_type n) const;
 
3230
  constexpr reference at(size_type n);
3231
+ constexpr const_reference at(size_type n) const;
3232
  constexpr reference front();
3233
  constexpr const_reference front() const;
3234
  constexpr reference back();
3235
  constexpr const_reference back() const;
3236
 
 
3261
  };
3262
  }
3263
  ```
3264
 
3265
  Unless described below, all operations have the same requirements and
3266
+ semantics as the `vector` primary template, except that operations
3267
  dealing with the `bool` value type map to bit values in the container
3268
  storage and `allocator_traits::construct` [[allocator.traits.members]]
3269
  is not used to construct these values.
3270
 
3271
  There is no requirement that the data be stored as a contiguous
 
3349
  format(const T& ref, FormatContext& ctx) const;
3350
  ```
3351
 
3352
  Equivalent to: `return `*`underlying_`*`.format(ref, ctx);`
3353
 
3354
+ ### Header `<inplace_vector>` synopsis <a id="inplace.vector.syn">[[inplace.vector.syn]]</a>
3355
+
3356
+ ``` cpp
3357
+ // mostly freestanding
3358
+ #include <compare> // see [compare.syn]
3359
+ #include <initializer_list> // see [initializer.list.syn]
3360
+
3361
+ namespace std {
3362
+ // [inplace.vector], class template inplace_vector
3363
+ template<class T, size_t N> class inplace_vector; // partially freestanding
3364
+
3365
+ // [inplace.vector.erasure], erasure
3366
+ template<class T, size_t N, class U = T>
3367
+ constexpr typename inplace_vector<T, N>::size_type
3368
+ erase(inplace_vector<T, N>& c, const U& value);
3369
+ template<class T, size_t N, class Predicate>
3370
+ constexpr typename inplace_vector<T, N>::size_type
3371
+ erase_if(inplace_vector<T, N>& c, Predicate pred);
3372
+ }
3373
+ ```
3374
+
3375
+ ### Class template `inplace_vector` <a id="inplace.vector">[[inplace.vector]]</a>
3376
+
3377
+ #### Overview <a id="inplace.vector.overview">[[inplace.vector.overview]]</a>
3378
+
3379
+ An `inplace_vector` is a contiguous container. Its capacity is fixed and
3380
+ its elements are stored within the `inplace_vector` object itself.
3381
+
3382
+ An `inplace_vector` meets all of the requirements of a container
3383
+ [[container.reqmts]], of a reversible container
3384
+ [[container.rev.reqmts]], of a contiguous container, and of a sequence
3385
+ container, including most of the optional sequence container
3386
+ requirements [[sequence.reqmts]]. The exceptions are the `push_front`,
3387
+ `prepend_range`, `pop_front`, and `emplace_front` member functions,
3388
+ which are not provided. Descriptions are provided here only for
3389
+ operations on `inplace_vector` that are not described in one of these
3390
+ tables or for operations where there is additional semantic information.
3391
+
3392
+ For any `N`, `inplace_vector<T, N>::iterator` and
3393
+ `inplace_vector<T, N>::const_iterator` meet the constexpr iterator
3394
+ requirements.
3395
+
3396
+ Any member function of `inplace_vector<T, N>` that would cause the size
3397
+ to exceed `N` throws an exception of type `bad_alloc`.
3398
+
3399
+ Let `IV` denote a specialization of `inplace_vector<T, N>`. If `N` is
3400
+ zero, then `IV` is trivially copyable and empty, and
3401
+ `std::is_trivially_default_constructible_v<IV>` is `true`. Otherwise:
3402
+
3403
+ - If `is_trivially_copy_constructible_v<T>` is `true`, then `IV` has a
3404
+ trivial copy constructor.
3405
+ - If `is_trivially_move_constructible_v<T>` is `true`, then `IV` has a
3406
+ trivial move constructor.
3407
+ - If `is_trivially_destructible_v<T>` is `true`, then:
3408
+ - `IV` has a trivial destructor.
3409
+ - If
3410
+ ``` cpp
3411
+ is_trivially_copy_constructible_v<T> && is_trivially_copy_assignable_v<T>
3412
+ ```
3413
+
3414
+ is `true`, then `IV` has a trivial copy assignment operator.
3415
+ - If
3416
+ ``` cpp
3417
+ is_trivially_move_constructible_v<T> && is_trivially_move_assignable_v<T>
3418
+ ```
3419
+
3420
+ is `true`, then `IV` has a trivial move assignment operator.
3421
+
3422
+ ``` cpp
3423
+ namespace std {
3424
+ template<class T, size_t N>
3425
+ class inplace_vector {
3426
+ public:
3427
+ // types:
3428
+ using value_type = T;
3429
+ using pointer = T*;
3430
+ using const_pointer = const T*;
3431
+ using reference = value_type&;
3432
+ using const_reference = const value_type&;
3433
+ using size_type = size_t;
3434
+ using difference_type = ptrdiff_t;
3435
+ using iterator = implementation-defined // type of inplace_vector::iterator; // see [container.requirements]
3436
+ using const_iterator = implementation-defined // type of inplace_vector::const_iterator; // see [container.requirements]
3437
+ using reverse_iterator = std::reverse_iterator<iterator>;
3438
+ using const_reverse_iterator = std::reverse_iterator<const_iterator>;
3439
+
3440
+ // [inplace.vector.cons], construct/copy/destroy
3441
+ constexpr inplace_vector() noexcept;
3442
+ constexpr explicit inplace_vector(size_type n); // freestanding-deleted
3443
+ constexpr inplace_vector(size_type n, const T& value); // freestanding-deleted
3444
+ template<class InputIterator>
3445
+ constexpr inplace_vector(InputIterator first, InputIterator last); // freestanding-deleted
3446
+ template<container-compatible-range<T> R>
3447
+ constexpr inplace_vector(from_range_t, R&& rg); // freestanding-deleted
3448
+ constexpr inplace_vector(const inplace_vector&);
3449
+ constexpr inplace_vector(inplace_vector&&)
3450
+ noexcept(N == 0 || is_nothrow_move_constructible_v<T>);
3451
+ constexpr inplace_vector(initializer_list<T> il); // freestanding-deleted
3452
+ constexpr ~inplace_vector();
3453
+ constexpr inplace_vector& operator=(const inplace_vector& other);
3454
+ constexpr inplace_vector& operator=(inplace_vector&& other)
3455
+ noexcept(N == 0 || (is_nothrow_move_assignable_v<T> &&
3456
+ is_nothrow_move_constructible_v<T>));
3457
+ constexpr inplace_vector& operator=(initializer_list<T>); // freestanding-deleted
3458
+ template<class InputIterator>
3459
+ constexpr void assign(InputIterator first, InputIterator last); // freestanding-deleted
3460
+ template<container-compatible-range<T> R>
3461
+ constexpr void assign_range(R&& rg); // freestanding-deleted
3462
+ constexpr void assign(size_type n, const T& u); // freestanding-deleted
3463
+ constexpr void assign(initializer_list<T> il); // freestanding-deleted
3464
+
3465
+ // iterators
3466
+ constexpr iterator begin() noexcept;
3467
+ constexpr const_iterator begin() const noexcept;
3468
+ constexpr iterator end() noexcept;
3469
+ constexpr const_iterator end() const noexcept;
3470
+ constexpr reverse_iterator rbegin() noexcept;
3471
+ constexpr const_reverse_iterator rbegin() const noexcept;
3472
+ constexpr reverse_iterator rend() noexcept;
3473
+ constexpr const_reverse_iterator rend() const noexcept;
3474
+
3475
+ constexpr const_iterator cbegin() const noexcept;
3476
+ constexpr const_iterator cend() const noexcept;
3477
+ constexpr const_reverse_iterator crbegin() const noexcept;
3478
+ constexpr const_reverse_iterator crend() const noexcept;
3479
+
3480
+ // [inplace.vector.capacity], capacity
3481
+ constexpr bool empty() const noexcept;
3482
+ constexpr size_type size() const noexcept;
3483
+ static constexpr size_type max_size() noexcept;
3484
+ static constexpr size_type capacity() noexcept;
3485
+ constexpr void resize(size_type sz); // freestanding-deleted
3486
+ constexpr void resize(size_type sz, const T& c); // freestanding-deleted
3487
+ static constexpr void reserve(size_type n); // freestanding-deleted
3488
+ static constexpr void shrink_to_fit() noexcept;
3489
+
3490
+ // element access
3491
+ constexpr reference operator[](size_type n);
3492
+ constexpr const_reference operator[](size_type n) const;
3493
+ constexpr reference at(size_type n); // freestanding-deleted
3494
+ constexpr const_reference at(size_type n) const; // freestanding-deleted
3495
+ constexpr reference front();
3496
+ constexpr const_reference front() const;
3497
+ constexpr reference back();
3498
+ constexpr const_reference back() const;
3499
+
3500
+ // [inplace.vector.data], data access
3501
+ constexpr T* data() noexcept;
3502
+ constexpr const T* data() const noexcept;
3503
+
3504
+ // [inplace.vector.modifiers], modifiers
3505
+ template<class... Args>
3506
+ constexpr reference emplace_back(Args&&... args); // freestanding-deleted
3507
+ constexpr reference push_back(const T& x); // freestanding-deleted
3508
+ constexpr reference push_back(T&& x); // freestanding-deleted
3509
+ template<container-compatible-range<T> R>
3510
+ constexpr void append_range(R&& rg); // freestanding-deleted
3511
+ constexpr void pop_back();
3512
+
3513
+ template<class... Args>
3514
+ constexpr pointer try_emplace_back(Args&&... args);
3515
+ constexpr pointer try_push_back(const T& x);
3516
+ constexpr pointer try_push_back(T&& x);
3517
+ template<container-compatible-range<T> R>
3518
+ constexpr ranges::borrowed_iterator_t<R> try_append_range(R&& rg);
3519
+
3520
+ template<class... Args>
3521
+ constexpr reference unchecked_emplace_back(Args&&... args);
3522
+ constexpr reference unchecked_push_back(const T& x);
3523
+ constexpr reference unchecked_push_back(T&& x);
3524
+
3525
+ template<class... Args>
3526
+ constexpr iterator emplace(const_iterator position, Args&&... args); // freestanding-deleted
3527
+ constexpr iterator insert(const_iterator position, const T& x); // freestanding-deleted
3528
+ constexpr iterator insert(const_iterator position, T&& x); // freestanding-deleted
3529
+ constexpr iterator insert(const_iterator position, size_type n, // freestanding-deleted
3530
+ const T& x);
3531
+ template<class InputIterator>
3532
+ constexpr iterator insert(const_iterator position, // freestanding-deleted
3533
+ InputIterator first, InputIterator last);
3534
+ template<container-compatible-range<T> R>
3535
+ constexpr iterator insert_range(const_iterator position, R&& rg); // freestanding-deleted
3536
+ constexpr iterator insert(const_iterator position, // freestanding-deleted
3537
+ initializer_list<T> il);
3538
+ constexpr iterator erase(const_iterator position);
3539
+ constexpr iterator erase(const_iterator first, const_iterator last);
3540
+ constexpr void swap(inplace_vector& x)
3541
+ noexcept(N == 0 || (is_nothrow_swappable_v<T> &&
3542
+ is_nothrow_move_constructible_v<T>));
3543
+ constexpr void clear() noexcept;
3544
+
3545
+ friend constexpr bool operator==(const inplace_vector& x,
3546
+ const inplace_vector& y);
3547
+ friend constexpr synth-three-way-result<T>
3548
+ operator<=>(const inplace_vector& x, const inplace_vector& y);
3549
+ friend constexpr void swap(inplace_vector& x, inplace_vector& y)
3550
+ noexcept(N == 0 || (is_nothrow_swappable_v<T> &&
3551
+ is_nothrow_move_constructible_v<T>))
3552
+ { x.swap(y); }
3553
+ };
3554
+ }
3555
+ ```
3556
+
3557
+ #### Constructors <a id="inplace.vector.cons">[[inplace.vector.cons]]</a>
3558
+
3559
+ ``` cpp
3560
+ constexpr explicit inplace_vector(size_type n);
3561
+ ```
3562
+
3563
+ *Preconditions:* `T` is *Cpp17DefaultInsertable* into `inplace_vector`.
3564
+
3565
+ *Effects:* Constructs an `inplace_vector` with `n` default-inserted
3566
+ elements.
3567
+
3568
+ *Complexity:* Linear in `n`.
3569
+
3570
+ ``` cpp
3571
+ constexpr inplace_vector(size_type n, const T& value);
3572
+ ```
3573
+
3574
+ *Preconditions:* `T` is *Cpp17CopyInsertable* into `inplace_vector`.
3575
+
3576
+ *Effects:* Constructs an `inplace_vector` with `n` copies of `value`.
3577
+
3578
+ *Complexity:* Linear in `n`.
3579
+
3580
+ ``` cpp
3581
+ template<class InputIterator>
3582
+ constexpr inplace_vector(InputIterator first, InputIterator last);
3583
+ ```
3584
+
3585
+ *Effects:* Constructs an `inplace_vector` equal to the range \[`first`,
3586
+ `last`).
3587
+
3588
+ *Complexity:* Linear in `distance(first, last)`.
3589
+
3590
+ ``` cpp
3591
+ template<container-compatible-range<T> R>
3592
+ constexpr inplace_vector(from_range_t, R&& rg);
3593
+ ```
3594
+
3595
+ *Effects:* Constructs an `inplace_vector` with the elements of the range
3596
+ `rg`.
3597
+
3598
+ *Complexity:* Linear in `ranges::distance(rg)`.
3599
+
3600
+ #### Capacity <a id="inplace.vector.capacity">[[inplace.vector.capacity]]</a>
3601
+
3602
+ ``` cpp
3603
+ static constexpr size_type capacity() noexcept;
3604
+ static constexpr size_type max_size() noexcept;
3605
+ ```
3606
+
3607
+ *Returns:* `N`.
3608
+
3609
+ ``` cpp
3610
+ constexpr void resize(size_type sz);
3611
+ ```
3612
+
3613
+ *Preconditions:* `T` is *Cpp17DefaultInsertable* into `inplace_vector`.
3614
+
3615
+ *Effects:* If `sz < size()`, erases the last `size() - sz` elements from
3616
+ the sequence. Otherwise, appends `sz - size()` default-inserted elements
3617
+ to the sequence.
3618
+
3619
+ *Remarks:* If an exception is thrown, there are no effects on `*this`.
3620
+
3621
+ ``` cpp
3622
+ constexpr void resize(size_type sz, const T& c);
3623
+ ```
3624
+
3625
+ *Preconditions:* `T` is *Cpp17CopyInsertable* into `inplace_vector`.
3626
+
3627
+ *Effects:* If `sz < size()`, erases the last `size() - sz` elements from
3628
+ the sequence. Otherwise, appends `sz - size()` copies of `c` to the
3629
+ sequence.
3630
+
3631
+ *Remarks:* If an exception is thrown, there are no effects on `*this`.
3632
+
3633
+ ``` cpp
3634
+ static constexpr void reserve(size_type n);
3635
+ ```
3636
+
3637
+ *Effects:* None.
3638
+
3639
+ *Throws:* `bad_alloc` if `n > capacity()` is `true`.
3640
+
3641
+ ``` cpp
3642
+ static constexpr void shrink_to_fit() noexcept;
3643
+ ```
3644
+
3645
+ *Effects:* None.
3646
+
3647
+ #### Data <a id="inplace.vector.data">[[inplace.vector.data]]</a>
3648
+
3649
+ ``` cpp
3650
+ constexpr T* data() noexcept;
3651
+ constexpr const T* data() const noexcept;
3652
+ ```
3653
+
3654
+ *Returns:* A pointer such that \[`data()`, `data() + size()`) is a valid
3655
+ range. For a non-empty `inplace_vector`, `data() == addressof(front())`
3656
+ is `true`.
3657
+
3658
+ *Complexity:* Constant time.
3659
+
3660
+ #### Modifiers <a id="inplace.vector.modifiers">[[inplace.vector.modifiers]]</a>
3661
+
3662
+ ``` cpp
3663
+ constexpr iterator insert(const_iterator position, const T& x);
3664
+ constexpr iterator insert(const_iterator position, T&& x);
3665
+ constexpr iterator insert(const_iterator position, size_type n, const T& x);
3666
+ template<class InputIterator>
3667
+ constexpr iterator insert(const_iterator position, InputIterator first, InputIterator last);
3668
+ template<container-compatible-range<T> R>
3669
+ constexpr iterator insert_range(const_iterator position, R&& rg);
3670
+ constexpr iterator insert(const_iterator position, initializer_list<T> il);
3671
+
3672
+ template<class... Args>
3673
+ constexpr iterator emplace(const_iterator position, Args&&... args);
3674
+ template<container-compatible-range<T> R>
3675
+ constexpr void append_range(R&& rg);
3676
+ ```
3677
+
3678
+ Let n be the value of `size()` before this call for the `append_range`
3679
+ overload, and `distance(begin, position)` otherwise.
3680
+
3681
+ *Complexity:* Linear in the number of elements inserted plus the
3682
+ distance to the end of the vector.
3683
+
3684
+ *Remarks:* If an exception is thrown other than by the copy constructor,
3685
+ move constructor, assignment operator, or move assignment operator of
3686
+ `T` or by any `InputIterator` operation, there are no effects.
3687
+ Otherwise, if an exception is thrown, then `size()` ≥ n and elements in
3688
+ the range `begin() + ``[``0, `n`)` are not modified.
3689
+
3690
+ ``` cpp
3691
+ constexpr reference push_back(const T& x);
3692
+ constexpr reference push_back(T&& x);
3693
+ template<class... Args>
3694
+ constexpr reference emplace_back(Args&&... args);
3695
+ ```
3696
+
3697
+ *Returns:* `back()`.
3698
+
3699
+ *Throws:* `bad_alloc` or any exception thrown by the initialization of
3700
+ the inserted element.
3701
+
3702
+ *Complexity:* Constant.
3703
+
3704
+ *Remarks:* If an exception is thrown, there are no effects on `*this`.
3705
+
3706
+ ``` cpp
3707
+ template<class... Args>
3708
+ constexpr pointer try_emplace_back(Args&&... args);
3709
+ constexpr pointer try_push_back(const T& x);
3710
+ constexpr pointer try_push_back(T&& x);
3711
+ ```
3712
+
3713
+ Let `vals` denote a pack:
3714
+
3715
+ - `std::forward<Args>(args)...` for the first overload,
3716
+ - `x` for the second overload,
3717
+ - `std::move(x)` for the third overload.
3718
+
3719
+ *Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into
3720
+ `inplace_vector` from `vals...`.
3721
+
3722
+ *Effects:* If `size() < capacity()` is `true`, appends an object of type
3723
+ `T` direct-non-list-initialized with `vals...`. Otherwise, there are no
3724
+ effects.
3725
+
3726
+ *Returns:* `nullptr` if `size() == capacity()` is `true`, otherwise
3727
+ `addressof(back())`.
3728
+
3729
+ *Throws:* Nothing unless an exception is thrown by the initialization of
3730
+ the inserted element.
3731
+
3732
+ *Complexity:* Constant.
3733
+
3734
+ *Remarks:* If an exception is thrown, there are no effects on `*this`.
3735
+
3736
+ ``` cpp
3737
+ template<container-compatible-range<T> R>
3738
+ constexpr ranges::borrowed_iterator_t<R> try_append_range(R&& rg);
3739
+ ```
3740
+
3741
+ *Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into
3742
+ `inplace_vector` from
3743
+ `*ranges::begin(rg)`.
3744
+
3745
+ *Effects:* Appends copies of initial elements in `rg` before `end()`,
3746
+ until all elements are inserted or `size() == capacity()` is `true`.
3747
+ Each iterator in the range `rg` is dereferenced at most once.
3748
+
3749
+ *Returns:* The first iterator in the range `ranges::begin(rg)`+\[0, `n`)
3750
+ that was not inserted into `*this`, where `n` is the number of elements
3751
+ in `rg`.
3752
+
3753
+ *Complexity:* Linear in the number of elements inserted.
3754
+
3755
+ *Remarks:* Let n be the value of `size()` prior to this call. If an
3756
+ exception is thrown after the insertion of k elements, then `size()`
3757
+ equals n + k, elements in the range `begin() + ``[``0, `n`)` are not
3758
+ modified, and elements in the range `begin() + ``[`n`, `n + k`)`
3759
+ correspond to the inserted elements.
3760
+
3761
+ ``` cpp
3762
+ template<class... Args>
3763
+ constexpr reference unchecked_emplace_back(Args&&... args);
3764
+ ```
3765
+
3766
+ *Preconditions:* `size() < capacity()` is `true`.
3767
+
3768
+ *Effects:* Equivalent to:
3769
+ `return *try_emplace_back(std::forward<Args>(args)...);`
3770
+
3771
+ ``` cpp
3772
+ constexpr reference unchecked_push_back(const T& x);
3773
+ constexpr reference unchecked_push_back(T&& x);
3774
+ ```
3775
+
3776
+ *Preconditions:* `size() < capacity()` is `true`.
3777
+
3778
+ *Effects:* Equivalent to:
3779
+ `return *try_push_back(std::forward<decltype(x)>(x));`
3780
+
3781
+ ``` cpp
3782
+ constexpr iterator erase(const_iterator position);
3783
+ constexpr iterator erase(const_iterator first, const_iterator last);
3784
+ constexpr void pop_back();
3785
+ ```
3786
+
3787
+ *Effects:* Invalidates iterators and references at or after the point of
3788
+ the erase.
3789
+
3790
+ *Throws:* Nothing unless an exception is thrown by the assignment
3791
+ operator or move assignment operator of `T`.
3792
+
3793
+ *Complexity:* The destructor of `T` is called the number of times equal
3794
+ to the number of the elements erased, but the assignment operator of `T`
3795
+ is called the number of times equal to the number of elements after the
3796
+ erased elements.
3797
+
3798
+ #### Erasure <a id="inplace.vector.erasure">[[inplace.vector.erasure]]</a>
3799
+
3800
+ ``` cpp
3801
+ template<class T, size_t N, class U = T>
3802
+ constexpr size_t erase(inplace_vector<T, N>& c, const U& value);
3803
+ ```
3804
+
3805
+ *Effects:* Equivalent to:
3806
+
3807
+ ``` cpp
3808
+ auto it = remove(c.begin(), c.end(), value);
3809
+ auto r = distance(it, c.end());
3810
+ c.erase(it, c.end());
3811
+ return r;
3812
+ ```
3813
+
3814
+ ``` cpp
3815
+ template<class T, size_t N, class Predicate>
3816
+ constexpr size_t erase_if(inplace_vector<T, N>& c, Predicate pred);
3817
+ ```
3818
+
3819
+ *Effects:* Equivalent to:
3820
+
3821
+ ``` cpp
3822
+ auto it = remove_if(c.begin(), c.end(), pred);
3823
+ auto r = distance(it, c.end());
3824
+ c.erase(it, c.end());
3825
+ return r;
3826
+ ```
3827
+