From Jason Turner

[sequences]

Diff to HTML by rtfpessoa

Files changed (1) hide show
  1. tmp/tmpuemfgmkt/{from.md → to.md} +467 -247
tmp/tmpuemfgmkt/{from.md → to.md} RENAMED
@@ -76,10 +76,11 @@ namespace std {
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
  template<class T, class Allocator, class U>
82
  typename deque<T, Allocator>::size_type
83
  erase(deque<T, Allocator>& c, const U& value);
84
  template<class T, class Allocator, class Predicate>
85
  typename deque<T, Allocator>::size_type
@@ -97,11 +98,11 @@ namespace std {
97
  ``` cpp
98
  #include <compare> // see [compare.syn]
99
  #include <initializer_list> // see [initializer.list.syn]
100
 
101
  namespace std {
102
- // [forwardlist], class template forward_list
103
  template<class T, class Allocator = allocator<T>> class forward_list;
104
 
105
  template<class T, class Allocator>
106
  bool operator==(const forward_list<T, Allocator>& x, const forward_list<T, Allocator>& y);
107
  template<class T, class Allocator>
@@ -110,10 +111,11 @@ namespace std {
110
 
111
  template<class T, class Allocator>
112
  void swap(forward_list<T, Allocator>& x, forward_list<T, Allocator>& y)
113
  noexcept(noexcept(x.swap(y)));
114
 
 
115
  template<class T, class Allocator, class U>
116
  typename forward_list<T, Allocator>::size_type
117
  erase(forward_list<T, Allocator>& c, const U& value);
118
  template<class T, class Allocator, class Predicate>
119
  typename forward_list<T, Allocator>::size_type
@@ -144,10 +146,11 @@ namespace std {
144
 
145
  template<class T, class Allocator>
146
  void swap(list<T, Allocator>& x, list<T, Allocator>& y)
147
  noexcept(noexcept(x.swap(y)));
148
 
 
149
  template<class T, class Allocator, class U>
150
  typename list<T, Allocator>::size_type
151
  erase(list<T, Allocator>& c, const U& value);
152
  template<class T, class Allocator, class Predicate>
153
  typename list<T, Allocator>::size_type
@@ -178,52 +181,62 @@ namespace std {
178
 
179
  template<class T, class Allocator>
180
  constexpr void swap(vector<T, Allocator>& x, vector<T, Allocator>& y)
181
  noexcept(noexcept(x.swap(y)));
182
 
 
183
  template<class T, class Allocator, class U>
184
  constexpr typename vector<T, Allocator>::size_type
185
  erase(vector<T, Allocator>& c, const U& value);
186
  template<class T, class Allocator, class Predicate>
187
  constexpr typename vector<T, Allocator>::size_type
188
  erase_if(vector<T, Allocator>& c, Predicate pred);
189
 
190
- // [vector.bool], class vector<bool>
191
- template<class Allocator> class vector<bool, Allocator>;
 
 
 
 
 
 
 
 
 
 
192
 
193
  // hash support
194
  template<class T> struct hash;
195
  template<class Allocator> struct hash<vector<bool, Allocator>>;
196
 
197
- namespace pmr {
198
- template<class T>
199
- using vector = std::vector<T, polymorphic_allocator<T>>;
200
- }
201
  }
202
  ```
203
 
204
  ### Class template `array` <a id="array">[[array]]</a>
205
 
206
  #### Overview <a id="array.overview">[[array.overview]]</a>
207
 
208
  The header `<array>` defines a class template for storing fixed-size
209
  sequences of objects. An `array` is a contiguous container
210
- [[container.requirements.general]]. An instance of `array<T, N>` stores
211
- `N` elements of type `T`, so that `size() == N` is an invariant.
212
 
213
  An `array` is an aggregate [[dcl.init.aggr]] that can be
214
  list-initialized with up to `N` elements whose types are convertible to
215
  `T`.
216
 
217
- An `array` meets all of the requirements of a container and of a
218
- reversible container [[container.requirements]], except that a default
219
- constructed `array` object is not empty and that `swap` does not have
220
- constant complexity. An `array` meets some of the requirements of a
221
- sequence container [[sequence.reqmts]]. Descriptions are provided here
222
- only for operations on `array` that are not described in one of these
223
- tables and for operations where there is additional semantic
224
- information.
225
 
226
  `array<T, N>` is a structural type [[temp.param]] if `T` is a structural
227
  type. Two values `a1` and `a2` of type `array<T, N>` are
228
  template-argument-equivalent [[temp.type]] if and only if each pair of
229
  corresponding elements in `a1` and `a2` are
@@ -295,17 +308,17 @@ namespace std {
295
  ```
296
 
297
  #### Constructors, copy, and assignment <a id="array.cons">[[array.cons]]</a>
298
 
299
  The conditions for an aggregate [[dcl.init.aggr]] shall be met. Class
300
- `array` relies on the implicitly-declared special member functions (
301
- [[class.default.ctor]], [[class.dtor]], and [[class.copy.ctor]]) to
302
- conform to the container requirements table in 
303
- [[container.requirements]]. In addition to the requirements specified in
304
- the container requirements table, the implicit move constructor and move
305
- assignment operator for `array` require that `T` be
306
- *Cpp17MoveConstructible* or *Cpp17MoveAssignable*, respectively.
307
 
308
  ``` cpp
309
  template<class T, class... U>
310
  array(T, U...) -> array<T, 1 + sizeof...(U)>;
311
  ```
@@ -339,11 +352,11 @@ constexpr void swap(array& y) noexcept(is_nothrow_swappable_v<T>);
339
  ```
340
 
341
  *Effects:* Equivalent to `swap_ranges(begin(), end(), y.begin())`.
342
 
343
  [*Note 1*: Unlike the `swap` function for other containers,
344
- `array::swap` takes linear time, may exit via an exception, and does not
345
  cause iterators to become associated with the other
346
  container. — *end note*]
347
 
348
  #### Specialized algorithms <a id="array.special">[[array.special]]</a>
349
 
@@ -438,17 +451,18 @@ A `deque` is a sequence container that supports random access iterators
438
  insert and erase operations at the beginning or the end; insert and
439
  erase in the middle take linear time. That is, a deque is especially
440
  optimized for pushing and popping elements at the beginning and end.
441
  Storage management is handled automatically.
442
 
443
- A `deque` meets all of the requirements of a container, of a reversible
444
- container (given in tables in  [[container.requirements]]), of a
445
- sequence container, including the optional sequence container
446
- requirements [[sequence.reqmts]], and of an allocator-aware container (
447
- [[container.alloc.req]]). Descriptions are provided here only for
448
- operations on `deque` that are not described in one of these tables or
449
- for operations where there is additional semantic information.
 
450
 
451
  ``` cpp
452
  namespace std {
453
  template<class T, class Allocator = allocator<T>>
454
  class deque {
@@ -458,12 +472,12 @@ namespace std {
458
  using allocator_type = Allocator;
459
  using pointer = typename allocator_traits<Allocator>::pointer;
460
  using const_pointer = typename allocator_traits<Allocator>::const_pointer;
461
  using reference = value_type&;
462
  using const_reference = const value_type&;
463
- using size_type = implementation-defined; // see [container.requirements]
464
- using difference_type = implementation-defined; // see [container.requirements]
465
  using iterator = implementation-defined // type of deque::iterator; // see [container.requirements]
466
  using const_iterator = implementation-defined // type of deque::const_iterator; // see [container.requirements]
467
  using reverse_iterator = std::reverse_iterator<iterator>;
468
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
469
 
@@ -472,23 +486,27 @@ namespace std {
472
  explicit deque(const Allocator&);
473
  explicit deque(size_type n, const Allocator& = Allocator());
474
  deque(size_type n, const T& value, const Allocator& = Allocator());
475
  template<class InputIterator>
476
  deque(InputIterator first, InputIterator last, const Allocator& = Allocator());
 
 
477
  deque(const deque& x);
478
  deque(deque&&);
479
- deque(const deque&, const Allocator&);
480
- deque(deque&&, const Allocator&);
481
  deque(initializer_list<T>, const Allocator& = Allocator());
482
 
483
  ~deque();
484
  deque& operator=(const deque& x);
485
  deque& operator=(deque&& x)
486
  noexcept(allocator_traits<Allocator>::is_always_equal::value);
487
  deque& operator=(initializer_list<T>);
488
  template<class InputIterator>
489
  void assign(InputIterator first, InputIterator last);
 
 
490
  void assign(size_type n, const T& t);
491
  void assign(initializer_list<T>);
492
  allocator_type get_allocator() const noexcept;
493
 
494
  // iterators
@@ -529,18 +547,24 @@ namespace std {
529
  template<class... Args> reference emplace_back(Args&&... args);
530
  template<class... Args> iterator emplace(const_iterator position, Args&&... args);
531
 
532
  void push_front(const T& x);
533
  void push_front(T&& x);
 
 
534
  void push_back(const T& x);
535
  void push_back(T&& x);
 
 
536
 
537
  iterator insert(const_iterator position, const T& x);
538
  iterator insert(const_iterator position, T&& x);
539
  iterator insert(const_iterator position, size_type n, const T& x);
540
  template<class InputIterator>
541
  iterator insert(const_iterator position, InputIterator first, InputIterator last);
 
 
542
  iterator insert(const_iterator position, initializer_list<T>);
543
 
544
  void pop_front();
545
  void pop_back();
546
 
@@ -553,14 +577,13 @@ namespace std {
553
 
554
  template<class InputIterator, class Allocator = allocator<iter-value-type<InputIterator>>>
555
  deque(InputIterator, InputIterator, Allocator = Allocator())
556
  -> deque<iter-value-type<InputIterator>, Allocator>;
557
 
558
- // swap
559
- template<class T, class Allocator>
560
- void swap(deque<T, Allocator>& x, deque<T, Allocator>& y)
561
- noexcept(noexcept(x.swap(y)));
562
  }
563
  ```
564
 
565
  #### Constructors, copy, and assignment <a id="deque.cons">[[deque.cons]]</a>
566
 
@@ -574,26 +597,26 @@ explicit deque(const Allocator&);
574
 
575
  ``` cpp
576
  explicit deque(size_type n, const Allocator& = Allocator());
577
  ```
578
 
 
 
579
  *Effects:* Constructs a `deque` with `n` default-inserted elements using
580
  the specified allocator.
581
 
582
- *Preconditions:* `T` is *Cpp17DefaultInsertable* into `*this`.
583
-
584
  *Complexity:* Linear in `n`.
585
 
586
  ``` cpp
587
  deque(size_type n, const T& value, const Allocator& = Allocator());
588
  ```
589
 
 
 
590
  *Effects:* Constructs a `deque` with `n` copies of `value`, using the
591
  specified allocator.
592
 
593
- *Preconditions:* `T` is *Cpp17CopyInsertable* into `*this`.
594
-
595
  *Complexity:* Linear in `n`.
596
 
597
  ``` cpp
598
  template<class InputIterator>
599
  deque(InputIterator first, InputIterator last, const Allocator& = Allocator());
@@ -602,10 +625,20 @@ template<class InputIterator>
602
  *Effects:* Constructs a `deque` equal to the range \[`first`, `last`),
603
  using the specified allocator.
604
 
605
  *Complexity:* Linear in `distance(first, last)`.
606
 
 
 
 
 
 
 
 
 
 
 
607
  #### Capacity <a id="deque.capacity">[[deque.capacity]]</a>
608
 
609
  ``` cpp
610
  void resize(size_type sz);
611
  ```
@@ -657,39 +690,45 @@ iterator insert(const_iterator position, const T& x);
657
  iterator insert(const_iterator position, T&& x);
658
  iterator insert(const_iterator position, size_type n, const T& x);
659
  template<class InputIterator>
660
  iterator insert(const_iterator position,
661
  InputIterator first, InputIterator last);
 
 
662
  iterator insert(const_iterator position, initializer_list<T>);
663
 
664
  template<class... Args> reference emplace_front(Args&&... args);
665
  template<class... Args> reference emplace_back(Args&&... args);
666
  template<class... Args> iterator emplace(const_iterator position, Args&&... args);
667
  void push_front(const T& x);
668
  void push_front(T&& x);
 
 
669
  void push_back(const T& x);
670
  void push_back(T&& x);
 
 
671
  ```
672
 
673
  *Effects:* An insertion in the middle of the deque invalidates all the
674
  iterators and references to elements of the deque. An insertion at
675
  either end of the deque invalidates all the iterators to the deque, but
676
  has no effect on the validity of references to elements of the deque.
677
 
 
 
 
 
 
 
678
  *Remarks:* If an exception is thrown other than by the copy constructor,
679
  move constructor, assignment operator, or move assignment operator of
680
  `T` there are no effects. If an exception is thrown while inserting a
681
  single element at either end, there are no effects. Otherwise, if an
682
  exception is thrown by the move constructor of a
683
  non-*Cpp17CopyInsertable* `T`, the effects are unspecified.
684
 
685
- *Complexity:* The complexity is linear in the number of elements
686
- inserted plus the lesser of the distances to the beginning and end of
687
- the deque. Inserting a single element at either the beginning or end of
688
- a deque always takes constant time and causes a single call to a
689
- constructor of `T`.
690
-
691
  ``` cpp
692
  iterator erase(const_iterator position);
693
  iterator erase(const_iterator first, const_iterator last);
694
  void pop_front();
695
  void pop_back();
@@ -705,19 +744,19 @@ invalidates the past-the-end iterator and all iterators and references
705
  to all the elements of the deque.
706
 
707
  [*Note 1*: `pop_front` and `pop_back` are erase
708
  operations. — *end note*]
709
 
 
 
 
710
  *Complexity:* The number of calls to the destructor of `T` is the same
711
  as the number of elements erased, but the number of calls to the
712
  assignment operator of `T` is no more than the lesser of the number of
713
  elements before the erased elements and the number of elements after the
714
  erased elements.
715
 
716
- *Throws:* Nothing unless an exception is thrown by the assignment
717
- operator of `T`.
718
-
719
  #### Erasure <a id="deque.erasure">[[deque.erasure]]</a>
720
 
721
  ``` cpp
722
  template<class T, class Allocator, class U>
723
  typename deque<T, Allocator>::size_type
@@ -746,39 +785,38 @@ auto it = remove_if(c.begin(), c.end(), pred);
746
  auto r = distance(it, c.end());
747
  c.erase(it, c.end());
748
  return r;
749
  ```
750
 
751
- ### Class template `forward_list` <a id="forwardlist">[[forwardlist]]</a>
752
 
753
- #### Overview <a id="forwardlist.overview">[[forwardlist.overview]]</a>
754
 
755
  A `forward_list` is a container that supports forward iterators and
756
  allows constant time insert and erase operations anywhere within the
757
  sequence, with storage management handled automatically. Fast random
758
  access to list elements is not supported.
759
 
760
  [*Note 1*: It is intended that `forward_list` have zero space or time
761
  overhead relative to a hand-written C-style singly linked list. Features
762
  that would conflict with that goal have been omitted. — *end note*]
763
 
764
- A `forward_list` meets all of the requirements of a container (
765
- [[container.req]]), except that the `size()` member function is not
766
- provided and `operator==` has linear complexity. A `forward_list` also
767
- meets all of the requirements for an allocator-aware container (
768
- [[container.alloc.req]]). In addition, a `forward_list` provides the
769
- `assign` member functions ([[container.seq.req]]) and several of the
770
- optional container requirements ([[container.seq.opt]]). Descriptions
771
- are provided here only for operations on `forward_list` that are not
772
- described in that table or for operations where there is additional
773
- semantic information.
774
 
775
  [*Note 2*: Modifying any list requires access to the element preceding
776
  the first element of interest, but in a `forward_list` there is no
777
- constant-time way to access a preceding element. For this reason, ranges
778
- that are modified, such as those supplied to `erase` and `splice`, must
779
- be open at the beginning. — *end note*]
780
 
781
  ``` cpp
782
  namespace std {
783
  template<class T, class Allocator = allocator<T>>
784
  class forward_list {
@@ -788,39 +826,43 @@ namespace std {
788
  using allocator_type = Allocator;
789
  using pointer = typename allocator_traits<Allocator>::pointer;
790
  using const_pointer = typename allocator_traits<Allocator>::const_pointer;
791
  using reference = value_type&;
792
  using const_reference = const value_type&;
793
- using size_type = implementation-defined; // see [container.requirements]
794
- using difference_type = implementation-defined; // see [container.requirements]
795
  using iterator = implementation-defined // type of forward_list::iterator; // see [container.requirements]
796
  using const_iterator = implementation-defined // type of forward_list::const_iterator; // see [container.requirements]
797
 
798
- // [forwardlist.cons], construct/copy/destroy
799
  forward_list() : forward_list(Allocator()) { }
800
  explicit forward_list(const Allocator&);
801
  explicit forward_list(size_type n, const Allocator& = Allocator());
802
  forward_list(size_type n, const T& value, const Allocator& = Allocator());
803
  template<class InputIterator>
804
  forward_list(InputIterator first, InputIterator last, const Allocator& = Allocator());
 
 
805
  forward_list(const forward_list& x);
806
  forward_list(forward_list&& x);
807
- forward_list(const forward_list& x, const Allocator&);
808
- forward_list(forward_list&& x, const Allocator&);
809
  forward_list(initializer_list<T>, const Allocator& = Allocator());
810
  ~forward_list();
811
  forward_list& operator=(const forward_list& x);
812
  forward_list& operator=(forward_list&& x)
813
  noexcept(allocator_traits<Allocator>::is_always_equal::value);
814
  forward_list& operator=(initializer_list<T>);
815
  template<class InputIterator>
816
  void assign(InputIterator first, InputIterator last);
 
 
817
  void assign(size_type n, const T& t);
818
  void assign(initializer_list<T>);
819
  allocator_type get_allocator() const noexcept;
820
 
821
- // [forwardlist.iter], iterators
822
  iterator before_begin() noexcept;
823
  const_iterator before_begin() const noexcept;
824
  iterator begin() noexcept;
825
  const_iterator begin() const noexcept;
826
  iterator end() noexcept;
@@ -832,39 +874,43 @@ namespace std {
832
 
833
  // capacity
834
  [[nodiscard]] bool empty() const noexcept;
835
  size_type max_size() const noexcept;
836
 
837
- // [forwardlist.access], element access
838
  reference front();
839
  const_reference front() const;
840
 
841
- // [forwardlist.modifiers], modifiers
842
  template<class... Args> reference emplace_front(Args&&... args);
843
  void push_front(const T& x);
844
  void push_front(T&& x);
 
 
845
  void pop_front();
846
 
847
  template<class... Args> iterator emplace_after(const_iterator position, Args&&... args);
848
  iterator insert_after(const_iterator position, const T& x);
849
  iterator insert_after(const_iterator position, T&& x);
850
 
851
  iterator insert_after(const_iterator position, size_type n, const T& x);
852
  template<class InputIterator>
853
  iterator insert_after(const_iterator position, InputIterator first, InputIterator last);
854
  iterator insert_after(const_iterator position, initializer_list<T> il);
 
 
855
 
856
  iterator erase_after(const_iterator position);
857
  iterator erase_after(const_iterator position, const_iterator last);
858
  void swap(forward_list&)
859
  noexcept(allocator_traits<Allocator>::is_always_equal::value);
860
 
861
  void resize(size_type sz);
862
  void resize(size_type sz, const value_type& c);
863
  void clear() noexcept;
864
 
865
- // [forwardlist.ops], forward_list operations
866
  void splice_after(const_iterator position, forward_list& x);
867
  void splice_after(const_iterator position, forward_list&& x);
868
  void splice_after(const_iterator position, forward_list& x, const_iterator i);
869
  void splice_after(const_iterator position, forward_list&& x, const_iterator i);
870
  void splice_after(const_iterator position, forward_list& x,
@@ -891,24 +937,23 @@ namespace std {
891
 
892
  template<class InputIterator, class Allocator = allocator<iter-value-type<InputIterator>>>
893
  forward_list(InputIterator, InputIterator, Allocator = Allocator())
894
  -> forward_list<iter-value-type<InputIterator>, Allocator>;
895
 
896
- // swap
897
- template<class T, class Allocator>
898
- void swap(forward_list<T, Allocator>& x, forward_list<T, Allocator>& y)
899
- noexcept(noexcept(x.swap(y)));
900
  }
901
  ```
902
 
903
  An incomplete type `T` may be used when instantiating `forward_list` if
904
  the allocator meets the allocator completeness requirements
905
  [[allocator.requirements.completeness]]. `T` shall be complete before
906
  any member of the resulting specialization of `forward_list` is
907
  referenced.
908
 
909
- #### Constructors, copy, and assignment <a id="forwardlist.cons">[[forwardlist.cons]]</a>
910
 
911
  ``` cpp
912
  explicit forward_list(const Allocator&);
913
  ```
914
 
@@ -947,36 +992,46 @@ template<class InputIterator>
947
  *Effects:* Constructs a `forward_list` object equal to the range
948
  \[`first`, `last`).
949
 
950
  *Complexity:* Linear in `distance(first, last)`.
951
 
952
- #### Iterators <a id="forwardlist.iter">[[forwardlist.iter]]</a>
 
 
 
 
 
 
 
 
 
 
953
 
954
  ``` cpp
955
  iterator before_begin() noexcept;
956
  const_iterator before_begin() const noexcept;
957
  const_iterator cbefore_begin() const noexcept;
958
  ```
959
 
960
- *Returns:* A non-dereferenceable iterator that, when incremented, is
961
- equal to the iterator returned by `begin()`.
962
-
963
  *Effects:* `cbefore_begin()` is equivalent to
964
  `const_cast<forward_list const&>(*this).before_begin()`.
965
 
 
 
 
966
  *Remarks:* `before_begin() == end()` shall equal `false`.
967
 
968
- #### Element access <a id="forwardlist.access">[[forwardlist.access]]</a>
969
 
970
  ``` cpp
971
  reference front();
972
  const_reference front() const;
973
  ```
974
 
975
  *Returns:* `*begin()`
976
 
977
- #### Modifiers <a id="forwardlist.modifiers">[[forwardlist.modifiers]]</a>
978
 
979
  None of the overloads of `insert_after` shall affect the validity of
980
  iterators and references, and `erase_after` shall invalidate only
981
  iterators and references to the erased elements. If an exception is
982
  thrown during `insert_after` there shall be no effect. Inserting `n`
@@ -997,74 +1052,114 @@ void push_front(const T& x);
997
  void push_front(T&& x);
998
  ```
999
 
1000
  *Effects:* Inserts a copy of `x` at the beginning of the list.
1001
 
 
 
 
 
 
 
 
 
 
 
1002
  ``` cpp
1003
  void pop_front();
1004
  ```
1005
 
1006
  *Effects:* As if by `erase_after(before_begin())`.
1007
 
1008
  ``` cpp
1009
  iterator insert_after(const_iterator position, const T& x);
 
 
 
 
 
 
 
 
 
 
 
1010
  iterator insert_after(const_iterator position, T&& x);
1011
  ```
1012
 
1013
- *Preconditions:* `position` is `before_begin()` or is a dereferenceable
1014
- iterator in the range \[`begin()`, `end()`).
 
1015
 
1016
  *Effects:* Inserts a copy of `x` after `position`.
1017
 
1018
  *Returns:* An iterator pointing to the copy of `x`.
1019
 
1020
  ``` cpp
1021
  iterator insert_after(const_iterator position, size_type n, const T& x);
1022
  ```
1023
 
1024
- *Preconditions:* `position` is `before_begin()` or is a dereferenceable
1025
- iterator in the range \[`begin()`, `end()`).
 
1026
 
1027
  *Effects:* Inserts `n` copies of `x` after `position`.
1028
 
1029
- *Returns:* An iterator pointing to the last inserted copy of `x` or
1030
- `position` if `n == 0`.
1031
 
1032
  ``` cpp
1033
  template<class InputIterator>
1034
  iterator insert_after(const_iterator position, InputIterator first, InputIterator last);
1035
  ```
1036
 
1037
- *Preconditions:* `position` is `before_begin()` or is a dereferenceable
 
1038
  iterator in the range \[`begin()`, `end()`). Neither `first` nor `last`
1039
  are iterators in `*this`.
1040
 
1041
  *Effects:* Inserts copies of elements in \[`first`, `last`) after
1042
  `position`.
1043
 
1044
- *Returns:* An iterator pointing to the last inserted element or
1045
- `position` if `first == last`.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1046
 
1047
  ``` cpp
1048
  iterator insert_after(const_iterator position, initializer_list<T> il);
1049
  ```
1050
 
1051
- *Effects:* `insert_after(p, il.begin(), il.end())`.
1052
-
1053
- *Returns:* An iterator pointing to the last inserted element or
1054
- `position` if `il` is empty.
1055
 
1056
  ``` cpp
1057
  template<class... Args>
1058
  iterator emplace_after(const_iterator position, Args&&... args);
1059
  ```
1060
 
1061
- *Preconditions:* `position` is `before_begin()` or is a dereferenceable
1062
- iterator in the range \[`begin()`, `end()`).
 
1063
 
1064
- *Effects:* Inserts an object of type `value_type` constructed with
1065
- `value_type(std::forward<Args>(args)...)` after `position`.
 
1066
 
1067
  *Returns:* An iterator pointing to the new object.
1068
 
1069
  ``` cpp
1070
  iterator erase_after(const_iterator position);
@@ -1121,16 +1216,20 @@ void clear() noexcept;
1121
 
1122
  *Effects:* Erases all elements in the range \[`begin()`, `end()`).
1123
 
1124
  *Remarks:* Does not invalidate past-the-end iterators.
1125
 
1126
- #### Operations <a id="forwardlist.ops">[[forwardlist.ops]]</a>
1127
 
1128
  In this subclause, arguments for a template parameter named `Predicate`
1129
  or `BinaryPredicate` shall meet the corresponding requirements in
1130
- [[algorithms.requirements]]. For `merge` and `sort`, the definitions and
1131
- requirements in [[alg.sorting]] apply.
 
 
 
 
1132
 
1133
  ``` cpp
1134
  void splice_after(const_iterator position, forward_list& x);
1135
  void splice_after(const_iterator position, forward_list&& x);
1136
  ```
@@ -1206,61 +1305,66 @@ the iterators and references to the erased elements.
1206
  *Returns:* The number of elements erased.
1207
 
1208
  *Throws:* Nothing unless an exception is thrown by the equality
1209
  comparison or the predicate.
1210
 
1211
- *Remarks:* Stable [[algorithm.stable]].
1212
-
1213
  *Complexity:* Exactly `distance(begin(), end())` applications of the
1214
  corresponding predicate.
1215
 
 
 
1216
  ``` cpp
1217
  size_type unique();
1218
- template<class BinaryPredicate> size_type unique(BinaryPredicate pred);
1219
  ```
1220
 
 
 
 
 
1221
  *Effects:* Erases all but the first element from every consecutive group
1222
- of equal elements referred to by the iterator `i` in the range
1223
- \[`first + 1`, `last`) for which `*i == *(i-1)` (for the version with no
1224
- arguments) or `pred(*i, *(i - 1))` (for the version with a predicate
1225
- argument) holds. Invalidates only the iterators and references to the
1226
- erased elements.
1227
 
1228
  *Returns:* The number of elements erased.
1229
 
1230
- *Throws:* Nothing unless an exception is thrown by the equality
1231
- comparison or the predicate.
1232
 
1233
- *Complexity:* If the range \[`first`, `last`) is not empty, exactly
1234
- `(last - first) - 1` applications of the corresponding predicate,
1235
- otherwise no applications of the predicate.
1236
 
1237
  ``` cpp
1238
  void merge(forward_list& x);
1239
  void merge(forward_list&& x);
1240
  template<class Compare> void merge(forward_list& x, Compare comp);
1241
  template<class Compare> void merge(forward_list&& x, Compare comp);
1242
  ```
1243
 
 
 
1244
  *Preconditions:* `*this` and `x` are both sorted with respect to the
1245
- comparator `operator<` (for the first two overloads) or `comp` (for the
1246
- last two overloads), and `get_allocator() == x.get_allocator()` is
1247
- `true`.
1248
 
1249
- *Effects:* Merges the two sorted ranges `[begin(), end())` and
1250
- `[x.begin(), x.end())`. `x` is empty after the merge. If an exception is
1251
- thrown other than by a comparison there are no effects. Pointers and
1252
- references to the moved elements of `x` now refer to those same elements
1253
- but as members of `*this`. Iterators referring to the moved elements
1254
- will continue to refer to their elements, but they now behave as
1255
- iterators into `*this`, not into `x`.
1256
-
1257
- *Remarks:* Stable [[algorithm.stable]].
1258
 
1259
  *Complexity:* At most
1260
  `distance(begin(), end()) + distance(x.begin(), x.end()) - 1`
1261
- comparisons.
 
 
 
 
 
1262
 
1263
  ``` cpp
1264
  void sort();
1265
  template<class Compare> void sort(Compare comp);
1266
  ```
@@ -1268,15 +1372,15 @@ template<class Compare> void sort(Compare comp);
1268
  *Effects:* Sorts the list according to the `operator<` or the `comp`
1269
  function object. If an exception is thrown, the order of the elements in
1270
  `*this` is unspecified. Does not affect the validity of iterators and
1271
  references.
1272
 
1273
- *Remarks:* Stable [[algorithm.stable]].
1274
-
1275
  *Complexity:* Approximately N log N comparisons, where N is
1276
  `distance(begin(), end())`.
1277
 
 
 
1278
  ``` cpp
1279
  void reverse() noexcept;
1280
  ```
1281
 
1282
  *Effects:* Reverses the order of the elements in the list. Does not
@@ -1311,19 +1415,21 @@ A `list` is a sequence container that supports bidirectional iterators
1311
  and allows constant time insert and erase operations anywhere within the
1312
  sequence, with storage management handled automatically. Unlike vectors
1313
  [[vector]] and deques [[deque]], fast random access to list elements is
1314
  not supported, but many algorithms only need sequential access anyway.
1315
 
1316
- A `list` meets all of the requirements of a container, of a reversible
1317
- container (given in two tables in [[container.requirements]]), of a
1318
- sequence container, including most of the optional sequence container
1319
- requirements [[sequence.reqmts]], and of an allocator-aware container (
1320
- [[container.alloc.req]]). The exceptions are the `operator[]` and `at`
1321
- member functions, which are not provided.[^2] Descriptions are provided
1322
- here only for operations on `list` that are not described in one of
1323
- these tables or for operations where there is additional semantic
1324
- information.
 
 
1325
 
1326
  ``` cpp
1327
  namespace std {
1328
  template<class T, class Allocator = allocator<T>>
1329
  class list {
@@ -1333,12 +1439,12 @@ namespace std {
1333
  using allocator_type = Allocator;
1334
  using pointer = typename allocator_traits<Allocator>::pointer;
1335
  using const_pointer = typename allocator_traits<Allocator>::const_pointer;
1336
  using reference = value_type&;
1337
  using const_reference = const value_type&;
1338
- using size_type = implementation-defined; // see [container.requirements]
1339
- using difference_type = implementation-defined; // see [container.requirements]
1340
  using iterator = implementation-defined // type of list::iterator; // see [container.requirements]
1341
  using const_iterator = implementation-defined // type of list::const_iterator; // see [container.requirements]
1342
  using reverse_iterator = std::reverse_iterator<iterator>;
1343
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
1344
 
@@ -1347,22 +1453,26 @@ namespace std {
1347
  explicit list(const Allocator&);
1348
  explicit list(size_type n, const Allocator& = Allocator());
1349
  list(size_type n, const T& value, const Allocator& = Allocator());
1350
  template<class InputIterator>
1351
  list(InputIterator first, InputIterator last, const Allocator& = Allocator());
 
 
1352
  list(const list& x);
1353
  list(list&& x);
1354
- list(const list&, const Allocator&);
1355
- list(list&&, const Allocator&);
1356
  list(initializer_list<T>, const Allocator& = Allocator());
1357
  ~list();
1358
  list& operator=(const list& x);
1359
  list& operator=(list&& x)
1360
  noexcept(allocator_traits<Allocator>::is_always_equal::value);
1361
  list& operator=(initializer_list<T>);
1362
  template<class InputIterator>
1363
  void assign(InputIterator first, InputIterator last);
 
 
1364
  void assign(size_type n, const T& t);
1365
  void assign(initializer_list<T>);
1366
  allocator_type get_allocator() const noexcept;
1367
 
1368
  // iterators
@@ -1396,21 +1506,27 @@ namespace std {
1396
  // [list.modifiers], modifiers
1397
  template<class... Args> reference emplace_front(Args&&... args);
1398
  template<class... Args> reference emplace_back(Args&&... args);
1399
  void push_front(const T& x);
1400
  void push_front(T&& x);
 
 
1401
  void pop_front();
1402
  void push_back(const T& x);
1403
  void push_back(T&& x);
 
 
1404
  void pop_back();
1405
 
1406
  template<class... Args> iterator emplace(const_iterator position, Args&&... args);
1407
  iterator insert(const_iterator position, const T& x);
1408
  iterator insert(const_iterator position, T&& x);
1409
  iterator insert(const_iterator position, size_type n, const T& x);
1410
  template<class InputIterator>
1411
  iterator insert(const_iterator position, InputIterator first, InputIterator last);
 
 
1412
  iterator insert(const_iterator position, initializer_list<T> il);
1413
 
1414
  iterator erase(const_iterator position);
1415
  iterator erase(const_iterator position, const_iterator last);
1416
  void swap(list&) noexcept(allocator_traits<Allocator>::is_always_equal::value);
@@ -1444,14 +1560,13 @@ namespace std {
1444
 
1445
  template<class InputIterator, class Allocator = allocator<iter-value-type<InputIterator>>>
1446
  list(InputIterator, InputIterator, Allocator = Allocator())
1447
  -> list<iter-value-type<InputIterator>, Allocator>;
1448
 
1449
- // swap
1450
- template<class T, class Allocator>
1451
- void swap(list<T, Allocator>& x, list<T, Allocator>& y)
1452
- noexcept(noexcept(x.swap(y)));
1453
  }
1454
  ```
1455
 
1456
  An incomplete type `T` may be used when instantiating `list` if the
1457
  allocator meets the allocator completeness requirements
@@ -1497,10 +1612,20 @@ template<class InputIterator>
1497
 
1498
  *Effects:* Constructs a `list` equal to the range \[`first`, `last`).
1499
 
1500
  *Complexity:* Linear in `distance(first, last)`.
1501
 
 
 
 
 
 
 
 
 
 
 
1502
  #### Capacity <a id="list.capacity">[[list.capacity]]</a>
1503
 
1504
  ``` cpp
1505
  void resize(size_type sz);
1506
  ```
@@ -1543,30 +1668,36 @@ iterator insert(const_iterator position, const T& x);
1543
  iterator insert(const_iterator position, T&& x);
1544
  iterator insert(const_iterator position, size_type n, const T& x);
1545
  template<class InputIterator>
1546
  iterator insert(const_iterator position, InputIterator first,
1547
  InputIterator last);
 
 
1548
  iterator insert(const_iterator position, initializer_list<T>);
1549
 
1550
  template<class... Args> reference emplace_front(Args&&... args);
1551
  template<class... Args> reference emplace_back(Args&&... args);
1552
  template<class... Args> iterator emplace(const_iterator position, Args&&... args);
1553
  void push_front(const T& x);
1554
  void push_front(T&& x);
 
 
1555
  void push_back(const T& x);
1556
  void push_back(T&& x);
 
 
1557
  ```
1558
 
1559
- *Remarks:* Does not affect the validity of iterators and references. If
1560
- an exception is thrown there are no effects.
1561
-
1562
  *Complexity:* Insertion of a single element into a list takes constant
1563
  time and exactly one call to a constructor of `T`. Insertion of multiple
1564
  elements into a list is linear in the number of elements inserted, and
1565
  the number of calls to the copy constructor or move constructor of `T`
1566
  is exactly equal to the number of elements inserted.
1567
 
 
 
 
1568
  ``` cpp
1569
  iterator erase(const_iterator position);
1570
  iterator erase(const_iterator first, const_iterator last);
1571
 
1572
  void pop_front();
@@ -1585,15 +1716,18 @@ linear time in the size of the range and the number of calls to the
1585
  destructor of type `T` is exactly equal to the size of the range.
1586
 
1587
  #### Operations <a id="list.ops">[[list.ops]]</a>
1588
 
1589
  Since lists allow fast insertion and erasing from the middle of a list,
1590
- certain operations are provided specifically for them.[^3] In this
1591
- subclause, arguments for a template parameter named `Predicate` or
1592
- `BinaryPredicate` shall meet the corresponding requirements in
1593
- [[algorithms.requirements]]. For `merge` and `sort`, the definitions and
1594
- requirements in [[alg.sorting]] apply.
 
 
 
1595
 
1596
  `list` provides three splice operations that destructively move elements
1597
  from one list to another. The behavior of splice operations is undefined
1598
  if `get_allocator() !=
1599
  x.get_allocator()`.
@@ -1668,67 +1802,64 @@ the erased elements.
1668
  *Returns:* The number of elements erased.
1669
 
1670
  *Throws:* Nothing unless an exception is thrown by `*i == value` or
1671
  `pred(*i) != false`.
1672
 
1673
- *Remarks:* Stable [[algorithm.stable]].
1674
-
1675
  *Complexity:* Exactly `size()` applications of the corresponding
1676
  predicate.
1677
 
 
 
1678
  ``` cpp
1679
  size_type unique();
1680
  template<class BinaryPredicate> size_type unique(BinaryPredicate binary_pred);
1681
  ```
1682
 
 
 
 
 
1683
  *Effects:* Erases all but the first element from every consecutive group
1684
- of equal elements referred to by the iterator `i` in the range
1685
- \[`first + 1`, `last`) for which `*i == *(i-1)` (for the version of
1686
- `unique` with no arguments) or `pred(*i, *(i - 1))` (for the version of
1687
- `unique` with a predicate argument) holds. Invalidates only the
1688
- iterators and references to the erased elements.
1689
 
1690
  *Returns:* The number of elements erased.
1691
 
1692
- *Throws:* Nothing unless an exception is thrown by `*i == *(i-1)` or
1693
- `pred(*i, *(i - 1))`
1694
 
1695
- *Complexity:* If the range `[first, last)` is not empty, exactly
1696
- `(last - first) - 1` applications of the corresponding predicate,
1697
- otherwise no applications of the predicate.
1698
 
1699
  ``` cpp
1700
  void merge(list& x);
1701
  void merge(list&& x);
1702
  template<class Compare> void merge(list& x, Compare comp);
1703
  template<class Compare> void merge(list&& x, Compare comp);
1704
  ```
1705
 
1706
- *Preconditions:* Both the list and the argument list shall be sorted
1707
- with respect to the comparator `operator<` (for the first two overloads)
1708
- or `comp` (for the last two overloads), and
1709
- `get_allocator() == x.get_allocator()` is `true`.
1710
 
1711
- *Effects:* If `addressof(x) == this`, does nothing; otherwise, merges
1712
- the two sorted ranges `[begin(), end())` and `[x.begin(), x.end())`. The
1713
- result is a range in which the elements will be sorted in non-decreasing
1714
- order according to the ordering defined by `comp`; that is, for every
1715
- iterator `i`, in the range other than the first, the condition
1716
- `comp(*i, *(i - 1))` will be `false`. Pointers and references to the
1717
- moved elements of `x` now refer to those same elements but as members of
1718
- `*this`. Iterators referring to the moved elements will continue to
1719
- refer to their elements, but they now behave as iterators into `*this`,
1720
- not into `x`.
1721
 
1722
- *Remarks:* Stable [[algorithm.stable]]. If `addressof(x) != this`, the
1723
- range `[x.begin(), x.end())` is empty after the merge. No elements are
1724
- copied by this operation.
 
 
 
 
1725
 
1726
- *Complexity:* At most `size() + x.size() - 1` applications of `comp` if
1727
- `addressof(x) != this`; otherwise, no applications of `comp` are
1728
- performed. If an exception is thrown other than by a comparison there
1729
- are no effects.
 
 
1730
 
1731
  ``` cpp
1732
  void reverse() noexcept;
1733
  ```
1734
 
@@ -1745,14 +1876,14 @@ template<class Compare> void sort(Compare comp);
1745
  *Effects:* Sorts the list according to the `operator<` or a `Compare`
1746
  function object. If an exception is thrown, the order of the elements in
1747
  `*this` is unspecified. Does not affect the validity of iterators and
1748
  references.
1749
 
1750
- *Remarks:* Stable [[algorithm.stable]].
1751
-
1752
  *Complexity:* Approximately N log N comparisons, where `N == size()`.
1753
 
 
 
1754
  #### Erasure <a id="list.erasure">[[list.erasure]]</a>
1755
 
1756
  ``` cpp
1757
  template<class T, class Allocator, class U>
1758
  typename list<T, Allocator>::size_type
@@ -1777,21 +1908,21 @@ template<class T, class Allocator, class Predicate>
1777
  A `vector` is a sequence container that supports (amortized) constant
1778
  time insert and erase operations at the end; insert and erase in the
1779
  middle take linear time. Storage management is handled automatically,
1780
  though hints can be given to improve efficiency.
1781
 
1782
- A `vector` meets all of the requirements of a container and of a
1783
- reversible container (given in two tables in 
1784
- [[container.requirements]]), of a sequence container, including most of
1785
- the optional sequence container requirements [[sequence.reqmts]], of an
1786
- allocator-aware container ([[container.alloc.req]]), and, for an
1787
- element type other than `bool`, of a contiguous container
1788
- [[container.requirements.general]]. The exceptions are the `push_front`,
1789
- `pop_front`, and `emplace_front` member functions, which are not
1790
- provided. Descriptions are provided here only for operations on `vector`
1791
- that are not described in one of these tables or for operations where
1792
- there is additional semantic information.
1793
 
1794
  The types `iterator` and `const_iterator` meet the constexpr iterator
1795
  requirements [[iterator.requirements.general]].
1796
 
1797
  ``` cpp
@@ -1804,12 +1935,12 @@ namespace std {
1804
  using allocator_type = Allocator;
1805
  using pointer = typename allocator_traits<Allocator>::pointer;
1806
  using const_pointer = typename allocator_traits<Allocator>::const_pointer;
1807
  using reference = value_type&;
1808
  using const_reference = const value_type&;
1809
- using size_type = implementation-defined; // see [container.requirements]
1810
- using difference_type = implementation-defined; // see [container.requirements]
1811
  using iterator = implementation-defined // type of vector::iterator; // see [container.requirements]
1812
  using const_iterator = implementation-defined // type of vector::const_iterator; // see [container.requirements]
1813
  using reverse_iterator = std::reverse_iterator<iterator>;
1814
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
1815
 
@@ -1818,23 +1949,27 @@ namespace std {
1818
  constexpr explicit vector(const Allocator&) noexcept;
1819
  constexpr explicit vector(size_type n, const Allocator& = Allocator());
1820
  constexpr vector(size_type n, const T& value, const Allocator& = Allocator());
1821
  template<class InputIterator>
1822
  constexpr vector(InputIterator first, InputIterator last, const Allocator& = Allocator());
 
 
1823
  constexpr vector(const vector& x);
1824
  constexpr vector(vector&&) noexcept;
1825
- constexpr vector(const vector&, const Allocator&);
1826
- constexpr vector(vector&&, const Allocator&);
1827
  constexpr vector(initializer_list<T>, const Allocator& = Allocator());
1828
  constexpr ~vector();
1829
  constexpr vector& operator=(const vector& x);
1830
  constexpr vector& operator=(vector&& x)
1831
  noexcept(allocator_traits<Allocator>::propagate_on_container_move_assignment::value ||
1832
  allocator_traits<Allocator>::is_always_equal::value);
1833
  constexpr vector& operator=(initializer_list<T>);
1834
  template<class InputIterator>
1835
  constexpr void assign(InputIterator first, InputIterator last);
 
 
1836
  constexpr void assign(size_type n, const T& u);
1837
  constexpr void assign(initializer_list<T>);
1838
  constexpr allocator_type get_allocator() const noexcept;
1839
 
1840
  // iterators
@@ -1878,19 +2013,23 @@ namespace std {
1878
 
1879
  // [vector.modifiers], modifiers
1880
  template<class... Args> constexpr reference emplace_back(Args&&... args);
1881
  constexpr void push_back(const T& x);
1882
  constexpr void push_back(T&& x);
 
 
1883
  constexpr void pop_back();
1884
 
1885
  template<class... Args> constexpr iterator emplace(const_iterator position, Args&&... args);
1886
  constexpr iterator insert(const_iterator position, const T& x);
1887
  constexpr iterator insert(const_iterator position, T&& x);
1888
  constexpr iterator insert(const_iterator position, size_type n, const T& x);
1889
  template<class InputIterator>
1890
  constexpr iterator insert(const_iterator position,
1891
  InputIterator first, InputIterator last);
 
 
1892
  constexpr iterator insert(const_iterator position, initializer_list<T> il);
1893
  constexpr iterator erase(const_iterator position);
1894
  constexpr iterator erase(const_iterator first, const_iterator last);
1895
  constexpr void swap(vector&)
1896
  noexcept(allocator_traits<Allocator>::propagate_on_container_swap::value ||
@@ -1900,23 +2039,22 @@ namespace std {
1900
 
1901
  template<class InputIterator, class Allocator = allocator<iter-value-type<InputIterator>>>
1902
  vector(InputIterator, InputIterator, Allocator = Allocator())
1903
  -> vector<iter-value-type<InputIterator>, Allocator>;
1904
 
1905
- // swap
1906
- template<class T, class Allocator>
1907
- constexpr void swap(vector<T, Allocator>& x, vector<T, Allocator>& y)
1908
- noexcept(noexcept(x.swap(y)));
1909
  }
1910
  ```
1911
 
1912
  An incomplete type `T` may be used when instantiating `vector` if the
1913
  allocator meets the allocator completeness requirements
1914
  [[allocator.requirements.completeness]]. `T` shall be complete before
1915
  any member of the resulting specialization of `vector` is referenced.
1916
 
1917
- #### Constructors, copy, and assignment <a id="vector.cons">[[vector.cons]]</a>
1918
 
1919
  ``` cpp
1920
  constexpr explicit vector(const Allocator&) noexcept;
1921
  ```
1922
 
@@ -1957,12 +2095,27 @@ template<class InputIterator>
1957
  using the specified allocator.
1958
 
1959
  *Complexity:* Makes only N calls to the copy constructor of `T` (where N
1960
  is the distance between `first` and `last`) and no reallocations if
1961
  iterators `first` and `last` are of forward, bidirectional, or random
1962
- access categories. It makes order `N` calls to the copy constructor of
1963
- `T` and order log N reallocations if they are just input iterators.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1964
 
1965
  #### Capacity <a id="vector.capacity">[[vector.capacity]]</a>
1966
 
1967
  ``` cpp
1968
  constexpr size_type capacity() const noexcept;
@@ -1986,15 +2139,15 @@ size, so that it can manage the storage allocation accordingly. After
1986
  `capacity()` otherwise. Reallocation happens at this point if and only
1987
  if the current capacity is less than the argument of `reserve()`. If an
1988
  exception is thrown other than by the move constructor of a
1989
  non-*Cpp17CopyInsertable* type, there are no effects.
1990
 
 
 
1991
  *Complexity:* It does not change the size of the sequence and takes at
1992
  most linear time in the size of the sequence.
1993
 
1994
- *Throws:* `length_error` if `n > max_size()`.[^4]
1995
-
1996
  *Remarks:* Reallocation invalidates all the references, pointers, and
1997
  iterators referring to the elements in the sequence, as well as the
1998
  past-the-end iterator.
1999
 
2000
  [*Note 1*: If no reallocation happens, they remain
@@ -2085,18 +2238,26 @@ range. For a non-empty vector, `data()` `==` `addressof(front())`.
2085
  constexpr iterator insert(const_iterator position, const T& x);
2086
  constexpr iterator insert(const_iterator position, T&& x);
2087
  constexpr iterator insert(const_iterator position, size_type n, const T& x);
2088
  template<class InputIterator>
2089
  constexpr iterator insert(const_iterator position, InputIterator first, InputIterator last);
 
 
2090
  constexpr iterator insert(const_iterator position, initializer_list<T>);
2091
 
2092
  template<class... Args> constexpr reference emplace_back(Args&&... args);
2093
  template<class... Args> constexpr iterator emplace(const_iterator position, Args&&... args);
2094
  constexpr void push_back(const T& x);
2095
  constexpr void push_back(T&& x);
 
 
2096
  ```
2097
 
 
 
 
 
2098
  *Remarks:* Causes reallocation if the new size is greater than the old
2099
  capacity. Reallocation invalidates all the references, pointers, and
2100
  iterators referring to the elements in the sequence, as well as the
2101
  past-the-end iterator. If no reallocation happens, then references,
2102
  pointers, and iterators before the insertion point remain valid but
@@ -2108,31 +2269,27 @@ no effects. If an exception is thrown while inserting a single element
2108
  at the end and `T` is *Cpp17CopyInsertable* or
2109
  `is_nothrow_move_constructible_v<T>` is `true`, there are no effects.
2110
  Otherwise, if an exception is thrown by the move constructor of a
2111
  non-*Cpp17CopyInsertable* `T`, the effects are unspecified.
2112
 
2113
- *Complexity:* If reallocation happens, linear in the number of elements
2114
- of the resulting vector; otherwise, linear in the number of elements
2115
- inserted plus the distance to the end of the vector.
2116
-
2117
  ``` cpp
2118
  constexpr iterator erase(const_iterator position);
2119
  constexpr iterator erase(const_iterator first, const_iterator last);
2120
  constexpr void pop_back();
2121
  ```
2122
 
2123
  *Effects:* Invalidates iterators and references at or after the point of
2124
  the erase.
2125
 
 
 
 
2126
  *Complexity:* The destructor of `T` is called the number of times equal
2127
  to the number of the elements erased, but the assignment operator of `T`
2128
  is called the number of times equal to the number of elements in the
2129
  vector after the erased elements.
2130
 
2131
- *Throws:* Nothing unless an exception is thrown by the assignment
2132
- operator or move assignment operator of `T`.
2133
-
2134
  #### Erasure <a id="vector.erasure">[[vector.erasure]]</a>
2135
 
2136
  ``` cpp
2137
  template<class T, class Allocator, class U>
2138
  constexpr typename vector<T, Allocator>::size_type
@@ -2161,64 +2318,74 @@ auto it = remove_if(c.begin(), c.end(), pred);
2161
  auto r = distance(it, c.end());
2162
  c.erase(it, c.end());
2163
  return r;
2164
  ```
2165
 
2166
- ### Class `vector<bool>` <a id="vector.bool">[[vector.bool]]</a>
2167
 
2168
- To optimize space allocation, a specialization of vector for `bool`
2169
- elements is provided:
 
 
2170
 
2171
  ``` cpp
2172
  namespace std {
2173
  template<class Allocator>
2174
  class vector<bool, Allocator> {
2175
  public:
2176
  // types
2177
  using value_type = bool;
2178
  using allocator_type = Allocator;
2179
- using pointer = implementation-defined;
2180
- using const_pointer = implementation-defined;
2181
  using const_reference = bool;
2182
- using size_type = implementation-defined; // see [container.requirements]
2183
- using difference_type = implementation-defined; // see [container.requirements]
2184
  using iterator = implementation-defined // type of vector<bool>::iterator; // see [container.requirements]
2185
  using const_iterator = implementation-defined // type of vector<bool>::const_iterator; // see [container.requirements]
2186
  using reverse_iterator = std::reverse_iterator<iterator>;
2187
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
2188
 
2189
  // bit reference
2190
  class reference {
2191
  friend class vector;
2192
  constexpr reference() noexcept;
 
2193
  public:
2194
  constexpr reference(const reference&) = default;
2195
  constexpr ~reference();
2196
  constexpr operator bool() const noexcept;
2197
- constexpr reference& operator=(const bool x) noexcept;
2198
  constexpr reference& operator=(const reference& x) noexcept;
 
2199
  constexpr void flip() noexcept; // flips the bit
2200
  };
2201
 
2202
  // construct/copy/destroy
2203
- constexpr vector() : vector(Allocator()) { }
2204
- constexpr explicit vector(const Allocator&);
2205
  constexpr explicit vector(size_type n, const Allocator& = Allocator());
2206
  constexpr vector(size_type n, const bool& value, const Allocator& = Allocator());
2207
  template<class InputIterator>
2208
  constexpr vector(InputIterator first, InputIterator last, const Allocator& = Allocator());
 
 
2209
  constexpr vector(const vector& x);
2210
- constexpr vector(vector&& x);
2211
- constexpr vector(const vector&, const Allocator&);
2212
- constexpr vector(vector&&, const Allocator&);
2213
- constexpr vector(initializer_list<bool>, const Allocator& = Allocator()));
2214
  constexpr ~vector();
2215
  constexpr vector& operator=(const vector& x);
2216
- constexpr vector& operator=(vector&& x);
 
 
2217
  constexpr vector& operator=(initializer_list<bool>);
2218
  template<class InputIterator>
2219
  constexpr void assign(InputIterator first, InputIterator last);
 
 
2220
  constexpr void assign(size_type n, const bool& t);
2221
  constexpr void assign(initializer_list<bool>);
2222
  constexpr allocator_type get_allocator() const noexcept;
2223
 
2224
  // iterators
@@ -2256,23 +2423,29 @@ namespace std {
2256
  constexpr const_reference back() const;
2257
 
2258
  // modifiers
2259
  template<class... Args> constexpr reference emplace_back(Args&&... args);
2260
  constexpr void push_back(const bool& x);
 
 
2261
  constexpr void pop_back();
2262
  template<class... Args> constexpr iterator emplace(const_iterator position, Args&&... args);
2263
  constexpr iterator insert(const_iterator position, const bool& x);
2264
  constexpr iterator insert(const_iterator position, size_type n, const bool& x);
2265
  template<class InputIterator>
2266
  constexpr iterator insert(const_iterator position,
2267
  InputIterator first, InputIterator last);
 
 
2268
  constexpr iterator insert(const_iterator position, initializer_list<bool> il);
2269
 
2270
  constexpr iterator erase(const_iterator position);
2271
  constexpr iterator erase(const_iterator first, const_iterator last);
2272
- constexpr void swap(vector&);
2273
- constexpr static void swap(reference x, reference y) noexcept;
 
 
2274
  constexpr void flip() noexcept; // flips all bits
2275
  constexpr void clear() noexcept;
2276
  };
2277
  }
2278
  ```
@@ -2289,22 +2462,22 @@ recommended instead.
2289
 
2290
  `reference`
2291
 
2292
  is a class that simulates the behavior of references of a single bit in
2293
  `vector<bool>`. The conversion function returns `true` when the bit is
2294
- set, and `false` otherwise. The assignment operator sets the bit when
2295
- the argument is (convertible to) `true` and clears it otherwise. `flip`
2296
  reverses the state of the bit.
2297
 
2298
  ``` cpp
2299
  constexpr void flip() noexcept;
2300
  ```
2301
 
2302
  *Effects:* Replaces each element in the container with its complement.
2303
 
2304
  ``` cpp
2305
- constexpr static void swap(reference x, reference y) noexcept;
2306
  ```
2307
 
2308
  *Effects:* Exchanges the contents of `x` and `y` as if by:
2309
 
2310
  ``` cpp
@@ -2317,5 +2490,52 @@ y = b;
2317
  template<class Allocator> struct hash<vector<bool, Allocator>>;
2318
  ```
2319
 
2320
  The specialization is enabled [[unord.hash]].
2321
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
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
 
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>
 
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
 
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
 
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
222
  sequences of objects. An `array` is a contiguous container
223
+ [[container.reqmts]]. An instance of `array<T, N>` stores `N` elements
224
+ of type `T`, so that `size() == N` is an invariant.
225
 
226
  An `array` is an aggregate [[dcl.init.aggr]] that can be
227
  list-initialized with up to `N` elements whose types are convertible to
228
  `T`.
229
 
230
+ An `array` meets all of the requirements of a container
231
+ [[container.reqmts]] and of a reversible container
232
+ [[container.rev.reqmts]], except that a default constructed `array`
233
+ 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
 
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)>;
324
  ```
 
352
  ```
353
 
354
  *Effects:* Equivalent to `swap_ranges(begin(), end(), y.begin())`.
355
 
356
  [*Note 1*: Unlike the `swap` function for other containers,
357
+ `array::swap` takes linear time, can exit via an exception, and does not
358
  cause iterators to become associated with the other
359
  container. — *end note*]
360
 
361
  #### Specialized algorithms <a id="array.special">[[array.special]]</a>
362
 
 
451
  insert and erase operations at the beginning or the end; insert and
452
  erase in the middle take linear time. That is, a deque is especially
453
  optimized for pushing and popping elements at the beginning and end.
454
  Storage management is handled automatically.
455
 
456
+ A `deque` meets all of the requirements of a container
457
+ [[container.reqmts]], of a reversible container
458
+ [[container.rev.reqmts]], of an allocator-aware container
459
+ [[container.alloc.reqmts]], and of a sequence container, including the
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 {
 
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
 
 
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
 
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
 
 
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>;
581
 
582
+ template<ranges::input_range R, class Allocator = allocator<ranges::range_value_t<R>>>
583
+ deque(from_range_t, R&&, Allocator = Allocator())
584
+ -> deque<ranges::range_value_t<R>, Allocator>;
 
585
  }
586
  ```
587
 
588
  #### Constructors, copy, and assignment <a id="deque.cons">[[deque.cons]]</a>
589
 
 
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());
 
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
  ```
 
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
715
  has no effect on the validity of references to elements of the deque.
716
 
717
+ *Complexity:* The complexity is linear in the number of elements
718
+ inserted plus the lesser of the distances to the beginning and end of
719
+ 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();
 
744
  to all the elements of the deque.
745
 
746
  [*Note 1*: `pop_front` and `pop_back` are erase
747
  operations. — *end note*]
748
 
749
+ *Throws:* Nothing unless an exception is thrown by the assignment
750
+ operator of `T`.
751
+
752
  *Complexity:* The number of calls to the destructor of `T` is the same
753
  as the number of elements erased, but the number of calls to the
754
  assignment operator of `T` is no more than the lesser of the number of
755
  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
 
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
795
  allows constant time insert and erase operations anywhere within the
796
  sequence, with storage management handled automatically. Fast random
797
  access to list elements is not supported.
798
 
799
  [*Note 1*: It is intended that `forward_list` have zero space or time
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
811
+ for operations where there is additional semantic information.
 
812
 
813
  [*Note 2*: Modifying any list requires access to the element preceding
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 {
 
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;
 
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,
 
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>;
941
 
942
+ template<ranges::input_range R, class Allocator = allocator<ranges::range_value_t<R>>>
943
+ forward_list(from_range_t, R&&, Allocator = Allocator())
944
+ -> forward_list<ranges::range_value_t<R>, Allocator>;
 
945
  }
946
  ```
947
 
948
  An incomplete type `T` may be used when instantiating `forward_list` if
949
  the allocator meets the allocator completeness requirements
950
  [[allocator.requirements.completeness]]. `T` shall be complete before
951
  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
 
 
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
 
1018
+ *Returns:* A non-dereferenceable iterator that, when incremented, is
1019
+ equal to the iterator returned by `begin()`.
1020
+
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`
 
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()`).
1080
+
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()`).
1092
 
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()`).
1104
 
1105
  *Effects:* Inserts `n` copies of `x` after `position`.
1106
 
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`
1118
  are iterators in `*this`.
1119
 
1120
  *Effects:* Inserts copies of elements in \[`first`, `last`) after
1121
  `position`.
1122
 
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
1134
+ `*this` do not overlap.
1135
+
1136
+ *Effects:* Inserts copies of elements in the range `rg` after
1137
+ `position`.
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()`).
1157
 
1158
+ *Effects:* Inserts an object of type `value_type`
1159
+ 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);
 
1216
 
1217
  *Effects:* Erases all elements in the range \[`begin()`, `end()`).
1218
 
1219
  *Remarks:* Does not invalidate past-the-end iterators.
1220
 
1221
+ #### Operations <a id="forward.list.ops">[[forward.list.ops]]</a>
1222
 
1223
  In this subclause, arguments for a template parameter named `Predicate`
1224
  or `BinaryPredicate` shall meet the corresponding requirements in
1225
+ [[algorithms.requirements]]. The semantics of `i + n`, where `i` is an
1226
+ iterator into the list and `n` is an integer, are the same as those of
1227
+ `next(i, n)`. The expression `i - n`, where `i` is an iterator into the
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
  ```
 
1305
  *Returns:* The number of elements erased.
1306
 
1307
  *Throws:* Nothing unless an exception is thrown by the equality
1308
  comparison or the predicate.
1309
 
 
 
1310
  *Complexity:* Exactly `distance(begin(), end())` applications of the
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.
1323
+
1324
  *Effects:* Erases all but the first element from every consecutive group
1325
+ of equivalent elements. That is, for a nonempty list, erases all
1326
+ elements referred to by the iterator `i` in the range \[`begin() + 1`,
1327
+ `end()`) for which `binary_pred(*i, *(i - 1))` is `true`. Invalidates
1328
+ only the iterators and references to the erased elements.
 
1329
 
1330
  *Returns:* The number of elements erased.
1331
 
1332
+ *Throws:* Nothing unless an exception is thrown by the predicate.
 
1333
 
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
1348
+ comparator `comp`, and `get_allocator() == x.get_allocator()` is `true`.
 
 
1349
 
1350
+ *Effects:* If `addressof(x) == this`, there are no effects. Otherwise,
1351
+ merges the two sorted ranges \[`begin()`, `end()`) and \[`x.begin()`,
1352
+ `x.end()`). The result is a range that is sorted with respect to the
1353
+ comparator `comp`. Pointers and references to the moved elements of `x`
1354
+ now refer to those same elements but as members of `*this`. Iterators
1355
+ referring to the moved elements will continue to refer to their
1356
+ elements, but they now behave as iterators into `*this`, not into `x`.
 
 
1357
 
1358
  *Complexity:* At most
1359
  `distance(begin(), end()) + distance(x.begin(), x.end()) - 1`
1360
+ comparisons if `addressof(x) != this`; otherwise, no comparisons are
1361
+ performed.
1362
+
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
  ```
 
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
1375
  references.
1376
 
 
 
1377
  *Complexity:* Approximately N log N comparisons, where N is
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
 
1415
  and allows constant time insert and erase operations anywhere within the
1416
  sequence, with storage management handled automatically. Unlike vectors
1417
  [[vector]] and deques [[deque]], fast random access to list elements is
1418
  not supported, but many algorithms only need sequential access anyway.
1419
 
1420
+ A `list` meets all of the requirements of a container
1421
+ [[container.reqmts]], of a reversible container
1422
+ [[container.rev.reqmts]], of an allocator-aware container
1423
+ [[container.alloc.reqmts]], and of a sequence container, including most
1424
+ of the optional sequence container requirements [[sequence.reqmts]]. The
1425
+ exceptions are the `operator[]` and `at` member functions, which are not
1426
+ 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 {
 
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
 
 
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
 
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);
 
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>;
1564
 
1565
+ template<ranges::input_range R, class Allocator = allocator<ranges::range_value_t<R>>>
1566
+ list(from_range_t, R&&, Allocator = Allocator())
1567
+ -> list<ranges::range_value_t<R>, Allocator>;
 
1568
  }
1569
  ```
1570
 
1571
  An incomplete type `T` may be used when instantiating `list` if the
1572
  allocator meets the allocator completeness requirements
 
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
  ```
 
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();
 
1716
  destructor of type `T` is exactly equal to the size of the range.
1717
 
1718
  #### Operations <a id="list.ops">[[list.ops]]</a>
1719
 
1720
  Since lists allow fast insertion and erasing from the middle of a list,
1721
+ certain operations are provided specifically for them.[^3]
1722
+
1723
+ In this subclause, arguments for a template parameter named `Predicate`
1724
+ or `BinaryPredicate` shall meet the corresponding requirements in
1725
+ [[algorithms.requirements]]. The semantics of `i + n` and `i - n`, where
1726
+ `i` is an iterator into the list and `n` is an integer, are the same as
1727
+ those of `next(i, n)` and `prev(i, n)`, respectively. For `merge` and
1728
+ `sort`, the definitions and requirements in [[alg.sorting]] apply.
1729
 
1730
  `list` provides three splice operations that destructively move elements
1731
  from one list to another. The behavior of splice operations is undefined
1732
  if `get_allocator() !=
1733
  x.get_allocator()`.
 
1802
  *Returns:* The number of elements erased.
1803
 
1804
  *Throws:* Nothing unless an exception is thrown by `*i == value` or
1805
  `pred(*i) != false`.
1806
 
 
 
1807
  *Complexity:* Exactly `size()` applications of the corresponding
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.
1820
+
1821
  *Effects:* Erases all but the first element from every consecutive group
1822
+ of equivalent elements. That is, for a nonempty list, erases all
1823
+ elements referred to by the iterator `i` in the range \[`begin() + 1`,
1824
+ `end()`) for which `binary_pred(*i, *(i - 1))` is `true`. Invalidates
1825
+ only the iterators and references to the erased elements.
 
1826
 
1827
  *Returns:* The number of elements erased.
1828
 
1829
+ *Throws:* Nothing unless an exception is thrown by the predicate.
 
1830
 
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
1845
+ comparator `comp`, and `get_allocator() == x.get_allocator()` is `true`.
 
 
 
 
 
 
 
 
1846
 
1847
+ *Effects:* If `addressof(x) == this`, there are no effects. Otherwise,
1848
+ merges the two sorted ranges \[`begin()`, `end()`) and \[`x.begin()`,
1849
+ `x.end()`). The result is a range that is sorted with respect to the
1850
+ comparator `comp`. Pointers and references to the moved elements of `x`
1851
+ now refer to those same elements but as members of `*this`. Iterators
1852
+ referring to the moved elements will continue to refer to their
1853
+ elements, but they now behave as iterators into `*this`, not into `x`.
1854
 
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
 
 
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
 
1908
  A `vector` is a sequence container that supports (amortized) constant
1909
  time insert and erase operations at the end; insert and erase in the
1910
  middle take linear time. Storage management is handled automatically,
1911
  though hints can be given to improve efficiency.
1912
 
1913
+ A `vector` meets all of the requirements of a container
1914
+ [[container.reqmts]], of a reversible container
1915
+ [[container.rev.reqmts]], of an allocator-aware container
1916
+ [[container.alloc.reqmts]], of a sequence container, including most of
1917
+ the optional sequence container requirements [[sequence.reqmts]], and,
1918
+ for an element type other than `bool`, of a contiguous container
1919
+ [[container.reqmts]]. The exceptions are the `push_front`,
1920
+ `prepend_range`, `pop_front`, and `emplace_front` member functions,
1921
+ which are not provided. Descriptions are provided here only for
1922
+ operations on `vector` that are not described in one of these tables or
1923
+ for operations where there is additional semantic information.
1924
 
1925
  The types `iterator` and `const_iterator` meet the constexpr iterator
1926
  requirements [[iterator.requirements.general]].
1927
 
1928
  ``` cpp
 
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]
1943
  using const_iterator = implementation-defined // type of vector::const_iterator; // see [container.requirements]
1944
  using reverse_iterator = std::reverse_iterator<iterator>;
1945
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
1946
 
 
1949
  constexpr explicit vector(const Allocator&) noexcept;
1950
  constexpr explicit vector(size_type n, const Allocator& = Allocator());
1951
  constexpr vector(size_type n, const T& value, const Allocator& = Allocator());
1952
  template<class InputIterator>
1953
  constexpr vector(InputIterator first, InputIterator last, const Allocator& = Allocator());
1954
+ template<container-compatible-range<T> R>
1955
+ constexpr vector(from_range_t, R&& rg, const Allocator& = Allocator());
1956
  constexpr vector(const vector& x);
1957
  constexpr vector(vector&&) noexcept;
1958
+ constexpr vector(const vector&, const type_identity_t<Allocator>&);
1959
+ constexpr vector(vector&&, const type_identity_t<Allocator>&);
1960
  constexpr vector(initializer_list<T>, const Allocator& = Allocator());
1961
  constexpr ~vector();
1962
  constexpr vector& operator=(const vector& x);
1963
  constexpr vector& operator=(vector&& x)
1964
  noexcept(allocator_traits<Allocator>::propagate_on_container_move_assignment::value ||
1965
  allocator_traits<Allocator>::is_always_equal::value);
1966
  constexpr vector& operator=(initializer_list<T>);
1967
  template<class InputIterator>
1968
  constexpr void assign(InputIterator first, InputIterator last);
1969
+ template<container-compatible-range<T> R>
1970
+ constexpr void assign_range(R&& rg);
1971
  constexpr void assign(size_type n, const T& u);
1972
  constexpr void assign(initializer_list<T>);
1973
  constexpr allocator_type get_allocator() const noexcept;
1974
 
1975
  // iterators
 
2013
 
2014
  // [vector.modifiers], modifiers
2015
  template<class... Args> constexpr reference emplace_back(Args&&... args);
2016
  constexpr void push_back(const T& x);
2017
  constexpr void push_back(T&& x);
2018
+ template<container-compatible-range<T> R>
2019
+ constexpr void append_range(R&& rg);
2020
  constexpr void pop_back();
2021
 
2022
  template<class... Args> constexpr iterator emplace(const_iterator position, Args&&... args);
2023
  constexpr iterator insert(const_iterator position, const T& x);
2024
  constexpr iterator insert(const_iterator position, T&& x);
2025
  constexpr iterator insert(const_iterator position, size_type n, const T& x);
2026
  template<class InputIterator>
2027
  constexpr iterator insert(const_iterator position,
2028
  InputIterator first, InputIterator last);
2029
+ template<container-compatible-range<T> R>
2030
+ constexpr iterator insert_range(const_iterator position, R&& rg);
2031
  constexpr iterator insert(const_iterator position, initializer_list<T> il);
2032
  constexpr iterator erase(const_iterator position);
2033
  constexpr iterator erase(const_iterator first, const_iterator last);
2034
  constexpr void swap(vector&)
2035
  noexcept(allocator_traits<Allocator>::propagate_on_container_swap::value ||
 
2039
 
2040
  template<class InputIterator, class Allocator = allocator<iter-value-type<InputIterator>>>
2041
  vector(InputIterator, InputIterator, Allocator = Allocator())
2042
  -> vector<iter-value-type<InputIterator>, Allocator>;
2043
 
2044
+ template<ranges::input_range R, class Allocator = allocator<ranges::range_value_t<R>>>
2045
+ vector(from_range_t, R&&, Allocator = Allocator())
2046
+ -> vector<ranges::range_value_t<R>, Allocator>;
 
2047
  }
2048
  ```
2049
 
2050
  An incomplete type `T` may be used when instantiating `vector` if the
2051
  allocator meets the allocator completeness requirements
2052
  [[allocator.requirements.completeness]]. `T` shall be complete before
2053
  any member of the resulting specialization of `vector` is referenced.
2054
 
2055
+ #### Constructors <a id="vector.cons">[[vector.cons]]</a>
2056
 
2057
  ``` cpp
2058
  constexpr explicit vector(const Allocator&) noexcept;
2059
  ```
2060
 
 
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
+ ```
2107
+
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;
 
2139
  `capacity()` otherwise. Reallocation happens at this point if and only
2140
  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
 
2238
  constexpr iterator insert(const_iterator position, const T& x);
2239
  constexpr iterator insert(const_iterator position, T&& x);
2240
  constexpr iterator insert(const_iterator position, size_type n, const T& x);
2241
  template<class InputIterator>
2242
  constexpr iterator insert(const_iterator position, InputIterator first, InputIterator last);
2243
+ template<container-compatible-range<T> R>
2244
+ constexpr iterator insert_range(const_iterator position, R&& rg);
2245
  constexpr iterator insert(const_iterator position, initializer_list<T>);
2246
 
2247
  template<class... Args> constexpr reference emplace_back(Args&&... args);
2248
  template<class... Args> constexpr iterator emplace(const_iterator position, Args&&... args);
2249
  constexpr void push_back(const T& x);
2250
  constexpr void push_back(T&& x);
2251
+ template<container-compatible-range<T> R>
2252
+ constexpr void append_range(R&& rg);
2253
  ```
2254
 
2255
+ *Complexity:* If reallocation happens, linear in the number of elements
2256
+ of the resulting vector; otherwise, linear in the number of elements
2257
+ inserted plus the distance to the end of the vector.
2258
+
2259
  *Remarks:* Causes reallocation if the new size is greater than the old
2260
  capacity. Reallocation invalidates all the references, pointers, and
2261
  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
 
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
  ```
2279
 
2280
  *Effects:* Invalidates iterators and references at or after the point of
2281
  the erase.
2282
 
2283
+ *Throws:* Nothing unless an exception is thrown by the assignment
2284
+ operator or move assignment operator of `T`.
2285
+
2286
  *Complexity:* The destructor of `T` is called the number of times equal
2287
  to the number of the elements erased, but the assignment operator of `T`
2288
  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
 
2318
  auto r = distance(it, c.end());
2319
  c.erase(it, c.end());
2320
  return r;
2321
  ```
2322
 
2323
+ ### Specialization of `vector` for `bool` <a id="vector.bool">[[vector.bool]]</a>
2324
 
2325
+ #### Partial class template specialization `vector<bool, Allocator>` <a id="vector.bool.pspc">[[vector.bool.pspc]]</a>
2326
+
2327
+ To optimize space allocation, a partial specialization of `vector` for
2328
+ `bool` elements is provided:
2329
 
2330
  ``` cpp
2331
  namespace std {
2332
  template<class Allocator>
2333
  class vector<bool, Allocator> {
2334
  public:
2335
  // types
2336
  using value_type = bool;
2337
  using allocator_type = Allocator;
2338
+ using pointer = implementation-defined // type of vector<bool>::pointer;
2339
+ using const_pointer = implementation-defined // type of vector<bool>::const_pointer;
2340
  using const_reference = bool;
2341
+ using size_type = implementation-defined // type of vector<bool>::size_type; // see [container.requirements]
2342
+ using difference_type = implementation-defined // type of vector<bool>::difference_type; // see [container.requirements]
2343
  using iterator = implementation-defined // type of vector<bool>::iterator; // see [container.requirements]
2344
  using const_iterator = implementation-defined // type of vector<bool>::const_iterator; // see [container.requirements]
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;
2358
  constexpr reference& operator=(const reference& x) noexcept;
2359
+ constexpr const reference& operator=(bool x) const noexcept;
2360
  constexpr void flip() noexcept; // flips the bit
2361
  };
2362
 
2363
  // construct/copy/destroy
2364
+ constexpr vector() noexcept(noexcept(Allocator())) : vector(Allocator()) { }
2365
+ constexpr explicit vector(const Allocator&) noexcept;
2366
  constexpr explicit vector(size_type n, const Allocator& = Allocator());
2367
  constexpr vector(size_type n, const bool& value, const Allocator& = Allocator());
2368
  template<class InputIterator>
2369
  constexpr vector(InputIterator first, InputIterator last, const Allocator& = Allocator());
2370
+ template<container-compatible-range<bool> R>
2371
+ constexpr vector(from_range_t, R&& rg, const Allocator& = Allocator());
2372
  constexpr vector(const vector& x);
2373
+ constexpr vector(vector&& x) noexcept;
2374
+ constexpr vector(const vector&, const type_identity_t<Allocator>&);
2375
+ constexpr vector(vector&&, const type_identity_t<Allocator>&);
2376
+ constexpr vector(initializer_list<bool>, const Allocator& = Allocator());
2377
  constexpr ~vector();
2378
  constexpr vector& operator=(const vector& x);
2379
+ constexpr vector& operator=(vector&& x)
2380
+ noexcept(allocator_traits<Allocator>::propagate_on_container_move_assignment::value ||
2381
+ allocator_traits<Allocator>::is_always_equal::value);
2382
  constexpr vector& operator=(initializer_list<bool>);
2383
  template<class InputIterator>
2384
  constexpr void assign(InputIterator first, InputIterator last);
2385
+ template<container-compatible-range<bool> R>
2386
+ constexpr void assign_range(R&& rg);
2387
  constexpr void assign(size_type n, const bool& t);
2388
  constexpr void assign(initializer_list<bool>);
2389
  constexpr allocator_type get_allocator() const noexcept;
2390
 
2391
  // iterators
 
2423
  constexpr const_reference back() const;
2424
 
2425
  // modifiers
2426
  template<class... Args> constexpr reference emplace_back(Args&&... args);
2427
  constexpr void push_back(const bool& x);
2428
+ template<container-compatible-range<bool> R>
2429
+ constexpr void append_range(R&& rg);
2430
  constexpr void pop_back();
2431
  template<class... Args> constexpr iterator emplace(const_iterator position, Args&&... args);
2432
  constexpr iterator insert(const_iterator position, const bool& x);
2433
  constexpr iterator insert(const_iterator position, size_type n, const bool& x);
2434
  template<class InputIterator>
2435
  constexpr iterator insert(const_iterator position,
2436
  InputIterator first, InputIterator last);
2437
+ template<container-compatible-range<bool> R>
2438
+ constexpr iterator insert_range(const_iterator position, R&& rg);
2439
  constexpr iterator insert(const_iterator position, initializer_list<bool> il);
2440
 
2441
  constexpr iterator erase(const_iterator position);
2442
  constexpr iterator erase(const_iterator first, const_iterator last);
2443
+ constexpr void swap(vector&)
2444
+ noexcept(allocator_traits<Allocator>::propagate_on_container_swap::value ||
2445
+ allocator_traits<Allocator>::is_always_equal::value);
2446
+ static constexpr void swap(reference x, reference y) noexcept;
2447
  constexpr void flip() noexcept; // flips all bits
2448
  constexpr void clear() noexcept;
2449
  };
2450
  }
2451
  ```
 
2462
 
2463
  `reference`
2464
 
2465
  is a class that simulates the behavior of references of a single bit in
2466
  `vector<bool>`. The conversion function returns `true` when the bit is
2467
+ set, and `false` otherwise. The assignment operators set the bit when
2468
+ the argument is (convertible to) `true` and clear it otherwise. `flip`
2469
  reverses the state of the bit.
2470
 
2471
  ``` cpp
2472
  constexpr void flip() noexcept;
2473
  ```
2474
 
2475
  *Effects:* Replaces each element in the container with its complement.
2476
 
2477
  ``` cpp
2478
+ static constexpr void swap(reference x, reference y) noexcept;
2479
  ```
2480
 
2481
  *Effects:* Exchanges the contents of `x` and `y` as if by:
2482
 
2483
  ``` cpp
 
2490
  template<class Allocator> struct hash<vector<bool, Allocator>>;
2491
  ```
2492
 
2493
  The specialization is enabled [[unord.hash]].
2494
 
2495
+ ``` cpp
2496
+ template<class T>
2497
+ constexpr bool is-vector-bool-reference = see below;
2498
+ ```
2499
+
2500
+ The expression *`is-vector-bool-reference`*`<T>` is `true` if `T`
2501
+ denotes the type `vector<bool, Alloc>::reference` for some type `Alloc`
2502
+ and `vector<bool, Alloc>` is not a program-defined specialization.
2503
+
2504
+ #### Formatter specialization for `vector<bool>` <a id="vector.bool.fmt">[[vector.bool.fmt]]</a>
2505
+
2506
+ ``` cpp
2507
+ namespace std {
2508
+ template<class T, class charT>
2509
+ requires is-vector-bool-reference<T>
2510
+ struct formatter<T, charT> {
2511
+ private:
2512
+ formatter<bool, charT> underlying_; // exposition only
2513
+
2514
+ public:
2515
+ template<class ParseContext>
2516
+ constexpr typename ParseContext::iterator
2517
+ parse(ParseContext& ctx);
2518
+
2519
+ template<class FormatContext>
2520
+ typename FormatContext::iterator
2521
+ format(const T& ref, FormatContext& ctx) const;
2522
+ };
2523
+ }
2524
+ ```
2525
+
2526
+ ``` cpp
2527
+ template<class ParseContext>
2528
+ constexpr typename ParseContext::iterator
2529
+ parse(ParseContext& ctx);
2530
+ ```
2531
+
2532
+ Equivalent to: `return `*`underlying_`*`.parse(ctx);`
2533
+
2534
+ ``` cpp
2535
+ template<class FormatContext>
2536
+ typename FormatContext::iterator
2537
+ format(const T& ref, FormatContext& ctx) const;
2538
+ ```
2539
+
2540
+ Equivalent to: `return `*`underlying_`*`.format(ref, ctx);`
2541
+