From Jason Turner

[unord]

C++23 → Trunk 94.2 KB 1256 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/tmplbsb5njp/{from.md → to.md} +667 -552
tmp/tmplbsb5njp/{from.md → to.md} RENAMED
@@ -1,8 +1,8 @@
1
  ## Unordered associative containers <a id="unord">[[unord]]</a>
2
 
3
- ### In general <a id="unord.general">[[unord.general]]</a>
4
 
5
  The header `<unordered_map>` defines the class templates `unordered_map`
6
  and `unordered_multimap`; the header `<unordered_set>` defines the class
7
  templates `unordered_set` and `unordered_multiset`.
8
 
@@ -34,35 +34,35 @@ namespace std {
34
  class Pred = equal_to<Key>,
35
  class Alloc = allocator<pair<const Key, T>>>
36
  class unordered_multimap;
37
 
38
  template<class Key, class T, class Hash, class Pred, class Alloc>
39
- bool operator==(const unordered_map<Key, T, Hash, Pred, Alloc>& a,
40
  const unordered_map<Key, T, Hash, Pred, Alloc>& b);
41
 
42
  template<class Key, class T, class Hash, class Pred, class Alloc>
43
- bool operator==(const unordered_multimap<Key, T, Hash, Pred, Alloc>& a,
44
  const unordered_multimap<Key, T, Hash, Pred, Alloc>& b);
45
 
46
  template<class Key, class T, class Hash, class Pred, class Alloc>
47
- void swap(unordered_map<Key, T, Hash, Pred, Alloc>& x,
48
  unordered_map<Key, T, Hash, Pred, Alloc>& y)
49
  noexcept(noexcept(x.swap(y)));
50
 
51
  template<class Key, class T, class Hash, class Pred, class Alloc>
52
- void swap(unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
53
  unordered_multimap<Key, T, Hash, Pred, Alloc>& y)
54
  noexcept(noexcept(x.swap(y)));
55
 
56
  // [unord.map.erasure], erasure for unordered_map
57
  template<class K, class T, class H, class P, class A, class Predicate>
58
- typename unordered_map<K, T, H, P, A>::size_type
59
  erase_if(unordered_map<K, T, H, P, A>& c, Predicate pred);
60
 
61
  // [unord.multimap.erasure], erasure for unordered_multimap
62
  template<class K, class T, class H, class P, class A, class Predicate>
63
- typename unordered_multimap<K, T, H, P, A>::size_type
64
  erase_if(unordered_multimap<K, T, H, P, A>& c, Predicate pred);
65
 
66
  namespace pmr {
67
  template<class Key,
68
  class T,
@@ -81,75 +81,10 @@ namespace std {
81
 
82
  }
83
  }
84
  ```
85
 
86
- ### Header `<unordered_set>` synopsis <a id="unord.set.syn">[[unord.set.syn]]</a>
87
-
88
- ``` cpp
89
- #include <compare> // see [compare.syn]
90
- #include <initializer_list> // see [initializer.list.syn]
91
-
92
- namespace std {
93
- // [unord.set], class template unordered_set
94
- template<class Key,
95
- class Hash = hash<Key>,
96
- class Pred = equal_to<Key>,
97
- class Alloc = allocator<Key>>
98
- class unordered_set;
99
-
100
- // [unord.multiset], class template unordered_multiset
101
- template<class Key,
102
- class Hash = hash<Key>,
103
- class Pred = equal_to<Key>,
104
- class Alloc = allocator<Key>>
105
- class unordered_multiset;
106
-
107
- template<class Key, class Hash, class Pred, class Alloc>
108
- bool operator==(const unordered_set<Key, Hash, Pred, Alloc>& a,
109
- const unordered_set<Key, Hash, Pred, Alloc>& b);
110
-
111
- template<class Key, class Hash, class Pred, class Alloc>
112
- bool operator==(const unordered_multiset<Key, Hash, Pred, Alloc>& a,
113
- const unordered_multiset<Key, Hash, Pred, Alloc>& b);
114
-
115
- template<class Key, class Hash, class Pred, class Alloc>
116
- void swap(unordered_set<Key, Hash, Pred, Alloc>& x,
117
- unordered_set<Key, Hash, Pred, Alloc>& y)
118
- noexcept(noexcept(x.swap(y)));
119
-
120
- template<class Key, class Hash, class Pred, class Alloc>
121
- void swap(unordered_multiset<Key, Hash, Pred, Alloc>& x,
122
- unordered_multiset<Key, Hash, Pred, Alloc>& y)
123
- noexcept(noexcept(x.swap(y)));
124
-
125
- // [unord.set.erasure], erasure for unordered_set
126
- template<class K, class H, class P, class A, class Predicate>
127
- typename unordered_set<K, H, P, A>::size_type
128
- erase_if(unordered_set<K, H, P, A>& c, Predicate pred);
129
-
130
- // [unord.multiset.erasure], erasure for unordered_multiset
131
- template<class K, class H, class P, class A, class Predicate>
132
- typename unordered_multiset<K, H, P, A>::size_type
133
- erase_if(unordered_multiset<K, H, P, A>& c, Predicate pred);
134
-
135
- namespace pmr {
136
- template<class Key,
137
- class Hash = hash<Key>,
138
- class Pred = equal_to<Key>>
139
- using unordered_set = std::unordered_set<Key, Hash, Pred,
140
- polymorphic_allocator<Key>>;
141
-
142
- template<class Key,
143
- class Hash = hash<Key>,
144
- class Pred = equal_to<Key>>
145
- using unordered_multiset = std::unordered_multiset<Key, Hash, Pred,
146
- polymorphic_allocator<Key>>;
147
- }
148
- }
149
- ```
150
-
151
  ### Class template `unordered_map` <a id="unord.map">[[unord.map]]</a>
152
 
153
  #### Overview <a id="unord.map.overview">[[unord.map.overview]]</a>
154
 
155
  An `unordered_map` is an unordered associative container that supports
@@ -168,10 +103,13 @@ the `a_uniq` operations in that table, not the `a_eq` operations. For an
168
 
169
  Subclause  [[unord.map]] only describes operations on `unordered_map`
170
  that are not described in one of the requirement tables, or for which
171
  there is additional semantic information.
172
 
 
 
 
173
  ``` cpp
174
  namespace std {
175
  template<class Key,
176
  class T,
177
  class Hash = hash<Key>,
@@ -184,12 +122,12 @@ namespace std {
184
  using mapped_type = T;
185
  using value_type = pair<const Key, T>;
186
  using hasher = Hash;
187
  using key_equal = Pred;
188
  using allocator_type = Allocator;
189
- using pointer = typename allocator_traits<Allocator>::pointer;
190
- using const_pointer = typename allocator_traits<Allocator>::const_pointer;
191
  using reference = value_type&;
192
  using const_reference = const value_type&;
193
  using size_type = implementation-defined // type of unordered_map::size_type; // see [container.requirements]
194
  using difference_type = implementation-defined // type of unordered_map::difference_type; // see [container.requirements]
195
 
@@ -199,185 +137,197 @@ namespace std {
199
  using const_local_iterator = implementation-defined // type of unordered_map::const_local_iterator; // see [container.requirements]
200
  using node_type = unspecified;
201
  using insert_return_type = insert-return-type<iterator, node_type>;
202
 
203
  // [unord.map.cnstr], construct/copy/destroy
204
- unordered_map();
205
- explicit unordered_map(size_type n,
206
- const hasher& hf = hasher(),
207
  const key_equal& eql = key_equal(),
208
  const allocator_type& a = allocator_type());
209
  template<class InputIterator>
210
- unordered_map(InputIterator f, InputIterator l,
211
- size_type n = see below,
212
- const hasher& hf = hasher(),
213
  const key_equal& eql = key_equal(),
214
  const allocator_type& a = allocator_type());
215
 
216
  template<container-compatible-range<value_type> R>
217
- unordered_map(from_range_t, R&& rg, size_type n = see below,
218
  const hasher& hf = hasher(), const key_equal& eql = key_equal(),
219
  const allocator_type& a = allocator_type());
220
- unordered_map(const unordered_map&);
221
- unordered_map(unordered_map&&);
222
- explicit unordered_map(const Allocator&);
223
- unordered_map(const unordered_map&, const type_identity_t<Allocator>&);
224
- unordered_map(unordered_map&&, const type_identity_t<Allocator>&);
225
- unordered_map(initializer_list<value_type> il,
226
- size_type n = see below,
227
  const hasher& hf = hasher(),
228
  const key_equal& eql = key_equal(),
229
  const allocator_type& a = allocator_type());
230
- unordered_map(size_type n, const allocator_type& a)
231
  : unordered_map(n, hasher(), key_equal(), a) { }
232
- unordered_map(size_type n, const hasher& hf, const allocator_type& a)
233
  : unordered_map(n, hf, key_equal(), a) { }
234
  template<class InputIterator>
235
- unordered_map(InputIterator f, InputIterator l, size_type n, const allocator_type& a)
 
236
  : unordered_map(f, l, n, hasher(), key_equal(), a) { }
237
  template<class InputIterator>
238
- unordered_map(InputIterator f, InputIterator l, size_type n, const hasher& hf,
239
  const allocator_type& a)
240
  : unordered_map(f, l, n, hf, key_equal(), a) { }
241
  template<container-compatible-range<value_type> R>
242
- unordered_map(from_range_t, R&& rg, size_type n, const allocator_type& a)
243
  : unordered_map(from_range, std::forward<R>(rg), n, hasher(), key_equal(), a) { }
244
  template<container-compatible-range<value_type> R>
245
- unordered_map(from_range_t, R&& rg, size_type n, const hasher& hf, const allocator_type& a)
 
246
  : unordered_map(from_range, std::forward<R>(rg), n, hf, key_equal(), a) { }
247
- unordered_map(initializer_list<value_type> il, size_type n, const allocator_type& a)
 
248
  : unordered_map(il, n, hasher(), key_equal(), a) { }
249
- unordered_map(initializer_list<value_type> il, size_type n, const hasher& hf,
250
  const allocator_type& a)
251
  : unordered_map(il, n, hf, key_equal(), a) { }
252
- ~unordered_map();
253
- unordered_map& operator=(const unordered_map&);
254
- unordered_map& operator=(unordered_map&&)
255
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
256
  is_nothrow_move_assignable_v<Hash> &&
257
  is_nothrow_move_assignable_v<Pred>);
258
- unordered_map& operator=(initializer_list<value_type>);
259
- allocator_type get_allocator() const noexcept;
260
 
261
  // iterators
262
- iterator begin() noexcept;
263
- const_iterator begin() const noexcept;
264
- iterator end() noexcept;
265
- const_iterator end() const noexcept;
266
- const_iterator cbegin() const noexcept;
267
- const_iterator cend() const noexcept;
268
 
269
  // capacity
270
- [[nodiscard]] bool empty() const noexcept;
271
- size_type size() const noexcept;
272
- size_type max_size() const noexcept;
273
 
274
  // [unord.map.modifiers], modifiers
275
- template<class... Args> pair<iterator, bool> emplace(Args&&... args);
276
- template<class... Args> iterator emplace_hint(const_iterator position, Args&&... args);
277
- pair<iterator, bool> insert(const value_type& obj);
278
- pair<iterator, bool> insert(value_type&& obj);
279
- template<class P> pair<iterator, bool> insert(P&& obj);
280
- iterator insert(const_iterator hint, const value_type& obj);
281
- iterator insert(const_iterator hint, value_type&& obj);
282
- template<class P> iterator insert(const_iterator hint, P&& obj);
283
- template<class InputIterator> void insert(InputIterator first, InputIterator last);
 
284
  template<container-compatible-range<value_type> R>
285
- void insert_range(R&& rg);
286
- void insert(initializer_list<value_type>);
287
 
288
- node_type extract(const_iterator position);
289
- node_type extract(const key_type& x);
290
- template<class K> node_type extract(K&& x);
291
- insert_return_type insert(node_type&& nh);
292
- iterator insert(const_iterator hint, node_type&& nh);
293
 
294
  template<class... Args>
295
- pair<iterator, bool> try_emplace(const key_type& k, Args&&... args);
296
  template<class... Args>
297
- pair<iterator, bool> try_emplace(key_type&& k, Args&&... args);
 
 
298
  template<class... Args>
299
- iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args);
300
  template<class... Args>
301
- iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args);
 
 
302
  template<class M>
303
- pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj);
304
  template<class M>
305
- pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj);
 
 
306
  template<class M>
307
- iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj);
308
  template<class M>
309
- iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj);
 
 
310
 
311
- iterator erase(iterator position);
312
- iterator erase(const_iterator position);
313
- size_type erase(const key_type& k);
314
- template<class K> size_type erase(K&& x);
315
- iterator erase(const_iterator first, const_iterator last);
316
- void swap(unordered_map&)
317
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
318
- is_nothrow_swappable_v<Hash> &&
319
- is_nothrow_swappable_v<Pred>);
320
- void clear() noexcept;
321
 
322
  template<class H2, class P2>
323
- void merge(unordered_map<Key, T, H2, P2, Allocator>& source);
324
  template<class H2, class P2>
325
- void merge(unordered_map<Key, T, H2, P2, Allocator>&& source);
326
  template<class H2, class P2>
327
- void merge(unordered_multimap<Key, T, H2, P2, Allocator>& source);
328
  template<class H2, class P2>
329
- void merge(unordered_multimap<Key, T, H2, P2, Allocator>&& source);
330
 
331
  // observers
332
- hasher hash_function() const;
333
- key_equal key_eq() const;
334
 
335
  // map operations
336
- iterator find(const key_type& k);
337
- const_iterator find(const key_type& k) const;
338
  template<class K>
339
- iterator find(const K& k);
340
  template<class K>
341
- const_iterator find(const K& k) const;
342
- size_type count(const key_type& k) const;
343
  template<class K>
344
- size_type count(const K& k) const;
345
- bool contains(const key_type& k) const;
346
  template<class K>
347
- bool contains(const K& k) const;
348
- pair<iterator, iterator> equal_range(const key_type& k);
349
- pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
350
  template<class K>
351
- pair<iterator, iterator> equal_range(const K& k);
352
  template<class K>
353
- pair<const_iterator, const_iterator> equal_range(const K& k) const;
354
 
355
  // [unord.map.elem], element access
356
- mapped_type& operator[](const key_type& k);
357
- mapped_type& operator[](key_type&& k);
358
- mapped_type& at(const key_type& k);
359
- const mapped_type& at(const key_type& k) const;
 
 
 
360
 
361
  // bucket interface
362
- size_type bucket_count() const noexcept;
363
- size_type max_bucket_count() const noexcept;
364
- size_type bucket_size(size_type n) const;
365
- size_type bucket(const key_type& k) const;
366
- local_iterator begin(size_type n);
367
- const_local_iterator begin(size_type n) const;
368
- local_iterator end(size_type n);
369
- const_local_iterator end(size_type n) const;
370
- const_local_iterator cbegin(size_type n) const;
371
- const_local_iterator cend(size_type n) const;
 
372
 
373
  // hash policy
374
- float load_factor() const noexcept;
375
- float max_load_factor() const noexcept;
376
- void max_load_factor(float z);
377
- void rehash(size_type n);
378
- void reserve(size_type n);
379
  };
380
 
381
  template<class InputIterator,
382
  class Hash = hash<iter-key-type<InputIterator>>,
383
  class Pred = equal_to<iter-key-type<InputIterator>>,
@@ -454,13 +404,12 @@ refers to the `size_type` member type of the type deduced by the
454
  deduction guide.
455
 
456
  #### Constructors <a id="unord.map.cnstr">[[unord.map.cnstr]]</a>
457
 
458
  ``` cpp
459
- unordered_map() : unordered_map(size_type(see below)) { }
460
- explicit unordered_map(size_type n,
461
- const hasher& hf = hasher(),
462
  const key_equal& eql = key_equal(),
463
  const allocator_type& a = allocator_type());
464
  ```
465
 
466
  *Effects:* Constructs an empty `unordered_map` using the specified hash
@@ -470,24 +419,21 @@ buckets. For the default constructor, the number of buckets is
470
 
471
  *Complexity:* Constant.
472
 
473
  ``` cpp
474
  template<class InputIterator>
475
- unordered_map(InputIterator f, InputIterator l,
476
- size_type n = see below,
477
- const hasher& hf = hasher(),
478
  const key_equal& eql = key_equal(),
479
  const allocator_type& a = allocator_type());
480
  template<container-compatible-range<value_type> R>
481
- unordered_map(from_range_t, R&& rg,
482
- size_type n = see below,
483
- const hasher& hf = hasher(),
484
  const key_equal& eql = key_equal(),
485
  const allocator_type& a = allocator_type());
486
- unordered_map(initializer_list<value_type> il,
487
- size_type n = see below,
488
- const hasher& hf = hasher(),
489
  const key_equal& eql = key_equal(),
490
  const allocator_type& a = allocator_type());
491
  ```
492
 
493
  *Effects:* Constructs an empty `unordered_map` using the specified hash
@@ -499,59 +445,85 @@ buckets. If `n` is not provided, the number of buckets is
499
  *Complexity:* Average case linear, worst case quadratic.
500
 
501
  #### Element access <a id="unord.map.elem">[[unord.map.elem]]</a>
502
 
503
  ``` cpp
504
- mapped_type& operator[](const key_type& k);
505
  ```
506
 
507
  *Effects:* Equivalent to: `return try_emplace(k).first->second;`
508
 
509
  ``` cpp
510
- mapped_type& operator[](key_type&& k);
511
  ```
512
 
513
  *Effects:* Equivalent to:
514
  `return try_emplace(std::move(k)).first->second;`
515
 
516
  ``` cpp
517
- mapped_type& at(const key_type& k);
518
- const mapped_type& at(const key_type& k) const;
 
 
 
 
 
 
 
 
 
 
519
  ```
520
 
521
  *Returns:* A reference to `x.second`, where `x` is the (unique) element
522
  whose key is equivalent to `k`.
523
 
524
  *Throws:* An exception object of type `out_of_range` if no such element
525
  is present.
526
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
527
  #### Modifiers <a id="unord.map.modifiers">[[unord.map.modifiers]]</a>
528
 
529
  ``` cpp
530
  template<class P>
531
- pair<iterator, bool> insert(P&& obj);
532
  ```
533
 
534
  *Constraints:* `is_constructible_v<value_type, P&&>` is `true`.
535
 
536
  *Effects:* Equivalent to: `return emplace(std::forward<P>(obj));`
537
 
538
  ``` cpp
539
  template<class P>
540
- iterator insert(const_iterator hint, P&& obj);
541
  ```
542
 
543
  *Constraints:* `is_constructible_v<value_type, P&&>` is `true`.
544
 
545
  *Effects:* Equivalent to:
546
  `return emplace_hint(hint, std::forward<P>(obj));`
547
 
548
  ``` cpp
549
  template<class... Args>
550
- pair<iterator, bool> try_emplace(const key_type& k, Args&&... args);
551
  template<class... Args>
552
- iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args);
553
  ```
554
 
555
  *Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into
556
  `unordered_map` from `piecewise_construct`, `forward_as_tuple(k)`,
557
  `forward_as_tuple(std::forward<Args>(args)...)`.
@@ -567,13 +539,13 @@ iterator points to the map element whose key is equivalent to `k`.
567
 
568
  *Complexity:* The same as `emplace` and `emplace_hint`, respectively.
569
 
570
  ``` cpp
571
  template<class... Args>
572
- pair<iterator, bool> try_emplace(key_type&& k, Args&&... args);
573
  template<class... Args>
574
- iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args);
575
  ```
576
 
577
  *Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into
578
  `unordered_map` from `piecewise_construct`,
579
  `forward_as_tuple(std::move(k))`,
@@ -589,15 +561,44 @@ type `value_type` constructed with `piecewise_construct`,
589
  pair is `true` if and only if the insertion took place. The returned
590
  iterator points to the map element whose key is equivalent to `k`.
591
 
592
  *Complexity:* The same as `emplace` and `emplace_hint`, respectively.
593
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
594
  ``` cpp
595
  template<class M>
596
- pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj);
597
  template<class M>
598
- iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj);
599
  ```
600
 
601
  *Mandates:* `is_assignable_v<mapped_type&, M&&>` is `true`.
602
 
603
  *Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into
@@ -614,13 +615,13 @@ iterator points to the map element whose key is equivalent to `k`.
614
 
615
  *Complexity:* The same as `emplace` and `emplace_hint`, respectively.
616
 
617
  ``` cpp
618
  template<class M>
619
- pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj);
620
  template<class M>
621
- iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj);
622
  ```
623
 
624
  *Mandates:* `is_assignable_v<mapped_type&, M&&>` is `true`.
625
 
626
  *Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into
@@ -635,15 +636,43 @@ Otherwise inserts an object of type `value_type` constructed with
635
  pair is `true` if and only if the insertion took place. The returned
636
  iterator points to the map element whose key is equivalent to `k`.
637
 
638
  *Complexity:* The same as `emplace` and `emplace_hint`, respectively.
639
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
640
  #### Erasure <a id="unord.map.erasure">[[unord.map.erasure]]</a>
641
 
642
  ``` cpp
643
  template<class K, class T, class H, class P, class A, class Predicate>
644
- typename unordered_map<K, T, H, P, A>::size_type
645
  erase_if(unordered_map<K, T, H, P, A>& c, Predicate pred);
646
  ```
647
 
648
  *Effects:* Equivalent to:
649
 
@@ -680,10 +709,13 @@ the `mapped_type` is `T`, and the `value_type` is `pair<const Key, T>`.
680
 
681
  Subclause  [[unord.multimap]] only describes operations on
682
  `unordered_multimap` that are not described in one of the requirement
683
  tables, or for which there is additional semantic information.
684
 
 
 
 
685
  ``` cpp
686
  namespace std {
687
  template<class Key,
688
  class T,
689
  class Hash = hash<Key>,
@@ -696,12 +728,12 @@ namespace std {
696
  using mapped_type = T;
697
  using value_type = pair<const Key, T>;
698
  using hasher = Hash;
699
  using key_equal = Pred;
700
  using allocator_type = Allocator;
701
- using pointer = typename allocator_traits<Allocator>::pointer;
702
- using const_pointer = typename allocator_traits<Allocator>::const_pointer;
703
  using reference = value_type&;
704
  using const_reference = const value_type&;
705
  using size_type = implementation-defined // type of unordered_multimap::size_type; // see [container.requirements]
706
  using difference_type = implementation-defined // type of unordered_multimap::difference_type; // see [container.requirements]
707
 
@@ -710,165 +742,163 @@ namespace std {
710
  using local_iterator = implementation-defined // type of unordered_multimap::local_iterator; // see [container.requirements]
711
  using const_local_iterator = implementation-defined // type of unordered_multimap::const_local_iterator; // see [container.requirements]
712
  using node_type = unspecified;
713
 
714
  // [unord.multimap.cnstr], construct/copy/destroy
715
- unordered_multimap();
716
- explicit unordered_multimap(size_type n,
717
- const hasher& hf = hasher(),
718
  const key_equal& eql = key_equal(),
719
  const allocator_type& a = allocator_type());
720
  template<class InputIterator>
721
- unordered_multimap(InputIterator f, InputIterator l,
722
- size_type n = see below,
723
- const hasher& hf = hasher(),
724
  const key_equal& eql = key_equal(),
725
  const allocator_type& a = allocator_type());
726
  template<container-compatible-range<value_type> R>
727
- unordered_multimap(from_range_t, R&& rg,
728
- size_type n = see below,
729
- const hasher& hf = hasher(),
730
  const key_equal& eql = key_equal(),
731
  const allocator_type& a = allocator_type());
732
- unordered_multimap(const unordered_multimap&);
733
- unordered_multimap(unordered_multimap&&);
734
- explicit unordered_multimap(const Allocator&);
735
- unordered_multimap(const unordered_multimap&, const type_identity_t<Allocator>&);
736
- unordered_multimap(unordered_multimap&&, const type_identity_t<Allocator>&);
737
- unordered_multimap(initializer_list<value_type> il,
738
- size_type n = see below,
739
- const hasher& hf = hasher(),
740
  const key_equal& eql = key_equal(),
741
  const allocator_type& a = allocator_type());
742
- unordered_multimap(size_type n, const allocator_type& a)
743
  : unordered_multimap(n, hasher(), key_equal(), a) { }
744
- unordered_multimap(size_type n, const hasher& hf, const allocator_type& a)
745
  : unordered_multimap(n, hf, key_equal(), a) { }
746
  template<class InputIterator>
747
- unordered_multimap(InputIterator f, InputIterator l, size_type n, const allocator_type& a)
 
748
  : unordered_multimap(f, l, n, hasher(), key_equal(), a) { }
749
  template<class InputIterator>
750
- unordered_multimap(InputIterator f, InputIterator l, size_type n, const hasher& hf,
751
- const allocator_type& a)
752
  : unordered_multimap(f, l, n, hf, key_equal(), a) { }
753
  template<container-compatible-range<value_type> R>
754
- unordered_multimap(from_range_t, R&& rg, size_type n, const allocator_type& a)
755
  : unordered_multimap(from_range, std::forward<R>(rg),
756
  n, hasher(), key_equal(), a) { }
757
  template<container-compatible-range<value_type> R>
758
- unordered_multimap(from_range_t, R&& rg, size_type n, const hasher& hf,
759
  const allocator_type& a)
760
  : unordered_multimap(from_range, std::forward<R>(rg), n, hf, key_equal(), a) { }
761
- unordered_multimap(initializer_list<value_type> il, size_type n, const allocator_type& a)
 
762
  : unordered_multimap(il, n, hasher(), key_equal(), a) { }
763
- unordered_multimap(initializer_list<value_type> il, size_type n, const hasher& hf,
764
  const allocator_type& a)
765
  : unordered_multimap(il, n, hf, key_equal(), a) { }
766
- ~unordered_multimap();
767
- unordered_multimap& operator=(const unordered_multimap&);
768
- unordered_multimap& operator=(unordered_multimap&&)
769
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
770
- is_nothrow_move_assignable_v<Hash> &&
771
- is_nothrow_move_assignable_v<Pred>);
772
- unordered_multimap& operator=(initializer_list<value_type>);
773
- allocator_type get_allocator() const noexcept;
774
 
775
  // iterators
776
- iterator begin() noexcept;
777
- const_iterator begin() const noexcept;
778
- iterator end() noexcept;
779
- const_iterator end() const noexcept;
780
- const_iterator cbegin() const noexcept;
781
- const_iterator cend() const noexcept;
782
 
783
  // capacity
784
- [[nodiscard]] bool empty() const noexcept;
785
- size_type size() const noexcept;
786
- size_type max_size() const noexcept;
787
 
788
  // [unord.multimap.modifiers], modifiers
789
- template<class... Args> iterator emplace(Args&&... args);
790
- template<class... Args> iterator emplace_hint(const_iterator position, Args&&... args);
791
- iterator insert(const value_type& obj);
792
- iterator insert(value_type&& obj);
793
- template<class P> iterator insert(P&& obj);
794
- iterator insert(const_iterator hint, const value_type& obj);
795
- iterator insert(const_iterator hint, value_type&& obj);
796
- template<class P> iterator insert(const_iterator hint, P&& obj);
797
- template<class InputIterator> void insert(InputIterator first, InputIterator last);
 
798
  template<container-compatible-range<value_type> R>
799
- void insert_range(R&& rg);
800
- void insert(initializer_list<value_type>);
801
 
802
- node_type extract(const_iterator position);
803
- node_type extract(const key_type& x);
804
- template<class K> node_type extract(K&& x);
805
- iterator insert(node_type&& nh);
806
- iterator insert(const_iterator hint, node_type&& nh);
807
 
808
- iterator erase(iterator position);
809
- iterator erase(const_iterator position);
810
- size_type erase(const key_type& k);
811
- template<class K> size_type erase(K&& x);
812
- iterator erase(const_iterator first, const_iterator last);
813
- void swap(unordered_multimap&)
814
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
815
- is_nothrow_swappable_v<Hash> &&
816
- is_nothrow_swappable_v<Pred>);
817
- void clear() noexcept;
818
 
819
  template<class H2, class P2>
820
- void merge(unordered_multimap<Key, T, H2, P2, Allocator>& source);
821
  template<class H2, class P2>
822
- void merge(unordered_multimap<Key, T, H2, P2, Allocator>&& source);
823
  template<class H2, class P2>
824
- void merge(unordered_map<Key, T, H2, P2, Allocator>& source);
825
  template<class H2, class P2>
826
- void merge(unordered_map<Key, T, H2, P2, Allocator>&& source);
827
 
828
  // observers
829
- hasher hash_function() const;
830
- key_equal key_eq() const;
831
 
832
  // map operations
833
- iterator find(const key_type& k);
834
- const_iterator find(const key_type& k) const;
835
  template<class K>
836
- iterator find(const K& k);
837
  template<class K>
838
- const_iterator find(const K& k) const;
839
- size_type count(const key_type& k) const;
840
  template<class K>
841
- size_type count(const K& k) const;
842
- bool contains(const key_type& k) const;
843
  template<class K>
844
- bool contains(const K& k) const;
845
- pair<iterator, iterator> equal_range(const key_type& k);
846
- pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
847
  template<class K>
848
- pair<iterator, iterator> equal_range(const K& k);
849
  template<class K>
850
- pair<const_iterator, const_iterator> equal_range(const K& k) const;
851
 
852
  // bucket interface
853
- size_type bucket_count() const noexcept;
854
- size_type max_bucket_count() const noexcept;
855
- size_type bucket_size(size_type n) const;
856
- size_type bucket(const key_type& k) const;
857
- local_iterator begin(size_type n);
858
- const_local_iterator begin(size_type n) const;
859
- local_iterator end(size_type n);
860
- const_local_iterator end(size_type n) const;
861
- const_local_iterator cbegin(size_type n) const;
862
- const_local_iterator cend(size_type n) const;
 
863
 
864
  // hash policy
865
- float load_factor() const noexcept;
866
- float max_load_factor() const noexcept;
867
- void max_load_factor(float z);
868
- void rehash(size_type n);
869
- void reserve(size_type n);
870
  };
871
 
872
  template<class InputIterator,
873
  class Hash = hash<iter-key-type<InputIterator>>,
874
  class Pred = equal_to<iter-key-type<InputIterator>>,
@@ -948,13 +978,12 @@ refers to the `size_type` member type of the type deduced by the
948
  deduction guide.
949
 
950
  #### Constructors <a id="unord.multimap.cnstr">[[unord.multimap.cnstr]]</a>
951
 
952
  ``` cpp
953
- unordered_multimap() : unordered_multimap(size_type(see below)) { }
954
- explicit unordered_multimap(size_type n,
955
- const hasher& hf = hasher(),
956
  const key_equal& eql = key_equal(),
957
  const allocator_type& a = allocator_type());
958
  ```
959
 
960
  *Effects:* Constructs an empty `unordered_multimap` using the specified
@@ -964,24 +993,21 @@ hash function, key equality predicate, and allocator, and using at least
964
 
965
  *Complexity:* Constant.
966
 
967
  ``` cpp
968
  template<class InputIterator>
969
- unordered_multimap(InputIterator f, InputIterator l,
970
- size_type n = see below,
971
- const hasher& hf = hasher(),
972
  const key_equal& eql = key_equal(),
973
  const allocator_type& a = allocator_type());
974
  template<container-compatible-range<value_type> R>
975
- unordered_multimap(from_range_t, R&& rg,
976
- size_type n = see below,
977
- const hasher& hf = hasher(),
978
  const key_equal& eql = key_equal(),
979
  const allocator_type& a = allocator_type());
980
- unordered_multimap(initializer_list<value_type> il,
981
- size_type n = see below,
982
- const hasher& hf = hasher(),
983
  const key_equal& eql = key_equal(),
984
  const allocator_type& a = allocator_type());
985
  ```
986
 
987
  *Effects:* Constructs an empty `unordered_multimap` using the specified
@@ -994,20 +1020,20 @@ hash function, key equality predicate, and allocator, and using at least
994
 
995
  #### Modifiers <a id="unord.multimap.modifiers">[[unord.multimap.modifiers]]</a>
996
 
997
  ``` cpp
998
  template<class P>
999
- iterator insert(P&& obj);
1000
  ```
1001
 
1002
  *Constraints:* `is_constructible_v<value_type, P&&>` is `true`.
1003
 
1004
  *Effects:* Equivalent to: `return emplace(std::forward<P>(obj));`
1005
 
1006
  ``` cpp
1007
  template<class P>
1008
- iterator insert(const_iterator hint, P&& obj);
1009
  ```
1010
 
1011
  *Constraints:* `is_constructible_v<value_type, P&&>` is `true`.
1012
 
1013
  *Effects:* Equivalent to:
@@ -1015,11 +1041,11 @@ template<class P>
1015
 
1016
  #### Erasure <a id="unord.multimap.erasure">[[unord.multimap.erasure]]</a>
1017
 
1018
  ``` cpp
1019
  template<class K, class T, class H, class P, class A, class Predicate>
1020
- typename unordered_multimap<K, T, H, P, A>::size_type
1021
  erase_if(unordered_multimap<K, T, H, P, A>& c, Predicate pred);
1022
  ```
1023
 
1024
  *Effects:* Equivalent to:
1025
 
@@ -1033,10 +1059,75 @@ for (auto i = c.begin(), last = c.end(); i != last; ) {
1033
  }
1034
  }
1035
  return original_size - c.size();
1036
  ```
1037
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1038
  ### Class template `unordered_set` <a id="unord.set">[[unord.set]]</a>
1039
 
1040
  #### Overview <a id="unord.set.overview">[[unord.set.overview]]</a>
1041
 
1042
  An `unordered_set` is an unordered associative container that supports
@@ -1044,11 +1135,11 @@ unique keys (an `unordered_set` contains at most one of each key value)
1044
  and in which the elements’ keys are the elements themselves. The
1045
  `unordered_set` class supports forward iterators.
1046
 
1047
  An `unordered_set` meets all of the requirements of a container
1048
  [[container.reqmts]], of an allocator-aware container
1049
- [[container.alloc.reqmts]], of an unordered associative container
1050
  [[unord.req]]. It provides the operations described in the preceding
1051
  requirements table for unique keys; that is, an `unordered_set` supports
1052
  the `a_uniq` operations in that table, not the `a_eq` operations. For an
1053
  `unordered_set<Key>` the `key_type` and the `value_type` are both `Key`.
1054
  The `iterator` and `const_iterator` types are both constant iterator
@@ -1056,10 +1147,13 @@ types. It is unspecified whether they are the same type.
1056
 
1057
  Subclause  [[unord.set]] only describes operations on `unordered_set`
1058
  that are not described in one of the requirement tables, or for which
1059
  there is additional semantic information.
1060
 
 
 
 
1061
  ``` cpp
1062
  namespace std {
1063
  template<class Key,
1064
  class Hash = hash<Key>,
1065
  class Pred = equal_to<Key>,
@@ -1070,12 +1164,12 @@ namespace std {
1070
  using key_type = Key;
1071
  using value_type = Key;
1072
  using hasher = Hash;
1073
  using key_equal = Pred;
1074
  using allocator_type = Allocator;
1075
- using pointer = typename allocator_traits<Allocator>::pointer;
1076
- using const_pointer = typename allocator_traits<Allocator>::const_pointer;
1077
  using reference = value_type&;
1078
  using const_reference = const value_type&;
1079
  using size_type = implementation-defined // type of unordered_set::size_type; // see [container.requirements]
1080
  using difference_type = implementation-defined // type of unordered_set::difference_type; // see [container.requirements]
1081
 
@@ -1085,162 +1179,163 @@ namespace std {
1085
  using const_local_iterator = implementation-defined // type of unordered_set::const_local_iterator; // see [container.requirements]
1086
  using node_type = unspecified;
1087
  using insert_return_type = insert-return-type<iterator, node_type>;
1088
 
1089
  // [unord.set.cnstr], construct/copy/destroy
1090
- unordered_set();
1091
- explicit unordered_set(size_type n,
1092
- const hasher& hf = hasher(),
1093
  const key_equal& eql = key_equal(),
1094
  const allocator_type& a = allocator_type());
1095
  template<class InputIterator>
1096
- unordered_set(InputIterator f, InputIterator l,
1097
- size_type n = see below,
1098
- const hasher& hf = hasher(),
1099
  const key_equal& eql = key_equal(),
1100
  const allocator_type& a = allocator_type());
1101
  template<container-compatible-range<value_type> R>
1102
- unordered_set(from_range_t, R&& rg,
1103
- size_type n = see below,
1104
- const hasher& hf = hasher(),
1105
  const key_equal& eql = key_equal(),
1106
  const allocator_type& a = allocator_type());
1107
- unordered_set(const unordered_set&);
1108
- unordered_set(unordered_set&&);
1109
- explicit unordered_set(const Allocator&);
1110
- unordered_set(const unordered_set&, const type_identity_t<Allocator>&);
1111
- unordered_set(unordered_set&&, const type_identity_t<Allocator>&);
1112
- unordered_set(initializer_list<value_type> il,
1113
- size_type n = see below,
1114
- const hasher& hf = hasher(),
1115
  const key_equal& eql = key_equal(),
1116
  const allocator_type& a = allocator_type());
1117
- unordered_set(size_type n, const allocator_type& a)
1118
  : unordered_set(n, hasher(), key_equal(), a) { }
1119
- unordered_set(size_type n, const hasher& hf, const allocator_type& a)
1120
  : unordered_set(n, hf, key_equal(), a) { }
1121
  template<class InputIterator>
1122
- unordered_set(InputIterator f, InputIterator l, size_type n, const allocator_type& a)
 
1123
  : unordered_set(f, l, n, hasher(), key_equal(), a) { }
1124
  template<class InputIterator>
1125
- unordered_set(InputIterator f, InputIterator l, size_type n, const hasher& hf,
1126
  const allocator_type& a)
1127
  : unordered_set(f, l, n, hf, key_equal(), a) { }
1128
- unordered_set(initializer_list<value_type> il, size_type n, const allocator_type& a)
 
1129
  : unordered_set(il, n, hasher(), key_equal(), a) { }
1130
  template<container-compatible-range<value_type> R>
1131
- unordered_set(from_range_t, R&& rg, size_type n, const allocator_type& a)
1132
  : unordered_set(from_range, std::forward<R>(rg), n, hasher(), key_equal(), a) { }
1133
  template<container-compatible-range<value_type> R>
1134
- unordered_set(from_range_t, R&& rg, size_type n, const hasher& hf, const allocator_type& a)
 
1135
  : unordered_set(from_range, std::forward<R>(rg), n, hf, key_equal(), a) { }
1136
- unordered_set(initializer_list<value_type> il, size_type n, const hasher& hf,
1137
  const allocator_type& a)
1138
  : unordered_set(il, n, hf, key_equal(), a) { }
1139
- ~unordered_set();
1140
- unordered_set& operator=(const unordered_set&);
1141
- unordered_set& operator=(unordered_set&&)
1142
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
1143
- is_nothrow_move_assignable_v<Hash> &&
1144
- is_nothrow_move_assignable_v<Pred>);
1145
- unordered_set& operator=(initializer_list<value_type>);
1146
- allocator_type get_allocator() const noexcept;
1147
 
1148
  // iterators
1149
- iterator begin() noexcept;
1150
- const_iterator begin() const noexcept;
1151
- iterator end() noexcept;
1152
- const_iterator end() const noexcept;
1153
- const_iterator cbegin() const noexcept;
1154
- const_iterator cend() const noexcept;
1155
 
1156
  // capacity
1157
- [[nodiscard]] bool empty() const noexcept;
1158
- size_type size() const noexcept;
1159
- size_type max_size() const noexcept;
1160
 
1161
- // modifiers
1162
- template<class... Args> pair<iterator, bool> emplace(Args&&... args);
1163
- template<class... Args> iterator emplace_hint(const_iterator position, Args&&... args);
1164
- pair<iterator, bool> insert(const value_type& obj);
1165
- pair<iterator, bool> insert(value_type&& obj);
1166
- iterator insert(const_iterator hint, const value_type& obj);
1167
- iterator insert(const_iterator hint, value_type&& obj);
1168
- template<class InputIterator> void insert(InputIterator first, InputIterator last);
 
 
 
1169
  template<container-compatible-range<value_type> R>
1170
- void insert_range(R&& rg);
1171
- void insert(initializer_list<value_type>);
1172
 
1173
- node_type extract(const_iterator position);
1174
- node_type extract(const key_type& x);
1175
- template<class K> node_type extract(K&& x);
1176
- insert_return_type insert(node_type&& nh);
1177
- iterator insert(const_iterator hint, node_type&& nh);
1178
 
1179
- iterator erase(iterator position)
1180
  requires (!same_as<iterator, const_iterator>);
1181
- iterator erase(const_iterator position);
1182
- size_type erase(const key_type& k);
1183
- template<class K> size_type erase(K&& x);
1184
- iterator erase(const_iterator first, const_iterator last);
1185
- void swap(unordered_set&)
1186
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
1187
- is_nothrow_swappable_v<Hash> &&
1188
- is_nothrow_swappable_v<Pred>);
1189
- void clear() noexcept;
1190
 
1191
  template<class H2, class P2>
1192
- void merge(unordered_set<Key, H2, P2, Allocator>& source);
1193
  template<class H2, class P2>
1194
- void merge(unordered_set<Key, H2, P2, Allocator>&& source);
1195
  template<class H2, class P2>
1196
- void merge(unordered_multiset<Key, H2, P2, Allocator>& source);
1197
  template<class H2, class P2>
1198
- void merge(unordered_multiset<Key, H2, P2, Allocator>&& source);
1199
 
1200
  // observers
1201
- hasher hash_function() const;
1202
- key_equal key_eq() const;
1203
 
1204
  // set operations
1205
- iterator find(const key_type& k);
1206
- const_iterator find(const key_type& k) const;
1207
  template<class K>
1208
- iterator find(const K& k);
1209
  template<class K>
1210
- const_iterator find(const K& k) const;
1211
- size_type count(const key_type& k) const;
1212
  template<class K>
1213
- size_type count(const K& k) const;
1214
- bool contains(const key_type& k) const;
1215
  template<class K>
1216
- bool contains(const K& k) const;
1217
- pair<iterator, iterator> equal_range(const key_type& k);
1218
- pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
1219
  template<class K>
1220
- pair<iterator, iterator> equal_range(const K& k);
1221
  template<class K>
1222
- pair<const_iterator, const_iterator> equal_range(const K& k) const;
1223
 
1224
  // bucket interface
1225
- size_type bucket_count() const noexcept;
1226
- size_type max_bucket_count() const noexcept;
1227
- size_type bucket_size(size_type n) const;
1228
- size_type bucket(const key_type& k) const;
1229
- local_iterator begin(size_type n);
1230
- const_local_iterator begin(size_type n) const;
1231
- local_iterator end(size_type n);
1232
- const_local_iterator end(size_type n) const;
1233
- const_local_iterator cbegin(size_type n) const;
1234
- const_local_iterator cend(size_type n) const;
 
1235
 
1236
  // hash policy
1237
- float load_factor() const noexcept;
1238
- float max_load_factor() const noexcept;
1239
- void max_load_factor(float z);
1240
- void rehash(size_type n);
1241
- void reserve(size_type n);
1242
  };
1243
 
1244
  template<class InputIterator,
1245
  class Hash = hash<iter-value-type<InputIterator>>,
1246
  class Pred = equal_to<iter-value-type<InputIterator>>,
@@ -1308,13 +1403,12 @@ refers to the `size_type` member type of the type deduced by the
1308
  deduction guide.
1309
 
1310
  #### Constructors <a id="unord.set.cnstr">[[unord.set.cnstr]]</a>
1311
 
1312
  ``` cpp
1313
- unordered_set() : unordered_set(size_type(see below)) { }
1314
- explicit unordered_set(size_type n,
1315
- const hasher& hf = hasher(),
1316
  const key_equal& eql = key_equal(),
1317
  const allocator_type& a = allocator_type());
1318
  ```
1319
 
1320
  *Effects:* Constructs an empty `unordered_set` using the specified hash
@@ -1324,24 +1418,21 @@ buckets. For the default constructor, the number of buckets is
1324
 
1325
  *Complexity:* Constant.
1326
 
1327
  ``` cpp
1328
  template<class InputIterator>
1329
- unordered_set(InputIterator f, InputIterator l,
1330
- size_type n = see below,
1331
- const hasher& hf = hasher(),
1332
  const key_equal& eql = key_equal(),
1333
  const allocator_type& a = allocator_type());
1334
  template<container-compatible-range<value_type> R>
1335
- unordered_multiset(from_range_t, R&& rg,
1336
- size_type n = see below,
1337
- const hasher& hf = hasher(),
1338
  const key_equal& eql = key_equal(),
1339
  const allocator_type& a = allocator_type());
1340
- unordered_set(initializer_list<value_type> il,
1341
- size_type n = see below,
1342
- const hasher& hf = hasher(),
1343
  const key_equal& eql = key_equal(),
1344
  const allocator_type& a = allocator_type());
1345
  ```
1346
 
1347
  *Effects:* Constructs an empty `unordered_set` using the specified hash
@@ -1354,11 +1445,11 @@ buckets. If `n` is not provided, the number of buckets is
1354
 
1355
  #### Erasure <a id="unord.set.erasure">[[unord.set.erasure]]</a>
1356
 
1357
  ``` cpp
1358
  template<class K, class H, class P, class A, class Predicate>
1359
- typename unordered_set<K, H, P, A>::size_type
1360
  erase_if(unordered_set<K, H, P, A>& c, Predicate pred);
1361
  ```
1362
 
1363
  *Effects:* Equivalent to:
1364
 
@@ -1372,10 +1463,37 @@ for (auto i = c.begin(), last = c.end(); i != last; ) {
1372
  }
1373
  }
1374
  return original_size - c.size();
1375
  ```
1376
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1377
  ### Class template `unordered_multiset` <a id="unord.multiset">[[unord.multiset]]</a>
1378
 
1379
  #### Overview <a id="unord.multiset.overview">[[unord.multiset.overview]]</a>
1380
 
1381
  An `unordered_multiset` is an unordered associative container that
@@ -1397,10 +1515,13 @@ same type.
1397
 
1398
  Subclause  [[unord.multiset]] only describes operations on
1399
  `unordered_multiset` that are not described in one of the requirement
1400
  tables, or for which there is additional semantic information.
1401
 
 
 
 
1402
  ``` cpp
1403
  namespace std {
1404
  template<class Key,
1405
  class Hash = hash<Key>,
1406
  class Pred = equal_to<Key>,
@@ -1411,12 +1532,12 @@ namespace std {
1411
  using key_type = Key;
1412
  using value_type = Key;
1413
  using hasher = Hash;
1414
  using key_equal = Pred;
1415
  using allocator_type = Allocator;
1416
- using pointer = typename allocator_traits<Allocator>::pointer;
1417
- using const_pointer = typename allocator_traits<Allocator>::const_pointer;
1418
  using reference = value_type&;
1419
  using const_reference = const value_type&;
1420
  using size_type = implementation-defined // type of unordered_multiset::size_type; // see [container.requirements]
1421
  using difference_type = implementation-defined // type of unordered_multiset::difference_type; // see [container.requirements]
1422
 
@@ -1425,171 +1546,169 @@ namespace std {
1425
  using local_iterator = implementation-defined // type of unordered_multiset::local_iterator; // see [container.requirements]
1426
  using const_local_iterator = implementation-defined // type of unordered_multiset::const_local_iterator; // see [container.requirements]
1427
  using node_type = unspecified;
1428
 
1429
  // [unord.multiset.cnstr], construct/copy/destroy
1430
- unordered_multiset();
1431
- explicit unordered_multiset(size_type n,
1432
- const hasher& hf = hasher(),
1433
  const key_equal& eql = key_equal(),
1434
  const allocator_type& a = allocator_type());
1435
  template<class InputIterator>
1436
- unordered_multiset(InputIterator f, InputIterator l,
1437
- size_type n = see below,
1438
- const hasher& hf = hasher(),
1439
  const key_equal& eql = key_equal(),
1440
  const allocator_type& a = allocator_type());
1441
  template<container-compatible-range<value_type> R>
1442
- unordered_multiset(from_range_t, R&& rg,
1443
- size_type n = see below,
1444
- const hasher& hf = hasher(),
1445
  const key_equal& eql = key_equal(),
1446
  const allocator_type& a = allocator_type());
1447
- unordered_multiset(const unordered_multiset&);
1448
- unordered_multiset(unordered_multiset&&);
1449
- explicit unordered_multiset(const Allocator&);
1450
- unordered_multiset(const unordered_multiset&, const type_identity_t<Allocator>&);
1451
- unordered_multiset(unordered_multiset&&, const type_identity_t<Allocator>&);
1452
- unordered_multiset(initializer_list<value_type> il,
1453
- size_type n = see below,
1454
- const hasher& hf = hasher(),
1455
  const key_equal& eql = key_equal(),
1456
  const allocator_type& a = allocator_type());
1457
- unordered_multiset(size_type n, const allocator_type& a)
1458
  : unordered_multiset(n, hasher(), key_equal(), a) { }
1459
- unordered_multiset(size_type n, const hasher& hf, const allocator_type& a)
1460
  : unordered_multiset(n, hf, key_equal(), a) { }
1461
  template<class InputIterator>
1462
- unordered_multiset(InputIterator f, InputIterator l, size_type n, const allocator_type& a)
 
1463
  : unordered_multiset(f, l, n, hasher(), key_equal(), a) { }
1464
  template<class InputIterator>
1465
- unordered_multiset(InputIterator f, InputIterator l, size_type n, const hasher& hf,
1466
- const allocator_type& a)
1467
  : unordered_multiset(f, l, n, hf, key_equal(), a) { }
1468
  template<container-compatible-range<value_type> R>
1469
- unordered_multiset(from_range_t, R&& rg, size_type n, const allocator_type& a)
1470
  : unordered_multiset(from_range, std::forward<R>(rg),
1471
  n, hasher(), key_equal(), a) { }
1472
  template<container-compatible-range<value_type> R>
1473
- unordered_multiset(from_range_t, R&& rg, size_type n, const hasher& hf,
1474
  const allocator_type& a)
1475
  : unordered_multiset(from_range, std::forward<R>(rg), n, hf, key_equal(), a) { }
1476
- unordered_multiset(initializer_list<value_type> il, size_type n, const allocator_type& a)
 
1477
  : unordered_multiset(il, n, hasher(), key_equal(), a) { }
1478
- unordered_multiset(initializer_list<value_type> il, size_type n, const hasher& hf,
1479
  const allocator_type& a)
1480
  : unordered_multiset(il, n, hf, key_equal(), a) { }
1481
- ~unordered_multiset();
1482
- unordered_multiset& operator=(const unordered_multiset&);
1483
- unordered_multiset& operator=(unordered_multiset&&)
1484
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
1485
- is_nothrow_move_assignable_v<Hash> &&
1486
- is_nothrow_move_assignable_v<Pred>);
1487
- unordered_multiset& operator=(initializer_list<value_type>);
1488
- allocator_type get_allocator() const noexcept;
1489
 
1490
  // iterators
1491
- iterator begin() noexcept;
1492
- const_iterator begin() const noexcept;
1493
- iterator end() noexcept;
1494
- const_iterator end() const noexcept;
1495
- const_iterator cbegin() const noexcept;
1496
- const_iterator cend() const noexcept;
1497
 
1498
  // capacity
1499
- [[nodiscard]] bool empty() const noexcept;
1500
- size_type size() const noexcept;
1501
- size_type max_size() const noexcept;
1502
 
1503
  // modifiers
1504
- template<class... Args> iterator emplace(Args&&... args);
1505
- template<class... Args> iterator emplace_hint(const_iterator position, Args&&... args);
1506
- iterator insert(const value_type& obj);
1507
- iterator insert(value_type&& obj);
1508
- iterator insert(const_iterator hint, const value_type& obj);
1509
- iterator insert(const_iterator hint, value_type&& obj);
1510
- template<class InputIterator> void insert(InputIterator first, InputIterator last);
 
1511
  template<container-compatible-range<value_type> R>
1512
- void insert_range(R&& rg);
1513
- void insert(initializer_list<value_type>);
1514
 
1515
- node_type extract(const_iterator position);
1516
- node_type extract(const key_type& x);
1517
- template<class K> node_type extract(K&& x);
1518
- iterator insert(node_type&& nh);
1519
- iterator insert(const_iterator hint, node_type&& nh);
1520
 
1521
- iterator erase(iterator position)
1522
  requires (!same_as<iterator, const_iterator>);
1523
- iterator erase(const_iterator position);
1524
- size_type erase(const key_type& k);
1525
- template<class K> size_type erase(K&& x);
1526
- iterator erase(const_iterator first, const_iterator last);
1527
- void swap(unordered_multiset&)
1528
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
1529
- is_nothrow_swappable_v<Hash> &&
1530
- is_nothrow_swappable_v<Pred>);
1531
- void clear() noexcept;
1532
 
1533
  template<class H2, class P2>
1534
- void merge(unordered_multiset<Key, H2, P2, Allocator>& source);
1535
  template<class H2, class P2>
1536
- void merge(unordered_multiset<Key, H2, P2, Allocator>&& source);
1537
  template<class H2, class P2>
1538
- void merge(unordered_set<Key, H2, P2, Allocator>& source);
1539
  template<class H2, class P2>
1540
- void merge(unordered_set<Key, H2, P2, Allocator>&& source);
1541
 
1542
  // observers
1543
- hasher hash_function() const;
1544
- key_equal key_eq() const;
1545
 
1546
  // set operations
1547
- iterator find(const key_type& k);
1548
- const_iterator find(const key_type& k) const;
1549
  template<class K>
1550
- iterator find(const K& k);
1551
  template<class K>
1552
- const_iterator find(const K& k) const;
1553
- size_type count(const key_type& k) const;
1554
  template<class K>
1555
- size_type count(const K& k) const;
1556
- bool contains(const key_type& k) const;
1557
  template<class K>
1558
- bool contains(const K& k) const;
1559
- pair<iterator, iterator> equal_range(const key_type& k);
1560
- pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
1561
  template<class K>
1562
- pair<iterator, iterator> equal_range(const K& k);
1563
  template<class K>
1564
- pair<const_iterator, const_iterator> equal_range(const K& k) const;
1565
 
1566
  // bucket interface
1567
- size_type bucket_count() const noexcept;
1568
- size_type max_bucket_count() const noexcept;
1569
- size_type bucket_size(size_type n) const;
1570
- size_type bucket(const key_type& k) const;
1571
- local_iterator begin(size_type n);
1572
- const_local_iterator begin(size_type n) const;
1573
- local_iterator end(size_type n);
1574
- const_local_iterator end(size_type n) const;
1575
- const_local_iterator cbegin(size_type n) const;
1576
- const_local_iterator cend(size_type n) const;
 
1577
 
1578
  // hash policy
1579
- float load_factor() const noexcept;
1580
- float max_load_factor() const noexcept;
1581
- void max_load_factor(float z);
1582
- void rehash(size_type n);
1583
- void reserve(size_type n);
1584
  };
1585
 
1586
  template<class InputIterator,
1587
  class Hash = hash<iter-value-type<InputIterator>>,
1588
  class Pred = equal_to<iter-value-type<InputIterator>>,
1589
  class Allocator = allocator<iter-value-type<InputIterator>>>
1590
- unordered_multiset(InputIterator, InputIterator, see below::size_type = see below,
1591
  Hash = Hash(), Pred = Pred(), Allocator = Allocator())
1592
  -> unordered_multiset<iter-value-type<InputIterator>,
1593
  Hash, Pred, Allocator>;
1594
 
1595
  template<ranges::input_range R,
@@ -1650,13 +1769,12 @@ refers to the `size_type` member type of the type deduced by the
1650
  deduction guide.
1651
 
1652
  #### Constructors <a id="unord.multiset.cnstr">[[unord.multiset.cnstr]]</a>
1653
 
1654
  ``` cpp
1655
- unordered_multiset() : unordered_multiset(size_type(see below)) { }
1656
- explicit unordered_multiset(size_type n,
1657
- const hasher& hf = hasher(),
1658
  const key_equal& eql = key_equal(),
1659
  const allocator_type& a = allocator_type());
1660
  ```
1661
 
1662
  *Effects:* Constructs an empty `unordered_multiset` using the specified
@@ -1666,24 +1784,21 @@ hash function, key equality predicate, and allocator, and using at least
1666
 
1667
  *Complexity:* Constant.
1668
 
1669
  ``` cpp
1670
  template<class InputIterator>
1671
- unordered_multiset(InputIterator f, InputIterator l,
1672
- size_type n = see below,
1673
- const hasher& hf = hasher(),
1674
  const key_equal& eql = key_equal(),
1675
  const allocator_type& a = allocator_type());
1676
  template<container-compatible-range<value_type> R>
1677
- unordered_multiset(from_range_t, R&& rg,
1678
- size_type n = see below,
1679
- const hasher& hf = hasher(),
1680
  const key_equal& eql = key_equal(),
1681
  const allocator_type& a = allocator_type());
1682
- unordered_multiset(initializer_list<value_type> il,
1683
- size_type n = see below,
1684
- const hasher& hf = hasher(),
1685
  const key_equal& eql = key_equal(),
1686
  const allocator_type& a = allocator_type());
1687
  ```
1688
 
1689
  *Effects:* Constructs an empty `unordered_multiset` using the specified
@@ -1696,11 +1811,11 @@ hash function, key equality predicate, and allocator, and using at least
1696
 
1697
  #### Erasure <a id="unord.multiset.erasure">[[unord.multiset.erasure]]</a>
1698
 
1699
  ``` cpp
1700
  template<class K, class H, class P, class A, class Predicate>
1701
- typename unordered_multiset<K, H, P, A>::size_type
1702
  erase_if(unordered_multiset<K, H, P, A>& c, Predicate pred);
1703
  ```
1704
 
1705
  *Effects:* Equivalent to:
1706
 
 
1
  ## Unordered associative containers <a id="unord">[[unord]]</a>
2
 
3
+ ### General <a id="unord.general">[[unord.general]]</a>
4
 
5
  The header `<unordered_map>` defines the class templates `unordered_map`
6
  and `unordered_multimap`; the header `<unordered_set>` defines the class
7
  templates `unordered_set` and `unordered_multiset`.
8
 
 
34
  class Pred = equal_to<Key>,
35
  class Alloc = allocator<pair<const Key, T>>>
36
  class unordered_multimap;
37
 
38
  template<class Key, class T, class Hash, class Pred, class Alloc>
39
+ constexpr bool operator==(const unordered_map<Key, T, Hash, Pred, Alloc>& a,
40
  const unordered_map<Key, T, Hash, Pred, Alloc>& b);
41
 
42
  template<class Key, class T, class Hash, class Pred, class Alloc>
43
+ constexpr bool operator==(const unordered_multimap<Key, T, Hash, Pred, Alloc>& a,
44
  const unordered_multimap<Key, T, Hash, Pred, Alloc>& b);
45
 
46
  template<class Key, class T, class Hash, class Pred, class Alloc>
47
+ constexpr void swap(unordered_map<Key, T, Hash, Pred, Alloc>& x,
48
  unordered_map<Key, T, Hash, Pred, Alloc>& y)
49
  noexcept(noexcept(x.swap(y)));
50
 
51
  template<class Key, class T, class Hash, class Pred, class Alloc>
52
+ constexpr void swap(unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
53
  unordered_multimap<Key, T, Hash, Pred, Alloc>& y)
54
  noexcept(noexcept(x.swap(y)));
55
 
56
  // [unord.map.erasure], erasure for unordered_map
57
  template<class K, class T, class H, class P, class A, class Predicate>
58
+ constexpr typename unordered_map<K, T, H, P, A>::size_type
59
  erase_if(unordered_map<K, T, H, P, A>& c, Predicate pred);
60
 
61
  // [unord.multimap.erasure], erasure for unordered_multimap
62
  template<class K, class T, class H, class P, class A, class Predicate>
63
+ constexpr typename unordered_multimap<K, T, H, P, A>::size_type
64
  erase_if(unordered_multimap<K, T, H, P, A>& c, Predicate pred);
65
 
66
  namespace pmr {
67
  template<class Key,
68
  class T,
 
81
 
82
  }
83
  }
84
  ```
85
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
86
  ### Class template `unordered_map` <a id="unord.map">[[unord.map]]</a>
87
 
88
  #### Overview <a id="unord.map.overview">[[unord.map.overview]]</a>
89
 
90
  An `unordered_map` is an unordered associative container that supports
 
103
 
104
  Subclause  [[unord.map]] only describes operations on `unordered_map`
105
  that are not described in one of the requirement tables, or for which
106
  there is additional semantic information.
107
 
108
+ The types `iterator` and `const_iterator` meet the constexpr iterator
109
+ requirements [[iterator.requirements.general]].
110
+
111
  ``` cpp
112
  namespace std {
113
  template<class Key,
114
  class T,
115
  class Hash = hash<Key>,
 
122
  using mapped_type = T;
123
  using value_type = pair<const Key, T>;
124
  using hasher = Hash;
125
  using key_equal = Pred;
126
  using allocator_type = Allocator;
127
+ using pointer = allocator_traits<Allocator>::pointer;
128
+ using const_pointer = allocator_traits<Allocator>::const_pointer;
129
  using reference = value_type&;
130
  using const_reference = const value_type&;
131
  using size_type = implementation-defined // type of unordered_map::size_type; // see [container.requirements]
132
  using difference_type = implementation-defined // type of unordered_map::difference_type; // see [container.requirements]
133
 
 
137
  using const_local_iterator = implementation-defined // type of unordered_map::const_local_iterator; // see [container.requirements]
138
  using node_type = unspecified;
139
  using insert_return_type = insert-return-type<iterator, node_type>;
140
 
141
  // [unord.map.cnstr], construct/copy/destroy
142
+ constexpr unordered_map();
143
+ constexpr explicit unordered_map(size_type n, const hasher& hf = hasher(),
 
144
  const key_equal& eql = key_equal(),
145
  const allocator_type& a = allocator_type());
146
  template<class InputIterator>
147
+ constexpr unordered_map(InputIterator f, InputIterator l,
148
+ size_type n = see below, const hasher& hf = hasher(),
 
149
  const key_equal& eql = key_equal(),
150
  const allocator_type& a = allocator_type());
151
 
152
  template<container-compatible-range<value_type> R>
153
+ constexpr unordered_map(from_range_t, R&& rg, size_type n = see below,
154
  const hasher& hf = hasher(), const key_equal& eql = key_equal(),
155
  const allocator_type& a = allocator_type());
156
+ constexpr unordered_map(const unordered_map&);
157
+ constexpr unordered_map(unordered_map&&);
158
+ constexpr explicit unordered_map(const Allocator&);
159
+ constexpr unordered_map(const unordered_map&, const type_identity_t<Allocator>&);
160
+ constexpr unordered_map(unordered_map&&, const type_identity_t<Allocator>&);
161
+ constexpr unordered_map(initializer_list<value_type> il, size_type n = see below,
 
162
  const hasher& hf = hasher(),
163
  const key_equal& eql = key_equal(),
164
  const allocator_type& a = allocator_type());
165
+ constexpr unordered_map(size_type n, const allocator_type& a)
166
  : unordered_map(n, hasher(), key_equal(), a) { }
167
+ constexpr unordered_map(size_type n, const hasher& hf, const allocator_type& a)
168
  : unordered_map(n, hf, key_equal(), a) { }
169
  template<class InputIterator>
170
+ constexpr unordered_map(InputIterator f, InputIterator l, size_type n,
171
+ const allocator_type& a)
172
  : unordered_map(f, l, n, hasher(), key_equal(), a) { }
173
  template<class InputIterator>
174
+ constexpr unordered_map(InputIterator f, InputIterator l, size_type n, const hasher& hf,
175
  const allocator_type& a)
176
  : unordered_map(f, l, n, hf, key_equal(), a) { }
177
  template<container-compatible-range<value_type> R>
178
+ constexpr unordered_map(from_range_t, R&& rg, size_type n, const allocator_type& a)
179
  : unordered_map(from_range, std::forward<R>(rg), n, hasher(), key_equal(), a) { }
180
  template<container-compatible-range<value_type> R>
181
+ constexpr unordered_map(from_range_t, R&& rg, size_type n, const hasher& hf,
182
+ const allocator_type& a)
183
  : unordered_map(from_range, std::forward<R>(rg), n, hf, key_equal(), a) { }
184
+ constexpr unordered_map(initializer_list<value_type> il, size_type n,
185
+ const allocator_type& a)
186
  : unordered_map(il, n, hasher(), key_equal(), a) { }
187
+ constexpr unordered_map(initializer_list<value_type> il, size_type n, const hasher& hf,
188
  const allocator_type& a)
189
  : unordered_map(il, n, hf, key_equal(), a) { }
190
+ constexpr ~unordered_map();
191
+ constexpr unordered_map& operator=(const unordered_map&);
192
+ constexpr unordered_map& operator=(unordered_map&&)
193
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
194
  is_nothrow_move_assignable_v<Hash> &&
195
  is_nothrow_move_assignable_v<Pred>);
196
+ constexpr unordered_map& operator=(initializer_list<value_type>);
197
+ constexpr allocator_type get_allocator() const noexcept;
198
 
199
  // iterators
200
+ constexpr iterator begin() noexcept;
201
+ constexpr const_iterator begin() const noexcept;
202
+ constexpr iterator end() noexcept;
203
+ constexpr const_iterator end() const noexcept;
204
+ constexpr const_iterator cbegin() const noexcept;
205
+ constexpr const_iterator cend() const noexcept;
206
 
207
  // capacity
208
+ constexpr bool empty() const noexcept;
209
+ constexpr size_type size() const noexcept;
210
+ constexpr size_type max_size() const noexcept;
211
 
212
  // [unord.map.modifiers], modifiers
213
+ template<class... Args> constexpr pair<iterator, bool> emplace(Args&&... args);
214
+ template<class... Args>
215
+ constexpr iterator emplace_hint(const_iterator position, Args&&... args);
216
+ constexpr pair<iterator, bool> insert(const value_type& obj);
217
+ constexpr pair<iterator, bool> insert(value_type&& obj);
218
+ template<class P> constexpr pair<iterator, bool> insert(P&& obj);
219
+ constexpr iterator insert(const_iterator hint, const value_type& obj);
220
+ constexpr iterator insert(const_iterator hint, value_type&& obj);
221
+ template<class P> constexpr iterator insert(const_iterator hint, P&& obj);
222
+ template<class InputIterator> constexpr void insert(InputIterator first, InputIterator last);
223
  template<container-compatible-range<value_type> R>
224
+ constexpr void insert_range(R&& rg);
225
+ constexpr void insert(initializer_list<value_type>);
226
 
227
+ constexpr node_type extract(const_iterator position);
228
+ constexpr node_type extract(const key_type& x);
229
+ template<class K> constexpr node_type extract(K&& x);
230
+ constexpr insert_return_type insert(node_type&& nh);
231
+ constexpr iterator insert(const_iterator hint, node_type&& nh);
232
 
233
  template<class... Args>
234
+ constexpr pair<iterator, bool> try_emplace(const key_type& k, Args&&... args);
235
  template<class... Args>
236
+ constexpr pair<iterator, bool> try_emplace(key_type&& k, Args&&... args);
237
+ template<class K, class... Args>
238
+ constexpr pair<iterator, bool> try_emplace(K&& k, Args&&... args);
239
  template<class... Args>
240
+ constexpr iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args);
241
  template<class... Args>
242
+ constexpr iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args);
243
+ template<class K, class... Args>
244
+ constexpr iterator try_emplace(const_iterator hint, K&& k, Args&&... args);
245
  template<class M>
246
+ constexpr pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj);
247
  template<class M>
248
+ constexpr pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj);
249
+ template<class K, class M>
250
+ constexpr pair<iterator, bool> insert_or_assign(K&& k, M&& obj);
251
  template<class M>
252
+ constexpr iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj);
253
  template<class M>
254
+ constexpr iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj);
255
+ template<class K, class M>
256
+ constexpr iterator insert_or_assign(const_iterator hint, K&& k, M&& obj);
257
 
258
+ constexpr iterator erase(iterator position);
259
+ constexpr iterator erase(const_iterator position);
260
+ constexpr size_type erase(const key_type& k);
261
+ template<class K> constexpr size_type erase(K&& x);
262
+ constexpr iterator erase(const_iterator first, const_iterator last);
263
+ constexpr void swap(unordered_map&)
264
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
265
+ is_nothrow_swappable_v<Hash> && is_nothrow_swappable_v<Pred>);
266
+ constexpr void clear() noexcept;
 
267
 
268
  template<class H2, class P2>
269
+ constexpr void merge(unordered_map<Key, T, H2, P2, Allocator>& source);
270
  template<class H2, class P2>
271
+ constexpr void merge(unordered_map<Key, T, H2, P2, Allocator>&& source);
272
  template<class H2, class P2>
273
+ constexpr void merge(unordered_multimap<Key, T, H2, P2, Allocator>& source);
274
  template<class H2, class P2>
275
+ constexpr void merge(unordered_multimap<Key, T, H2, P2, Allocator>&& source);
276
 
277
  // observers
278
+ constexpr hasher hash_function() const;
279
+ constexpr key_equal key_eq() const;
280
 
281
  // map operations
282
+ constexpr iterator find(const key_type& k);
283
+ constexpr const_iterator find(const key_type& k) const;
284
  template<class K>
285
+ constexpr iterator find(const K& k);
286
  template<class K>
287
+ constexpr const_iterator find(const K& k) const;
288
+ constexpr size_type count(const key_type& k) const;
289
  template<class K>
290
+ constexpr size_type count(const K& k) const;
291
+ constexpr bool contains(const key_type& k) const;
292
  template<class K>
293
+ constexpr bool contains(const K& k) const;
294
+ constexpr pair<iterator, iterator> equal_range(const key_type& k);
295
+ constexpr pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
296
  template<class K>
297
+ constexpr pair<iterator, iterator> equal_range(const K& k);
298
  template<class K>
299
+ constexpr pair<const_iterator, const_iterator> equal_range(const K& k) const;
300
 
301
  // [unord.map.elem], element access
302
+ constexpr mapped_type& operator[](const key_type& k);
303
+ constexpr mapped_type& operator[](key_type&& k);
304
+ template<class K> constexpr mapped_type& operator[](K&& k);
305
+ constexpr mapped_type& at(const key_type& k);
306
+ constexpr const mapped_type& at(const key_type& k) const;
307
+ template<class K> constexpr mapped_type& at(const K& k);
308
+ template<class K> constexpr const mapped_type& at(const K& k) const;
309
 
310
  // bucket interface
311
+ constexpr size_type bucket_count() const noexcept;
312
+ constexpr size_type max_bucket_count() const noexcept;
313
+ constexpr size_type bucket_size(size_type n) const;
314
+ constexpr size_type bucket(const key_type& k) const;
315
+ template<class K> constexpr size_type bucket(const K& k) const;
316
+ constexpr local_iterator begin(size_type n);
317
+ constexpr const_local_iterator begin(size_type n) const;
318
+ constexpr local_iterator end(size_type n);
319
+ constexpr const_local_iterator end(size_type n) const;
320
+ constexpr const_local_iterator cbegin(size_type n) const;
321
+ constexpr const_local_iterator cend(size_type n) const;
322
 
323
  // hash policy
324
+ constexpr float load_factor() const noexcept;
325
+ constexpr float max_load_factor() const noexcept;
326
+ constexpr void max_load_factor(float z);
327
+ constexpr void rehash(size_type n);
328
+ constexpr void reserve(size_type n);
329
  };
330
 
331
  template<class InputIterator,
332
  class Hash = hash<iter-key-type<InputIterator>>,
333
  class Pred = equal_to<iter-key-type<InputIterator>>,
 
404
  deduction guide.
405
 
406
  #### Constructors <a id="unord.map.cnstr">[[unord.map.cnstr]]</a>
407
 
408
  ``` cpp
409
+ constexpr unordered_map() : unordered_map(size_type(see below)) { }
410
+ constexpr explicit unordered_map(size_type n, const hasher& hf = hasher(),
 
411
  const key_equal& eql = key_equal(),
412
  const allocator_type& a = allocator_type());
413
  ```
414
 
415
  *Effects:* Constructs an empty `unordered_map` using the specified hash
 
419
 
420
  *Complexity:* Constant.
421
 
422
  ``` cpp
423
  template<class InputIterator>
424
+ constexpr unordered_map(InputIterator f, InputIterator l,
425
+ size_type n = see below, const hasher& hf = hasher(),
 
426
  const key_equal& eql = key_equal(),
427
  const allocator_type& a = allocator_type());
428
  template<container-compatible-range<value_type> R>
429
+ constexpr unordered_map(from_range_t, R&& rg,
430
+ size_type n = see below, const hasher& hf = hasher(),
 
431
  const key_equal& eql = key_equal(),
432
  const allocator_type& a = allocator_type());
433
+ constexpr unordered_map(initializer_list<value_type> il,
434
+ size_type n = see below, const hasher& hf = hasher(),
 
435
  const key_equal& eql = key_equal(),
436
  const allocator_type& a = allocator_type());
437
  ```
438
 
439
  *Effects:* Constructs an empty `unordered_map` using the specified hash
 
445
  *Complexity:* Average case linear, worst case quadratic.
446
 
447
  #### Element access <a id="unord.map.elem">[[unord.map.elem]]</a>
448
 
449
  ``` cpp
450
+ constexpr mapped_type& operator[](const key_type& k);
451
  ```
452
 
453
  *Effects:* Equivalent to: `return try_emplace(k).first->second;`
454
 
455
  ``` cpp
456
+ constexpr mapped_type& operator[](key_type&& k);
457
  ```
458
 
459
  *Effects:* Equivalent to:
460
  `return try_emplace(std::move(k)).first->second;`
461
 
462
  ``` cpp
463
+ template<class K> constexpr mapped_type& operator[](K&& k);
464
+ ```
465
+
466
+ *Constraints:* The *qualified-id*s `Hash::is_transparent` and
467
+ `Pred::is_transparent` are valid and denote types.
468
+
469
+ *Effects:* Equivalent to:
470
+ `return try_emplace(std::forward<K>(k)).first->second;`
471
+
472
+ ``` cpp
473
+ constexpr mapped_type& at(const key_type& k);
474
+ constexpr const mapped_type& at(const key_type& k) const;
475
  ```
476
 
477
  *Returns:* A reference to `x.second`, where `x` is the (unique) element
478
  whose key is equivalent to `k`.
479
 
480
  *Throws:* An exception object of type `out_of_range` if no such element
481
  is present.
482
 
483
+ ``` cpp
484
+ template<class K> constexpr mapped_type& at(const K& k);
485
+ template<class K> constexpr const mapped_type& at(const K& k) const;
486
+ ```
487
+
488
+ *Constraints:* The *qualified-id*s `Hash::is_transparent` and
489
+ `Pred::is_transparent` are valid and denote types.
490
+
491
+ *Preconditions:* The expression `find(k)` is well-formed and has
492
+ well-defined behavior.
493
+
494
+ *Returns:* A reference to `find(k)->second`.
495
+
496
+ *Throws:* An exception object of type `out_of_range` if
497
+ `find(k) == end()` is `true`.
498
+
499
  #### Modifiers <a id="unord.map.modifiers">[[unord.map.modifiers]]</a>
500
 
501
  ``` cpp
502
  template<class P>
503
+ constexpr pair<iterator, bool> insert(P&& obj);
504
  ```
505
 
506
  *Constraints:* `is_constructible_v<value_type, P&&>` is `true`.
507
 
508
  *Effects:* Equivalent to: `return emplace(std::forward<P>(obj));`
509
 
510
  ``` cpp
511
  template<class P>
512
+ constexpr iterator insert(const_iterator hint, P&& obj);
513
  ```
514
 
515
  *Constraints:* `is_constructible_v<value_type, P&&>` is `true`.
516
 
517
  *Effects:* Equivalent to:
518
  `return emplace_hint(hint, std::forward<P>(obj));`
519
 
520
  ``` cpp
521
  template<class... Args>
522
+ constexpr pair<iterator, bool> try_emplace(const key_type& k, Args&&... args);
523
  template<class... Args>
524
+ constexpr iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args);
525
  ```
526
 
527
  *Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into
528
  `unordered_map` from `piecewise_construct`, `forward_as_tuple(k)`,
529
  `forward_as_tuple(std::forward<Args>(args)...)`.
 
539
 
540
  *Complexity:* The same as `emplace` and `emplace_hint`, respectively.
541
 
542
  ``` cpp
543
  template<class... Args>
544
+ constexpr pair<iterator, bool> try_emplace(key_type&& k, Args&&... args);
545
  template<class... Args>
546
+ constexpr iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args);
547
  ```
548
 
549
  *Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into
550
  `unordered_map` from `piecewise_construct`,
551
  `forward_as_tuple(std::move(k))`,
 
561
  pair is `true` if and only if the insertion took place. The returned
562
  iterator points to the map element whose key is equivalent to `k`.
563
 
564
  *Complexity:* The same as `emplace` and `emplace_hint`, respectively.
565
 
566
+ ``` cpp
567
+ template<class K, class... Args>
568
+ constexpr pair<iterator, bool> try_emplace(K&& k, Args&&... args);
569
+ template<class K, class... Args>
570
+ constexpr iterator try_emplace(const_iterator hint, K&& k, Args&&... args);
571
+ ```
572
+
573
+ *Constraints:* The *qualified-id*s `Hash::is_transparent` and
574
+ `Pred::is_transparent` are valid and denote types. For the first
575
+ overload, `is_convertible_v<K&&, const_iterator>` and
576
+ `is_convertible_v<K&&, iterator>` are both `false`.
577
+
578
+ *Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into
579
+ `unordered_map` from
580
+ `piecewise_construct, forward_as_tuple(std::forward<K>(k)), forward_as_tuple(std::forward<Args> (args)...)`.
581
+
582
+ *Effects:* If the map already contains an element whose key is
583
+ equivalent to `k`, there is no effect. Otherwise, let `h` be
584
+ `hash_function()(k)`. Constructs an object `u` of type `value_type` with
585
+ `piecewise_construct, forward_as_tuple(std::forward<K>(k)), forward_as_tuple(std::forward<Args>(args)...)`.
586
+ If `hash_function()(u.first) != h || contains(u.first)` is `true`, the
587
+ behavior is undefined. Inserts `u` into `*this`.
588
+
589
+ *Returns:* For the first overload, the `bool` component of the returned
590
+ pair is `true` if and only if the insertion took place. The returned
591
+ iterator points to the map element whose key is equivalent to `k`.
592
+
593
+ *Complexity:* The same as `emplace` and `emplace_hint`, respectively.
594
+
595
  ``` cpp
596
  template<class M>
597
+ constexpr pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj);
598
  template<class M>
599
+ constexpr iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj);
600
  ```
601
 
602
  *Mandates:* `is_assignable_v<mapped_type&, M&&>` is `true`.
603
 
604
  *Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into
 
615
 
616
  *Complexity:* The same as `emplace` and `emplace_hint`, respectively.
617
 
618
  ``` cpp
619
  template<class M>
620
+ constexpr pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj);
621
  template<class M>
622
+ constexpr iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj);
623
  ```
624
 
625
  *Mandates:* `is_assignable_v<mapped_type&, M&&>` is `true`.
626
 
627
  *Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into
 
636
  pair is `true` if and only if the insertion took place. The returned
637
  iterator points to the map element whose key is equivalent to `k`.
638
 
639
  *Complexity:* The same as `emplace` and `emplace_hint`, respectively.
640
 
641
+ ``` cpp
642
+ template<class K, class M>
643
+ constexpr pair<iterator, bool> insert_or_assign(K&& k, M&& obj);
644
+ template<class K, class M>
645
+ constexpr iterator insert_or_assign(const_iterator hint, K&& k, M&& obj);
646
+ ```
647
+
648
+ *Constraints:* The *qualified-id*s `Hash::is_transparent` and
649
+ `Pred::is_transparent` are valid and denote types.
650
+
651
+ *Mandates:* `is_assignable_v<mapped_type&, M&&>` is `true`.
652
+
653
+ *Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into
654
+ `unordered_map` from `std::forward<K> (k), std::forward<M>(obj)`.
655
+
656
+ *Effects:* If the map already contains an element `e` whose key is
657
+ equivalent to `k`, assigns `std::forward<M> (obj)` to `e.second`.
658
+ Otherwise, let `h` be `hash_function()(k)`. Constructs an object `u` of
659
+ type `value_type` with `std::forward<K>(k), std::forward<M>(obj)`. If
660
+ `hash_function()(u.first) != h || contains(u.first)` is `true`, the
661
+ behavior is undefined. Inserts `u` into `*this`.
662
+
663
+ *Returns:* For the first overload, the `bool` component of the returned
664
+ pair is `true` if and only if the insertion took place. The returned
665
+ iterator points to the map element whose key is equivalent to `k`.
666
+
667
+ *Complexity:* The same as `emplace` and `emplace_hint`, respectively.
668
+
669
  #### Erasure <a id="unord.map.erasure">[[unord.map.erasure]]</a>
670
 
671
  ``` cpp
672
  template<class K, class T, class H, class P, class A, class Predicate>
673
+ constexpr typename unordered_map<K, T, H, P, A>::size_type
674
  erase_if(unordered_map<K, T, H, P, A>& c, Predicate pred);
675
  ```
676
 
677
  *Effects:* Equivalent to:
678
 
 
709
 
710
  Subclause  [[unord.multimap]] only describes operations on
711
  `unordered_multimap` that are not described in one of the requirement
712
  tables, or for which there is additional semantic information.
713
 
714
+ The types `iterator` and `const_iterator` meet the constexpr iterator
715
+ requirements [[iterator.requirements.general]].
716
+
717
  ``` cpp
718
  namespace std {
719
  template<class Key,
720
  class T,
721
  class Hash = hash<Key>,
 
728
  using mapped_type = T;
729
  using value_type = pair<const Key, T>;
730
  using hasher = Hash;
731
  using key_equal = Pred;
732
  using allocator_type = Allocator;
733
+ using pointer = allocator_traits<Allocator>::pointer;
734
+ using const_pointer = allocator_traits<Allocator>::const_pointer;
735
  using reference = value_type&;
736
  using const_reference = const value_type&;
737
  using size_type = implementation-defined // type of unordered_multimap::size_type; // see [container.requirements]
738
  using difference_type = implementation-defined // type of unordered_multimap::difference_type; // see [container.requirements]
739
 
 
742
  using local_iterator = implementation-defined // type of unordered_multimap::local_iterator; // see [container.requirements]
743
  using const_local_iterator = implementation-defined // type of unordered_multimap::const_local_iterator; // see [container.requirements]
744
  using node_type = unspecified;
745
 
746
  // [unord.multimap.cnstr], construct/copy/destroy
747
+ constexpr unordered_multimap();
748
+ constexpr explicit unordered_multimap(size_type n, const hasher& hf = hasher(),
 
749
  const key_equal& eql = key_equal(),
750
  const allocator_type& a = allocator_type());
751
  template<class InputIterator>
752
+ constexpr unordered_multimap(InputIterator f, InputIterator l,
753
+ size_type n = see below, const hasher& hf = hasher(),
 
754
  const key_equal& eql = key_equal(),
755
  const allocator_type& a = allocator_type());
756
  template<container-compatible-range<value_type> R>
757
+ constexpr unordered_multimap(from_range_t, R&& rg,
758
+ size_type n = see below, const hasher& hf = hasher(),
 
759
  const key_equal& eql = key_equal(),
760
  const allocator_type& a = allocator_type());
761
+ constexpr unordered_multimap(const unordered_multimap&);
762
+ constexpr unordered_multimap(unordered_multimap&&);
763
+ constexpr explicit unordered_multimap(const Allocator&);
764
+ constexpr unordered_multimap(const unordered_multimap&, const type_identity_t<Allocator>&);
765
+ constexpr unordered_multimap(unordered_multimap&&, const type_identity_t<Allocator>&);
766
+ constexpr unordered_multimap(initializer_list<value_type> il,
767
+ size_type n = see below, const hasher& hf = hasher(),
 
768
  const key_equal& eql = key_equal(),
769
  const allocator_type& a = allocator_type());
770
+ constexpr unordered_multimap(size_type n, const allocator_type& a)
771
  : unordered_multimap(n, hasher(), key_equal(), a) { }
772
+ constexpr unordered_multimap(size_type n, const hasher& hf, const allocator_type& a)
773
  : unordered_multimap(n, hf, key_equal(), a) { }
774
  template<class InputIterator>
775
+ constexpr unordered_multimap(InputIterator f, InputIterator l, size_type n,
776
+ const allocator_type& a)
777
  : unordered_multimap(f, l, n, hasher(), key_equal(), a) { }
778
  template<class InputIterator>
779
+ constexpr unordered_multimap(InputIterator f, InputIterator l, size_type n,
780
+ const hasher& hf, const allocator_type& a)
781
  : unordered_multimap(f, l, n, hf, key_equal(), a) { }
782
  template<container-compatible-range<value_type> R>
783
+ constexpr unordered_multimap(from_range_t, R&& rg, size_type n, const allocator_type& a)
784
  : unordered_multimap(from_range, std::forward<R>(rg),
785
  n, hasher(), key_equal(), a) { }
786
  template<container-compatible-range<value_type> R>
787
+ constexpr unordered_multimap(from_range_t, R&& rg, size_type n, const hasher& hf,
788
  const allocator_type& a)
789
  : unordered_multimap(from_range, std::forward<R>(rg), n, hf, key_equal(), a) { }
790
+ constexpr unordered_multimap(initializer_list<value_type> il, size_type n,
791
+ const allocator_type& a)
792
  : unordered_multimap(il, n, hasher(), key_equal(), a) { }
793
+ constexpr unordered_multimap(initializer_list<value_type> il, size_type n, const hasher& hf,
794
  const allocator_type& a)
795
  : unordered_multimap(il, n, hf, key_equal(), a) { }
796
+ constexpr ~unordered_multimap();
797
+ constexpr unordered_multimap& operator=(const unordered_multimap&);
798
+ constexpr unordered_multimap& operator=(unordered_multimap&&)
799
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
800
+ is_nothrow_move_assignable_v<Hash> && is_nothrow_move_assignable_v<Pred>);
801
+ constexpr unordered_multimap& operator=(initializer_list<value_type>);
802
+ constexpr allocator_type get_allocator() const noexcept;
 
803
 
804
  // iterators
805
+ constexpr iterator begin() noexcept;
806
+ constexpr const_iterator begin() const noexcept;
807
+ constexpr iterator end() noexcept;
808
+ constexpr const_iterator end() const noexcept;
809
+ constexpr const_iterator cbegin() const noexcept;
810
+ constexpr const_iterator cend() const noexcept;
811
 
812
  // capacity
813
+ constexpr bool empty() const noexcept;
814
+ constexpr size_type size() const noexcept;
815
+ constexpr size_type max_size() const noexcept;
816
 
817
  // [unord.multimap.modifiers], modifiers
818
+ template<class... Args> constexpr iterator emplace(Args&&... args);
819
+ template<class... Args>
820
+ constexpr iterator emplace_hint(const_iterator position, Args&&... args);
821
+ constexpr iterator insert(const value_type& obj);
822
+ constexpr iterator insert(value_type&& obj);
823
+ template<class P> constexpr iterator insert(P&& obj);
824
+ constexpr iterator insert(const_iterator hint, const value_type& obj);
825
+ constexpr iterator insert(const_iterator hint, value_type&& obj);
826
+ template<class P> constexpr iterator insert(const_iterator hint, P&& obj);
827
+ template<class InputIterator> constexpr void insert(InputIterator first, InputIterator last);
828
  template<container-compatible-range<value_type> R>
829
+ constexpr void insert_range(R&& rg);
830
+ constexpr void insert(initializer_list<value_type>);
831
 
832
+ constexpr node_type extract(const_iterator position);
833
+ constexpr node_type extract(const key_type& x);
834
+ template<class K> constexpr node_type extract(K&& x);
835
+ constexpr iterator insert(node_type&& nh);
836
+ constexpr iterator insert(const_iterator hint, node_type&& nh);
837
 
838
+ constexpr iterator erase(iterator position);
839
+ constexpr iterator erase(const_iterator position);
840
+ constexpr size_type erase(const key_type& k);
841
+ template<class K> constexpr size_type erase(K&& x);
842
+ constexpr iterator erase(const_iterator first, const_iterator last);
843
+ constexpr void swap(unordered_multimap&)
844
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
845
+ is_nothrow_swappable_v<Hash> && is_nothrow_swappable_v<Pred>);
846
+ constexpr void clear() noexcept;
 
847
 
848
  template<class H2, class P2>
849
+ constexpr void merge(unordered_multimap<Key, T, H2, P2, Allocator>& source);
850
  template<class H2, class P2>
851
+ constexpr void merge(unordered_multimap<Key, T, H2, P2, Allocator>&& source);
852
  template<class H2, class P2>
853
+ constexpr void merge(unordered_map<Key, T, H2, P2, Allocator>& source);
854
  template<class H2, class P2>
855
+ constexpr void merge(unordered_map<Key, T, H2, P2, Allocator>&& source);
856
 
857
  // observers
858
+ constexpr hasher hash_function() const;
859
+ constexpr key_equal key_eq() const;
860
 
861
  // map operations
862
+ constexpr iterator find(const key_type& k);
863
+ constexpr const_iterator find(const key_type& k) const;
864
  template<class K>
865
+ constexpr iterator find(const K& k);
866
  template<class K>
867
+ constexpr const_iterator find(const K& k) const;
868
+ constexpr size_type count(const key_type& k) const;
869
  template<class K>
870
+ constexpr size_type count(const K& k) const;
871
+ constexpr bool contains(const key_type& k) const;
872
  template<class K>
873
+ constexpr bool contains(const K& k) const;
874
+ constexpr pair<iterator, iterator> equal_range(const key_type& k);
875
+ constexpr pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
876
  template<class K>
877
+ constexpr pair<iterator, iterator> equal_range(const K& k);
878
  template<class K>
879
+ constexpr pair<const_iterator, const_iterator> equal_range(const K& k) const;
880
 
881
  // bucket interface
882
+ constexpr size_type bucket_count() const noexcept;
883
+ constexpr size_type max_bucket_count() const noexcept;
884
+ constexpr size_type bucket_size(size_type n) const;
885
+ constexpr size_type bucket(const key_type& k) const;
886
+ template<class K> constexpr size_type bucket(const K& k) const;
887
+ constexpr local_iterator begin(size_type n);
888
+ constexpr const_local_iterator begin(size_type n) const;
889
+ constexpr local_iterator end(size_type n);
890
+ constexpr const_local_iterator end(size_type n) const;
891
+ constexpr const_local_iterator cbegin(size_type n) const;
892
+ constexpr const_local_iterator cend(size_type n) const;
893
 
894
  // hash policy
895
+ constexpr float load_factor() const noexcept;
896
+ constexpr float max_load_factor() const noexcept;
897
+ constexpr void max_load_factor(float z);
898
+ constexpr void rehash(size_type n);
899
+ constexpr void reserve(size_type n);
900
  };
901
 
902
  template<class InputIterator,
903
  class Hash = hash<iter-key-type<InputIterator>>,
904
  class Pred = equal_to<iter-key-type<InputIterator>>,
 
978
  deduction guide.
979
 
980
  #### Constructors <a id="unord.multimap.cnstr">[[unord.multimap.cnstr]]</a>
981
 
982
  ``` cpp
983
+ constexpr unordered_multimap() : unordered_multimap(size_type(see below)) { }
984
+ constexpr explicit unordered_multimap(size_type n, const hasher& hf = hasher(),
 
985
  const key_equal& eql = key_equal(),
986
  const allocator_type& a = allocator_type());
987
  ```
988
 
989
  *Effects:* Constructs an empty `unordered_multimap` using the specified
 
993
 
994
  *Complexity:* Constant.
995
 
996
  ``` cpp
997
  template<class InputIterator>
998
+ constexpr unordered_multimap(InputIterator f, InputIterator l,
999
+ size_type n = see below, const hasher& hf = hasher(),
 
1000
  const key_equal& eql = key_equal(),
1001
  const allocator_type& a = allocator_type());
1002
  template<container-compatible-range<value_type> R>
1003
+ constexpr unordered_multimap(from_range_t, R&& rg,
1004
+ size_type n = see below, const hasher& hf = hasher(),
 
1005
  const key_equal& eql = key_equal(),
1006
  const allocator_type& a = allocator_type());
1007
+ constexpr unordered_multimap(initializer_list<value_type> il,
1008
+ size_type n = see below, const hasher& hf = hasher(),
 
1009
  const key_equal& eql = key_equal(),
1010
  const allocator_type& a = allocator_type());
1011
  ```
1012
 
1013
  *Effects:* Constructs an empty `unordered_multimap` using the specified
 
1020
 
1021
  #### Modifiers <a id="unord.multimap.modifiers">[[unord.multimap.modifiers]]</a>
1022
 
1023
  ``` cpp
1024
  template<class P>
1025
+ constexpr iterator insert(P&& obj);
1026
  ```
1027
 
1028
  *Constraints:* `is_constructible_v<value_type, P&&>` is `true`.
1029
 
1030
  *Effects:* Equivalent to: `return emplace(std::forward<P>(obj));`
1031
 
1032
  ``` cpp
1033
  template<class P>
1034
+ constexpr iterator insert(const_iterator hint, P&& obj);
1035
  ```
1036
 
1037
  *Constraints:* `is_constructible_v<value_type, P&&>` is `true`.
1038
 
1039
  *Effects:* Equivalent to:
 
1041
 
1042
  #### Erasure <a id="unord.multimap.erasure">[[unord.multimap.erasure]]</a>
1043
 
1044
  ``` cpp
1045
  template<class K, class T, class H, class P, class A, class Predicate>
1046
+ constexpr typename unordered_multimap<K, T, H, P, A>::size_type
1047
  erase_if(unordered_multimap<K, T, H, P, A>& c, Predicate pred);
1048
  ```
1049
 
1050
  *Effects:* Equivalent to:
1051
 
 
1059
  }
1060
  }
1061
  return original_size - c.size();
1062
  ```
1063
 
1064
+ ### Header `<unordered_set>` synopsis <a id="unord.set.syn">[[unord.set.syn]]</a>
1065
+
1066
+ ``` cpp
1067
+ #include <compare> // see [compare.syn]
1068
+ #include <initializer_list> // see [initializer.list.syn]
1069
+
1070
+ namespace std {
1071
+ // [unord.set], class template unordered_set
1072
+ template<class Key,
1073
+ class Hash = hash<Key>,
1074
+ class Pred = equal_to<Key>,
1075
+ class Alloc = allocator<Key>>
1076
+ class unordered_set;
1077
+
1078
+ // [unord.multiset], class template unordered_multiset
1079
+ template<class Key,
1080
+ class Hash = hash<Key>,
1081
+ class Pred = equal_to<Key>,
1082
+ class Alloc = allocator<Key>>
1083
+ class unordered_multiset;
1084
+
1085
+ template<class Key, class Hash, class Pred, class Alloc>
1086
+ constexpr bool operator==(const unordered_set<Key, Hash, Pred, Alloc>& a,
1087
+ const unordered_set<Key, Hash, Pred, Alloc>& b);
1088
+
1089
+ template<class Key, class Hash, class Pred, class Alloc>
1090
+ constexpr bool operator==(const unordered_multiset<Key, Hash, Pred, Alloc>& a,
1091
+ const unordered_multiset<Key, Hash, Pred, Alloc>& b);
1092
+
1093
+ template<class Key, class Hash, class Pred, class Alloc>
1094
+ constexpr void swap(unordered_set<Key, Hash, Pred, Alloc>& x,
1095
+ unordered_set<Key, Hash, Pred, Alloc>& y)
1096
+ noexcept(noexcept(x.swap(y)));
1097
+
1098
+ template<class Key, class Hash, class Pred, class Alloc>
1099
+ constexpr void swap(unordered_multiset<Key, Hash, Pred, Alloc>& x,
1100
+ unordered_multiset<Key, Hash, Pred, Alloc>& y)
1101
+ noexcept(noexcept(x.swap(y)));
1102
+
1103
+ // [unord.set.erasure], erasure for unordered_set
1104
+ template<class K, class H, class P, class A, class Predicate>
1105
+ constexpr typename unordered_set<K, H, P, A>::size_type
1106
+ erase_if(unordered_set<K, H, P, A>& c, Predicate pred);
1107
+
1108
+ // [unord.multiset.erasure], erasure for unordered_multiset
1109
+ template<class K, class H, class P, class A, class Predicate>
1110
+ constexpr typename unordered_multiset<K, H, P, A>::size_type
1111
+ erase_if(unordered_multiset<K, H, P, A>& c, Predicate pred);
1112
+
1113
+ namespace pmr {
1114
+ template<class Key,
1115
+ class Hash = hash<Key>,
1116
+ class Pred = equal_to<Key>>
1117
+ using unordered_set = std::unordered_set<Key, Hash, Pred,
1118
+ polymorphic_allocator<Key>>;
1119
+
1120
+ template<class Key,
1121
+ class Hash = hash<Key>,
1122
+ class Pred = equal_to<Key>>
1123
+ using unordered_multiset = std::unordered_multiset<Key, Hash, Pred,
1124
+ polymorphic_allocator<Key>>;
1125
+ }
1126
+ }
1127
+ ```
1128
+
1129
  ### Class template `unordered_set` <a id="unord.set">[[unord.set]]</a>
1130
 
1131
  #### Overview <a id="unord.set.overview">[[unord.set.overview]]</a>
1132
 
1133
  An `unordered_set` is an unordered associative container that supports
 
1135
  and in which the elements’ keys are the elements themselves. The
1136
  `unordered_set` class supports forward iterators.
1137
 
1138
  An `unordered_set` meets all of the requirements of a container
1139
  [[container.reqmts]], of an allocator-aware container
1140
+ [[container.alloc.reqmts]], and of an unordered associative container
1141
  [[unord.req]]. It provides the operations described in the preceding
1142
  requirements table for unique keys; that is, an `unordered_set` supports
1143
  the `a_uniq` operations in that table, not the `a_eq` operations. For an
1144
  `unordered_set<Key>` the `key_type` and the `value_type` are both `Key`.
1145
  The `iterator` and `const_iterator` types are both constant iterator
 
1147
 
1148
  Subclause  [[unord.set]] only describes operations on `unordered_set`
1149
  that are not described in one of the requirement tables, or for which
1150
  there is additional semantic information.
1151
 
1152
+ The types `iterator` and `const_iterator` meet the constexpr iterator
1153
+ requirements [[iterator.requirements.general]].
1154
+
1155
  ``` cpp
1156
  namespace std {
1157
  template<class Key,
1158
  class Hash = hash<Key>,
1159
  class Pred = equal_to<Key>,
 
1164
  using key_type = Key;
1165
  using value_type = Key;
1166
  using hasher = Hash;
1167
  using key_equal = Pred;
1168
  using allocator_type = Allocator;
1169
+ using pointer = allocator_traits<Allocator>::pointer;
1170
+ using const_pointer = allocator_traits<Allocator>::const_pointer;
1171
  using reference = value_type&;
1172
  using const_reference = const value_type&;
1173
  using size_type = implementation-defined // type of unordered_set::size_type; // see [container.requirements]
1174
  using difference_type = implementation-defined // type of unordered_set::difference_type; // see [container.requirements]
1175
 
 
1179
  using const_local_iterator = implementation-defined // type of unordered_set::const_local_iterator; // see [container.requirements]
1180
  using node_type = unspecified;
1181
  using insert_return_type = insert-return-type<iterator, node_type>;
1182
 
1183
  // [unord.set.cnstr], construct/copy/destroy
1184
+ constexpr unordered_set();
1185
+ constexpr explicit unordered_set(size_type n, const hasher& hf = hasher(),
 
1186
  const key_equal& eql = key_equal(),
1187
  const allocator_type& a = allocator_type());
1188
  template<class InputIterator>
1189
+ constexpr unordered_set(InputIterator f, InputIterator l,
1190
+ size_type n = see below, const hasher& hf = hasher(),
 
1191
  const key_equal& eql = key_equal(),
1192
  const allocator_type& a = allocator_type());
1193
  template<container-compatible-range<value_type> R>
1194
+ constexpr unordered_set(from_range_t, R&& rg,
1195
+ size_type n = see below, const hasher& hf = hasher(),
 
1196
  const key_equal& eql = key_equal(),
1197
  const allocator_type& a = allocator_type());
1198
+ constexpr unordered_set(const unordered_set&);
1199
+ constexpr unordered_set(unordered_set&&);
1200
+ constexpr explicit unordered_set(const Allocator&);
1201
+ constexpr unordered_set(const unordered_set&, const type_identity_t<Allocator>&);
1202
+ constexpr unordered_set(unordered_set&&, const type_identity_t<Allocator>&);
1203
+ constexpr unordered_set(initializer_list<value_type> il,
1204
+ size_type n = see below, const hasher& hf = hasher(),
 
1205
  const key_equal& eql = key_equal(),
1206
  const allocator_type& a = allocator_type());
1207
+ constexpr unordered_set(size_type n, const allocator_type& a)
1208
  : unordered_set(n, hasher(), key_equal(), a) { }
1209
+ constexpr unordered_set(size_type n, const hasher& hf, const allocator_type& a)
1210
  : unordered_set(n, hf, key_equal(), a) { }
1211
  template<class InputIterator>
1212
+ constexpr unordered_set(InputIterator f, InputIterator l, size_type n,
1213
+ const allocator_type& a)
1214
  : unordered_set(f, l, n, hasher(), key_equal(), a) { }
1215
  template<class InputIterator>
1216
+ constexpr unordered_set(InputIterator f, InputIterator l, size_type n, const hasher& hf,
1217
  const allocator_type& a)
1218
  : unordered_set(f, l, n, hf, key_equal(), a) { }
1219
+ constexpr unordered_set(initializer_list<value_type> il, size_type n,
1220
+ const allocator_type& a)
1221
  : unordered_set(il, n, hasher(), key_equal(), a) { }
1222
  template<container-compatible-range<value_type> R>
1223
+ constexpr unordered_set(from_range_t, R&& rg, size_type n, const allocator_type& a)
1224
  : unordered_set(from_range, std::forward<R>(rg), n, hasher(), key_equal(), a) { }
1225
  template<container-compatible-range<value_type> R>
1226
+ constexpr unordered_set(from_range_t, R&& rg, size_type n, const hasher& hf,
1227
+ const allocator_type& a)
1228
  : unordered_set(from_range, std::forward<R>(rg), n, hf, key_equal(), a) { }
1229
+ constexpr unordered_set(initializer_list<value_type> il, size_type n, const hasher& hf,
1230
  const allocator_type& a)
1231
  : unordered_set(il, n, hf, key_equal(), a) { }
1232
+ constexpr ~unordered_set();
1233
+ constexpr unordered_set& operator=(const unordered_set&);
1234
+ constexpr unordered_set& operator=(unordered_set&&)
1235
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
1236
+ is_nothrow_move_assignable_v<Hash> && is_nothrow_move_assignable_v<Pred>);
1237
+ constexpr unordered_set& operator=(initializer_list<value_type>);
1238
+ constexpr allocator_type get_allocator() const noexcept;
 
1239
 
1240
  // iterators
1241
+ constexpr iterator begin() noexcept;
1242
+ constexpr const_iterator begin() const noexcept;
1243
+ constexpr iterator end() noexcept;
1244
+ constexpr const_iterator end() const noexcept;
1245
+ constexpr const_iterator cbegin() const noexcept;
1246
+ constexpr const_iterator cend() const noexcept;
1247
 
1248
  // capacity
1249
+ constexpr bool empty() const noexcept;
1250
+ constexpr size_type size() const noexcept;
1251
+ constexpr size_type max_size() const noexcept;
1252
 
1253
+ // [unord.set.modifiers], modifiers
1254
+ template<class... Args> constexpr pair<iterator, bool> emplace(Args&&... args);
1255
+ template<class... Args>
1256
+ constexpr iterator emplace_hint(const_iterator position, Args&&... args);
1257
+ constexpr pair<iterator, bool> insert(const value_type& obj);
1258
+ constexpr pair<iterator, bool> insert(value_type&& obj);
1259
+ template<class K> constexpr pair<iterator, bool> insert(K&& obj);
1260
+ constexpr iterator insert(const_iterator hint, const value_type& obj);
1261
+ constexpr iterator insert(const_iterator hint, value_type&& obj);
1262
+ template<class K> constexpr iterator insert(const_iterator hint, K&& obj);
1263
+ template<class InputIterator> constexpr void insert(InputIterator first, InputIterator last);
1264
  template<container-compatible-range<value_type> R>
1265
+ constexpr void insert_range(R&& rg);
1266
+ constexpr void insert(initializer_list<value_type>);
1267
 
1268
+ constexpr node_type extract(const_iterator position);
1269
+ constexpr node_type extract(const key_type& x);
1270
+ template<class K> constexpr node_type extract(K&& x);
1271
+ constexpr insert_return_type insert(node_type&& nh);
1272
+ constexpr iterator insert(const_iterator hint, node_type&& nh);
1273
 
1274
+ constexpr iterator erase(iterator position)
1275
  requires (!same_as<iterator, const_iterator>);
1276
+ constexpr iterator erase(const_iterator position);
1277
+ constexpr size_type erase(const key_type& k);
1278
+ template<class K> constexpr size_type erase(K&& x);
1279
+ constexpr iterator erase(const_iterator first, const_iterator last);
1280
+ constexpr void swap(unordered_set&)
1281
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
1282
+ is_nothrow_swappable_v<Hash> && is_nothrow_swappable_v<Pred>);
1283
+ constexpr void clear() noexcept;
 
1284
 
1285
  template<class H2, class P2>
1286
+ constexpr void merge(unordered_set<Key, H2, P2, Allocator>& source);
1287
  template<class H2, class P2>
1288
+ constexpr void merge(unordered_set<Key, H2, P2, Allocator>&& source);
1289
  template<class H2, class P2>
1290
+ constexpr void merge(unordered_multiset<Key, H2, P2, Allocator>& source);
1291
  template<class H2, class P2>
1292
+ constexpr void merge(unordered_multiset<Key, H2, P2, Allocator>&& source);
1293
 
1294
  // observers
1295
+ constexpr hasher hash_function() const;
1296
+ constexpr key_equal key_eq() const;
1297
 
1298
  // set operations
1299
+ constexpr iterator find(const key_type& k);
1300
+ constexpr const_iterator find(const key_type& k) const;
1301
  template<class K>
1302
+ constexpr iterator find(const K& k);
1303
  template<class K>
1304
+ constexpr const_iterator find(const K& k) const;
1305
+ constexpr size_type count(const key_type& k) const;
1306
  template<class K>
1307
+ constexpr size_type count(const K& k) const;
1308
+ constexpr bool contains(const key_type& k) const;
1309
  template<class K>
1310
+ constexpr bool contains(const K& k) const;
1311
+ constexpr pair<iterator, iterator> equal_range(const key_type& k);
1312
+ constexpr pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
1313
  template<class K>
1314
+ constexpr pair<iterator, iterator> equal_range(const K& k);
1315
  template<class K>
1316
+ constexpr pair<const_iterator, const_iterator> equal_range(const K& k) const;
1317
 
1318
  // bucket interface
1319
+ constexpr size_type bucket_count() const noexcept;
1320
+ constexpr size_type max_bucket_count() const noexcept;
1321
+ constexpr size_type bucket_size(size_type n) const;
1322
+ constexpr size_type bucket(const key_type& k) const;
1323
+ template<class K> constexpr size_type bucket(const K& k) const;
1324
+ constexpr local_iterator begin(size_type n);
1325
+ constexpr const_local_iterator begin(size_type n) const;
1326
+ constexpr local_iterator end(size_type n);
1327
+ constexpr const_local_iterator end(size_type n) const;
1328
+ constexpr const_local_iterator cbegin(size_type n) const;
1329
+ constexpr const_local_iterator cend(size_type n) const;
1330
 
1331
  // hash policy
1332
+ constexpr float load_factor() const noexcept;
1333
+ constexpr float max_load_factor() const noexcept;
1334
+ constexpr void max_load_factor(float z);
1335
+ constexpr void rehash(size_type n);
1336
+ constexpr void reserve(size_type n);
1337
  };
1338
 
1339
  template<class InputIterator,
1340
  class Hash = hash<iter-value-type<InputIterator>>,
1341
  class Pred = equal_to<iter-value-type<InputIterator>>,
 
1403
  deduction guide.
1404
 
1405
  #### Constructors <a id="unord.set.cnstr">[[unord.set.cnstr]]</a>
1406
 
1407
  ``` cpp
1408
+ constexpr unordered_set() : unordered_set(size_type(see below)) { }
1409
+ constexpr explicit unordered_set(size_type n, const hasher& hf = hasher(),
 
1410
  const key_equal& eql = key_equal(),
1411
  const allocator_type& a = allocator_type());
1412
  ```
1413
 
1414
  *Effects:* Constructs an empty `unordered_set` using the specified hash
 
1418
 
1419
  *Complexity:* Constant.
1420
 
1421
  ``` cpp
1422
  template<class InputIterator>
1423
+ constexpr unordered_set(InputIterator f, InputIterator l,
1424
+ size_type n = see below, const hasher& hf = hasher(),
 
1425
  const key_equal& eql = key_equal(),
1426
  const allocator_type& a = allocator_type());
1427
  template<container-compatible-range<value_type> R>
1428
+ constexpr unordered_multiset(from_range_t, R&& rg,
1429
+ size_type n = see below, const hasher& hf = hasher(),
 
1430
  const key_equal& eql = key_equal(),
1431
  const allocator_type& a = allocator_type());
1432
+ constexpr unordered_set(initializer_list<value_type> il,
1433
+ size_type n = see below, const hasher& hf = hasher(),
 
1434
  const key_equal& eql = key_equal(),
1435
  const allocator_type& a = allocator_type());
1436
  ```
1437
 
1438
  *Effects:* Constructs an empty `unordered_set` using the specified hash
 
1445
 
1446
  #### Erasure <a id="unord.set.erasure">[[unord.set.erasure]]</a>
1447
 
1448
  ``` cpp
1449
  template<class K, class H, class P, class A, class Predicate>
1450
+ constexpr typename unordered_set<K, H, P, A>::size_type
1451
  erase_if(unordered_set<K, H, P, A>& c, Predicate pred);
1452
  ```
1453
 
1454
  *Effects:* Equivalent to:
1455
 
 
1463
  }
1464
  }
1465
  return original_size - c.size();
1466
  ```
1467
 
1468
+ #### Modifiers <a id="unord.set.modifiers">[[unord.set.modifiers]]</a>
1469
+
1470
+ ``` cpp
1471
+ template<class K> constexpr pair<iterator, bool> insert(K&& obj);
1472
+ template<class K> constexpr iterator insert(const_iterator hint, K&& obj);
1473
+ ```
1474
+
1475
+ *Constraints:* The *qualified-id*s `Hash::is_transparent` and
1476
+ `Pred::is_transparent` are valid and denote types. For the second
1477
+ overload, `is_convertible_v<K&&, const_iterator>` and
1478
+ `is_convertible_v<K&&, iterator>` are both `false`.
1479
+
1480
+ *Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into
1481
+ `unordered_set` from `std::forward<K> (obj)`.
1482
+
1483
+ *Effects:* If the set already contains an element that is equivalent to
1484
+ `obj`, there is no effect. Otherwise, let `h` be `hash_function()(obj)`.
1485
+ Constructs an object `u` of type `value_type` with
1486
+ `std::forward<K>(obj)`. If `hash_function()(u) != h || contains(u)` is
1487
+ `true`, the behavior is undefined. Inserts `u` into `*this`.
1488
+
1489
+ *Returns:* For the first overload, the `bool` component of the returned
1490
+ pair is `true` if and only if the insertion took place. The returned
1491
+ iterator points to the set element that is equivalent to `obj`.
1492
+
1493
+ *Complexity:* Average case constant, worst case linear.
1494
+
1495
  ### Class template `unordered_multiset` <a id="unord.multiset">[[unord.multiset]]</a>
1496
 
1497
  #### Overview <a id="unord.multiset.overview">[[unord.multiset.overview]]</a>
1498
 
1499
  An `unordered_multiset` is an unordered associative container that
 
1515
 
1516
  Subclause  [[unord.multiset]] only describes operations on
1517
  `unordered_multiset` that are not described in one of the requirement
1518
  tables, or for which there is additional semantic information.
1519
 
1520
+ The types `iterator` and `const_iterator` meet the constexpr iterator
1521
+ requirements [[iterator.requirements.general]].
1522
+
1523
  ``` cpp
1524
  namespace std {
1525
  template<class Key,
1526
  class Hash = hash<Key>,
1527
  class Pred = equal_to<Key>,
 
1532
  using key_type = Key;
1533
  using value_type = Key;
1534
  using hasher = Hash;
1535
  using key_equal = Pred;
1536
  using allocator_type = Allocator;
1537
+ using pointer = allocator_traits<Allocator>::pointer;
1538
+ using const_pointer = allocator_traits<Allocator>::const_pointer;
1539
  using reference = value_type&;
1540
  using const_reference = const value_type&;
1541
  using size_type = implementation-defined // type of unordered_multiset::size_type; // see [container.requirements]
1542
  using difference_type = implementation-defined // type of unordered_multiset::difference_type; // see [container.requirements]
1543
 
 
1546
  using local_iterator = implementation-defined // type of unordered_multiset::local_iterator; // see [container.requirements]
1547
  using const_local_iterator = implementation-defined // type of unordered_multiset::const_local_iterator; // see [container.requirements]
1548
  using node_type = unspecified;
1549
 
1550
  // [unord.multiset.cnstr], construct/copy/destroy
1551
+ constexpr unordered_multiset();
1552
+ constexpr explicit unordered_multiset(size_type n, const hasher& hf = hasher(),
 
1553
  const key_equal& eql = key_equal(),
1554
  const allocator_type& a = allocator_type());
1555
  template<class InputIterator>
1556
+ constexpr unordered_multiset(InputIterator f, InputIterator l,
1557
+ size_type n = see below, const hasher& hf = hasher(),
 
1558
  const key_equal& eql = key_equal(),
1559
  const allocator_type& a = allocator_type());
1560
  template<container-compatible-range<value_type> R>
1561
+ constexpr unordered_multiset(from_range_t, R&& rg,
1562
+ size_type n = see below, const hasher& hf = hasher(),
 
1563
  const key_equal& eql = key_equal(),
1564
  const allocator_type& a = allocator_type());
1565
+ constexpr unordered_multiset(const unordered_multiset&);
1566
+ constexpr unordered_multiset(unordered_multiset&&);
1567
+ constexpr explicit unordered_multiset(const Allocator&);
1568
+ constexpr unordered_multiset(const unordered_multiset&, const type_identity_t<Allocator>&);
1569
+ constexpr unordered_multiset(unordered_multiset&&, const type_identity_t<Allocator>&);
1570
+ constexpr unordered_multiset(initializer_list<value_type> il,
1571
+ size_type n = see below, const hasher& hf = hasher(),
 
1572
  const key_equal& eql = key_equal(),
1573
  const allocator_type& a = allocator_type());
1574
+ constexpr unordered_multiset(size_type n, const allocator_type& a)
1575
  : unordered_multiset(n, hasher(), key_equal(), a) { }
1576
+ constexpr unordered_multiset(size_type n, const hasher& hf, const allocator_type& a)
1577
  : unordered_multiset(n, hf, key_equal(), a) { }
1578
  template<class InputIterator>
1579
+ constexpr unordered_multiset(InputIterator f, InputIterator l, size_type n,
1580
+ const allocator_type& a)
1581
  : unordered_multiset(f, l, n, hasher(), key_equal(), a) { }
1582
  template<class InputIterator>
1583
+ constexpr unordered_multiset(InputIterator f, InputIterator l, size_type n,
1584
+ const hasher& hf, const allocator_type& a)
1585
  : unordered_multiset(f, l, n, hf, key_equal(), a) { }
1586
  template<container-compatible-range<value_type> R>
1587
+ constexpr unordered_multiset(from_range_t, R&& rg, size_type n, const allocator_type& a)
1588
  : unordered_multiset(from_range, std::forward<R>(rg),
1589
  n, hasher(), key_equal(), a) { }
1590
  template<container-compatible-range<value_type> R>
1591
+ constexpr unordered_multiset(from_range_t, R&& rg, size_type n, const hasher& hf,
1592
  const allocator_type& a)
1593
  : unordered_multiset(from_range, std::forward<R>(rg), n, hf, key_equal(), a) { }
1594
+ constexpr unordered_multiset(initializer_list<value_type> il, size_type n,
1595
+ const allocator_type& a)
1596
  : unordered_multiset(il, n, hasher(), key_equal(), a) { }
1597
+ constexpr unordered_multiset(initializer_list<value_type> il, size_type n, const hasher& hf,
1598
  const allocator_type& a)
1599
  : unordered_multiset(il, n, hf, key_equal(), a) { }
1600
+ constexpr ~unordered_multiset();
1601
+ constexpr unordered_multiset& operator=(const unordered_multiset&);
1602
+ constexpr unordered_multiset& operator=(unordered_multiset&&)
1603
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
1604
+ is_nothrow_move_assignable_v<Hash> && is_nothrow_move_assignable_v<Pred>);
1605
+ constexpr unordered_multiset& operator=(initializer_list<value_type>);
1606
+ constexpr allocator_type get_allocator() const noexcept;
 
1607
 
1608
  // iterators
1609
+ constexpr iterator begin() noexcept;
1610
+ constexpr const_iterator begin() const noexcept;
1611
+ constexpr iterator end() noexcept;
1612
+ constexpr const_iterator end() const noexcept;
1613
+ constexpr const_iterator cbegin() const noexcept;
1614
+ constexpr const_iterator cend() const noexcept;
1615
 
1616
  // capacity
1617
+ constexpr bool empty() const noexcept;
1618
+ constexpr size_type size() const noexcept;
1619
+ constexpr size_type max_size() const noexcept;
1620
 
1621
  // modifiers
1622
+ template<class... Args> constexpr iterator emplace(Args&&... args);
1623
+ template<class... Args>
1624
+ constexpr iterator emplace_hint(const_iterator position, Args&&... args);
1625
+ constexpr iterator insert(const value_type& obj);
1626
+ constexpr iterator insert(value_type&& obj);
1627
+ constexpr iterator insert(const_iterator hint, const value_type& obj);
1628
+ constexpr iterator insert(const_iterator hint, value_type&& obj);
1629
+ template<class InputIterator> constexpr void insert(InputIterator first, InputIterator last);
1630
  template<container-compatible-range<value_type> R>
1631
+ constexpr void insert_range(R&& rg);
1632
+ constexpr void insert(initializer_list<value_type>);
1633
 
1634
+ constexpr node_type extract(const_iterator position);
1635
+ constexpr node_type extract(const key_type& x);
1636
+ template<class K> constexpr node_type extract(K&& x);
1637
+ constexpr iterator insert(node_type&& nh);
1638
+ constexpr iterator insert(const_iterator hint, node_type&& nh);
1639
 
1640
+ constexpr iterator erase(iterator position)
1641
  requires (!same_as<iterator, const_iterator>);
1642
+ constexpr iterator erase(const_iterator position);
1643
+ constexpr size_type erase(const key_type& k);
1644
+ template<class K> constexpr size_type erase(K&& x);
1645
+ constexpr iterator erase(const_iterator first, const_iterator last);
1646
+ constexpr void swap(unordered_multiset&)
1647
  noexcept(allocator_traits<Allocator>::is_always_equal::value &&
1648
+ is_nothrow_swappable_v<Hash> && is_nothrow_swappable_v<Pred>);
1649
+ constexpr void clear() noexcept;
 
1650
 
1651
  template<class H2, class P2>
1652
+ constexpr void merge(unordered_multiset<Key, H2, P2, Allocator>& source);
1653
  template<class H2, class P2>
1654
+ constexpr void merge(unordered_multiset<Key, H2, P2, Allocator>&& source);
1655
  template<class H2, class P2>
1656
+ constexpr void merge(unordered_set<Key, H2, P2, Allocator>& source);
1657
  template<class H2, class P2>
1658
+ constexpr void merge(unordered_set<Key, H2, P2, Allocator>&& source);
1659
 
1660
  // observers
1661
+ constexpr hasher hash_function() const;
1662
+ constexpr key_equal key_eq() const;
1663
 
1664
  // set operations
1665
+ constexpr iterator find(const key_type& k);
1666
+ constexpr const_iterator find(const key_type& k) const;
1667
  template<class K>
1668
+ constexpr iterator find(const K& k);
1669
  template<class K>
1670
+ constexpr const_iterator find(const K& k) const;
1671
+ constexpr size_type count(const key_type& k) const;
1672
  template<class K>
1673
+ constexpr size_type count(const K& k) const;
1674
+ constexpr bool contains(const key_type& k) const;
1675
  template<class K>
1676
+ constexpr bool contains(const K& k) const;
1677
+ constexpr pair<iterator, iterator> equal_range(const key_type& k);
1678
+ constexpr pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
1679
  template<class K>
1680
+ constexpr pair<iterator, iterator> equal_range(const K& k);
1681
  template<class K>
1682
+ constexpr pair<const_iterator, const_iterator> equal_range(const K& k) const;
1683
 
1684
  // bucket interface
1685
+ constexpr size_type bucket_count() const noexcept;
1686
+ constexpr size_type max_bucket_count() const noexcept;
1687
+ constexpr size_type bucket_size(size_type n) const;
1688
+ constexpr size_type bucket(const key_type& k) const;
1689
+ template<class K> constexpr size_type bucket(const K& k) const;
1690
+ constexpr local_iterator begin(size_type n);
1691
+ constexpr const_local_iterator begin(size_type n) const;
1692
+ constexpr local_iterator end(size_type n);
1693
+ constexpr const_local_iterator end(size_type n) const;
1694
+ constexpr const_local_iterator cbegin(size_type n) const;
1695
+ constexpr const_local_iterator cend(size_type n) const;
1696
 
1697
  // hash policy
1698
+ constexpr float load_factor() const noexcept;
1699
+ constexpr float max_load_factor() const noexcept;
1700
+ constexpr void max_load_factor(float z);
1701
+ constexpr void rehash(size_type n);
1702
+ constexpr void reserve(size_type n);
1703
  };
1704
 
1705
  template<class InputIterator,
1706
  class Hash = hash<iter-value-type<InputIterator>>,
1707
  class Pred = equal_to<iter-value-type<InputIterator>>,
1708
  class Allocator = allocator<iter-value-type<InputIterator>>>
1709
+ unordered_multiset(InputIterator, InputIterator, typename see below::size_type = see below,
1710
  Hash = Hash(), Pred = Pred(), Allocator = Allocator())
1711
  -> unordered_multiset<iter-value-type<InputIterator>,
1712
  Hash, Pred, Allocator>;
1713
 
1714
  template<ranges::input_range R,
 
1769
  deduction guide.
1770
 
1771
  #### Constructors <a id="unord.multiset.cnstr">[[unord.multiset.cnstr]]</a>
1772
 
1773
  ``` cpp
1774
+ constexpr unordered_multiset() : unordered_multiset(size_type(see below)) { }
1775
+ constexpr explicit unordered_multiset(size_type n, const hasher& hf = hasher(),
 
1776
  const key_equal& eql = key_equal(),
1777
  const allocator_type& a = allocator_type());
1778
  ```
1779
 
1780
  *Effects:* Constructs an empty `unordered_multiset` using the specified
 
1784
 
1785
  *Complexity:* Constant.
1786
 
1787
  ``` cpp
1788
  template<class InputIterator>
1789
+ constexpr unordered_multiset(InputIterator f, InputIterator l,
1790
+ size_type n = see below, const hasher& hf = hasher(),
 
1791
  const key_equal& eql = key_equal(),
1792
  const allocator_type& a = allocator_type());
1793
  template<container-compatible-range<value_type> R>
1794
+ constexpr unordered_multiset(from_range_t, R&& rg,
1795
+ size_type n = see below, const hasher& hf = hasher(),
 
1796
  const key_equal& eql = key_equal(),
1797
  const allocator_type& a = allocator_type());
1798
+ constexpr unordered_multiset(initializer_list<value_type> il,
1799
+ size_type n = see below, const hasher& hf = hasher(),
 
1800
  const key_equal& eql = key_equal(),
1801
  const allocator_type& a = allocator_type());
1802
  ```
1803
 
1804
  *Effects:* Constructs an empty `unordered_multiset` using the specified
 
1811
 
1812
  #### Erasure <a id="unord.multiset.erasure">[[unord.multiset.erasure]]</a>
1813
 
1814
  ``` cpp
1815
  template<class K, class H, class P, class A, class Predicate>
1816
+ constexpr typename unordered_multiset<K, H, P, A>::size_type
1817
  erase_if(unordered_multiset<K, H, P, A>& c, Predicate pred);
1818
  ```
1819
 
1820
  *Effects:* Equivalent to:
1821