From Jason Turner

[associative]

C++23 → Trunk 82.7 KB 1108 lines
Current Draft | LaTeX Source
Archived: C++23
Markdown: C++23 | Trunk
Explore in Adventure Game

Diff to HTML by rtfpessoa

Files changed (1) hide show
  1. tmp/tmpd5beixw0/{from.md → to.md} +607 -465
tmp/tmpd5beixw0/{from.md → to.md} RENAMED
@@ -1,37 +1,36 @@
1
  ## Associative containers <a id="associative">[[associative]]</a>
2
 
3
- ### In general <a id="associative.general">[[associative.general]]</a>
4
 
5
  The header `<map>` defines the class templates `map` and `multimap`; the
6
  header `<set>` defines the class templates `set` and `multiset`.
7
 
8
  The following exposition-only alias templates may appear in deduction
9
  guides for associative containers:
10
 
11
  ``` cpp
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
 
@@ -44,48 +43,48 @@ namespace std {
44
  template<class Key, class T, class Compare = less<Key>,
45
  class Allocator = allocator<pair<const Key, T>>>
46
  class map;
47
 
48
  template<class Key, class T, class Compare, class Allocator>
49
- bool operator==(const map<Key, T, Compare, Allocator>& x,
50
  const map<Key, T, Compare, Allocator>& y);
51
  template<class Key, class T, class Compare, class Allocator>
52
- synth-three-way-result<pair<const Key, T>>
53
  operator<=>(const map<Key, T, Compare, Allocator>& x,
54
  const map<Key, T, Compare, Allocator>& y);
55
 
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
67
  template<class Key, class T, class Compare = less<Key>,
68
  class Allocator = allocator<pair<const Key, T>>>
69
  class multimap;
70
 
71
  template<class Key, class T, class Compare, class Allocator>
72
- bool operator==(const multimap<Key, T, Compare, Allocator>& x,
73
  const multimap<Key, T, Compare, Allocator>& y);
74
  template<class Key, class T, class Compare, class Allocator>
75
- synth-three-way-result<pair<const Key, T>>
76
  operator<=>(const multimap<Key, T, Compare, Allocator>& x,
77
  const multimap<Key, T, Compare, Allocator>& y);
78
 
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 {
90
  template<class Key, class T, class Compare = less<Key>>
91
  using map = std::map<Key, T, Compare,
@@ -96,69 +95,10 @@ namespace std {
96
  polymorphic_allocator<pair<const Key, T>>>;
97
  }
98
  }
99
  ```
100
 
101
- ### Header `<set>` synopsis <a id="associative.set.syn">[[associative.set.syn]]</a>
102
-
103
- ``` cpp
104
- #include <compare> // see [compare.syn]
105
- #include <initializer_list> // see [initializer.list.syn]
106
-
107
- namespace std {
108
- // [set], class template set
109
- template<class Key, class Compare = less<Key>, class Allocator = allocator<Key>>
110
- class set;
111
-
112
- template<class Key, class Compare, class Allocator>
113
- bool operator==(const set<Key, Compare, Allocator>& x,
114
- const set<Key, Compare, Allocator>& y);
115
- template<class Key, class Compare, class Allocator>
116
- synth-three-way-result<Key> operator<=>(const set<Key, Compare, Allocator>& x,
117
- \itcorr const set<Key, Compare, Allocator>& y);
118
-
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
130
- template<class Key, class Compare = less<Key>, class Allocator = allocator<Key>>
131
- class multiset;
132
-
133
- template<class Key, class Compare, class Allocator>
134
- bool operator==(const multiset<Key, Compare, Allocator>& x,
135
- const multiset<Key, Compare, Allocator>& y);
136
- template<class Key, class Compare, class Allocator>
137
- synth-three-way-result<Key> operator<=>(const multiset<Key, Compare, Allocator>& x,
138
- \itcorr const multiset<Key, Compare, Allocator>& y);
139
-
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 {
151
- template<class Key, class Compare = less<Key>>
152
- using set = std::set<Key, Compare, polymorphic_allocator<Key>>;
153
-
154
- template<class Key, class Compare = less<Key>>
155
- using multiset = std::multiset<Key, Compare, polymorphic_allocator<Key>>;
156
- }
157
- }
158
- ```
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.,
@@ -167,19 +107,22 @@ 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>>>
185
  class map {
@@ -188,12 +131,12 @@ namespace std {
188
  using key_type = Key;
189
  using mapped_type = T;
190
  using value_type = pair<const Key, T>;
191
  using key_compare = Compare;
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]
@@ -202,170 +145,181 @@ namespace std {
202
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
203
  using node_type = unspecified;
204
  using insert_return_type = insert-return-type<iterator, node_type>;
205
 
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
  };
217
 
218
  // [map.cons], construct/copy/destroy
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)
245
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
246
  is_nothrow_move_assignable_v<Compare>);
247
- map& operator=(initializer_list<value_type>);
248
- allocator_type get_allocator() const noexcept;
249
 
250
  // iterators
251
- iterator begin() noexcept;
252
- const_iterator begin() const noexcept;
253
- iterator end() noexcept;
254
- const_iterator end() const noexcept;
255
 
256
- reverse_iterator rbegin() noexcept;
257
- const_reverse_iterator rbegin() const noexcept;
258
- reverse_iterator rend() noexcept;
259
- const_reverse_iterator rend() const noexcept;
260
 
261
- const_iterator cbegin() const noexcept;
262
- const_iterator cend() const noexcept;
263
- const_reverse_iterator crbegin() const noexcept;
264
- const_reverse_iterator crend() const noexcept;
265
 
266
  // capacity
267
- [[nodiscard]] bool empty() const noexcept;
268
- size_type size() const noexcept;
269
- size_type max_size() const noexcept;
270
 
271
  // [map.access], element access
272
- mapped_type& operator[](const key_type& x);
273
- mapped_type& operator[](key_type&& x);
274
- mapped_type& at(const key_type& x);
275
- const mapped_type& at(const key_type& x) const;
 
 
 
276
 
277
  // [map.modifiers], modifiers
278
- template<class... Args> pair<iterator, bool> emplace(Args&&... args);
279
- template<class... Args> iterator emplace_hint(const_iterator position, Args&&... args);
280
- pair<iterator, bool> insert(const value_type& x);
281
- pair<iterator, bool> insert(value_type&& x);
282
- template<class P> pair<iterator, bool> insert(P&& x);
283
- iterator insert(const_iterator position, const value_type& 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);
301
  template<class... Args>
302
- pair<iterator, bool> try_emplace(key_type&& k, Args&&... args);
 
 
303
  template<class... Args>
304
- iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args);
305
  template<class... Args>
306
- iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args);
 
 
307
  template<class M>
308
- pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj);
309
  template<class M>
310
- pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj);
 
 
311
  template<class M>
312
- iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj);
313
  template<class M>
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;
325
 
326
  template<class C2>
327
- void merge(map<Key, T, C2, Allocator>& source);
328
  template<class C2>
329
- void merge(map<Key, T, C2, Allocator>&& source);
330
  template<class C2>
331
- void merge(multimap<Key, T, C2, Allocator>& source);
332
  template<class C2>
333
- void merge(multimap<Key, T, C2, Allocator>&& source);
334
 
335
  // observers
336
- key_compare key_comp() const;
337
- value_compare value_comp() const;
338
 
339
  // map operations
340
- iterator find(const key_type& x);
341
- const_iterator find(const key_type& x) const;
342
- template<class K> iterator find(const K& x);
343
- template<class K> const_iterator find(const K& x) const;
344
 
345
- size_type count(const key_type& x) const;
346
- template<class K> size_type count(const K& x) const;
347
 
348
- bool contains(const key_type& x) const;
349
- template<class K> bool contains(const K& x) const;
350
 
351
- iterator lower_bound(const key_type& x);
352
- const_iterator lower_bound(const key_type& x) const;
353
- template<class K> iterator lower_bound(const K& x);
354
- template<class K> const_iterator lower_bound(const K& x) const;
355
 
356
- iterator upper_bound(const key_type& x);
357
- const_iterator upper_bound(const key_type& x) const;
358
- template<class K> iterator upper_bound(const K& x);
359
- template<class K> const_iterator upper_bound(const K& x) const;
360
 
361
- pair<iterator, iterator> equal_range(const key_type& x);
362
- pair<const_iterator, const_iterator> equal_range(const key_type& x) const;
363
  template<class K>
364
- pair<iterator, iterator> equal_range(const K& x);
365
  template<class K>
366
- pair<const_iterator, const_iterator> equal_range(const K& x) const;
367
  };
368
 
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())
@@ -396,21 +350,21 @@ namespace std {
396
  ```
397
 
398
  #### Constructors, copy, and assignment <a id="map.cons">[[map.cons]]</a>
399
 
400
  ``` cpp
401
- explicit map(const Compare& comp, const Allocator& = Allocator());
402
  ```
403
 
404
  *Effects:* Constructs an empty `map` using the specified comparison
405
  object and allocator.
406
 
407
  *Complexity:* Constant.
408
 
409
  ``` cpp
410
  template<class InputIterator>
411
- map(InputIterator first, InputIterator last,
412
  const Compare& comp = Compare(), const Allocator& = Allocator());
413
  ```
414
 
415
  *Effects:* Constructs an empty `map` using the specified comparison
416
  object and allocator, and inserts elements from the range \[`first`,
@@ -420,11 +374,12 @@ object and allocator, and inserts elements from the range \[`first`,
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
 
@@ -432,55 +387,83 @@ object and allocator, and inserts elements from the range `rg`.
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);
438
  ```
439
 
440
  *Effects:* Equivalent to: `return try_emplace(x).first->second;`
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
  ```
453
 
454
  *Returns:* A reference to the `mapped_type` corresponding to `x` in
455
  `*this`.
456
 
457
  *Throws:* An exception object of type `out_of_range` if no such element
458
  is present.
459
 
460
  *Complexity:* Logarithmic.
461
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
462
  #### Modifiers <a id="map.modifiers">[[map.modifiers]]</a>
463
 
464
  ``` cpp
465
  template<class P>
466
- pair<iterator, bool> insert(P&& x);
467
  template<class P>
468
- iterator insert(const_iterator position, P&& x);
469
  ```
470
 
471
  *Constraints:* `is_constructible_v<value_type, P&&>` is `true`.
472
 
473
  *Effects:* The first form is equivalent to
474
  `return emplace(std::forward<P>(x))`. The second form is equivalent to
475
  `return emplace_hint(position, std::forward<P>(x))`.
476
 
477
  ``` cpp
478
  template<class... Args>
479
- pair<iterator, bool> try_emplace(const key_type& k, Args&&... args);
480
  template<class... Args>
481
- iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args);
482
  ```
483
 
484
  *Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into `map`
485
  from `piecewise_construct`, `forward_as_tuple(k)`,
486
  `forward_as_tuple(std::forward<Args>(args)...)`.
@@ -496,13 +479,13 @@ iterator points to the map element whose key is equivalent to `k`.
496
 
497
  *Complexity:* The same as `emplace` and `emplace_hint`, respectively.
498
 
499
  ``` cpp
500
  template<class... Args>
501
- pair<iterator, bool> try_emplace(key_type&& k, Args&&... args);
502
  template<class... Args>
503
- iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args);
504
  ```
505
 
506
  *Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into `map`
507
  from `piecewise_construct`, `forward_as_tuple(std::move(k))`,
508
  `forward_as_tuple(std::forward<Args>(args)...)`.
@@ -517,15 +500,44 @@ type `value_type` constructed with `piecewise_construct`,
517
  pair is `true` if and only if the insertion took place. The returned
518
  iterator points to the map element whose key is equivalent to `k`.
519
 
520
  *Complexity:* The same as `emplace` and `emplace_hint`, respectively.
521
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
522
  ``` cpp
523
  template<class M>
524
- pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj);
525
  template<class M>
526
- iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj);
527
  ```
528
 
529
  *Mandates:* `is_assignable_v<mapped_type&, M&&>` is `true`.
530
 
531
  *Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into `map`
@@ -542,13 +554,13 @@ iterator points to the map element whose key is equivalent to `k`.
542
 
543
  *Complexity:* The same as `emplace` and `emplace_hint`, respectively.
544
 
545
  ``` cpp
546
  template<class M>
547
- pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj);
548
  template<class M>
549
- iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj);
550
  ```
551
 
552
  *Mandates:* `is_assignable_v<mapped_type&, M&&>` is `true`.
553
 
554
  *Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into `map`
@@ -563,16 +575,44 @@ Otherwise inserts an object of type `value_type` constructed with
563
  pair is `true` if and only if the insertion took place. The returned
564
  iterator points to the map element whose key is equivalent to `k`.
565
 
566
  *Complexity:* The same as `emplace` and `emplace_hint`, respectively.
567
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
568
  #### Erasure <a id="map.erasure">[[map.erasure]]</a>
569
 
570
  ``` cpp
571
  template<class Key, class T, class Compare, class Allocator, class Predicate>
572
  typename map<Key, T, Compare, Allocator>::size_type
573
- erase_if(map<Key, T, Compare, Allocator>& c, Predicate pred);
574
  ```
575
 
576
  *Effects:* Equivalent to:
577
 
578
  ``` cpp
@@ -607,10 +647,13 @@ 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
609
  in one of those tables or for operations where there is additional
610
  semantic information.
611
 
 
 
 
612
  ``` cpp
613
  namespace std {
614
  template<class Key, class T, class Compare = less<Key>,
615
  class Allocator = allocator<pair<const Key, T>>>
616
  class multimap {
@@ -619,12 +662,12 @@ namespace std {
619
  using key_type = Key;
620
  using mapped_type = T;
621
  using value_type = pair<const Key, T>;
622
  using key_compare = Compare;
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]
@@ -632,148 +675,146 @@ namespace std {
632
  using reverse_iterator = std::reverse_iterator<iterator>;
633
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
634
  using node_type = unspecified;
635
 
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
  };
647
 
648
  // [multimap.cons], construct/copy/destroy
649
- multimap() : multimap(Compare()) { }
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)
677
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
678
  is_nothrow_move_assignable_v<Compare>);
679
- multimap& operator=(initializer_list<value_type>);
680
- allocator_type get_allocator() const noexcept;
681
 
682
  // iterators
683
- iterator begin() noexcept;
684
- const_iterator begin() const noexcept;
685
- iterator end() noexcept;
686
- const_iterator end() const noexcept;
687
 
688
- reverse_iterator rbegin() noexcept;
689
- const_reverse_iterator rbegin() const noexcept;
690
- reverse_iterator rend() noexcept;
691
- const_reverse_iterator rend() const noexcept;
692
 
693
- const_iterator cbegin() const noexcept;
694
- const_iterator cend() const noexcept;
695
- const_reverse_iterator crbegin() const noexcept;
696
- const_reverse_iterator crend() const noexcept;
697
 
698
  // capacity
699
- [[nodiscard]] bool empty() const noexcept;
700
- size_type size() const noexcept;
701
- size_type max_size() const noexcept;
702
 
703
  // [multimap.modifiers], modifiers
704
- template<class... Args> iterator emplace(Args&&... args);
705
- template<class... Args> iterator emplace_hint(const_iterator position, Args&&... args);
706
- iterator insert(const value_type& x);
707
- iterator insert(value_type&& x);
708
- template<class P> iterator insert(P&& 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;
733
 
734
  template<class C2>
735
- void merge(multimap<Key, T, C2, Allocator>& source);
736
  template<class C2>
737
- void merge(multimap<Key, T, C2, Allocator>&& source);
738
  template<class C2>
739
- void merge(map<Key, T, C2, Allocator>& source);
740
  template<class C2>
741
- void merge(map<Key, T, C2, Allocator>&& source);
742
 
743
  // observers
744
- key_compare key_comp() const;
745
- value_compare value_comp() const;
746
 
747
  // map operations
748
- iterator find(const key_type& x);
749
- const_iterator find(const key_type& x) const;
750
- template<class K> iterator find(const K& x);
751
- template<class K> const_iterator find(const K& x) const;
752
 
753
- size_type count(const key_type& x) const;
754
- template<class K> size_type count(const K& x) const;
755
 
756
- bool contains(const key_type& x) const;
757
- template<class K> bool contains(const K& x) const;
758
 
759
- iterator lower_bound(const key_type& x);
760
- const_iterator lower_bound(const key_type& x) const;
761
- template<class K> iterator lower_bound(const K& x);
762
- template<class K> const_iterator lower_bound(const K& x) const;
763
 
764
- iterator upper_bound(const key_type& x);
765
- const_iterator upper_bound(const key_type& x) const;
766
- template<class K> iterator upper_bound(const K& x);
767
- template<class K> const_iterator upper_bound(const K& x) const;
768
 
769
- pair<iterator, iterator> equal_range(const key_type& x);
770
- pair<const_iterator, const_iterator> equal_range(const key_type& x) const;
771
  template<class K>
772
- pair<iterator, iterator> equal_range(const K& x);
773
  template<class K>
774
- pair<const_iterator, const_iterator> equal_range(const K& x) const;
775
  };
776
 
777
  template<class InputIterator, class Compare = less<iter-key-type<InputIterator>>,
778
  class Allocator = allocator<iter-to-alloc-type<InputIterator>>>
779
  multimap(InputIterator, InputIterator, Compare = Compare(), Allocator = Allocator())
@@ -806,23 +847,22 @@ namespace std {
806
  ```
807
 
808
  #### Constructors <a id="multimap.cons">[[multimap.cons]]</a>
809
 
810
  ``` cpp
811
- explicit multimap(const Compare& comp, const Allocator& = Allocator());
812
  ```
813
 
814
  *Effects:* Constructs an empty `multimap` using the specified comparison
815
  object and allocator.
816
 
817
  *Complexity:* Constant.
818
 
819
  ``` cpp
820
  template<class InputIterator>
821
- multimap(InputIterator first, InputIterator last,
822
- const Compare& comp = Compare(),
823
- const Allocator& = Allocator());
824
  ```
825
 
826
  *Effects:* Constructs an empty `multimap` using the specified comparison
827
  object and allocator, and inserts elements from the range \[`first`,
828
  `last`).
@@ -831,11 +871,12 @@ object and allocator, and inserts elements from the range \[`first`,
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
 
@@ -843,12 +884,12 @@ object and allocator, and inserts elements from the range `rg`.
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);
849
- template<class P> iterator insert(const_iterator position, P&& x);
850
  ```
851
 
852
  *Constraints:* `is_constructible_v<value_type, P&&>` is `true`.
853
 
854
  *Effects:* The first form is equivalent to
@@ -858,11 +899,11 @@ template<class P> iterator insert(const_iterator position, P&& x);
858
  #### Erasure <a id="multimap.erasure">[[multimap.erasure]]</a>
859
 
860
  ``` cpp
861
  template<class Key, class T, class Compare, class Allocator, class Predicate>
862
  typename multimap<Key, T, Compare, Allocator>::size_type
863
- erase_if(multimap<Key, T, Compare, Allocator>& c, Predicate pred);
864
  ```
865
 
866
  *Effects:* Equivalent to:
867
 
868
  ``` cpp
@@ -875,10 +916,71 @@ for (auto i = c.begin(), last = c.end(); i != last; ) {
875
  }
876
  }
877
  return original_size - c.size();
878
  ```
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.,
@@ -887,19 +989,22 @@ 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>>
905
  class set {
@@ -908,12 +1013,12 @@ namespace std {
908
  using key_type = Key;
909
  using key_compare = Compare;
910
  using value_type = Key;
911
  using value_compare = Compare;
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]
@@ -922,132 +1027,136 @@ namespace std {
922
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
923
  using node_type = unspecified;
924
  using insert_return_type = insert-return-type<iterator, node_type>;
925
 
926
  // [set.cons], construct/copy/destroy
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)
952
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
953
  is_nothrow_move_assignable_v<Compare>);
954
- set& operator=(initializer_list<value_type>);
955
- allocator_type get_allocator() const noexcept;
956
 
957
  // iterators
958
- iterator begin() noexcept;
959
- const_iterator begin() const noexcept;
960
- iterator end() noexcept;
961
- const_iterator end() const noexcept;
962
 
963
- reverse_iterator rbegin() noexcept;
964
- const_reverse_iterator rbegin() const noexcept;
965
- reverse_iterator rend() noexcept;
966
- const_reverse_iterator rend() const noexcept;
967
 
968
- const_iterator cbegin() const noexcept;
969
- const_iterator cend() const noexcept;
970
- const_reverse_iterator crbegin() const noexcept;
971
- const_reverse_iterator crend() const noexcept;
972
 
973
  // capacity
974
- [[nodiscard]] bool empty() const noexcept;
975
- size_type size() const noexcept;
976
- size_type max_size() const noexcept;
977
 
978
- // modifiers
979
- template<class... Args> pair<iterator, bool> emplace(Args&&... args);
980
- template<class... Args> iterator emplace_hint(const_iterator position, Args&&... args);
981
- pair<iterator,bool> insert(const value_type& 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;
1007
 
1008
  template<class C2>
1009
- void merge(set<Key, C2, Allocator>& source);
1010
  template<class C2>
1011
- void merge(set<Key, C2, Allocator>&& source);
1012
  template<class C2>
1013
- void merge(multiset<Key, C2, Allocator>& source);
1014
  template<class C2>
1015
- void merge(multiset<Key, C2, Allocator>&& source);
1016
 
1017
  // observers
1018
- key_compare key_comp() const;
1019
- value_compare value_comp() const;
1020
 
1021
  // set operations
1022
- iterator find(const key_type& x);
1023
- const_iterator find(const key_type& x) const;
1024
- template<class K> iterator find(const K& x);
1025
- template<class K> const_iterator find(const K& x) const;
1026
 
1027
- size_type count(const key_type& x) const;
1028
- template<class K> size_type count(const K& x) const;
1029
 
1030
- bool contains(const key_type& x) const;
1031
- template<class K> bool contains(const K& x) const;
1032
 
1033
- iterator lower_bound(const key_type& x);
1034
- const_iterator lower_bound(const key_type& x) const;
1035
- template<class K> iterator lower_bound(const K& x);
1036
- template<class K> const_iterator lower_bound(const K& x) const;
1037
 
1038
- iterator upper_bound(const key_type& x);
1039
- const_iterator upper_bound(const key_type& x) const;
1040
- template<class K> iterator upper_bound(const K& x);
1041
- template<class K> const_iterator upper_bound(const K& x) const;
1042
 
1043
- pair<iterator, iterator> equal_range(const key_type& x);
1044
- pair<const_iterator, const_iterator> equal_range(const key_type& x) const;
1045
  template<class K>
1046
- pair<iterator, iterator> equal_range(const K& x);
1047
  template<class K>
1048
- pair<const_iterator, const_iterator> equal_range(const K& x) const;
1049
  };
1050
 
1051
  template<class InputIterator,
1052
  class Compare = less<iter-value-type<InputIterator>>,
1053
  class Allocator = allocator<iter-value-type<InputIterator>>>
@@ -1079,21 +1188,21 @@ namespace std {
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>
1094
- set(InputIterator first, InputIterator last,
1095
  const Compare& comp = Compare(), const Allocator& = Allocator());
1096
  ```
1097
 
1098
  *Effects:* Constructs an empty `set` using the specified comparison
1099
  object and allocator, and inserts elements from the range \[`first`,
@@ -1103,11 +1212,12 @@ object and allocator, and inserts elements from the range \[`first`,
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
 
@@ -1116,11 +1226,11 @@ object and allocator, and inserts elements from the range `rg`.
1116
 
1117
  #### Erasure <a id="set.erasure">[[set.erasure]]</a>
1118
 
1119
  ``` cpp
1120
  template<class Key, class Compare, class Allocator, class Predicate>
1121
- typename set<Key, Compare, Allocator>::size_type
1122
  erase_if(set<Key, Compare, Allocator>& c, Predicate pred);
1123
  ```
1124
 
1125
  *Effects:* Equivalent to:
1126
 
@@ -1134,10 +1244,37 @@ for (auto i = c.begin(), last = c.end(); i != last; ) {
1134
  }
1135
  }
1136
  return original_size - c.size();
1137
  ```
1138
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
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
@@ -1146,20 +1283,23 @@ 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
1158
  tables and for operations where there is additional semantic
1159
  information.
1160
 
 
 
 
1161
  ``` cpp
1162
  namespace std {
1163
  template<class Key, class Compare = less<Key>,
1164
  class Allocator = allocator<Key>>
1165
  class multiset {
@@ -1168,12 +1308,12 @@ namespace std {
1168
  using key_type = Key;
1169
  using key_compare = Compare;
1170
  using value_type = Key;
1171
  using value_compare = Compare;
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]
@@ -1181,133 +1321,134 @@ namespace std {
1181
  using reverse_iterator = std::reverse_iterator<iterator>;
1182
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
1183
  using node_type = unspecified;
1184
 
1185
  // [multiset.cons], construct/copy/destroy
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)
1212
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
1213
  is_nothrow_move_assignable_v<Compare>);
1214
- multiset& operator=(initializer_list<value_type>);
1215
- allocator_type get_allocator() const noexcept;
1216
 
1217
  // iterators
1218
- iterator begin() noexcept;
1219
- const_iterator begin() const noexcept;
1220
- iterator end() noexcept;
1221
- const_iterator end() const noexcept;
1222
 
1223
- reverse_iterator rbegin() noexcept;
1224
- const_reverse_iterator rbegin() const noexcept;
1225
- reverse_iterator rend() noexcept;
1226
- const_reverse_iterator rend() const noexcept;
1227
 
1228
- const_iterator cbegin() const noexcept;
1229
- const_iterator cend() const noexcept;
1230
- const_reverse_iterator crbegin() const noexcept;
1231
- const_reverse_iterator crend() const noexcept;
1232
 
1233
  // capacity
1234
- [[nodiscard]] bool empty() const noexcept;
1235
- size_type size() const noexcept;
1236
- size_type max_size() const noexcept;
1237
 
1238
  // modifiers
1239
- template<class... Args> iterator emplace(Args&&... args);
1240
- template<class... Args> iterator emplace_hint(const_iterator position, Args&&... args);
1241
- iterator insert(const value_type& 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;
1267
 
1268
  template<class C2>
1269
- void merge(multiset<Key, C2, Allocator>& source);
1270
  template<class C2>
1271
- void merge(multiset<Key, C2, Allocator>&& source);
1272
  template<class C2>
1273
- void merge(set<Key, C2, Allocator>& source);
1274
  template<class C2>
1275
- void merge(set<Key, C2, Allocator>&& source);
1276
 
1277
  // observers
1278
- key_compare key_comp() const;
1279
- value_compare value_comp() const;
1280
 
1281
  // set operations
1282
- iterator find(const key_type& x);
1283
- const_iterator find(const key_type& x) const;
1284
- template<class K> iterator find(const K& x);
1285
- template<class K> const_iterator find(const K& x) const;
1286
 
1287
- size_type count(const key_type& x) const;
1288
- template<class K> size_type count(const K& x) const;
1289
 
1290
- bool contains(const key_type& x) const;
1291
- template<class K> bool contains(const K& x) const;
1292
 
1293
- iterator lower_bound(const key_type& x);
1294
- const_iterator lower_bound(const key_type& x) const;
1295
- template<class K> iterator lower_bound(const K& x);
1296
- template<class K> const_iterator lower_bound(const K& x) const;
1297
 
1298
- iterator upper_bound(const key_type& x);
1299
- const_iterator upper_bound(const key_type& x) const;
1300
- template<class K> iterator upper_bound(const K& x);
1301
- template<class K> const_iterator upper_bound(const K& x) const;
1302
 
1303
- pair<iterator, iterator> equal_range(const key_type& x);
1304
- pair<const_iterator, const_iterator> equal_range(const key_type& x) const;
1305
  template<class K>
1306
- pair<iterator, iterator> equal_range(const K& x);
1307
  template<class K>
1308
- pair<const_iterator, const_iterator> equal_range(const K& x) const;
1309
  };
1310
 
1311
  template<class InputIterator,
1312
  class Compare = less<iter-value-type<InputIterator>>,
1313
  class Allocator = allocator<iter-value-type<InputIterator>>>
@@ -1339,21 +1480,21 @@ namespace std {
1339
  ```
1340
 
1341
  #### Constructors <a id="multiset.cons">[[multiset.cons]]</a>
1342
 
1343
  ``` cpp
1344
- explicit multiset(const Compare& comp, const Allocator& = Allocator());
1345
  ```
1346
 
1347
  *Effects:* Constructs an empty `multiset` using the specified comparison
1348
  object and allocator.
1349
 
1350
  *Complexity:* Constant.
1351
 
1352
  ``` cpp
1353
  template<class InputIterator>
1354
- multiset(InputIterator first, InputIterator last,
1355
  const Compare& comp = Compare(), const Allocator& = Allocator());
1356
  ```
1357
 
1358
  *Effects:* Constructs an empty `multiset` using the specified comparison
1359
  object and allocator, and inserts elements from the range \[`first`,
@@ -1363,11 +1504,12 @@ object and allocator, and inserts elements from the range \[`first`,
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
 
@@ -1376,11 +1518,11 @@ object and allocator, and inserts elements from the range `rg`.
1376
 
1377
  #### Erasure <a id="multiset.erasure">[[multiset.erasure]]</a>
1378
 
1379
  ``` cpp
1380
  template<class Key, class Compare, class Allocator, class Predicate>
1381
- typename multiset<Key, Compare, Allocator>::size_type
1382
  erase_if(multiset<Key, Compare, Allocator>& c, Predicate pred);
1383
  ```
1384
 
1385
  *Effects:* Equivalent to:
1386
 
 
1
  ## Associative containers <a id="associative">[[associative]]</a>
2
 
3
+ ### General <a id="associative.general">[[associative.general]]</a>
4
 
5
  The header `<map>` defines the class templates `map` and `multimap`; the
6
  header `<set>` defines the class templates `set` and `multiset`.
7
 
8
  The following exposition-only alias templates may appear in deduction
9
  guides for associative containers:
10
 
11
  ``` cpp
12
  template<class InputIterator>
13
+ using iter-value-type = iterator_traits<InputIterator>::value_type; // exposition only
 
14
  template<class InputIterator>
15
  using iter-key-type = remove_const_t<
16
  tuple_element_t<0, iter-value-type<InputIterator>>>; // exposition only
17
  template<class InputIterator>
18
  using iter-mapped-type =
19
  tuple_element_t<1, iter-value-type<InputIterator>>; // exposition only
20
  template<class InputIterator>
21
  using iter-to-alloc-type = pair<
22
+ const tuple_element_t<0, iter-value-type<InputIterator>>,
23
  tuple_element_t<1, iter-value-type<InputIterator>>>; // exposition only
24
  template<ranges::input_range Range>
25
  using range-key-type =
26
  remove_const_t<typename ranges::range_value_t<Range>::first_type>; // exposition only
27
  template<ranges::input_range Range>
28
+ using range-mapped-type = ranges::range_value_t<Range>::second_type; // exposition only
29
  template<ranges::input_range Range>
30
  using range-to-alloc-type =
31
+ pair<const typename ranges::range_value_t<Range>::first_type,
32
  typename ranges::range_value_t<Range>::second_type>; // exposition only
33
  ```
34
 
35
  ### Header `<map>` synopsis <a id="associative.map.syn">[[associative.map.syn]]</a>
36
 
 
43
  template<class Key, class T, class Compare = less<Key>,
44
  class Allocator = allocator<pair<const Key, T>>>
45
  class map;
46
 
47
  template<class Key, class T, class Compare, class Allocator>
48
+ constexpr bool operator==(const map<Key, T, Compare, Allocator>& x,
49
  const map<Key, T, Compare, Allocator>& y);
50
  template<class Key, class T, class Compare, class Allocator>
51
+ constexpr synth-three-way-result<pair<const Key, T>>
52
  operator<=>(const map<Key, T, Compare, Allocator>& x,
53
  const map<Key, T, Compare, Allocator>& y);
54
 
55
  template<class Key, class T, class Compare, class Allocator>
56
+ constexpr void swap(map<Key, T, Compare, Allocator>& x,
57
  map<Key, T, Compare, Allocator>& y)
58
  noexcept(noexcept(x.swap(y)));
59
 
60
  // [map.erasure], erasure for map
61
  template<class Key, class T, class Compare, class Allocator, class Predicate>
62
+ constexpr typename map<Key, T, Compare, Allocator>::size_type
63
  erase_if(map<Key, T, Compare, Allocator>& c, Predicate pred);
64
 
65
  // [multimap], class template multimap
66
  template<class Key, class T, class Compare = less<Key>,
67
  class Allocator = allocator<pair<const Key, T>>>
68
  class multimap;
69
 
70
  template<class Key, class T, class Compare, class Allocator>
71
+ constexpr bool operator==(const multimap<Key, T, Compare, Allocator>& x,
72
  const multimap<Key, T, Compare, Allocator>& y);
73
  template<class Key, class T, class Compare, class Allocator>
74
+ constexpr synth-three-way-result<pair<const Key, T>>
75
  operator<=>(const multimap<Key, T, Compare, Allocator>& x,
76
  const multimap<Key, T, Compare, Allocator>& y);
77
 
78
  template<class Key, class T, class Compare, class Allocator>
79
+ constexpr void swap(multimap<Key, T, Compare, Allocator>& x,
80
  multimap<Key, T, Compare, Allocator>& y)
81
  noexcept(noexcept(x.swap(y)));
82
 
83
  // [multimap.erasure], erasure for multimap
84
  template<class Key, class T, class Compare, class Allocator, class Predicate>
85
+ constexpr typename multimap<Key, T, Compare, Allocator>::size_type
86
  erase_if(multimap<Key, T, Compare, Allocator>& c, Predicate pred);
87
 
88
  namespace pmr {
89
  template<class Key, class T, class Compare = less<Key>>
90
  using map = std::map<Key, T, Compare,
 
95
  polymorphic_allocator<pair<const Key, T>>>;
96
  }
97
  }
98
  ```
99
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
100
  ### Class template `map` <a id="map">[[map]]</a>
101
 
102
  #### Overview <a id="map.overview">[[map.overview]]</a>
103
 
104
  A `map` is an associative container that supports unique keys (i.e.,
 
107
  supports bidirectional iterators.
108
 
109
  A `map` meets all of the requirements of a container
110
  [[container.reqmts]], of a reversible container
111
  [[container.rev.reqmts]], of an allocator-aware container
112
+ [[container.alloc.reqmts]], and of an associative container
113
  [[associative.reqmts]]. A `map` also provides most operations described
114
  in  [[associative.reqmts]] for unique keys. This means that a `map`
115
  supports the `a_uniq` operations in  [[associative.reqmts]] but not the
116
  `a_eq` operations. For a `map<Key,T>` the `key_type` is `Key` and the
117
  `value_type` is `pair<const Key,T>`. Descriptions are provided here only
118
  for operations on `map` that are not described in one of those tables or
119
  for operations where there is additional semantic information.
120
 
121
+ The types `iterator` and `const_iterator` meet the constexpr iterator
122
+ requirements [[iterator.requirements.general]].
123
+
124
  ``` cpp
125
  namespace std {
126
  template<class Key, class T, class Compare = less<Key>,
127
  class Allocator = allocator<pair<const Key, T>>>
128
  class map {
 
131
  using key_type = Key;
132
  using mapped_type = T;
133
  using value_type = pair<const Key, T>;
134
  using key_compare = Compare;
135
  using allocator_type = Allocator;
136
+ using pointer = allocator_traits<Allocator>::pointer;
137
+ using const_pointer = allocator_traits<Allocator>::const_pointer;
138
  using reference = value_type&;
139
  using const_reference = const value_type&;
140
  using size_type = implementation-defined // type of map::size_type; // see [container.requirements]
141
  using difference_type = implementation-defined // type of map::difference_type; // see [container.requirements]
142
  using iterator = implementation-defined // type of map::iterator; // see [container.requirements]
 
145
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
146
  using node_type = unspecified;
147
  using insert_return_type = insert-return-type<iterator, node_type>;
148
 
149
  class value_compare {
 
150
  protected:
151
  Compare comp;
152
+ constexpr value_compare(Compare c) : comp(c) {}
153
 
154
  public:
155
+ constexpr bool operator()(const value_type& x, const value_type& y) const {
156
  return comp(x.first, y.first);
157
  }
158
  };
159
 
160
  // [map.cons], construct/copy/destroy
161
+ constexpr map() : map(Compare()) { }
162
+ constexpr explicit map(const Compare& comp, const Allocator& = Allocator());
163
  template<class InputIterator>
164
+ constexpr map(InputIterator first, InputIterator last,
165
  const Compare& comp = Compare(), const Allocator& = Allocator());
166
  template<container-compatible-range<value_type> R>
167
+ constexpr map(from_range_t, R&& rg, const Compare& comp = Compare(),
168
+ const Allocator& = Allocator());
169
+ constexpr map(const map& x);
170
+ constexpr map(map&& x);
171
  explicit map(const Allocator&);
172
+ constexpr map(const map&, const type_identity_t<Allocator>&);
173
+ constexpr map(map&&, const type_identity_t<Allocator>&);
174
+ constexpr map(initializer_list<value_type>, const Compare& = Compare(),
 
175
  const Allocator& = Allocator());
176
  template<class InputIterator>
177
+ constexpr map(InputIterator first, InputIterator last, const Allocator& a)
178
  : map(first, last, Compare(), a) { }
179
  template<container-compatible-range<value_type> R>
180
+ constexpr map(from_range_t, R&& rg, const Allocator& a)
181
  : map(from_range, std::forward<R>(rg), Compare(), a) { }
182
+ constexpr map(initializer_list<value_type> il, const Allocator& a)
183
  : map(il, Compare(), a) { }
184
+ constexpr ~map();
185
+ constexpr map& operator=(const map& x);
186
+ constexpr map& operator=(map&& x)
187
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
188
  is_nothrow_move_assignable_v<Compare>);
189
+ constexpr map& operator=(initializer_list<value_type>);
190
+ constexpr allocator_type get_allocator() const noexcept;
191
 
192
  // iterators
193
+ constexpr iterator begin() noexcept;
194
+ constexpr const_iterator begin() const noexcept;
195
+ constexpr iterator end() noexcept;
196
+ constexpr const_iterator end() const noexcept;
197
 
198
+ constexpr reverse_iterator rbegin() noexcept;
199
+ constexpr const_reverse_iterator rbegin() const noexcept;
200
+ constexpr reverse_iterator rend() noexcept;
201
+ constexpr const_reverse_iterator rend() const noexcept;
202
 
203
+ constexpr const_iterator cbegin() const noexcept;
204
+ constexpr const_iterator cend() const noexcept;
205
+ constexpr const_reverse_iterator crbegin() const noexcept;
206
+ constexpr const_reverse_iterator crend() const noexcept;
207
 
208
  // capacity
209
+ constexpr bool empty() const noexcept;
210
+ constexpr size_type size() const noexcept;
211
+ constexpr size_type max_size() const noexcept;
212
 
213
  // [map.access], element access
214
+ constexpr mapped_type& operator[](const key_type& x);
215
+ constexpr mapped_type& operator[](key_type&& x);
216
+ template<class K> constexpr mapped_type& operator[](K&& x);
217
+ constexpr mapped_type& at(const key_type& x);
218
+ constexpr const mapped_type& at(const key_type& x) const;
219
+ template<class K> constexpr mapped_type& at(const K& x);
220
+ template<class K> constexpr const mapped_type& at(const K& x) const;
221
 
222
  // [map.modifiers], modifiers
223
+ template<class... Args> constexpr pair<iterator, bool> emplace(Args&&... args);
224
+ template<class... Args>
225
+ constexpr iterator emplace_hint(const_iterator position, Args&&... args);
226
+ constexpr pair<iterator, bool> insert(const value_type& x);
227
+ constexpr pair<iterator, bool> insert(value_type&& x);
228
+ template<class P> constexpr pair<iterator, bool> insert(P&& x);
229
+ constexpr iterator insert(const_iterator position, const value_type& x);
230
+ constexpr iterator insert(const_iterator position, value_type&& x);
231
  template<class P>
232
+ constexpr iterator insert(const_iterator position, P&&);
233
  template<class InputIterator>
234
+ constexpr void insert(InputIterator first, InputIterator last);
235
  template<container-compatible-range<value_type> R>
236
+ constexpr void insert_range(R&& rg);
237
+ constexpr void insert(initializer_list<value_type>);
238
 
239
+ constexpr node_type extract(const_iterator position);
240
+ constexpr node_type extract(const key_type& x);
241
+ template<class K> constexpr node_type extract(K&& x);
242
+ constexpr insert_return_type insert(node_type&& nh);
243
+ constexpr iterator insert(const_iterator hint, node_type&& nh);
244
 
245
  template<class... Args>
246
+ constexpr pair<iterator, bool> try_emplace(const key_type& k, Args&&... args);
247
  template<class... Args>
248
+ constexpr pair<iterator, bool> try_emplace(key_type&& k, Args&&... args);
249
+ template<class K, class... Args>
250
+ constexpr pair<iterator, bool> try_emplace(K&& k, Args&&... args);
251
  template<class... Args>
252
+ constexpr iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args);
253
  template<class... Args>
254
+ constexpr iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args);
255
+ template<class K, class... Args>
256
+ constexpr iterator try_emplace(const_iterator hint, K&& k, Args&&... args);
257
  template<class M>
258
+ constexpr pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj);
259
  template<class M>
260
+ constexpr pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj);
261
+ template<class K, class M>
262
+ constexpr pair<iterator, bool> insert_or_assign(K&& k, M&& obj);
263
  template<class M>
264
+ constexpr iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj);
265
  template<class M>
266
+ constexpr iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj);
267
+ template<class K, class M>
268
+ constexpr iterator insert_or_assign(const_iterator hint, K&& k, M&& obj);
269
 
270
+ constexpr iterator erase(iterator position);
271
+ constexpr iterator erase(const_iterator position);
272
+ constexpr size_type erase(const key_type& x);
273
+ template<class K> constexpr size_type erase(K&& x);
274
+ constexpr iterator erase(const_iterator first, const_iterator last);
275
+ constexpr void swap(map&)
276
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
277
  is_nothrow_swappable_v<Compare>);
278
+ constexpr void clear() noexcept;
279
 
280
  template<class C2>
281
+ constexpr void merge(map<Key, T, C2, Allocator>& source);
282
  template<class C2>
283
+ constexpr void merge(map<Key, T, C2, Allocator>&& source);
284
  template<class C2>
285
+ constexpr void merge(multimap<Key, T, C2, Allocator>& source);
286
  template<class C2>
287
+ constexpr void merge(multimap<Key, T, C2, Allocator>&& source);
288
 
289
  // observers
290
+ constexpr key_compare key_comp() const;
291
+ constexpr value_compare value_comp() const;
292
 
293
  // map operations
294
+ constexpr iterator find(const key_type& x);
295
+ constexpr const_iterator find(const key_type& x) const;
296
+ template<class K> constexpr iterator find(const K& x);
297
+ template<class K> constexpr const_iterator find(const K& x) const;
298
 
299
+ constexpr size_type count(const key_type& x) const;
300
+ template<class K> constexpr size_type count(const K& x) const;
301
 
302
+ constexpr bool contains(const key_type& x) const;
303
+ template<class K> constexpr bool contains(const K& x) const;
304
 
305
+ constexpr iterator lower_bound(const key_type& x);
306
+ constexpr const_iterator lower_bound(const key_type& x) const;
307
+ template<class K> constexpr iterator lower_bound(const K& x);
308
+ template<class K> constexpr const_iterator lower_bound(const K& x) const;
309
 
310
+ constexpr iterator upper_bound(const key_type& x);
311
+ constexpr const_iterator upper_bound(const key_type& x) const;
312
+ template<class K> constexpr iterator upper_bound(const K& x);
313
+ template<class K> constexpr const_iterator upper_bound(const K& x) const;
314
 
315
+ constexpr pair<iterator, iterator> equal_range(const key_type& x);
316
+ constexpr pair<const_iterator, const_iterator> equal_range(const key_type& x) const;
317
  template<class K>
318
+ constexpr pair<iterator, iterator> equal_range(const K& x);
319
  template<class K>
320
+ constexpr pair<const_iterator, const_iterator> equal_range(const K& x) const;
321
  };
322
 
323
  template<class InputIterator, class Compare = less<iter-key-type<InputIterator>>,
324
  class Allocator = allocator<iter-to-alloc-type<InputIterator>>>
325
  map(InputIterator, InputIterator, Compare = Compare(), Allocator = Allocator())
 
350
  ```
351
 
352
  #### Constructors, copy, and assignment <a id="map.cons">[[map.cons]]</a>
353
 
354
  ``` cpp
355
+ constexpr explicit map(const Compare& comp, const Allocator& = Allocator());
356
  ```
357
 
358
  *Effects:* Constructs an empty `map` using the specified comparison
359
  object and allocator.
360
 
361
  *Complexity:* Constant.
362
 
363
  ``` cpp
364
  template<class InputIterator>
365
+ constexpr map(InputIterator first, InputIterator last,
366
  const Compare& comp = Compare(), const Allocator& = Allocator());
367
  ```
368
 
369
  *Effects:* Constructs an empty `map` using the specified comparison
370
  object and allocator, and inserts elements from the range \[`first`,
 
374
  sorted with respect to `comp` and otherwise N log N, where N is
375
  `last - first`.
376
 
377
  ``` cpp
378
  template<container-compatible-range<value_type> R>
379
+ constexpr map(from_range_t, R&& rg, const Compare& comp = Compare(),
380
+ const Allocator& = Allocator());
381
  ```
382
 
383
  *Effects:* Constructs an empty `map` using the specified comparison
384
  object and allocator, and inserts elements from the range `rg`.
385
 
 
387
  `comp` and otherwise N log N, where N is `ranges::distance(rg)`.
388
 
389
  #### Element access <a id="map.access">[[map.access]]</a>
390
 
391
  ``` cpp
392
+ constexpr mapped_type& operator[](const key_type& x);
393
  ```
394
 
395
  *Effects:* Equivalent to: `return try_emplace(x).first->second;`
396
 
397
  ``` cpp
398
+ constexpr mapped_type& operator[](key_type&& x);
399
  ```
400
 
401
  *Effects:* Equivalent to:
402
  `return try_emplace(std::move(x)).first->second;`
403
 
404
  ``` cpp
405
+ template<class K> constexpr mapped_type& operator[](K&& x);
406
+ ```
407
+
408
+ *Constraints:* The *qualified-id* `Compare::is_transparent` is valid and
409
+ denotes a type.
410
+
411
+ *Effects:* Equivalent to:
412
+ `return try_emplace(std::forward<K>(x)).first->second;`
413
+
414
+ ``` cpp
415
+ constexpr mapped_type& at(const key_type& x);
416
+ constexpr const mapped_type& at(const key_type& x) const;
417
  ```
418
 
419
  *Returns:* A reference to the `mapped_type` corresponding to `x` in
420
  `*this`.
421
 
422
  *Throws:* An exception object of type `out_of_range` if no such element
423
  is present.
424
 
425
  *Complexity:* Logarithmic.
426
 
427
+ ``` cpp
428
+ template<class K> constexpr mapped_type& at(const K& x);
429
+ template<class K> constexpr const mapped_type& at(const K& x) const;
430
+ ```
431
+
432
+ *Constraints:* The *qualified-id* `Compare::is_transparent` is valid and
433
+ denotes a type.
434
+
435
+ *Preconditions:* The expression `find(x)` is well-formed and has
436
+ well-defined behavior.
437
+
438
+ *Returns:* A reference to `find(x)->second`.
439
+
440
+ *Throws:* An exception object of type `out_of_range` if
441
+ `find(x) == end()` is `true`.
442
+
443
+ *Complexity:* Logarithmic.
444
+
445
  #### Modifiers <a id="map.modifiers">[[map.modifiers]]</a>
446
 
447
  ``` cpp
448
  template<class P>
449
+ constexpr pair<iterator, bool> insert(P&& x);
450
  template<class P>
451
+ constexpr iterator insert(const_iterator position, P&& x);
452
  ```
453
 
454
  *Constraints:* `is_constructible_v<value_type, P&&>` is `true`.
455
 
456
  *Effects:* The first form is equivalent to
457
  `return emplace(std::forward<P>(x))`. The second form is equivalent to
458
  `return emplace_hint(position, std::forward<P>(x))`.
459
 
460
  ``` cpp
461
  template<class... Args>
462
+ constexpr pair<iterator, bool> try_emplace(const key_type& k, Args&&... args);
463
  template<class... Args>
464
+ constexpr iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args);
465
  ```
466
 
467
  *Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into `map`
468
  from `piecewise_construct`, `forward_as_tuple(k)`,
469
  `forward_as_tuple(std::forward<Args>(args)...)`.
 
479
 
480
  *Complexity:* The same as `emplace` and `emplace_hint`, respectively.
481
 
482
  ``` cpp
483
  template<class... Args>
484
+ constexpr pair<iterator, bool> try_emplace(key_type&& k, Args&&... args);
485
  template<class... Args>
486
+ constexpr iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args);
487
  ```
488
 
489
  *Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into `map`
490
  from `piecewise_construct`, `forward_as_tuple(std::move(k))`,
491
  `forward_as_tuple(std::forward<Args>(args)...)`.
 
500
  pair is `true` if and only if the insertion took place. The returned
501
  iterator points to the map element whose key is equivalent to `k`.
502
 
503
  *Complexity:* The same as `emplace` and `emplace_hint`, respectively.
504
 
505
+ ``` cpp
506
+ template<class K, class... Args>
507
+ constexpr pair<iterator, bool> try_emplace(K&& k, Args&&... args);
508
+ template<class K, class... Args>
509
+ constexpr iterator try_emplace(const_iterator hint, K&& k, Args&&... args);
510
+ ```
511
+
512
+ *Constraints:* The *qualified-id* `Compare::is_transparent` is valid and
513
+ denotes a type. For the first overload,
514
+ `is_convertible_v<K&&, const_iterator>` and
515
+ `is_convertible_v<K&&, iterator>` are both `false`.
516
+
517
+ *Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into `map`
518
+ from
519
+ `piecewise_construct, forward_as_tuple(std::forward<K>(k)), forward_as_tuple(std::forward<Args>(args)...)`.
520
+
521
+ *Effects:* If the map already contains an element whose key is
522
+ equivalent to `k`, there is no effect. Otherwise, let `r` be
523
+ `equal_range(k)`. Constructs an object `u` of type `value_type` with
524
+ `piecewise_construct, forward_as_tuple(std::forward<K>(k)), forward_as_tuple(std::forward<Args>(args)...)`.
525
+ If `equal_range(u.first) == r` is `false`, the behavior is undefined.
526
+ Inserts `u` into `*this`.
527
+
528
+ *Returns:* For the first overload, the `bool` component of the returned
529
+ pair is `true` if and only if the insertion took place. The returned
530
+ iterator points to the map element whose key is equivalent to `k`.
531
+
532
+ *Complexity:* The same as `emplace` and `emplace_hint`, respectively.
533
+
534
  ``` cpp
535
  template<class M>
536
+ constexpr pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj);
537
  template<class M>
538
+ constexpr iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj);
539
  ```
540
 
541
  *Mandates:* `is_assignable_v<mapped_type&, M&&>` is `true`.
542
 
543
  *Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into `map`
 
554
 
555
  *Complexity:* The same as `emplace` and `emplace_hint`, respectively.
556
 
557
  ``` cpp
558
  template<class M>
559
+ constexpr pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj);
560
  template<class M>
561
+ constexpr iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj);
562
  ```
563
 
564
  *Mandates:* `is_assignable_v<mapped_type&, M&&>` is `true`.
565
 
566
  *Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into `map`
 
575
  pair is `true` if and only if the insertion took place. The returned
576
  iterator points to the map element whose key is equivalent to `k`.
577
 
578
  *Complexity:* The same as `emplace` and `emplace_hint`, respectively.
579
 
580
+ ``` cpp
581
+ template<class K, class M>
582
+ constexpr pair<iterator, bool> insert_or_assign(K&& k, M&& obj);
583
+ template<class K, class M>
584
+ constexpr iterator insert_or_assign(const_iterator hint, K&& k, M&& obj);
585
+ ```
586
+
587
+ *Constraints:* The *qualified-id* `Compare::is_transparent` is valid and
588
+ denotes a type.
589
+
590
+ *Mandates:* `is_assignable_v<mapped_type&, M&&>` is `true`.
591
+
592
+ *Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into `map`
593
+ from `std::forward<K>(k), std:: forward<M>(obj)`.
594
+
595
+ *Effects:* If the map already contains an element `e` whose key is
596
+ equivalent to `k`, assigns `std::forward<M> (obj)` to `e.second`.
597
+ Otherwise, let `r` be `equal_range(k)`. Constructs an object `u` of type
598
+ `value_type` with `std::forward<K>(k), std::forward<M>(obj)`. If
599
+ `equal_range(u.first) == r` is `false`, the behavior is undefined.
600
+ Inserts `u` into `*this`.
601
+
602
+ *Returns:* For the first overload, the `bool` component of the returned
603
+ pair is `true` if and only if the insertion took place. The returned
604
+ iterator points to the map element whose key is equivalent to `k`.
605
+
606
+ *Complexity:* The same as `emplace` and `emplace_hint`, respectively.
607
+
608
  #### Erasure <a id="map.erasure">[[map.erasure]]</a>
609
 
610
  ``` cpp
611
  template<class Key, class T, class Compare, class Allocator, class Predicate>
612
  typename map<Key, T, Compare, Allocator>::size_type
613
+ constexpr erase_if(map<Key, T, Compare, Allocator>& c, Predicate pred);
614
  ```
615
 
616
  *Effects:* Equivalent to:
617
 
618
  ``` cpp
 
647
  `Key` and the `value_type` is `pair<const Key,T>`. Descriptions are
648
  provided here only for operations on `multimap` that are not described
649
  in one of those tables or for operations where there is additional
650
  semantic information.
651
 
652
+ The types `iterator` and `const_iterator` meet the constexpr iterator
653
+ requirements [[iterator.requirements.general]].
654
+
655
  ``` cpp
656
  namespace std {
657
  template<class Key, class T, class Compare = less<Key>,
658
  class Allocator = allocator<pair<const Key, T>>>
659
  class multimap {
 
662
  using key_type = Key;
663
  using mapped_type = T;
664
  using value_type = pair<const Key, T>;
665
  using key_compare = Compare;
666
  using allocator_type = Allocator;
667
+ using pointer = allocator_traits<Allocator>::pointer;
668
+ using const_pointer = allocator_traits<Allocator>::const_pointer;
669
  using reference = value_type&;
670
  using const_reference = const value_type&;
671
  using size_type = implementation-defined // type of multimap::size_type; // see [container.requirements]
672
  using difference_type = implementation-defined // type of multimap::difference_type; // see [container.requirements]
673
  using iterator = implementation-defined // type of multimap::iterator; // see [container.requirements]
 
675
  using reverse_iterator = std::reverse_iterator<iterator>;
676
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
677
  using node_type = unspecified;
678
 
679
  class value_compare {
 
680
  protected:
681
  Compare comp;
682
+ constexpr value_compare(Compare c) : comp(c) { }
683
 
684
  public:
685
+ constexpr bool operator()(const value_type& x, const value_type& y) const {
686
  return comp(x.first, y.first);
687
  }
688
  };
689
 
690
  // [multimap.cons], construct/copy/destroy
691
+ constexpr multimap() : multimap(Compare()) { }
692
+ constexpr explicit multimap(const Compare& comp, const Allocator& = Allocator());
693
  template<class InputIterator>
694
+ constexpr multimap(InputIterator first, InputIterator last,
695
+ const Compare& comp = Compare(), const Allocator& = Allocator());
 
696
  template<container-compatible-range<value_type> R>
697
+ constexpr multimap(from_range_t, R&& rg,
698
  const Compare& comp = Compare(), const Allocator& = Allocator());
699
+ constexpr multimap(const multimap& x);
700
+ constexpr multimap(multimap&& x);
701
+ constexpr explicit multimap(const Allocator&);
702
+ constexpr multimap(const multimap&, const type_identity_t<Allocator>&);
703
+ constexpr multimap(multimap&&, const type_identity_t<Allocator>&);
704
+ constexpr multimap(initializer_list<value_type>,
705
+ const Compare& = Compare(), const Allocator& = Allocator());
 
706
  template<class InputIterator>
707
+ constexpr multimap(InputIterator first, InputIterator last, const Allocator& a)
708
  : multimap(first, last, Compare(), a) { }
709
  template<container-compatible-range<value_type> R>
710
+ constexpr multimap(from_range_t, R&& rg, const Allocator& a)
711
  : multimap(from_range, std::forward<R>(rg), Compare(), a) { }
712
+ constexpr multimap(initializer_list<value_type> il, const Allocator& a)
713
  : multimap(il, Compare(), a) { }
714
+ constexpr ~multimap();
715
+ constexpr multimap& operator=(const multimap& x);
716
+ constexpr multimap& operator=(multimap&& x)
717
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
718
  is_nothrow_move_assignable_v<Compare>);
719
+ constexpr multimap& operator=(initializer_list<value_type>);
720
+ constexpr allocator_type get_allocator() const noexcept;
721
 
722
  // iterators
723
+ constexpr iterator begin() noexcept;
724
+ constexpr const_iterator begin() const noexcept;
725
+ constexpr iterator end() noexcept;
726
+ constexpr const_iterator end() const noexcept;
727
 
728
+ constexpr reverse_iterator rbegin() noexcept;
729
+ constexpr const_reverse_iterator rbegin() const noexcept;
730
+ constexpr reverse_iterator rend() noexcept;
731
+ constexpr const_reverse_iterator rend() const noexcept;
732
 
733
+ constexpr const_iterator cbegin() const noexcept;
734
+ constexpr const_iterator cend() const noexcept;
735
+ constexpr const_reverse_iterator crbegin() const noexcept;
736
+ constexpr const_reverse_iterator crend() const noexcept;
737
 
738
  // capacity
739
+ constexpr bool empty() const noexcept;
740
+ constexpr size_type size() const noexcept;
741
+ constexpr size_type max_size() const noexcept;
742
 
743
  // [multimap.modifiers], modifiers
744
+ template<class... Args> constexpr iterator emplace(Args&&... args);
745
+ template<class... Args>
746
+ constexpr iterator emplace_hint(const_iterator position, Args&&... args);
747
+ constexpr iterator insert(const value_type& x);
748
+ constexpr iterator insert(value_type&& x);
749
+ template<class P> constexpr iterator insert(P&& x);
750
+ constexpr iterator insert(const_iterator position, const value_type& x);
751
+ constexpr iterator insert(const_iterator position, value_type&& x);
752
+ template<class P> constexpr iterator insert(const_iterator position, P&& x);
753
  template<class InputIterator>
754
+ constexpr void insert(InputIterator first, InputIterator last);
755
  template<container-compatible-range<value_type> R>
756
+ constexpr void insert_range(R&& rg);
757
+ constexpr void insert(initializer_list<value_type>);
758
 
759
+ constexpr node_type extract(const_iterator position);
760
+ constexpr node_type extract(const key_type& x);
761
  template<class K> node_type extract(K&& x);
762
+ constexpr iterator insert(node_type&& nh);
763
+ constexpr iterator insert(const_iterator hint, node_type&& nh);
764
 
765
+ constexpr iterator erase(iterator position);
766
+ constexpr iterator erase(const_iterator position);
767
+ constexpr size_type erase(const key_type& x);
768
+ template<class K> constexpr size_type erase(K&& x);
769
+ constexpr iterator erase(const_iterator first, const_iterator last);
770
+ constexpr void swap(multimap&)
771
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
772
  is_nothrow_swappable_v<Compare>);
773
+ constexpr void clear() noexcept;
774
 
775
  template<class C2>
776
+ constexpr void merge(multimap<Key, T, C2, Allocator>& source);
777
  template<class C2>
778
+ constexpr void merge(multimap<Key, T, C2, Allocator>&& source);
779
  template<class C2>
780
+ constexpr void merge(map<Key, T, C2, Allocator>& source);
781
  template<class C2>
782
+ constexpr void merge(map<Key, T, C2, Allocator>&& source);
783
 
784
  // observers
785
+ constexpr key_compare key_comp() const;
786
+ constexpr value_compare value_comp() const;
787
 
788
  // map operations
789
+ constexpr iterator find(const key_type& x);
790
+ constexpr const_iterator find(const key_type& x) const;
791
+ template<class K> constexpr iterator find(const K& x);
792
+ template<class K> constexpr const_iterator find(const K& x) const;
793
 
794
+ constexpr size_type count(const key_type& x) const;
795
+ template<class K> constexpr size_type count(const K& x) const;
796
 
797
+ constexpr bool contains(const key_type& x) const;
798
+ template<class K> constexpr bool contains(const K& x) const;
799
 
800
+ constexpr iterator lower_bound(const key_type& x);
801
+ constexpr const_iterator lower_bound(const key_type& x) const;
802
+ template<class K> constexpr iterator lower_bound(const K& x);
803
+ template<class K> constexpr const_iterator lower_bound(const K& x) const;
804
 
805
+ constexpr iterator upper_bound(const key_type& x);
806
+ constexpr const_iterator upper_bound(const key_type& x) const;
807
+ template<class K> constexpr iterator upper_bound(const K& x);
808
+ template<class K> constexpr const_iterator upper_bound(const K& x) const;
809
 
810
+ constexpr pair<iterator, iterator> equal_range(const key_type& x);
811
+ constexpr pair<const_iterator, const_iterator> equal_range(const key_type& x) const;
812
  template<class K>
813
+ constexpr pair<iterator, iterator> equal_range(const K& x);
814
  template<class K>
815
+ constexpr pair<const_iterator, const_iterator> equal_range(const K& x) const;
816
  };
817
 
818
  template<class InputIterator, class Compare = less<iter-key-type<InputIterator>>,
819
  class Allocator = allocator<iter-to-alloc-type<InputIterator>>>
820
  multimap(InputIterator, InputIterator, Compare = Compare(), Allocator = Allocator())
 
847
  ```
848
 
849
  #### Constructors <a id="multimap.cons">[[multimap.cons]]</a>
850
 
851
  ``` cpp
852
+ constexpr explicit multimap(const Compare& comp, const Allocator& = Allocator());
853
  ```
854
 
855
  *Effects:* Constructs an empty `multimap` using the specified comparison
856
  object and allocator.
857
 
858
  *Complexity:* Constant.
859
 
860
  ``` cpp
861
  template<class InputIterator>
862
+ constexpr multimap(InputIterator first, InputIterator last,
863
+ const Compare& comp = Compare(), const Allocator& = Allocator());
 
864
  ```
865
 
866
  *Effects:* Constructs an empty `multimap` using the specified comparison
867
  object and allocator, and inserts elements from the range \[`first`,
868
  `last`).
 
871
  sorted with respect to `comp` and otherwise N log N, where N is
872
  `last - first`.
873
 
874
  ``` cpp
875
  template<container-compatible-range<value_type> R>
876
+ constexpr multimap(from_range_t, R&& rg,
877
+ const Compare& comp = Compare(), const Allocator& = Allocator());
878
  ```
879
 
880
  *Effects:* Constructs an empty `multimap` using the specified comparison
881
  object and allocator, and inserts elements from the range `rg`.
882
 
 
884
  `comp` and otherwise N log N, where N is `ranges::distance(rg)`.
885
 
886
  #### Modifiers <a id="multimap.modifiers">[[multimap.modifiers]]</a>
887
 
888
  ``` cpp
889
+ template<class P> constexpr iterator insert(P&& x);
890
+ template<class P> constexpr iterator insert(const_iterator position, P&& x);
891
  ```
892
 
893
  *Constraints:* `is_constructible_v<value_type, P&&>` is `true`.
894
 
895
  *Effects:* The first form is equivalent to
 
899
  #### Erasure <a id="multimap.erasure">[[multimap.erasure]]</a>
900
 
901
  ``` cpp
902
  template<class Key, class T, class Compare, class Allocator, class Predicate>
903
  typename multimap<Key, T, Compare, Allocator>::size_type
904
+ constexpr erase_if(multimap<Key, T, Compare, Allocator>& c, Predicate pred);
905
  ```
906
 
907
  *Effects:* Equivalent to:
908
 
909
  ``` cpp
 
916
  }
917
  }
918
  return original_size - c.size();
919
  ```
920
 
921
+ ### Header `<set>` synopsis <a id="associative.set.syn">[[associative.set.syn]]</a>
922
+
923
+ ``` cpp
924
+ #include <compare> // see [compare.syn]
925
+ #include <initializer_list> // see [initializer.list.syn]
926
+
927
+ namespace std {
928
+ // [set], class template set
929
+ template<class Key, class Compare = less<Key>, class Allocator = allocator<Key>>
930
+ class set;
931
+
932
+ template<class Key, class Compare, class Allocator>
933
+ constexpr bool operator==(const set<Key, Compare, Allocator>& x,
934
+ const set<Key, Compare, Allocator>& y);
935
+ template<class Key, class Compare, class Allocator>
936
+ constexpr synth-three-way-result<Key>
937
+ operator<=>(const set<Key, Compare, Allocator>& x,
938
+ const set<Key, Compare, Allocator>& y);
939
+
940
+ template<class Key, class Compare, class Allocator>
941
+ constexpr void swap(set<Key, Compare, Allocator>& x,
942
+ set<Key, Compare, Allocator>& y)
943
+ noexcept(noexcept(x.swap(y)));
944
+
945
+ // [set.erasure], erasure for set
946
+ template<class Key, class Compare, class Allocator, class Predicate>
947
+ constexpr typename set<Key, Compare, Allocator>::size_type
948
+ erase_if(set<Key, Compare, Allocator>& c, Predicate pred);
949
+
950
+ // [multiset], class template multiset
951
+ template<class Key, class Compare = less<Key>, class Allocator = allocator<Key>>
952
+ class multiset;
953
+
954
+ template<class Key, class Compare, class Allocator>
955
+ constexpr bool operator==(const multiset<Key, Compare, Allocator>& x,
956
+ const multiset<Key, Compare, Allocator>& y);
957
+ template<class Key, class Compare, class Allocator>
958
+ constexpr synth-three-way-result<Key>
959
+ operator<=>(const multiset<Key, Compare, Allocator>& x,
960
+ const multiset<Key, Compare, Allocator>& y);
961
+
962
+ template<class Key, class Compare, class Allocator>
963
+ constexpr void swap(multiset<Key, Compare, Allocator>& x,
964
+ multiset<Key, Compare, Allocator>& y)
965
+ noexcept(noexcept(x.swap(y)));
966
+
967
+ // [multiset.erasure], erasure for multiset
968
+ template<class Key, class Compare, class Allocator, class Predicate>
969
+ constexpr typename multiset<Key, Compare, Allocator>::size_type
970
+ erase_if(multiset<Key, Compare, Allocator>& c, Predicate pred);
971
+
972
+ namespace pmr {
973
+ template<class Key, class Compare = less<Key>>
974
+ using set = std::set<Key, Compare, polymorphic_allocator<Key>>;
975
+
976
+ template<class Key, class Compare = less<Key>>
977
+ using multiset = std::multiset<Key, Compare, polymorphic_allocator<Key>>;
978
+ }
979
+ }
980
+ ```
981
+
982
  ### Class template `set` <a id="set">[[set]]</a>
983
 
984
  #### Overview <a id="set.overview">[[set.overview]]</a>
985
 
986
  A `set` is an associative container that supports unique keys (i.e.,
 
989
  iterators.
990
 
991
  A `set` meets all of the requirements of a container
992
  [[container.reqmts]], of a reversible container
993
  [[container.rev.reqmts]], of an allocator-aware container
994
+ [[container.alloc.reqmts]], and of an associative container
995
  [[associative.reqmts]]. A `set` also provides most operations described
996
  in  [[associative.reqmts]] for unique keys. This means that a `set`
997
  supports the `a_uniq` operations in  [[associative.reqmts]] but not the
998
  `a_eq` operations. For a `set<Key>` both the `key_type` and `value_type`
999
  are `Key`. Descriptions are provided here only for operations on `set`
1000
  that are not described in one of these tables and for operations where
1001
  there is additional semantic information.
1002
 
1003
+ The types `iterator` and `const_iterator` meet the constexpr iterator
1004
+ requirements [[iterator.requirements.general]].
1005
+
1006
  ``` cpp
1007
  namespace std {
1008
  template<class Key, class Compare = less<Key>,
1009
  class Allocator = allocator<Key>>
1010
  class set {
 
1013
  using key_type = Key;
1014
  using key_compare = Compare;
1015
  using value_type = Key;
1016
  using value_compare = Compare;
1017
  using allocator_type = Allocator;
1018
+ using pointer = allocator_traits<Allocator>::pointer;
1019
+ using const_pointer = allocator_traits<Allocator>::const_pointer;
1020
  using reference = value_type&;
1021
  using const_reference = const value_type&;
1022
  using size_type = implementation-defined // type of set::size_type; // see [container.requirements]
1023
  using difference_type = implementation-defined // type of set::difference_type; // see [container.requirements]
1024
  using iterator = implementation-defined // type of set::iterator; // see [container.requirements]
 
1027
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
1028
  using node_type = unspecified;
1029
  using insert_return_type = insert-return-type<iterator, node_type>;
1030
 
1031
  // [set.cons], construct/copy/destroy
1032
+ constexpr set() : set(Compare()) { }
1033
+ constexpr explicit set(const Compare& comp, const Allocator& = Allocator());
1034
  template<class InputIterator>
1035
+ constexpr set(InputIterator first, InputIterator last,
1036
  const Compare& comp = Compare(), const Allocator& = Allocator());
1037
  template<container-compatible-range<value_type> R>
1038
+ constexpr set(from_range_t, R&& rg,
1039
+ const Compare& comp = Compare(), const Allocator& = Allocator());
1040
+ constexpr set(const set& x);
1041
+ constexpr set(set&& x);
1042
+ constexpr explicit set(const Allocator&);
1043
+ constexpr set(const set&, const type_identity_t<Allocator>&);
1044
+ constexpr set(set&&, const type_identity_t<Allocator>&);
1045
+ constexpr set(initializer_list<value_type>,
1046
+ const Compare& = Compare(), const Allocator& = Allocator());
1047
  template<class InputIterator>
1048
+ constexpr set(InputIterator first, InputIterator last, const Allocator& a)
1049
  : set(first, last, Compare(), a) { }
1050
  template<container-compatible-range<value_type> R>
1051
+ constexpr set(from_range_t, R&& rg, const Allocator& a)
1052
  : set(from_range, std::forward<R>(rg), Compare(), a) { }
1053
+ constexpr set(initializer_list<value_type> il, const Allocator& a)
1054
  : set(il, Compare(), a) { }
1055
+ constexpr ~set();
1056
+ constexpr set& operator=(const set& x);
1057
+ constexpr set& operator=(set&& x)
1058
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
1059
  is_nothrow_move_assignable_v<Compare>);
1060
+ constexpr set& operator=(initializer_list<value_type>);
1061
+ constexpr allocator_type get_allocator() const noexcept;
1062
 
1063
  // iterators
1064
+ constexpr iterator begin() noexcept;
1065
+ constexpr const_iterator begin() const noexcept;
1066
+ constexpr iterator end() noexcept;
1067
+ constexpr const_iterator end() const noexcept;
1068
 
1069
+ constexpr reverse_iterator rbegin() noexcept;
1070
+ constexpr const_reverse_iterator rbegin() const noexcept;
1071
+ constexpr reverse_iterator rend() noexcept;
1072
+ constexpr const_reverse_iterator rend() const noexcept;
1073
 
1074
+ constexpr const_iterator cbegin() const noexcept;
1075
+ constexpr const_iterator cend() const noexcept;
1076
+ constexpr const_reverse_iterator crbegin() const noexcept;
1077
+ constexpr const_reverse_iterator crend() const noexcept;
1078
 
1079
  // capacity
1080
+ constexpr bool empty() const noexcept;
1081
+ constexpr size_type size() const noexcept;
1082
+ constexpr size_type max_size() const noexcept;
1083
 
1084
+ // [set.modifiers], modifiers
1085
+ template<class... Args> constexpr pair<iterator, bool> emplace(Args&&... args);
1086
+ template<class... Args>
1087
+ constexpr iterator emplace_hint(const_iterator position, Args&&... args);
1088
+ constexpr pair<iterator,bool> insert(const value_type& x);
1089
+ constexpr pair<iterator,bool> insert(value_type&& x);
1090
+ template<class K> constexpr pair<iterator, bool> insert(K&& x);
1091
+ constexpr iterator insert(const_iterator position, const value_type& x);
1092
+ constexpr iterator insert(const_iterator position, value_type&& x);
1093
+ template<class K> constexpr iterator insert(const_iterator position, K&& x);
1094
  template<class InputIterator>
1095
+ constexpr void insert(InputIterator first, InputIterator last);
1096
  template<container-compatible-range<value_type> R>
1097
+ constexpr void insert_range(R&& rg);
1098
+ constexpr void insert(initializer_list<value_type>);
1099
 
1100
+ constexpr node_type extract(const_iterator position);
1101
+ constexpr node_type extract(const key_type& x);
1102
+ template<class K> constexpr node_type extract(K&& x);
1103
+ constexpr insert_return_type insert(node_type&& nh);
1104
+ constexpr iterator insert(const_iterator hint, node_type&& nh);
1105
 
1106
+ constexpr iterator erase(iterator position)
1107
  requires (!same_as<iterator, const_iterator>);
1108
+ constexpr iterator erase(const_iterator position);
1109
+ constexpr size_type erase(const key_type& x);
1110
+ template<class K> constexpr size_type erase(K&& x);
1111
+ constexpr iterator erase(const_iterator first, const_iterator last);
1112
+ constexpr void swap(set&)
1113
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
1114
  is_nothrow_swappable_v<Compare>);
1115
+ constexpr void clear() noexcept;
1116
 
1117
  template<class C2>
1118
+ constexpr void merge(set<Key, C2, Allocator>& source);
1119
  template<class C2>
1120
+ constexpr void merge(set<Key, C2, Allocator>&& source);
1121
  template<class C2>
1122
+ constexpr void merge(multiset<Key, C2, Allocator>& source);
1123
  template<class C2>
1124
+ constexpr void merge(multiset<Key, C2, Allocator>&& source);
1125
 
1126
  // observers
1127
+ constexpr key_compare key_comp() const;
1128
+ constexpr value_compare value_comp() const;
1129
 
1130
  // set operations
1131
+ constexpr iterator find(const key_type& x);
1132
+ constexpr const_iterator find(const key_type& x) const;
1133
+ template<class K> constexpr iterator find(const K& x);
1134
+ template<class K> constexpr const_iterator find(const K& x) const;
1135
 
1136
+ constexpr size_type count(const key_type& x) const;
1137
+ template<class K> constexpr size_type count(const K& x) const;
1138
 
1139
+ constexpr bool contains(const key_type& x) const;
1140
+ template<class K> constexpr bool contains(const K& x) const;
1141
 
1142
+ constexpr iterator lower_bound(const key_type& x);
1143
+ constexpr const_iterator lower_bound(const key_type& x) const;
1144
+ template<class K> constexpr iterator lower_bound(const K& x);
1145
+ template<class K> constexpr const_iterator lower_bound(const K& x) const;
1146
 
1147
+ constexpr iterator upper_bound(const key_type& x);
1148
+ constexpr const_iterator upper_bound(const key_type& x) const;
1149
+ template<class K> constexpr iterator upper_bound(const K& x);
1150
+ template<class K> constexpr const_iterator upper_bound(const K& x) const;
1151
 
1152
+ constexpr pair<iterator, iterator> equal_range(const key_type& x);
1153
+ constexpr pair<const_iterator, const_iterator> equal_range(const key_type& x) const;
1154
  template<class K>
1155
+ constexpr pair<iterator, iterator> equal_range(const K& x);
1156
  template<class K>
1157
+ constexpr pair<const_iterator, const_iterator> equal_range(const K& x) const;
1158
  };
1159
 
1160
  template<class InputIterator,
1161
  class Compare = less<iter-value-type<InputIterator>>,
1162
  class Allocator = allocator<iter-value-type<InputIterator>>>
 
1188
  ```
1189
 
1190
  #### Constructors, copy, and assignment <a id="set.cons">[[set.cons]]</a>
1191
 
1192
  ``` cpp
1193
+ constexpr explicit set(const Compare& comp, const Allocator& = Allocator());
1194
  ```
1195
 
1196
  *Effects:* Constructs an empty `set` using the specified comparison
1197
  object and allocator.
1198
 
1199
  *Complexity:* Constant.
1200
 
1201
  ``` cpp
1202
  template<class InputIterator>
1203
+ constexpr set(InputIterator first, InputIterator last,
1204
  const Compare& comp = Compare(), const Allocator& = Allocator());
1205
  ```
1206
 
1207
  *Effects:* Constructs an empty `set` using the specified comparison
1208
  object and allocator, and inserts elements from the range \[`first`,
 
1212
  sorted with respect to `comp` and otherwise N log N, where N is
1213
  `last - first`.
1214
 
1215
  ``` cpp
1216
  template<container-compatible-range<value_type> R>
1217
+ constexpr set(from_range_t, R&& rg, const Compare& comp = Compare(),
1218
+ const Allocator& = Allocator());
1219
  ```
1220
 
1221
  *Effects:* Constructs an empty `set` using the specified comparison
1222
  object and allocator, and inserts elements from the range `rg`.
1223
 
 
1226
 
1227
  #### Erasure <a id="set.erasure">[[set.erasure]]</a>
1228
 
1229
  ``` cpp
1230
  template<class Key, class Compare, class Allocator, class Predicate>
1231
+ constexpr typename set<Key, Compare, Allocator>::size_type
1232
  erase_if(set<Key, Compare, Allocator>& c, Predicate pred);
1233
  ```
1234
 
1235
  *Effects:* Equivalent to:
1236
 
 
1244
  }
1245
  }
1246
  return original_size - c.size();
1247
  ```
1248
 
1249
+ #### Modifiers <a id="set.modifiers">[[set.modifiers]]</a>
1250
+
1251
+ ``` cpp
1252
+ template<class K> constexpr pair<iterator, bool> insert(K&& x);
1253
+ template<class K> constexpr iterator insert(const_iterator hint, K&& x);
1254
+ ```
1255
+
1256
+ *Constraints:* The *qualified-id* `Compare::is_transparent` is valid and
1257
+ denotes a type. For the second overload,
1258
+ `is_convertible_v<K&&, const_iterator>` and
1259
+ `is_convertible_v<K&&, iterator>` are both `false`.
1260
+
1261
+ *Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into `set`
1262
+ from `std::forward<K>(x)`.
1263
+
1264
+ *Effects:* If the set already contains an element that is equivalent to
1265
+ `x`, there is no effect. Otherwise, let `r` be `equal_range(x)`.
1266
+ Constructs an object `u` of type `value_type` with `std::forward<K>(x)`.
1267
+ If `equal_range(u) == r` is `false`, the behavior is undefined. Inserts
1268
+ `u` into `*this`.
1269
+
1270
+ *Returns:* For the first overload, the `bool` component of the returned
1271
+ pair is `true` if and only if the insertion took place. The returned
1272
+ iterator points to the set element that is equivalent to `x`.
1273
+
1274
+ *Complexity:* Logarithmic.
1275
+
1276
  ### Class template `multiset` <a id="multiset">[[multiset]]</a>
1277
 
1278
  #### Overview <a id="multiset.overview">[[multiset.overview]]</a>
1279
 
1280
  A `multiset` is an associative container that supports equivalent keys
 
1283
  supports bidirectional iterators.
1284
 
1285
  A `multiset` meets all of the requirements of a container
1286
  [[container.reqmts]], of a reversible container
1287
  [[container.rev.reqmts]], of an allocator-aware container
1288
+ [[container.alloc.reqmts]], and of an associative container
1289
  [[associative.reqmts]]. `multiset` also provides most operations
1290
  described in  [[associative.reqmts]] for duplicate keys. This means that
1291
  a `multiset` supports the `a_eq` operations in  [[associative.reqmts]]
1292
  but not the `a_uniq` operations. For a `multiset<Key>` both the
1293
  `key_type` and `value_type` are `Key`. Descriptions are provided here
1294
  only for operations on `multiset` that are not described in one of these
1295
  tables and for operations where there is additional semantic
1296
  information.
1297
 
1298
+ The types `iterator` and `const_iterator` meet the constexpr iterator
1299
+ requirements [[iterator.requirements.general]].
1300
+
1301
  ``` cpp
1302
  namespace std {
1303
  template<class Key, class Compare = less<Key>,
1304
  class Allocator = allocator<Key>>
1305
  class multiset {
 
1308
  using key_type = Key;
1309
  using key_compare = Compare;
1310
  using value_type = Key;
1311
  using value_compare = Compare;
1312
  using allocator_type = Allocator;
1313
+ using pointer = allocator_traits<Allocator>::pointer;
1314
+ using const_pointer = allocator_traits<Allocator>::const_pointer;
1315
  using reference = value_type&;
1316
  using const_reference = const value_type&;
1317
  using size_type = implementation-defined // type of multiset::size_type; // see [container.requirements]
1318
  using difference_type = implementation-defined // type of multiset::difference_type; // see [container.requirements]
1319
  using iterator = implementation-defined // type of multiset::iterator; // see [container.requirements]
 
1321
  using reverse_iterator = std::reverse_iterator<iterator>;
1322
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
1323
  using node_type = unspecified;
1324
 
1325
  // [multiset.cons], construct/copy/destroy
1326
+ constexpr multiset() : multiset(Compare()) { }
1327
+ constexpr explicit multiset(const Compare& comp, const Allocator& = Allocator());
1328
  template<class InputIterator>
1329
+ constexpr multiset(InputIterator first, InputIterator last,
1330
  const Compare& comp = Compare(), const Allocator& = Allocator());
1331
  template<container-compatible-range<value_type> R>
1332
+ constexpr multiset(from_range_t, R&& rg,
1333
  const Compare& comp = Compare(), const Allocator& = Allocator());
1334
+ constexpr multiset(const multiset& x);
1335
+ constexpr multiset(multiset&& x);
1336
+ constexpr explicit multiset(const Allocator&);
1337
+ constexpr multiset(const multiset&, const type_identity_t<Allocator>&);
1338
+ constexpr multiset(multiset&&, const type_identity_t<Allocator>&);
1339
+ constexpr multiset(initializer_list<value_type>, const Compare& = Compare(),
1340
  const Allocator& = Allocator());
1341
  template<class InputIterator>
1342
+ constexpr multiset(InputIterator first, InputIterator last, const Allocator& a)
1343
  : multiset(first, last, Compare(), a) { }
1344
  template<container-compatible-range<value_type> R>
1345
+ constexpr multiset(from_range_t, R&& rg, const Allocator& a)
1346
  : multiset(from_range, std::forward<R>(rg), Compare(), a) { }
1347
+ constexpr multiset(initializer_list<value_type> il, const Allocator& a)
1348
  : multiset(il, Compare(), a) { }
1349
+ constexpr ~multiset();
1350
+ constexpr multiset& operator=(const multiset& x);
1351
+ constexpr multiset& operator=(multiset&& x)
1352
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
1353
  is_nothrow_move_assignable_v<Compare>);
1354
+ constexpr multiset& operator=(initializer_list<value_type>);
1355
+ constexpr allocator_type get_allocator() const noexcept;
1356
 
1357
  // iterators
1358
+ constexpr iterator begin() noexcept;
1359
+ constexpr const_iterator begin() const noexcept;
1360
+ constexpr iterator end() noexcept;
1361
+ constexpr const_iterator end() const noexcept;
1362
 
1363
+ constexpr reverse_iterator rbegin() noexcept;
1364
+ constexpr const_reverse_iterator rbegin() const noexcept;
1365
+ constexpr reverse_iterator rend() noexcept;
1366
+ constexpr const_reverse_iterator rend() const noexcept;
1367
 
1368
+ constexpr const_iterator cbegin() const noexcept;
1369
+ constexpr const_iterator cend() const noexcept;
1370
+ constexpr const_reverse_iterator crbegin() const noexcept;
1371
+ constexpr const_reverse_iterator crend() const noexcept;
1372
 
1373
  // capacity
1374
+ constexpr bool empty() const noexcept;
1375
+ constexpr size_type size() const noexcept;
1376
+ constexpr size_type max_size() const noexcept;
1377
 
1378
  // modifiers
1379
+ template<class... Args> constexpr iterator emplace(Args&&... args);
1380
+ template<class... Args>
1381
+ constexpr iterator emplace_hint(const_iterator position, Args&&... args);
1382
+ constexpr iterator insert(const value_type& x);
1383
+ constexpr iterator insert(value_type&& x);
1384
+ constexpr iterator insert(const_iterator position, const value_type& x);
1385
+ constexpr iterator insert(const_iterator position, value_type&& x);
1386
  template<class InputIterator>
1387
+ constexpr void insert(InputIterator first, InputIterator last);
1388
  template<container-compatible-range<value_type> R>
1389
+ constexpr void insert_range(R&& rg);
1390
+ constexpr void insert(initializer_list<value_type>);
1391
 
1392
+ constexpr node_type extract(const_iterator position);
1393
+ constexpr node_type extract(const key_type& x);
1394
+ template<class K> constexpr node_type extract(K&& x);
1395
+ constexpr iterator insert(node_type&& nh);
1396
+ constexpr iterator insert(const_iterator hint, node_type&& nh);
1397
 
1398
+ constexpr iterator erase(iterator position)
1399
  requires (!same_as<iterator, const_iterator>);
1400
+ constexpr iterator erase(const_iterator position);
1401
+ constexpr size_type erase(const key_type& x);
1402
+ template<class K> constexpr size_type erase(K&& x);
1403
+ constexpr iterator erase(const_iterator first, const_iterator last);
1404
+ constexpr void swap(multiset&)
1405
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
1406
  is_nothrow_swappable_v<Compare>);
1407
+ constexpr void clear() noexcept;
1408
 
1409
  template<class C2>
1410
+ constexpr void merge(multiset<Key, C2, Allocator>& source);
1411
  template<class C2>
1412
+ constexpr void merge(multiset<Key, C2, Allocator>&& source);
1413
  template<class C2>
1414
+ constexpr void merge(set<Key, C2, Allocator>& source);
1415
  template<class C2>
1416
+ constexpr void merge(set<Key, C2, Allocator>&& source);
1417
 
1418
  // observers
1419
+ constexpr key_compare key_comp() const;
1420
+ constexpr value_compare value_comp() const;
1421
 
1422
  // set operations
1423
+ constexpr iterator find(const key_type& x);
1424
+ constexpr const_iterator find(const key_type& x) const;
1425
+ template<class K> constexpr iterator find(const K& x);
1426
+ template<class K> constexpr const_iterator find(const K& x) const;
1427
 
1428
+ constexpr size_type count(const key_type& x) const;
1429
+ template<class K> constexpr size_type count(const K& x) const;
1430
 
1431
+ constexpr bool contains(const key_type& x) const;
1432
+ template<class K> constexpr bool contains(const K& x) const;
1433
 
1434
+ constexpr iterator lower_bound(const key_type& x);
1435
+ constexpr const_iterator lower_bound(const key_type& x) const;
1436
+ template<class K> constexpr iterator lower_bound(const K& x);
1437
+ template<class K> constexpr const_iterator lower_bound(const K& x) const;
1438
 
1439
+ constexpr iterator upper_bound(const key_type& x);
1440
+ constexpr const_iterator upper_bound(const key_type& x) const;
1441
+ template<class K> constexpr iterator upper_bound(const K& x);
1442
+ template<class K> constexpr const_iterator upper_bound(const K& x) const;
1443
 
1444
+ constexpr pair<iterator, iterator> equal_range(const key_type& x);
1445
+ constexpr pair<const_iterator, const_iterator> equal_range(const key_type& x) const;
1446
  template<class K>
1447
+ constexpr pair<iterator, iterator> equal_range(const K& x);
1448
  template<class K>
1449
+ constexpr pair<const_iterator, const_iterator> equal_range(const K& x) const;
1450
  };
1451
 
1452
  template<class InputIterator,
1453
  class Compare = less<iter-value-type<InputIterator>>,
1454
  class Allocator = allocator<iter-value-type<InputIterator>>>
 
1480
  ```
1481
 
1482
  #### Constructors <a id="multiset.cons">[[multiset.cons]]</a>
1483
 
1484
  ``` cpp
1485
+ constexpr explicit multiset(const Compare& comp, const Allocator& = Allocator());
1486
  ```
1487
 
1488
  *Effects:* Constructs an empty `multiset` using the specified comparison
1489
  object and allocator.
1490
 
1491
  *Complexity:* Constant.
1492
 
1493
  ``` cpp
1494
  template<class InputIterator>
1495
+ constexpr multiset(InputIterator first, InputIterator last,
1496
  const Compare& comp = Compare(), const Allocator& = Allocator());
1497
  ```
1498
 
1499
  *Effects:* Constructs an empty `multiset` using the specified comparison
1500
  object and allocator, and inserts elements from the range \[`first`,
 
1504
  sorted with respect to `comp` and otherwise N log N, where N is
1505
  `last - first`.
1506
 
1507
  ``` cpp
1508
  template<container-compatible-range<value_type> R>
1509
+ constexpr multiset(from_range_t, R&& rg, const Compare& comp = Compare(),
1510
+ const Allocator& = Allocator());
1511
  ```
1512
 
1513
  *Effects:* Constructs an empty `multiset` using the specified comparison
1514
  object and allocator, and inserts elements from the range `rg`.
1515
 
 
1518
 
1519
  #### Erasure <a id="multiset.erasure">[[multiset.erasure]]</a>
1520
 
1521
  ``` cpp
1522
  template<class Key, class Compare, class Allocator, class Predicate>
1523
+ constexpr typename multiset<Key, Compare, Allocator>::size_type
1524
  erase_if(multiset<Key, Compare, Allocator>& c, Predicate pred);
1525
  ```
1526
 
1527
  *Effects:* Equivalent to:
1528