From Jason Turner

[associative]

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

Diff to HTML by rtfpessoa

Files changed (1) hide show
  1. tmp/tmp5jd7n0v5/{from.md → to.md} +216 -95
tmp/tmp5jd7n0v5/{from.md → to.md} RENAMED
@@ -12,18 +12,27 @@ guides for associative containers:
12
  template<class InputIterator>
13
  using iter-value-type =
14
  typename iterator_traits<InputIterator>::value_type; // exposition only
15
  template<class InputIterator>
16
  using iter-key-type = remove_const_t<
17
- typename iterator_traits<InputIterator>::value_type::first_type>; // exposition only
18
  template<class InputIterator>
19
  using iter-mapped-type =
20
- typename iterator_traits<InputIterator>::value_type::second_type; // exposition only
21
  template<class InputIterator>
22
  using iter-to-alloc-type = pair<
23
- add_const_t<typename iterator_traits<InputIterator>::value_type::first_type>,
24
- typename iterator_traits<InputIterator>::value_type::second_type>; // exposition only
 
 
 
 
 
 
 
 
 
25
  ```
26
 
27
  ### Header `<map>` synopsis <a id="associative.map.syn">[[associative.map.syn]]</a>
28
 
29
  ``` cpp
@@ -47,10 +56,11 @@ namespace std {
47
  template<class Key, class T, class Compare, class Allocator>
48
  void swap(map<Key, T, Compare, Allocator>& x,
49
  map<Key, T, Compare, Allocator>& y)
50
  noexcept(noexcept(x.swap(y)));
51
 
 
52
  template<class Key, class T, class Compare, class Allocator, class Predicate>
53
  typename map<Key, T, Compare, Allocator>::size_type
54
  erase_if(map<Key, T, Compare, Allocator>& c, Predicate pred);
55
 
56
  // [multimap], class template multimap
@@ -69,10 +79,11 @@ namespace std {
69
  template<class Key, class T, class Compare, class Allocator>
70
  void swap(multimap<Key, T, Compare, Allocator>& x,
71
  multimap<Key, T, Compare, Allocator>& y)
72
  noexcept(noexcept(x.swap(y)));
73
 
 
74
  template<class Key, class T, class Compare, class Allocator, class Predicate>
75
  typename multimap<Key, T, Compare, Allocator>::size_type
76
  erase_if(multimap<Key, T, Compare, Allocator>& c, Predicate pred);
77
 
78
  namespace pmr {
@@ -108,10 +119,11 @@ namespace std {
108
  template<class Key, class Compare, class Allocator>
109
  void swap(set<Key, Compare, Allocator>& x,
110
  set<Key, Compare, Allocator>& y)
111
  noexcept(noexcept(x.swap(y)));
112
 
 
113
  template<class Key, class Compare, class Allocator, class Predicate>
114
  typename set<Key, Compare, Allocator>::size_type
115
  erase_if(set<Key, Compare, Allocator>& c, Predicate pred);
116
 
117
  // [multiset], class template multiset
@@ -128,10 +140,11 @@ namespace std {
128
  template<class Key, class Compare, class Allocator>
129
  void swap(multiset<Key, Compare, Allocator>& x,
130
  multiset<Key, Compare, Allocator>& y)
131
  noexcept(noexcept(x.swap(y)));
132
 
 
133
  template<class Key, class Compare, class Allocator, class Predicate>
134
  typename multiset<Key, Compare, Allocator>::size_type
135
  erase_if(multiset<Key, Compare, Allocator>& c, Predicate pred);
136
 
137
  namespace pmr {
@@ -146,25 +159,26 @@ namespace std {
146
 
147
  ### Class template `map` <a id="map">[[map]]</a>
148
 
149
  #### Overview <a id="map.overview">[[map.overview]]</a>
150
 
151
- A `map` is an associative container that supports unique keys (contains
152
- at most one of each key value) and provides for fast retrieval of values
153
- of another type `T` based on the keys. The `map` class supports
154
- bidirectional iterators.
155
 
156
- A `map` meets all of the requirements of a container, of a reversible
157
- container [[container.requirements]], of an associative container
158
- [[associative.reqmts]], and of an allocator-aware container (
159
- [[container.alloc.req]]). A `map` also provides most operations
160
- described in  [[associative.reqmts]] for unique keys. This means that a
161
- `map` supports the `a_uniq` operations in  [[associative.reqmts]] but
162
- not the `a_eq` operations. For a `map<Key,T>` the `key_type` is `Key`
163
- and the `value_type` is `pair<const Key,T>`. Descriptions are provided
164
- here only for operations on `map` that are not described in one of those
165
- tables or for operations where there is additional semantic information.
 
166
 
167
  ``` cpp
168
  namespace std {
169
  template<class Key, class T, class Compare = less<Key>,
170
  class Allocator = allocator<pair<const Key, T>>>
@@ -178,12 +192,12 @@ namespace std {
178
  using allocator_type = Allocator;
179
  using pointer = typename allocator_traits<Allocator>::pointer;
180
  using const_pointer = typename allocator_traits<Allocator>::const_pointer;
181
  using reference = value_type&;
182
  using const_reference = const value_type&;
183
- using size_type = implementation-defined; // see [container.requirements]
184
- using difference_type = implementation-defined; // see [container.requirements]
185
  using iterator = implementation-defined // type of map::iterator; // see [container.requirements]
186
  using const_iterator = implementation-defined // type of map::const_iterator; // see [container.requirements]
187
  using reverse_iterator = std::reverse_iterator<iterator>;
188
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
189
  using node_type = unspecified;
@@ -192,10 +206,11 @@ namespace std {
192
  class value_compare {
193
  friend class map;
194
  protected:
195
  Compare comp;
196
  value_compare(Compare c) : comp(c) {}
 
197
  public:
198
  bool operator()(const value_type& x, const value_type& y) const {
199
  return comp(x.first, y.first);
200
  }
201
  };
@@ -204,21 +219,26 @@ namespace std {
204
  map() : map(Compare()) { }
205
  explicit map(const Compare& comp, const Allocator& = Allocator());
206
  template<class InputIterator>
207
  map(InputIterator first, InputIterator last,
208
  const Compare& comp = Compare(), const Allocator& = Allocator());
 
 
209
  map(const map& x);
210
  map(map&& x);
211
  explicit map(const Allocator&);
212
- map(const map&, const Allocator&);
213
- map(map&&, const Allocator&);
214
  map(initializer_list<value_type>,
215
  const Compare& = Compare(),
216
  const Allocator& = Allocator());
217
  template<class InputIterator>
218
  map(InputIterator first, InputIterator last, const Allocator& a)
219
  : map(first, last, Compare(), a) { }
 
 
 
220
  map(initializer_list<value_type> il, const Allocator& a)
221
  : map(il, Compare(), a) { }
222
  ~map();
223
  map& operator=(const map& x);
224
  map& operator=(map&& x)
@@ -264,14 +284,17 @@ namespace std {
264
  iterator insert(const_iterator position, value_type&& x);
265
  template<class P>
266
  iterator insert(const_iterator position, P&&);
267
  template<class InputIterator>
268
  void insert(InputIterator first, InputIterator last);
 
 
269
  void insert(initializer_list<value_type>);
270
 
271
  node_type extract(const_iterator position);
272
  node_type extract(const key_type& x);
 
273
  insert_return_type insert(node_type&& nh);
274
  iterator insert(const_iterator hint, node_type&& nh);
275
 
276
  template<class... Args>
277
  pair<iterator, bool> try_emplace(const key_type& k, Args&&... args);
@@ -291,10 +314,11 @@ namespace std {
291
  iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj);
292
 
293
  iterator erase(iterator position);
294
  iterator erase(const_iterator position);
295
  size_type erase(const key_type& x);
 
296
  iterator erase(const_iterator first, const_iterator last);
297
  void swap(map&)
298
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
299
  is_nothrow_swappable_v<Compare>);
300
  void clear() noexcept;
@@ -345,28 +369,31 @@ namespace std {
345
  template<class InputIterator, class Compare = less<iter-key-type<InputIterator>>,
346
  class Allocator = allocator<iter-to-alloc-type<InputIterator>>>
347
  map(InputIterator, InputIterator, Compare = Compare(), Allocator = Allocator())
348
  -> map<iter-key-type<InputIterator>, iter-mapped-type<InputIterator>, Compare, Allocator>;
349
 
 
 
 
 
 
350
  template<class Key, class T, class Compare = less<Key>,
351
  class Allocator = allocator<pair<const Key, T>>>
352
  map(initializer_list<pair<Key, T>>, Compare = Compare(), Allocator = Allocator())
353
  -> map<Key, T, Compare, Allocator>;
354
 
355
  template<class InputIterator, class Allocator>
356
  map(InputIterator, InputIterator, Allocator)
357
  -> map<iter-key-type<InputIterator>, iter-mapped-type<InputIterator>,
358
  less<iter-key-type<InputIterator>>, Allocator>;
359
 
 
 
 
 
360
  template<class Key, class T, class Allocator>
361
  map(initializer_list<pair<Key, T>>, Allocator) -> map<Key, T, less<Key>, Allocator>;
362
-
363
- // swap
364
- template<class Key, class T, class Compare, class Allocator>
365
- void swap(map<Key, T, Compare, Allocator>& x,
366
- map<Key, T, Compare, Allocator>& y)
367
- noexcept(noexcept(x.swap(y)));
368
  }
369
  ```
370
 
371
  #### Constructors, copy, and assignment <a id="map.cons">[[map.cons]]</a>
372
 
@@ -388,11 +415,23 @@ template<class InputIterator>
388
  *Effects:* Constructs an empty `map` using the specified comparison
389
  object and allocator, and inserts elements from the range \[`first`,
390
  `last`).
391
 
392
  *Complexity:* Linear in N if the range \[`first`, `last`) is already
393
- sorted using `comp` and otherwise N log N, where N is `last - first`.
 
 
 
 
 
 
 
 
 
 
 
 
394
 
395
  #### Element access <a id="map.access">[[map.access]]</a>
396
 
397
  ``` cpp
398
  mapped_type& operator[](const key_type& x);
@@ -402,11 +441,12 @@ mapped_type& operator[](const key_type& x);
402
 
403
  ``` cpp
404
  mapped_type& operator[](key_type&& x);
405
  ```
406
 
407
- *Effects:* Equivalent to: `return try_emplace(move(x)).first->second;`
 
408
 
409
  ``` cpp
410
  mapped_type& at(const key_type& x);
411
  const mapped_type& at(const key_type& x) const;
412
  ```
@@ -487,11 +527,11 @@ template<class M>
487
  ```
488
 
489
  *Mandates:* `is_assignable_v<mapped_type&, M&&>` is `true`.
490
 
491
  *Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into `map`
492
- from `k`, `forward<M>(obj)`.
493
 
494
  *Effects:* If the map already contains an element `e` whose key is
495
  equivalent to `k`, assigns `std::forward<M>(obj)` to `e.second`.
496
  Otherwise inserts an object of type `value_type` constructed with `k`,
497
  `std::forward<M>(obj)`.
@@ -510,11 +550,11 @@ template<class M>
510
  ```
511
 
512
  *Mandates:* `is_assignable_v<mapped_type&, M&&>` is `true`.
513
 
514
  *Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into `map`
515
- from `move(k)`, `forward<M>(obj)`.
516
 
517
  *Effects:* If the map already contains an element `e` whose key is
518
  equivalent to `k`, assigns `std::forward<M>(obj)` to `e.second`.
519
  Otherwise inserts an object of type `value_type` constructed with
520
  `std::move(k)`, `std::forward<M>(obj)`.
@@ -550,18 +590,19 @@ return original_size - c.size();
550
  ### Class template `multimap` <a id="multimap">[[multimap]]</a>
551
 
552
  #### Overview <a id="multimap.overview">[[multimap.overview]]</a>
553
 
554
  A `multimap` is an associative container that supports equivalent keys
555
- (possibly containing multiple copies of the same key value) and provides
556
- for fast retrieval of values of another type `T` based on the keys. The
557
- `multimap` class supports bidirectional iterators.
558
 
559
- A `multimap` meets all of the requirements of a container and of a
560
- reversible container [[container.requirements]], of an associative
561
- container [[associative.reqmts]], and of an allocator-aware container (
562
- [[container.alloc.req]]). A `multimap` also provides most operations
 
563
  described in  [[associative.reqmts]] for equal keys. This means that a
564
  `multimap` supports the `a_eq` operations in  [[associative.reqmts]] but
565
  not the `a_uniq` operations. For a `multimap<Key,T>` the `key_type` is
566
  `Key` and the `value_type` is `pair<const Key,T>`. Descriptions are
567
  provided here only for operations on `multimap` that are not described
@@ -582,12 +623,12 @@ namespace std {
582
  using allocator_type = Allocator;
583
  using pointer = typename allocator_traits<Allocator>::pointer;
584
  using const_pointer = typename allocator_traits<Allocator>::const_pointer;
585
  using reference = value_type&;
586
  using const_reference = const value_type&;
587
- using size_type = implementation-defined; // see [container.requirements]
588
- using difference_type = implementation-defined; // see [container.requirements]
589
  using iterator = implementation-defined // type of multimap::iterator; // see [container.requirements]
590
  using const_iterator = implementation-defined // type of multimap::const_iterator; // see [container.requirements]
591
  using reverse_iterator = std::reverse_iterator<iterator>;
592
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
593
  using node_type = unspecified;
@@ -595,10 +636,11 @@ namespace std {
595
  class value_compare {
596
  friend class multimap;
597
  protected:
598
  Compare comp;
599
  value_compare(Compare c) : comp(c) { }
 
600
  public:
601
  bool operator()(const value_type& x, const value_type& y) const {
602
  return comp(x.first, y.first);
603
  }
604
  };
@@ -608,21 +650,27 @@ namespace std {
608
  explicit multimap(const Compare& comp, const Allocator& = Allocator());
609
  template<class InputIterator>
610
  multimap(InputIterator first, InputIterator last,
611
  const Compare& comp = Compare(),
612
  const Allocator& = Allocator());
 
 
 
613
  multimap(const multimap& x);
614
  multimap(multimap&& x);
615
  explicit multimap(const Allocator&);
616
- multimap(const multimap&, const Allocator&);
617
- multimap(multimap&&, const Allocator&);
618
  multimap(initializer_list<value_type>,
619
  const Compare& = Compare(),
620
  const Allocator& = Allocator());
621
  template<class InputIterator>
622
  multimap(InputIterator first, InputIterator last, const Allocator& a)
623
  : multimap(first, last, Compare(), a) { }
 
 
 
624
  multimap(initializer_list<value_type> il, const Allocator& a)
625
  : multimap(il, Compare(), a) { }
626
  ~multimap();
627
  multimap& operator=(const multimap& x);
628
  multimap& operator=(multimap&& x)
@@ -661,20 +709,24 @@ namespace std {
661
  iterator insert(const_iterator position, const value_type& x);
662
  iterator insert(const_iterator position, value_type&& x);
663
  template<class P> iterator insert(const_iterator position, P&& x);
664
  template<class InputIterator>
665
  void insert(InputIterator first, InputIterator last);
 
 
666
  void insert(initializer_list<value_type>);
667
 
668
  node_type extract(const_iterator position);
669
  node_type extract(const key_type& x);
 
670
  iterator insert(node_type&& nh);
671
  iterator insert(const_iterator hint, node_type&& nh);
672
 
673
  iterator erase(iterator position);
674
  iterator erase(const_iterator position);
675
  size_type erase(const key_type& x);
 
676
  iterator erase(const_iterator first, const_iterator last);
677
  void swap(multimap&)
678
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
679
  is_nothrow_swappable_v<Compare>);
680
  void clear() noexcept;
@@ -726,29 +778,32 @@ namespace std {
726
  class Allocator = allocator<iter-to-alloc-type<InputIterator>>>
727
  multimap(InputIterator, InputIterator, Compare = Compare(), Allocator = Allocator())
728
  -> multimap<iter-key-type<InputIterator>, iter-mapped-type<InputIterator>,
729
  Compare, Allocator>;
730
 
 
 
 
 
 
731
  template<class Key, class T, class Compare = less<Key>,
732
  class Allocator = allocator<pair<const Key, T>>>
733
  multimap(initializer_list<pair<Key, T>>, Compare = Compare(), Allocator = Allocator())
734
  -> multimap<Key, T, Compare, Allocator>;
735
 
736
  template<class InputIterator, class Allocator>
737
  multimap(InputIterator, InputIterator, Allocator)
738
  -> multimap<iter-key-type<InputIterator>, iter-mapped-type<InputIterator>,
739
  less<iter-key-type<InputIterator>>, Allocator>;
740
 
 
 
 
 
741
  template<class Key, class T, class Allocator>
742
  multimap(initializer_list<pair<Key, T>>, Allocator)
743
  -> multimap<Key, T, less<Key>, Allocator>;
744
-
745
- // swap
746
- template<class Key, class T, class Compare, class Allocator>
747
- void swap(multimap<Key, T, Compare, Allocator>& x,
748
- multimap<Key, T, Compare, Allocator>& y)
749
- noexcept(noexcept(x.swap(y)));
750
  }
751
  ```
752
 
753
  #### Constructors <a id="multimap.cons">[[multimap.cons]]</a>
754
 
@@ -771,11 +826,23 @@ template<class InputIterator>
771
  *Effects:* Constructs an empty `multimap` using the specified comparison
772
  object and allocator, and inserts elements from the range \[`first`,
773
  `last`).
774
 
775
  *Complexity:* Linear in N if the range \[`first`, `last`) is already
776
- sorted using `comp` and otherwise N log N, where N is `last - first`.
 
 
 
 
 
 
 
 
 
 
 
 
777
 
778
  #### Modifiers <a id="multimap.modifiers">[[multimap.modifiers]]</a>
779
 
780
  ``` cpp
781
  template<class P> iterator insert(P&& x);
@@ -812,24 +879,26 @@ return original_size - c.size();
812
 
813
  ### Class template `set` <a id="set">[[set]]</a>
814
 
815
  #### Overview <a id="set.overview">[[set.overview]]</a>
816
 
817
- A `set` is an associative container that supports unique keys (contains
818
- at most one of each key value) and provides for fast retrieval of the
819
- keys themselves. The `set` class supports bidirectional iterators.
 
820
 
821
- A `set` meets all of the requirements of a container, of a reversible
822
- container [[container.requirements]], of an associative container
823
- [[associative.reqmts]], and of an allocator-aware container (
824
- [[container.alloc.req]]). A `set` also provides most operations
825
- described in  [[associative.reqmts]] for unique keys. This means that a
826
- `set` supports the `a_uniq` operations in  [[associative.reqmts]] but
827
- not the `a_eq` operations. For a `set<Key>` both the `key_type` and
828
- `value_type` are `Key`. Descriptions are provided here only for
829
- operations on `set` that are not described in one of these tables and
830
- for operations where there is additional semantic information.
 
831
 
832
  ``` cpp
833
  namespace std {
834
  template<class Key, class Compare = less<Key>,
835
  class Allocator = allocator<Key>>
@@ -843,12 +912,12 @@ namespace std {
843
  using allocator_type = Allocator;
844
  using pointer = typename allocator_traits<Allocator>::pointer;
845
  using const_pointer = typename allocator_traits<Allocator>::const_pointer;
846
  using reference = value_type&;
847
  using const_reference = const value_type&;
848
- using size_type = implementation-defined; // see [container.requirements]
849
- using difference_type = implementation-defined; // see [container.requirements]
850
  using iterator = implementation-defined // type of set::iterator; // see [container.requirements]
851
  using const_iterator = implementation-defined // type of set::const_iterator; // see [container.requirements]
852
  using reverse_iterator = std::reverse_iterator<iterator>;
853
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
854
  using node_type = unspecified;
@@ -858,20 +927,25 @@ namespace std {
858
  set() : set(Compare()) { }
859
  explicit set(const Compare& comp, const Allocator& = Allocator());
860
  template<class InputIterator>
861
  set(InputIterator first, InputIterator last,
862
  const Compare& comp = Compare(), const Allocator& = Allocator());
 
 
863
  set(const set& x);
864
  set(set&& x);
865
  explicit set(const Allocator&);
866
- set(const set&, const Allocator&);
867
- set(set&&, const Allocator&);
868
  set(initializer_list<value_type>, const Compare& = Compare(),
869
  const Allocator& = Allocator());
870
  template<class InputIterator>
871
  set(InputIterator first, InputIterator last, const Allocator& a)
872
  : set(first, last, Compare(), a) { }
 
 
 
873
  set(initializer_list<value_type> il, const Allocator& a)
874
  : set(il, Compare(), a) { }
875
  ~set();
876
  set& operator=(const set& x);
877
  set& operator=(set&& x)
@@ -908,20 +982,25 @@ namespace std {
908
  pair<iterator,bool> insert(value_type&& x);
909
  iterator insert(const_iterator position, const value_type& x);
910
  iterator insert(const_iterator position, value_type&& x);
911
  template<class InputIterator>
912
  void insert(InputIterator first, InputIterator last);
 
 
913
  void insert(initializer_list<value_type>);
914
 
915
  node_type extract(const_iterator position);
916
  node_type extract(const key_type& x);
 
917
  insert_return_type insert(node_type&& nh);
918
  iterator insert(const_iterator hint, node_type&& nh);
919
 
920
- iterator erase(iterator position);
 
921
  iterator erase(const_iterator position);
922
  size_type erase(const key_type& x);
 
923
  iterator erase(const_iterator first, const_iterator last);
924
  void swap(set&)
925
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
926
  is_nothrow_swappable_v<Compare>);
927
  void clear() noexcept;
@@ -974,38 +1053,41 @@ namespace std {
974
  class Allocator = allocator<iter-value-type<InputIterator>>>
975
  set(InputIterator, InputIterator,
976
  Compare = Compare(), Allocator = Allocator())
977
  -> set<iter-value-type<InputIterator>, Compare, Allocator>;
978
 
 
 
 
 
 
979
  template<class Key, class Compare = less<Key>, class Allocator = allocator<Key>>
980
  set(initializer_list<Key>, Compare = Compare(), Allocator = Allocator())
981
  -> set<Key, Compare, Allocator>;
982
 
983
  template<class InputIterator, class Allocator>
984
  set(InputIterator, InputIterator, Allocator)
985
  -> set<iter-value-type<InputIterator>,
986
  less<iter-value-type<InputIterator>>, Allocator>;
987
 
 
 
 
 
988
  template<class Key, class Allocator>
989
  set(initializer_list<Key>, Allocator) -> set<Key, less<Key>, Allocator>;
990
-
991
- // swap
992
- template<class Key, class Compare, class Allocator>
993
- void swap(set<Key, Compare, Allocator>& x,
994
- set<Key, Compare, Allocator>& y)
995
- noexcept(noexcept(x.swap(y)));
996
  }
997
  ```
998
 
999
  #### Constructors, copy, and assignment <a id="set.cons">[[set.cons]]</a>
1000
 
1001
  ``` cpp
1002
  explicit set(const Compare& comp, const Allocator& = Allocator());
1003
  ```
1004
 
1005
  *Effects:* Constructs an empty `set` using the specified comparison
1006
- objects and allocator.
1007
 
1008
  *Complexity:* Constant.
1009
 
1010
  ``` cpp
1011
  template<class InputIterator>
@@ -1016,11 +1098,23 @@ template<class InputIterator>
1016
  *Effects:* Constructs an empty `set` using the specified comparison
1017
  object and allocator, and inserts elements from the range \[`first`,
1018
  `last`).
1019
 
1020
  *Complexity:* Linear in N if the range \[`first`, `last`) is already
1021
- sorted using `comp` and otherwise N log N, where N is `last - first`.
 
 
 
 
 
 
 
 
 
 
 
 
1022
 
1023
  #### Erasure <a id="set.erasure">[[set.erasure]]</a>
1024
 
1025
  ``` cpp
1026
  template<class Key, class Compare, class Allocator, class Predicate>
@@ -1045,18 +1139,19 @@ return original_size - c.size();
1045
  ### Class template `multiset` <a id="multiset">[[multiset]]</a>
1046
 
1047
  #### Overview <a id="multiset.overview">[[multiset.overview]]</a>
1048
 
1049
  A `multiset` is an associative container that supports equivalent keys
1050
- (possibly contains multiple copies of the same key value) and provides
1051
- for fast retrieval of the keys themselves. The `multiset` class supports
1052
- bidirectional iterators.
1053
 
1054
- A `multiset` meets all of the requirements of a container, of a
1055
- reversible container [[container.requirements]], of an associative
1056
- container [[associative.reqmts]], and of an allocator-aware container (
1057
- [[container.alloc.req]]). `multiset` also provides most operations
 
1058
  described in  [[associative.reqmts]] for duplicate keys. This means that
1059
  a `multiset` supports the `a_eq` operations in  [[associative.reqmts]]
1060
  but not the `a_uniq` operations. For a `multiset<Key>` both the
1061
  `key_type` and `value_type` are `Key`. Descriptions are provided here
1062
  only for operations on `multiset` that are not described in one of these
@@ -1077,12 +1172,12 @@ namespace std {
1077
  using allocator_type = Allocator;
1078
  using pointer = typename allocator_traits<Allocator>::pointer;
1079
  using const_pointer = typename allocator_traits<Allocator>::const_pointer;
1080
  using reference = value_type&;
1081
  using const_reference = const value_type&;
1082
- using size_type = implementation-defined; // see [container.requirements]
1083
- using difference_type = implementation-defined; // see [container.requirements]
1084
  using iterator = implementation-defined // type of multiset::iterator; // see [container.requirements]
1085
  using const_iterator = implementation-defined // type of multiset::const_iterator; // see [container.requirements]
1086
  using reverse_iterator = std::reverse_iterator<iterator>;
1087
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
1088
  using node_type = unspecified;
@@ -1091,20 +1186,26 @@ namespace std {
1091
  multiset() : multiset(Compare()) { }
1092
  explicit multiset(const Compare& comp, const Allocator& = Allocator());
1093
  template<class InputIterator>
1094
  multiset(InputIterator first, InputIterator last,
1095
  const Compare& comp = Compare(), const Allocator& = Allocator());
 
 
 
1096
  multiset(const multiset& x);
1097
  multiset(multiset&& x);
1098
  explicit multiset(const Allocator&);
1099
- multiset(const multiset&, const Allocator&);
1100
- multiset(multiset&&, const Allocator&);
1101
  multiset(initializer_list<value_type>, const Compare& = Compare(),
1102
  const Allocator& = Allocator());
1103
  template<class InputIterator>
1104
  multiset(InputIterator first, InputIterator last, const Allocator& a)
1105
  : multiset(first, last, Compare(), a) { }
 
 
 
1106
  multiset(initializer_list<value_type> il, const Allocator& a)
1107
  : multiset(il, Compare(), a) { }
1108
  ~multiset();
1109
  multiset& operator=(const multiset& x);
1110
  multiset& operator=(multiset&& x)
@@ -1141,20 +1242,25 @@ namespace std {
1141
  iterator insert(value_type&& x);
1142
  iterator insert(const_iterator position, const value_type& x);
1143
  iterator insert(const_iterator position, value_type&& x);
1144
  template<class InputIterator>
1145
  void insert(InputIterator first, InputIterator last);
 
 
1146
  void insert(initializer_list<value_type>);
1147
 
1148
  node_type extract(const_iterator position);
1149
  node_type extract(const key_type& x);
 
1150
  iterator insert(node_type&& nh);
1151
  iterator insert(const_iterator hint, node_type&& nh);
1152
 
1153
- iterator erase(iterator position);
 
1154
  iterator erase(const_iterator position);
1155
  size_type erase(const key_type& x);
 
1156
  iterator erase(const_iterator first, const_iterator last);
1157
  void swap(multiset&)
1158
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
1159
  is_nothrow_swappable_v<Compare>);
1160
  void clear() noexcept;
@@ -1207,27 +1313,30 @@ namespace std {
1207
  class Allocator = allocator<iter-value-type<InputIterator>>>
1208
  multiset(InputIterator, InputIterator,
1209
  Compare = Compare(), Allocator = Allocator())
1210
  -> multiset<iter-value-type<InputIterator>, Compare, Allocator>;
1211
 
 
 
 
 
 
1212
  template<class Key, class Compare = less<Key>, class Allocator = allocator<Key>>
1213
  multiset(initializer_list<Key>, Compare = Compare(), Allocator = Allocator())
1214
  -> multiset<Key, Compare, Allocator>;
1215
 
1216
  template<class InputIterator, class Allocator>
1217
  multiset(InputIterator, InputIterator, Allocator)
1218
  -> multiset<iter-value-type<InputIterator>,
1219
  less<iter-value-type<InputIterator>>, Allocator>;
1220
 
 
 
 
 
1221
  template<class Key, class Allocator>
1222
  multiset(initializer_list<Key>, Allocator) -> multiset<Key, less<Key>, Allocator>;
1223
-
1224
- // swap
1225
- template<class Key, class Compare, class Allocator>
1226
- void swap(multiset<Key, Compare, Allocator>& x,
1227
- multiset<Key, Compare, Allocator>& y)
1228
- noexcept(noexcept(x.swap(y)));
1229
  }
1230
  ```
1231
 
1232
  #### Constructors <a id="multiset.cons">[[multiset.cons]]</a>
1233
 
@@ -1249,11 +1358,23 @@ template<class InputIterator>
1249
  *Effects:* Constructs an empty `multiset` using the specified comparison
1250
  object and allocator, and inserts elements from the range \[`first`,
1251
  `last`).
1252
 
1253
  *Complexity:* Linear in N if the range \[`first`, `last`) is already
1254
- sorted using `comp` and otherwise N log N, where N is `last - first`.
 
 
 
 
 
 
 
 
 
 
 
 
1255
 
1256
  #### Erasure <a id="multiset.erasure">[[multiset.erasure]]</a>
1257
 
1258
  ``` cpp
1259
  template<class Key, class Compare, class Allocator, class Predicate>
 
12
  template<class InputIterator>
13
  using iter-value-type =
14
  typename iterator_traits<InputIterator>::value_type; // exposition only
15
  template<class InputIterator>
16
  using iter-key-type = remove_const_t<
17
+ tuple_element_t<0, iter-value-type<InputIterator>>>; // exposition only
18
  template<class InputIterator>
19
  using iter-mapped-type =
20
+ tuple_element_t<1, iter-value-type<InputIterator>>; // exposition only
21
  template<class InputIterator>
22
  using iter-to-alloc-type = pair<
23
+ add_const_t<tuple_element_t<0, iter-value-type<InputIterator>>>,
24
+ tuple_element_t<1, iter-value-type<InputIterator>>>; // exposition only
25
+ template<ranges::input_range Range>
26
+ using range-key-type =
27
+ remove_const_t<typename ranges::range_value_t<Range>::first_type>; // exposition only
28
+ template<ranges::input_range Range>
29
+ using range-mapped-type = typename ranges::range_value_t<Range>::second_type; // exposition only
30
+ template<ranges::input_range Range>
31
+ using range-to-alloc-type =
32
+ pair<add_const_t<typename ranges::range_value_t<Range>::first_type>,
33
+ typename ranges::range_value_t<Range>::second_type>; // exposition only
34
  ```
35
 
36
  ### Header `<map>` synopsis <a id="associative.map.syn">[[associative.map.syn]]</a>
37
 
38
  ``` cpp
 
56
  template<class Key, class T, class Compare, class Allocator>
57
  void swap(map<Key, T, Compare, Allocator>& x,
58
  map<Key, T, Compare, Allocator>& y)
59
  noexcept(noexcept(x.swap(y)));
60
 
61
+ // [map.erasure], erasure for map
62
  template<class Key, class T, class Compare, class Allocator, class Predicate>
63
  typename map<Key, T, Compare, Allocator>::size_type
64
  erase_if(map<Key, T, Compare, Allocator>& c, Predicate pred);
65
 
66
  // [multimap], class template multimap
 
79
  template<class Key, class T, class Compare, class Allocator>
80
  void swap(multimap<Key, T, Compare, Allocator>& x,
81
  multimap<Key, T, Compare, Allocator>& y)
82
  noexcept(noexcept(x.swap(y)));
83
 
84
+ // [multimap.erasure], erasure for multimap
85
  template<class Key, class T, class Compare, class Allocator, class Predicate>
86
  typename multimap<Key, T, Compare, Allocator>::size_type
87
  erase_if(multimap<Key, T, Compare, Allocator>& c, Predicate pred);
88
 
89
  namespace pmr {
 
119
  template<class Key, class Compare, class Allocator>
120
  void swap(set<Key, Compare, Allocator>& x,
121
  set<Key, Compare, Allocator>& y)
122
  noexcept(noexcept(x.swap(y)));
123
 
124
+ // [set.erasure], erasure for set
125
  template<class Key, class Compare, class Allocator, class Predicate>
126
  typename set<Key, Compare, Allocator>::size_type
127
  erase_if(set<Key, Compare, Allocator>& c, Predicate pred);
128
 
129
  // [multiset], class template multiset
 
140
  template<class Key, class Compare, class Allocator>
141
  void swap(multiset<Key, Compare, Allocator>& x,
142
  multiset<Key, Compare, Allocator>& y)
143
  noexcept(noexcept(x.swap(y)));
144
 
145
+ // [multiset.erasure], erasure for multiset
146
  template<class Key, class Compare, class Allocator, class Predicate>
147
  typename multiset<Key, Compare, Allocator>::size_type
148
  erase_if(multiset<Key, Compare, Allocator>& c, Predicate pred);
149
 
150
  namespace pmr {
 
159
 
160
  ### Class template `map` <a id="map">[[map]]</a>
161
 
162
  #### Overview <a id="map.overview">[[map.overview]]</a>
163
 
164
+ A `map` is an associative container that supports unique keys (i.e.,
165
+ contains at most one of each key value) and provides for fast retrieval
166
+ of values of another type `T` based on the keys. The `map` class
167
+ supports bidirectional iterators.
168
 
169
+ A `map` meets all of the requirements of a container
170
+ [[container.reqmts]], of a reversible container
171
+ [[container.rev.reqmts]], of an allocator-aware container
172
+ [[container.alloc.reqmts]]. and of an associative container
173
+ [[associative.reqmts]]. A `map` also provides most operations described
174
+ in  [[associative.reqmts]] for unique keys. This means that a `map`
175
+ supports the `a_uniq` operations in  [[associative.reqmts]] but not the
176
+ `a_eq` operations. For a `map<Key,T>` the `key_type` is `Key` and the
177
+ `value_type` is `pair<const Key,T>`. Descriptions are provided here only
178
+ for operations on `map` that are not described in one of those tables or
179
+ for operations where there is additional semantic information.
180
 
181
  ``` cpp
182
  namespace std {
183
  template<class Key, class T, class Compare = less<Key>,
184
  class Allocator = allocator<pair<const Key, T>>>
 
192
  using allocator_type = Allocator;
193
  using pointer = typename allocator_traits<Allocator>::pointer;
194
  using const_pointer = typename allocator_traits<Allocator>::const_pointer;
195
  using reference = value_type&;
196
  using const_reference = const value_type&;
197
+ using size_type = implementation-defined // type of map::size_type; // see [container.requirements]
198
+ using difference_type = implementation-defined // type of map::difference_type; // see [container.requirements]
199
  using iterator = implementation-defined // type of map::iterator; // see [container.requirements]
200
  using const_iterator = implementation-defined // type of map::const_iterator; // see [container.requirements]
201
  using reverse_iterator = std::reverse_iterator<iterator>;
202
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
203
  using node_type = unspecified;
 
206
  class value_compare {
207
  friend class map;
208
  protected:
209
  Compare comp;
210
  value_compare(Compare c) : comp(c) {}
211
+
212
  public:
213
  bool operator()(const value_type& x, const value_type& y) const {
214
  return comp(x.first, y.first);
215
  }
216
  };
 
219
  map() : map(Compare()) { }
220
  explicit map(const Compare& comp, const Allocator& = Allocator());
221
  template<class InputIterator>
222
  map(InputIterator first, InputIterator last,
223
  const Compare& comp = Compare(), const Allocator& = Allocator());
224
+ template<container-compatible-range<value_type> R>
225
+ map(from_range_t, R&& rg, const Compare& comp = Compare(), const Allocator& = Allocator());
226
  map(const map& x);
227
  map(map&& x);
228
  explicit map(const Allocator&);
229
+ map(const map&, const type_identity_t<Allocator>&);
230
+ map(map&&, const type_identity_t<Allocator>&);
231
  map(initializer_list<value_type>,
232
  const Compare& = Compare(),
233
  const Allocator& = Allocator());
234
  template<class InputIterator>
235
  map(InputIterator first, InputIterator last, const Allocator& a)
236
  : map(first, last, Compare(), a) { }
237
+ template<container-compatible-range<value_type> R>
238
+ map(from_range_t, R&& rg, const Allocator& a))
239
+ : map(from_range, std::forward<R>(rg), Compare(), a) { }
240
  map(initializer_list<value_type> il, const Allocator& a)
241
  : map(il, Compare(), a) { }
242
  ~map();
243
  map& operator=(const map& x);
244
  map& operator=(map&& x)
 
284
  iterator insert(const_iterator position, value_type&& x);
285
  template<class P>
286
  iterator insert(const_iterator position, P&&);
287
  template<class InputIterator>
288
  void insert(InputIterator first, InputIterator last);
289
+ template<container-compatible-range<value_type> R>
290
+ void insert_range(R&& rg);
291
  void insert(initializer_list<value_type>);
292
 
293
  node_type extract(const_iterator position);
294
  node_type extract(const key_type& x);
295
+ template<class K> node_type extract(K&& x);
296
  insert_return_type insert(node_type&& nh);
297
  iterator insert(const_iterator hint, node_type&& nh);
298
 
299
  template<class... Args>
300
  pair<iterator, bool> try_emplace(const key_type& k, Args&&... args);
 
314
  iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj);
315
 
316
  iterator erase(iterator position);
317
  iterator erase(const_iterator position);
318
  size_type erase(const key_type& x);
319
+ template<class K> size_type erase(K&& x);
320
  iterator erase(const_iterator first, const_iterator last);
321
  void swap(map&)
322
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
323
  is_nothrow_swappable_v<Compare>);
324
  void clear() noexcept;
 
369
  template<class InputIterator, class Compare = less<iter-key-type<InputIterator>>,
370
  class Allocator = allocator<iter-to-alloc-type<InputIterator>>>
371
  map(InputIterator, InputIterator, Compare = Compare(), Allocator = Allocator())
372
  -> map<iter-key-type<InputIterator>, iter-mapped-type<InputIterator>, Compare, Allocator>;
373
 
374
+ template<ranges::input_range R, class Compare = less<range-key-type<R>,
375
+ class Allocator = allocator<range-to-alloc-type<R>>>
376
+ map(from_range_t, R&&, Compare = Compare(), Allocator = Allocator())
377
+ -> map<range-key-type<R>, range-mapped-type<R>, Compare, Allocator>;
378
+
379
  template<class Key, class T, class Compare = less<Key>,
380
  class Allocator = allocator<pair<const Key, T>>>
381
  map(initializer_list<pair<Key, T>>, Compare = Compare(), Allocator = Allocator())
382
  -> map<Key, T, Compare, Allocator>;
383
 
384
  template<class InputIterator, class Allocator>
385
  map(InputIterator, InputIterator, Allocator)
386
  -> map<iter-key-type<InputIterator>, iter-mapped-type<InputIterator>,
387
  less<iter-key-type<InputIterator>>, Allocator>;
388
 
389
+ template<ranges::input_range R, class Allocator>
390
+ map(from_range_t, R&&, Allocator)
391
+ -> map<range-key-type<R>, range-mapped-type<R>, less<range-key-type<R>>, Allocator>;
392
+
393
  template<class Key, class T, class Allocator>
394
  map(initializer_list<pair<Key, T>>, Allocator) -> map<Key, T, less<Key>, Allocator>;
 
 
 
 
 
 
395
  }
396
  ```
397
 
398
  #### Constructors, copy, and assignment <a id="map.cons">[[map.cons]]</a>
399
 
 
415
  *Effects:* Constructs an empty `map` using the specified comparison
416
  object and allocator, and inserts elements from the range \[`first`,
417
  `last`).
418
 
419
  *Complexity:* Linear in N if the range \[`first`, `last`) is already
420
+ sorted with respect to `comp` and otherwise N log N, where N is
421
+ `last - first`.
422
+
423
+ ``` cpp
424
+ template<container-compatible-range<value_type> R>
425
+ map(from_range_t, R&& rg, const Compare& comp = Compare(), const Allocator& = Allocator());
426
+ ```
427
+
428
+ *Effects:* Constructs an empty `map` using the specified comparison
429
+ object and allocator, and inserts elements from the range `rg`.
430
+
431
+ *Complexity:* Linear in N if `rg` is already sorted with respect to
432
+ `comp` and otherwise N log N, where N is `ranges::distance(rg)`.
433
 
434
  #### Element access <a id="map.access">[[map.access]]</a>
435
 
436
  ``` cpp
437
  mapped_type& operator[](const key_type& x);
 
441
 
442
  ``` cpp
443
  mapped_type& operator[](key_type&& x);
444
  ```
445
 
446
+ *Effects:* Equivalent to:
447
+ `return try_emplace(std::move(x)).first->second;`
448
 
449
  ``` cpp
450
  mapped_type& at(const key_type& x);
451
  const mapped_type& at(const key_type& x) const;
452
  ```
 
527
  ```
528
 
529
  *Mandates:* `is_assignable_v<mapped_type&, M&&>` is `true`.
530
 
531
  *Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into `map`
532
+ from `k`, `std::forward<M>(obj)`.
533
 
534
  *Effects:* If the map already contains an element `e` whose key is
535
  equivalent to `k`, assigns `std::forward<M>(obj)` to `e.second`.
536
  Otherwise inserts an object of type `value_type` constructed with `k`,
537
  `std::forward<M>(obj)`.
 
550
  ```
551
 
552
  *Mandates:* `is_assignable_v<mapped_type&, M&&>` is `true`.
553
 
554
  *Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into `map`
555
+ from `std::move(k)`, `std::forward<M>(obj)`.
556
 
557
  *Effects:* If the map already contains an element `e` whose key is
558
  equivalent to `k`, assigns `std::forward<M>(obj)` to `e.second`.
559
  Otherwise inserts an object of type `value_type` constructed with
560
  `std::move(k)`, `std::forward<M>(obj)`.
 
590
  ### Class template `multimap` <a id="multimap">[[multimap]]</a>
591
 
592
  #### Overview <a id="multimap.overview">[[multimap.overview]]</a>
593
 
594
  A `multimap` is an associative container that supports equivalent keys
595
+ (i.e., possibly containing multiple copies of the same key value) and
596
+ provides for fast retrieval of values of another type `T` based on the
597
+ keys. The `multimap` class supports bidirectional iterators.
598
 
599
+ A `multimap` meets all of the requirements of a container
600
+ [[container.reqmts]], of a reversible container
601
+ [[container.rev.reqmts]], of an allocator-aware container
602
+ [[container.alloc.reqmts]], and of an associative container
603
+ [[associative.reqmts]]. A `multimap` also provides most operations
604
  described in  [[associative.reqmts]] for equal keys. This means that a
605
  `multimap` supports the `a_eq` operations in  [[associative.reqmts]] but
606
  not the `a_uniq` operations. For a `multimap<Key,T>` the `key_type` is
607
  `Key` and the `value_type` is `pair<const Key,T>`. Descriptions are
608
  provided here only for operations on `multimap` that are not described
 
623
  using allocator_type = Allocator;
624
  using pointer = typename allocator_traits<Allocator>::pointer;
625
  using const_pointer = typename allocator_traits<Allocator>::const_pointer;
626
  using reference = value_type&;
627
  using const_reference = const value_type&;
628
+ using size_type = implementation-defined // type of multimap::size_type; // see [container.requirements]
629
+ using difference_type = implementation-defined // type of multimap::difference_type; // see [container.requirements]
630
  using iterator = implementation-defined // type of multimap::iterator; // see [container.requirements]
631
  using const_iterator = implementation-defined // type of multimap::const_iterator; // see [container.requirements]
632
  using reverse_iterator = std::reverse_iterator<iterator>;
633
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
634
  using node_type = unspecified;
 
636
  class value_compare {
637
  friend class multimap;
638
  protected:
639
  Compare comp;
640
  value_compare(Compare c) : comp(c) { }
641
+
642
  public:
643
  bool operator()(const value_type& x, const value_type& y) const {
644
  return comp(x.first, y.first);
645
  }
646
  };
 
650
  explicit multimap(const Compare& comp, const Allocator& = Allocator());
651
  template<class InputIterator>
652
  multimap(InputIterator first, InputIterator last,
653
  const Compare& comp = Compare(),
654
  const Allocator& = Allocator());
655
+ template<container-compatible-range<value_type> R>
656
+ multimap(from_range_t, R&& rg,
657
+ const Compare& comp = Compare(), const Allocator& = Allocator());
658
  multimap(const multimap& x);
659
  multimap(multimap&& x);
660
  explicit multimap(const Allocator&);
661
+ multimap(const multimap&, const type_identity_t<Allocator>&);
662
+ multimap(multimap&&, const type_identity_t<Allocator>&);
663
  multimap(initializer_list<value_type>,
664
  const Compare& = Compare(),
665
  const Allocator& = Allocator());
666
  template<class InputIterator>
667
  multimap(InputIterator first, InputIterator last, const Allocator& a)
668
  : multimap(first, last, Compare(), a) { }
669
+ template<container-compatible-range<value_type> R>
670
+ multimap(from_range_t, R&& rg, const Allocator& a))
671
+ : multimap(from_range, std::forward<R>(rg), Compare(), a) { }
672
  multimap(initializer_list<value_type> il, const Allocator& a)
673
  : multimap(il, Compare(), a) { }
674
  ~multimap();
675
  multimap& operator=(const multimap& x);
676
  multimap& operator=(multimap&& x)
 
709
  iterator insert(const_iterator position, const value_type& x);
710
  iterator insert(const_iterator position, value_type&& x);
711
  template<class P> iterator insert(const_iterator position, P&& x);
712
  template<class InputIterator>
713
  void insert(InputIterator first, InputIterator last);
714
+ template<container-compatible-range<value_type> R>
715
+ void insert_range(R&& rg);
716
  void insert(initializer_list<value_type>);
717
 
718
  node_type extract(const_iterator position);
719
  node_type extract(const key_type& x);
720
+ template<class K> node_type extract(K&& x);
721
  iterator insert(node_type&& nh);
722
  iterator insert(const_iterator hint, node_type&& nh);
723
 
724
  iterator erase(iterator position);
725
  iterator erase(const_iterator position);
726
  size_type erase(const key_type& x);
727
+ template<class K> size_type erase(K&& x);
728
  iterator erase(const_iterator first, const_iterator last);
729
  void swap(multimap&)
730
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
731
  is_nothrow_swappable_v<Compare>);
732
  void clear() noexcept;
 
778
  class Allocator = allocator<iter-to-alloc-type<InputIterator>>>
779
  multimap(InputIterator, InputIterator, Compare = Compare(), Allocator = Allocator())
780
  -> multimap<iter-key-type<InputIterator>, iter-mapped-type<InputIterator>,
781
  Compare, Allocator>;
782
 
783
+ template<ranges::input_range R, class Compare = less<range-key-type<R>>,
784
+ class Allocator = allocator<range-to-alloc-type<R>>>
785
+ multimap(from_range_t, R&&, Compare = Compare(), Allocator = Allocator())
786
+ -> multimap<range-key-type<R>, range-mapped-type<R>, Compare, Allocator>;
787
+
788
  template<class Key, class T, class Compare = less<Key>,
789
  class Allocator = allocator<pair<const Key, T>>>
790
  multimap(initializer_list<pair<Key, T>>, Compare = Compare(), Allocator = Allocator())
791
  -> multimap<Key, T, Compare, Allocator>;
792
 
793
  template<class InputIterator, class Allocator>
794
  multimap(InputIterator, InputIterator, Allocator)
795
  -> multimap<iter-key-type<InputIterator>, iter-mapped-type<InputIterator>,
796
  less<iter-key-type<InputIterator>>, Allocator>;
797
 
798
+ template<ranges::input_range R, class Allocator>
799
+ multimap(from_range_t, R&&, Allocator)
800
+ -> multimap<range-key-type<R>, range-mapped-type<R>, less<range-key-type<R>>, Allocator>;
801
+
802
  template<class Key, class T, class Allocator>
803
  multimap(initializer_list<pair<Key, T>>, Allocator)
804
  -> multimap<Key, T, less<Key>, Allocator>;
 
 
 
 
 
 
805
  }
806
  ```
807
 
808
  #### Constructors <a id="multimap.cons">[[multimap.cons]]</a>
809
 
 
826
  *Effects:* Constructs an empty `multimap` using the specified comparison
827
  object and allocator, and inserts elements from the range \[`first`,
828
  `last`).
829
 
830
  *Complexity:* Linear in N if the range \[`first`, `last`) is already
831
+ sorted with respect to `comp` and otherwise N log N, where N is
832
+ `last - first`.
833
+
834
+ ``` cpp
835
+ template<container-compatible-range<value_type> R>
836
+ multimap(from_range_t, R&& rg, const Compare& comp = Compare(), const Allocator& = Allocator());
837
+ ```
838
+
839
+ *Effects:* Constructs an empty `multimap` using the specified comparison
840
+ object and allocator, and inserts elements from the range `rg`.
841
+
842
+ *Complexity:* Linear in N if `rg` is already sorted with respect to
843
+ `comp` and otherwise N log N, where N is `ranges::distance(rg)`.
844
 
845
  #### Modifiers <a id="multimap.modifiers">[[multimap.modifiers]]</a>
846
 
847
  ``` cpp
848
  template<class P> iterator insert(P&& x);
 
879
 
880
  ### Class template `set` <a id="set">[[set]]</a>
881
 
882
  #### Overview <a id="set.overview">[[set.overview]]</a>
883
 
884
+ A `set` is an associative container that supports unique keys (i.e.,
885
+ contains at most one of each key value) and provides for fast retrieval
886
+ of the keys themselves. The `set` class supports bidirectional
887
+ iterators.
888
 
889
+ A `set` meets all of the requirements of a container
890
+ [[container.reqmts]], of a reversible container
891
+ [[container.rev.reqmts]], of an allocator-aware container
892
+ [[container.alloc.reqmts]]. and of an associative container
893
+ [[associative.reqmts]]. A `set` also provides most operations described
894
+ in  [[associative.reqmts]] for unique keys. This means that a `set`
895
+ supports the `a_uniq` operations in  [[associative.reqmts]] but not the
896
+ `a_eq` operations. For a `set<Key>` both the `key_type` and `value_type`
897
+ are `Key`. Descriptions are provided here only for operations on `set`
898
+ that are not described in one of these tables and for operations where
899
+ there is additional semantic information.
900
 
901
  ``` cpp
902
  namespace std {
903
  template<class Key, class Compare = less<Key>,
904
  class Allocator = allocator<Key>>
 
912
  using allocator_type = Allocator;
913
  using pointer = typename allocator_traits<Allocator>::pointer;
914
  using const_pointer = typename allocator_traits<Allocator>::const_pointer;
915
  using reference = value_type&;
916
  using const_reference = const value_type&;
917
+ using size_type = implementation-defined // type of set::size_type; // see [container.requirements]
918
+ using difference_type = implementation-defined // type of set::difference_type; // see [container.requirements]
919
  using iterator = implementation-defined // type of set::iterator; // see [container.requirements]
920
  using const_iterator = implementation-defined // type of set::const_iterator; // see [container.requirements]
921
  using reverse_iterator = std::reverse_iterator<iterator>;
922
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
923
  using node_type = unspecified;
 
927
  set() : set(Compare()) { }
928
  explicit set(const Compare& comp, const Allocator& = Allocator());
929
  template<class InputIterator>
930
  set(InputIterator first, InputIterator last,
931
  const Compare& comp = Compare(), const Allocator& = Allocator());
932
+ template<container-compatible-range<value_type> R>
933
+ set(from_range_t, R&& rg, const Compare& comp = Compare(), const Allocator& = Allocator());
934
  set(const set& x);
935
  set(set&& x);
936
  explicit set(const Allocator&);
937
+ set(const set&, const type_identity_t<Allocator>&);
938
+ set(set&&, const type_identity_t<Allocator>&);
939
  set(initializer_list<value_type>, const Compare& = Compare(),
940
  const Allocator& = Allocator());
941
  template<class InputIterator>
942
  set(InputIterator first, InputIterator last, const Allocator& a)
943
  : set(first, last, Compare(), a) { }
944
+ template<container-compatible-range<value_type> R>
945
+ set(from_range_t, R&& rg, const Allocator& a))
946
+ : set(from_range, std::forward<R>(rg), Compare(), a) { }
947
  set(initializer_list<value_type> il, const Allocator& a)
948
  : set(il, Compare(), a) { }
949
  ~set();
950
  set& operator=(const set& x);
951
  set& operator=(set&& x)
 
982
  pair<iterator,bool> insert(value_type&& x);
983
  iterator insert(const_iterator position, const value_type& x);
984
  iterator insert(const_iterator position, value_type&& x);
985
  template<class InputIterator>
986
  void insert(InputIterator first, InputIterator last);
987
+ template<container-compatible-range<value_type> R>
988
+ void insert_range(R&& rg);
989
  void insert(initializer_list<value_type>);
990
 
991
  node_type extract(const_iterator position);
992
  node_type extract(const key_type& x);
993
+ template<class K> node_type extract(K&& x);
994
  insert_return_type insert(node_type&& nh);
995
  iterator insert(const_iterator hint, node_type&& nh);
996
 
997
+ iterator erase(iterator position)
998
+ requires (!same_as<iterator, const_iterator>);
999
  iterator erase(const_iterator position);
1000
  size_type erase(const key_type& x);
1001
+ template<class K> size_type erase(K&& x);
1002
  iterator erase(const_iterator first, const_iterator last);
1003
  void swap(set&)
1004
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
1005
  is_nothrow_swappable_v<Compare>);
1006
  void clear() noexcept;
 
1053
  class Allocator = allocator<iter-value-type<InputIterator>>>
1054
  set(InputIterator, InputIterator,
1055
  Compare = Compare(), Allocator = Allocator())
1056
  -> set<iter-value-type<InputIterator>, Compare, Allocator>;
1057
 
1058
+ template<ranges::input_range R, class Compare = less<ranges::range_value_t<R>>,
1059
+ class Allocator = allocator<ranges::range_value_t<R>>>
1060
+ set(from_range_t, R&&, Compare = Compare(), Allocator = Allocator())
1061
+ -> set<ranges::range_value_t<R>, Compare, Allocator>;
1062
+
1063
  template<class Key, class Compare = less<Key>, class Allocator = allocator<Key>>
1064
  set(initializer_list<Key>, Compare = Compare(), Allocator = Allocator())
1065
  -> set<Key, Compare, Allocator>;
1066
 
1067
  template<class InputIterator, class Allocator>
1068
  set(InputIterator, InputIterator, Allocator)
1069
  -> set<iter-value-type<InputIterator>,
1070
  less<iter-value-type<InputIterator>>, Allocator>;
1071
 
1072
+ template<ranges::input_range R, class Allocator>
1073
+ set(from_range_t, R&&, Allocator)
1074
+ -> set<ranges::range_value_t<R>, less<ranges::range_value_t<R>>, Allocator>;
1075
+
1076
  template<class Key, class Allocator>
1077
  set(initializer_list<Key>, Allocator) -> set<Key, less<Key>, Allocator>;
 
 
 
 
 
 
1078
  }
1079
  ```
1080
 
1081
  #### Constructors, copy, and assignment <a id="set.cons">[[set.cons]]</a>
1082
 
1083
  ``` cpp
1084
  explicit set(const Compare& comp, const Allocator& = Allocator());
1085
  ```
1086
 
1087
  *Effects:* Constructs an empty `set` using the specified comparison
1088
+ object and allocator.
1089
 
1090
  *Complexity:* Constant.
1091
 
1092
  ``` cpp
1093
  template<class InputIterator>
 
1098
  *Effects:* Constructs an empty `set` using the specified comparison
1099
  object and allocator, and inserts elements from the range \[`first`,
1100
  `last`).
1101
 
1102
  *Complexity:* Linear in N if the range \[`first`, `last`) is already
1103
+ sorted with respect to `comp` and otherwise N log N, where N is
1104
+ `last - first`.
1105
+
1106
+ ``` cpp
1107
+ template<container-compatible-range<value_type> R>
1108
+ set(from_range_t, R&& rg, const Compare& comp = Compare(), const Allocator& = Allocator());
1109
+ ```
1110
+
1111
+ *Effects:* Constructs an empty `set` using the specified comparison
1112
+ object and allocator, and inserts elements from the range `rg`.
1113
+
1114
+ *Complexity:* Linear in N if `rg` is already sorted with respect to
1115
+ `comp` and otherwise N log N, where N is `ranges::distance(rg)`.
1116
 
1117
  #### Erasure <a id="set.erasure">[[set.erasure]]</a>
1118
 
1119
  ``` cpp
1120
  template<class Key, class Compare, class Allocator, class Predicate>
 
1139
  ### Class template `multiset` <a id="multiset">[[multiset]]</a>
1140
 
1141
  #### Overview <a id="multiset.overview">[[multiset.overview]]</a>
1142
 
1143
  A `multiset` is an associative container that supports equivalent keys
1144
+ (i.e., possibly contains multiple copies of the same key value) and
1145
+ provides for fast retrieval of the keys themselves. The `multiset` class
1146
+ supports bidirectional iterators.
1147
 
1148
+ A `multiset` meets all of the requirements of a container
1149
+ [[container.reqmts]], of a reversible container
1150
+ [[container.rev.reqmts]], of an allocator-aware container
1151
+ [[container.alloc.reqmts]], of an associative container
1152
+ [[associative.reqmts]]. `multiset` also provides most operations
1153
  described in  [[associative.reqmts]] for duplicate keys. This means that
1154
  a `multiset` supports the `a_eq` operations in  [[associative.reqmts]]
1155
  but not the `a_uniq` operations. For a `multiset<Key>` both the
1156
  `key_type` and `value_type` are `Key`. Descriptions are provided here
1157
  only for operations on `multiset` that are not described in one of these
 
1172
  using allocator_type = Allocator;
1173
  using pointer = typename allocator_traits<Allocator>::pointer;
1174
  using const_pointer = typename allocator_traits<Allocator>::const_pointer;
1175
  using reference = value_type&;
1176
  using const_reference = const value_type&;
1177
+ using size_type = implementation-defined // type of multiset::size_type; // see [container.requirements]
1178
+ using difference_type = implementation-defined // type of multiset::difference_type; // see [container.requirements]
1179
  using iterator = implementation-defined // type of multiset::iterator; // see [container.requirements]
1180
  using const_iterator = implementation-defined // type of multiset::const_iterator; // see [container.requirements]
1181
  using reverse_iterator = std::reverse_iterator<iterator>;
1182
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
1183
  using node_type = unspecified;
 
1186
  multiset() : multiset(Compare()) { }
1187
  explicit multiset(const Compare& comp, const Allocator& = Allocator());
1188
  template<class InputIterator>
1189
  multiset(InputIterator first, InputIterator last,
1190
  const Compare& comp = Compare(), const Allocator& = Allocator());
1191
+ template<container-compatible-range<value_type> R>
1192
+ multiset(from_range_t, R&& rg,
1193
+ const Compare& comp = Compare(), const Allocator& = Allocator());
1194
  multiset(const multiset& x);
1195
  multiset(multiset&& x);
1196
  explicit multiset(const Allocator&);
1197
+ multiset(const multiset&, const type_identity_t<Allocator>&);
1198
+ multiset(multiset&&, const type_identity_t<Allocator>&);
1199
  multiset(initializer_list<value_type>, const Compare& = Compare(),
1200
  const Allocator& = Allocator());
1201
  template<class InputIterator>
1202
  multiset(InputIterator first, InputIterator last, const Allocator& a)
1203
  : multiset(first, last, Compare(), a) { }
1204
+ template<container-compatible-range<value_type> R>
1205
+ multiset(from_range_t, R&& rg, const Allocator& a))
1206
+ : multiset(from_range, std::forward<R>(rg), Compare(), a) { }
1207
  multiset(initializer_list<value_type> il, const Allocator& a)
1208
  : multiset(il, Compare(), a) { }
1209
  ~multiset();
1210
  multiset& operator=(const multiset& x);
1211
  multiset& operator=(multiset&& x)
 
1242
  iterator insert(value_type&& x);
1243
  iterator insert(const_iterator position, const value_type& x);
1244
  iterator insert(const_iterator position, value_type&& x);
1245
  template<class InputIterator>
1246
  void insert(InputIterator first, InputIterator last);
1247
+ template<container-compatible-range<value_type> R>
1248
+ void insert_range(R&& rg);
1249
  void insert(initializer_list<value_type>);
1250
 
1251
  node_type extract(const_iterator position);
1252
  node_type extract(const key_type& x);
1253
+ template<class K> node_type extract(K&& x);
1254
  iterator insert(node_type&& nh);
1255
  iterator insert(const_iterator hint, node_type&& nh);
1256
 
1257
+ iterator erase(iterator position)
1258
+ requires (!same_as<iterator, const_iterator>);
1259
  iterator erase(const_iterator position);
1260
  size_type erase(const key_type& x);
1261
+ template<class K> size_type erase(K&& x);
1262
  iterator erase(const_iterator first, const_iterator last);
1263
  void swap(multiset&)
1264
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
1265
  is_nothrow_swappable_v<Compare>);
1266
  void clear() noexcept;
 
1313
  class Allocator = allocator<iter-value-type<InputIterator>>>
1314
  multiset(InputIterator, InputIterator,
1315
  Compare = Compare(), Allocator = Allocator())
1316
  -> multiset<iter-value-type<InputIterator>, Compare, Allocator>;
1317
 
1318
+ template<ranges::input_range R, class Compare = less<ranges::range_value_t<R>>,
1319
+ class Allocator = allocator<ranges::range_value_t<R>>>
1320
+ multiset(from_range_t, R&&, Compare = Compare(), Allocator = Allocator())
1321
+ -> multiset<ranges::range_value_t<R>, Compare, Allocator>;
1322
+
1323
  template<class Key, class Compare = less<Key>, class Allocator = allocator<Key>>
1324
  multiset(initializer_list<Key>, Compare = Compare(), Allocator = Allocator())
1325
  -> multiset<Key, Compare, Allocator>;
1326
 
1327
  template<class InputIterator, class Allocator>
1328
  multiset(InputIterator, InputIterator, Allocator)
1329
  -> multiset<iter-value-type<InputIterator>,
1330
  less<iter-value-type<InputIterator>>, Allocator>;
1331
 
1332
+ template<ranges::input_range R, class Allocator>
1333
+ multiset(from_range_t, R&&, Allocator)
1334
+ -> multiset<ranges::range_value_t<R>, less<ranges::range_value_t<R>>, Allocator>;
1335
+
1336
  template<class Key, class Allocator>
1337
  multiset(initializer_list<Key>, Allocator) -> multiset<Key, less<Key>, Allocator>;
 
 
 
 
 
 
1338
  }
1339
  ```
1340
 
1341
  #### Constructors <a id="multiset.cons">[[multiset.cons]]</a>
1342
 
 
1358
  *Effects:* Constructs an empty `multiset` using the specified comparison
1359
  object and allocator, and inserts elements from the range \[`first`,
1360
  `last`).
1361
 
1362
  *Complexity:* Linear in N if the range \[`first`, `last`) is already
1363
+ sorted with respect to `comp` and otherwise N log N, where N is
1364
+ `last - first`.
1365
+
1366
+ ``` cpp
1367
+ template<container-compatible-range<value_type> R>
1368
+ multiset(from_range_t, R&& rg, const Compare& comp = Compare(), const Allocator& = Allocator());
1369
+ ```
1370
+
1371
+ *Effects:* Constructs an empty `multiset` using the specified comparison
1372
+ object and allocator, and inserts elements from the range `rg`.
1373
+
1374
+ *Complexity:* Linear in N if `rg` is already sorted with respect to
1375
+ `comp` and otherwise N log N, where N is `ranges::distance(rg)`.
1376
 
1377
  #### Erasure <a id="multiset.erasure">[[multiset.erasure]]</a>
1378
 
1379
  ``` cpp
1380
  template<class Key, class Compare, class Allocator, class Predicate>