From Jason Turner

[unord]

C++14 → C++17 73.7 KB 968 lines
Current Draft | LaTeX Source
Archived: C++14 | C++17
Markdown: C++14 | C++17
Explore in Adventure Game

Diff to HTML by rtfpessoa

Files changed (1) hide show
  1. tmp/tmpkvwomio4/{from.md → to.md} +695 -247
tmp/tmpkvwomio4/{from.md → to.md} RENAMED
@@ -4,40 +4,45 @@
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
  ### Header `<unordered_map>` synopsis <a id="unord.map.syn">[[unord.map.syn]]</a>
10
 
11
  ``` cpp
12
  #include <initializer_list>
13
 
14
  namespace std {
15
-
16
- // [unord.map], class template unordered_map:
17
  template <class Key,
18
  class T,
19
  class Hash = hash<Key>,
20
- class Pred = std::equal_to<Key>,
21
- class Alloc = std::allocator<std::pair<const Key, T> > >
22
  class unordered_map;
23
 
24
- // [unord.multimap], class template unordered_multimap:
25
  template <class Key,
26
  class T,
27
  class Hash = hash<Key>,
28
- class Pred = std::equal_to<Key>,
29
- class Alloc = std::allocator<std::pair<const Key, T> > >
30
  class unordered_multimap;
31
 
32
  template <class Key, class T, class Hash, class Pred, class Alloc>
33
  void swap(unordered_map<Key, T, Hash, Pred, Alloc>& x,
34
- unordered_map<Key, T, Hash, Pred, Alloc>& y);
 
35
 
36
  template <class Key, class T, class Hash, class Pred, class Alloc>
37
  void swap(unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
38
- unordered_multimap<Key, T, Hash, Pred, Alloc>& y);
 
39
 
40
  template <class Key, class T, class Hash, class Pred, class Alloc>
41
  bool operator==(const unordered_map<Key, T, Hash, Pred, Alloc>& a,
42
  const unordered_map<Key, T, Hash, Pred, Alloc>& b);
43
  template <class Key, class T, class Hash, class Pred, class Alloc>
@@ -47,41 +52,60 @@ namespace std {
47
  bool operator==(const unordered_multimap<Key, T, Hash, Pred, Alloc>& a,
48
  const unordered_multimap<Key, T, Hash, Pred, Alloc>& b);
49
  template <class Key, class T, class Hash, class Pred, class Alloc>
50
  bool operator!=(const unordered_multimap<Key, T, Hash, Pred, Alloc>& a,
51
  const unordered_multimap<Key, T, Hash, Pred, Alloc>& b);
52
- } // namespace std
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
53
  ```
54
 
55
  ### Header `<unordered_set>` synopsis <a id="unord.set.syn">[[unord.set.syn]]</a>
56
 
57
  ``` cpp
58
  #include <initializer_list>
59
 
60
  namespace std {
61
-
62
- // [unord.set], class template unordered_set:
63
  template <class Key,
64
  class Hash = hash<Key>,
65
- class Pred = std::equal_to<Key>,
66
- class Alloc = std::allocator<Key> >
67
  class unordered_set;
68
 
69
- // [unord.multiset], class template unordered_multiset:
70
  template <class Key,
71
  class Hash = hash<Key>,
72
- class Pred = std::equal_to<Key>,
73
- class Alloc = std::allocator<Key> >
74
  class unordered_multiset;
75
 
76
  template <class Key, class Hash, class Pred, class Alloc>
77
  void swap(unordered_set<Key, Hash, Pred, Alloc>& x,
78
- unordered_set<Key, Hash, Pred, Alloc>& y);
 
79
 
80
  template <class Key, class Hash, class Pred, class Alloc>
81
  void swap(unordered_multiset<Key, Hash, Pred, Alloc>& x,
82
- unordered_multiset<Key, Hash, Pred, Alloc>& y);
 
83
 
84
  template <class Key, class Hash, class Pred, class Alloc>
85
  bool operator==(const unordered_set<Key, Hash, Pred, Alloc>& a,
86
  const unordered_set<Key, Hash, Pred, Alloc>& b);
87
  template <class Key, class Hash, class Pred, class Alloc>
@@ -91,11 +115,25 @@ namespace std {
91
  bool operator==(const unordered_multiset<Key, Hash, Pred, Alloc>& a,
92
  const unordered_multiset<Key, Hash, Pred, Alloc>& b);
93
  template <class Key, class Hash, class Pred, class Alloc>
94
  bool operator!=(const unordered_multiset<Key, Hash, Pred, Alloc>& a,
95
  const unordered_multiset<Key, Hash, Pred, Alloc>& b);
96
- } // namespace std
 
 
 
 
 
 
 
 
 
 
 
 
 
 
97
  ```
98
 
99
  ### Class template `unordered_map` <a id="unord.map">[[unord.map]]</a>
100
 
101
  #### Class template `unordered_map` overview <a id="unord.map.overview">[[unord.map.overview]]</a>
@@ -110,46 +148,47 @@ an unordered associative container, and of an allocator-aware container
110
  (Table  [[tab:containers.allocatoraware]]). It provides the operations
111
  described in the preceding requirements table for unique keys; that is,
112
  an `unordered_map` supports the `a_uniq` operations in that table, not
113
  the `a_eq` operations. For an `unordered_map<Key, T>` the `key type` is
114
  `Key`, the mapped type is `T`, and the value type is
115
- `std::pair<const Key, T>`.
116
 
117
  This section only describes operations on `unordered_map` that are not
118
  described in one of the requirement tables, or for which there is
119
  additional semantic information.
120
 
121
  ``` cpp
122
  namespace std {
123
  template <class Key,
124
  class T,
125
  class Hash = hash<Key>,
126
- class Pred = std::equal_to<Key>,
127
- class Allocator = std::allocator<std::pair<const Key, T> > >
128
- class unordered_map
129
- {
130
  public:
131
- // types
132
- typedef Key key_type;
133
- typedef std::pair<const Key, T> value_type;
134
- typedef T mapped_type;
135
- typedef Hash hasher;
136
- typedef Pred key_equal;
137
- typedef Allocator allocator_type;
138
- typedef typename allocator_traits<Allocator>::pointer pointer;
139
- typedef typename allocator_traits<Allocator>::const_pointer const_pointer;
140
- typedef value_type& reference;
141
- typedef const value_type& const_reference;
142
- typedef implementation-defined size_type;
143
- typedef implementation-defined difference_type;
144
 
145
- typedef implementation-defined iterator;
146
- typedef implementation-defined const_iterator;
147
- typedef implementation-defined local_iterator;
148
- typedef implementation-defined const_local_iterator;
 
 
149
 
150
- // construct/destroy/copy
151
  unordered_map();
152
  explicit unordered_map(size_type n,
153
  const hasher& hf = hasher(),
154
  const key_equal& eql = key_equal(),
155
  const allocator_type& a = allocator_type());
@@ -162,12 +201,12 @@ namespace std {
162
  unordered_map(const unordered_map&);
163
  unordered_map(unordered_map&&);
164
  explicit unordered_map(const Allocator&);
165
  unordered_map(const unordered_map&, const Allocator&);
166
  unordered_map(unordered_map&&, const Allocator&);
167
- unordered_map(initializer_list<value_type>,
168
- size_type = see below,
169
  const hasher& hf = hasher(),
170
  const key_equal& eql = key_equal(),
171
  const allocator_type& a = allocator_type());
172
  unordered_map(size_type n, const allocator_type& a)
173
  : unordered_map(n, hasher(), key_equal(), a) { }
@@ -185,61 +224,101 @@ namespace std {
185
  unordered_map(initializer_list<value_type> il, size_type n, const hasher& hf,
186
  const allocator_type& a)
187
  : unordered_map(il, n, hf, key_equal(), a) { }
188
  ~unordered_map();
189
  unordered_map& operator=(const unordered_map&);
190
- unordered_map& operator=(unordered_map&&);
 
 
 
191
  unordered_map& operator=(initializer_list<value_type>);
192
  allocator_type get_allocator() const noexcept;
193
 
194
- // size and capacity
195
- bool empty() const noexcept;
196
- size_type size() const noexcept;
197
- size_type max_size() const noexcept;
198
-
199
- // iterators
200
  iterator begin() noexcept;
201
  const_iterator begin() const noexcept;
202
  iterator end() noexcept;
203
  const_iterator end() const noexcept;
204
  const_iterator cbegin() const noexcept;
205
  const_iterator cend() const noexcept;
206
 
207
- // modifiers
 
 
 
 
 
208
  template <class... Args> pair<iterator, bool> emplace(Args&&... args);
209
  template <class... Args> iterator emplace_hint(const_iterator position, Args&&... args);
210
  pair<iterator, bool> insert(const value_type& obj);
 
211
  template <class P> pair<iterator, bool> insert(P&& obj);
212
  iterator insert(const_iterator hint, const value_type& obj);
 
213
  template <class P> iterator insert(const_iterator hint, P&& obj);
214
  template <class InputIterator> void insert(InputIterator first, InputIterator last);
215
  void insert(initializer_list<value_type>);
216
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
217
  iterator erase(const_iterator position);
218
  size_type erase(const key_type& k);
219
  iterator erase(const_iterator first, const_iterator last);
 
 
 
 
220
  void clear() noexcept;
221
 
222
- void swap(unordered_map&);
 
 
 
 
 
 
 
223
 
224
- // observers
225
  hasher hash_function() const;
226
  key_equal key_eq() const;
227
 
228
- // lookup
229
  iterator find(const key_type& k);
230
  const_iterator find(const key_type& k) const;
231
  size_type count(const key_type& k) const;
232
- std::pair<iterator, iterator> equal_range(const key_type& k);
233
- std::pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
234
 
 
235
  mapped_type& operator[](const key_type& k);
236
  mapped_type& operator[](key_type&& k);
237
  mapped_type& at(const key_type& k);
238
  const mapped_type& at(const key_type& k) const;
239
 
240
- // bucket interface
241
  size_type bucket_count() const noexcept;
242
  size_type max_bucket_count() const noexcept;
243
  size_type bucket_size(size_type n) const;
244
  size_type bucket(const key_type& k) const;
245
  local_iterator begin(size_type n);
@@ -247,31 +326,84 @@ namespace std {
247
  local_iterator end(size_type n);
248
  const_local_iterator end(size_type n) const;
249
  const_local_iterator cbegin(size_type n) const;
250
  const_local_iterator cend(size_type n) const;
251
 
252
- // hash policy
253
  float load_factor() const noexcept;
254
  float max_load_factor() const noexcept;
255
  void max_load_factor(float z);
256
  void rehash(size_type n);
257
  void reserve(size_type n);
258
  };
259
 
260
- template <class Key, class T, class Hash, class Pred, class Alloc>
261
- void swap(unordered_map<Key, T, Hash, Pred, Alloc>& x,
262
- unordered_map<Key, T, Hash, Pred, Alloc>& y);
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
263
 
264
  template <class Key, class T, class Hash, class Pred, class Alloc>
265
  bool operator==(const unordered_map<Key, T, Hash, Pred, Alloc>& a,
266
  const unordered_map<Key, T, Hash, Pred, Alloc>& b);
267
  template <class Key, class T, class Hash, class Pred, class Alloc>
268
  bool operator!=(const unordered_map<Key, T, Hash, Pred, Alloc>& a,
269
  const unordered_map<Key, T, Hash, Pred, Alloc>& b);
 
 
 
 
 
 
270
  }
271
  ```
272
 
 
 
 
 
273
  #### `unordered_map` constructors <a id="unord.map.cnstr">[[unord.map.cnstr]]</a>
274
 
275
  ``` cpp
276
  unordered_map() : unordered_map(size_type(see below)) { }
277
  explicit unordered_map(size_type n,
@@ -279,53 +411,52 @@ explicit unordered_map(size_type n,
279
  const key_equal& eql = key_equal(),
280
  const allocator_type& a = allocator_type());
281
  ```
282
 
283
  *Effects:* Constructs an empty `unordered_map` using the specified hash
284
- function, key equality function, and allocator, and using at least *`n`*
285
  buckets. For the default constructor, the number of buckets is
286
- *implementation-defined*. `max_load_factor()` returns 1.0.
287
 
288
  *Complexity:* Constant.
289
 
290
  ``` cpp
291
  template <class InputIterator>
292
  unordered_map(InputIterator f, InputIterator l,
293
  size_type n = see below,
294
  const hasher& hf = hasher(),
295
  const key_equal& eql = key_equal(),
296
  const allocator_type& a = allocator_type());
 
 
 
 
 
297
  ```
298
 
299
  *Effects:* Constructs an empty `unordered_map` using the specified hash
300
- function, key equality function, and allocator, and using at least *`n`*
301
- buckets. If *`n`* is not provided, the number of buckets is
302
- *implementation-defined*. Then inserts elements from the range
303
- `[`*`f`*`, `*`l`*`)`. `max_load_factor()` returns 1.0.
 
304
 
305
  *Complexity:* Average case linear, worst case quadratic.
306
 
307
  #### `unordered_map` element access <a id="unord.map.elem">[[unord.map.elem]]</a>
308
 
309
  ``` cpp
310
  mapped_type& operator[](const key_type& k);
 
 
 
 
 
311
  mapped_type& operator[](key_type&& k);
312
  ```
313
 
314
- *Requires:* `mapped_type` shall be `DefaultInsertable` into `*this`. For
315
- the first operator, `key_type` shall be `CopyInsertable` into `*this`.
316
- For the second operator, `key_type` shall be `MoveConstructible`.
317
-
318
- *Effects:* If the `unordered_map` does not already contain an element
319
- whose key is equivalent to *`k`*, the first operator inserts the value
320
- `value_type(k, mapped_type())` and the second operator inserts the value
321
- `value_type(std::move(k), mapped_type())`.
322
-
323
- *Returns:* A reference to `x.second`, where `x` is the (unique) element
324
- whose key is equivalent to *`k`*.
325
-
326
- *Complexity:* Average case 𝑂(1), worst case 𝑂(`size()`).
327
 
328
  ``` cpp
329
  mapped_type& at(const key_type& k);
330
  const mapped_type& at(const key_type& k) const;
331
  ```
@@ -341,35 +472,126 @@ is present.
341
  ``` cpp
342
  template <class P>
343
  pair<iterator, bool> insert(P&& obj);
344
  ```
345
 
346
- *Effects:* Equivalent to `return emplace(std::forward<P>(obj))`.
347
 
348
  *Remarks:* This signature shall not participate in overload resolution
349
- unless `std::is_constructible<value_type, P&&>::value` is `true`.
350
 
351
  ``` cpp
352
  template <class P>
353
  iterator insert(const_iterator hint, P&& obj);
354
  ```
355
 
356
- *Effects:* Equivalent to
357
- `return emplace_hint(hint, std::forward<P>(obj))`.
358
 
359
  *Remarks:* This signature shall not participate in overload resolution
360
- unless `std::is_constructible<value_type, P&&>::value` is `true`.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
361
 
362
  #### `unordered_map` swap <a id="unord.map.swap">[[unord.map.swap]]</a>
363
 
364
  ``` cpp
365
  template <class Key, class T, class Hash, class Pred, class Alloc>
366
  void swap(unordered_map<Key, T, Hash, Pred, Alloc>& x,
367
- unordered_map<Key, T, Hash, Pred, Alloc>& y);
 
368
  ```
369
 
370
- *Effects:* `x.swap(y)`.
371
 
372
  ### Class template `unordered_multimap` <a id="unord.multimap">[[unord.multimap]]</a>
373
 
374
  #### Class template `unordered_multimap` overview <a id="unord.multimap.overview">[[unord.multimap.overview]]</a>
375
 
@@ -384,46 +606,46 @@ container, of an unordered associative container, and of an
384
  allocator-aware container (Table  [[tab:containers.allocatoraware]]). It
385
  provides the operations described in the preceding requirements table
386
  for equivalent keys; that is, an `unordered_multimap` supports the
387
  `a_eq` operations in that table, not the `a_uniq` operations. For an
388
  `unordered_multimap<Key, T>` the `key type` is `Key`, the mapped type is
389
- `T`, and the value type is `std::pair<const Key, T>`.
390
 
391
  This section only describes operations on `unordered_multimap` that are
392
  not described in one of the requirement tables, or for which there is
393
  additional semantic information.
394
 
395
  ``` cpp
396
  namespace std {
397
  template <class Key,
398
  class T,
399
  class Hash = hash<Key>,
400
- class Pred = std::equal_to<Key>,
401
- class Allocator = std::allocator<std::pair<const Key, T> > >
402
- class unordered_multimap
403
- {
404
  public:
405
- // types
406
- typedef Key key_type;
407
- typedef std::pair<const Key, T> value_type;
408
- typedef T mapped_type;
409
- typedef Hash hasher;
410
- typedef Pred key_equal;
411
- typedef Allocator allocator_type;
412
- typedef typename allocator_traits<Allocator>::pointer pointer;
413
- typedef typename allocator_traits<Allocator>::const_pointer const_pointer;
414
- typedef value_type& reference;
415
- typedef const value_type& const_reference;
416
- typedef implementation-defined size_type;
417
- typedef implementation-defined difference_type;
418
 
419
- typedef implementation-defined iterator;
420
- typedef implementation-defined const_iterator;
421
- typedef implementation-defined local_iterator;
422
- typedef implementation-defined const_local_iterator;
 
423
 
424
- // construct/destroy/copy
425
  unordered_multimap();
426
  explicit unordered_multimap(size_type n,
427
  const hasher& hf = hasher(),
428
  const key_equal& eql = key_equal(),
429
  const allocator_type& a = allocator_type());
@@ -436,12 +658,12 @@ namespace std {
436
  unordered_multimap(const unordered_multimap&);
437
  unordered_multimap(unordered_multimap&&);
438
  explicit unordered_multimap(const Allocator&);
439
  unordered_multimap(const unordered_multimap&, const Allocator&);
440
  unordered_multimap(unordered_multimap&&, const Allocator&);
441
- unordered_multimap(initializer_list<value_type>,
442
- size_type = see below,
443
  const hasher& hf = hasher(),
444
  const key_equal& eql = key_equal(),
445
  const allocator_type& a = allocator_type());
446
  unordered_multimap(size_type n, const allocator_type& a)
447
  : unordered_multimap(n, hasher(), key_equal(), a) { }
@@ -459,56 +681,78 @@ namespace std {
459
  unordered_multimap(initializer_list<value_type> il, size_type n, const hasher& hf,
460
  const allocator_type& a)
461
  : unordered_multimap(il, n, hf, key_equal(), a) { }
462
  ~unordered_multimap();
463
  unordered_multimap& operator=(const unordered_multimap&);
464
- unordered_multimap& operator=(unordered_multimap&&);
 
 
 
465
  unordered_multimap& operator=(initializer_list<value_type>);
466
  allocator_type get_allocator() const noexcept;
467
 
468
- // size and capacity
469
- bool empty() const noexcept;
470
- size_type size() const noexcept;
471
- size_type max_size() const noexcept;
472
-
473
- // iterators
474
  iterator begin() noexcept;
475
  const_iterator begin() const noexcept;
476
  iterator end() noexcept;
477
  const_iterator end() const noexcept;
478
  const_iterator cbegin() const noexcept;
479
  const_iterator cend() const noexcept;
480
 
481
- // modifiers
 
 
 
 
 
482
  template <class... Args> iterator emplace(Args&&... args);
483
  template <class... Args> iterator emplace_hint(const_iterator position, Args&&... args);
484
  iterator insert(const value_type& obj);
 
485
  template <class P> iterator insert(P&& obj);
486
  iterator insert(const_iterator hint, const value_type& obj);
 
487
  template <class P> iterator insert(const_iterator hint, P&& obj);
488
  template <class InputIterator> void insert(InputIterator first, InputIterator last);
489
  void insert(initializer_list<value_type>);
490
 
 
 
 
 
 
 
491
  iterator erase(const_iterator position);
492
  size_type erase(const key_type& k);
493
  iterator erase(const_iterator first, const_iterator last);
 
 
 
 
494
  void clear() noexcept;
495
 
496
- void swap(unordered_multimap&);
 
 
 
 
 
 
 
497
 
498
- // observers
499
  hasher hash_function() const;
500
  key_equal key_eq() const;
501
 
502
- // lookup
503
  iterator find(const key_type& k);
504
  const_iterator find(const key_type& k) const;
505
  size_type count(const key_type& k) const;
506
- std::pair<iterator, iterator> equal_range(const key_type& k);
507
- std::pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
508
 
509
- // bucket interface
510
  size_type bucket_count() const noexcept;
511
  size_type max_bucket_count() const noexcept;
512
  size_type bucket_size(size_type n) const;
513
  size_type bucket(const key_type& k) const;
514
  local_iterator begin(size_type n);
@@ -524,23 +768,78 @@ namespace std {
524
  void max_load_factor(float z);
525
  void rehash(size_type n);
526
  void reserve(size_type n);
527
  };
528
 
529
- template <class Key, class T, class Hash, class Pred, class Alloc>
530
- void swap(unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
531
- unordered_multimap<Key, T, Hash, Pred, Alloc>& y);
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
532
 
533
  template <class Key, class T, class Hash, class Pred, class Alloc>
534
  bool operator==(const unordered_multimap<Key, T, Hash, Pred, Alloc>& a,
535
  const unordered_multimap<Key, T, Hash, Pred, Alloc>& b);
536
  template <class Key, class T, class Hash, class Pred, class Alloc>
537
  bool operator!=(const unordered_multimap<Key, T, Hash, Pred, Alloc>& a,
538
  const unordered_multimap<Key, T, Hash, Pred, Alloc>& b);
 
 
 
 
 
 
539
  }
540
  ```
541
 
 
 
 
 
542
  #### `unordered_multimap` constructors <a id="unord.multimap.cnstr">[[unord.multimap.cnstr]]</a>
543
 
544
  ``` cpp
545
  unordered_multimap() : unordered_multimap(size_type(see below)) { }
546
  explicit unordered_multimap(size_type n,
@@ -548,65 +847,72 @@ explicit unordered_multimap(size_type n,
548
  const key_equal& eql = key_equal(),
549
  const allocator_type& a = allocator_type());
550
  ```
551
 
552
  *Effects:* Constructs an empty `unordered_multimap` using the specified
553
- hash function, key equality function, and allocator, and using at least
554
- *`n`* buckets. For the default constructor, the number of buckets is
555
- *implementation-defined*. `max_load_factor()` returns 1.0.
556
 
557
  *Complexity:* Constant.
558
 
559
  ``` cpp
560
  template <class InputIterator>
561
  unordered_multimap(InputIterator f, InputIterator l,
562
  size_type n = see below,
563
  const hasher& hf = hasher(),
564
  const key_equal& eql = key_equal(),
565
  const allocator_type& a = allocator_type());
 
 
 
 
 
566
  ```
567
 
568
  *Effects:* Constructs an empty `unordered_multimap` using the specified
569
- hash function, key equality function, and allocator, and using at least
570
- *`n`* buckets. If *`n`* is not provided, the number of buckets is
571
- *implementation-defined*. Then inserts elements from the range
572
- `[`*`f`*`, `*`l`*`)`. `max_load_factor()` returns 1.0.
 
573
 
574
  *Complexity:* Average case linear, worst case quadratic.
575
 
576
  #### `unordered_multimap` modifiers <a id="unord.multimap.modifiers">[[unord.multimap.modifiers]]</a>
577
 
578
  ``` cpp
579
  template <class P>
580
  iterator insert(P&& obj);
581
  ```
582
 
583
- *Effects:* Equivalent to `return emplace(std::forward<P>(obj))`.
584
 
585
  *Remarks:* This signature shall not participate in overload resolution
586
- unless `std::is_constructible<value_type, P&&>::value` is `true`.
587
 
588
  ``` cpp
589
  template <class P>
590
  iterator insert(const_iterator hint, P&& obj);
591
  ```
592
 
593
- *Effects:* Equivalent to
594
- `return emplace_hint(hint, std::forward<P>(obj))`.
595
 
596
  *Remarks:* This signature shall not participate in overload resolution
597
- unless `std::is_constructible<value_type, P&&>::value` is `true`.
598
 
599
  #### `unordered_multimap` swap <a id="unord.multimap.swap">[[unord.multimap.swap]]</a>
600
 
601
  ``` cpp
602
  template <class Key, class T, class Hash, class Pred, class Alloc>
603
  void swap(unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
604
- unordered_multimap<Key, T, Hash, Pred, Alloc>& y);
 
605
  ```
606
 
607
- *Effects:* `x.swap(y)`.
608
 
609
  ### Class template `unordered_set` <a id="unord.set">[[unord.set]]</a>
610
 
611
  #### Class template `unordered_set` overview <a id="unord.set.overview">[[unord.set.overview]]</a>
612
 
@@ -620,45 +926,46 @@ an unordered associative container, and of an allocator-aware container
620
  (Table  [[tab:containers.allocatoraware]]). It provides the operations
621
  described in the preceding requirements table for unique keys; that is,
622
  an `unordered_set` supports the `a_uniq` operations in that table, not
623
  the `a_eq` operations. For an `unordered_set<Key>` the `key type` and
624
  the value type are both `Key`. The `iterator` and `const_iterator` types
625
- are both const iterator types. It is unspecified whether they are the
626
  same type.
627
 
628
  This section only describes operations on `unordered_set` that are not
629
  described in one of the requirement tables, or for which there is
630
  additional semantic information.
631
 
632
  ``` cpp
633
  namespace std {
634
  template <class Key,
635
  class Hash = hash<Key>,
636
- class Pred = std::equal_to<Key>,
637
- class Allocator = std::allocator<Key> >
638
- class unordered_set
639
- {
640
  public:
641
- // types
642
- typedef Key key_type;
643
- typedef Key value_type;
644
- typedef Hash hasher;
645
- typedef Pred key_equal;
646
- typedef Allocator allocator_type;
647
- typedef typename allocator_traits<Allocator>::pointer pointer;
648
- typedef typename allocator_traits<Allocator>::const_pointer const_pointer;
649
- typedef value_type& reference;
650
- typedef const value_type& const_reference;
651
- typedef implementation-defined size_type;
652
- typedef implementation-defined difference_type;
653
 
654
- typedef implementation-defined iterator;
655
- typedef implementation-defined const_iterator;
656
- typedef implementation-defined local_iterator;
657
- typedef implementation-defined const_local_iterator;
 
 
658
 
659
- // construct/destroy/copy
660
  unordered_set();
661
  explicit unordered_set(size_type n,
662
  const hasher& hf = hasher(),
663
  const key_equal& eql = key_equal(),
664
  const allocator_type& a = allocator_type());
@@ -671,12 +978,12 @@ namespace std {
671
  unordered_set(const unordered_set&);
672
  unordered_set(unordered_set&&);
673
  explicit unordered_set(const Allocator&);
674
  unordered_set(const unordered_set&, const Allocator&);
675
  unordered_set(unordered_set&&, const Allocator&);
676
- unordered_set(initializer_list<value_type>,
677
- size_type = see below,
678
  const hasher& hf = hasher(),
679
  const key_equal& eql = key_equal(),
680
  const allocator_type& a = allocator_type());
681
  unordered_set(size_type n, const allocator_type& a)
682
  : unordered_set(n, hasher(), key_equal(), a) { }
@@ -694,56 +1001,76 @@ namespace std {
694
  unordered_set(initializer_list<value_type> il, size_type n, const hasher& hf,
695
  const allocator_type& a)
696
  : unordered_set(il, n, hf, key_equal(), a) { }
697
  ~unordered_set();
698
  unordered_set& operator=(const unordered_set&);
699
- unordered_set& operator=(unordered_set&&);
 
 
 
700
  unordered_set& operator=(initializer_list<value_type>);
701
  allocator_type get_allocator() const noexcept;
702
 
703
- // size and capacity
704
- bool empty() const noexcept;
705
- size_type size() const noexcept;
706
- size_type max_size() const noexcept;
707
-
708
- // iterators
709
  iterator begin() noexcept;
710
  const_iterator begin() const noexcept;
711
  iterator end() noexcept;
712
  const_iterator end() const noexcept;
713
  const_iterator cbegin() const noexcept;
714
  const_iterator cend() const noexcept;
715
 
716
- // modifiers
 
 
 
 
 
717
  template <class... Args> pair<iterator, bool> emplace(Args&&... args);
718
  template <class... Args> iterator emplace_hint(const_iterator position, Args&&... args);
719
  pair<iterator, bool> insert(const value_type& obj);
720
  pair<iterator, bool> insert(value_type&& obj);
721
  iterator insert(const_iterator hint, const value_type& obj);
722
  iterator insert(const_iterator hint, value_type&& obj);
723
  template <class InputIterator> void insert(InputIterator first, InputIterator last);
724
  void insert(initializer_list<value_type>);
725
 
 
 
 
 
 
 
726
  iterator erase(const_iterator position);
727
  size_type erase(const key_type& k);
728
  iterator erase(const_iterator first, const_iterator last);
 
 
 
 
729
  void clear() noexcept;
730
 
731
- void swap(unordered_set&);
 
 
 
 
 
 
 
732
 
733
- // observers
734
  hasher hash_function() const;
735
  key_equal key_eq() const;
736
 
737
- // lookup
738
  iterator find(const key_type& k);
739
  const_iterator find(const key_type& k) const;
740
  size_type count(const key_type& k) const;
741
- std::pair<iterator, iterator> equal_range(const key_type& k);
742
- std::pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
743
 
744
- // bucket interface
745
  size_type bucket_count() const noexcept;
746
  size_type max_bucket_count() const noexcept;
747
  size_type bucket_size(size_type n) const;
748
  size_type bucket(const key_type& k) const;
749
  local_iterator begin(size_type n);
@@ -751,31 +1078,74 @@ namespace std {
751
  local_iterator end(size_type n);
752
  const_local_iterator end(size_type n) const;
753
  const_local_iterator cbegin(size_type n) const;
754
  const_local_iterator cend(size_type n) const;
755
 
756
- // hash policy
757
  float load_factor() const noexcept;
758
  float max_load_factor() const noexcept;
759
  void max_load_factor(float z);
760
  void rehash(size_type n);
761
  void reserve(size_type n);
762
  };
763
 
764
- template <class Key, class Hash, class Pred, class Alloc>
765
- void swap(unordered_set<Key, Hash, Pred, Alloc>& x,
766
- unordered_set<Key, Hash, Pred, Alloc>& y);
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
767
 
768
  template <class Key, class Hash, class Pred, class Alloc>
769
  bool operator==(const unordered_set<Key, Hash, Pred, Alloc>& a,
770
  const unordered_set<Key, Hash, Pred, Alloc>& b);
771
  template <class Key, class Hash, class Pred, class Alloc>
772
  bool operator!=(const unordered_set<Key, Hash, Pred, Alloc>& a,
773
  const unordered_set<Key, Hash, Pred, Alloc>& b);
 
 
 
 
 
 
774
  }
775
  ```
776
 
 
 
 
 
777
  #### `unordered_set` constructors <a id="unord.set.cnstr">[[unord.set.cnstr]]</a>
778
 
779
  ``` cpp
780
  unordered_set() : unordered_set(size_type(see below)) { }
781
  explicit unordered_set(size_type n,
@@ -783,42 +1153,49 @@ explicit unordered_set(size_type n,
783
  const key_equal& eql = key_equal(),
784
  const allocator_type& a = allocator_type());
785
  ```
786
 
787
  *Effects:* Constructs an empty `unordered_set` using the specified hash
788
- function, key equality function, and allocator, and using at least *`n`*
789
  buckets. For the default constructor, the number of buckets is
790
- *implementation-defined*. `max_load_factor()` returns 1.0.
791
 
792
  *Complexity:* Constant.
793
 
794
  ``` cpp
795
  template <class InputIterator>
796
  unordered_set(InputIterator f, InputIterator l,
797
  size_type n = see below,
798
  const hasher& hf = hasher(),
799
  const key_equal& eql = key_equal(),
800
  const allocator_type& a = allocator_type());
 
 
 
 
 
801
  ```
802
 
803
  *Effects:* Constructs an empty `unordered_set` using the specified hash
804
- function, key equality function, and allocator, and using at least *`n`*
805
- buckets. If *`n`* is not provided, the number of buckets is
806
- *implementation-defined*. Then inserts elements from the range
807
- `[`*`f`*`, `*`l`*`)`. `max_load_factor()` returns 1.0.
 
808
 
809
  *Complexity:* Average case linear, worst case quadratic.
810
 
811
  #### `unordered_set` swap <a id="unord.set.swap">[[unord.set.swap]]</a>
812
 
813
  ``` cpp
814
  template <class Key, class Hash, class Pred, class Alloc>
815
  void swap(unordered_set<Key, Hash, Pred, Alloc>& x,
816
- unordered_set<Key, Hash, Pred, Alloc>& y);
 
817
  ```
818
 
819
- *Effects:* `x.swap(y)`.
820
 
821
  ### Class template `unordered_multiset` <a id="unord.multiset">[[unord.multiset]]</a>
822
 
823
  #### Class template `unordered_multiset` overview <a id="unord.multiset.overview">[[unord.multiset.overview]]</a>
824
 
@@ -833,45 +1210,45 @@ container, of an unordered associative container, and of an
833
  allocator-aware container (Table  [[tab:containers.allocatoraware]]). It
834
  provides the operations described in the preceding requirements table
835
  for equivalent keys; that is, an `unordered_multiset` supports the
836
  `a_eq` operations in that table, not the `a_uniq` operations. For an
837
  `unordered_multiset<Key>` the `key type` and the value type are both
838
- `Key`. The `iterator` and `const_iterator` types are both const iterator
839
- types. It is unspecified whether they are the same type.
840
 
841
  This section only describes operations on `unordered_multiset` that are
842
  not described in one of the requirement tables, or for which there is
843
  additional semantic information.
844
 
845
  ``` cpp
846
  namespace std {
847
  template <class Key,
848
  class Hash = hash<Key>,
849
- class Pred = std::equal_to<Key>,
850
- class Allocator = std::allocator<Key> >
851
- class unordered_multiset
852
- {
853
  public:
854
- // types
855
- typedef Key key_type;
856
- typedef Key value_type;
857
- typedef Hash hasher;
858
- typedef Pred key_equal;
859
- typedef Allocator allocator_type;
860
- typedef typename allocator_traits<Allocator>::pointer pointer;
861
- typedef typename allocator_traits<Allocator>::const_pointer const_pointer;
862
- typedef value_type& reference;
863
- typedef const value_type& const_reference;
864
- typedef implementation-defined size_type;
865
- typedef implementation-defined difference_type;
866
 
867
- typedef implementation-defined iterator;
868
- typedef implementation-defined const_iterator;
869
- typedef implementation-defined local_iterator;
870
- typedef implementation-defined const_local_iterator;
 
871
 
872
- // construct/destroy/copy
873
  unordered_multiset();
874
  explicit unordered_multiset(size_type n,
875
  const hasher& hf = hasher(),
876
  const key_equal& eql = key_equal(),
877
  const allocator_type& a = allocator_type());
@@ -884,12 +1261,12 @@ namespace std {
884
  unordered_multiset(const unordered_multiset&);
885
  unordered_multiset(unordered_multiset&&);
886
  explicit unordered_multiset(const Allocator&);
887
  unordered_multiset(const unordered_multiset&, const Allocator&);
888
  unordered_multiset(unordered_multiset&&, const Allocator&);
889
- unordered_multiset(initializer_list<value_type>,
890
- size_type = see below,
891
  const hasher& hf = hasher(),
892
  const key_equal& eql = key_equal(),
893
  const allocator_type& a = allocator_type());
894
  unordered_multiset(size_type n, const allocator_type& a)
895
  : unordered_multiset(n, hasher(), key_equal(), a) { }
@@ -907,56 +1284,76 @@ namespace std {
907
  unordered_multiset(initializer_list<value_type> il, size_type n, const hasher& hf,
908
  const allocator_type& a)
909
  : unordered_multiset(il, n, hf, key_equal(), a) { }
910
  ~unordered_multiset();
911
  unordered_multiset& operator=(const unordered_multiset&);
912
- unordered_multiset& operator=(unordered_multiset&&);
 
 
 
913
  unordered_multiset& operator=(initializer_list<value_type>);
914
  allocator_type get_allocator() const noexcept;
915
 
916
- // size and capacity
917
- bool empty() const noexcept;
918
- size_type size() const noexcept;
919
- size_type max_size() const noexcept;
920
-
921
- // iterators
922
  iterator begin() noexcept;
923
  const_iterator begin() const noexcept;
924
  iterator end() noexcept;
925
  const_iterator end() const noexcept;
926
  const_iterator cbegin() const noexcept;
927
  const_iterator cend() const noexcept;
928
 
929
- // modifiers
 
 
 
 
 
930
  template <class... Args> iterator emplace(Args&&... args);
931
  template <class... Args> iterator emplace_hint(const_iterator position, Args&&... args);
932
  iterator insert(const value_type& obj);
933
  iterator insert(value_type&& obj);
934
  iterator insert(const_iterator hint, const value_type& obj);
935
  iterator insert(const_iterator hint, value_type&& obj);
936
  template <class InputIterator> void insert(InputIterator first, InputIterator last);
937
  void insert(initializer_list<value_type>);
938
 
 
 
 
 
 
 
939
  iterator erase(const_iterator position);
940
  size_type erase(const key_type& k);
941
  iterator erase(const_iterator first, const_iterator last);
 
 
 
 
942
  void clear() noexcept;
943
 
944
- void swap(unordered_multiset&);
 
 
 
 
 
 
 
945
 
946
- // observers
947
  hasher hash_function() const;
948
  key_equal key_eq() const;
949
 
950
- // lookup
951
  iterator find(const key_type& k);
952
  const_iterator find(const key_type& k) const;
953
  size_type count(const key_type& k) const;
954
- std::pair<iterator, iterator> equal_range(const key_type& k);
955
- std::pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
956
 
957
- // bucket interface
958
  size_type bucket_count() const noexcept;
959
  size_type max_bucket_count() const noexcept;
960
  size_type bucket_size(size_type n) const;
961
  size_type bucket(const key_type& k) const;
962
  local_iterator begin(size_type n);
@@ -964,30 +1361,74 @@ namespace std {
964
  local_iterator end(size_type n);
965
  const_local_iterator end(size_type n) const;
966
  const_local_iterator cbegin(size_type n) const;
967
  const_local_iterator cend(size_type n) const;
968
 
969
- // hash policy
970
  float load_factor() const noexcept;
971
  float max_load_factor() const noexcept;
972
  void max_load_factor(float z);
973
  void rehash(size_type n);
974
  void reserve(size_type n);
975
  };
976
 
977
- template <class Key, class Hash, class Pred, class Alloc>
978
- void swap(unordered_multiset<Key, Hash, Pred, Alloc>& x,
979
- unordered_multiset<Key, Hash, Pred, Alloc>& y);
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
980
  template <class Key, class Hash, class Pred, class Alloc>
981
  bool operator==(const unordered_multiset<Key, Hash, Pred, Alloc>& a,
982
  const unordered_multiset<Key, Hash, Pred, Alloc>& b);
983
  template <class Key, class Hash, class Pred, class Alloc>
984
  bool operator!=(const unordered_multiset<Key, Hash, Pred, Alloc>& a,
985
  const unordered_multiset<Key, Hash, Pred, Alloc>& b);
 
 
 
 
 
 
986
  }
987
  ```
988
 
 
 
 
 
989
  #### `unordered_multiset` constructors <a id="unord.multiset.cnstr">[[unord.multiset.cnstr]]</a>
990
 
991
  ``` cpp
992
  unordered_multiset() : unordered_multiset(size_type(see below)) { }
993
  explicit unordered_multiset(size_type n,
@@ -995,38 +1436,45 @@ explicit unordered_multiset(size_type n,
995
  const key_equal& eql = key_equal(),
996
  const allocator_type& a = allocator_type());
997
  ```
998
 
999
  *Effects:* Constructs an empty `unordered_multiset` using the specified
1000
- hash function, key equality function, and allocator, and using at least
1001
- *`n`* buckets. For the default constructor, the number of buckets is
1002
- *implementation-defined*. `max_load_factor()` returns 1.0.
1003
 
1004
  *Complexity:* Constant.
1005
 
1006
  ``` cpp
1007
  template <class InputIterator>
1008
  unordered_multiset(InputIterator f, InputIterator l,
1009
  size_type n = see below,
1010
  const hasher& hf = hasher(),
1011
  const key_equal& eql = key_equal(),
1012
  const allocator_type& a = allocator_type());
 
 
 
 
 
1013
  ```
1014
 
1015
  *Effects:* Constructs an empty `unordered_multiset` using the specified
1016
- hash function, key equality function, and allocator, and using at least
1017
- *`n`* buckets. If *`n`* is not provided, the number of buckets is
1018
- *implementation-defined*. Then inserts elements from the range
1019
- `[`*`f`*`, `*`l`*`)`. `max_load_factor()` returns 1.0.
 
1020
 
1021
  *Complexity:* Average case linear, worst case quadratic.
1022
 
1023
  #### `unordered_multiset` swap <a id="unord.multiset.swap">[[unord.multiset.swap]]</a>
1024
 
1025
  ``` cpp
1026
  template <class Key, class Hash, class Pred, class Alloc>
1027
  void swap(unordered_multiset<Key, Hash, Pred, Alloc>& x,
1028
- unordered_multiset<Key, Hash, Pred, Alloc>& y);
 
1029
  ```
1030
 
1031
- *Effects:* `x.swap(y);`
1032
 
 
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,
22
  class Hash = hash<Key>,
23
+ class Pred = equal_to<Key>,
24
+ class Alloc = allocator<pair<const Key, T>>>
25
  class unordered_map;
26
 
27
+ // [unord.multimap], class template unordered_multimap
28
  template <class Key,
29
  class T,
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>
 
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>,
62
+ class Pred = equal_to<Key>>
63
+ using unordered_map =
64
+ std::unordered_map<Key, T, Hash, Pred,
65
+ polymorphic_allocator<pair<const Key, T>>>;
66
+ template <class Key,
67
+ class T,
68
+ class Hash = hash<Key>,
69
+ class Pred = equal_to<Key>>
70
+ using unordered_multimap =
71
+ std::unordered_multimap<Key, T, Hash, Pred,
72
+ polymorphic_allocator<pair<const Key, T>>>;
73
+
74
+ }
75
+ }
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>,
87
+ class Pred = equal_to<Key>,
88
+ class Alloc = allocator<Key>>
89
  class unordered_set;
90
 
91
+ // [unord.multiset], class template unordered_multiset
92
  template <class Key,
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>
 
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>>
125
+ using unordered_set = std::unordered_set<Key, Hash, Pred,
126
+ polymorphic_allocator<Key>>;
127
+
128
+ template <class Key,
129
+ class Hash = hash<Key>,
130
+ class Pred = equal_to<Key>>
131
+ using unordered_multiset = std::unordered_multiset<Key, Hash, Pred,
132
+ polymorphic_allocator<Key>>;
133
+ }
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>
 
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;
174
+ using allocator_type = Allocator;
175
+ using pointer = typename allocator_traits<Allocator>::pointer;
176
+ using const_pointer = typename allocator_traits<Allocator>::const_pointer;
177
+ using reference = value_type&;
178
+ using const_reference = const value_type&;
179
+ using size_type = implementation-defined; // see [container.requirements]
180
+ using difference_type = implementation-defined; // see [container.requirements]
181
 
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(),
193
  const key_equal& eql = key_equal(),
194
  const allocator_type& a = allocator_type());
 
201
  unordered_map(const unordered_map&);
202
  unordered_map(unordered_map&&);
203
  explicit unordered_map(const Allocator&);
204
  unordered_map(const unordered_map&, const Allocator&);
205
  unordered_map(unordered_map&&, const Allocator&);
206
+ unordered_map(initializer_list<value_type> il,
207
+ size_type n = see below,
208
  const hasher& hf = hasher(),
209
  const key_equal& eql = key_equal(),
210
  const allocator_type& a = allocator_type());
211
  unordered_map(size_type n, const allocator_type& a)
212
  : unordered_map(n, hasher(), key_equal(), a) { }
 
224
  unordered_map(initializer_list<value_type> il, size_type n, const hasher& hf,
225
  const allocator_type& a)
226
  : unordered_map(il, n, hf, key_equal(), a) { }
227
  ~unordered_map();
228
  unordered_map& operator=(const unordered_map&);
229
+ unordered_map& operator=(unordered_map&&)
230
+ noexcept(allocator_traits<Allocator>::is_always_equal::value &&
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);
251
  template <class... Args> iterator emplace_hint(const_iterator position, Args&&... args);
252
  pair<iterator, bool> insert(const value_type& obj);
253
+ pair<iterator, bool> insert(value_type&& obj);
254
  template <class P> pair<iterator, bool> insert(P&& obj);
255
  iterator insert(const_iterator hint, const value_type& obj);
256
+ iterator insert(const_iterator hint, value_type&& obj);
257
  template <class P> iterator insert(const_iterator hint, P&& obj);
258
  template <class InputIterator> void insert(InputIterator first, InputIterator last);
259
  void insert(initializer_list<value_type>);
260
 
261
+ node_type extract(const_iterator position);
262
+ node_type extract(const key_type& x);
263
+ insert_return_type insert(node_type&& nh);
264
+ iterator insert(const_iterator hint, node_type&& nh);
265
+
266
+ template <class... Args>
267
+ pair<iterator, bool> try_emplace(const key_type& k, Args&&... args);
268
+ template <class... Args>
269
+ pair<iterator, bool> try_emplace(key_type&& k, Args&&... args);
270
+ template <class... Args>
271
+ iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args);
272
+ template <class... Args>
273
+ iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args);
274
+ template <class M>
275
+ pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj);
276
+ template <class M>
277
+ pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj);
278
+ template <class M>
279
+ iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj);
280
+ template <class M>
281
+ iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj);
282
+
283
+ iterator erase(iterator position);
284
  iterator erase(const_iterator position);
285
  size_type erase(const key_type& k);
286
  iterator erase(const_iterator first, const_iterator last);
287
+ void swap(unordered_map&)
288
+ noexcept(allocator_traits<Allocator>::is_always_equal::value &&
289
+ is_nothrow_swappable_v<Hash> &&
290
+ is_nothrow_swappable_v<Pred>);
291
  void clear() noexcept;
292
 
293
+ template<class H2, class P2>
294
+ void merge(unordered_map<Key, T, H2, P2, Allocator>& source);
295
+ template<class H2, class P2>
296
+ void merge(unordered_map<Key, T, H2, P2, Allocator>&& source);
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
  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
  }
399
  ```
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,
 
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
416
+ function, key equality predicate, and allocator, and using at least `n`
417
  buckets. For the default constructor, the number of buckets is
418
+ *implementation-defined*. `max_load_factor()` returns `1.0`.
419
 
420
  *Complexity:* Constant.
421
 
422
  ``` cpp
423
  template <class InputIterator>
424
  unordered_map(InputIterator f, InputIterator l,
425
  size_type n = see below,
426
  const hasher& hf = hasher(),
427
  const key_equal& eql = key_equal(),
428
  const allocator_type& a = allocator_type());
429
+ unordered_map(initializer_list<value_type> il,
430
+ size_type n = see below,
431
+ const hasher& hf = hasher(),
432
+ const key_equal& eql = key_equal(),
433
+ const allocator_type& a = allocator_type());
434
  ```
435
 
436
  *Effects:* Constructs an empty `unordered_map` using the specified hash
437
+ function, key equality predicate, and allocator, and using at least `n`
438
+ buckets. If `n` is not provided, the number of buckets is
439
+ *implementation-defined*. Then inserts elements from the range \[`f`,
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
+
451
+ *Effects:* Equivalent to: `return try_emplace(k).first->second;`
452
+
453
+ ``` cpp
454
  mapped_type& operator[](key_type&& k);
455
  ```
456
 
457
+ *Effects:* Equivalent to: `return try_emplace(move(k)).first->second;`
 
 
 
 
 
 
 
 
 
 
 
 
458
 
459
  ``` cpp
460
  mapped_type& at(const key_type& k);
461
  const mapped_type& at(const key_type& k) const;
462
  ```
 
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
506
+ type `value_type` constructed with `piecewise_construct`,
507
+ `forward_as_tuple(k)`, `forward_as_tuple(std::forward<Args>(args)...)`.
508
+
509
+ *Returns:* In the first overload, the `bool` component of the returned
510
+ pair is `true` if and only if the insertion took place. The returned
511
+ iterator points to the map element whose key is equivalent to `k`.
512
+
513
+ *Complexity:* The same as `emplace` and `emplace_hint`, respectively.
514
+
515
+ ``` cpp
516
+ 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
528
+ equivalent to `k`, there is no effect. Otherwise inserts an object of
529
+ type `value_type` constructed with `piecewise_construct`,
530
+ `forward_as_tuple(std::move(k))`,
531
+ `forward_as_tuple(std::forward<Args>(args)...)`.
532
+
533
+ *Returns:* In the first overload, the `bool` component of the returned
534
+ pair is `true` if and only if the insertion took place. The returned
535
+ iterator points to the map element whose key is equivalent to `k`.
536
+
537
+ *Complexity:* The same as `emplace` and `emplace_hint`, respectively.
538
+
539
+ ``` cpp
540
+ 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)`.
554
+
555
+ *Returns:* In the first overload, the `bool` component of the returned
556
+ pair is `true` if and only if the insertion took place. The returned
557
+ iterator points to the map element whose key is equivalent to `k`.
558
+
559
+ *Complexity:* The same as `emplace` and `emplace_hint`, respectively.
560
+
561
+ ``` cpp
562
+ 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)`.
576
+
577
+ *Returns:* In the first overload, the `bool` component of the returned
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
 
 
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;
632
+ using allocator_type = Allocator;
633
+ using pointer = typename allocator_traits<Allocator>::pointer;
634
+ using const_pointer = typename allocator_traits<Allocator>::const_pointer;
635
+ using reference = value_type&;
636
+ using const_reference = const value_type&;
637
+ using size_type = implementation-defined; // see [container.requirements]
638
+ using difference_type = implementation-defined; // see [container.requirements]
639
 
640
+ using iterator = implementation-defined // type of unordered_multimap::iterator; // see [container.requirements]
641
+ using const_iterator = implementation-defined // type of unordered_multimap::const_iterator; // see [container.requirements]
642
+ using local_iterator = implementation-defined // type of unordered_multimap::local_iterator; // see [container.requirements]
643
+ using const_local_iterator = implementation-defined // type of unordered_multimap::const_local_iterator; // see [container.requirements]
644
+ using node_type = unspecified;
645
 
646
+ // [unord.multimap.cnstr], construct/copy/destroy
647
  unordered_multimap();
648
  explicit unordered_multimap(size_type n,
649
  const hasher& hf = hasher(),
650
  const key_equal& eql = key_equal(),
651
  const allocator_type& a = allocator_type());
 
658
  unordered_multimap(const unordered_multimap&);
659
  unordered_multimap(unordered_multimap&&);
660
  explicit unordered_multimap(const Allocator&);
661
  unordered_multimap(const unordered_multimap&, const Allocator&);
662
  unordered_multimap(unordered_multimap&&, const Allocator&);
663
+ unordered_multimap(initializer_list<value_type> il,
664
+ size_type n = see below,
665
  const hasher& hf = hasher(),
666
  const key_equal& eql = key_equal(),
667
  const allocator_type& a = allocator_type());
668
  unordered_multimap(size_type n, const allocator_type& a)
669
  : unordered_multimap(n, hasher(), key_equal(), a) { }
 
681
  unordered_multimap(initializer_list<value_type> il, size_type n, const hasher& hf,
682
  const allocator_type& a)
683
  : unordered_multimap(il, n, hf, key_equal(), a) { }
684
  ~unordered_multimap();
685
  unordered_multimap& operator=(const unordered_multimap&);
686
+ unordered_multimap& operator=(unordered_multimap&&)
687
+ noexcept(allocator_traits<Allocator>::is_always_equal::value &&
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);
708
  template <class... Args> iterator emplace_hint(const_iterator position, Args&&... args);
709
  iterator insert(const value_type& obj);
710
+ iterator insert(value_type&& obj);
711
  template <class P> iterator insert(P&& obj);
712
  iterator insert(const_iterator hint, const value_type& obj);
713
+ iterator insert(const_iterator hint, value_type&& obj);
714
  template <class P> iterator insert(const_iterator hint, P&& obj);
715
  template <class InputIterator> void insert(InputIterator first, InputIterator last);
716
  void insert(initializer_list<value_type>);
717
 
718
+ node_type extract(const_iterator position);
719
+ node_type extract(const key_type& x);
720
+ iterator insert(node_type&& nh);
721
+ iterator insert(const_iterator hint, node_type&& nh);
722
+
723
+ iterator erase(iterator position);
724
  iterator erase(const_iterator position);
725
  size_type erase(const key_type& k);
726
  iterator erase(const_iterator first, const_iterator last);
727
+ void swap(unordered_multimap&)
728
+ noexcept(allocator_traits<Allocator>::is_always_equal::value &&
729
+ is_nothrow_swappable_v<Hash> &&
730
+ is_nothrow_swappable_v<Pred>);
731
  void clear() noexcept;
732
 
733
+ template<class H2, class P2>
734
+ void merge(unordered_multimap<Key, T, H2, P2, Allocator>& source);
735
+ template<class H2, class P2>
736
+ void merge(unordered_multimap<Key, T, H2, P2, Allocator>&& source);
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);
 
768
  void max_load_factor(float z);
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
  }
835
  ```
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,
 
847
  const key_equal& eql = key_equal(),
848
  const allocator_type& a = allocator_type());
849
  ```
850
 
851
  *Effects:* Constructs an empty `unordered_multimap` using the specified
852
+ hash function, key equality predicate, and allocator, and using at least
853
+ `n` buckets. For the default constructor, the number of buckets is
854
+ *implementation-defined*. `max_load_factor()` returns `1.0`.
855
 
856
  *Complexity:* Constant.
857
 
858
  ``` cpp
859
  template <class InputIterator>
860
  unordered_multimap(InputIterator f, InputIterator l,
861
  size_type n = see below,
862
  const hasher& hf = hasher(),
863
  const key_equal& eql = key_equal(),
864
  const allocator_type& a = allocator_type());
865
+ unordered_multimap(initializer_list<value_type> il,
866
+ size_type n = see below,
867
+ const hasher& hf = hasher(),
868
+ const key_equal& eql = key_equal(),
869
+ const allocator_type& a = allocator_type());
870
  ```
871
 
872
  *Effects:* Constructs an empty `unordered_multimap` using the specified
873
+ hash function, key equality predicate, and allocator, and using at least
874
+ `n` buckets. If `n` is not provided, the number of buckets is
875
+ *implementation-defined*. Then inserts elements from the range \[`f`,
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
 
 
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;
952
+ using pointer = typename allocator_traits<Allocator>::pointer;
953
+ using const_pointer = typename allocator_traits<Allocator>::const_pointer;
954
+ using reference = value_type&;
955
+ using const_reference = const value_type&;
956
+ using size_type = implementation-defined; // see [container.requirements]
957
+ using difference_type = implementation-defined; // see [container.requirements]
958
 
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(),
970
  const key_equal& eql = key_equal(),
971
  const allocator_type& a = allocator_type());
 
978
  unordered_set(const unordered_set&);
979
  unordered_set(unordered_set&&);
980
  explicit unordered_set(const Allocator&);
981
  unordered_set(const unordered_set&, const Allocator&);
982
  unordered_set(unordered_set&&, const Allocator&);
983
+ unordered_set(initializer_list<value_type> il,
984
+ size_type n = see below,
985
  const hasher& hf = hasher(),
986
  const key_equal& eql = key_equal(),
987
  const allocator_type& a = allocator_type());
988
  unordered_set(size_type n, const allocator_type& a)
989
  : unordered_set(n, hasher(), key_equal(), a) { }
 
1001
  unordered_set(initializer_list<value_type> il, size_type n, const hasher& hf,
1002
  const allocator_type& a)
1003
  : unordered_set(il, n, hf, key_equal(), a) { }
1004
  ~unordered_set();
1005
  unordered_set& operator=(const unordered_set&);
1006
+ unordered_set& operator=(unordered_set&&)
1007
+ noexcept(allocator_traits<Allocator>::is_always_equal::value &&
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);
1032
  iterator insert(const_iterator hint, value_type&& obj);
1033
  template <class InputIterator> void insert(InputIterator first, InputIterator last);
1034
  void insert(initializer_list<value_type>);
1035
 
1036
+ node_type extract(const_iterator position);
1037
+ node_type extract(const key_type& x);
1038
+ insert_return_type insert(node_type&& nh);
1039
+ iterator insert(const_iterator hint, node_type&& nh);
1040
+
1041
+ iterator erase(iterator position);
1042
  iterator erase(const_iterator position);
1043
  size_type erase(const key_type& k);
1044
  iterator erase(const_iterator first, const_iterator last);
1045
+ void swap(unordered_set&)
1046
+ noexcept(allocator_traits<Allocator>::is_always_equal::value &&
1047
+ is_nothrow_swappable_v<Hash> &&
1048
+ is_nothrow_swappable_v<Pred>);
1049
  void clear() noexcept;
1050
 
1051
+ template<class H2, class P2>
1052
+ void merge(unordered_set<Key, H2, P2, Allocator>& source);
1053
+ template<class H2, class P2>
1054
+ void merge(unordered_set<Key, H2, P2, Allocator>&& source);
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
  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,
 
1153
  const key_equal& eql = key_equal(),
1154
  const allocator_type& a = allocator_type());
1155
  ```
1156
 
1157
  *Effects:* Constructs an empty `unordered_set` using the specified hash
1158
+ function, key equality predicate, and allocator, and using at least `n`
1159
  buckets. For the default constructor, the number of buckets is
1160
+ *implementation-defined*. `max_load_factor()` returns `1.0`.
1161
 
1162
  *Complexity:* Constant.
1163
 
1164
  ``` cpp
1165
  template <class InputIterator>
1166
  unordered_set(InputIterator f, InputIterator l,
1167
  size_type n = see below,
1168
  const hasher& hf = hasher(),
1169
  const key_equal& eql = key_equal(),
1170
  const allocator_type& a = allocator_type());
1171
+ unordered_set(initializer_list<value_type> il,
1172
+ size_type n = see below,
1173
+ const hasher& hf = hasher(),
1174
+ const key_equal& eql = key_equal(),
1175
+ const allocator_type& a = allocator_type());
1176
  ```
1177
 
1178
  *Effects:* Constructs an empty `unordered_set` using the specified hash
1179
+ function, key equality predicate, and allocator, and using at least `n`
1180
+ buckets. If `n` is not provided, the number of buckets is
1181
+ *implementation-defined*. Then inserts elements from the range \[`f`,
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
 
 
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;
1236
+ using pointer = typename allocator_traits<Allocator>::pointer;
1237
+ using const_pointer = typename allocator_traits<Allocator>::const_pointer;
1238
+ using reference = value_type&;
1239
+ using const_reference = const value_type&;
1240
+ using size_type = implementation-defined; // see [container.requirements]
1241
+ using difference_type = implementation-defined; // see [container.requirements]
1242
 
1243
+ using iterator = implementation-defined // type of unordered_multiset::iterator; // see [container.requirements]
1244
+ using const_iterator = implementation-defined // type of unordered_multiset::const_iterator; // see [container.requirements]
1245
+ using local_iterator = implementation-defined // type of unordered_multiset::local_iterator; // see [container.requirements]
1246
+ using const_local_iterator = implementation-defined // type of unordered_multiset::const_local_iterator; // see [container.requirements]
1247
+ using node_type = unspecified;
1248
 
1249
+ // [unord.multiset.cnstr], construct/copy/destroy
1250
  unordered_multiset();
1251
  explicit unordered_multiset(size_type n,
1252
  const hasher& hf = hasher(),
1253
  const key_equal& eql = key_equal(),
1254
  const allocator_type& a = allocator_type());
 
1261
  unordered_multiset(const unordered_multiset&);
1262
  unordered_multiset(unordered_multiset&&);
1263
  explicit unordered_multiset(const Allocator&);
1264
  unordered_multiset(const unordered_multiset&, const Allocator&);
1265
  unordered_multiset(unordered_multiset&&, const Allocator&);
1266
+ unordered_multiset(initializer_list<value_type> il,
1267
+ size_type n = see below,
1268
  const hasher& hf = hasher(),
1269
  const key_equal& eql = key_equal(),
1270
  const allocator_type& a = allocator_type());
1271
  unordered_multiset(size_type n, const allocator_type& a)
1272
  : unordered_multiset(n, hasher(), key_equal(), a) { }
 
1284
  unordered_multiset(initializer_list<value_type> il, size_type n, const hasher& hf,
1285
  const allocator_type& a)
1286
  : unordered_multiset(il, n, hf, key_equal(), a) { }
1287
  ~unordered_multiset();
1288
  unordered_multiset& operator=(const unordered_multiset&);
1289
+ unordered_multiset& operator=(unordered_multiset&&)
1290
+ noexcept(allocator_traits<Allocator>::is_always_equal::value &&
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);
1315
  iterator insert(const_iterator hint, value_type&& obj);
1316
  template <class InputIterator> void insert(InputIterator first, InputIterator last);
1317
  void insert(initializer_list<value_type>);
1318
 
1319
+ node_type extract(const_iterator position);
1320
+ node_type extract(const key_type& x);
1321
+ iterator insert(node_type&& nh);
1322
+ iterator insert(const_iterator hint, node_type&& nh);
1323
+
1324
+ iterator erase(iterator position);
1325
  iterator erase(const_iterator position);
1326
  size_type erase(const key_type& k);
1327
  iterator erase(const_iterator first, const_iterator last);
1328
+ void swap(unordered_multiset&)
1329
+ noexcept(allocator_traits<Allocator>::is_always_equal::value &&
1330
+ is_nothrow_swappable_v<Hash> &&
1331
+ is_nothrow_swappable_v<Pred>);
1332
  void clear() noexcept;
1333
 
1334
+ template<class H2, class P2>
1335
+ void merge(unordered_multiset<Key, H2, P2, Allocator>& source);
1336
+ template<class H2, class P2>
1337
+ void merge(unordered_multiset<Key, H2, P2, Allocator>&& source);
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
  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,
 
1436
  const key_equal& eql = key_equal(),
1437
  const allocator_type& a = allocator_type());
1438
  ```
1439
 
1440
  *Effects:* Constructs an empty `unordered_multiset` using the specified
1441
+ hash function, key equality predicate, and allocator, and using at least
1442
+ `n` buckets. For the default constructor, the number of buckets is
1443
+ *implementation-defined*. `max_load_factor()` returns `1.0`.
1444
 
1445
  *Complexity:* Constant.
1446
 
1447
  ``` cpp
1448
  template <class InputIterator>
1449
  unordered_multiset(InputIterator f, InputIterator l,
1450
  size_type n = see below,
1451
  const hasher& hf = hasher(),
1452
  const key_equal& eql = key_equal(),
1453
  const allocator_type& a = allocator_type());
1454
+ unordered_multiset(initializer_list<value_type> il,
1455
+ size_type n = see below,
1456
+ const hasher& hf = hasher(),
1457
+ const key_equal& eql = key_equal(),
1458
+ const allocator_type& a = allocator_type());
1459
  ```
1460
 
1461
  *Effects:* Constructs an empty `unordered_multiset` using the specified
1462
+ hash function, key equality predicate, and allocator, and using at least
1463
+ `n` buckets. If `n` is not provided, the number of buckets is
1464
+ *implementation-defined*. Then inserts elements from the range \[`f`,
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