From Jason Turner

[associative]

C++17 → C++20 52.0 KB 596 lines
Current Draft | LaTeX Source
Archived: C++17 | C++20
Markdown: C++17 | C++20
Explore in Adventure Game

Diff to HTML by rtfpessoa

Files changed (1) hide show
  1. tmp/tmpc17o7bpy/{from.md → to.md} +262 -304
tmp/tmpc17o7bpy/{from.md → to.md} RENAMED
@@ -8,81 +8,75 @@ header `<set>` defines the class templates `set` and `multiset`.
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_key_t = remove_const_t<
 
 
 
14
  typename iterator_traits<InputIterator>::value_type::first_type>; // exposition only
15
  template<class InputIterator>
16
- using iter_val_t
17
- = typename iterator_traits<InputIterator>::value_type::second_type; // exposition only
18
  template<class InputIterator>
19
- using iter_to_alloc_t
20
- = pair<add_const_t<typename iterator_traits<InputIterator>::value_type::first_type>,
21
  typename iterator_traits<InputIterator>::value_type::second_type>; // exposition only
22
  ```
23
 
24
  ### Header `<map>` synopsis <a id="associative.map.syn">[[associative.map.syn]]</a>
25
 
26
  ``` cpp
27
- #include <initializer_list>
 
28
 
29
  namespace std {
30
  // [map], class template map
31
  template<class Key, class T, class Compare = less<Key>,
32
  class Allocator = allocator<pair<const Key, T>>>
33
  class map;
 
34
  template<class Key, class T, class Compare, class Allocator>
35
  bool operator==(const map<Key, T, Compare, Allocator>& x,
36
  const map<Key, T, Compare, Allocator>& y);
37
  template<class Key, class T, class Compare, class Allocator>
38
- bool operator< (const map<Key, T, Compare, Allocator>& x,
39
- const map<Key, T, Compare, Allocator>& y);
40
- template <class Key, class T, class Compare, class Allocator>
41
- bool operator!=(const map<Key, T, Compare, Allocator>& x,
42
- const map<Key, T, Compare, Allocator>& y);
43
- template <class Key, class T, class Compare, class Allocator>
44
- bool operator> (const map<Key, T, Compare, Allocator>& x,
45
- const map<Key, T, Compare, Allocator>& y);
46
- template <class Key, class T, class Compare, class Allocator>
47
- bool operator>=(const map<Key, T, Compare, Allocator>& x,
48
- const map<Key, T, Compare, Allocator>& y);
49
- template <class Key, class T, class Compare, class Allocator>
50
- bool operator<=(const map<Key, T, Compare, Allocator>& x,
51
  const map<Key, T, Compare, Allocator>& y);
 
52
  template<class Key, class T, class Compare, class Allocator>
53
  void swap(map<Key, T, Compare, Allocator>& x,
54
  map<Key, T, Compare, Allocator>& y)
55
  noexcept(noexcept(x.swap(y)));
56
 
 
 
 
 
57
  // [multimap], class template multimap
58
  template<class Key, class T, class Compare = less<Key>,
59
  class Allocator = allocator<pair<const Key, T>>>
60
  class multimap;
 
61
  template<class Key, class T, class Compare, class Allocator>
62
  bool operator==(const multimap<Key, T, Compare, Allocator>& x,
63
  const multimap<Key, T, Compare, Allocator>& y);
64
  template<class Key, class T, class Compare, class Allocator>
65
- bool operator< (const multimap<Key, T, Compare, Allocator>& x,
66
- const multimap<Key, T, Compare, Allocator>& y);
67
- template <class Key, class T, class Compare, class Allocator>
68
- bool operator!=(const multimap<Key, T, Compare, Allocator>& x,
69
- const multimap<Key, T, Compare, Allocator>& y);
70
- template <class Key, class T, class Compare, class Allocator>
71
- 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
- bool operator>=(const multimap<Key, T, Compare, Allocator>& x,
75
- const multimap<Key, T, Compare, Allocator>& y);
76
- template <class Key, class T, class Compare, class Allocator>
77
- bool operator<=(const multimap<Key, T, Compare, Allocator>& x,
78
  const multimap<Key, T, Compare, Allocator>& y);
 
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
  namespace pmr {
85
  template<class Key, class T, class Compare = less<Key>>
86
  using map = std::map<Key, T, Compare,
87
  polymorphic_allocator<pair<const Key, T>>>;
88
 
@@ -94,107 +88,91 @@ namespace std {
94
  ```
95
 
96
  ### Header `<set>` synopsis <a id="associative.set.syn">[[associative.set.syn]]</a>
97
 
98
  ``` cpp
99
- #include <initializer_list>
 
100
 
101
  namespace std {
102
  // [set], class template set
103
- template <class Key, class Compare = less<Key>,
104
- class Allocator = allocator<Key>>
105
  class set;
 
106
  template<class Key, class Compare, class Allocator>
107
  bool operator==(const set<Key, Compare, Allocator>& x,
108
  const set<Key, Compare, Allocator>& y);
109
  template<class Key, class Compare, class Allocator>
110
- bool operator< (const set<Key, Compare, Allocator>& x,
111
- const set<Key, Compare, Allocator>& y);
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
- bool operator> (const set<Key, Compare, Allocator>& x,
117
- const set<Key, Compare, Allocator>& y);
118
- template <class Key, class Compare, class Allocator>
119
- bool operator>=(const set<Key, Compare, Allocator>& x,
120
- const set<Key, Compare, Allocator>& y);
121
- template <class Key, class Compare, class Allocator>
122
- bool operator<=(const set<Key, Compare, Allocator>& x,
123
- const set<Key, Compare, Allocator>& y);
124
  template<class Key, class Compare, class Allocator>
125
  void swap(set<Key, Compare, Allocator>& x,
126
  set<Key, Compare, Allocator>& y)
127
  noexcept(noexcept(x.swap(y)));
128
 
 
 
 
 
129
  // [multiset], class template multiset
130
- template <class Key, class Compare = less<Key>,
131
- class Allocator = allocator<Key>>
132
  class multiset;
 
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
- bool operator< (const multiset<Key, Compare, Allocator>& x,
138
- const multiset<Key, Compare, Allocator>& y);
139
- template <class Key, class Compare, class Allocator>
140
- bool operator!=(const multiset<Key, Compare, Allocator>& x,
141
- const multiset<Key, Compare, Allocator>& y);
142
- template <class Key, class Compare, class Allocator>
143
- bool operator> (const multiset<Key, Compare, Allocator>& x,
144
- const multiset<Key, Compare, Allocator>& y);
145
- template <class Key, class Compare, class Allocator>
146
- bool operator>=(const multiset<Key, Compare, Allocator>& x,
147
- const multiset<Key, Compare, Allocator>& y);
148
- template <class Key, class Compare, class Allocator>
149
- bool operator<=(const multiset<Key, Compare, Allocator>& x,
150
- const multiset<Key, Compare, Allocator>& y);
151
  template<class Key, class Compare, class Allocator>
152
  void swap(multiset<Key, Compare, Allocator>& x,
153
  multiset<Key, Compare, Allocator>& y)
154
  noexcept(noexcept(x.swap(y)));
155
 
 
 
 
 
156
  namespace pmr {
157
  template<class Key, class Compare = less<Key>>
158
- using set = std::set<Key, Compare,
159
- polymorphic_allocator<Key>>;
160
 
161
  template<class Key, class Compare = less<Key>>
162
- using multiset = std::multiset<Key, Compare,
163
- polymorphic_allocator<Key>>;
164
  }
165
  }
166
  ```
167
 
168
  ### Class template `map` <a id="map">[[map]]</a>
169
 
170
- #### Class template `map` overview <a id="map.overview">[[map.overview]]</a>
171
 
172
  A `map` is an associative container that supports unique keys (contains
173
  at most one of each key value) and provides for fast retrieval of values
174
  of another type `T` based on the keys. The `map` class supports
175
  bidirectional iterators.
176
 
177
- A `map` satisfies all of the requirements of a container, of a
178
- reversible container ([[container.requirements]]), of an associative
179
- container ([[associative.reqmts]]), and of an allocator-aware container
180
- (Table  [[tab:containers.allocatoraware]]). A `map` also provides most
181
- operations described in  [[associative.reqmts]] for unique keys. This
182
- means that a `map` supports the `a_uniq` operations in 
183
- [[associative.reqmts]] but not the `a_eq` operations. For a `map<Key,T>`
184
- the `key_type` is `Key` and the `value_type` is `pair<const Key,T>`.
185
- Descriptions are provided here only for operations on `map` that are not
186
- described in one of those tables or for operations where there is
187
- additional semantic information.
188
 
189
  ``` cpp
190
  namespace std {
191
  template<class Key, class T, class Compare = less<Key>,
192
  class Allocator = allocator<pair<const Key, T>>>
193
  class map {
194
  public:
195
- // types:
196
  using key_type = Key;
197
  using mapped_type = T;
198
  using value_type = pair<const Key, T>;
199
  using key_compare = Compare;
200
  using allocator_type = Allocator;
@@ -207,11 +185,11 @@ namespace std {
207
  using iterator = implementation-defined // type of map::iterator; // see [container.requirements]
208
  using const_iterator = implementation-defined // type of map::const_iterator; // see [container.requirements]
209
  using reverse_iterator = std::reverse_iterator<iterator>;
210
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
211
  using node_type = unspecified;
212
- using insert_return_type = INSERT_RETURN_TYPE<iterator, node_type>;
213
 
214
  class value_compare {
215
  friend class map;
216
  protected:
217
  Compare comp;
@@ -247,11 +225,11 @@ namespace std {
247
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
248
  is_nothrow_move_assignable_v<Compare>);
249
  map& operator=(initializer_list<value_type>);
250
  allocator_type get_allocator() const noexcept;
251
 
252
- // iterators:
253
  iterator begin() noexcept;
254
  const_iterator begin() const noexcept;
255
  iterator end() noexcept;
256
  const_iterator end() const noexcept;
257
 
@@ -263,20 +241,20 @@ namespace std {
263
  const_iterator cbegin() const noexcept;
264
  const_iterator cend() const noexcept;
265
  const_reverse_iterator crbegin() const noexcept;
266
  const_reverse_iterator crend() const noexcept;
267
 
268
- // capacity:
269
- bool empty() const noexcept;
270
  size_type size() const noexcept;
271
  size_type max_size() const noexcept;
272
 
273
  // [map.access], element access
274
- T& operator[](const key_type& x);
275
- T& operator[](key_type&& x);
276
- T& at(const key_type& x);
277
- const T& at(const key_type& x) const;
278
 
279
  // [map.modifiers], modifiers
280
  template<class... Args> pair<iterator, bool> emplace(Args&&... args);
281
  template<class... Args> iterator emplace_hint(const_iterator position, Args&&... args);
282
  pair<iterator, bool> insert(const value_type& x);
@@ -328,23 +306,26 @@ namespace std {
328
  template<class C2>
329
  void merge(multimap<Key, T, C2, Allocator>& source);
330
  template<class C2>
331
  void merge(multimap<Key, T, C2, Allocator>&& source);
332
 
333
- // observers:
334
  key_compare key_comp() const;
335
  value_compare value_comp() const;
336
 
337
- // map operations:
338
  iterator find(const key_type& x);
339
  const_iterator find(const key_type& x) const;
340
  template<class K> iterator find(const K& x);
341
  template<class K> const_iterator find(const K& x) const;
342
 
343
  size_type count(const key_type& x) const;
344
  template<class K> size_type count(const K& x) const;
345
 
 
 
 
346
  iterator lower_bound(const key_type& x);
347
  const_iterator lower_bound(const key_type& x) const;
348
  template<class K> iterator lower_bound(const K& x);
349
  template<class K> const_iterator lower_bound(const K& x) const;
350
 
@@ -359,56 +340,37 @@ namespace std {
359
  pair<iterator, iterator> equal_range(const K& x);
360
  template<class K>
361
  pair<const_iterator, const_iterator> equal_range(const K& x) const;
362
  };
363
 
364
- template<class InputIterator, class Compare = less<iter_key_t<InputIterator>>,
365
- class Allocator = allocator<iter_to_alloc_t<InputIterator>>>
366
  map(InputIterator, InputIterator, Compare = Compare(), Allocator = Allocator())
367
- -> map<iter_key_t<InputIterator>, iter_val_t<InputIterator>, Compare, Allocator>;
368
 
369
  template<class Key, class T, class Compare = less<Key>,
370
  class Allocator = allocator<pair<const Key, T>>>
371
- map(initializer_list<pair<const Key, T>>, Compare = Compare(), Allocator = Allocator())
372
  -> map<Key, T, Compare, Allocator>;
373
 
374
  template<class InputIterator, class Allocator>
375
  map(InputIterator, InputIterator, Allocator)
376
- -> map<iter_key_t<InputIterator>, iter_val_t<InputIterator>,
377
- less<iter_key_t<InputIterator>>, Allocator>;
378
 
379
  template<class Key, class T, class Allocator>
380
- map(initializer_list<pair<const Key, T>>, Allocator) -> map<Key, T, less<Key>, Allocator>;
381
 
382
- template <class Key, class T, class Compare, class Allocator>
383
- bool operator==(const map<Key, T, Compare, Allocator>& x,
384
- const map<Key, T, Compare, Allocator>& y);
385
- template <class Key, class T, class Compare, class Allocator>
386
- bool operator< (const map<Key, T, Compare, Allocator>& x,
387
- const map<Key, T, Compare, Allocator>& y);
388
- template <class Key, class T, class Compare, class Allocator>
389
- bool operator!=(const map<Key, T, Compare, Allocator>& x,
390
- const map<Key, T, Compare, Allocator>& y);
391
- template <class Key, class T, class Compare, class Allocator>
392
- bool operator> (const map<Key, T, Compare, Allocator>& x,
393
- const map<Key, T, Compare, Allocator>& y);
394
- template <class Key, class T, class Compare, class Allocator>
395
- bool operator>=(const map<Key, T, Compare, Allocator>& x,
396
- const map<Key, T, Compare, Allocator>& y);
397
- template <class Key, class T, class Compare, class Allocator>
398
- bool operator<=(const map<Key, T, Compare, Allocator>& x,
399
- const map<Key, T, Compare, Allocator>& y);
400
-
401
- // [map.special], specialized algorithms
402
  template<class Key, class T, class Compare, class Allocator>
403
  void swap(map<Key, T, Compare, Allocator>& x,
404
  map<Key, T, Compare, Allocator>& y)
405
  noexcept(noexcept(x.swap(y)));
406
  }
407
  ```
408
 
409
- #### `map` constructors, copy, and assignment <a id="map.cons">[[map.cons]]</a>
410
 
411
  ``` cpp
412
  explicit map(const Compare& comp, const Allocator& = Allocator());
413
  ```
414
 
@@ -428,62 +390,61 @@ object and allocator, and inserts elements from the range \[`first`,
428
  `last`).
429
 
430
  *Complexity:* Linear in N if the range \[`first`, `last`) is already
431
  sorted using `comp` and otherwise N log N, where N is `last - first`.
432
 
433
- #### `map` element access <a id="map.access">[[map.access]]</a>
434
 
435
  ``` cpp
436
- T& operator[](const key_type& x);
437
  ```
438
 
439
  *Effects:* Equivalent to: `return try_emplace(x).first->second;`
440
 
441
  ``` cpp
442
- T& operator[](key_type&& x);
443
  ```
444
 
445
  *Effects:* Equivalent to: `return try_emplace(move(x)).first->second;`
446
 
447
  ``` cpp
448
- T& at(const key_type& x);
449
- const T& at(const key_type& x) const;
450
  ```
451
 
452
  *Returns:* A reference to the `mapped_type` corresponding to `x` in
453
  `*this`.
454
 
455
  *Throws:* An exception object of type `out_of_range` if no such element
456
  is present.
457
 
458
  *Complexity:* Logarithmic.
459
 
460
- #### `map` modifiers <a id="map.modifiers">[[map.modifiers]]</a>
461
 
462
  ``` cpp
463
  template<class P>
464
  pair<iterator, bool> insert(P&& x);
465
  template<class P>
466
  iterator insert(const_iterator position, P&& x);
467
  ```
468
 
 
 
469
  *Effects:* The first form is equivalent to
470
  `return emplace(std::forward<P>(x))`. The second form is equivalent to
471
  `return emplace_hint(position, std::forward<P>(x))`.
472
 
473
- *Remarks:* These signatures shall not participate in overload resolution
474
- unless `is_constructible_v<value_type, P&&>` is `true`.
475
-
476
  ``` cpp
477
  template<class... Args>
478
  pair<iterator, bool> try_emplace(const key_type& k, Args&&... args);
479
  template<class... Args>
480
  iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args);
481
  ```
482
 
483
- *Requires:* `value_type` shall be `EmplaceConstructible` into `map` from
484
- `piecewise_construct`, `forward_as_tuple(k)`,
485
  `forward_as_tuple(std::forward<Args>(args)...)`.
486
 
487
  *Effects:* If the map already contains an element whose key is
488
  equivalent to `k`, there is no effect. Otherwise inserts an object of
489
  type `value_type` constructed with `piecewise_construct`,
@@ -500,12 +461,12 @@ template <class... Args>
500
  pair<iterator, bool> try_emplace(key_type&& k, Args&&... args);
501
  template<class... Args>
502
  iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args);
503
  ```
504
 
505
- *Requires:* `value_type` shall be `EmplaceConstructible` into `map` from
506
- `piecewise_construct`, `forward_as_tuple(std::move(k))`,
507
  `forward_as_tuple(std::forward<Args>(args)...)`.
508
 
509
  *Effects:* If the map already contains an element whose key is
510
  equivalent to `k`, there is no effect. Otherwise inserts an object of
511
  type `value_type` constructed with `piecewise_construct`,
@@ -523,13 +484,14 @@ template <class M>
523
  pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj);
524
  template<class M>
525
  iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj);
526
  ```
527
 
528
- *Requires:* `is_assignable_v<mapped_type&, M&&>` shall be `true`.
529
- `value_type` shall be `EmplaceConstructible` into `map` from `k`,
530
- `forward<M>(obj)`.
 
531
 
532
  *Effects:* If the map already contains an element `e` whose key is
533
  equivalent to `k`, assigns `std::forward<M>(obj)` to `e.second`.
534
  Otherwise inserts an object of type `value_type` constructed with `k`,
535
  `std::forward<M>(obj)`.
@@ -545,13 +507,14 @@ template <class M>
545
  pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj);
546
  template<class M>
547
  iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj);
548
  ```
549
 
550
- *Requires:* `is_assignable_v<mapped_type&, M&&>` shall be `true`.
551
- `value_type` shall be `EmplaceConstructible` into `map` from `move(k)`,
552
- `forward<M>(obj)`.
 
553
 
554
  *Effects:* If the map already contains an element `e` whose key is
555
  equivalent to `k`, assigns `std::forward<M>(obj)` to `e.second`.
556
  Otherwise inserts an object of type `value_type` constructed with
557
  `std::move(k)`, `std::forward<M>(obj)`.
@@ -560,49 +523,60 @@ Otherwise inserts an object of type `value_type` constructed with
560
  pair is `true` if and only if the insertion took place. The returned
561
  iterator points to the map element whose key is equivalent to `k`.
562
 
563
  *Complexity:* The same as `emplace` and `emplace_hint`, respectively.
564
 
565
- #### `map` specialized algorithms <a id="map.special">[[map.special]]</a>
566
 
567
  ``` cpp
568
- template <class Key, class T, class Compare, class Allocator>
569
- void swap(map<Key, T, Compare, Allocator>& x,
570
- map<Key, T, Compare, Allocator>& y)
571
- noexcept(noexcept(x.swap(y)));
572
  ```
573
 
574
- *Effects:* As if by `x.swap(y)`.
 
 
 
 
 
 
 
 
 
 
 
 
575
 
576
  ### Class template `multimap` <a id="multimap">[[multimap]]</a>
577
 
578
- #### Class template `multimap` overview <a id="multimap.overview">[[multimap.overview]]</a>
579
 
580
  A `multimap` is an associative container that supports equivalent keys
581
  (possibly containing multiple copies of the same key value) and provides
582
  for fast retrieval of values of another type `T` based on the keys. The
583
  `multimap` class supports bidirectional iterators.
584
 
585
- A `multimap` satisfies all of the requirements of a container and of a
586
- reversible container ([[container.requirements]]), of an associative
587
- container ([[associative.reqmts]]), and of an allocator-aware container
588
- (Table  [[tab:containers.allocatoraware]]). A `multimap` also provides
589
- most operations described in  [[associative.reqmts]] for equal keys.
590
- This means that a `multimap` supports the `a_eq` operations in 
591
- [[associative.reqmts]] but not the `a_uniq` operations. For a
592
- `multimap<Key,T>` the `key_type` is `Key` and the `value_type` is
593
- `pair<const Key,T>`. Descriptions are provided here only for operations
594
- on `multimap` that are not described in one of those tables or for
595
- operations where there is additional semantic information.
596
 
597
  ``` cpp
598
  namespace std {
599
  template<class Key, class T, class Compare = less<Key>,
600
  class Allocator = allocator<pair<const Key, T>>>
601
  class multimap {
602
  public:
603
- // types:
604
  using key_type = Key;
605
  using mapped_type = T;
606
  using value_type = pair<const Key, T>;
607
  using key_compare = Compare;
608
  using allocator_type = Allocator;
@@ -655,11 +629,11 @@ namespace std {
655
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
656
  is_nothrow_move_assignable_v<Compare>);
657
  multimap& operator=(initializer_list<value_type>);
658
  allocator_type get_allocator() const noexcept;
659
 
660
- // iterators:
661
  iterator begin() noexcept;
662
  const_iterator begin() const noexcept;
663
  iterator end() noexcept;
664
  const_iterator end() const noexcept;
665
 
@@ -671,12 +645,12 @@ namespace std {
671
  const_iterator cbegin() const noexcept;
672
  const_iterator cend() const noexcept;
673
  const_reverse_iterator crbegin() const noexcept;
674
  const_reverse_iterator crend() const noexcept;
675
 
676
- // capacity:
677
- bool empty() const noexcept;
678
  size_type size() const noexcept;
679
  size_type max_size() const noexcept;
680
 
681
  // [multimap.modifiers], modifiers
682
  template<class... Args> iterator emplace(Args&&... args);
@@ -712,23 +686,26 @@ namespace std {
712
  template<class C2>
713
  void merge(map<Key, T, C2, Allocator>& source);
714
  template<class C2>
715
  void merge(map<Key, T, C2, Allocator>&& source);
716
 
717
- // observers:
718
  key_compare key_comp() const;
719
  value_compare value_comp() const;
720
 
721
- // map operations:
722
  iterator find(const key_type& x);
723
  const_iterator find(const key_type& x) const;
724
  template<class K> iterator find(const K& x);
725
  template<class K> const_iterator find(const K& x) const;
726
 
727
  size_type count(const key_type& x) const;
728
  template<class K> size_type count(const K& x) const;
729
 
 
 
 
730
  iterator lower_bound(const key_type& x);
731
  const_iterator lower_bound(const key_type& x) const;
732
  template<class K> iterator lower_bound(const K& x);
733
  template<class K> const_iterator lower_bound(const K& x) const;
734
 
@@ -743,57 +720,39 @@ namespace std {
743
  pair<iterator, iterator> equal_range(const K& x);
744
  template<class K>
745
  pair<const_iterator, const_iterator> equal_range(const K& x) const;
746
  };
747
 
748
- template<class InputIterator, class Compare = less<iter_key_t<InputIterator>>,
749
- class Allocator = allocator<iter_to_alloc_t<InputIterator>>>
750
  multimap(InputIterator, InputIterator, Compare = Compare(), Allocator = Allocator())
751
- -> multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>, Compare, Allocator>;
 
752
 
753
  template<class Key, class T, class Compare = less<Key>,
754
  class Allocator = allocator<pair<const Key, T>>>
755
- multimap(initializer_list<pair<const Key, T>>, Compare = Compare(), Allocator = Allocator())
756
  -> multimap<Key, T, Compare, Allocator>;
757
 
758
  template<class InputIterator, class Allocator>
759
  multimap(InputIterator, InputIterator, Allocator)
760
- -> multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>,
761
- less<iter_key_t<InputIterator>>, Allocator>;
762
 
763
  template<class Key, class T, class Allocator>
764
- multimap(initializer_list<pair<const Key, T>>, Allocator)
765
  -> multimap<Key, T, less<Key>, Allocator>;
766
 
767
- template <class Key, class T, class Compare, class Allocator>
768
- bool operator==(const multimap<Key, T, Compare, Allocator>& x,
769
- const multimap<Key, T, Compare, Allocator>& y);
770
- template <class Key, class T, class Compare, class Allocator>
771
- bool operator< (const multimap<Key, T, Compare, Allocator>& x,
772
- const multimap<Key, T, Compare, Allocator>& y);
773
- template <class Key, class T, class Compare, class Allocator>
774
- bool operator!=(const multimap<Key, T, Compare, Allocator>& x,
775
- const multimap<Key, T, Compare, Allocator>& y);
776
- template <class Key, class T, class Compare, class Allocator>
777
- bool operator> (const multimap<Key, T, Compare, Allocator>& x,
778
- const multimap<Key, T, Compare, Allocator>& y);
779
- template <class Key, class T, class Compare, class Allocator>
780
- bool operator>=(const multimap<Key, T, Compare, Allocator>& x,
781
- const multimap<Key, T, Compare, Allocator>& y);
782
- template <class Key, class T, class Compare, class Allocator>
783
- bool operator<=(const multimap<Key, T, Compare, Allocator>& x,
784
- const multimap<Key, T, Compare, Allocator>& y);
785
-
786
- // [multimap.special], specialized algorithms
787
  template<class Key, class T, class Compare, class Allocator>
788
  void swap(multimap<Key, T, Compare, Allocator>& x,
789
  multimap<Key, T, Compare, Allocator>& y)
790
  noexcept(noexcept(x.swap(y)));
791
  }
792
  ```
793
 
794
- #### `multimap` constructors <a id="multimap.cons">[[multimap.cons]]</a>
795
 
796
  ``` cpp
797
  explicit multimap(const Compare& comp, const Allocator& = Allocator());
798
  ```
799
 
@@ -814,62 +773,71 @@ object and allocator, and inserts elements from the range \[`first`,
814
  `last`).
815
 
816
  *Complexity:* Linear in N if the range \[`first`, `last`) is already
817
  sorted using `comp` and otherwise N log N, where N is `last - first`.
818
 
819
- #### `multimap` modifiers <a id="multimap.modifiers">[[multimap.modifiers]]</a>
820
 
821
  ``` cpp
822
  template<class P> iterator insert(P&& x);
823
  template<class P> iterator insert(const_iterator position, P&& x);
824
  ```
825
 
 
 
826
  *Effects:* The first form is equivalent to
827
  `return emplace(std::forward<P>(x))`. The second form is equivalent to
828
  `return emplace_hint(position, std::forward<P>(x))`.
829
 
830
- *Remarks:* These signatures shall not participate in overload resolution
831
- unless `is_constructible_v<value_type, P&&>` is `true`.
832
-
833
- #### `multimap` specialized algorithms <a id="multimap.special">[[multimap.special]]</a>
834
 
835
  ``` cpp
836
- template <class Key, class T, class Compare, class Allocator>
837
- void swap(multimap<Key, T, Compare, Allocator>& x,
838
- multimap<Key, T, Compare, Allocator>& y)
839
- noexcept(noexcept(x.swap(y)));
840
  ```
841
 
842
- *Effects:* As if by `x.swap(y)`.
 
 
 
 
 
 
 
 
 
 
 
 
843
 
844
  ### Class template `set` <a id="set">[[set]]</a>
845
 
846
- #### Class template `set` overview <a id="set.overview">[[set.overview]]</a>
847
 
848
  A `set` is an associative container that supports unique keys (contains
849
  at most one of each key value) and provides for fast retrieval of the
850
  keys themselves. The `set` class supports bidirectional iterators.
851
 
852
- A `set` satisfies all of the requirements of a container, of a
853
- reversible container ([[container.requirements]]), of an associative
854
- container ([[associative.reqmts]]), and of an allocator-aware container
855
- (Table  [[tab:containers.allocatoraware]]). A `set` also provides most
856
- operations described in  [[associative.reqmts]] for unique keys. This
857
- means that a `set` supports the `a_uniq` operations in 
858
- [[associative.reqmts]] but not the `a_eq` operations. For a `set<Key>`
859
- both the `key_type` and `value_type` are `Key`. Descriptions are
860
- provided here only for operations on `set` that are not described in one
861
- of these tables and for operations where there is additional semantic
862
- information.
863
 
864
  ``` cpp
865
  namespace std {
866
  template<class Key, class Compare = less<Key>,
867
  class Allocator = allocator<Key>>
868
  class set {
869
  public:
870
- // types:
871
  using key_type = Key;
872
  using key_compare = Compare;
873
  using value_type = Key;
874
  using value_compare = Compare;
875
  using allocator_type = Allocator;
@@ -882,11 +850,11 @@ namespace std {
882
  using iterator = implementation-defined // type of set::iterator; // see [container.requirements]
883
  using const_iterator = implementation-defined // type of set::const_iterator; // see [container.requirements]
884
  using reverse_iterator = std::reverse_iterator<iterator>;
885
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
886
  using node_type = unspecified;
887
- using insert_return_type = INSERT_RETURN_TYPE<iterator, node_type>;
888
 
889
  // [set.cons], construct/copy/destroy
890
  set() : set(Compare()) { }
891
  explicit set(const Compare& comp, const Allocator& = Allocator());
892
  template<class InputIterator>
@@ -910,11 +878,11 @@ namespace std {
910
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
911
  is_nothrow_move_assignable_v<Compare>);
912
  set& operator=(initializer_list<value_type>);
913
  allocator_type get_allocator() const noexcept;
914
 
915
- // iterators:
916
  iterator begin() noexcept;
917
  const_iterator begin() const noexcept;
918
  iterator end() noexcept;
919
  const_iterator end() const noexcept;
920
 
@@ -926,16 +894,16 @@ namespace std {
926
  const_iterator cbegin() const noexcept;
927
  const_iterator cend() const noexcept;
928
  const_reverse_iterator crbegin() const noexcept;
929
  const_reverse_iterator crend() const noexcept;
930
 
931
- // capacity:
932
- bool empty() const noexcept;
933
  size_type size() const noexcept;
934
  size_type max_size() const noexcept;
935
 
936
- // modifiers:
937
  template<class... Args> pair<iterator, bool> emplace(Args&&... args);
938
  template<class... Args> iterator emplace_hint(const_iterator position, Args&&... args);
939
  pair<iterator,bool> insert(const value_type& x);
940
  pair<iterator,bool> insert(value_type&& x);
941
  iterator insert(const_iterator position, const value_type& x);
@@ -965,23 +933,26 @@ namespace std {
965
  template<class C2>
966
  void merge(multiset<Key, C2, Allocator>& source);
967
  template<class C2>
968
  void merge(multiset<Key, C2, Allocator>&& source);
969
 
970
- // observers:
971
  key_compare key_comp() const;
972
  value_compare value_comp() const;
973
 
974
- // set operations:
975
  iterator find(const key_type& x);
976
  const_iterator find(const key_type& x) const;
977
  template<class K> iterator find(const K& x);
978
  template<class K> const_iterator find(const K& x) const;
979
 
980
  size_type count(const key_type& x) const;
981
  template<class K> size_type count(const K& x) const;
982
 
 
 
 
983
  iterator lower_bound(const key_type& x);
984
  const_iterator lower_bound(const key_type& x) const;
985
  template<class K> iterator lower_bound(const K& x);
986
  template<class K> const_iterator lower_bound(const K& x) const;
987
 
@@ -997,56 +968,37 @@ namespace std {
997
  template<class K>
998
  pair<const_iterator, const_iterator> equal_range(const K& x) const;
999
  };
1000
 
1001
  template<class InputIterator,
1002
- class Compare = less<typename iterator_traits<InputIterator>::value_type>,
1003
- class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
1004
  set(InputIterator, InputIterator,
1005
  Compare = Compare(), Allocator = Allocator())
1006
- -> set<typename iterator_traits<InputIterator>::value_type, Compare, Allocator>;
1007
 
1008
  template<class Key, class Compare = less<Key>, class Allocator = allocator<Key>>
1009
  set(initializer_list<Key>, Compare = Compare(), Allocator = Allocator())
1010
  -> set<Key, Compare, Allocator>;
1011
 
1012
  template<class InputIterator, class Allocator>
1013
  set(InputIterator, InputIterator, Allocator)
1014
- -> set<typename iterator_traits<InputIterator>::value_type,
1015
- less<typename iterator_traits<InputIterator>::value_type>, Allocator>;
1016
 
1017
  template<class Key, class Allocator>
1018
  set(initializer_list<Key>, Allocator) -> set<Key, less<Key>, Allocator>;
1019
 
1020
- template <class Key, class Compare, class Allocator>
1021
- bool operator==(const set<Key, Compare, Allocator>& x,
1022
- const set<Key, Compare, Allocator>& y);
1023
- template <class Key, class Compare, class Allocator>
1024
- bool operator< (const set<Key, Compare, Allocator>& x,
1025
- const set<Key, Compare, Allocator>& y);
1026
- template <class Key, class Compare, class Allocator>
1027
- bool operator!=(const set<Key, Compare, Allocator>& x,
1028
- const set<Key, Compare, Allocator>& y);
1029
- template <class Key, class Compare, class Allocator>
1030
- bool operator> (const set<Key, Compare, Allocator>& x,
1031
- const set<Key, Compare, Allocator>& y);
1032
- template <class Key, class Compare, class Allocator>
1033
- bool operator>=(const set<Key, Compare, Allocator>& x,
1034
- const set<Key, Compare, Allocator>& y);
1035
- template <class Key, class Compare, class Allocator>
1036
- bool operator<=(const set<Key, Compare, Allocator>& x,
1037
- const set<Key, Compare, Allocator>& y);
1038
-
1039
- // [set.special], specialized algorithms
1040
  template<class Key, class Compare, class Allocator>
1041
  void swap(set<Key, Compare, Allocator>& x,
1042
  set<Key, Compare, Allocator>& y)
1043
  noexcept(noexcept(x.swap(y)));
1044
  }
1045
  ```
1046
 
1047
- #### `set` constructors, copy, and assignment <a id="set.cons">[[set.cons]]</a>
1048
 
1049
  ``` cpp
1050
  explicit set(const Compare& comp, const Allocator& = Allocator());
1051
  ```
1052
 
@@ -1066,49 +1018,60 @@ object and allocator, and inserts elements from the range \[`first`,
1066
  `last`).
1067
 
1068
  *Complexity:* Linear in N if the range \[`first`, `last`) is already
1069
  sorted using `comp` and otherwise N log N, where N is `last - first`.
1070
 
1071
- #### `set` specialized algorithms <a id="set.special">[[set.special]]</a>
1072
 
1073
  ``` cpp
1074
- template <class Key, class Compare, class Allocator>
1075
- void swap(set<Key, Compare, Allocator>& x,
1076
- set<Key, Compare, Allocator>& y)
1077
- noexcept(noexcept(x.swap(y)));
1078
  ```
1079
 
1080
- *Effects:* As if by `x.swap(y)`.
 
 
 
 
 
 
 
 
 
 
 
 
1081
 
1082
  ### Class template `multiset` <a id="multiset">[[multiset]]</a>
1083
 
1084
- #### Class template `multiset` overview <a id="multiset.overview">[[multiset.overview]]</a>
1085
 
1086
  A `multiset` is an associative container that supports equivalent keys
1087
  (possibly contains multiple copies of the same key value) and provides
1088
  for fast retrieval of the keys themselves. The `multiset` class supports
1089
  bidirectional iterators.
1090
 
1091
- A `multiset` satisfies all of the requirements of a container, of a
1092
- reversible container ([[container.requirements]]), of an associative
1093
- container ([[associative.reqmts]]), and of an allocator-aware container
1094
- (Table  [[tab:containers.allocatoraware]]). `multiset` also provides
1095
- most operations described in  [[associative.reqmts]] for duplicate keys.
1096
- This means that a `multiset` supports the `a_eq` operations in 
1097
- [[associative.reqmts]] but not the `a_uniq` operations. For a
1098
- `multiset<Key>` both the `key_type` and `value_type` are `Key`.
1099
- Descriptions are provided here only for operations on `multiset` that
1100
- are not described in one of these tables and for operations where there
1101
- is additional semantic information.
1102
 
1103
  ``` cpp
1104
  namespace std {
1105
  template<class Key, class Compare = less<Key>,
1106
  class Allocator = allocator<Key>>
1107
  class multiset {
1108
  public:
1109
- // types:
1110
  using key_type = Key;
1111
  using key_compare = Compare;
1112
  using value_type = Key;
1113
  using value_compare = Compare;
1114
  using allocator_type = Allocator;
@@ -1148,11 +1111,11 @@ namespace std {
1148
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
1149
  is_nothrow_move_assignable_v<Compare>);
1150
  multiset& operator=(initializer_list<value_type>);
1151
  allocator_type get_allocator() const noexcept;
1152
 
1153
- // iterators:
1154
  iterator begin() noexcept;
1155
  const_iterator begin() const noexcept;
1156
  iterator end() noexcept;
1157
  const_iterator end() const noexcept;
1158
 
@@ -1164,16 +1127,16 @@ namespace std {
1164
  const_iterator cbegin() const noexcept;
1165
  const_iterator cend() const noexcept;
1166
  const_reverse_iterator crbegin() const noexcept;
1167
  const_reverse_iterator crend() const noexcept;
1168
 
1169
- // capacity:
1170
- bool empty() const noexcept;
1171
  size_type size() const noexcept;
1172
  size_type max_size() const noexcept;
1173
 
1174
- // modifiers:
1175
  template<class... Args> iterator emplace(Args&&... args);
1176
  template<class... Args> iterator emplace_hint(const_iterator position, Args&&... args);
1177
  iterator insert(const value_type& x);
1178
  iterator insert(value_type&& x);
1179
  iterator insert(const_iterator position, const value_type& x);
@@ -1203,23 +1166,26 @@ namespace std {
1203
  template<class C2>
1204
  void merge(set<Key, C2, Allocator>& source);
1205
  template<class C2>
1206
  void merge(set<Key, C2, Allocator>&& source);
1207
 
1208
- // observers:
1209
  key_compare key_comp() const;
1210
  value_compare value_comp() const;
1211
 
1212
- // set operations:
1213
  iterator find(const key_type& x);
1214
  const_iterator find(const key_type& x) const;
1215
  template<class K> iterator find(const K& x);
1216
  template<class K> const_iterator find(const K& x) const;
1217
 
1218
  size_type count(const key_type& x) const;
1219
  template<class K> size_type count(const K& x) const;
1220
 
 
 
 
1221
  iterator lower_bound(const key_type& x);
1222
  const_iterator lower_bound(const key_type& x) const;
1223
  template<class K> iterator lower_bound(const K& x);
1224
  template<class K> const_iterator lower_bound(const K& x) const;
1225
 
@@ -1235,56 +1201,37 @@ namespace std {
1235
  template<class K>
1236
  pair<const_iterator, const_iterator> equal_range(const K& x) const;
1237
  };
1238
 
1239
  template<class InputIterator,
1240
- class Compare = less<typename iterator_traits<InputIterator>::value_type>,
1241
- class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
1242
  multiset(InputIterator, InputIterator,
1243
  Compare = Compare(), Allocator = Allocator())
1244
- -> multiset<typename iterator_traits<InputIterator>::value_type, Compare, Allocator>;
1245
 
1246
  template<class Key, class Compare = less<Key>, class Allocator = allocator<Key>>
1247
  multiset(initializer_list<Key>, Compare = Compare(), Allocator = Allocator())
1248
  -> multiset<Key, Compare, Allocator>;
1249
 
1250
  template<class InputIterator, class Allocator>
1251
  multiset(InputIterator, InputIterator, Allocator)
1252
- -> multiset<typename iterator_traits<InputIterator>::value_type,
1253
- less<typename iterator_traits<InputIterator>::value_type>, Allocator>;
1254
 
1255
  template<class Key, class Allocator>
1256
  multiset(initializer_list<Key>, Allocator) -> multiset<Key, less<Key>, Allocator>;
1257
 
1258
- template <class Key, class Compare, class Allocator>
1259
- bool operator==(const multiset<Key, Compare, Allocator>& x,
1260
- const multiset<Key, Compare, Allocator>& y);
1261
- template <class Key, class Compare, class Allocator>
1262
- bool operator< (const multiset<Key, Compare, Allocator>& x,
1263
- const multiset<Key, Compare, Allocator>& y);
1264
- template <class Key, class Compare, class Allocator>
1265
- bool operator!=(const multiset<Key, Compare, Allocator>& x,
1266
- const multiset<Key, Compare, Allocator>& y);
1267
- template <class Key, class Compare, class Allocator>
1268
- bool operator> (const multiset<Key, Compare, Allocator>& x,
1269
- const multiset<Key, Compare, Allocator>& y);
1270
- template <class Key, class Compare, class Allocator>
1271
- bool operator>=(const multiset<Key, Compare, Allocator>& x,
1272
- const multiset<Key, Compare, Allocator>& y);
1273
- template <class Key, class Compare, class Allocator>
1274
- bool operator<=(const multiset<Key, Compare, Allocator>& x,
1275
- const multiset<Key, Compare, Allocator>& y);
1276
-
1277
- // [multiset.special], specialized algorithms
1278
  template<class Key, class Compare, class Allocator>
1279
  void swap(multiset<Key, Compare, Allocator>& x,
1280
  multiset<Key, Compare, Allocator>& y)
1281
  noexcept(noexcept(x.swap(y)));
1282
  }
1283
  ```
1284
 
1285
- #### `multiset` constructors <a id="multiset.cons">[[multiset.cons]]</a>
1286
 
1287
  ``` cpp
1288
  explicit multiset(const Compare& comp, const Allocator& = Allocator());
1289
  ```
1290
 
@@ -1304,16 +1251,27 @@ object and allocator, and inserts elements from the range \[`first`,
1304
  `last`).
1305
 
1306
  *Complexity:* Linear in N if the range \[`first`, `last`) is already
1307
  sorted using `comp` and otherwise N log N, where N is `last - first`.
1308
 
1309
- #### `multiset` specialized algorithms <a id="multiset.special">[[multiset.special]]</a>
1310
 
1311
  ``` cpp
1312
- template <class Key, class Compare, class Allocator>
1313
- void swap(multiset<Key, Compare, Allocator>& x,
1314
- multiset<Key, Compare, Allocator>& y)
1315
- noexcept(noexcept(x.swap(y)));
1316
  ```
1317
 
1318
- *Effects:* As if by `x.swap(y)`.
 
 
 
 
 
 
 
 
 
 
 
 
1319
 
 
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
  typename iterator_traits<InputIterator>::value_type::first_type>; // exposition only
18
  template<class InputIterator>
19
+ using iter-mapped-type =
20
+ typename iterator_traits<InputIterator>::value_type::second_type; // exposition only
21
  template<class InputIterator>
22
+ using iter-to-alloc-type = pair<
23
+ add_const_t<typename iterator_traits<InputIterator>::value_type::first_type>,
24
  typename iterator_traits<InputIterator>::value_type::second_type>; // exposition only
25
  ```
26
 
27
  ### Header `<map>` synopsis <a id="associative.map.syn">[[associative.map.syn]]</a>
28
 
29
  ``` cpp
30
+ #include <compare> // see [compare.syn]
31
+ #include <initializer_list> // see [initializer.list.syn]
32
 
33
  namespace std {
34
  // [map], class template map
35
  template<class Key, class T, class Compare = less<Key>,
36
  class Allocator = allocator<pair<const Key, T>>>
37
  class map;
38
+
39
  template<class Key, class T, class Compare, class Allocator>
40
  bool operator==(const map<Key, T, Compare, Allocator>& x,
41
  const map<Key, T, Compare, Allocator>& y);
42
  template<class Key, class T, class Compare, class Allocator>
43
+ synth-three-way-result<pair<const Key, T>>
44
+ operator<=>(const map<Key, T, Compare, Allocator>& x,
 
 
 
 
 
 
 
 
 
 
 
45
  const map<Key, T, Compare, Allocator>& y);
46
+
47
  template<class Key, class T, class Compare, class Allocator>
48
  void swap(map<Key, T, Compare, Allocator>& x,
49
  map<Key, T, Compare, Allocator>& y)
50
  noexcept(noexcept(x.swap(y)));
51
 
52
+ template<class Key, class T, class Compare, class Allocator, class Predicate>
53
+ typename map<Key, T, Compare, Allocator>::size_type
54
+ erase_if(map<Key, T, Compare, Allocator>& c, Predicate pred);
55
+
56
  // [multimap], class template multimap
57
  template<class Key, class T, class Compare = less<Key>,
58
  class Allocator = allocator<pair<const Key, T>>>
59
  class multimap;
60
+
61
  template<class Key, class T, class Compare, class Allocator>
62
  bool operator==(const multimap<Key, T, Compare, Allocator>& x,
63
  const multimap<Key, T, Compare, Allocator>& y);
64
  template<class Key, class T, class Compare, class Allocator>
65
+ synth-three-way-result<pair<const Key, T>>
66
+ operator<=>(const multimap<Key, T, Compare, Allocator>& x,
 
 
 
 
 
 
 
 
 
 
 
67
  const multimap<Key, T, Compare, Allocator>& y);
68
+
69
  template<class Key, class T, class Compare, class Allocator>
70
  void swap(multimap<Key, T, Compare, Allocator>& x,
71
  multimap<Key, T, Compare, Allocator>& y)
72
  noexcept(noexcept(x.swap(y)));
73
 
74
+ template<class Key, class T, class Compare, class Allocator, class Predicate>
75
+ typename multimap<Key, T, Compare, Allocator>::size_type
76
+ erase_if(multimap<Key, T, Compare, Allocator>& c, Predicate pred);
77
+
78
  namespace pmr {
79
  template<class Key, class T, class Compare = less<Key>>
80
  using map = std::map<Key, T, Compare,
81
  polymorphic_allocator<pair<const Key, T>>>;
82
 
 
88
  ```
89
 
90
  ### Header `<set>` synopsis <a id="associative.set.syn">[[associative.set.syn]]</a>
91
 
92
  ``` cpp
93
+ #include <compare> // see [compare.syn]
94
+ #include <initializer_list> // see [initializer.list.syn]
95
 
96
  namespace std {
97
  // [set], class template set
98
+ template<class Key, class Compare = less<Key>, class Allocator = allocator<Key>>
 
99
  class set;
100
+
101
  template<class Key, class Compare, class Allocator>
102
  bool operator==(const set<Key, Compare, Allocator>& x,
103
  const set<Key, Compare, Allocator>& y);
104
  template<class Key, class Compare, class Allocator>
105
+ synth-three-way-result<Key> operator<=>(const set<Key, Compare, Allocator>& x,
106
+ \itcorr const set<Key, Compare, Allocator>& y);
107
+
 
 
 
 
 
 
 
 
 
 
 
108
  template<class Key, class Compare, class Allocator>
109
  void swap(set<Key, Compare, Allocator>& x,
110
  set<Key, Compare, Allocator>& y)
111
  noexcept(noexcept(x.swap(y)));
112
 
113
+ template<class Key, class Compare, class Allocator, class Predicate>
114
+ typename set<Key, Compare, Allocator>::size_type
115
+ erase_if(set<Key, Compare, Allocator>& c, Predicate pred);
116
+
117
  // [multiset], class template multiset
118
+ template<class Key, class Compare = less<Key>, class Allocator = allocator<Key>>
 
119
  class multiset;
120
+
121
  template<class Key, class Compare, class Allocator>
122
  bool operator==(const multiset<Key, Compare, Allocator>& x,
123
  const multiset<Key, Compare, Allocator>& y);
124
  template<class Key, class Compare, class Allocator>
125
+ synth-three-way-result<Key> operator<=>(const multiset<Key, Compare, Allocator>& x,
126
+ \itcorr const multiset<Key, Compare, Allocator>& y);
127
+
 
 
 
 
 
 
 
 
 
 
 
128
  template<class Key, class Compare, class Allocator>
129
  void swap(multiset<Key, Compare, Allocator>& x,
130
  multiset<Key, Compare, Allocator>& y)
131
  noexcept(noexcept(x.swap(y)));
132
 
133
+ template<class Key, class Compare, class Allocator, class Predicate>
134
+ typename multiset<Key, Compare, Allocator>::size_type
135
+ erase_if(multiset<Key, Compare, Allocator>& c, Predicate pred);
136
+
137
  namespace pmr {
138
  template<class Key, class Compare = less<Key>>
139
+ using set = std::set<Key, Compare, polymorphic_allocator<Key>>;
 
140
 
141
  template<class Key, class Compare = less<Key>>
142
+ using multiset = std::multiset<Key, Compare, polymorphic_allocator<Key>>;
 
143
  }
144
  }
145
  ```
146
 
147
  ### Class template `map` <a id="map">[[map]]</a>
148
 
149
+ #### Overview <a id="map.overview">[[map.overview]]</a>
150
 
151
  A `map` is an associative container that supports unique keys (contains
152
  at most one of each key value) and provides for fast retrieval of values
153
  of another type `T` based on the keys. The `map` class supports
154
  bidirectional iterators.
155
 
156
+ A `map` meets all of the requirements of a container, of a reversible
157
+ container [[container.requirements]], of an associative container
158
+ [[associative.reqmts]], and of an allocator-aware container (
159
+ [[container.alloc.req]]). A `map` also provides most operations
160
+ described in  [[associative.reqmts]] for unique keys. This means that a
161
+ `map` supports the `a_uniq` operations in  [[associative.reqmts]] but
162
+ not the `a_eq` operations. For a `map<Key,T>` the `key_type` is `Key`
163
+ and the `value_type` is `pair<const Key,T>`. Descriptions are provided
164
+ here only for operations on `map` that are not described in one of those
165
+ tables or for operations where there is additional semantic information.
 
166
 
167
  ``` cpp
168
  namespace std {
169
  template<class Key, class T, class Compare = less<Key>,
170
  class Allocator = allocator<pair<const Key, T>>>
171
  class map {
172
  public:
173
+ // types
174
  using key_type = Key;
175
  using mapped_type = T;
176
  using value_type = pair<const Key, T>;
177
  using key_compare = Compare;
178
  using allocator_type = Allocator;
 
185
  using iterator = implementation-defined // type of map::iterator; // see [container.requirements]
186
  using const_iterator = implementation-defined // type of map::const_iterator; // see [container.requirements]
187
  using reverse_iterator = std::reverse_iterator<iterator>;
188
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
189
  using node_type = unspecified;
190
+ using insert_return_type = insert-return-type<iterator, node_type>;
191
 
192
  class value_compare {
193
  friend class map;
194
  protected:
195
  Compare comp;
 
225
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
226
  is_nothrow_move_assignable_v<Compare>);
227
  map& operator=(initializer_list<value_type>);
228
  allocator_type get_allocator() const noexcept;
229
 
230
+ // iterators
231
  iterator begin() noexcept;
232
  const_iterator begin() const noexcept;
233
  iterator end() noexcept;
234
  const_iterator end() const noexcept;
235
 
 
241
  const_iterator cbegin() const noexcept;
242
  const_iterator cend() const noexcept;
243
  const_reverse_iterator crbegin() const noexcept;
244
  const_reverse_iterator crend() const noexcept;
245
 
246
+ // capacity
247
+ [[nodiscard]] bool empty() const noexcept;
248
  size_type size() const noexcept;
249
  size_type max_size() const noexcept;
250
 
251
  // [map.access], element access
252
+ mapped_type& operator[](const key_type& x);
253
+ mapped_type& operator[](key_type&& x);
254
+ mapped_type& at(const key_type& x);
255
+ const mapped_type& at(const key_type& x) const;
256
 
257
  // [map.modifiers], modifiers
258
  template<class... Args> pair<iterator, bool> emplace(Args&&... args);
259
  template<class... Args> iterator emplace_hint(const_iterator position, Args&&... args);
260
  pair<iterator, bool> insert(const value_type& x);
 
306
  template<class C2>
307
  void merge(multimap<Key, T, C2, Allocator>& source);
308
  template<class C2>
309
  void merge(multimap<Key, T, C2, Allocator>&& source);
310
 
311
+ // observers
312
  key_compare key_comp() const;
313
  value_compare value_comp() const;
314
 
315
+ // map operations
316
  iterator find(const key_type& x);
317
  const_iterator find(const key_type& x) const;
318
  template<class K> iterator find(const K& x);
319
  template<class K> const_iterator find(const K& x) const;
320
 
321
  size_type count(const key_type& x) const;
322
  template<class K> size_type count(const K& x) const;
323
 
324
+ bool contains(const key_type& x) const;
325
+ template<class K> bool contains(const K& x) const;
326
+
327
  iterator lower_bound(const key_type& x);
328
  const_iterator lower_bound(const key_type& x) const;
329
  template<class K> iterator lower_bound(const K& x);
330
  template<class K> const_iterator lower_bound(const K& x) const;
331
 
 
340
  pair<iterator, iterator> equal_range(const K& x);
341
  template<class K>
342
  pair<const_iterator, const_iterator> equal_range(const K& x) const;
343
  };
344
 
345
+ template<class InputIterator, class Compare = less<iter-key-type<InputIterator>>,
346
+ class Allocator = allocator<iter-to-alloc-type<InputIterator>>>
347
  map(InputIterator, InputIterator, Compare = Compare(), Allocator = Allocator())
348
+ -> map<iter-key-type<InputIterator>, iter-mapped-type<InputIterator>, Compare, Allocator>;
349
 
350
  template<class Key, class T, class Compare = less<Key>,
351
  class Allocator = allocator<pair<const Key, T>>>
352
+ map(initializer_list<pair<Key, T>>, Compare = Compare(), Allocator = Allocator())
353
  -> map<Key, T, Compare, Allocator>;
354
 
355
  template<class InputIterator, class Allocator>
356
  map(InputIterator, InputIterator, Allocator)
357
+ -> map<iter-key-type<InputIterator>, iter-mapped-type<InputIterator>,
358
+ less<iter-key-type<InputIterator>>, Allocator>;
359
 
360
  template<class Key, class T, class Allocator>
361
+ map(initializer_list<pair<Key, T>>, Allocator) -> map<Key, T, less<Key>, Allocator>;
362
 
363
+ // swap
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
364
  template<class Key, class T, class Compare, class Allocator>
365
  void swap(map<Key, T, Compare, Allocator>& x,
366
  map<Key, T, Compare, Allocator>& y)
367
  noexcept(noexcept(x.swap(y)));
368
  }
369
  ```
370
 
371
+ #### Constructors, copy, and assignment <a id="map.cons">[[map.cons]]</a>
372
 
373
  ``` cpp
374
  explicit map(const Compare& comp, const Allocator& = Allocator());
375
  ```
376
 
 
390
  `last`).
391
 
392
  *Complexity:* Linear in N if the range \[`first`, `last`) is already
393
  sorted using `comp` and otherwise N log N, where N is `last - first`.
394
 
395
+ #### Element access <a id="map.access">[[map.access]]</a>
396
 
397
  ``` cpp
398
+ mapped_type& operator[](const key_type& x);
399
  ```
400
 
401
  *Effects:* Equivalent to: `return try_emplace(x).first->second;`
402
 
403
  ``` cpp
404
+ mapped_type& operator[](key_type&& x);
405
  ```
406
 
407
  *Effects:* Equivalent to: `return try_emplace(move(x)).first->second;`
408
 
409
  ``` cpp
410
+ mapped_type& at(const key_type& x);
411
+ const mapped_type& at(const key_type& x) const;
412
  ```
413
 
414
  *Returns:* A reference to the `mapped_type` corresponding to `x` in
415
  `*this`.
416
 
417
  *Throws:* An exception object of type `out_of_range` if no such element
418
  is present.
419
 
420
  *Complexity:* Logarithmic.
421
 
422
+ #### Modifiers <a id="map.modifiers">[[map.modifiers]]</a>
423
 
424
  ``` cpp
425
  template<class P>
426
  pair<iterator, bool> insert(P&& x);
427
  template<class P>
428
  iterator insert(const_iterator position, P&& x);
429
  ```
430
 
431
+ *Constraints:* `is_constructible_v<value_type, P&&>` is `true`.
432
+
433
  *Effects:* The first form is equivalent to
434
  `return emplace(std::forward<P>(x))`. The second form is equivalent to
435
  `return emplace_hint(position, std::forward<P>(x))`.
436
 
 
 
 
437
  ``` cpp
438
  template<class... Args>
439
  pair<iterator, bool> try_emplace(const key_type& k, Args&&... args);
440
  template<class... Args>
441
  iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args);
442
  ```
443
 
444
+ *Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into `map`
445
+ from `piecewise_construct`, `forward_as_tuple(k)`,
446
  `forward_as_tuple(std::forward<Args>(args)...)`.
447
 
448
  *Effects:* If the map already contains an element whose key is
449
  equivalent to `k`, there is no effect. Otherwise inserts an object of
450
  type `value_type` constructed with `piecewise_construct`,
 
461
  pair<iterator, bool> try_emplace(key_type&& k, Args&&... args);
462
  template<class... Args>
463
  iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args);
464
  ```
465
 
466
+ *Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into `map`
467
+ from `piecewise_construct`, `forward_as_tuple(std::move(k))`,
468
  `forward_as_tuple(std::forward<Args>(args)...)`.
469
 
470
  *Effects:* If the map already contains an element whose key is
471
  equivalent to `k`, there is no effect. Otherwise inserts an object of
472
  type `value_type` constructed with `piecewise_construct`,
 
484
  pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj);
485
  template<class M>
486
  iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj);
487
  ```
488
 
489
+ *Mandates:* `is_assignable_v<mapped_type&, M&&>` is `true`.
490
+
491
+ *Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into `map`
492
+ from `k`, `forward<M>(obj)`.
493
 
494
  *Effects:* If the map already contains an element `e` whose key is
495
  equivalent to `k`, assigns `std::forward<M>(obj)` to `e.second`.
496
  Otherwise inserts an object of type `value_type` constructed with `k`,
497
  `std::forward<M>(obj)`.
 
507
  pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj);
508
  template<class M>
509
  iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj);
510
  ```
511
 
512
+ *Mandates:* `is_assignable_v<mapped_type&, M&&>` is `true`.
513
+
514
+ *Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into `map`
515
+ from `move(k)`, `forward<M>(obj)`.
516
 
517
  *Effects:* If the map already contains an element `e` whose key is
518
  equivalent to `k`, assigns `std::forward<M>(obj)` to `e.second`.
519
  Otherwise inserts an object of type `value_type` constructed with
520
  `std::move(k)`, `std::forward<M>(obj)`.
 
523
  pair is `true` if and only if the insertion took place. The returned
524
  iterator points to the map element whose key is equivalent to `k`.
525
 
526
  *Complexity:* The same as `emplace` and `emplace_hint`, respectively.
527
 
528
+ #### Erasure <a id="map.erasure">[[map.erasure]]</a>
529
 
530
  ``` cpp
531
+ template<class Key, class T, class Compare, class Allocator, class Predicate>
532
+ typename map<Key, T, Compare, Allocator>::size_type
533
+ erase_if(map<Key, T, Compare, Allocator>& c, Predicate pred);
 
534
  ```
535
 
536
+ *Effects:* Equivalent to:
537
+
538
+ ``` cpp
539
+ auto original_size = c.size();
540
+ for (auto i = c.begin(), last = c.end(); i != last; ) {
541
+ if (pred(*i)) {
542
+ i = c.erase(i);
543
+ } else {
544
+ ++i;
545
+ }
546
+ }
547
+ return original_size - c.size();
548
+ ```
549
 
550
  ### Class template `multimap` <a id="multimap">[[multimap]]</a>
551
 
552
+ #### Overview <a id="multimap.overview">[[multimap.overview]]</a>
553
 
554
  A `multimap` is an associative container that supports equivalent keys
555
  (possibly containing multiple copies of the same key value) and provides
556
  for fast retrieval of values of another type `T` based on the keys. The
557
  `multimap` class supports bidirectional iterators.
558
 
559
+ A `multimap` meets all of the requirements of a container and of a
560
+ reversible container [[container.requirements]], of an associative
561
+ container [[associative.reqmts]], and of an allocator-aware container (
562
+ [[container.alloc.req]]). A `multimap` also provides most operations
563
+ described in  [[associative.reqmts]] for equal keys. This means that a
564
+ `multimap` supports the `a_eq` operations in  [[associative.reqmts]] but
565
+ not the `a_uniq` operations. For a `multimap<Key,T>` the `key_type` is
566
+ `Key` and the `value_type` is `pair<const Key,T>`. Descriptions are
567
+ provided here only for operations on `multimap` that are not described
568
+ in one of those tables or for operations where there is additional
569
+ semantic information.
570
 
571
  ``` cpp
572
  namespace std {
573
  template<class Key, class T, class Compare = less<Key>,
574
  class Allocator = allocator<pair<const Key, T>>>
575
  class multimap {
576
  public:
577
+ // types
578
  using key_type = Key;
579
  using mapped_type = T;
580
  using value_type = pair<const Key, T>;
581
  using key_compare = Compare;
582
  using allocator_type = Allocator;
 
629
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
630
  is_nothrow_move_assignable_v<Compare>);
631
  multimap& operator=(initializer_list<value_type>);
632
  allocator_type get_allocator() const noexcept;
633
 
634
+ // iterators
635
  iterator begin() noexcept;
636
  const_iterator begin() const noexcept;
637
  iterator end() noexcept;
638
  const_iterator end() const noexcept;
639
 
 
645
  const_iterator cbegin() const noexcept;
646
  const_iterator cend() const noexcept;
647
  const_reverse_iterator crbegin() const noexcept;
648
  const_reverse_iterator crend() const noexcept;
649
 
650
+ // capacity
651
+ [[nodiscard]] bool empty() const noexcept;
652
  size_type size() const noexcept;
653
  size_type max_size() const noexcept;
654
 
655
  // [multimap.modifiers], modifiers
656
  template<class... Args> iterator emplace(Args&&... args);
 
686
  template<class C2>
687
  void merge(map<Key, T, C2, Allocator>& source);
688
  template<class C2>
689
  void merge(map<Key, T, C2, Allocator>&& source);
690
 
691
+ // observers
692
  key_compare key_comp() const;
693
  value_compare value_comp() const;
694
 
695
+ // map operations
696
  iterator find(const key_type& x);
697
  const_iterator find(const key_type& x) const;
698
  template<class K> iterator find(const K& x);
699
  template<class K> const_iterator find(const K& x) const;
700
 
701
  size_type count(const key_type& x) const;
702
  template<class K> size_type count(const K& x) const;
703
 
704
+ bool contains(const key_type& x) const;
705
+ template<class K> bool contains(const K& x) const;
706
+
707
  iterator lower_bound(const key_type& x);
708
  const_iterator lower_bound(const key_type& x) const;
709
  template<class K> iterator lower_bound(const K& x);
710
  template<class K> const_iterator lower_bound(const K& x) const;
711
 
 
720
  pair<iterator, iterator> equal_range(const K& x);
721
  template<class K>
722
  pair<const_iterator, const_iterator> equal_range(const K& x) const;
723
  };
724
 
725
+ template<class InputIterator, class Compare = less<iter-key-type<InputIterator>>,
726
+ class Allocator = allocator<iter-to-alloc-type<InputIterator>>>
727
  multimap(InputIterator, InputIterator, Compare = Compare(), Allocator = Allocator())
728
+ -> multimap<iter-key-type<InputIterator>, iter-mapped-type<InputIterator>,
729
+ Compare, Allocator>;
730
 
731
  template<class Key, class T, class Compare = less<Key>,
732
  class Allocator = allocator<pair<const Key, T>>>
733
+ multimap(initializer_list<pair<Key, T>>, Compare = Compare(), Allocator = Allocator())
734
  -> multimap<Key, T, Compare, Allocator>;
735
 
736
  template<class InputIterator, class Allocator>
737
  multimap(InputIterator, InputIterator, Allocator)
738
+ -> multimap<iter-key-type<InputIterator>, iter-mapped-type<InputIterator>,
739
+ less<iter-key-type<InputIterator>>, Allocator>;
740
 
741
  template<class Key, class T, class Allocator>
742
+ multimap(initializer_list<pair<Key, T>>, Allocator)
743
  -> multimap<Key, T, less<Key>, Allocator>;
744
 
745
+ // swap
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
746
  template<class Key, class T, class Compare, class Allocator>
747
  void swap(multimap<Key, T, Compare, Allocator>& x,
748
  multimap<Key, T, Compare, Allocator>& y)
749
  noexcept(noexcept(x.swap(y)));
750
  }
751
  ```
752
 
753
+ #### Constructors <a id="multimap.cons">[[multimap.cons]]</a>
754
 
755
  ``` cpp
756
  explicit multimap(const Compare& comp, const Allocator& = Allocator());
757
  ```
758
 
 
773
  `last`).
774
 
775
  *Complexity:* Linear in N if the range \[`first`, `last`) is already
776
  sorted using `comp` and otherwise N log N, where N is `last - first`.
777
 
778
+ #### Modifiers <a id="multimap.modifiers">[[multimap.modifiers]]</a>
779
 
780
  ``` cpp
781
  template<class P> iterator insert(P&& x);
782
  template<class P> iterator insert(const_iterator position, P&& x);
783
  ```
784
 
785
+ *Constraints:* `is_constructible_v<value_type, P&&>` is `true`.
786
+
787
  *Effects:* The first form is equivalent to
788
  `return emplace(std::forward<P>(x))`. The second form is equivalent to
789
  `return emplace_hint(position, std::forward<P>(x))`.
790
 
791
+ #### Erasure <a id="multimap.erasure">[[multimap.erasure]]</a>
 
 
 
792
 
793
  ``` cpp
794
+ template<class Key, class T, class Compare, class Allocator, class Predicate>
795
+ typename multimap<Key, T, Compare, Allocator>::size_type
796
+ erase_if(multimap<Key, T, Compare, Allocator>& c, Predicate pred);
 
797
  ```
798
 
799
+ *Effects:* Equivalent to:
800
+
801
+ ``` cpp
802
+ auto original_size = c.size();
803
+ for (auto i = c.begin(), last = c.end(); i != last; ) {
804
+ if (pred(*i)) {
805
+ i = c.erase(i);
806
+ } else {
807
+ ++i;
808
+ }
809
+ }
810
+ return original_size - c.size();
811
+ ```
812
 
813
  ### Class template `set` <a id="set">[[set]]</a>
814
 
815
+ #### Overview <a id="set.overview">[[set.overview]]</a>
816
 
817
  A `set` is an associative container that supports unique keys (contains
818
  at most one of each key value) and provides for fast retrieval of the
819
  keys themselves. The `set` class supports bidirectional iterators.
820
 
821
+ A `set` meets all of the requirements of a container, of a reversible
822
+ container [[container.requirements]], of an associative container
823
+ [[associative.reqmts]], and of an allocator-aware container (
824
+ [[container.alloc.req]]). A `set` also provides most operations
825
+ described in  [[associative.reqmts]] for unique keys. This means that a
826
+ `set` supports the `a_uniq` operations in  [[associative.reqmts]] but
827
+ not the `a_eq` operations. For a `set<Key>` both the `key_type` and
828
+ `value_type` are `Key`. Descriptions are provided here only for
829
+ operations on `set` that are not described in one of these tables and
830
+ for operations where there is additional semantic information.
 
831
 
832
  ``` cpp
833
  namespace std {
834
  template<class Key, class Compare = less<Key>,
835
  class Allocator = allocator<Key>>
836
  class set {
837
  public:
838
+ // types
839
  using key_type = Key;
840
  using key_compare = Compare;
841
  using value_type = Key;
842
  using value_compare = Compare;
843
  using allocator_type = Allocator;
 
850
  using iterator = implementation-defined // type of set::iterator; // see [container.requirements]
851
  using const_iterator = implementation-defined // type of set::const_iterator; // see [container.requirements]
852
  using reverse_iterator = std::reverse_iterator<iterator>;
853
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
854
  using node_type = unspecified;
855
+ using insert_return_type = insert-return-type<iterator, node_type>;
856
 
857
  // [set.cons], construct/copy/destroy
858
  set() : set(Compare()) { }
859
  explicit set(const Compare& comp, const Allocator& = Allocator());
860
  template<class InputIterator>
 
878
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
879
  is_nothrow_move_assignable_v<Compare>);
880
  set& operator=(initializer_list<value_type>);
881
  allocator_type get_allocator() const noexcept;
882
 
883
+ // iterators
884
  iterator begin() noexcept;
885
  const_iterator begin() const noexcept;
886
  iterator end() noexcept;
887
  const_iterator end() const noexcept;
888
 
 
894
  const_iterator cbegin() const noexcept;
895
  const_iterator cend() const noexcept;
896
  const_reverse_iterator crbegin() const noexcept;
897
  const_reverse_iterator crend() const noexcept;
898
 
899
+ // capacity
900
+ [[nodiscard]] bool empty() const noexcept;
901
  size_type size() const noexcept;
902
  size_type max_size() const noexcept;
903
 
904
+ // modifiers
905
  template<class... Args> pair<iterator, bool> emplace(Args&&... args);
906
  template<class... Args> iterator emplace_hint(const_iterator position, Args&&... args);
907
  pair<iterator,bool> insert(const value_type& x);
908
  pair<iterator,bool> insert(value_type&& x);
909
  iterator insert(const_iterator position, const value_type& x);
 
933
  template<class C2>
934
  void merge(multiset<Key, C2, Allocator>& source);
935
  template<class C2>
936
  void merge(multiset<Key, C2, Allocator>&& source);
937
 
938
+ // observers
939
  key_compare key_comp() const;
940
  value_compare value_comp() const;
941
 
942
+ // set operations
943
  iterator find(const key_type& x);
944
  const_iterator find(const key_type& x) const;
945
  template<class K> iterator find(const K& x);
946
  template<class K> const_iterator find(const K& x) const;
947
 
948
  size_type count(const key_type& x) const;
949
  template<class K> size_type count(const K& x) const;
950
 
951
+ bool contains(const key_type& x) const;
952
+ template<class K> bool contains(const K& x) const;
953
+
954
  iterator lower_bound(const key_type& x);
955
  const_iterator lower_bound(const key_type& x) const;
956
  template<class K> iterator lower_bound(const K& x);
957
  template<class K> const_iterator lower_bound(const K& x) const;
958
 
 
968
  template<class K>
969
  pair<const_iterator, const_iterator> equal_range(const K& x) const;
970
  };
971
 
972
  template<class InputIterator,
973
+ class Compare = less<iter-value-type<InputIterator>>,
974
+ class Allocator = allocator<iter-value-type<InputIterator>>>
975
  set(InputIterator, InputIterator,
976
  Compare = Compare(), Allocator = Allocator())
977
+ -> set<iter-value-type<InputIterator>, Compare, Allocator>;
978
 
979
  template<class Key, class Compare = less<Key>, class Allocator = allocator<Key>>
980
  set(initializer_list<Key>, Compare = Compare(), Allocator = Allocator())
981
  -> set<Key, Compare, Allocator>;
982
 
983
  template<class InputIterator, class Allocator>
984
  set(InputIterator, InputIterator, Allocator)
985
+ -> set<iter-value-type<InputIterator>,
986
+ less<iter-value-type<InputIterator>>, Allocator>;
987
 
988
  template<class Key, class Allocator>
989
  set(initializer_list<Key>, Allocator) -> set<Key, less<Key>, Allocator>;
990
 
991
+ // swap
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
992
  template<class Key, class Compare, class Allocator>
993
  void swap(set<Key, Compare, Allocator>& x,
994
  set<Key, Compare, Allocator>& y)
995
  noexcept(noexcept(x.swap(y)));
996
  }
997
  ```
998
 
999
+ #### Constructors, copy, and assignment <a id="set.cons">[[set.cons]]</a>
1000
 
1001
  ``` cpp
1002
  explicit set(const Compare& comp, const Allocator& = Allocator());
1003
  ```
1004
 
 
1018
  `last`).
1019
 
1020
  *Complexity:* Linear in N if the range \[`first`, `last`) is already
1021
  sorted using `comp` and otherwise N log N, where N is `last - first`.
1022
 
1023
+ #### Erasure <a id="set.erasure">[[set.erasure]]</a>
1024
 
1025
  ``` cpp
1026
+ template<class Key, class Compare, class Allocator, class Predicate>
1027
+ typename set<Key, Compare, Allocator>::size_type
1028
+ erase_if(set<Key, Compare, Allocator>& c, Predicate pred);
 
1029
  ```
1030
 
1031
+ *Effects:* Equivalent to:
1032
+
1033
+ ``` cpp
1034
+ auto original_size = c.size();
1035
+ for (auto i = c.begin(), last = c.end(); i != last; ) {
1036
+ if (pred(*i)) {
1037
+ i = c.erase(i);
1038
+ } else {
1039
+ ++i;
1040
+ }
1041
+ }
1042
+ return original_size - c.size();
1043
+ ```
1044
 
1045
  ### Class template `multiset` <a id="multiset">[[multiset]]</a>
1046
 
1047
+ #### Overview <a id="multiset.overview">[[multiset.overview]]</a>
1048
 
1049
  A `multiset` is an associative container that supports equivalent keys
1050
  (possibly contains multiple copies of the same key value) and provides
1051
  for fast retrieval of the keys themselves. The `multiset` class supports
1052
  bidirectional iterators.
1053
 
1054
+ A `multiset` meets all of the requirements of a container, of a
1055
+ reversible container [[container.requirements]], of an associative
1056
+ container [[associative.reqmts]], and of an allocator-aware container (
1057
+ [[container.alloc.req]]). `multiset` also provides most operations
1058
+ described in  [[associative.reqmts]] for duplicate keys. This means that
1059
+ a `multiset` supports the `a_eq` operations in  [[associative.reqmts]]
1060
+ but not the `a_uniq` operations. For a `multiset<Key>` both the
1061
+ `key_type` and `value_type` are `Key`. Descriptions are provided here
1062
+ only for operations on `multiset` that are not described in one of these
1063
+ tables and for operations where there is additional semantic
1064
+ information.
1065
 
1066
  ``` cpp
1067
  namespace std {
1068
  template<class Key, class Compare = less<Key>,
1069
  class Allocator = allocator<Key>>
1070
  class multiset {
1071
  public:
1072
+ // types
1073
  using key_type = Key;
1074
  using key_compare = Compare;
1075
  using value_type = Key;
1076
  using value_compare = Compare;
1077
  using allocator_type = Allocator;
 
1111
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
1112
  is_nothrow_move_assignable_v<Compare>);
1113
  multiset& operator=(initializer_list<value_type>);
1114
  allocator_type get_allocator() const noexcept;
1115
 
1116
+ // iterators
1117
  iterator begin() noexcept;
1118
  const_iterator begin() const noexcept;
1119
  iterator end() noexcept;
1120
  const_iterator end() const noexcept;
1121
 
 
1127
  const_iterator cbegin() const noexcept;
1128
  const_iterator cend() const noexcept;
1129
  const_reverse_iterator crbegin() const noexcept;
1130
  const_reverse_iterator crend() const noexcept;
1131
 
1132
+ // capacity
1133
+ [[nodiscard]] bool empty() const noexcept;
1134
  size_type size() const noexcept;
1135
  size_type max_size() const noexcept;
1136
 
1137
+ // modifiers
1138
  template<class... Args> iterator emplace(Args&&... args);
1139
  template<class... Args> iterator emplace_hint(const_iterator position, Args&&... args);
1140
  iterator insert(const value_type& x);
1141
  iterator insert(value_type&& x);
1142
  iterator insert(const_iterator position, const value_type& x);
 
1166
  template<class C2>
1167
  void merge(set<Key, C2, Allocator>& source);
1168
  template<class C2>
1169
  void merge(set<Key, C2, Allocator>&& source);
1170
 
1171
+ // observers
1172
  key_compare key_comp() const;
1173
  value_compare value_comp() const;
1174
 
1175
+ // set operations
1176
  iterator find(const key_type& x);
1177
  const_iterator find(const key_type& x) const;
1178
  template<class K> iterator find(const K& x);
1179
  template<class K> const_iterator find(const K& x) const;
1180
 
1181
  size_type count(const key_type& x) const;
1182
  template<class K> size_type count(const K& x) const;
1183
 
1184
+ bool contains(const key_type& x) const;
1185
+ template<class K> bool contains(const K& x) const;
1186
+
1187
  iterator lower_bound(const key_type& x);
1188
  const_iterator lower_bound(const key_type& x) const;
1189
  template<class K> iterator lower_bound(const K& x);
1190
  template<class K> const_iterator lower_bound(const K& x) const;
1191
 
 
1201
  template<class K>
1202
  pair<const_iterator, const_iterator> equal_range(const K& x) const;
1203
  };
1204
 
1205
  template<class InputIterator,
1206
+ class Compare = less<iter-value-type<InputIterator>>,
1207
+ class Allocator = allocator<iter-value-type<InputIterator>>>
1208
  multiset(InputIterator, InputIterator,
1209
  Compare = Compare(), Allocator = Allocator())
1210
+ -> multiset<iter-value-type<InputIterator>, Compare, Allocator>;
1211
 
1212
  template<class Key, class Compare = less<Key>, class Allocator = allocator<Key>>
1213
  multiset(initializer_list<Key>, Compare = Compare(), Allocator = Allocator())
1214
  -> multiset<Key, Compare, Allocator>;
1215
 
1216
  template<class InputIterator, class Allocator>
1217
  multiset(InputIterator, InputIterator, Allocator)
1218
+ -> multiset<iter-value-type<InputIterator>,
1219
+ less<iter-value-type<InputIterator>>, Allocator>;
1220
 
1221
  template<class Key, class Allocator>
1222
  multiset(initializer_list<Key>, Allocator) -> multiset<Key, less<Key>, Allocator>;
1223
 
1224
+ // swap
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1225
  template<class Key, class Compare, class Allocator>
1226
  void swap(multiset<Key, Compare, Allocator>& x,
1227
  multiset<Key, Compare, Allocator>& y)
1228
  noexcept(noexcept(x.swap(y)));
1229
  }
1230
  ```
1231
 
1232
+ #### Constructors <a id="multiset.cons">[[multiset.cons]]</a>
1233
 
1234
  ``` cpp
1235
  explicit multiset(const Compare& comp, const Allocator& = Allocator());
1236
  ```
1237
 
 
1251
  `last`).
1252
 
1253
  *Complexity:* Linear in N if the range \[`first`, `last`) is already
1254
  sorted using `comp` and otherwise N log N, where N is `last - first`.
1255
 
1256
+ #### Erasure <a id="multiset.erasure">[[multiset.erasure]]</a>
1257
 
1258
  ``` cpp
1259
+ template<class Key, class Compare, class Allocator, class Predicate>
1260
+ typename multiset<Key, Compare, Allocator>::size_type
1261
+ erase_if(multiset<Key, Compare, Allocator>& c, Predicate pred);
 
1262
  ```
1263
 
1264
+ *Effects:* Equivalent to:
1265
+
1266
+ ``` cpp
1267
+ auto original_size = c.size();
1268
+ for (auto i = c.begin(), last = c.end(); i != last; ) {
1269
+ if (pred(*i)) {
1270
+ i = c.erase(i);
1271
+ } else {
1272
+ ++i;
1273
+ }
1274
+ }
1275
+ return original_size - c.size();
1276
+ ```
1277