From Jason Turner

[unord]

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

Diff to HTML by rtfpessoa

Files changed (1) hide show
  1. tmp/tmppk3mxk2t/{from.md → to.md} +329 -253
tmp/tmppk3mxk2t/{from.md → to.md} RENAMED
@@ -4,18 +4,20 @@
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
 
9
- The exposition-only alias templates `iter_key_t`, `iter_val_t`, and
10
- `iter_to_alloc_t` defined in [[associative.general]] may appear in
11
- deduction guides for unordered containers.
 
12
 
13
  ### Header `<unordered_map>` synopsis <a id="unord.map.syn">[[unord.map.syn]]</a>
14
 
15
  ``` cpp
16
- #include <initializer_list>
 
17
 
18
  namespace std {
19
  // [unord.map], class template unordered_map
20
  template<class Key,
21
  class T,
@@ -30,32 +32,35 @@ namespace std {
30
  class Hash = hash<Key>,
31
  class Pred = equal_to<Key>,
32
  class Alloc = allocator<pair<const Key, T>>>
33
  class unordered_multimap;
34
 
 
 
 
 
 
 
 
 
35
  template<class Key, class T, class Hash, class Pred, class Alloc>
36
  void swap(unordered_map<Key, T, Hash, Pred, Alloc>& x,
37
  unordered_map<Key, T, Hash, Pred, Alloc>& y)
38
  noexcept(noexcept(x.swap(y)));
39
 
40
  template<class Key, class T, class Hash, class Pred, class Alloc>
41
  void swap(unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
42
  unordered_multimap<Key, T, Hash, Pred, Alloc>& y)
43
  noexcept(noexcept(x.swap(y)));
44
 
45
- template <class Key, class T, class Hash, class Pred, class Alloc>
46
- bool operator==(const unordered_map<Key, T, Hash, Pred, Alloc>& a,
47
- const unordered_map<Key, T, Hash, Pred, Alloc>& b);
48
- template <class Key, class T, class Hash, class Pred, class Alloc>
49
- bool operator!=(const unordered_map<Key, T, Hash, Pred, Alloc>& a,
50
- const unordered_map<Key, T, Hash, Pred, Alloc>& b);
51
- template <class Key, class T, class Hash, class Pred, class Alloc>
52
- bool operator==(const unordered_multimap<Key, T, Hash, Pred, Alloc>& a,
53
- const unordered_multimap<Key, T, Hash, Pred, Alloc>& b);
54
- template <class Key, class T, class Hash, class Pred, class Alloc>
55
- bool operator!=(const unordered_multimap<Key, T, Hash, Pred, Alloc>& a,
56
- const unordered_multimap<Key, T, Hash, Pred, Alloc>& b);
57
 
58
  namespace pmr {
59
  template<class Key,
60
  class T,
61
  class Hash = hash<Key>,
@@ -76,11 +81,12 @@ namespace std {
76
  ```
77
 
78
  ### Header `<unordered_set>` synopsis <a id="unord.set.syn">[[unord.set.syn]]</a>
79
 
80
  ``` cpp
81
- #include <initializer_list>
 
82
 
83
  namespace std {
84
  // [unord.set], class template unordered_set
85
  template<class Key,
86
  class Hash = hash<Key>,
@@ -93,32 +99,35 @@ namespace std {
93
  class Hash = hash<Key>,
94
  class Pred = equal_to<Key>,
95
  class Alloc = allocator<Key>>
96
  class unordered_multiset;
97
 
 
 
 
 
 
 
 
 
98
  template<class Key, class Hash, class Pred, class Alloc>
99
  void swap(unordered_set<Key, Hash, Pred, Alloc>& x,
100
  unordered_set<Key, Hash, Pred, Alloc>& y)
101
  noexcept(noexcept(x.swap(y)));
102
 
103
  template<class Key, class Hash, class Pred, class Alloc>
104
  void swap(unordered_multiset<Key, Hash, Pred, Alloc>& x,
105
  unordered_multiset<Key, Hash, Pred, Alloc>& y)
106
  noexcept(noexcept(x.swap(y)));
107
 
108
- template <class Key, class Hash, class Pred, class Alloc>
109
- bool operator==(const unordered_set<Key, Hash, Pred, Alloc>& a,
110
- const unordered_set<Key, Hash, Pred, Alloc>& b);
111
- template <class Key, class Hash, class Pred, class Alloc>
112
- bool operator!=(const unordered_set<Key, Hash, Pred, Alloc>& a,
113
- const unordered_set<Key, Hash, Pred, Alloc>& b);
114
- template <class Key, class Hash, class Pred, class Alloc>
115
- bool operator==(const unordered_multiset<Key, Hash, Pred, Alloc>& a,
116
- const unordered_multiset<Key, Hash, Pred, Alloc>& b);
117
- template <class Key, class Hash, class Pred, class Alloc>
118
- bool operator!=(const unordered_multiset<Key, Hash, Pred, Alloc>& a,
119
- const unordered_multiset<Key, Hash, Pred, Alloc>& b);
120
 
121
  namespace pmr {
122
  template<class Key,
123
  class Hash = hash<Key>,
124
  class Pred = equal_to<Key>>
@@ -134,40 +143,40 @@ namespace std {
134
  }
135
  ```
136
 
137
  ### Class template `unordered_map` <a id="unord.map">[[unord.map]]</a>
138
 
139
- #### Class template `unordered_map` overview <a id="unord.map.overview">[[unord.map.overview]]</a>
140
 
141
  An `unordered_map` is an unordered associative container that supports
142
  unique keys (an `unordered_map` contains at most one of each key value)
143
  and that associates values of another type `mapped_type` with the keys.
144
  The `unordered_map` class supports forward iterators.
145
 
146
- An `unordered_map` satisfies all of the requirements of a container, of
147
- an unordered associative container, and of an allocator-aware container
148
- (Table  [[tab:containers.allocatoraware]]). It provides the operations
149
- described in the preceding requirements table for unique keys; that is,
150
- an `unordered_map` supports the `a_uniq` operations in that table, not
151
- the `a_eq` operations. For an `unordered_map<Key, T>` the `key type` is
152
  `Key`, the mapped type is `T`, and the value type is
153
  `pair<const Key, T>`.
154
 
155
- This section only describes operations on `unordered_map` that are not
156
- described in one of the requirement tables, or for which there is
157
- additional semantic information.
158
 
159
  ``` cpp
160
  namespace std {
161
  template<class Key,
162
  class T,
163
  class Hash = hash<Key>,
164
  class Pred = equal_to<Key>,
165
  class Allocator = allocator<pair<const Key, T>>>
166
  class unordered_map {
167
  public:
168
- // types:
169
  using key_type = Key;
170
  using mapped_type = T;
171
  using value_type = pair<const Key, T>;
172
  using hasher = Hash;
173
  using key_equal = Pred;
@@ -182,11 +191,11 @@ namespace std {
182
  using iterator = implementation-defined // type of unordered_map::iterator; // see [container.requirements]
183
  using const_iterator = implementation-defined // type of unordered_map::const_iterator; // see [container.requirements]
184
  using local_iterator = implementation-defined // type of unordered_map::local_iterator; // see [container.requirements]
185
  using const_local_iterator = implementation-defined // type of unordered_map::const_local_iterator; // see [container.requirements]
186
  using node_type = unspecified;
187
- using insert_return_type = INSERT_RETURN_TYPE<iterator, node_type>;
188
 
189
  // [unord.map.cnstr], construct/copy/destroy
190
  unordered_map();
191
  explicit unordered_map(size_type n,
192
  const hasher& hf = hasher(),
@@ -231,20 +240,20 @@ namespace std {
231
  is_nothrow_move_assignable_v<Hash> &&
232
  is_nothrow_move_assignable_v<Pred>);
233
  unordered_map& operator=(initializer_list<value_type>);
234
  allocator_type get_allocator() const noexcept;
235
 
236
- // iterators:
237
  iterator begin() noexcept;
238
  const_iterator begin() const noexcept;
239
  iterator end() noexcept;
240
  const_iterator end() const noexcept;
241
  const_iterator cbegin() const noexcept;
242
  const_iterator cend() const noexcept;
243
 
244
- // capacity:
245
- bool empty() const noexcept;
246
  size_type size() const noexcept;
247
  size_type max_size() const noexcept;
248
 
249
  // [unord.map.modifiers], modifiers
250
  template<class... Args> pair<iterator, bool> emplace(Args&&... args);
@@ -297,28 +306,42 @@ namespace std {
297
  template<class H2, class P2>
298
  void merge(unordered_multimap<Key, T, H2, P2, Allocator>& source);
299
  template<class H2, class P2>
300
  void merge(unordered_multimap<Key, T, H2, P2, Allocator>&& source);
301
 
302
- // observers:
303
  hasher hash_function() const;
304
  key_equal key_eq() const;
305
 
306
- // map operations:
307
  iterator find(const key_type& k);
308
  const_iterator find(const key_type& k) const;
 
 
 
 
 
309
  size_type count(const key_type& k) const;
 
 
 
 
 
310
  pair<iterator, iterator> equal_range(const key_type& k);
311
  pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
 
 
 
 
312
 
313
  // [unord.map.elem], element access
314
  mapped_type& operator[](const key_type& k);
315
  mapped_type& operator[](key_type&& k);
316
  mapped_type& at(const key_type& k);
317
  const mapped_type& at(const key_type& k) const;
318
 
319
- // bucket interface:
320
  size_type bucket_count() const noexcept;
321
  size_type max_bucket_count() const noexcept;
322
  size_type bucket_size(size_type n) const;
323
  size_type bucket(const key_type& k) const;
324
  local_iterator begin(size_type n);
@@ -326,73 +349,66 @@ namespace std {
326
  local_iterator end(size_type n);
327
  const_local_iterator end(size_type n) const;
328
  const_local_iterator cbegin(size_type n) const;
329
  const_local_iterator cend(size_type n) const;
330
 
331
- // hash policy:
332
  float load_factor() const noexcept;
333
  float max_load_factor() const noexcept;
334
  void max_load_factor(float z);
335
  void rehash(size_type n);
336
  void reserve(size_type n);
337
  };
338
 
339
  template<class InputIterator,
340
- class Hash = hash<iter_key_t<InputIterator>>,
341
- class Pred = equal_to<iter_key_t<InputIterator>>,
342
- class Allocator = allocator<iter_to_alloc_t<InputIterator>>>
343
  unordered_map(InputIterator, InputIterator, typename see below::size_type = see below,
344
  Hash = Hash(), Pred = Pred(), Allocator = Allocator())
345
- -> unordered_map<iter_key_t<InputIterator>, iter_value_t<InputIterator>, Hash, Pred,
346
  Allocator>;
347
 
348
  template<class Key, class T, class Hash = hash<Key>,
349
  class Pred = equal_to<Key>, class Allocator = allocator<pair<const Key, T>>>
350
- unordered_map(initializer_list<pair<const Key, T>>,
351
  typename see below::size_type = see below, Hash = Hash(),
352
  Pred = Pred(), Allocator = Allocator())
353
  -> unordered_map<Key, T, Hash, Pred, Allocator>;
354
 
355
  template<class InputIterator, class Allocator>
356
  unordered_map(InputIterator, InputIterator, typename see below::size_type, Allocator)
357
- -> unordered_map<iter_key_t<InputIterator>, iter_val_t<InputIterator>,
358
- hash<iter_key_t<InputIterator>>, equal_to<iter_key_t<InputIterator>>,
359
- Allocator>;
360
 
361
  template<class InputIterator, class Allocator>
362
  unordered_map(InputIterator, InputIterator, Allocator)
363
- -> unordered_map<iter_key_t<InputIterator>, iter_val_t<InputIterator>,
364
- hash<iter_key_t<InputIterator>>, equal_to<iter_key_t<InputIterator>>,
365
- Allocator>;
366
 
367
  template<class InputIterator, class Hash, class Allocator>
368
  unordered_map(InputIterator, InputIterator, typename see below::size_type, Hash, Allocator)
369
- -> unordered_map<iter_key_t<InputIterator>, iter_val_t<InputIterator>, Hash,
370
- equal_to<iter_key_t<InputIterator>>, Allocator>;
371
 
372
- template<class Key, class T, typename Allocator>
373
- unordered_map(initializer_list<pair<const Key, T>>, typename see below::size_type,
374
  Allocator)
375
  -> unordered_map<Key, T, hash<Key>, equal_to<Key>, Allocator>;
376
 
377
- template<class Key, class T, typename Allocator>
378
- unordered_map(initializer_list<pair<const Key, T>>, Allocator)
379
  -> unordered_map<Key, T, hash<Key>, equal_to<Key>, Allocator>;
380
 
381
  template<class Key, class T, class Hash, class Allocator>
382
- unordered_map(initializer_list<pair<const Key, T>>, typename see below::size_type, Hash,
383
  Allocator)
384
  -> unordered_map<Key, T, Hash, equal_to<Key>, Allocator>;
385
 
386
- template <class Key, class T, class Hash, class Pred, class Alloc>
387
- bool operator==(const unordered_map<Key, T, Hash, Pred, Alloc>& a,
388
- const unordered_map<Key, T, Hash, Pred, Alloc>& b);
389
- template <class Key, class T, class Hash, class Pred, class Alloc>
390
- bool operator!=(const unordered_map<Key, T, Hash, Pred, Alloc>& a,
391
- const unordered_map<Key, T, Hash, Pred, Alloc>& b);
392
-
393
- // [unord.map.swap], swap
394
  template<class Key, class T, class Hash, class Pred, class Alloc>
395
  void swap(unordered_map<Key, T, Hash, Pred, Alloc>& x,
396
  unordered_map<Key, T, Hash, Pred, Alloc>& y)
397
  noexcept(noexcept(x.swap(y)));
398
  }
@@ -400,11 +416,11 @@ namespace std {
400
 
401
  A `size_type` parameter type in an `unordered_map` deduction guide
402
  refers to the `size_type` member type of the type deduced by the
403
  deduction guide.
404
 
405
- #### `unordered_map` constructors <a id="unord.map.cnstr">[[unord.map.cnstr]]</a>
406
 
407
  ``` cpp
408
  unordered_map() : unordered_map(size_type(see below)) { }
409
  explicit unordered_map(size_type n,
410
  const hasher& hf = hasher(),
@@ -440,11 +456,11 @@ buckets. If `n` is not provided, the number of buckets is
440
  `l`) for the first form, or from the range \[`il.begin()`, `il.end()`)
441
  for the second form. `max_load_factor()` returns `1.0`.
442
 
443
  *Complexity:* Average case linear, worst case quadratic.
444
 
445
- #### `unordered_map` element access <a id="unord.map.elem">[[unord.map.elem]]</a>
446
 
447
  ``` cpp
448
  mapped_type& operator[](const key_type& k);
449
  ```
450
 
@@ -465,41 +481,39 @@ const mapped_type& at(const key_type& k) const;
465
  whose key is equivalent to `k`.
466
 
467
  *Throws:* An exception object of type `out_of_range` if no such element
468
  is present.
469
 
470
- #### `unordered_map` modifiers <a id="unord.map.modifiers">[[unord.map.modifiers]]</a>
471
 
472
  ``` cpp
473
  template<class P>
474
  pair<iterator, bool> insert(P&& obj);
475
  ```
476
 
 
 
477
  *Effects:* Equivalent to: `return emplace(std::forward<P>(obj));`
478
 
479
- *Remarks:* This signature shall not participate in overload resolution
480
- unless `is_constructible_v<value_type, P&&>` is `true`.
481
-
482
  ``` cpp
483
  template<class P>
484
  iterator insert(const_iterator hint, P&& obj);
485
  ```
486
 
 
 
487
  *Effects:* Equivalent to:
488
  `return emplace_hint(hint, std::forward<P>(obj));`
489
 
490
- *Remarks:* This signature shall not participate in overload resolution
491
- unless `is_constructible_v<value_type, P&&>` is `true`.
492
-
493
  ``` cpp
494
  template<class... Args>
495
  pair<iterator, bool> try_emplace(const key_type& k, Args&&... args);
496
  template<class... Args>
497
  iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args);
498
  ```
499
 
500
- *Requires:* `value_type` shall be `EmplaceConstructible` into
501
  `unordered_map` from `piecewise_construct`, `forward_as_tuple(k)`,
502
  `forward_as_tuple(std::forward<Args>(args)...)`.
503
 
504
  *Effects:* If the map already contains an element whose key is
505
  equivalent to `k`, there is no effect. Otherwise inserts an object of
@@ -517,11 +531,11 @@ template <class... Args>
517
  pair<iterator, bool> try_emplace(key_type&& k, Args&&... args);
518
  template<class... Args>
519
  iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args);
520
  ```
521
 
522
- *Requires:* `value_type` shall be `EmplaceConstructible` into
523
  `unordered_map` from `piecewise_construct`,
524
  `forward_as_tuple(std::move(k))`,
525
  `forward_as_tuple(std::forward<Args>(args)...)`.
526
 
527
  *Effects:* If the map already contains an element whose key is
@@ -541,13 +555,14 @@ template <class M>
541
  pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj);
542
  template<class M>
543
  iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj);
544
  ```
545
 
546
- *Requires:* `is_assignable_v<mapped_type&, M&&>` shall be `true`.
547
- `value_type` shall be `EmplaceConstructible` into `unordered_map` from
548
- `k`, `std::forward<M>(obj)`.
 
549
 
550
  *Effects:* If the map already contains an element `e` whose key is
551
  equivalent to `k`, assigns `std::forward<M>(obj)` to `e.second`.
552
  Otherwise inserts an object of type `value_type` constructed with `k`,
553
  `std::forward<M>(obj)`.
@@ -563,13 +578,14 @@ template <class M>
563
  pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj);
564
  template<class M>
565
  iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj);
566
  ```
567
 
568
- *Requires:* `is_assignable_v<mapped_type&, M&&>` shall be `true`.
569
- `value_type` shall be `EmplaceConstructible` into `unordered_map` from
570
- `std::move(k)`, `std::forward<M>(obj)`.
 
571
 
572
  *Effects:* If the map already contains an element `e` whose key is
573
  equivalent to `k`, assigns `std::forward<M>(obj)` to `e.second`.
574
  Otherwise inserts an object of type `value_type` constructed with
575
  `std::move(k)`, `std::forward<M>(obj)`.
@@ -578,54 +594,65 @@ Otherwise inserts an object of type `value_type` constructed with
578
  pair is `true` if and only if the insertion took place. The returned
579
  iterator points to the map element whose key is equivalent to `k`.
580
 
581
  *Complexity:* The same as `emplace` and `emplace_hint`, respectively.
582
 
583
- #### `unordered_map` swap <a id="unord.map.swap">[[unord.map.swap]]</a>
584
 
585
  ``` cpp
586
- template <class Key, class T, class Hash, class Pred, class Alloc>
587
- void swap(unordered_map<Key, T, Hash, Pred, Alloc>& x,
588
- unordered_map<Key, T, Hash, Pred, Alloc>& y)
589
- noexcept(noexcept(x.swap(y)));
590
  ```
591
 
592
- *Effects:* As if by `x.swap(y)`.
 
 
 
 
 
 
 
 
 
 
 
 
593
 
594
  ### Class template `unordered_multimap` <a id="unord.multimap">[[unord.multimap]]</a>
595
 
596
- #### Class template `unordered_multimap` overview <a id="unord.multimap.overview">[[unord.multimap.overview]]</a>
597
 
598
  An `unordered_multimap` is an unordered associative container that
599
  supports equivalent keys (an instance of `unordered_multimap` may
600
  contain multiple copies of each key value) and that associates values of
601
  another type `mapped_type` with the keys. The `unordered_multimap` class
602
  supports forward iterators.
603
 
604
- An `unordered_multimap` satisfies all of the requirements of a
605
- container, of an unordered associative container, and of an
606
- allocator-aware container (Table  [[tab:containers.allocatoraware]]). It
607
- provides the operations described in the preceding requirements table
608
- for equivalent keys; that is, an `unordered_multimap` supports the
609
- `a_eq` operations in that table, not the `a_uniq` operations. For an
610
- `unordered_multimap<Key, T>` the `key type` is `Key`, the mapped type is
611
- `T`, and the value type is `pair<const Key, T>`.
612
 
613
- This section only describes operations on `unordered_multimap` that are
614
- not described in one of the requirement tables, or for which there is
615
- additional semantic information.
616
 
617
  ``` cpp
618
  namespace std {
619
  template<class Key,
620
  class T,
621
  class Hash = hash<Key>,
622
  class Pred = equal_to<Key>,
623
  class Allocator = allocator<pair<const Key, T>>>
624
  class unordered_multimap {
625
  public:
626
- // types:
627
  using key_type = Key;
628
  using mapped_type = T;
629
  using value_type = pair<const Key, T>;
630
  using hasher = Hash;
631
  using key_equal = Pred;
@@ -688,20 +715,20 @@ namespace std {
688
  is_nothrow_move_assignable_v<Hash> &&
689
  is_nothrow_move_assignable_v<Pred>);
690
  unordered_multimap& operator=(initializer_list<value_type>);
691
  allocator_type get_allocator() const noexcept;
692
 
693
- // iterators:
694
  iterator begin() noexcept;
695
  const_iterator begin() const noexcept;
696
  iterator end() noexcept;
697
  const_iterator end() const noexcept;
698
  const_iterator cbegin() const noexcept;
699
  const_iterator cend() const noexcept;
700
 
701
- // capacity:
702
- bool empty() const noexcept;
703
  size_type size() const noexcept;
704
  size_type max_size() const noexcept;
705
 
706
  // [unord.multimap.modifiers], modifiers
707
  template<class... Args> iterator emplace(Args&&... args);
@@ -737,22 +764,35 @@ namespace std {
737
  template<class H2, class P2>
738
  void merge(unordered_map<Key, T, H2, P2, Allocator>& source);
739
  template<class H2, class P2>
740
  void merge(unordered_map<Key, T, H2, P2, Allocator>&& source);
741
 
742
- // observers:
743
  hasher hash_function() const;
744
  key_equal key_eq() const;
745
 
746
- // map operations:
747
  iterator find(const key_type& k);
748
  const_iterator find(const key_type& k) const;
 
 
 
 
749
  size_type count(const key_type& k) const;
 
 
 
 
 
750
  pair<iterator, iterator> equal_range(const key_type& k);
751
  pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
 
 
 
 
752
 
753
- // bucket interface:
754
  size_type bucket_count() const noexcept;
755
  size_type max_bucket_count() const noexcept;
756
  size_type bucket_size(size_type n) const;
757
  size_type bucket(const key_type& k) const;
758
  local_iterator begin(size_type n);
@@ -769,66 +809,59 @@ namespace std {
769
  void rehash(size_type n);
770
  void reserve(size_type n);
771
  };
772
 
773
  template<class InputIterator,
774
- class Hash = hash<iter_key_t<InputIterator>>,
775
- class Pred = equal_to<iter_key_t<InputIterator>>,
776
- class Allocator = allocator<iter_to_alloc_t<InputIterator>>>
777
  unordered_multimap(InputIterator, InputIterator,
778
  typename see below::size_type = see below,
779
  Hash = Hash(), Pred = Pred(), Allocator = Allocator())
780
- -> unordered_multimap<iter_key_t<InputIterator>, iter_value_t<InputIterator>, Hash, Pred,
781
- Allocator>;
782
 
783
  template<class Key, class T, class Hash = hash<Key>,
784
  class Pred = equal_to<Key>, class Allocator = allocator<pair<const Key, T>>>
785
- unordered_multimap(initializer_list<pair<const Key, T>>,
786
  typename see below::size_type = see below,
787
  Hash = Hash(), Pred = Pred(), Allocator = Allocator())
788
  -> unordered_multimap<Key, T, Hash, Pred, Allocator>;
789
 
790
  template<class InputIterator, class Allocator>
791
  unordered_multimap(InputIterator, InputIterator, typename see below::size_type, Allocator)
792
- -> unordered_multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>,
793
- hash<iter_key_t<InputIterator>>,
794
- equal_to<iter_key_t<InputIterator>>, Allocator>;
795
 
796
  template<class InputIterator, class Allocator>
797
  unordered_multimap(InputIterator, InputIterator, Allocator)
798
- -> unordered_multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>,
799
- hash<iter_key_t<InputIterator>>,
800
- equal_to<iter_key_t<InputIterator>>, Allocator>;
801
 
802
  template<class InputIterator, class Hash, class Allocator>
803
  unordered_multimap(InputIterator, InputIterator, typename see below::size_type, Hash,
804
  Allocator)
805
- -> unordered_multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>, Hash,
806
- equal_to<iter_key_t<InputIterator>>, Allocator>;
807
 
808
- template<class Key, class T, typename Allocator>
809
- unordered_multimap(initializer_list<pair<const Key, T>>, typename see below::size_type,
810
  Allocator)
811
  -> unordered_multimap<Key, T, hash<Key>, equal_to<Key>, Allocator>;
812
 
813
- template<class Key, class T, typename Allocator>
814
- unordered_multimap(initializer_list<pair<const Key, T>>, Allocator)
815
  -> unordered_multimap<Key, T, hash<Key>, equal_to<Key>, Allocator>;
816
 
817
  template<class Key, class T, class Hash, class Allocator>
818
- unordered_multimap(initializer_list<pair<const Key, T>>, typename see below::size_type,
819
  Hash, Allocator)
820
  -> unordered_multimap<Key, T, Hash, equal_to<Key>, Allocator>;
821
 
822
- template <class Key, class T, class Hash, class Pred, class Alloc>
823
- bool operator==(const unordered_multimap<Key, T, Hash, Pred, Alloc>& a,
824
- const unordered_multimap<Key, T, Hash, Pred, Alloc>& b);
825
- template <class Key, class T, class Hash, class Pred, class Alloc>
826
- bool operator!=(const unordered_multimap<Key, T, Hash, Pred, Alloc>& a,
827
- const unordered_multimap<Key, T, Hash, Pred, Alloc>& b);
828
-
829
- // [unord.multimap.swap], swap
830
  template<class Key, class T, class Hash, class Pred, class Alloc>
831
  void swap(unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
832
  unordered_multimap<Key, T, Hash, Pred, Alloc>& y)
833
  noexcept(noexcept(x.swap(y)));
834
  }
@@ -836,11 +869,11 @@ namespace std {
836
 
837
  A `size_type` parameter type in an `unordered_multimap` deduction guide
838
  refers to the `size_type` member type of the type deduced by the
839
  deduction guide.
840
 
841
- #### `unordered_multimap` constructors <a id="unord.multimap.cnstr">[[unord.multimap.cnstr]]</a>
842
 
843
  ``` cpp
844
  unordered_multimap() : unordered_multimap(size_type(see below)) { }
845
  explicit unordered_multimap(size_type n,
846
  const hasher& hf = hasher(),
@@ -876,76 +909,85 @@ hash function, key equality predicate, and allocator, and using at least
876
  `l`) for the first form, or from the range \[`il.begin()`, `il.end()`)
877
  for the second form. `max_load_factor()` returns `1.0`.
878
 
879
  *Complexity:* Average case linear, worst case quadratic.
880
 
881
- #### `unordered_multimap` modifiers <a id="unord.multimap.modifiers">[[unord.multimap.modifiers]]</a>
882
 
883
  ``` cpp
884
  template<class P>
885
  iterator insert(P&& obj);
886
  ```
887
 
 
 
888
  *Effects:* Equivalent to: `return emplace(std::forward<P>(obj));`
889
 
890
- *Remarks:* This signature shall not participate in overload resolution
891
- unless `is_constructible_v<value_type, P&&>` is `true`.
892
-
893
  ``` cpp
894
  template<class P>
895
  iterator insert(const_iterator hint, P&& obj);
896
  ```
897
 
 
 
898
  *Effects:* Equivalent to:
899
  `return emplace_hint(hint, std::forward<P>(obj));`
900
 
901
- *Remarks:* This signature shall not participate in overload resolution
902
- unless `is_constructible_v<value_type, P&&>` is `true`.
903
-
904
- #### `unordered_multimap` swap <a id="unord.multimap.swap">[[unord.multimap.swap]]</a>
905
 
906
  ``` cpp
907
- template <class Key, class T, class Hash, class Pred, class Alloc>
908
- void swap(unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
909
- unordered_multimap<Key, T, Hash, Pred, Alloc>& y)
910
- noexcept(noexcept(x.swap(y)));
911
  ```
912
 
913
- *Effects:* As if by `x.swap(y)`.
 
 
 
 
 
 
 
 
 
 
 
 
914
 
915
  ### Class template `unordered_set` <a id="unord.set">[[unord.set]]</a>
916
 
917
- #### Class template `unordered_set` overview <a id="unord.set.overview">[[unord.set.overview]]</a>
918
 
919
  An `unordered_set` is an unordered associative container that supports
920
  unique keys (an `unordered_set` contains at most one of each key value)
921
  and in which the elements’ keys are the elements themselves. The
922
  `unordered_set` class supports forward iterators.
923
 
924
- An `unordered_set` satisfies all of the requirements of a container, of
925
- an unordered associative container, and of an allocator-aware container
926
- (Table  [[tab:containers.allocatoraware]]). It provides the operations
927
- described in the preceding requirements table for unique keys; that is,
928
- an `unordered_set` supports the `a_uniq` operations in that table, not
929
- the `a_eq` operations. For an `unordered_set<Key>` the `key type` and
930
- the value type are both `Key`. The `iterator` and `const_iterator` types
931
- are both constant iterator types. It is unspecified whether they are the
932
  same type.
933
 
934
- This section only describes operations on `unordered_set` that are not
935
- described in one of the requirement tables, or for which there is
936
- additional semantic information.
937
 
938
  ``` cpp
939
  namespace std {
940
  template<class Key,
941
  class Hash = hash<Key>,
942
  class Pred = equal_to<Key>,
943
  class Allocator = allocator<Key>>
944
  class unordered_set {
945
  public:
946
- // types:
947
  using key_type = Key;
948
  using value_type = Key;
949
  using hasher = Hash;
950
  using key_equal = Pred;
951
  using allocator_type = Allocator;
@@ -959,11 +1001,11 @@ namespace std {
959
  using iterator = implementation-defined // type of unordered_set::iterator; // see [container.requirements]
960
  using const_iterator = implementation-defined // type of unordered_set::const_iterator; // see [container.requirements]
961
  using local_iterator = implementation-defined // type of unordered_set::local_iterator; // see [container.requirements]
962
  using const_local_iterator = implementation-defined // type of unordered_set::const_local_iterator; // see [container.requirements]
963
  using node_type = unspecified;
964
- using insert_return_type = INSERT_RETURN_TYPE<iterator, node_type>;
965
 
966
  // [unord.set.cnstr], construct/copy/destroy
967
  unordered_set();
968
  explicit unordered_set(size_type n,
969
  const hasher& hf = hasher(),
@@ -1008,24 +1050,24 @@ namespace std {
1008
  is_nothrow_move_assignable_v<Hash> &&
1009
  is_nothrow_move_assignable_v<Pred>);
1010
  unordered_set& operator=(initializer_list<value_type>);
1011
  allocator_type get_allocator() const noexcept;
1012
 
1013
- // iterators:
1014
  iterator begin() noexcept;
1015
  const_iterator begin() const noexcept;
1016
  iterator end() noexcept;
1017
  const_iterator end() const noexcept;
1018
  const_iterator cbegin() const noexcept;
1019
  const_iterator cend() const noexcept;
1020
 
1021
- // capacity:
1022
- bool empty() const noexcept;
1023
  size_type size() const noexcept;
1024
  size_type max_size() const noexcept;
1025
 
1026
- // modifiers:
1027
  template<class... Args> pair<iterator, bool> emplace(Args&&... args);
1028
  template<class... Args> iterator emplace_hint(const_iterator position, Args&&... args);
1029
  pair<iterator, bool> insert(const value_type& obj);
1030
  pair<iterator, bool> insert(value_type&& obj);
1031
  iterator insert(const_iterator hint, const value_type& obj);
@@ -1055,22 +1097,35 @@ namespace std {
1055
  template<class H2, class P2>
1056
  void merge(unordered_multiset<Key, H2, P2, Allocator>& source);
1057
  template<class H2, class P2>
1058
  void merge(unordered_multiset<Key, H2, P2, Allocator>&& source);
1059
 
1060
- // observers:
1061
  hasher hash_function() const;
1062
  key_equal key_eq() const;
1063
 
1064
- // set operations:
1065
  iterator find(const key_type& k);
1066
  const_iterator find(const key_type& k) const;
 
 
 
 
1067
  size_type count(const key_type& k) const;
 
 
 
 
 
1068
  pair<iterator, iterator> equal_range(const key_type& k);
1069
  pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
 
 
 
 
1070
 
1071
- // bucket interface:
1072
  size_type bucket_count() const noexcept;
1073
  size_type max_bucket_count() const noexcept;
1074
  size_type bucket_size(size_type n) const;
1075
  size_type bucket(const key_type& k) const;
1076
  local_iterator begin(size_type n);
@@ -1078,75 +1133,68 @@ namespace std {
1078
  local_iterator end(size_type n);
1079
  const_local_iterator end(size_type n) const;
1080
  const_local_iterator cbegin(size_type n) const;
1081
  const_local_iterator cend(size_type n) const;
1082
 
1083
- // hash policy:
1084
  float load_factor() const noexcept;
1085
  float max_load_factor() const noexcept;
1086
  void max_load_factor(float z);
1087
  void rehash(size_type n);
1088
  void reserve(size_type n);
1089
  };
1090
 
1091
  template<class InputIterator,
1092
- class Hash = hash<typename iterator_traits<InputIterator>::value_type>,
1093
- class Pred = equal_to<typename iterator_traits<InputIterator>::value_type>,
1094
- class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
1095
  unordered_set(InputIterator, InputIterator, typename see below::size_type = see below,
1096
  Hash = Hash(), Pred = Pred(), Allocator = Allocator())
1097
- -> unordered_set<typename iterator_traits<InputIterator>::value_type,
1098
  Hash, Pred, Allocator>;
1099
 
1100
  template<class T, class Hash = hash<T>,
1101
  class Pred = equal_to<T>, class Allocator = allocator<T>>
1102
  unordered_set(initializer_list<T>, typename see below::size_type = see below,
1103
  Hash = Hash(), Pred = Pred(), Allocator = Allocator())
1104
  -> unordered_set<T, Hash, Pred, Allocator>;
1105
 
1106
  template<class InputIterator, class Allocator>
1107
  unordered_set(InputIterator, InputIterator, typename see below::size_type, Allocator)
1108
- -> unordered_set<typename iterator_traits<InputIterator>::value_type,
1109
- hash<typename iterator_traits<InputIterator>::value_type>,
1110
- equal_to<typename iterator_traits<InputIterator>::value_type>,
1111
  Allocator>;
1112
 
1113
  template<class InputIterator, class Hash, class Allocator>
1114
  unordered_set(InputIterator, InputIterator, typename see below::size_type,
1115
  Hash, Allocator)
1116
- -> unordered_set<typename iterator_traits<InputIterator>::value_type, Hash,
1117
- equal_to<typename iterator_traits<InputIterator>::value_type>,
1118
  Allocator>;
1119
 
1120
  template<class T, class Allocator>
1121
  unordered_set(initializer_list<T>, typename see below::size_type, Allocator)
1122
  -> unordered_set<T, hash<T>, equal_to<T>, Allocator>;
1123
 
1124
  template<class T, class Hash, class Allocator>
1125
  unordered_set(initializer_list<T>, typename see below::size_type, Hash, Allocator)
1126
  -> unordered_set<T, Hash, equal_to<T>, Allocator>;
1127
 
1128
- template <class Key, class Hash, class Pred, class Alloc>
1129
- bool operator==(const unordered_set<Key, Hash, Pred, Alloc>& a,
1130
- const unordered_set<Key, Hash, Pred, Alloc>& b);
1131
- template <class Key, class Hash, class Pred, class Alloc>
1132
- bool operator!=(const unordered_set<Key, Hash, Pred, Alloc>& a,
1133
- const unordered_set<Key, Hash, Pred, Alloc>& b);
1134
-
1135
- // [unord.set.swap], swap
1136
  template<class Key, class Hash, class Pred, class Alloc>
1137
  void swap(unordered_set<Key, Hash, Pred, Alloc>& x,
1138
  unordered_set<Key, Hash, Pred, Alloc>& y)
1139
  noexcept(noexcept(x.swap(y)));
1140
  }
1141
  ```
1142
 
1143
  A `size_type` parameter type in an `unordered_set` deduction guide
1144
- refers to the `size_type` member type of the primary `unordered_set`
1145
- template.
1146
 
1147
- #### `unordered_set` constructors <a id="unord.set.cnstr">[[unord.set.cnstr]]</a>
1148
 
1149
  ``` cpp
1150
  unordered_set() : unordered_set(size_type(see below)) { }
1151
  explicit unordered_set(size_type n,
1152
  const hasher& hf = hasher(),
@@ -1182,54 +1230,65 @@ buckets. If `n` is not provided, the number of buckets is
1182
  `l`) for the first form, or from the range \[`il.begin()`, `il.end()`)
1183
  for the second form. `max_load_factor()` returns `1.0`.
1184
 
1185
  *Complexity:* Average case linear, worst case quadratic.
1186
 
1187
- #### `unordered_set` swap <a id="unord.set.swap">[[unord.set.swap]]</a>
1188
 
1189
  ``` cpp
1190
- template <class Key, class Hash, class Pred, class Alloc>
1191
- void swap(unordered_set<Key, Hash, Pred, Alloc>& x,
1192
- unordered_set<Key, Hash, Pred, Alloc>& y)
1193
- noexcept(noexcept(x.swap(y)));
1194
  ```
1195
 
1196
- *Effects:* As if by `x.swap(y)`.
 
 
 
 
 
 
 
 
 
 
 
 
1197
 
1198
  ### Class template `unordered_multiset` <a id="unord.multiset">[[unord.multiset]]</a>
1199
 
1200
- #### Class template `unordered_multiset` overview <a id="unord.multiset.overview">[[unord.multiset.overview]]</a>
1201
 
1202
  An `unordered_multiset` is an unordered associative container that
1203
  supports equivalent keys (an instance of `unordered_multiset` may
1204
  contain multiple copies of the same key value) and in which each
1205
  element’s key is the element itself. The `unordered_multiset` class
1206
  supports forward iterators.
1207
 
1208
- An `unordered_multiset` satisfies all of the requirements of a
1209
- container, of an unordered associative container, and of an
1210
- allocator-aware container (Table  [[tab:containers.allocatoraware]]). It
1211
- provides the operations described in the preceding requirements table
1212
- for equivalent keys; that is, an `unordered_multiset` supports the
1213
- `a_eq` operations in that table, not the `a_uniq` operations. For an
1214
- `unordered_multiset<Key>` the `key type` and the value type are both
1215
- `Key`. The `iterator` and `const_iterator` types are both constant
1216
- iterator types. It is unspecified whether they are the same type.
1217
 
1218
- This section only describes operations on `unordered_multiset` that are
1219
- not described in one of the requirement tables, or for which there is
1220
- additional semantic information.
1221
 
1222
  ``` cpp
1223
  namespace std {
1224
  template<class Key,
1225
  class Hash = hash<Key>,
1226
  class Pred = equal_to<Key>,
1227
  class Allocator = allocator<Key>>
1228
  class unordered_multiset {
1229
  public:
1230
- // types:
1231
  using key_type = Key;
1232
  using value_type = Key;
1233
  using hasher = Hash;
1234
  using key_equal = Pred;
1235
  using allocator_type = Allocator;
@@ -1291,24 +1350,24 @@ namespace std {
1291
  is_nothrow_move_assignable_v<Hash> &&
1292
  is_nothrow_move_assignable_v<Pred>);
1293
  unordered_multiset& operator=(initializer_list<value_type>);
1294
  allocator_type get_allocator() const noexcept;
1295
 
1296
- // iterators:
1297
  iterator begin() noexcept;
1298
  const_iterator begin() const noexcept;
1299
  iterator end() noexcept;
1300
  const_iterator end() const noexcept;
1301
  const_iterator cbegin() const noexcept;
1302
  const_iterator cend() const noexcept;
1303
 
1304
- // capacity:
1305
- bool empty() const noexcept;
1306
  size_type size() const noexcept;
1307
  size_type max_size() const noexcept;
1308
 
1309
- // modifiers:
1310
  template<class... Args> iterator emplace(Args&&... args);
1311
  template<class... Args> iterator emplace_hint(const_iterator position, Args&&... args);
1312
  iterator insert(const value_type& obj);
1313
  iterator insert(value_type&& obj);
1314
  iterator insert(const_iterator hint, const value_type& obj);
@@ -1338,22 +1397,35 @@ namespace std {
1338
  template<class H2, class P2>
1339
  void merge(unordered_set<Key, H2, P2, Allocator>& source);
1340
  template<class H2, class P2>
1341
  void merge(unordered_set<Key, H2, P2, Allocator>&& source);
1342
 
1343
- // observers:
1344
  hasher hash_function() const;
1345
  key_equal key_eq() const;
1346
 
1347
- // set operations:
1348
  iterator find(const key_type& k);
1349
  const_iterator find(const key_type& k) const;
 
 
 
 
1350
  size_type count(const key_type& k) const;
 
 
 
 
 
1351
  pair<iterator, iterator> equal_range(const key_type& k);
1352
  pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
 
 
 
 
1353
 
1354
- // bucket interface:
1355
  size_type bucket_count() const noexcept;
1356
  size_type max_bucket_count() const noexcept;
1357
  size_type bucket_size(size_type n) const;
1358
  size_type bucket(const key_type& k) const;
1359
  local_iterator begin(size_type n);
@@ -1361,75 +1433,68 @@ namespace std {
1361
  local_iterator end(size_type n);
1362
  const_local_iterator end(size_type n) const;
1363
  const_local_iterator cbegin(size_type n) const;
1364
  const_local_iterator cend(size_type n) const;
1365
 
1366
- // hash policy:
1367
  float load_factor() const noexcept;
1368
  float max_load_factor() const noexcept;
1369
  void max_load_factor(float z);
1370
  void rehash(size_type n);
1371
  void reserve(size_type n);
1372
  };
1373
 
1374
  template<class InputIterator,
1375
- class Hash = hash<typename iterator_traits<InputIterator>::value_type>,
1376
- class Pred = equal_to<typename iterator_traits<InputIterator>::value_type>,
1377
- class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
1378
  unordered_multiset(InputIterator, InputIterator, see below::size_type = see below,
1379
  Hash = Hash(), Pred = Pred(), Allocator = Allocator())
1380
- -> unordered_multiset<typename iterator_traits<InputIterator>::value_type,
1381
  Hash, Pred, Allocator>;
1382
 
1383
  template<class T, class Hash = hash<T>,
1384
  class Pred = equal_to<T>, class Allocator = allocator<T>>
1385
  unordered_multiset(initializer_list<T>, typename see below::size_type = see below,
1386
  Hash = Hash(), Pred = Pred(), Allocator = Allocator())
1387
  -> unordered_multiset<T, Hash, Pred, Allocator>;
1388
 
1389
  template<class InputIterator, class Allocator>
1390
  unordered_multiset(InputIterator, InputIterator, typename see below::size_type, Allocator)
1391
- -> unordered_multiset<typename iterator_traits<InputIterator>::value_type,
1392
- hash<typename iterator_traits<InputIterator>::value_type>,
1393
- equal_to<typename iterator_traits<InputIterator>::value_type>,
1394
  Allocator>;
1395
 
1396
  template<class InputIterator, class Hash, class Allocator>
1397
  unordered_multiset(InputIterator, InputIterator, typename see below::size_type,
1398
  Hash, Allocator)
1399
- -> unordered_multiset<typename iterator_traits<InputIterator>::value_type, Hash,
1400
- equal_to<typename iterator_traits<InputIterator>::value_type>,
1401
  Allocator>;
1402
 
1403
  template<class T, class Allocator>
1404
  unordered_multiset(initializer_list<T>, typename see below::size_type, Allocator)
1405
  -> unordered_multiset<T, hash<T>, equal_to<T>, Allocator>;
1406
 
1407
  template<class T, class Hash, class Allocator>
1408
  unordered_multiset(initializer_list<T>, typename see below::size_type, Hash, Allocator)
1409
  -> unordered_multiset<T, Hash, equal_to<T>, Allocator>;
1410
 
1411
- template <class Key, class Hash, class Pred, class Alloc>
1412
- bool operator==(const unordered_multiset<Key, Hash, Pred, Alloc>& a,
1413
- const unordered_multiset<Key, Hash, Pred, Alloc>& b);
1414
- template <class Key, class Hash, class Pred, class Alloc>
1415
- bool operator!=(const unordered_multiset<Key, Hash, Pred, Alloc>& a,
1416
- const unordered_multiset<Key, Hash, Pred, Alloc>& b);
1417
-
1418
- // [unord.multiset.swap], swap
1419
  template<class Key, class Hash, class Pred, class Alloc>
1420
  void swap(unordered_multiset<Key, Hash, Pred, Alloc>& x,
1421
  unordered_multiset<Key, Hash, Pred, Alloc>& y)
1422
  noexcept(noexcept(x.swap(y)));
1423
  }
1424
  ```
1425
 
1426
  A `size_type` parameter type in an `unordered_multiset` deduction guide
1427
- refers to the `size_type` member type of the primary
1428
- `unordered_multiset` template.
1429
 
1430
- #### `unordered_multiset` constructors <a id="unord.multiset.cnstr">[[unord.multiset.cnstr]]</a>
1431
 
1432
  ``` cpp
1433
  unordered_multiset() : unordered_multiset(size_type(see below)) { }
1434
  explicit unordered_multiset(size_type n,
1435
  const hasher& hf = hasher(),
@@ -1465,16 +1530,27 @@ hash function, key equality predicate, and allocator, and using at least
1465
  `l`) for the first form, or from the range \[`il.begin()`, `il.end()`)
1466
  for the second form. `max_load_factor()` returns `1.0`.
1467
 
1468
  *Complexity:* Average case linear, worst case quadratic.
1469
 
1470
- #### `unordered_multiset` swap <a id="unord.multiset.swap">[[unord.multiset.swap]]</a>
1471
 
1472
  ``` cpp
1473
- template <class Key, class Hash, class Pred, class Alloc>
1474
- void swap(unordered_multiset<Key, Hash, Pred, Alloc>& x,
1475
- unordered_multiset<Key, Hash, Pred, Alloc>& y)
1476
- noexcept(noexcept(x.swap(y)));
1477
  ```
1478
 
1479
- *Effects:* As if by `x.swap(y)`.
 
 
 
 
 
 
 
 
 
 
 
 
1480
 
 
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
 
9
+ The exposition-only alias templates *`iter-value-type`*,
10
+ *`iter-key-type`*, *`iter-mapped-type`*, and *`iter-to-alloc-type`*
11
+ defined in [[associative.general]] may appear in deduction guides for
12
+ unordered containers.
13
 
14
  ### Header `<unordered_map>` synopsis <a id="unord.map.syn">[[unord.map.syn]]</a>
15
 
16
  ``` cpp
17
+ #include <compare> // see [compare.syn]
18
+ #include <initializer_list> // see [initializer.list.syn]
19
 
20
  namespace std {
21
  // [unord.map], class template unordered_map
22
  template<class Key,
23
  class T,
 
32
  class Hash = hash<Key>,
33
  class Pred = equal_to<Key>,
34
  class Alloc = allocator<pair<const Key, T>>>
35
  class unordered_multimap;
36
 
37
+ template<class Key, class T, class Hash, class Pred, class Alloc>
38
+ bool operator==(const unordered_map<Key, T, Hash, Pred, Alloc>& a,
39
+ const unordered_map<Key, T, Hash, Pred, Alloc>& b);
40
+
41
+ template<class Key, class T, class Hash, class Pred, class Alloc>
42
+ bool operator==(const unordered_multimap<Key, T, Hash, Pred, Alloc>& a,
43
+ const unordered_multimap<Key, T, Hash, Pred, Alloc>& b);
44
+
45
  template<class Key, class T, class Hash, class Pred, class Alloc>
46
  void swap(unordered_map<Key, T, Hash, Pred, Alloc>& x,
47
  unordered_map<Key, T, Hash, Pred, Alloc>& y)
48
  noexcept(noexcept(x.swap(y)));
49
 
50
  template<class Key, class T, class Hash, class Pred, class Alloc>
51
  void swap(unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
52
  unordered_multimap<Key, T, Hash, Pred, Alloc>& y)
53
  noexcept(noexcept(x.swap(y)));
54
 
55
+ template<class K, class T, class H, class P, class A, class Predicate>
56
+ typename unordered_map<K, T, H, P, A>::size_type
57
+ erase_if(unordered_map<K, T, H, P, A>& c, Predicate pred);
58
+
59
+ template<class K, class T, class H, class P, class A, class Predicate>
60
+ typename unordered_multimap<K, T, H, P, A>::size_type
61
+ erase_if(unordered_multimap<K, T, H, P, A>& c, Predicate pred);
 
 
 
 
 
62
 
63
  namespace pmr {
64
  template<class Key,
65
  class T,
66
  class Hash = hash<Key>,
 
81
  ```
82
 
83
  ### Header `<unordered_set>` synopsis <a id="unord.set.syn">[[unord.set.syn]]</a>
84
 
85
  ``` cpp
86
+ #include <compare> // see [compare.syn]
87
+ #include <initializer_list> // see [initializer.list.syn]
88
 
89
  namespace std {
90
  // [unord.set], class template unordered_set
91
  template<class Key,
92
  class Hash = hash<Key>,
 
99
  class Hash = hash<Key>,
100
  class Pred = equal_to<Key>,
101
  class Alloc = allocator<Key>>
102
  class unordered_multiset;
103
 
104
+ template<class Key, class Hash, class Pred, class Alloc>
105
+ bool operator==(const unordered_set<Key, Hash, Pred, Alloc>& a,
106
+ const unordered_set<Key, Hash, Pred, Alloc>& b);
107
+
108
+ template<class Key, class Hash, class Pred, class Alloc>
109
+ bool operator==(const unordered_multiset<Key, Hash, Pred, Alloc>& a,
110
+ const unordered_multiset<Key, Hash, Pred, Alloc>& b);
111
+
112
  template<class Key, class Hash, class Pred, class Alloc>
113
  void swap(unordered_set<Key, Hash, Pred, Alloc>& x,
114
  unordered_set<Key, Hash, Pred, Alloc>& y)
115
  noexcept(noexcept(x.swap(y)));
116
 
117
  template<class Key, class Hash, class Pred, class Alloc>
118
  void swap(unordered_multiset<Key, Hash, Pred, Alloc>& x,
119
  unordered_multiset<Key, Hash, Pred, Alloc>& y)
120
  noexcept(noexcept(x.swap(y)));
121
 
122
+ template<class K, class H, class P, class A, class Predicate>
123
+ typename unordered_set<K, H, P, A>::size_type
124
+ erase_if(unordered_set<K, H, P, A>& c, Predicate pred);
125
+
126
+ template<class K, class H, class P, class A, class Predicate>
127
+ typename unordered_multiset<K, H, P, A>::size_type
128
+ erase_if(unordered_multiset<K, H, P, A>& c, Predicate pred);
 
 
 
 
 
129
 
130
  namespace pmr {
131
  template<class Key,
132
  class Hash = hash<Key>,
133
  class Pred = equal_to<Key>>
 
143
  }
144
  ```
145
 
146
  ### Class template `unordered_map` <a id="unord.map">[[unord.map]]</a>
147
 
148
+ #### Overview <a id="unord.map.overview">[[unord.map.overview]]</a>
149
 
150
  An `unordered_map` is an unordered associative container that supports
151
  unique keys (an `unordered_map` contains at most one of each key value)
152
  and that associates values of another type `mapped_type` with the keys.
153
  The `unordered_map` class supports forward iterators.
154
 
155
+ An `unordered_map` meets all of the requirements of a container, of an
156
+ unordered associative container, and of an allocator-aware container (
157
+ [[container.alloc.req]]). It provides the operations described in the
158
+ preceding requirements table for unique keys; that is, an
159
+ `unordered_map` supports the `a_uniq` operations in that table, not the
160
+ `a_eq` operations. For an `unordered_map<Key, T>` the `key type` is
161
  `Key`, the mapped type is `T`, and the value type is
162
  `pair<const Key, T>`.
163
 
164
+ Subclause  [[unord.map]] only describes operations on `unordered_map`
165
+ that are not described in one of the requirement tables, or for which
166
+ there is additional semantic information.
167
 
168
  ``` cpp
169
  namespace std {
170
  template<class Key,
171
  class T,
172
  class Hash = hash<Key>,
173
  class Pred = equal_to<Key>,
174
  class Allocator = allocator<pair<const Key, T>>>
175
  class unordered_map {
176
  public:
177
+ // types
178
  using key_type = Key;
179
  using mapped_type = T;
180
  using value_type = pair<const Key, T>;
181
  using hasher = Hash;
182
  using key_equal = Pred;
 
191
  using iterator = implementation-defined // type of unordered_map::iterator; // see [container.requirements]
192
  using const_iterator = implementation-defined // type of unordered_map::const_iterator; // see [container.requirements]
193
  using local_iterator = implementation-defined // type of unordered_map::local_iterator; // see [container.requirements]
194
  using const_local_iterator = implementation-defined // type of unordered_map::const_local_iterator; // see [container.requirements]
195
  using node_type = unspecified;
196
+ using insert_return_type = insert-return-type<iterator, node_type>;
197
 
198
  // [unord.map.cnstr], construct/copy/destroy
199
  unordered_map();
200
  explicit unordered_map(size_type n,
201
  const hasher& hf = hasher(),
 
240
  is_nothrow_move_assignable_v<Hash> &&
241
  is_nothrow_move_assignable_v<Pred>);
242
  unordered_map& operator=(initializer_list<value_type>);
243
  allocator_type get_allocator() const noexcept;
244
 
245
+ // iterators
246
  iterator begin() noexcept;
247
  const_iterator begin() const noexcept;
248
  iterator end() noexcept;
249
  const_iterator end() const noexcept;
250
  const_iterator cbegin() const noexcept;
251
  const_iterator cend() const noexcept;
252
 
253
+ // capacity
254
+ [[nodiscard]] bool empty() const noexcept;
255
  size_type size() const noexcept;
256
  size_type max_size() const noexcept;
257
 
258
  // [unord.map.modifiers], modifiers
259
  template<class... Args> pair<iterator, bool> emplace(Args&&... args);
 
306
  template<class H2, class P2>
307
  void merge(unordered_multimap<Key, T, H2, P2, Allocator>& source);
308
  template<class H2, class P2>
309
  void merge(unordered_multimap<Key, T, H2, P2, Allocator>&& source);
310
 
311
+ // observers
312
  hasher hash_function() const;
313
  key_equal key_eq() const;
314
 
315
+ // map operations
316
  iterator find(const key_type& k);
317
  const_iterator find(const key_type& k) const;
318
+ template<class K>
319
+ iterator find(const K& k);
320
+ template<class K>
321
+ const_iterator find(const K& k) const;
322
+ template<class K>
323
  size_type count(const key_type& k) const;
324
+ template<class K>
325
+ size_type count(const K& k) const;
326
+ bool contains(const key_type& k) const;
327
+ template<class K>
328
+ bool contains(const K& k) const;
329
  pair<iterator, iterator> equal_range(const key_type& k);
330
  pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
331
+ template<class K>
332
+ pair<iterator, iterator> equal_range(const K& k);
333
+ template<class K>
334
+ pair<const_iterator, const_iterator> equal_range(const K& k) const;
335
 
336
  // [unord.map.elem], element access
337
  mapped_type& operator[](const key_type& k);
338
  mapped_type& operator[](key_type&& k);
339
  mapped_type& at(const key_type& k);
340
  const mapped_type& at(const key_type& k) const;
341
 
342
+ // bucket interface
343
  size_type bucket_count() const noexcept;
344
  size_type max_bucket_count() const noexcept;
345
  size_type bucket_size(size_type n) const;
346
  size_type bucket(const key_type& k) const;
347
  local_iterator begin(size_type n);
 
349
  local_iterator end(size_type n);
350
  const_local_iterator end(size_type n) const;
351
  const_local_iterator cbegin(size_type n) const;
352
  const_local_iterator cend(size_type n) const;
353
 
354
+ // hash policy
355
  float load_factor() const noexcept;
356
  float max_load_factor() const noexcept;
357
  void max_load_factor(float z);
358
  void rehash(size_type n);
359
  void reserve(size_type n);
360
  };
361
 
362
  template<class InputIterator,
363
+ class Hash = hash<iter-key-type<InputIterator>>,
364
+ class Pred = equal_to<iter-key-type<InputIterator>>,
365
+ class Allocator = allocator<iter-to-alloc-type<InputIterator>>>
366
  unordered_map(InputIterator, InputIterator, typename see below::size_type = see below,
367
  Hash = Hash(), Pred = Pred(), Allocator = Allocator())
368
+ -> unordered_map<iter-key-type<InputIterator>, iter-mapped-type<InputIterator>, Hash, Pred,
369
  Allocator>;
370
 
371
  template<class Key, class T, class Hash = hash<Key>,
372
  class Pred = equal_to<Key>, class Allocator = allocator<pair<const Key, T>>>
373
+ unordered_map(initializer_list<pair<Key, T>>,
374
  typename see below::size_type = see below, Hash = Hash(),
375
  Pred = Pred(), Allocator = Allocator())
376
  -> unordered_map<Key, T, Hash, Pred, Allocator>;
377
 
378
  template<class InputIterator, class Allocator>
379
  unordered_map(InputIterator, InputIterator, typename see below::size_type, Allocator)
380
+ -> unordered_map<iter-key-type<InputIterator>, iter-mapped-type<InputIterator>,
381
+ hash<iter-key-type<InputIterator>>,
382
+ equal_to<iter-key-type<InputIterator>>, Allocator>;
383
 
384
  template<class InputIterator, class Allocator>
385
  unordered_map(InputIterator, InputIterator, Allocator)
386
+ -> unordered_map<iter-key-type<InputIterator>, iter-mapped-type<InputIterator>,
387
+ hash<iter-key-type<InputIterator>>,
388
+ equal_to<iter-key-type<InputIterator>>, Allocator>;
389
 
390
  template<class InputIterator, class Hash, class Allocator>
391
  unordered_map(InputIterator, InputIterator, typename see below::size_type, Hash, Allocator)
392
+ -> unordered_map<iter-key-type<InputIterator>, iter-mapped-type<InputIterator>, Hash,
393
+ equal_to<iter-key-type<InputIterator>>, Allocator>;
394
 
395
+ template<class Key, class T, class Allocator>
396
+ unordered_map(initializer_list<pair<Key, T>>, typename see below::size_type,
397
  Allocator)
398
  -> unordered_map<Key, T, hash<Key>, equal_to<Key>, Allocator>;
399
 
400
+ template<class Key, class T, class Allocator>
401
+ unordered_map(initializer_list<pair<Key, T>>, Allocator)
402
  -> unordered_map<Key, T, hash<Key>, equal_to<Key>, Allocator>;
403
 
404
  template<class Key, class T, class Hash, class Allocator>
405
+ unordered_map(initializer_list<pair<Key, T>>, typename see below::size_type, Hash,
406
  Allocator)
407
  -> unordered_map<Key, T, Hash, equal_to<Key>, Allocator>;
408
 
409
+ // swap
 
 
 
 
 
 
 
410
  template<class Key, class T, class Hash, class Pred, class Alloc>
411
  void swap(unordered_map<Key, T, Hash, Pred, Alloc>& x,
412
  unordered_map<Key, T, Hash, Pred, Alloc>& y)
413
  noexcept(noexcept(x.swap(y)));
414
  }
 
416
 
417
  A `size_type` parameter type in an `unordered_map` deduction guide
418
  refers to the `size_type` member type of the type deduced by the
419
  deduction guide.
420
 
421
+ #### Constructors <a id="unord.map.cnstr">[[unord.map.cnstr]]</a>
422
 
423
  ``` cpp
424
  unordered_map() : unordered_map(size_type(see below)) { }
425
  explicit unordered_map(size_type n,
426
  const hasher& hf = hasher(),
 
456
  `l`) for the first form, or from the range \[`il.begin()`, `il.end()`)
457
  for the second form. `max_load_factor()` returns `1.0`.
458
 
459
  *Complexity:* Average case linear, worst case quadratic.
460
 
461
+ #### Element access <a id="unord.map.elem">[[unord.map.elem]]</a>
462
 
463
  ``` cpp
464
  mapped_type& operator[](const key_type& k);
465
  ```
466
 
 
481
  whose key is equivalent to `k`.
482
 
483
  *Throws:* An exception object of type `out_of_range` if no such element
484
  is present.
485
 
486
+ #### Modifiers <a id="unord.map.modifiers">[[unord.map.modifiers]]</a>
487
 
488
  ``` cpp
489
  template<class P>
490
  pair<iterator, bool> insert(P&& obj);
491
  ```
492
 
493
+ *Constraints:* `is_constructible_v<value_type, P&&>` is `true`.
494
+
495
  *Effects:* Equivalent to: `return emplace(std::forward<P>(obj));`
496
 
 
 
 
497
  ``` cpp
498
  template<class P>
499
  iterator insert(const_iterator hint, P&& obj);
500
  ```
501
 
502
+ *Constraints:* `is_constructible_v<value_type, P&&>` is `true`.
503
+
504
  *Effects:* Equivalent to:
505
  `return emplace_hint(hint, std::forward<P>(obj));`
506
 
 
 
 
507
  ``` cpp
508
  template<class... Args>
509
  pair<iterator, bool> try_emplace(const key_type& k, Args&&... args);
510
  template<class... Args>
511
  iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args);
512
  ```
513
 
514
+ *Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into
515
  `unordered_map` from `piecewise_construct`, `forward_as_tuple(k)`,
516
  `forward_as_tuple(std::forward<Args>(args)...)`.
517
 
518
  *Effects:* If the map already contains an element whose key is
519
  equivalent to `k`, there is no effect. Otherwise inserts an object of
 
531
  pair<iterator, bool> try_emplace(key_type&& k, Args&&... args);
532
  template<class... Args>
533
  iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args);
534
  ```
535
 
536
+ *Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into
537
  `unordered_map` from `piecewise_construct`,
538
  `forward_as_tuple(std::move(k))`,
539
  `forward_as_tuple(std::forward<Args>(args)...)`.
540
 
541
  *Effects:* If the map already contains an element whose key is
 
555
  pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj);
556
  template<class M>
557
  iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj);
558
  ```
559
 
560
+ *Mandates:* `is_assignable_v<mapped_type&, M&&>` is `true`.
561
+
562
+ *Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into
563
+ `unordered_map` from `k`, `std::forward<M>(obj)`.
564
 
565
  *Effects:* If the map already contains an element `e` whose key is
566
  equivalent to `k`, assigns `std::forward<M>(obj)` to `e.second`.
567
  Otherwise inserts an object of type `value_type` constructed with `k`,
568
  `std::forward<M>(obj)`.
 
578
  pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj);
579
  template<class M>
580
  iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj);
581
  ```
582
 
583
+ *Mandates:* `is_assignable_v<mapped_type&, M&&>` is `true`.
584
+
585
+ *Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into
586
+ `unordered_map` from `std::move(k)`, `std::forward<M>(obj)`.
587
 
588
  *Effects:* If the map already contains an element `e` whose key is
589
  equivalent to `k`, assigns `std::forward<M>(obj)` to `e.second`.
590
  Otherwise inserts an object of type `value_type` constructed with
591
  `std::move(k)`, `std::forward<M>(obj)`.
 
594
  pair is `true` if and only if the insertion took place. The returned
595
  iterator points to the map element whose key is equivalent to `k`.
596
 
597
  *Complexity:* The same as `emplace` and `emplace_hint`, respectively.
598
 
599
+ #### Erasure <a id="unord.map.erasure">[[unord.map.erasure]]</a>
600
 
601
  ``` cpp
602
+ template<class K, class T, class H, class P, class A, class Predicate>
603
+ typename unordered_map<K, T, H, P, A>::size_type
604
+ erase_if(unordered_map<K, T, H, P, A>& c, Predicate pred);
 
605
  ```
606
 
607
+ *Effects:* Equivalent to:
608
+
609
+ ``` cpp
610
+ auto original_size = c.size();
611
+ for (auto i = c.begin(), last = c.end(); i != last; ) {
612
+ if (pred(*i)) {
613
+ i = c.erase(i);
614
+ } else {
615
+ ++i;
616
+ }
617
+ }
618
+ return original_size - c.size();
619
+ ```
620
 
621
  ### Class template `unordered_multimap` <a id="unord.multimap">[[unord.multimap]]</a>
622
 
623
+ #### Overview <a id="unord.multimap.overview">[[unord.multimap.overview]]</a>
624
 
625
  An `unordered_multimap` is an unordered associative container that
626
  supports equivalent keys (an instance of `unordered_multimap` may
627
  contain multiple copies of each key value) and that associates values of
628
  another type `mapped_type` with the keys. The `unordered_multimap` class
629
  supports forward iterators.
630
 
631
+ An `unordered_multimap` meets all of the requirements of a container, of
632
+ an unordered associative container, and of an allocator-aware container
633
+ ([[container.alloc.req]]). It provides the operations described in the
634
+ preceding requirements table for equivalent keys; that is, an
635
+ `unordered_multimap` supports the `a_eq` operations in that table, not
636
+ the `a_uniq` operations. For an `unordered_multimap<Key, T>` the
637
+ `key type` is `Key`, the mapped type is `T`, and the value type is
638
+ `pair<const Key, T>`.
639
 
640
+ Subclause  [[unord.multimap]] only describes operations on
641
+ `unordered_multimap` that are not described in one of the requirement
642
+ tables, or for which there is additional semantic information.
643
 
644
  ``` cpp
645
  namespace std {
646
  template<class Key,
647
  class T,
648
  class Hash = hash<Key>,
649
  class Pred = equal_to<Key>,
650
  class Allocator = allocator<pair<const Key, T>>>
651
  class unordered_multimap {
652
  public:
653
+ // types
654
  using key_type = Key;
655
  using mapped_type = T;
656
  using value_type = pair<const Key, T>;
657
  using hasher = Hash;
658
  using key_equal = Pred;
 
715
  is_nothrow_move_assignable_v<Hash> &&
716
  is_nothrow_move_assignable_v<Pred>);
717
  unordered_multimap& operator=(initializer_list<value_type>);
718
  allocator_type get_allocator() const noexcept;
719
 
720
+ // iterators
721
  iterator begin() noexcept;
722
  const_iterator begin() const noexcept;
723
  iterator end() noexcept;
724
  const_iterator end() const noexcept;
725
  const_iterator cbegin() const noexcept;
726
  const_iterator cend() const noexcept;
727
 
728
+ // capacity
729
+ [[nodiscard]] bool empty() const noexcept;
730
  size_type size() const noexcept;
731
  size_type max_size() const noexcept;
732
 
733
  // [unord.multimap.modifiers], modifiers
734
  template<class... Args> iterator emplace(Args&&... args);
 
764
  template<class H2, class P2>
765
  void merge(unordered_map<Key, T, H2, P2, Allocator>& source);
766
  template<class H2, class P2>
767
  void merge(unordered_map<Key, T, H2, P2, Allocator>&& source);
768
 
769
+ // observers
770
  hasher hash_function() const;
771
  key_equal key_eq() const;
772
 
773
+ // map operations
774
  iterator find(const key_type& k);
775
  const_iterator find(const key_type& k) const;
776
+ template<class K>
777
+ iterator find(const K& k);
778
+ template<class K>
779
+ const_iterator find(const K& k) const;
780
  size_type count(const key_type& k) const;
781
+ template<class K>
782
+ size_type count(const K& k) const;
783
+ bool contains(const key_type& k) const;
784
+ template<class K>
785
+ bool contains(const K& k) const;
786
  pair<iterator, iterator> equal_range(const key_type& k);
787
  pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
788
+ template<class K>
789
+ pair<iterator, iterator> equal_range(const K& k);
790
+ template<class K>
791
+ pair<const_iterator, const_iterator> equal_range(const K& k) const;
792
 
793
+ // bucket interface
794
  size_type bucket_count() const noexcept;
795
  size_type max_bucket_count() const noexcept;
796
  size_type bucket_size(size_type n) const;
797
  size_type bucket(const key_type& k) const;
798
  local_iterator begin(size_type n);
 
809
  void rehash(size_type n);
810
  void reserve(size_type n);
811
  };
812
 
813
  template<class InputIterator,
814
+ class Hash = hash<iter-key-type<InputIterator>>,
815
+ class Pred = equal_to<iter-key-type<InputIterator>>,
816
+ class Allocator = allocator<iter-to-alloc-type<InputIterator>>>
817
  unordered_multimap(InputIterator, InputIterator,
818
  typename see below::size_type = see below,
819
  Hash = Hash(), Pred = Pred(), Allocator = Allocator())
820
+ -> unordered_multimap<iter-key-type<InputIterator>, iter-mapped-type<InputIterator>,
821
+ Hash, Pred, Allocator>;
822
 
823
  template<class Key, class T, class Hash = hash<Key>,
824
  class Pred = equal_to<Key>, class Allocator = allocator<pair<const Key, T>>>
825
+ unordered_multimap(initializer_list<pair<Key, T>>,
826
  typename see below::size_type = see below,
827
  Hash = Hash(), Pred = Pred(), Allocator = Allocator())
828
  -> unordered_multimap<Key, T, Hash, Pred, Allocator>;
829
 
830
  template<class InputIterator, class Allocator>
831
  unordered_multimap(InputIterator, InputIterator, typename see below::size_type, Allocator)
832
+ -> unordered_multimap<iter-key-type<InputIterator>, iter-mapped-type<InputIterator>,
833
+ hash<iter-key-type<InputIterator>>,
834
+ equal_to<iter-key-type<InputIterator>>, Allocator>;
835
 
836
  template<class InputIterator, class Allocator>
837
  unordered_multimap(InputIterator, InputIterator, Allocator)
838
+ -> unordered_multimap<iter-key-type<InputIterator>, iter-mapped-type<InputIterator>,
839
+ hash<iter-key-type<InputIterator>>,
840
+ equal_to<iter-key-type<InputIterator>>, Allocator>;
841
 
842
  template<class InputIterator, class Hash, class Allocator>
843
  unordered_multimap(InputIterator, InputIterator, typename see below::size_type, Hash,
844
  Allocator)
845
+ -> unordered_multimap<iter-key-type<InputIterator>, iter-mapped-type<InputIterator>, Hash,
846
+ equal_to<iter-key-type<InputIterator>>, Allocator>;
847
 
848
+ template<class Key, class T, class Allocator>
849
+ unordered_multimap(initializer_list<pair<Key, T>>, typename see below::size_type,
850
  Allocator)
851
  -> unordered_multimap<Key, T, hash<Key>, equal_to<Key>, Allocator>;
852
 
853
+ template<class Key, class T, class Allocator>
854
+ unordered_multimap(initializer_list<pair<Key, T>>, Allocator)
855
  -> unordered_multimap<Key, T, hash<Key>, equal_to<Key>, Allocator>;
856
 
857
  template<class Key, class T, class Hash, class Allocator>
858
+ unordered_multimap(initializer_list<pair<Key, T>>, typename see below::size_type,
859
  Hash, Allocator)
860
  -> unordered_multimap<Key, T, Hash, equal_to<Key>, Allocator>;
861
 
862
+ // swap
 
 
 
 
 
 
 
863
  template<class Key, class T, class Hash, class Pred, class Alloc>
864
  void swap(unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
865
  unordered_multimap<Key, T, Hash, Pred, Alloc>& y)
866
  noexcept(noexcept(x.swap(y)));
867
  }
 
869
 
870
  A `size_type` parameter type in an `unordered_multimap` deduction guide
871
  refers to the `size_type` member type of the type deduced by the
872
  deduction guide.
873
 
874
+ #### Constructors <a id="unord.multimap.cnstr">[[unord.multimap.cnstr]]</a>
875
 
876
  ``` cpp
877
  unordered_multimap() : unordered_multimap(size_type(see below)) { }
878
  explicit unordered_multimap(size_type n,
879
  const hasher& hf = hasher(),
 
909
  `l`) for the first form, or from the range \[`il.begin()`, `il.end()`)
910
  for the second form. `max_load_factor()` returns `1.0`.
911
 
912
  *Complexity:* Average case linear, worst case quadratic.
913
 
914
+ #### Modifiers <a id="unord.multimap.modifiers">[[unord.multimap.modifiers]]</a>
915
 
916
  ``` cpp
917
  template<class P>
918
  iterator insert(P&& obj);
919
  ```
920
 
921
+ *Constraints:* `is_constructible_v<value_type, P&&>` is `true`.
922
+
923
  *Effects:* Equivalent to: `return emplace(std::forward<P>(obj));`
924
 
 
 
 
925
  ``` cpp
926
  template<class P>
927
  iterator insert(const_iterator hint, P&& obj);
928
  ```
929
 
930
+ *Constraints:* `is_constructible_v<value_type, P&&>` is `true`.
931
+
932
  *Effects:* Equivalent to:
933
  `return emplace_hint(hint, std::forward<P>(obj));`
934
 
935
+ #### Erasure <a id="unord.multimap.erasure">[[unord.multimap.erasure]]</a>
 
 
 
936
 
937
  ``` cpp
938
+ template<class K, class T, class H, class P, class A, class Predicate>
939
+ typename unordered_multimap<K, T, H, P, A>::size_type
940
+ erase_if(unordered_multimap<K, T, H, P, A>& c, Predicate pred);
 
941
  ```
942
 
943
+ *Effects:* Equivalent to:
944
+
945
+ ``` cpp
946
+ auto original_size = c.size();
947
+ for (auto i = c.begin(), last = c.end(); i != last; ) {
948
+ if (pred(*i)) {
949
+ i = c.erase(i);
950
+ } else {
951
+ ++i;
952
+ }
953
+ }
954
+ return original_size - c.size();
955
+ ```
956
 
957
  ### Class template `unordered_set` <a id="unord.set">[[unord.set]]</a>
958
 
959
+ #### Overview <a id="unord.set.overview">[[unord.set.overview]]</a>
960
 
961
  An `unordered_set` is an unordered associative container that supports
962
  unique keys (an `unordered_set` contains at most one of each key value)
963
  and in which the elements’ keys are the elements themselves. The
964
  `unordered_set` class supports forward iterators.
965
 
966
+ An `unordered_set` meets all of the requirements of a container, of an
967
+ unordered associative container, and of an allocator-aware container (
968
+ [[container.alloc.req]]). It provides the operations described in the
969
+ preceding requirements table for unique keys; that is, an
970
+ `unordered_set` supports the `a_uniq` operations in that table, not the
971
+ `a_eq` operations. For an `unordered_set<Key>` the `key type` and the
972
+ value type are both `Key`. The `iterator` and `const_iterator` types are
973
+ both constant iterator types. It is unspecified whether they are the
974
  same type.
975
 
976
+ Subclause  [[unord.set]] only describes operations on `unordered_set`
977
+ that are not described in one of the requirement tables, or for which
978
+ there is additional semantic information.
979
 
980
  ``` cpp
981
  namespace std {
982
  template<class Key,
983
  class Hash = hash<Key>,
984
  class Pred = equal_to<Key>,
985
  class Allocator = allocator<Key>>
986
  class unordered_set {
987
  public:
988
+ // types
989
  using key_type = Key;
990
  using value_type = Key;
991
  using hasher = Hash;
992
  using key_equal = Pred;
993
  using allocator_type = Allocator;
 
1001
  using iterator = implementation-defined // type of unordered_set::iterator; // see [container.requirements]
1002
  using const_iterator = implementation-defined // type of unordered_set::const_iterator; // see [container.requirements]
1003
  using local_iterator = implementation-defined // type of unordered_set::local_iterator; // see [container.requirements]
1004
  using const_local_iterator = implementation-defined // type of unordered_set::const_local_iterator; // see [container.requirements]
1005
  using node_type = unspecified;
1006
+ using insert_return_type = insert-return-type<iterator, node_type>;
1007
 
1008
  // [unord.set.cnstr], construct/copy/destroy
1009
  unordered_set();
1010
  explicit unordered_set(size_type n,
1011
  const hasher& hf = hasher(),
 
1050
  is_nothrow_move_assignable_v<Hash> &&
1051
  is_nothrow_move_assignable_v<Pred>);
1052
  unordered_set& operator=(initializer_list<value_type>);
1053
  allocator_type get_allocator() const noexcept;
1054
 
1055
+ // iterators
1056
  iterator begin() noexcept;
1057
  const_iterator begin() const noexcept;
1058
  iterator end() noexcept;
1059
  const_iterator end() const noexcept;
1060
  const_iterator cbegin() const noexcept;
1061
  const_iterator cend() const noexcept;
1062
 
1063
+ // capacity
1064
+ [[nodiscard]] bool empty() const noexcept;
1065
  size_type size() const noexcept;
1066
  size_type max_size() const noexcept;
1067
 
1068
+ // modifiers
1069
  template<class... Args> pair<iterator, bool> emplace(Args&&... args);
1070
  template<class... Args> iterator emplace_hint(const_iterator position, Args&&... args);
1071
  pair<iterator, bool> insert(const value_type& obj);
1072
  pair<iterator, bool> insert(value_type&& obj);
1073
  iterator insert(const_iterator hint, const value_type& obj);
 
1097
  template<class H2, class P2>
1098
  void merge(unordered_multiset<Key, H2, P2, Allocator>& source);
1099
  template<class H2, class P2>
1100
  void merge(unordered_multiset<Key, H2, P2, Allocator>&& source);
1101
 
1102
+ // observers
1103
  hasher hash_function() const;
1104
  key_equal key_eq() const;
1105
 
1106
+ // set operations
1107
  iterator find(const key_type& k);
1108
  const_iterator find(const key_type& k) const;
1109
+ template<class K>
1110
+ iterator find(const K& k);
1111
+ template<class K>
1112
+ const_iterator find(const K& k) const;
1113
  size_type count(const key_type& k) const;
1114
+ template<class K>
1115
+ size_type count(const K& k) const;
1116
+ bool contains(const key_type& k) const;
1117
+ template<class K>
1118
+ bool contains(const K& k) const;
1119
  pair<iterator, iterator> equal_range(const key_type& k);
1120
  pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
1121
+ template<class K>
1122
+ pair<iterator, iterator> equal_range(const K& k);
1123
+ template<class K>
1124
+ pair<const_iterator, const_iterator> equal_range(const K& k) const;
1125
 
1126
+ // bucket interface
1127
  size_type bucket_count() const noexcept;
1128
  size_type max_bucket_count() const noexcept;
1129
  size_type bucket_size(size_type n) const;
1130
  size_type bucket(const key_type& k) const;
1131
  local_iterator begin(size_type n);
 
1133
  local_iterator end(size_type n);
1134
  const_local_iterator end(size_type n) const;
1135
  const_local_iterator cbegin(size_type n) const;
1136
  const_local_iterator cend(size_type n) const;
1137
 
1138
+ // hash policy
1139
  float load_factor() const noexcept;
1140
  float max_load_factor() const noexcept;
1141
  void max_load_factor(float z);
1142
  void rehash(size_type n);
1143
  void reserve(size_type n);
1144
  };
1145
 
1146
  template<class InputIterator,
1147
+ class Hash = hash<iter-value-type<InputIterator>>,
1148
+ class Pred = equal_to<iter-value-type<InputIterator>>,
1149
+ class Allocator = allocator<iter-value-type<InputIterator>>>
1150
  unordered_set(InputIterator, InputIterator, typename see below::size_type = see below,
1151
  Hash = Hash(), Pred = Pred(), Allocator = Allocator())
1152
+ -> unordered_set<iter-value-type<InputIterator>,
1153
  Hash, Pred, Allocator>;
1154
 
1155
  template<class T, class Hash = hash<T>,
1156
  class Pred = equal_to<T>, class Allocator = allocator<T>>
1157
  unordered_set(initializer_list<T>, typename see below::size_type = see below,
1158
  Hash = Hash(), Pred = Pred(), Allocator = Allocator())
1159
  -> unordered_set<T, Hash, Pred, Allocator>;
1160
 
1161
  template<class InputIterator, class Allocator>
1162
  unordered_set(InputIterator, InputIterator, typename see below::size_type, Allocator)
1163
+ -> unordered_set<iter-value-type<InputIterator>,
1164
+ hash<iter-value-type<InputIterator>>,
1165
+ equal_to<iter-value-type<InputIterator>>,
1166
  Allocator>;
1167
 
1168
  template<class InputIterator, class Hash, class Allocator>
1169
  unordered_set(InputIterator, InputIterator, typename see below::size_type,
1170
  Hash, Allocator)
1171
+ -> unordered_set<iter-value-type<InputIterator>, Hash,
1172
+ equal_to<iter-value-type<InputIterator>>,
1173
  Allocator>;
1174
 
1175
  template<class T, class Allocator>
1176
  unordered_set(initializer_list<T>, typename see below::size_type, Allocator)
1177
  -> unordered_set<T, hash<T>, equal_to<T>, Allocator>;
1178
 
1179
  template<class T, class Hash, class Allocator>
1180
  unordered_set(initializer_list<T>, typename see below::size_type, Hash, Allocator)
1181
  -> unordered_set<T, Hash, equal_to<T>, Allocator>;
1182
 
1183
+ // swap
 
 
 
 
 
 
 
1184
  template<class Key, class Hash, class Pred, class Alloc>
1185
  void swap(unordered_set<Key, Hash, Pred, Alloc>& x,
1186
  unordered_set<Key, Hash, Pred, Alloc>& y)
1187
  noexcept(noexcept(x.swap(y)));
1188
  }
1189
  ```
1190
 
1191
  A `size_type` parameter type in an `unordered_set` deduction guide
1192
+ refers to the `size_type` member type of the type deduced by the
1193
+ deduction guide.
1194
 
1195
+ #### Constructors <a id="unord.set.cnstr">[[unord.set.cnstr]]</a>
1196
 
1197
  ``` cpp
1198
  unordered_set() : unordered_set(size_type(see below)) { }
1199
  explicit unordered_set(size_type n,
1200
  const hasher& hf = hasher(),
 
1230
  `l`) for the first form, or from the range \[`il.begin()`, `il.end()`)
1231
  for the second form. `max_load_factor()` returns `1.0`.
1232
 
1233
  *Complexity:* Average case linear, worst case quadratic.
1234
 
1235
+ #### Erasure <a id="unord.set.erasure">[[unord.set.erasure]]</a>
1236
 
1237
  ``` cpp
1238
+ template<class K, class H, class P, class A, class Predicate>
1239
+ typename unordered_set<K, H, P, A>::size_type
1240
+ erase_if(unordered_set<K, H, P, A>& c, Predicate pred);
 
1241
  ```
1242
 
1243
+ *Effects:* Equivalent to:
1244
+
1245
+ ``` cpp
1246
+ auto original_size = c.size();
1247
+ for (auto i = c.begin(), last = c.end(); i != last; ) {
1248
+ if (pred(*i)) {
1249
+ i = c.erase(i);
1250
+ } else {
1251
+ ++i;
1252
+ }
1253
+ }
1254
+ return original_size - c.size();
1255
+ ```
1256
 
1257
  ### Class template `unordered_multiset` <a id="unord.multiset">[[unord.multiset]]</a>
1258
 
1259
+ #### Overview <a id="unord.multiset.overview">[[unord.multiset.overview]]</a>
1260
 
1261
  An `unordered_multiset` is an unordered associative container that
1262
  supports equivalent keys (an instance of `unordered_multiset` may
1263
  contain multiple copies of the same key value) and in which each
1264
  element’s key is the element itself. The `unordered_multiset` class
1265
  supports forward iterators.
1266
 
1267
+ An `unordered_multiset` meets all of the requirements of a container, of
1268
+ an unordered associative container, and of an allocator-aware container
1269
+ ([[container.alloc.req]]). It provides the operations described in the
1270
+ preceding requirements table for equivalent keys; that is, an
1271
+ `unordered_multiset` supports the `a_eq` operations in that table, not
1272
+ the `a_uniq` operations. For an `unordered_multiset<Key>` the `key type`
1273
+ and the value type are both `Key`. The `iterator` and `const_iterator`
1274
+ types are both constant iterator types. It is unspecified whether they
1275
+ are the same type.
1276
 
1277
+ Subclause  [[unord.multiset]] only describes operations on
1278
+ `unordered_multiset` that are not described in one of the requirement
1279
+ tables, or for which there is additional semantic information.
1280
 
1281
  ``` cpp
1282
  namespace std {
1283
  template<class Key,
1284
  class Hash = hash<Key>,
1285
  class Pred = equal_to<Key>,
1286
  class Allocator = allocator<Key>>
1287
  class unordered_multiset {
1288
  public:
1289
+ // types
1290
  using key_type = Key;
1291
  using value_type = Key;
1292
  using hasher = Hash;
1293
  using key_equal = Pred;
1294
  using allocator_type = Allocator;
 
1350
  is_nothrow_move_assignable_v<Hash> &&
1351
  is_nothrow_move_assignable_v<Pred>);
1352
  unordered_multiset& operator=(initializer_list<value_type>);
1353
  allocator_type get_allocator() const noexcept;
1354
 
1355
+ // iterators
1356
  iterator begin() noexcept;
1357
  const_iterator begin() const noexcept;
1358
  iterator end() noexcept;
1359
  const_iterator end() const noexcept;
1360
  const_iterator cbegin() const noexcept;
1361
  const_iterator cend() const noexcept;
1362
 
1363
+ // capacity
1364
+ [[nodiscard]] bool empty() const noexcept;
1365
  size_type size() const noexcept;
1366
  size_type max_size() const noexcept;
1367
 
1368
+ // modifiers
1369
  template<class... Args> iterator emplace(Args&&... args);
1370
  template<class... Args> iterator emplace_hint(const_iterator position, Args&&... args);
1371
  iterator insert(const value_type& obj);
1372
  iterator insert(value_type&& obj);
1373
  iterator insert(const_iterator hint, const value_type& obj);
 
1397
  template<class H2, class P2>
1398
  void merge(unordered_set<Key, H2, P2, Allocator>& source);
1399
  template<class H2, class P2>
1400
  void merge(unordered_set<Key, H2, P2, Allocator>&& source);
1401
 
1402
+ // observers
1403
  hasher hash_function() const;
1404
  key_equal key_eq() const;
1405
 
1406
+ // set operations
1407
  iterator find(const key_type& k);
1408
  const_iterator find(const key_type& k) const;
1409
+ template<class K>
1410
+ iterator find(const K& k);
1411
+ template<class K>
1412
+ const_iterator find(const K& k) const;
1413
  size_type count(const key_type& k) const;
1414
+ template<class K>
1415
+ size_type count(const K& k) const;
1416
+ bool contains(const key_type& k) const;
1417
+ template<class K>
1418
+ bool contains(const K& k) const;
1419
  pair<iterator, iterator> equal_range(const key_type& k);
1420
  pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
1421
+ template<class K>
1422
+ pair<iterator, iterator> equal_range(const K& k);
1423
+ template<class K>
1424
+ pair<const_iterator, const_iterator> equal_range(const K& k) const;
1425
 
1426
+ // bucket interface
1427
  size_type bucket_count() const noexcept;
1428
  size_type max_bucket_count() const noexcept;
1429
  size_type bucket_size(size_type n) const;
1430
  size_type bucket(const key_type& k) const;
1431
  local_iterator begin(size_type n);
 
1433
  local_iterator end(size_type n);
1434
  const_local_iterator end(size_type n) const;
1435
  const_local_iterator cbegin(size_type n) const;
1436
  const_local_iterator cend(size_type n) const;
1437
 
1438
+ // hash policy
1439
  float load_factor() const noexcept;
1440
  float max_load_factor() const noexcept;
1441
  void max_load_factor(float z);
1442
  void rehash(size_type n);
1443
  void reserve(size_type n);
1444
  };
1445
 
1446
  template<class InputIterator,
1447
+ class Hash = hash<iter-value-type<InputIterator>>,
1448
+ class Pred = equal_to<iter-value-type<InputIterator>>,
1449
+ class Allocator = allocator<iter-value-type<InputIterator>>>
1450
  unordered_multiset(InputIterator, InputIterator, see below::size_type = see below,
1451
  Hash = Hash(), Pred = Pred(), Allocator = Allocator())
1452
+ -> unordered_multiset<iter-value-type<InputIterator>,
1453
  Hash, Pred, Allocator>;
1454
 
1455
  template<class T, class Hash = hash<T>,
1456
  class Pred = equal_to<T>, class Allocator = allocator<T>>
1457
  unordered_multiset(initializer_list<T>, typename see below::size_type = see below,
1458
  Hash = Hash(), Pred = Pred(), Allocator = Allocator())
1459
  -> unordered_multiset<T, Hash, Pred, Allocator>;
1460
 
1461
  template<class InputIterator, class Allocator>
1462
  unordered_multiset(InputIterator, InputIterator, typename see below::size_type, Allocator)
1463
+ -> unordered_multiset<iter-value-type<InputIterator>,
1464
+ hash<iter-value-type<InputIterator>>,
1465
+ equal_to<iter-value-type<InputIterator>>,
1466
  Allocator>;
1467
 
1468
  template<class InputIterator, class Hash, class Allocator>
1469
  unordered_multiset(InputIterator, InputIterator, typename see below::size_type,
1470
  Hash, Allocator)
1471
+ -> unordered_multiset<iter-value-type<InputIterator>, Hash,
1472
+ equal_to<iter-value-type<InputIterator>>,
1473
  Allocator>;
1474
 
1475
  template<class T, class Allocator>
1476
  unordered_multiset(initializer_list<T>, typename see below::size_type, Allocator)
1477
  -> unordered_multiset<T, hash<T>, equal_to<T>, Allocator>;
1478
 
1479
  template<class T, class Hash, class Allocator>
1480
  unordered_multiset(initializer_list<T>, typename see below::size_type, Hash, Allocator)
1481
  -> unordered_multiset<T, Hash, equal_to<T>, Allocator>;
1482
 
1483
+ // swap
 
 
 
 
 
 
 
1484
  template<class Key, class Hash, class Pred, class Alloc>
1485
  void swap(unordered_multiset<Key, Hash, Pred, Alloc>& x,
1486
  unordered_multiset<Key, Hash, Pred, Alloc>& y)
1487
  noexcept(noexcept(x.swap(y)));
1488
  }
1489
  ```
1490
 
1491
  A `size_type` parameter type in an `unordered_multiset` deduction guide
1492
+ refers to the `size_type` member type of the type deduced by the
1493
+ deduction guide.
1494
 
1495
+ #### Constructors <a id="unord.multiset.cnstr">[[unord.multiset.cnstr]]</a>
1496
 
1497
  ``` cpp
1498
  unordered_multiset() : unordered_multiset(size_type(see below)) { }
1499
  explicit unordered_multiset(size_type n,
1500
  const hasher& hf = hasher(),
 
1530
  `l`) for the first form, or from the range \[`il.begin()`, `il.end()`)
1531
  for the second form. `max_load_factor()` returns `1.0`.
1532
 
1533
  *Complexity:* Average case linear, worst case quadratic.
1534
 
1535
+ #### Erasure <a id="unord.multiset.erasure">[[unord.multiset.erasure]]</a>
1536
 
1537
  ``` cpp
1538
+ template<class K, class H, class P, class A, class Predicate>
1539
+ typename unordered_multiset<K, H, P, A>::size_type
1540
+ erase_if(unordered_multiset<K, H, P, A>& c, Predicate pred);
 
1541
  ```
1542
 
1543
+ *Effects:* Equivalent to:
1544
+
1545
+ ``` cpp
1546
+ auto original_size = c.size();
1547
+ for (auto i = c.begin(), last = c.end(); i != last; ) {
1548
+ if (pred(*i)) {
1549
+ i = c.erase(i);
1550
+ } else {
1551
+ ++i;
1552
+ }
1553
+ }
1554
+ return original_size - c.size();
1555
+ ```
1556