1// -*- C++ -*-
2//===----------------------------------------------------------------------===//
3//
4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5// See https://llvm.org/LICENSE.txt for license information.
6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7//
8//===----------------------------------------------------------------------===//
9
10#ifndef _LIBCPP_UNORDERED_MAP
11#define _LIBCPP_UNORDERED_MAP
12
13/*
14
15 unordered_map synopsis
16
17#include <initializer_list>
18
19namespace std
20{
21
22template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
23 class Alloc = allocator<pair<const Key, T>>>
24class unordered_map
25{
26public:
27 // types
28 typedef Key key_type;
29 typedef T mapped_type;
30 typedef Hash hasher;
31 typedef Pred key_equal;
32 typedef Alloc allocator_type;
33 typedef pair<const key_type, mapped_type> value_type;
34 typedef value_type& reference;
35 typedef const value_type& const_reference;
36 typedef typename allocator_traits<allocator_type>::pointer pointer;
37 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
38 typedef typename allocator_traits<allocator_type>::size_type size_type;
39 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
40
41 typedef /unspecified/ iterator;
42 typedef /unspecified/ const_iterator;
43 typedef /unspecified/ local_iterator;
44 typedef /unspecified/ const_local_iterator;
45
46 typedef unspecified node_type; // C++17
47 typedef INSERT_RETURN_TYPE<iterator, node_type> insert_return_type; // C++17
48
49 unordered_map()
50 noexcept(
51 is_nothrow_default_constructible<hasher>::value &&
52 is_nothrow_default_constructible<key_equal>::value &&
53 is_nothrow_default_constructible<allocator_type>::value);
54 explicit unordered_map(size_type n, const hasher& hf = hasher(),
55 const key_equal& eql = key_equal(),
56 const allocator_type& a = allocator_type());
57 template <class InputIterator>
58 unordered_map(InputIterator f, InputIterator l,
59 size_type n = 0, const hasher& hf = hasher(),
60 const key_equal& eql = key_equal(),
61 const allocator_type& a = allocator_type());
62 template<container-compatible-range<value_type> R>
63 unordered_map(from_range_t, R&& rg, size_type n = see below,
64 const hasher& hf = hasher(), const key_equal& eql = key_equal(),
65 const allocator_type& a = allocator_type()); // C++23
66
67 explicit unordered_map(const allocator_type&);
68 unordered_map(const unordered_map&);
69 unordered_map(const unordered_map&, const Allocator&);
70 unordered_map(unordered_map&&)
71 noexcept(
72 is_nothrow_move_constructible<hasher>::value &&
73 is_nothrow_move_constructible<key_equal>::value &&
74 is_nothrow_move_constructible<allocator_type>::value);
75 unordered_map(unordered_map&&, const Allocator&);
76 unordered_map(initializer_list<value_type>, size_type n = 0,
77 const hasher& hf = hasher(), const key_equal& eql = key_equal(),
78 const allocator_type& a = allocator_type());
79 unordered_map(size_type n, const allocator_type& a)
80 : unordered_map(n, hasher(), key_equal(), a) {} // C++14
81 unordered_map(size_type n, const hasher& hf, const allocator_type& a)
82 : unordered_map(n, hf, key_equal(), a) {} // C++14
83 template <class InputIterator>
84 unordered_map(InputIterator f, InputIterator l, size_type n, const allocator_type& a)
85 : unordered_map(f, l, n, hasher(), key_equal(), a) {} // C++14
86 template <class InputIterator>
87 unordered_map(InputIterator f, InputIterator l, size_type n, const hasher& hf,
88 const allocator_type& a)
89 : unordered_map(f, l, n, hf, key_equal(), a) {} // C++14
90 template<container-compatible-range<value_type> R>
91 unordered_map(from_range_t, R&& rg, size_type n, const allocator_type& a)
92 : unordered_map(from_range, std::forward<R>(rg), n, hasher(), key_equal(), a) { } // C++23
93 template<container-compatible-range<value_type> R>
94 unordered_map(from_range_t, R&& rg, size_type n, const hasher& hf, const allocator_type& a)
95 : unordered_map(from_range, std::forward<R>(rg), n, hf, key_equal(), a) { } // C++23
96 unordered_map(initializer_list<value_type> il, size_type n, const allocator_type& a)
97 : unordered_map(il, n, hasher(), key_equal(), a) {} // C++14
98 unordered_map(initializer_list<value_type> il, size_type n, const hasher& hf,
99 const allocator_type& a)
100 : unordered_map(il, n, hf, key_equal(), a) {} // C++14
101 ~unordered_map();
102 unordered_map& operator=(const unordered_map&);
103 unordered_map& operator=(unordered_map&&)
104 noexcept(
105 allocator_type::propagate_on_container_move_assignment::value &&
106 is_nothrow_move_assignable<allocator_type>::value &&
107 is_nothrow_move_assignable<hasher>::value &&
108 is_nothrow_move_assignable<key_equal>::value);
109 unordered_map& operator=(initializer_list<value_type>);
110
111 allocator_type get_allocator() const noexcept;
112
113 bool empty() const noexcept;
114 size_type size() const noexcept;
115 size_type max_size() const noexcept;
116
117 iterator begin() noexcept;
118 iterator end() noexcept;
119 const_iterator begin() const noexcept;
120 const_iterator end() const noexcept;
121 const_iterator cbegin() const noexcept;
122 const_iterator cend() const noexcept;
123
124 template <class... Args>
125 pair<iterator, bool> emplace(Args&&... args);
126 template <class... Args>
127 iterator emplace_hint(const_iterator position, Args&&... args);
128 pair<iterator, bool> insert(const value_type& obj);
129 template <class P>
130 pair<iterator, bool> insert(P&& obj);
131 iterator insert(const_iterator hint, const value_type& obj);
132 template <class P>
133 iterator insert(const_iterator hint, P&& obj);
134 template <class InputIterator>
135 void insert(InputIterator first, InputIterator last);
136 template<container-compatible-range<value_type> R>
137 void insert_range(R&& rg); // C++23
138 void insert(initializer_list<value_type>);
139
140 node_type extract(const_iterator position); // C++17
141 node_type extract(const key_type& x); // C++17
142 insert_return_type insert(node_type&& nh); // C++17
143 iterator insert(const_iterator hint, node_type&& nh); // C++17
144
145 template <class... Args>
146 pair<iterator, bool> try_emplace(const key_type& k, Args&&... args); // C++17
147 template <class... Args>
148 pair<iterator, bool> try_emplace(key_type&& k, Args&&... args); // C++17
149 template <class... Args>
150 iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args); // C++17
151 template <class... Args>
152 iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args); // C++17
153 template <class M>
154 pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj); // C++17
155 template <class M>
156 pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj); // C++17
157 template <class M>
158 iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj); // C++17
159 template <class M>
160 iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj); // C++17
161
162 iterator erase(const_iterator position);
163 iterator erase(iterator position); // C++14
164 size_type erase(const key_type& k);
165 iterator erase(const_iterator first, const_iterator last);
166 void clear() noexcept;
167
168 template<class H2, class P2>
169 void merge(unordered_map<Key, T, H2, P2, Allocator>& source); // C++17
170 template<class H2, class P2>
171 void merge(unordered_map<Key, T, H2, P2, Allocator>&& source); // C++17
172 template<class H2, class P2>
173 void merge(unordered_multimap<Key, T, H2, P2, Allocator>& source); // C++17
174 template<class H2, class P2>
175 void merge(unordered_multimap<Key, T, H2, P2, Allocator>&& source); // C++17
176
177 void swap(unordered_map&)
178 noexcept(
179 (!allocator_type::propagate_on_container_swap::value ||
180 __is_nothrow_swappable<allocator_type>::value) &&
181 __is_nothrow_swappable<hasher>::value &&
182 __is_nothrow_swappable<key_equal>::value);
183
184 hasher hash_function() const;
185 key_equal key_eq() const;
186
187 iterator find(const key_type& k);
188 const_iterator find(const key_type& k) const;
189 template<typename K>
190 iterator find(const K& x); // C++20
191 template<typename K>
192 const_iterator find(const K& x) const; // C++20
193 size_type count(const key_type& k) const;
194 template<typename K>
195 size_type count(const K& k) const; // C++20
196 bool contains(const key_type& k) const; // C++20
197 template<typename K>
198 bool contains(const K& k) const; // C++20
199 pair<iterator, iterator> equal_range(const key_type& k);
200 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
201 template<typename K>
202 pair<iterator, iterator> equal_range(const K& k); // C++20
203 template<typename K>
204 pair<const_iterator, const_iterator> equal_range(const K& k) const; // C++20
205
206 mapped_type& operator[](const key_type& k);
207 mapped_type& operator[](key_type&& k);
208
209 mapped_type& at(const key_type& k);
210 const mapped_type& at(const key_type& k) const;
211
212 size_type bucket_count() const noexcept;
213 size_type max_bucket_count() const noexcept;
214
215 size_type bucket_size(size_type n) const;
216 size_type bucket(const key_type& k) const;
217
218 local_iterator begin(size_type n);
219 local_iterator end(size_type n);
220 const_local_iterator begin(size_type n) const;
221 const_local_iterator end(size_type n) const;
222 const_local_iterator cbegin(size_type n) const;
223 const_local_iterator cend(size_type n) const;
224
225 float load_factor() const noexcept;
226 float max_load_factor() const noexcept;
227 void max_load_factor(float z);
228 void rehash(size_type n);
229 void reserve(size_type n);
230};
231
232template<class InputIterator,
233 class Hash = hash<iter_key_t<InputIterator>>, class Pred = equal_to<iter_key_t<InputIterator>>,
234 class Allocator = allocator<iter_to_alloc_t<InputIterator>>>
235unordered_map(InputIterator, InputIterator, typename see below::size_type = see below,
236 Hash = Hash(), Pred = Pred(), Allocator = Allocator())
237 -> unordered_map<iter_key_t<InputIterator>, iter_value_t<InputIterator>, Hash, Pred,
238 Allocator>; // C++17
239
240template<ranges::input_range R, class Hash = hash<range-key-type<R>>,
241 class Pred = equal_to<range-key-type<R>>,
242 class Allocator = allocator<range-to-alloc-type<R>>>
243 unordered_map(from_range_t, R&&, typename see below::size_type = see below,
244 Hash = Hash(), Pred = Pred(), Allocator = Allocator())
245 -> unordered_map<range-key-type<R>, range-mapped-type<R>, Hash, Pred, Allocator>; // C++23
246
247template<class Key, class T, class Hash = hash<Key>,
248 class Pred = equal_to<Key>, class Allocator = allocator<pair<const Key, T>>>
249unordered_map(initializer_list<pair<const Key, T>>, typename see below::size_type = see below,
250 Hash = Hash(), Pred = Pred(), Allocator = Allocator())
251 -> unordered_map<Key, T, Hash, Pred, Allocator>; // C++17
252
253template<class InputIterator, class Allocator>
254unordered_map(InputIterator, InputIterator, typename see below::size_type, Allocator)
255 -> unordered_map<iter_key_t<InputIterator>, iter_val_t<InputIterator>,
256 hash<iter_key_t<InputIterator>>, equal_to<iter_key_t<InputIterator>>, Allocator>; // C++17
257
258template<class InputIterator, class Allocator>
259unordered_map(InputIterator, InputIterator, Allocator)
260 -> unordered_map<iter_key_t<InputIterator>, iter_val_t<InputIterator>,
261 hash<iter_key_t<InputIterator>>, equal_to<iter_key_t<InputIterator>>, Allocator>; // C++17
262
263template<class InputIterator, class Hash, class Allocator>
264unordered_map(InputIterator, InputIterator, typename see below::size_type, Hash, Allocator)
265 -> unordered_map<iter_key_t<InputIterator>, iter_val_t<InputIterator>, Hash,
266 equal_to<iter_key_t<InputIterator>>, Allocator>; // C++17
267
268template<ranges::input_range R, class Allocator>
269 unordered_map(from_range_t, R&&, typename see below::size_type, Allocator)
270 -> unordered_map<range-key-type<R>, range-mapped-type<R>, hash<range-key-type<R>>,
271 equal_to<range-key-type<R>>, Allocator>; // C++23
272
273template<ranges::input_range R, class Allocator>
274 unordered_map(from_range_t, R&&, Allocator)
275 -> unordered_map<range-key-type<R>, range-mapped-type<R>, hash<range-key-type<R>>,
276 equal_to<range-key-type<R>>, Allocator>; // C++23
277
278template<ranges::input_range R, class Hash, class Allocator>
279 unordered_map(from_range_t, R&&, typename see below::size_type, Hash, Allocator)
280 -> unordered_map<range-key-type<R>, range-mapped-type<R>, Hash,
281 equal_to<range-key-type<R>>, Allocator>; // C++23
282
283template<class Key, class T, typename Allocator>
284unordered_map(initializer_list<pair<const Key, T>>, typename see below::size_type, Allocator)
285 -> unordered_map<Key, T, hash<Key>, equal_to<Key>, Allocator>; // C++17
286
287template<class Key, class T, typename Allocator>
288unordered_map(initializer_list<pair<const Key, T>>, Allocator)
289 -> unordered_map<Key, T, hash<Key>, equal_to<Key>, Allocator>; // C++17
290
291template<class Key, class T, class Hash, class Allocator>
292unordered_map(initializer_list<pair<const Key, T>>, typename see below::size_type, Hash, Allocator)
293 -> unordered_map<Key, T, Hash, equal_to<Key>, Allocator>; // C++17
294
295template <class Key, class T, class Hash, class Pred, class Alloc>
296 void swap(unordered_map<Key, T, Hash, Pred, Alloc>& x,
297 unordered_map<Key, T, Hash, Pred, Alloc>& y)
298 noexcept(noexcept(x.swap(y)));
299
300template <class Key, class T, class Hash, class Pred, class Alloc>
301 bool
302 operator==(const unordered_map<Key, T, Hash, Pred, Alloc>& x,
303 const unordered_map<Key, T, Hash, Pred, Alloc>& y);
304
305template <class Key, class T, class Hash, class Pred, class Alloc>
306 bool
307 operator!=(const unordered_map<Key, T, Hash, Pred, Alloc>& x,
308 const unordered_map<Key, T, Hash, Pred, Alloc>& y); // Removed in C++20
309
310template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
311 class Alloc = allocator<pair<const Key, T>>>
312class unordered_multimap
313{
314public:
315 // types
316 typedef Key key_type;
317 typedef T mapped_type;
318 typedef Hash hasher;
319 typedef Pred key_equal;
320 typedef Alloc allocator_type;
321 typedef pair<const key_type, mapped_type> value_type;
322 typedef value_type& reference;
323 typedef const value_type& const_reference;
324 typedef typename allocator_traits<allocator_type>::pointer pointer;
325 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
326 typedef typename allocator_traits<allocator_type>::size_type size_type;
327 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
328
329 typedef /unspecified/ iterator;
330 typedef /unspecified/ const_iterator;
331 typedef /unspecified/ local_iterator;
332 typedef /unspecified/ const_local_iterator;
333
334 typedef unspecified node_type; // C++17
335
336 unordered_multimap()
337 noexcept(
338 is_nothrow_default_constructible<hasher>::value &&
339 is_nothrow_default_constructible<key_equal>::value &&
340 is_nothrow_default_constructible<allocator_type>::value);
341 explicit unordered_multimap(size_type n, const hasher& hf = hasher(),
342 const key_equal& eql = key_equal(),
343 const allocator_type& a = allocator_type());
344 template <class InputIterator>
345 unordered_multimap(InputIterator f, InputIterator l,
346 size_type n = 0, const hasher& hf = hasher(),
347 const key_equal& eql = key_equal(),
348 const allocator_type& a = allocator_type());
349 template<container-compatible-range<value_type> R>
350 unordered_multimap(from_range_t, R&& rg, size_type n = see below,
351 const hasher& hf = hasher(), const key_equal& eql = key_equal(),
352 const allocator_type& a = allocator_type()); // C++23
353 explicit unordered_multimap(const allocator_type&);
354 unordered_multimap(const unordered_multimap&);
355 unordered_multimap(const unordered_multimap&, const Allocator&);
356 unordered_multimap(unordered_multimap&&)
357 noexcept(
358 is_nothrow_move_constructible<hasher>::value &&
359 is_nothrow_move_constructible<key_equal>::value &&
360 is_nothrow_move_constructible<allocator_type>::value);
361 unordered_multimap(unordered_multimap&&, const Allocator&);
362 unordered_multimap(initializer_list<value_type>, size_type n = 0,
363 const hasher& hf = hasher(), const key_equal& eql = key_equal(),
364 const allocator_type& a = allocator_type());
365 unordered_multimap(size_type n, const allocator_type& a)
366 : unordered_multimap(n, hasher(), key_equal(), a) {} // C++14
367 unordered_multimap(size_type n, const hasher& hf, const allocator_type& a)
368 : unordered_multimap(n, hf, key_equal(), a) {} // C++14
369 template <class InputIterator>
370 unordered_multimap(InputIterator f, InputIterator l, size_type n, const allocator_type& a)
371 : unordered_multimap(f, l, n, hasher(), key_equal(), a) {} // C++14
372 template <class InputIterator>
373 unordered_multimap(InputIterator f, InputIterator l, size_type n, const hasher& hf,
374 const allocator_type& a)
375 : unordered_multimap(f, l, n, hf, key_equal(), a) {} // C++14
376 template<container-compatible-range<value_type> R>
377 unordered_multimap(from_range_t, R&& rg, size_type n, const allocator_type& a)
378 : unordered_multimap(from_range, std::forward<R>(rg), n, hasher(), key_equal(), a) { } // C++23
379 template<container-compatible-range<value_type> R>
380 unordered_multimap(from_range_t, R&& rg, size_type n, const hasher& hf, const allocator_type& a)
381 : unordered_multimap(from_range, std::forward<R>(rg), n, hf, key_equal(), a) { } // C++23
382 unordered_multimap(initializer_list<value_type> il, size_type n, const allocator_type& a)
383 : unordered_multimap(il, n, hasher(), key_equal(), a) {} // C++14
384 unordered_multimap(initializer_list<value_type> il, size_type n, const hasher& hf,
385 const allocator_type& a)
386 : unordered_multimap(il, n, hf, key_equal(), a) {} // C++14
387 ~unordered_multimap();
388 unordered_multimap& operator=(const unordered_multimap&);
389 unordered_multimap& operator=(unordered_multimap&&)
390 noexcept(
391 allocator_type::propagate_on_container_move_assignment::value &&
392 is_nothrow_move_assignable<allocator_type>::value &&
393 is_nothrow_move_assignable<hasher>::value &&
394 is_nothrow_move_assignable<key_equal>::value);
395 unordered_multimap& operator=(initializer_list<value_type>);
396
397 allocator_type get_allocator() const noexcept;
398
399 bool empty() const noexcept;
400 size_type size() const noexcept;
401 size_type max_size() const noexcept;
402
403 iterator begin() noexcept;
404 iterator end() noexcept;
405 const_iterator begin() const noexcept;
406 const_iterator end() const noexcept;
407 const_iterator cbegin() const noexcept;
408 const_iterator cend() const noexcept;
409
410 template <class... Args>
411 iterator emplace(Args&&... args);
412 template <class... Args>
413 iterator emplace_hint(const_iterator position, Args&&... args);
414 iterator insert(const value_type& obj);
415 template <class P>
416 iterator insert(P&& obj);
417 iterator insert(const_iterator hint, const value_type& obj);
418 template <class P>
419 iterator insert(const_iterator hint, P&& obj);
420 template <class InputIterator>
421 void insert(InputIterator first, InputIterator last);
422 template<container-compatible-range<value_type> R>
423 void insert_range(R&& rg); // C++23
424 void insert(initializer_list<value_type>);
425
426 node_type extract(const_iterator position); // C++17
427 node_type extract(const key_type& x); // C++17
428 iterator insert(node_type&& nh); // C++17
429 iterator insert(const_iterator hint, node_type&& nh); // C++17
430
431 iterator erase(const_iterator position);
432 iterator erase(iterator position); // C++14
433 size_type erase(const key_type& k);
434 iterator erase(const_iterator first, const_iterator last);
435 void clear() noexcept;
436
437 template<class H2, class P2>
438 void merge(unordered_multimap<Key, T, H2, P2, Allocator>& source); // C++17
439 template<class H2, class P2>
440 void merge(unordered_multimap<Key, T, H2, P2, Allocator>&& source); // C++17
441 template<class H2, class P2>
442 void merge(unordered_map<Key, T, H2, P2, Allocator>& source); // C++17
443 template<class H2, class P2>
444 void merge(unordered_map<Key, T, H2, P2, Allocator>&& source); // C++17
445
446 void swap(unordered_multimap&)
447 noexcept(
448 (!allocator_type::propagate_on_container_swap::value ||
449 __is_nothrow_swappable<allocator_type>::value) &&
450 __is_nothrow_swappable<hasher>::value &&
451 __is_nothrow_swappable<key_equal>::value);
452
453 hasher hash_function() const;
454 key_equal key_eq() const;
455
456 iterator find(const key_type& k);
457 const_iterator find(const key_type& k) const;
458 template<typename K>
459 iterator find(const K& x); // C++20
460 template<typename K>
461 const_iterator find(const K& x) const; // C++20
462 size_type count(const key_type& k) const;
463 template<typename K>
464 size_type count(const K& k) const; // C++20
465 bool contains(const key_type& k) const; // C++20
466 template<typename K>
467 bool contains(const K& k) const; // C++20
468 pair<iterator, iterator> equal_range(const key_type& k);
469 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
470 template<typename K>
471 pair<iterator, iterator> equal_range(const K& k); // C++20
472 template<typename K>
473 pair<const_iterator, const_iterator> equal_range(const K& k) const; // C++20
474
475 size_type bucket_count() const noexcept;
476 size_type max_bucket_count() const noexcept;
477
478 size_type bucket_size(size_type n) const;
479 size_type bucket(const key_type& k) const;
480
481 local_iterator begin(size_type n);
482 local_iterator end(size_type n);
483 const_local_iterator begin(size_type n) const;
484 const_local_iterator end(size_type n) const;
485 const_local_iterator cbegin(size_type n) const;
486 const_local_iterator cend(size_type n) const;
487
488 float load_factor() const noexcept;
489 float max_load_factor() const noexcept;
490 void max_load_factor(float z);
491 void rehash(size_type n);
492 void reserve(size_type n);
493};
494
495template<class InputIterator,
496 class Hash = hash<iter_key_t<InputIterator>>, class Pred = equal_to<iter_key_t<InputIterator>>,
497 class Allocator = allocator<iter_to_alloc_t<InputIterator>>>
498unordered_multimap(InputIterator, InputIterator, typename see below::size_type = see below,
499 Hash = Hash(), Pred = Pred(), Allocator = Allocator())
500 -> unordered_multimap<iter_key_t<InputIterator>, iter_value_t<InputIterator>, Hash, Pred,
501 Allocator>; // C++17
502
503template<ranges::input_range R, class Hash = hash<range-key-type<R>>,
504 class Pred = equal_to<range-key-type<R>>,
505 class Allocator = allocator<range-to-alloc-type<R>>>
506 unordered_multimap(from_range_t, R&&, typename see below::size_type = see below,
507 Hash = Hash(), Pred = Pred(), Allocator = Allocator())
508 -> unordered_multimap<range-key-type<R>, range-mapped-type<R>, Hash, Pred, Allocator>; // C++23
509
510template<class Key, class T, class Hash = hash<Key>,
511 class Pred = equal_to<Key>, class Allocator = allocator<pair<const Key, T>>>
512unordered_multimap(initializer_list<pair<const Key, T>>, typename see below::size_type = see below,
513 Hash = Hash(), Pred = Pred(), Allocator = Allocator())
514 -> unordered_multimap<Key, T, Hash, Pred, Allocator>; // C++17
515
516template<class InputIterator, class Allocator>
517unordered_multimap(InputIterator, InputIterator, typename see below::size_type, Allocator)
518 -> unordered_multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>,
519 hash<iter_key_t<InputIterator>>, equal_to<iter_key_t<InputIterator>>, Allocator>; // C++17
520
521template<class InputIterator, class Allocator>
522unordered_multimap(InputIterator, InputIterator, Allocator)
523 -> unordered_multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>,
524 hash<iter_key_t<InputIterator>>, equal_to<iter_key_t<InputIterator>>, Allocator>; // C++17
525
526template<class InputIterator, class Hash, class Allocator>
527unordered_multimap(InputIterator, InputIterator, typename see below::size_type, Hash, Allocator)
528 -> unordered_multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>, Hash,
529 equal_to<iter_key_t<InputIterator>>, Allocator>; // C++17
530
531template<ranges::input_range R, class Allocator>
532 unordered_multimap(from_range_t, R&&, typename see below::size_type, Allocator)
533 -> unordered_multimap<range-key-type<R>, range-mapped-type<R>, hash<range-key-type<R>>,
534 equal_to<range-key-type<R>>, Allocator>; // C++23
535
536template<ranges::input_range R, class Allocator>
537 unordered_multimap(from_range_t, R&&, Allocator)
538 -> unordered_multimap<range-key-type<R>, range-mapped-type<R>, hash<range-key-type<R>>,
539 equal_to<range-key-type<R>>, Allocator>; // C++23
540
541template<ranges::input_range R, class Hash, class Allocator>
542 unordered_multimap(from_range_t, R&&, typename see below::size_type, Hash, Allocator)
543 -> unordered_multimap<range-key-type<R>, range-mapped-type<R>, Hash,
544 equal_to<range-key-type<R>>, Allocator>; // C++23
545
546template<class Key, class T, typename Allocator>
547unordered_multimap(initializer_list<pair<const Key, T>>, typename see below::size_type, Allocator)
548 -> unordered_multimap<Key, T, hash<Key>, equal_to<Key>, Allocator>; // C++17
549
550template<class Key, class T, typename Allocator>
551unordered_multimap(initializer_list<pair<const Key, T>>, Allocator)
552 -> unordered_multimap<Key, T, hash<Key>, equal_to<Key>, Allocator>; // C++17
553
554template<class Key, class T, class Hash, class Allocator>
555unordered_multimap(initializer_list<pair<const Key, T>>, typename see below::size_type, Hash,
556 Allocator)
557 -> unordered_multimap<Key, T, Hash, equal_to<Key>, Allocator>; // C++17
558
559template <class Key, class T, class Hash, class Pred, class Alloc>
560 void swap(unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
561 unordered_multimap<Key, T, Hash, Pred, Alloc>& y)
562 noexcept(noexcept(x.swap(y)));
563
564template <class K, class T, class H, class P, class A, class Predicate>
565 typename unordered_map<K, T, H, P, A>::size_type
566 erase_if(unordered_map<K, T, H, P, A>& c, Predicate pred); // C++20
567
568template <class K, class T, class H, class P, class A, class Predicate>
569 typename unordered_multimap<K, T, H, P, A>::size_type
570 erase_if(unordered_multimap<K, T, H, P, A>& c, Predicate pred); // C++20
571
572template <class Key, class T, class Hash, class Pred, class Alloc>
573 bool
574 operator==(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
575 const unordered_multimap<Key, T, Hash, Pred, Alloc>& y);
576
577template <class Key, class T, class Hash, class Pred, class Alloc>
578 bool
579 operator!=(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
580 const unordered_multimap<Key, T, Hash, Pred, Alloc>& y); // Removed in C++20
581
582} // std
583
584*/
585
586#if __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS)
587# include <__cxx03/unordered_map>
588#else
589# include <__algorithm/is_permutation.h>
590# include <__assert>
591# include <__config>
592# include <__functional/hash.h>
593# include <__functional/is_transparent.h>
594# include <__functional/operations.h>
595# include <__hash_table>
596# include <__iterator/distance.h>
597# include <__iterator/erase_if_container.h>
598# include <__iterator/iterator_traits.h>
599# include <__iterator/ranges_iterator_traits.h>
600# include <__memory/addressof.h>
601# include <__memory/allocator.h>
602# include <__memory/allocator_traits.h>
603# include <__memory/pointer_traits.h>
604# include <__memory/unique_ptr.h>
605# include <__memory_resource/polymorphic_allocator.h>
606# include <__new/launder.h>
607# include <__node_handle>
608# include <__ranges/concepts.h>
609# include <__ranges/container_compatible_range.h>
610# include <__ranges/from_range.h>
611# include <__type_traits/container_traits.h>
612# include <__type_traits/enable_if.h>
613# include <__type_traits/invoke.h>
614# include <__type_traits/is_allocator.h>
615# include <__type_traits/is_integral.h>
616# include <__type_traits/remove_const.h>
617# include <__type_traits/type_identity.h>
618# include <__utility/forward.h>
619# include <__utility/pair.h>
620# include <stdexcept>
621# include <tuple>
622# include <version>
623
624// standard-mandated includes
625
626// [iterator.range]
627# include <__iterator/access.h>
628# include <__iterator/data.h>
629# include <__iterator/empty.h>
630# include <__iterator/reverse_access.h>
631# include <__iterator/size.h>
632
633// [unord.map.syn]
634# include <compare>
635# include <initializer_list>
636
637# if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
638# pragma GCC system_header
639# endif
640
641_LIBCPP_PUSH_MACROS
642# include <__undef_macros>
643
644_LIBCPP_BEGIN_NAMESPACE_STD
645
646template <class _Key,
647 class _Cp,
648 class _Hash,
649 class _Pred,
650 bool = is_empty<_Hash>::value && !__libcpp_is_final<_Hash>::value>
651class __unordered_map_hasher : private _Hash {
652public:
653 _LIBCPP_HIDE_FROM_ABI __unordered_map_hasher() _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value) : _Hash() {}
654 _LIBCPP_HIDE_FROM_ABI __unordered_map_hasher(const _Hash& __h) _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value)
655 : _Hash(__h) {}
656 _LIBCPP_HIDE_FROM_ABI const _Hash& hash_function() const _NOEXCEPT { return *this; }
657 _LIBCPP_HIDE_FROM_ABI size_t operator()(const _Cp& __x) const { return static_cast<const _Hash&>(*this)(__x.first); }
658 _LIBCPP_HIDE_FROM_ABI size_t operator()(const _Key& __x) const { return static_cast<const _Hash&>(*this)(__x); }
659# if _LIBCPP_STD_VER >= 20
660 template <typename _K2>
661 _LIBCPP_HIDE_FROM_ABI size_t operator()(const _K2& __x) const {
662 return static_cast<const _Hash&>(*this)(__x);
663 }
664# endif
665 _LIBCPP_HIDE_FROM_ABI void swap(__unordered_map_hasher& __y) _NOEXCEPT_(__is_nothrow_swappable_v<_Hash>) {
666 using std::swap;
667 swap(static_cast<_Hash&>(*this), static_cast<_Hash&>(__y));
668 }
669};
670
671template <class _Key, class _Cp, class _Hash, class _Pred>
672class __unordered_map_hasher<_Key, _Cp, _Hash, _Pred, false> {
673 _Hash __hash_;
674
675public:
676 _LIBCPP_HIDE_FROM_ABI __unordered_map_hasher() _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value)
677 : __hash_() {}
678 _LIBCPP_HIDE_FROM_ABI __unordered_map_hasher(const _Hash& __h) _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value)
679 : __hash_(__h) {}
680 _LIBCPP_HIDE_FROM_ABI const _Hash& hash_function() const _NOEXCEPT { return __hash_; }
681 _LIBCPP_HIDE_FROM_ABI size_t operator()(const _Cp& __x) const { return __hash_(__x.first); }
682 _LIBCPP_HIDE_FROM_ABI size_t operator()(const _Key& __x) const { return __hash_(__x); }
683# if _LIBCPP_STD_VER >= 20
684 template <typename _K2>
685 _LIBCPP_HIDE_FROM_ABI size_t operator()(const _K2& __x) const {
686 return __hash_(__x);
687 }
688# endif
689 _LIBCPP_HIDE_FROM_ABI void swap(__unordered_map_hasher& __y) _NOEXCEPT_(__is_nothrow_swappable_v<_Hash>) {
690 using std::swap;
691 swap(__hash_, __y.__hash_);
692 }
693};
694
695template <class _Key, class _Cp, class _Hash, class _Pred, bool __b>
696inline _LIBCPP_HIDE_FROM_ABI void
697swap(__unordered_map_hasher<_Key, _Cp, _Hash, _Pred, __b>& __x,
698 __unordered_map_hasher<_Key, _Cp, _Hash, _Pred, __b>& __y) _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
699 __x.swap(__y);
700}
701
702template <class _Key,
703 class _Cp,
704 class _Pred,
705 class _Hash,
706 bool = is_empty<_Pred>::value && !__libcpp_is_final<_Pred>::value>
707class __unordered_map_equal : private _Pred {
708public:
709 _LIBCPP_HIDE_FROM_ABI __unordered_map_equal() _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value) : _Pred() {}
710 _LIBCPP_HIDE_FROM_ABI __unordered_map_equal(const _Pred& __p) _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value)
711 : _Pred(__p) {}
712 _LIBCPP_HIDE_FROM_ABI const _Pred& key_eq() const _NOEXCEPT { return *this; }
713 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Cp& __x, const _Cp& __y) const {
714 return static_cast<const _Pred&>(*this)(__x.first, __y.first);
715 }
716 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Cp& __x, const _Key& __y) const {
717 return static_cast<const _Pred&>(*this)(__x.first, __y);
718 }
719 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Key& __x, const _Cp& __y) const {
720 return static_cast<const _Pred&>(*this)(__x, __y.__get_value().first);
721 }
722# if _LIBCPP_STD_VER >= 20
723 template <typename _K2>
724 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Cp& __x, const _K2& __y) const {
725 return static_cast<const _Pred&>(*this)(__x.first, __y);
726 }
727 template <typename _K2>
728 _LIBCPP_HIDE_FROM_ABI bool operator()(const _K2& __x, const _Cp& __y) const {
729 return static_cast<const _Pred&>(*this)(__x, __y.__get_value().first);
730 }
731 template <typename _K2>
732 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Key& __x, const _K2& __y) const {
733 return static_cast<const _Pred&>(*this)(__x, __y);
734 }
735 template <typename _K2>
736 _LIBCPP_HIDE_FROM_ABI bool operator()(const _K2& __x, const _Key& __y) const {
737 return static_cast<const _Pred&>(*this)(__x, __y);
738 }
739# endif
740 _LIBCPP_HIDE_FROM_ABI void swap(__unordered_map_equal& __y) _NOEXCEPT_(__is_nothrow_swappable_v<_Pred>) {
741 using std::swap;
742 swap(static_cast<_Pred&>(*this), static_cast<_Pred&>(__y));
743 }
744};
745
746template <class _Key, class _Cp, class _Pred, class _Hash>
747class __unordered_map_equal<_Key, _Cp, _Pred, _Hash, false> {
748 _Pred __pred_;
749
750public:
751 _LIBCPP_HIDE_FROM_ABI __unordered_map_equal() _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value)
752 : __pred_() {}
753 _LIBCPP_HIDE_FROM_ABI __unordered_map_equal(const _Pred& __p) _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value)
754 : __pred_(__p) {}
755 _LIBCPP_HIDE_FROM_ABI const _Pred& key_eq() const _NOEXCEPT { return __pred_; }
756 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Cp& __x, const _Cp& __y) const { return __pred_(__x.first, __y.first); }
757 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Cp& __x, const _Key& __y) const { return __pred_(__x.first, __y); }
758 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Key& __x, const _Cp& __y) const { return __pred_(__x, __y.first); }
759# if _LIBCPP_STD_VER >= 20
760 template <typename _K2>
761 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Cp& __x, const _K2& __y) const {
762 return __pred_(__x.first, __y);
763 }
764 template <typename _K2>
765 _LIBCPP_HIDE_FROM_ABI bool operator()(const _K2& __x, const _Cp& __y) const {
766 return __pred_(__x, __y.first);
767 }
768 template <typename _K2>
769 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Key& __x, const _K2& __y) const {
770 return __pred_(__x, __y);
771 }
772 template <typename _K2>
773 _LIBCPP_HIDE_FROM_ABI bool operator()(const _K2& __x, const _Key& __y) const {
774 return __pred_(__x, __y);
775 }
776# endif
777 _LIBCPP_HIDE_FROM_ABI void swap(__unordered_map_equal& __y) _NOEXCEPT_(__is_nothrow_swappable_v<_Pred>) {
778 using std::swap;
779 swap(__pred_, __y.__pred_);
780 }
781};
782
783template <class _Key, class _Cp, class _Pred, class _Hash, bool __b>
784inline _LIBCPP_HIDE_FROM_ABI void
785swap(__unordered_map_equal<_Key, _Cp, _Pred, _Hash, __b>& __x, __unordered_map_equal<_Key, _Cp, _Pred, _Hash, __b>& __y)
786 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
787 __x.swap(__y);
788}
789
790template <class _Alloc>
791class __hash_map_node_destructor {
792 typedef _Alloc allocator_type;
793 typedef allocator_traits<allocator_type> __alloc_traits;
794
795public:
796 typedef typename __alloc_traits::pointer pointer;
797
798private:
799 allocator_type& __na_;
800
801public:
802 bool __first_constructed;
803 bool __second_constructed;
804
805 __hash_map_node_destructor& operator=(const __hash_map_node_destructor&) = delete;
806
807 _LIBCPP_HIDE_FROM_ABI explicit __hash_map_node_destructor(allocator_type& __na) _NOEXCEPT
808 : __na_(__na),
809 __first_constructed(false),
810 __second_constructed(false) {}
811
812# ifndef _LIBCPP_CXX03_LANG
813 _LIBCPP_HIDE_FROM_ABI __hash_map_node_destructor(__hash_node_destructor<allocator_type>&& __x) _NOEXCEPT
814 : __na_(__x.__na_),
815 __first_constructed(__x.__value_constructed),
816 __second_constructed(__x.__value_constructed) {
817 __x.__value_constructed = false;
818 }
819# else // _LIBCPP_CXX03_LANG
820 _LIBCPP_HIDE_FROM_ABI __hash_map_node_destructor(const __hash_node_destructor<allocator_type>& __x)
821 : __na_(__x.__na_), __first_constructed(__x.__value_constructed), __second_constructed(__x.__value_constructed) {
822 const_cast<bool&>(__x.__value_constructed) = false;
823 }
824# endif // _LIBCPP_CXX03_LANG
825
826 _LIBCPP_HIDE_FROM_ABI void operator()(pointer __p) _NOEXCEPT {
827 if (__second_constructed)
828 __alloc_traits::destroy(__na_, std::addressof(__p->__get_value().second));
829 if (__first_constructed)
830 __alloc_traits::destroy(__na_, std::addressof(__p->__get_value().first));
831 if (__p)
832 __alloc_traits::deallocate(__na_, __p, 1);
833 }
834};
835
836template <class _Key, class _Tp>
837struct __hash_value_type;
838
839template <class _HashIterator>
840class __hash_map_iterator {
841 _HashIterator __i_;
842
843 typedef __hash_node_types_from_iterator<_HashIterator> _NodeTypes;
844
845public:
846 typedef forward_iterator_tag iterator_category;
847 typedef typename _NodeTypes::__map_value_type value_type;
848 typedef typename _NodeTypes::difference_type difference_type;
849 typedef value_type& reference;
850 typedef typename _NodeTypes::__map_value_type_pointer pointer;
851
852 _LIBCPP_HIDE_FROM_ABI __hash_map_iterator() _NOEXCEPT {}
853
854 _LIBCPP_HIDE_FROM_ABI __hash_map_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
855
856 _LIBCPP_HIDE_FROM_ABI reference operator*() const { return *__i_; }
857 _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return pointer_traits<pointer>::pointer_to(*__i_); }
858
859 _LIBCPP_HIDE_FROM_ABI __hash_map_iterator& operator++() {
860 ++__i_;
861 return *this;
862 }
863 _LIBCPP_HIDE_FROM_ABI __hash_map_iterator operator++(int) {
864 __hash_map_iterator __t(*this);
865 ++(*this);
866 return __t;
867 }
868
869 friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y) {
870 return __x.__i_ == __y.__i_;
871 }
872# if _LIBCPP_STD_VER <= 17
873 friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y) {
874 return __x.__i_ != __y.__i_;
875 }
876# endif
877
878 template <class, class, class, class, class>
879 friend class unordered_map;
880 template <class, class, class, class, class>
881 friend class unordered_multimap;
882 template <class>
883 friend class __hash_const_iterator;
884 template <class>
885 friend class __hash_const_local_iterator;
886 template <class>
887 friend class __hash_map_const_iterator;
888};
889
890template <class _HashIterator>
891class __hash_map_const_iterator {
892 _HashIterator __i_;
893
894 typedef __hash_node_types_from_iterator<_HashIterator> _NodeTypes;
895
896public:
897 typedef forward_iterator_tag iterator_category;
898 typedef typename _NodeTypes::__map_value_type value_type;
899 typedef typename _NodeTypes::difference_type difference_type;
900 typedef const value_type& reference;
901 typedef typename _NodeTypes::__const_map_value_type_pointer pointer;
902
903 _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator() _NOEXCEPT {}
904
905 _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
906 _LIBCPP_HIDE_FROM_ABI
907 __hash_map_const_iterator(__hash_map_iterator<typename _HashIterator::__non_const_iterator> __i) _NOEXCEPT
908 : __i_(__i.__i_) {}
909
910 _LIBCPP_HIDE_FROM_ABI reference operator*() const { return *__i_; }
911 _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return pointer_traits<pointer>::pointer_to(*__i_); }
912
913 _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator& operator++() {
914 ++__i_;
915 return *this;
916 }
917 _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator operator++(int) {
918 __hash_map_const_iterator __t(*this);
919 ++(*this);
920 return __t;
921 }
922
923 friend _LIBCPP_HIDE_FROM_ABI bool
924 operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) {
925 return __x.__i_ == __y.__i_;
926 }
927# if _LIBCPP_STD_VER <= 17
928 friend _LIBCPP_HIDE_FROM_ABI bool
929 operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) {
930 return __x.__i_ != __y.__i_;
931 }
932# endif
933
934 template <class, class, class, class, class>
935 friend class unordered_map;
936 template <class, class, class, class, class>
937 friend class unordered_multimap;
938 template <class>
939 friend class __hash_const_iterator;
940 template <class>
941 friend class __hash_const_local_iterator;
942};
943
944template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
945class unordered_multimap;
946
947template <class _Key,
948 class _Tp,
949 class _Hash = hash<_Key>,
950 class _Pred = equal_to<_Key>,
951 class _Alloc = allocator<pair<const _Key, _Tp> > >
952class unordered_map {
953public:
954 // types
955 typedef _Key key_type;
956 typedef _Tp mapped_type;
957 typedef __type_identity_t<_Hash> hasher;
958 typedef __type_identity_t<_Pred> key_equal;
959 typedef __type_identity_t<_Alloc> allocator_type;
960 typedef pair<const key_type, mapped_type> value_type;
961 typedef value_type& reference;
962 typedef const value_type& const_reference;
963 static_assert(is_same<value_type, typename allocator_type::value_type>::value,
964 "Allocator::value_type must be same type as value_type");
965
966private:
967 typedef __hash_value_type<key_type, mapped_type> __value_type;
968 typedef __unordered_map_hasher<key_type, value_type, hasher, key_equal> __hasher;
969 typedef __unordered_map_equal<key_type, value_type, key_equal, hasher> __key_equal;
970 typedef __rebind_alloc<allocator_traits<allocator_type>, __value_type> __allocator_type;
971
972 typedef __hash_table<__value_type, __hasher, __key_equal, __allocator_type> __table;
973
974 __table __table_;
975
976 typedef typename __table::_NodeTypes _NodeTypes;
977 typedef typename __table::__node_pointer __node_pointer;
978 typedef typename __table::__node_const_pointer __node_const_pointer;
979 typedef typename __table::__node_traits __node_traits;
980 typedef typename __table::__node_allocator __node_allocator;
981 typedef typename __table::__node __node;
982 typedef __hash_map_node_destructor<__node_allocator> _Dp;
983 typedef unique_ptr<__node, _Dp> __node_holder;
984 typedef allocator_traits<allocator_type> __alloc_traits;
985
986 static_assert(__check_valid_allocator<allocator_type>::value, "");
987
988public:
989 typedef typename __alloc_traits::pointer pointer;
990 typedef typename __alloc_traits::const_pointer const_pointer;
991 typedef typename __table::size_type size_type;
992 typedef typename __table::difference_type difference_type;
993
994 typedef __hash_map_iterator<typename __table::iterator> iterator;
995 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
996 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
997 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
998
999# if _LIBCPP_STD_VER >= 17
1000 typedef __map_node_handle<__node, allocator_type> node_type;
1001 typedef __insert_return_type<iterator, node_type> insert_return_type;
1002# endif
1003
1004 template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2>
1005 friend class unordered_map;
1006 template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2>
1007 friend class unordered_multimap;
1008
1009 _LIBCPP_HIDE_FROM_ABI unordered_map() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) {}
1010 explicit _LIBCPP_HIDE_FROM_ABI
1011 unordered_map(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
1012 _LIBCPP_HIDE_FROM_ABI
1013 unordered_map(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a);
1014 template <class _InputIterator>
1015 _LIBCPP_HIDE_FROM_ABI unordered_map(_InputIterator __first, _InputIterator __last);
1016 template <class _InputIterator>
1017 _LIBCPP_HIDE_FROM_ABI
1018 unordered_map(_InputIterator __first,
1019 _InputIterator __last,
1020 size_type __n,
1021 const hasher& __hf = hasher(),
1022 const key_equal& __eql = key_equal());
1023 template <class _InputIterator>
1024 _LIBCPP_HIDE_FROM_ABI unordered_map(
1025 _InputIterator __first,
1026 _InputIterator __last,
1027 size_type __n,
1028 const hasher& __hf,
1029 const key_equal& __eql,
1030 const allocator_type& __a);
1031
1032# if _LIBCPP_STD_VER >= 23
1033 template <_ContainerCompatibleRange<value_type> _Range>
1034 _LIBCPP_HIDE_FROM_ABI unordered_map(
1035 from_range_t,
1036 _Range&& __range,
1037 size_type __n = /*implementation-defined*/ 0,
1038 const hasher& __hf = hasher(),
1039 const key_equal& __eql = key_equal(),
1040 const allocator_type& __a = allocator_type())
1041 : __table_(__hf, __eql, typename __table::allocator_type(__a)) {
1042 if (__n > 0) {
1043 __table_.__rehash_unique(__n);
1044 }
1045 insert_range(std::forward<_Range>(__range));
1046 }
1047# endif
1048
1049 _LIBCPP_HIDE_FROM_ABI explicit unordered_map(const allocator_type& __a);
1050 _LIBCPP_HIDE_FROM_ABI unordered_map(const unordered_map& __u);
1051 _LIBCPP_HIDE_FROM_ABI unordered_map(const unordered_map& __u, const allocator_type& __a);
1052# ifndef _LIBCPP_CXX03_LANG
1053 _LIBCPP_HIDE_FROM_ABI unordered_map(unordered_map&& __u) _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
1054 _LIBCPP_HIDE_FROM_ABI unordered_map(unordered_map&& __u, const allocator_type& __a);
1055 _LIBCPP_HIDE_FROM_ABI unordered_map(initializer_list<value_type> __il);
1056 _LIBCPP_HIDE_FROM_ABI
1057 unordered_map(initializer_list<value_type> __il,
1058 size_type __n,
1059 const hasher& __hf = hasher(),
1060 const key_equal& __eql = key_equal());
1061 _LIBCPP_HIDE_FROM_ABI unordered_map(
1062 initializer_list<value_type> __il,
1063 size_type __n,
1064 const hasher& __hf,
1065 const key_equal& __eql,
1066 const allocator_type& __a);
1067# endif // _LIBCPP_CXX03_LANG
1068# if _LIBCPP_STD_VER >= 14
1069 _LIBCPP_HIDE_FROM_ABI unordered_map(size_type __n, const allocator_type& __a)
1070 : unordered_map(__n, hasher(), key_equal(), __a) {}
1071 _LIBCPP_HIDE_FROM_ABI unordered_map(size_type __n, const hasher& __hf, const allocator_type& __a)
1072 : unordered_map(__n, __hf, key_equal(), __a) {}
1073 template <class _InputIterator>
1074 _LIBCPP_HIDE_FROM_ABI
1075 unordered_map(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a)
1076 : unordered_map(__first, __last, __n, hasher(), key_equal(), __a) {}
1077 template <class _InputIterator>
1078 _LIBCPP_HIDE_FROM_ABI unordered_map(
1079 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const allocator_type& __a)
1080 : unordered_map(__first, __last, __n, __hf, key_equal(), __a) {}
1081
1082# if _LIBCPP_STD_VER >= 23
1083 template <_ContainerCompatibleRange<value_type> _Range>
1084 _LIBCPP_HIDE_FROM_ABI unordered_map(from_range_t, _Range&& __range, size_type __n, const allocator_type& __a)
1085 : unordered_map(from_range, std::forward<_Range>(__range), __n, hasher(), key_equal(), __a) {}
1086
1087 template <_ContainerCompatibleRange<value_type> _Range>
1088 _LIBCPP_HIDE_FROM_ABI
1089 unordered_map(from_range_t, _Range&& __range, size_type __n, const hasher& __hf, const allocator_type& __a)
1090 : unordered_map(from_range, std::forward<_Range>(__range), __n, __hf, key_equal(), __a) {}
1091# endif
1092
1093 _LIBCPP_HIDE_FROM_ABI unordered_map(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)
1094 : unordered_map(__il, __n, hasher(), key_equal(), __a) {}
1095 _LIBCPP_HIDE_FROM_ABI
1096 unordered_map(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a)
1097 : unordered_map(__il, __n, __hf, key_equal(), __a) {}
1098# endif
1099 _LIBCPP_HIDE_FROM_ABI ~unordered_map() {
1100 static_assert(sizeof(std::__diagnose_unordered_container_requirements<_Key, _Hash, _Pred>(0)), "");
1101 }
1102
1103 _LIBCPP_HIDE_FROM_ABI unordered_map& operator=(const unordered_map& __u) {
1104# ifndef _LIBCPP_CXX03_LANG
1105 __table_ = __u.__table_;
1106# else
1107 if (this != std::addressof(__u)) {
1108 __table_.clear();
1109 __table_.hash_function() = __u.__table_.hash_function();
1110 __table_.key_eq() = __u.__table_.key_eq();
1111 __table_.max_load_factor() = __u.__table_.max_load_factor();
1112 __table_.__copy_assign_alloc(__u.__table_);
1113 insert(__u.begin(), __u.end());
1114 }
1115# endif
1116 return *this;
1117 }
1118# ifndef _LIBCPP_CXX03_LANG
1119 _LIBCPP_HIDE_FROM_ABI unordered_map& operator=(unordered_map&& __u)
1120 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
1121 _LIBCPP_HIDE_FROM_ABI unordered_map& operator=(initializer_list<value_type> __il);
1122# endif // _LIBCPP_CXX03_LANG
1123
1124 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT {
1125 return allocator_type(__table_.__node_alloc());
1126 }
1127
1128 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __table_.size() == 0; }
1129 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __table_.size(); }
1130 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __table_.max_size(); }
1131
1132 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __table_.begin(); }
1133 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __table_.end(); }
1134 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __table_.begin(); }
1135 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __table_.end(); }
1136 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return __table_.begin(); }
1137 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return __table_.end(); }
1138
1139 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(const value_type& __x) { return __table_.__insert_unique(__x); }
1140
1141 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, const value_type& __x) { return insert(__x).first; }
1142
1143 template <class _InputIterator>
1144 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last);
1145
1146# if _LIBCPP_STD_VER >= 23
1147 template <_ContainerCompatibleRange<value_type> _Range>
1148 _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) {
1149 for (auto&& __element : __range) {
1150 __table_.__insert_unique(std::forward<decltype(__element)>(__element));
1151 }
1152 }
1153# endif
1154
1155# ifndef _LIBCPP_CXX03_LANG
1156 _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); }
1157
1158 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(value_type&& __x) {
1159 return __table_.__insert_unique(std::move(__x));
1160 }
1161
1162 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, value_type&& __x) {
1163 return __table_.__insert_unique(std::move(__x)).first;
1164 }
1165
1166 template <class _Pp, __enable_if_t<is_constructible<value_type, _Pp>::value, int> = 0>
1167 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(_Pp&& __x) {
1168 return __table_.__insert_unique(std::forward<_Pp>(__x));
1169 }
1170
1171 template <class _Pp, __enable_if_t<is_constructible<value_type, _Pp>::value, int> = 0>
1172 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, _Pp&& __x) {
1173 return insert(std::forward<_Pp>(__x)).first;
1174 }
1175
1176 template <class... _Args>
1177 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> emplace(_Args&&... __args) {
1178 return __table_.__emplace_unique(std::forward<_Args>(__args)...);
1179 }
1180
1181 template <class... _Args>
1182 _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator, _Args&&... __args) {
1183 return __table_.__emplace_unique(std::forward<_Args>(__args)...).first;
1184 }
1185
1186# endif // _LIBCPP_CXX03_LANG
1187
1188# if _LIBCPP_STD_VER >= 17
1189 template <class... _Args>
1190 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args) {
1191 return __table_.__emplace_unique_key_args(
1192 __k, piecewise_construct, std::forward_as_tuple(__k), std::forward_as_tuple(std::forward<_Args>(__args)...));
1193 }
1194
1195 template <class... _Args>
1196 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args) {
1197 return __table_.__emplace_unique_key_args(
1198 __k,
1199 piecewise_construct,
1200 std::forward_as_tuple(std::move(__k)),
1201 std::forward_as_tuple(std::forward<_Args>(__args)...));
1202 }
1203
1204 template <class... _Args>
1205 _LIBCPP_HIDE_FROM_ABI iterator try_emplace(const_iterator, const key_type& __k, _Args&&... __args) {
1206 return try_emplace(__k, std::forward<_Args>(__args)...).first;
1207 }
1208
1209 template <class... _Args>
1210 _LIBCPP_HIDE_FROM_ABI iterator try_emplace(const_iterator, key_type&& __k, _Args&&... __args) {
1211 return try_emplace(std::move(__k), std::forward<_Args>(__args)...).first;
1212 }
1213
1214 template <class _Vp>
1215 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert_or_assign(const key_type& __k, _Vp&& __v) {
1216 pair<iterator, bool> __res = __table_.__emplace_unique_key_args(__k, __k, std::forward<_Vp>(__v));
1217 if (!__res.second) {
1218 __res.first->second = std::forward<_Vp>(__v);
1219 }
1220 return __res;
1221 }
1222
1223 template <class _Vp>
1224 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert_or_assign(key_type&& __k, _Vp&& __v) {
1225 pair<iterator, bool> __res = __table_.__emplace_unique_key_args(__k, std::move(__k), std::forward<_Vp>(__v));
1226 if (!__res.second) {
1227 __res.first->second = std::forward<_Vp>(__v);
1228 }
1229 return __res;
1230 }
1231
1232 template <class _Vp>
1233 _LIBCPP_HIDE_FROM_ABI iterator insert_or_assign(const_iterator, const key_type& __k, _Vp&& __v) {
1234 return insert_or_assign(__k, std::forward<_Vp>(__v)).first;
1235 }
1236
1237 template <class _Vp>
1238 _LIBCPP_HIDE_FROM_ABI iterator insert_or_assign(const_iterator, key_type&& __k, _Vp&& __v) {
1239 return insert_or_assign(std::move(__k), std::forward<_Vp>(__v)).first;
1240 }
1241# endif // _LIBCPP_STD_VER >= 17
1242
1243 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __table_.erase(__p.__i_); }
1244 _LIBCPP_HIDE_FROM_ABI iterator erase(iterator __p) { return __table_.erase(__p.__i_); }
1245 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_unique(__k); }
1246 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last) {
1247 return __table_.erase(__first.__i_, __last.__i_);
1248 }
1249 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __table_.clear(); }
1250
1251# if _LIBCPP_STD_VER >= 17
1252 _LIBCPP_HIDE_FROM_ABI insert_return_type insert(node_type&& __nh) {
1253 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
1254 "node_type with incompatible allocator passed to unordered_map::insert()");
1255 return __table_.template __node_handle_insert_unique< node_type, insert_return_type>(std::move(__nh));
1256 }
1257 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, node_type&& __nh) {
1258 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
1259 "node_type with incompatible allocator passed to unordered_map::insert()");
1260 return __table_.template __node_handle_insert_unique<node_type>(__hint.__i_, std::move(__nh));
1261 }
1262 _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) {
1263 return __table_.template __node_handle_extract<node_type>(__key);
1264 }
1265 _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __it) {
1266 return __table_.template __node_handle_extract<node_type>(__it.__i_);
1267 }
1268
1269 template <class _H2, class _P2>
1270 _LIBCPP_HIDE_FROM_ABI void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>& __source) {
1271 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1272 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1273 return __table_.__node_handle_merge_unique(__source.__table_);
1274 }
1275 template <class _H2, class _P2>
1276 _LIBCPP_HIDE_FROM_ABI void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>&& __source) {
1277 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1278 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1279 return __table_.__node_handle_merge_unique(__source.__table_);
1280 }
1281 template <class _H2, class _P2>
1282 _LIBCPP_HIDE_FROM_ABI void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>& __source) {
1283 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1284 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1285 return __table_.__node_handle_merge_unique(__source.__table_);
1286 }
1287 template <class _H2, class _P2>
1288 _LIBCPP_HIDE_FROM_ABI void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>&& __source) {
1289 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1290 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1291 return __table_.__node_handle_merge_unique(__source.__table_);
1292 }
1293# endif
1294
1295 _LIBCPP_HIDE_FROM_ABI void swap(unordered_map& __u) _NOEXCEPT_(__is_nothrow_swappable_v<__table>) {
1296 __table_.swap(__u.__table_);
1297 }
1298
1299 _LIBCPP_HIDE_FROM_ABI hasher hash_function() const { return __table_.hash_function().hash_function(); }
1300 _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq().key_eq(); }
1301
1302 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); }
1303 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); }
1304# if _LIBCPP_STD_VER >= 20
1305 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
1306 _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) {
1307 return __table_.find(__k);
1308 }
1309 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
1310 _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const {
1311 return __table_.find(__k);
1312 }
1313# endif // _LIBCPP_STD_VER >= 20
1314
1315 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_unique(__k); }
1316# if _LIBCPP_STD_VER >= 20
1317 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
1318 _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const {
1319 return __table_.__count_unique(__k);
1320 }
1321# endif // _LIBCPP_STD_VER >= 20
1322
1323# if _LIBCPP_STD_VER >= 20
1324 _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); }
1325
1326 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
1327 _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const {
1328 return find(__k) != end();
1329 }
1330# endif // _LIBCPP_STD_VER >= 20
1331
1332 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {
1333 return __table_.__equal_range_unique(__k);
1334 }
1335 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
1336 return __table_.__equal_range_unique(__k);
1337 }
1338# if _LIBCPP_STD_VER >= 20
1339 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
1340 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) {
1341 return __table_.__equal_range_unique(__k);
1342 }
1343 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
1344 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const {
1345 return __table_.__equal_range_unique(__k);
1346 }
1347# endif // _LIBCPP_STD_VER >= 20
1348
1349 _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](const key_type& __k);
1350# ifndef _LIBCPP_CXX03_LANG
1351 _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](key_type&& __k);
1352# endif
1353
1354 _LIBCPP_HIDE_FROM_ABI mapped_type& at(const key_type& __k);
1355 _LIBCPP_HIDE_FROM_ABI const mapped_type& at(const key_type& __k) const;
1356
1357 _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const _NOEXCEPT { return __table_.bucket_count(); }
1358 _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const _NOEXCEPT { return __table_.max_bucket_count(); }
1359
1360 _LIBCPP_HIDE_FROM_ABI size_type bucket_size(size_type __n) const { return __table_.bucket_size(__n); }
1361 _LIBCPP_HIDE_FROM_ABI size_type bucket(const key_type& __k) const { return __table_.bucket(__k); }
1362
1363 _LIBCPP_HIDE_FROM_ABI local_iterator begin(size_type __n) { return __table_.begin(__n); }
1364 _LIBCPP_HIDE_FROM_ABI local_iterator end(size_type __n) { return __table_.end(__n); }
1365 _LIBCPP_HIDE_FROM_ABI const_local_iterator begin(size_type __n) const { return __table_.cbegin(__n); }
1366 _LIBCPP_HIDE_FROM_ABI const_local_iterator end(size_type __n) const { return __table_.cend(__n); }
1367 _LIBCPP_HIDE_FROM_ABI const_local_iterator cbegin(size_type __n) const { return __table_.cbegin(__n); }
1368 _LIBCPP_HIDE_FROM_ABI const_local_iterator cend(size_type __n) const { return __table_.cend(__n); }
1369
1370 _LIBCPP_HIDE_FROM_ABI float load_factor() const _NOEXCEPT { return __table_.load_factor(); }
1371 _LIBCPP_HIDE_FROM_ABI float max_load_factor() const _NOEXCEPT { return __table_.max_load_factor(); }
1372 _LIBCPP_HIDE_FROM_ABI void max_load_factor(float __mlf) { __table_.max_load_factor(__mlf); }
1373 _LIBCPP_HIDE_FROM_ABI void rehash(size_type __n) { __table_.__rehash_unique(__n); }
1374 _LIBCPP_HIDE_FROM_ABI void reserve(size_type __n) { __table_.__reserve_unique(__n); }
1375
1376private:
1377# ifdef _LIBCPP_CXX03_LANG
1378 _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node_with_key(const key_type& __k);
1379# endif
1380};
1381
1382# if _LIBCPP_STD_VER >= 17
1383template <class _InputIterator,
1384 class _Hash = hash<__iter_key_type<_InputIterator>>,
1385 class _Pred = equal_to<__iter_key_type<_InputIterator>>,
1386 class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>,
1387 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
1388 class = enable_if_t<!__is_allocator<_Hash>::value>,
1389 class = enable_if_t<!is_integral<_Hash>::value>,
1390 class = enable_if_t<!__is_allocator<_Pred>::value>,
1391 class = enable_if_t<__is_allocator<_Allocator>::value>>
1392unordered_map(_InputIterator,
1393 _InputIterator,
1394 typename allocator_traits<_Allocator>::size_type = 0,
1395 _Hash = _Hash(),
1396 _Pred = _Pred(),
1397 _Allocator = _Allocator())
1398 -> unordered_map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Hash, _Pred, _Allocator>;
1399
1400# if _LIBCPP_STD_VER >= 23
1401template <ranges::input_range _Range,
1402 class _Hash = hash<__range_key_type<_Range>>,
1403 class _Pred = equal_to<__range_key_type<_Range>>,
1404 class _Allocator = allocator<__range_to_alloc_type<_Range>>,
1405 class = enable_if_t<!__is_allocator<_Hash>::value>,
1406 class = enable_if_t<!is_integral<_Hash>::value>,
1407 class = enable_if_t<!__is_allocator<_Pred>::value>,
1408 class = enable_if_t<__is_allocator<_Allocator>::value>>
1409unordered_map(from_range_t,
1410 _Range&&,
1411 typename allocator_traits<_Allocator>::size_type = 0,
1412 _Hash = _Hash(),
1413 _Pred = _Pred(),
1414 _Allocator = _Allocator())
1415 -> unordered_map<__range_key_type<_Range>, __range_mapped_type<_Range>, _Hash, _Pred, _Allocator>; // C++23
1416# endif
1417
1418template <class _Key,
1419 class _Tp,
1420 class _Hash = hash<remove_const_t<_Key>>,
1421 class _Pred = equal_to<remove_const_t<_Key>>,
1422 class _Allocator = allocator<pair<const _Key, _Tp>>,
1423 class = enable_if_t<!__is_allocator<_Hash>::value>,
1424 class = enable_if_t<!is_integral<_Hash>::value>,
1425 class = enable_if_t<!__is_allocator<_Pred>::value>,
1426 class = enable_if_t<__is_allocator<_Allocator>::value>>
1427unordered_map(initializer_list<pair<_Key, _Tp>>,
1428 typename allocator_traits<_Allocator>::size_type = 0,
1429 _Hash = _Hash(),
1430 _Pred = _Pred(),
1431 _Allocator = _Allocator()) -> unordered_map<remove_const_t<_Key>, _Tp, _Hash, _Pred, _Allocator>;
1432
1433template <class _InputIterator,
1434 class _Allocator,
1435 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
1436 class = enable_if_t<__is_allocator<_Allocator>::value>>
1437unordered_map(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Allocator)
1438 -> unordered_map<__iter_key_type<_InputIterator>,
1439 __iter_mapped_type<_InputIterator>,
1440 hash<__iter_key_type<_InputIterator>>,
1441 equal_to<__iter_key_type<_InputIterator>>,
1442 _Allocator>;
1443
1444template <class _InputIterator,
1445 class _Allocator,
1446 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
1447 class = enable_if_t<__is_allocator<_Allocator>::value>>
1448unordered_map(_InputIterator, _InputIterator, _Allocator)
1449 -> unordered_map<__iter_key_type<_InputIterator>,
1450 __iter_mapped_type<_InputIterator>,
1451 hash<__iter_key_type<_InputIterator>>,
1452 equal_to<__iter_key_type<_InputIterator>>,
1453 _Allocator>;
1454
1455template <class _InputIterator,
1456 class _Hash,
1457 class _Allocator,
1458 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
1459 class = enable_if_t<!__is_allocator<_Hash>::value>,
1460 class = enable_if_t<!is_integral<_Hash>::value>,
1461 class = enable_if_t<__is_allocator<_Allocator>::value>>
1462unordered_map(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
1463 -> unordered_map<__iter_key_type<_InputIterator>,
1464 __iter_mapped_type<_InputIterator>,
1465 _Hash,
1466 equal_to<__iter_key_type<_InputIterator>>,
1467 _Allocator>;
1468
1469# if _LIBCPP_STD_VER >= 23
1470
1471template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
1472unordered_map(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Allocator)
1473 -> unordered_map<__range_key_type<_Range>,
1474 __range_mapped_type<_Range>,
1475 hash<__range_key_type<_Range>>,
1476 equal_to<__range_key_type<_Range>>,
1477 _Allocator>;
1478
1479template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
1480unordered_map(from_range_t, _Range&&, _Allocator)
1481 -> unordered_map<__range_key_type<_Range>,
1482 __range_mapped_type<_Range>,
1483 hash<__range_key_type<_Range>>,
1484 equal_to<__range_key_type<_Range>>,
1485 _Allocator>;
1486
1487template <ranges::input_range _Range,
1488 class _Hash,
1489 class _Allocator,
1490 class = enable_if_t<!__is_allocator<_Hash>::value>,
1491 class = enable_if_t<!is_integral<_Hash>::value>,
1492 class = enable_if_t<__is_allocator<_Allocator>::value>>
1493unordered_map(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
1494 -> unordered_map<__range_key_type<_Range>,
1495 __range_mapped_type<_Range>,
1496 _Hash,
1497 equal_to<__range_key_type<_Range>>,
1498 _Allocator>;
1499
1500# endif
1501
1502template <class _Key, class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
1503unordered_map(initializer_list<pair<_Key, _Tp>>, typename allocator_traits<_Allocator>::size_type, _Allocator)
1504 -> unordered_map<remove_const_t<_Key>, _Tp, hash<remove_const_t<_Key>>, equal_to<remove_const_t<_Key>>, _Allocator>;
1505
1506template <class _Key, class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
1507unordered_map(initializer_list<pair<_Key, _Tp>>, _Allocator)
1508 -> unordered_map<remove_const_t<_Key>, _Tp, hash<remove_const_t<_Key>>, equal_to<remove_const_t<_Key>>, _Allocator>;
1509
1510template <class _Key,
1511 class _Tp,
1512 class _Hash,
1513 class _Allocator,
1514 class = enable_if_t<!__is_allocator<_Hash>::value>,
1515 class = enable_if_t<!is_integral<_Hash>::value>,
1516 class = enable_if_t<__is_allocator<_Allocator>::value>>
1517unordered_map(initializer_list<pair<_Key, _Tp>>, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
1518 -> unordered_map<remove_const_t<_Key>, _Tp, _Hash, equal_to<remove_const_t<_Key>>, _Allocator>;
1519# endif
1520
1521template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1522unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(size_type __n, const hasher& __hf, const key_equal& __eql)
1523 : __table_(__hf, __eql) {
1524 __table_.__rehash_unique(__n);
1525}
1526
1527template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1528unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1529 size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1530 : __table_(__hf, __eql, typename __table::allocator_type(__a)) {
1531 __table_.__rehash_unique(__n);
1532}
1533
1534template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1535inline unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(const allocator_type& __a)
1536 : __table_(typename __table::allocator_type(__a)) {}
1537
1538template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1539template <class _InputIterator>
1540unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(_InputIterator __first, _InputIterator __last) {
1541 insert(__first, __last);
1542}
1543
1544template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1545template <class _InputIterator>
1546unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1547 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql)
1548 : __table_(__hf, __eql) {
1549 __table_.__rehash_unique(__n);
1550 insert(__first, __last);
1551}
1552
1553template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1554template <class _InputIterator>
1555unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1556 _InputIterator __first,
1557 _InputIterator __last,
1558 size_type __n,
1559 const hasher& __hf,
1560 const key_equal& __eql,
1561 const allocator_type& __a)
1562 : __table_(__hf, __eql, typename __table::allocator_type(__a)) {
1563 __table_.__rehash_unique(__n);
1564 insert(__first, __last);
1565}
1566
1567template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1568unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(const unordered_map& __u) : __table_(__u.__table_) {
1569 __table_.__rehash_unique(__u.bucket_count());
1570 insert(__u.begin(), __u.end());
1571}
1572
1573template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1574unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(const unordered_map& __u, const allocator_type& __a)
1575 : __table_(__u.__table_, typename __table::allocator_type(__a)) {
1576 __table_.__rehash_unique(__u.bucket_count());
1577 insert(__u.begin(), __u.end());
1578}
1579
1580# ifndef _LIBCPP_CXX03_LANG
1581
1582template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1583inline unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(unordered_map&& __u)
1584 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
1585 : __table_(std::move(__u.__table_)) {}
1586
1587template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1588unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(unordered_map&& __u, const allocator_type& __a)
1589 : __table_(std::move(__u.__table_), typename __table::allocator_type(__a)) {
1590 if (__a != __u.get_allocator()) {
1591 iterator __i = __u.begin();
1592 while (__u.size() != 0)
1593 __table_.__insert_unique_from_orphaned_node(std::move(__u.__table_.remove((__i++).__i_)->__get_value()));
1594 }
1595}
1596
1597template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1598unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(initializer_list<value_type> __il) {
1599 insert(__il.begin(), __il.end());
1600}
1601
1602template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1603unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1604 initializer_list<value_type> __il, size_type __n, const hasher& __hf, const key_equal& __eql)
1605 : __table_(__hf, __eql) {
1606 __table_.__rehash_unique(__n);
1607 insert(__il.begin(), __il.end());
1608}
1609
1610template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1611unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1612 initializer_list<value_type> __il,
1613 size_type __n,
1614 const hasher& __hf,
1615 const key_equal& __eql,
1616 const allocator_type& __a)
1617 : __table_(__hf, __eql, typename __table::allocator_type(__a)) {
1618 __table_.__rehash_unique(__n);
1619 insert(__il.begin(), __il.end());
1620}
1621
1622template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1623inline unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
1624unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_map&& __u)
1625 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) {
1626 __table_ = std::move(__u.__table_);
1627 return *this;
1628}
1629
1630template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1631inline unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
1632unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(initializer_list<value_type> __il) {
1633 __table_.__assign_unique(__il.begin(), __il.end());
1634 return *this;
1635}
1636
1637# endif // _LIBCPP_CXX03_LANG
1638
1639template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1640template <class _InputIterator>
1641inline void unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) {
1642 for (; __first != __last; ++__first)
1643 __table_.__insert_unique(*__first);
1644}
1645
1646# ifndef _LIBCPP_CXX03_LANG
1647
1648template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1649_Tp& unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k) {
1650 return __table_
1651 .__emplace_unique_key_args(__k, piecewise_construct, std::forward_as_tuple(__k), std::forward_as_tuple())
1652 .first->second;
1653}
1654
1655template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1656_Tp& unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&& __k) {
1657 return __table_
1658 .__emplace_unique_key_args(
1659 __k, piecewise_construct, std::forward_as_tuple(std::move(__k)), std::forward_as_tuple())
1660 .first->second;
1661}
1662# else // _LIBCPP_CXX03_LANG
1663
1664template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1665typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1666unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(const key_type& __k) {
1667 __node_allocator& __na = __table_.__node_alloc();
1668 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1669 __node_traits::construct(__na, std::addressof(__h->__get_value().first), __k);
1670 __h.get_deleter().__first_constructed = true;
1671 __node_traits::construct(__na, std::addressof(__h->__get_value().second));
1672 __h.get_deleter().__second_constructed = true;
1673 return __h;
1674}
1675
1676template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1677_Tp& unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k) {
1678 iterator __i = find(__k);
1679 if (__i != end())
1680 return __i->second;
1681 __node_holder __h = __construct_node_with_key(__k);
1682 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1683 __h.release();
1684 return __r.first->second;
1685}
1686
1687# endif // _LIBCPP_CXX03_LANG
1688
1689template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1690_Tp& unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) {
1691 iterator __i = find(__k);
1692 if (__i == end())
1693 std::__throw_out_of_range(msg: "unordered_map::at: key not found");
1694 return __i->second;
1695}
1696
1697template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1698const _Tp& unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) const {
1699 const_iterator __i = find(__k);
1700 if (__i == end())
1701 std::__throw_out_of_range(msg: "unordered_map::at: key not found");
1702 return __i->second;
1703}
1704
1705template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1706inline _LIBCPP_HIDE_FROM_ABI void
1707swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1708 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
1709 __x.swap(__y);
1710}
1711
1712# if _LIBCPP_STD_VER >= 20
1713template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc, class _Predicate>
1714inline _LIBCPP_HIDE_FROM_ABI typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::size_type
1715erase_if(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __c, _Predicate __pred) {
1716 return std::__libcpp_erase_if_container(__c, __pred);
1717}
1718# endif
1719
1720template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1721_LIBCPP_HIDE_FROM_ABI bool operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1722 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) {
1723 if (__x.size() != __y.size())
1724 return false;
1725 typedef typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator const_iterator;
1726 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); __i != __ex; ++__i) {
1727 const_iterator __j = __y.find(__i->first);
1728 if (__j == __ey || !(*__i == *__j))
1729 return false;
1730 }
1731 return true;
1732}
1733
1734# if _LIBCPP_STD_VER <= 17
1735
1736template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1737inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1738 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) {
1739 return !(__x == __y);
1740}
1741
1742# endif
1743
1744template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1745struct __container_traits<unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc> > {
1746 // http://eel.is/c++draft/unord.req.except#2
1747 // For unordered associative containers, if an exception is thrown by any operation
1748 // other than the container's hash function from within an insert or emplace function
1749 // inserting a single element, the insertion has no effect.
1750 static _LIBCPP_CONSTEXPR const bool __emplacement_has_strong_exception_safety_guarantee =
1751 __is_nothrow_invocable_v<_Hash, const _Key&>;
1752
1753 static _LIBCPP_CONSTEXPR const bool __reservable = true;
1754};
1755
1756template <class _Key,
1757 class _Tp,
1758 class _Hash = hash<_Key>,
1759 class _Pred = equal_to<_Key>,
1760 class _Alloc = allocator<pair<const _Key, _Tp> > >
1761class unordered_multimap {
1762public:
1763 // types
1764 typedef _Key key_type;
1765 typedef _Tp mapped_type;
1766 typedef __type_identity_t<_Hash> hasher;
1767 typedef __type_identity_t<_Pred> key_equal;
1768 typedef __type_identity_t<_Alloc> allocator_type;
1769 typedef pair<const key_type, mapped_type> value_type;
1770 typedef value_type& reference;
1771 typedef const value_type& const_reference;
1772 static_assert(__check_valid_allocator<allocator_type>::value, "");
1773 static_assert(is_same<value_type, typename allocator_type::value_type>::value,
1774 "Allocator::value_type must be same type as value_type");
1775
1776private:
1777 typedef __hash_value_type<key_type, mapped_type> __value_type;
1778 typedef __unordered_map_hasher<key_type, value_type, hasher, key_equal> __hasher;
1779 typedef __unordered_map_equal<key_type, value_type, key_equal, hasher> __key_equal;
1780 typedef __rebind_alloc<allocator_traits<allocator_type>, __value_type> __allocator_type;
1781
1782 typedef __hash_table<__value_type, __hasher, __key_equal, __allocator_type> __table;
1783
1784 __table __table_;
1785
1786 typedef typename __table::_NodeTypes _NodeTypes;
1787 typedef typename __table::__node_traits __node_traits;
1788 typedef typename __table::__node_allocator __node_allocator;
1789 typedef typename __table::__node __node;
1790 typedef __hash_map_node_destructor<__node_allocator> _Dp;
1791 typedef unique_ptr<__node, _Dp> __node_holder;
1792 typedef allocator_traits<allocator_type> __alloc_traits;
1793 static_assert(is_same<typename __node_traits::size_type, typename __alloc_traits::size_type>::value,
1794 "Allocator uses different size_type for different types");
1795
1796public:
1797 typedef typename __alloc_traits::pointer pointer;
1798 typedef typename __alloc_traits::const_pointer const_pointer;
1799 typedef typename __table::size_type size_type;
1800 typedef typename __table::difference_type difference_type;
1801
1802 typedef __hash_map_iterator<typename __table::iterator> iterator;
1803 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
1804 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
1805 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
1806
1807# if _LIBCPP_STD_VER >= 17
1808 typedef __map_node_handle<__node, allocator_type> node_type;
1809# endif
1810
1811 template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2>
1812 friend class unordered_map;
1813 template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2>
1814 friend class unordered_multimap;
1815
1816 _LIBCPP_HIDE_FROM_ABI unordered_multimap() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) {}
1817 explicit _LIBCPP_HIDE_FROM_ABI
1818 unordered_multimap(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
1819 _LIBCPP_HIDE_FROM_ABI
1820 unordered_multimap(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a);
1821 template <class _InputIterator>
1822 _LIBCPP_HIDE_FROM_ABI unordered_multimap(_InputIterator __first, _InputIterator __last);
1823 template <class _InputIterator>
1824 _LIBCPP_HIDE_FROM_ABI unordered_multimap(
1825 _InputIterator __first,
1826 _InputIterator __last,
1827 size_type __n,
1828 const hasher& __hf = hasher(),
1829 const key_equal& __eql = key_equal());
1830 template <class _InputIterator>
1831 _LIBCPP_HIDE_FROM_ABI unordered_multimap(
1832 _InputIterator __first,
1833 _InputIterator __last,
1834 size_type __n,
1835 const hasher& __hf,
1836 const key_equal& __eql,
1837 const allocator_type& __a);
1838
1839# if _LIBCPP_STD_VER >= 23
1840 template <_ContainerCompatibleRange<value_type> _Range>
1841 _LIBCPP_HIDE_FROM_ABI unordered_multimap(
1842 from_range_t,
1843 _Range&& __range,
1844 size_type __n = /*implementation-defined*/ 0,
1845 const hasher& __hf = hasher(),
1846 const key_equal& __eql = key_equal(),
1847 const allocator_type& __a = allocator_type())
1848 : __table_(__hf, __eql, typename __table::allocator_type(__a)) {
1849 if (__n > 0) {
1850 __table_.__rehash_multi(__n);
1851 }
1852 insert_range(std::forward<_Range>(__range));
1853 }
1854# endif
1855
1856 _LIBCPP_HIDE_FROM_ABI explicit unordered_multimap(const allocator_type& __a);
1857 _LIBCPP_HIDE_FROM_ABI unordered_multimap(const unordered_multimap& __u);
1858 _LIBCPP_HIDE_FROM_ABI unordered_multimap(const unordered_multimap& __u, const allocator_type& __a);
1859# ifndef _LIBCPP_CXX03_LANG
1860 _LIBCPP_HIDE_FROM_ABI unordered_multimap(unordered_multimap&& __u)
1861 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
1862 _LIBCPP_HIDE_FROM_ABI unordered_multimap(unordered_multimap&& __u, const allocator_type& __a);
1863 _LIBCPP_HIDE_FROM_ABI unordered_multimap(initializer_list<value_type> __il);
1864 _LIBCPP_HIDE_FROM_ABI unordered_multimap(
1865 initializer_list<value_type> __il,
1866 size_type __n,
1867 const hasher& __hf = hasher(),
1868 const key_equal& __eql = key_equal());
1869 _LIBCPP_HIDE_FROM_ABI unordered_multimap(
1870 initializer_list<value_type> __il,
1871 size_type __n,
1872 const hasher& __hf,
1873 const key_equal& __eql,
1874 const allocator_type& __a);
1875# endif // _LIBCPP_CXX03_LANG
1876# if _LIBCPP_STD_VER >= 14
1877 _LIBCPP_HIDE_FROM_ABI unordered_multimap(size_type __n, const allocator_type& __a)
1878 : unordered_multimap(__n, hasher(), key_equal(), __a) {}
1879 _LIBCPP_HIDE_FROM_ABI unordered_multimap(size_type __n, const hasher& __hf, const allocator_type& __a)
1880 : unordered_multimap(__n, __hf, key_equal(), __a) {}
1881 template <class _InputIterator>
1882 _LIBCPP_HIDE_FROM_ABI
1883 unordered_multimap(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a)
1884 : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a) {}
1885 template <class _InputIterator>
1886 _LIBCPP_HIDE_FROM_ABI unordered_multimap(
1887 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const allocator_type& __a)
1888 : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a) {}
1889
1890# if _LIBCPP_STD_VER >= 23
1891 template <_ContainerCompatibleRange<value_type> _Range>
1892 _LIBCPP_HIDE_FROM_ABI unordered_multimap(from_range_t, _Range&& __range, size_type __n, const allocator_type& __a)
1893 : unordered_multimap(from_range, std::forward<_Range>(__range), __n, hasher(), key_equal(), __a) {}
1894
1895 template <_ContainerCompatibleRange<value_type> _Range>
1896 _LIBCPP_HIDE_FROM_ABI
1897 unordered_multimap(from_range_t, _Range&& __range, size_type __n, const hasher& __hf, const allocator_type& __a)
1898 : unordered_multimap(from_range, std::forward<_Range>(__range), __n, __hf, key_equal(), __a) {}
1899# endif
1900
1901 _LIBCPP_HIDE_FROM_ABI unordered_multimap(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)
1902 : unordered_multimap(__il, __n, hasher(), key_equal(), __a) {}
1903 _LIBCPP_HIDE_FROM_ABI
1904 unordered_multimap(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a)
1905 : unordered_multimap(__il, __n, __hf, key_equal(), __a) {}
1906# endif
1907 _LIBCPP_HIDE_FROM_ABI ~unordered_multimap() {
1908 static_assert(sizeof(std::__diagnose_unordered_container_requirements<_Key, _Hash, _Pred>(0)), "");
1909 }
1910
1911 _LIBCPP_HIDE_FROM_ABI unordered_multimap& operator=(const unordered_multimap& __u) {
1912# ifndef _LIBCPP_CXX03_LANG
1913 __table_ = __u.__table_;
1914# else
1915 if (this != std::addressof(__u)) {
1916 __table_.clear();
1917 __table_.hash_function() = __u.__table_.hash_function();
1918 __table_.key_eq() = __u.__table_.key_eq();
1919 __table_.max_load_factor() = __u.__table_.max_load_factor();
1920 __table_.__copy_assign_alloc(__u.__table_);
1921 insert(__u.begin(), __u.end());
1922 }
1923# endif
1924 return *this;
1925 }
1926# ifndef _LIBCPP_CXX03_LANG
1927 _LIBCPP_HIDE_FROM_ABI unordered_multimap& operator=(unordered_multimap&& __u)
1928 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
1929 _LIBCPP_HIDE_FROM_ABI unordered_multimap& operator=(initializer_list<value_type> __il);
1930# endif // _LIBCPP_CXX03_LANG
1931
1932 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT {
1933 return allocator_type(__table_.__node_alloc());
1934 }
1935
1936 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __table_.size() == 0; }
1937 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __table_.size(); }
1938 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __table_.max_size(); }
1939
1940 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __table_.begin(); }
1941 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __table_.end(); }
1942 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __table_.begin(); }
1943 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __table_.end(); }
1944 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return __table_.begin(); }
1945 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return __table_.end(); }
1946
1947 _LIBCPP_HIDE_FROM_ABI iterator insert(const value_type& __x) { return __table_.__insert_multi(__x); }
1948
1949 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __x) {
1950 return __table_.__insert_multi(__p.__i_, __x);
1951 }
1952
1953 template <class _InputIterator>
1954 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last);
1955
1956# if _LIBCPP_STD_VER >= 23
1957 template <_ContainerCompatibleRange<value_type> _Range>
1958 _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) {
1959 for (auto&& __element : __range) {
1960 __table_.__insert_multi(std::forward<decltype(__element)>(__element));
1961 }
1962 }
1963# endif
1964
1965# ifndef _LIBCPP_CXX03_LANG
1966 _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); }
1967 _LIBCPP_HIDE_FROM_ABI iterator insert(value_type&& __x) { return __table_.__insert_multi(std::move(__x)); }
1968
1969 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __x) {
1970 return __table_.__insert_multi(__p.__i_, std::move(__x));
1971 }
1972
1973 template <class _Pp, __enable_if_t<is_constructible<value_type, _Pp>::value, int> = 0>
1974 _LIBCPP_HIDE_FROM_ABI iterator insert(_Pp&& __x) {
1975 return __table_.__insert_multi(std::forward<_Pp>(__x));
1976 }
1977
1978 template <class _Pp, __enable_if_t<is_constructible<value_type, _Pp>::value, int> = 0>
1979 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, _Pp&& __x) {
1980 return __table_.__insert_multi(__p.__i_, std::forward<_Pp>(__x));
1981 }
1982
1983 template <class... _Args>
1984 _LIBCPP_HIDE_FROM_ABI iterator emplace(_Args&&... __args) {
1985 return __table_.__emplace_multi(std::forward<_Args>(__args)...);
1986 }
1987
1988 template <class... _Args>
1989 _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __p, _Args&&... __args) {
1990 return __table_.__emplace_hint_multi(__p.__i_, std::forward<_Args>(__args)...);
1991 }
1992# endif // _LIBCPP_CXX03_LANG
1993
1994 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __table_.erase(__p.__i_); }
1995 _LIBCPP_HIDE_FROM_ABI iterator erase(iterator __p) { return __table_.erase(__p.__i_); }
1996 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_multi(__k); }
1997 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last) {
1998 return __table_.erase(__first.__i_, __last.__i_);
1999 }
2000 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __table_.clear(); }
2001
2002# if _LIBCPP_STD_VER >= 17
2003 _LIBCPP_HIDE_FROM_ABI iterator insert(node_type&& __nh) {
2004 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
2005 "node_type with incompatible allocator passed to unordered_multimap::insert()");
2006 return __table_.template __node_handle_insert_multi<node_type>(std::move(__nh));
2007 }
2008 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, node_type&& __nh) {
2009 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
2010 "node_type with incompatible allocator passed to unordered_multimap::insert()");
2011 return __table_.template __node_handle_insert_multi<node_type>(__hint.__i_, std::move(__nh));
2012 }
2013 _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) {
2014 return __table_.template __node_handle_extract<node_type>(__key);
2015 }
2016 _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __it) {
2017 return __table_.template __node_handle_extract<node_type>(__it.__i_);
2018 }
2019
2020 template <class _H2, class _P2>
2021 _LIBCPP_HIDE_FROM_ABI void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>& __source) {
2022 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
2023 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
2024 return __table_.__node_handle_merge_multi(__source.__table_);
2025 }
2026 template <class _H2, class _P2>
2027 _LIBCPP_HIDE_FROM_ABI void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>&& __source) {
2028 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
2029 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
2030 return __table_.__node_handle_merge_multi(__source.__table_);
2031 }
2032 template <class _H2, class _P2>
2033 _LIBCPP_HIDE_FROM_ABI void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>& __source) {
2034 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
2035 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
2036 return __table_.__node_handle_merge_multi(__source.__table_);
2037 }
2038 template <class _H2, class _P2>
2039 _LIBCPP_HIDE_FROM_ABI void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>&& __source) {
2040 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
2041 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
2042 return __table_.__node_handle_merge_multi(__source.__table_);
2043 }
2044# endif
2045
2046 _LIBCPP_HIDE_FROM_ABI void swap(unordered_multimap& __u) _NOEXCEPT_(__is_nothrow_swappable_v<__table>) {
2047 __table_.swap(__u.__table_);
2048 }
2049
2050 _LIBCPP_HIDE_FROM_ABI hasher hash_function() const { return __table_.hash_function().hash_function(); }
2051 _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq().key_eq(); }
2052
2053 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); }
2054 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); }
2055# if _LIBCPP_STD_VER >= 20
2056 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
2057 _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) {
2058 return __table_.find(__k);
2059 }
2060 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
2061 _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const {
2062 return __table_.find(__k);
2063 }
2064# endif // _LIBCPP_STD_VER >= 20
2065
2066 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_multi(__k); }
2067# if _LIBCPP_STD_VER >= 20
2068 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
2069 _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const {
2070 return __table_.__count_multi(__k);
2071 }
2072# endif // _LIBCPP_STD_VER >= 20
2073
2074# if _LIBCPP_STD_VER >= 20
2075 _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); }
2076
2077 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
2078 _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const {
2079 return find(__k) != end();
2080 }
2081# endif // _LIBCPP_STD_VER >= 20
2082
2083 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {
2084 return __table_.__equal_range_multi(__k);
2085 }
2086 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
2087 return __table_.__equal_range_multi(__k);
2088 }
2089# if _LIBCPP_STD_VER >= 20
2090 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
2091 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) {
2092 return __table_.__equal_range_multi(__k);
2093 }
2094 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
2095 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const {
2096 return __table_.__equal_range_multi(__k);
2097 }
2098# endif // _LIBCPP_STD_VER >= 20
2099
2100 _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const _NOEXCEPT { return __table_.bucket_count(); }
2101 _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const _NOEXCEPT { return __table_.max_bucket_count(); }
2102
2103 _LIBCPP_HIDE_FROM_ABI size_type bucket_size(size_type __n) const { return __table_.bucket_size(__n); }
2104 _LIBCPP_HIDE_FROM_ABI size_type bucket(const key_type& __k) const { return __table_.bucket(__k); }
2105
2106 _LIBCPP_HIDE_FROM_ABI local_iterator begin(size_type __n) { return __table_.begin(__n); }
2107 _LIBCPP_HIDE_FROM_ABI local_iterator end(size_type __n) { return __table_.end(__n); }
2108 _LIBCPP_HIDE_FROM_ABI const_local_iterator begin(size_type __n) const { return __table_.cbegin(__n); }
2109 _LIBCPP_HIDE_FROM_ABI const_local_iterator end(size_type __n) const { return __table_.cend(__n); }
2110 _LIBCPP_HIDE_FROM_ABI const_local_iterator cbegin(size_type __n) const { return __table_.cbegin(__n); }
2111 _LIBCPP_HIDE_FROM_ABI const_local_iterator cend(size_type __n) const { return __table_.cend(__n); }
2112
2113 _LIBCPP_HIDE_FROM_ABI float load_factor() const _NOEXCEPT { return __table_.load_factor(); }
2114 _LIBCPP_HIDE_FROM_ABI float max_load_factor() const _NOEXCEPT { return __table_.max_load_factor(); }
2115 _LIBCPP_HIDE_FROM_ABI void max_load_factor(float __mlf) { __table_.max_load_factor(__mlf); }
2116 _LIBCPP_HIDE_FROM_ABI void rehash(size_type __n) { __table_.__rehash_multi(__n); }
2117 _LIBCPP_HIDE_FROM_ABI void reserve(size_type __n) { __table_.__reserve_multi(__n); }
2118};
2119
2120# if _LIBCPP_STD_VER >= 17
2121template <class _InputIterator,
2122 class _Hash = hash<__iter_key_type<_InputIterator>>,
2123 class _Pred = equal_to<__iter_key_type<_InputIterator>>,
2124 class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>,
2125 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
2126 class = enable_if_t<!__is_allocator<_Hash>::value>,
2127 class = enable_if_t<!is_integral<_Hash>::value>,
2128 class = enable_if_t<!__is_allocator<_Pred>::value>,
2129 class = enable_if_t<__is_allocator<_Allocator>::value>>
2130unordered_multimap(_InputIterator,
2131 _InputIterator,
2132 typename allocator_traits<_Allocator>::size_type = 0,
2133 _Hash = _Hash(),
2134 _Pred = _Pred(),
2135 _Allocator = _Allocator())
2136 -> unordered_multimap<__iter_key_type<_InputIterator>,
2137 __iter_mapped_type<_InputIterator>,
2138 _Hash,
2139 _Pred,
2140 _Allocator>;
2141
2142# if _LIBCPP_STD_VER >= 23
2143template <ranges::input_range _Range,
2144 class _Hash = hash<__range_key_type<_Range>>,
2145 class _Pred = equal_to<__range_key_type<_Range>>,
2146 class _Allocator = allocator<__range_to_alloc_type<_Range>>,
2147 class = enable_if_t<!__is_allocator<_Hash>::value>,
2148 class = enable_if_t<!is_integral<_Hash>::value>,
2149 class = enable_if_t<!__is_allocator<_Pred>::value>,
2150 class = enable_if_t<__is_allocator<_Allocator>::value>>
2151unordered_multimap(from_range_t,
2152 _Range&&,
2153 typename allocator_traits<_Allocator>::size_type = 0,
2154 _Hash = _Hash(),
2155 _Pred = _Pred(),
2156 _Allocator = _Allocator())
2157 -> unordered_multimap<__range_key_type<_Range>, __range_mapped_type<_Range>, _Hash, _Pred, _Allocator>;
2158# endif
2159
2160template <class _Key,
2161 class _Tp,
2162 class _Hash = hash<remove_const_t<_Key>>,
2163 class _Pred = equal_to<remove_const_t<_Key>>,
2164 class _Allocator = allocator<pair<const _Key, _Tp>>,
2165 class = enable_if_t<!__is_allocator<_Hash>::value>,
2166 class = enable_if_t<!is_integral<_Hash>::value>,
2167 class = enable_if_t<!__is_allocator<_Pred>::value>,
2168 class = enable_if_t<__is_allocator<_Allocator>::value>>
2169unordered_multimap(
2170 initializer_list<pair<_Key, _Tp>>,
2171 typename allocator_traits<_Allocator>::size_type = 0,
2172 _Hash = _Hash(),
2173 _Pred = _Pred(),
2174 _Allocator = _Allocator()) -> unordered_multimap<remove_const_t<_Key>, _Tp, _Hash, _Pred, _Allocator>;
2175
2176template <class _InputIterator,
2177 class _Allocator,
2178 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
2179 class = enable_if_t<__is_allocator<_Allocator>::value>>
2180unordered_multimap(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Allocator)
2181 -> unordered_multimap<__iter_key_type<_InputIterator>,
2182 __iter_mapped_type<_InputIterator>,
2183 hash<__iter_key_type<_InputIterator>>,
2184 equal_to<__iter_key_type<_InputIterator>>,
2185 _Allocator>;
2186
2187template <class _InputIterator,
2188 class _Allocator,
2189 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
2190 class = enable_if_t<__is_allocator<_Allocator>::value>>
2191unordered_multimap(_InputIterator, _InputIterator, _Allocator)
2192 -> unordered_multimap<__iter_key_type<_InputIterator>,
2193 __iter_mapped_type<_InputIterator>,
2194 hash<__iter_key_type<_InputIterator>>,
2195 equal_to<__iter_key_type<_InputIterator>>,
2196 _Allocator>;
2197
2198template <class _InputIterator,
2199 class _Hash,
2200 class _Allocator,
2201 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
2202 class = enable_if_t<!__is_allocator<_Hash>::value>,
2203 class = enable_if_t<!is_integral<_Hash>::value>,
2204 class = enable_if_t<__is_allocator<_Allocator>::value>>
2205unordered_multimap(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
2206 -> unordered_multimap<__iter_key_type<_InputIterator>,
2207 __iter_mapped_type<_InputIterator>,
2208 _Hash,
2209 equal_to<__iter_key_type<_InputIterator>>,
2210 _Allocator>;
2211
2212# if _LIBCPP_STD_VER >= 23
2213
2214template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
2215unordered_multimap(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Allocator)
2216 -> unordered_multimap<__range_key_type<_Range>,
2217 __range_mapped_type<_Range>,
2218 hash<__range_key_type<_Range>>,
2219 equal_to<__range_key_type<_Range>>,
2220 _Allocator>;
2221
2222template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
2223unordered_multimap(from_range_t, _Range&&, _Allocator)
2224 -> unordered_multimap<__range_key_type<_Range>,
2225 __range_mapped_type<_Range>,
2226 hash<__range_key_type<_Range>>,
2227 equal_to<__range_key_type<_Range>>,
2228 _Allocator>;
2229
2230template <ranges::input_range _Range,
2231 class _Hash,
2232 class _Allocator,
2233 class = enable_if_t<!__is_allocator<_Hash>::value>,
2234 class = enable_if_t<!is_integral<_Hash>::value>,
2235 class = enable_if_t<__is_allocator<_Allocator>::value>>
2236unordered_multimap(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
2237 -> unordered_multimap<__range_key_type<_Range>,
2238 __range_mapped_type<_Range>,
2239 _Hash,
2240 equal_to<__range_key_type<_Range>>,
2241 _Allocator>;
2242
2243# endif
2244
2245template <class _Key, class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
2246unordered_multimap(initializer_list<pair<_Key, _Tp>>, typename allocator_traits<_Allocator>::size_type, _Allocator)
2247 -> unordered_multimap<remove_const_t<_Key>,
2248 _Tp,
2249 hash<remove_const_t<_Key>>,
2250 equal_to<remove_const_t<_Key>>,
2251 _Allocator>;
2252
2253template <class _Key, class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
2254unordered_multimap(initializer_list<pair<_Key, _Tp>>, _Allocator)
2255 -> unordered_multimap<remove_const_t<_Key>,
2256 _Tp,
2257 hash<remove_const_t<_Key>>,
2258 equal_to<remove_const_t<_Key>>,
2259 _Allocator>;
2260
2261template <class _Key,
2262 class _Tp,
2263 class _Hash,
2264 class _Allocator,
2265 class = enable_if_t<!__is_allocator<_Hash>::value>,
2266 class = enable_if_t<!is_integral<_Hash>::value>,
2267 class = enable_if_t<__is_allocator<_Allocator>::value>>
2268unordered_multimap(
2269 initializer_list<pair<_Key, _Tp>>, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
2270 -> unordered_multimap<remove_const_t<_Key>, _Tp, _Hash, equal_to<remove_const_t<_Key>>, _Allocator>;
2271# endif
2272
2273template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2274unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2275 size_type __n, const hasher& __hf, const key_equal& __eql)
2276 : __table_(__hf, __eql) {
2277 __table_.__rehash_multi(__n);
2278}
2279
2280template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2281unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2282 size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
2283 : __table_(__hf, __eql, typename __table::allocator_type(__a)) {
2284 __table_.__rehash_multi(__n);
2285}
2286
2287template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2288template <class _InputIterator>
2289unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(_InputIterator __first, _InputIterator __last) {
2290 insert(__first, __last);
2291}
2292
2293template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2294template <class _InputIterator>
2295unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2296 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql)
2297 : __table_(__hf, __eql) {
2298 __table_.__rehash_multi(__n);
2299 insert(__first, __last);
2300}
2301
2302template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2303template <class _InputIterator>
2304unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2305 _InputIterator __first,
2306 _InputIterator __last,
2307 size_type __n,
2308 const hasher& __hf,
2309 const key_equal& __eql,
2310 const allocator_type& __a)
2311 : __table_(__hf, __eql, typename __table::allocator_type(__a)) {
2312 __table_.__rehash_multi(__n);
2313 insert(__first, __last);
2314}
2315
2316template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2317inline unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(const allocator_type& __a)
2318 : __table_(typename __table::allocator_type(__a)) {}
2319
2320template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2321unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(const unordered_multimap& __u)
2322 : __table_(__u.__table_) {
2323 __table_.__rehash_multi(__u.bucket_count());
2324 insert(__u.begin(), __u.end());
2325}
2326
2327template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2328unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2329 const unordered_multimap& __u, const allocator_type& __a)
2330 : __table_(__u.__table_, typename __table::allocator_type(__a)) {
2331 __table_.__rehash_multi(__u.bucket_count());
2332 insert(__u.begin(), __u.end());
2333}
2334
2335# ifndef _LIBCPP_CXX03_LANG
2336
2337template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2338inline unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(unordered_multimap&& __u)
2339 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
2340 : __table_(std::move(__u.__table_)) {}
2341
2342template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2343unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2344 unordered_multimap&& __u, const allocator_type& __a)
2345 : __table_(std::move(__u.__table_), typename __table::allocator_type(__a)) {
2346 if (__a != __u.get_allocator()) {
2347 iterator __i = __u.begin();
2348 while (__u.size() != 0)
2349 __table_.__insert_multi_from_orphaned_node(std::move(__u.__table_.remove((__i++).__i_)->__get_value()));
2350 }
2351}
2352
2353template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2354unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(initializer_list<value_type> __il) {
2355 insert(__il.begin(), __il.end());
2356}
2357
2358template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2359unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2360 initializer_list<value_type> __il, size_type __n, const hasher& __hf, const key_equal& __eql)
2361 : __table_(__hf, __eql) {
2362 __table_.__rehash_multi(__n);
2363 insert(__il.begin(), __il.end());
2364}
2365
2366template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2367unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2368 initializer_list<value_type> __il,
2369 size_type __n,
2370 const hasher& __hf,
2371 const key_equal& __eql,
2372 const allocator_type& __a)
2373 : __table_(__hf, __eql, typename __table::allocator_type(__a)) {
2374 __table_.__rehash_multi(__n);
2375 insert(__il.begin(), __il.end());
2376}
2377
2378template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2379inline unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
2380unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_multimap&& __u)
2381 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) {
2382 __table_ = std::move(__u.__table_);
2383 return *this;
2384}
2385
2386template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2387inline unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
2388unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(initializer_list<value_type> __il) {
2389 __table_.__assign_multi(__il.begin(), __il.end());
2390 return *this;
2391}
2392
2393# endif // _LIBCPP_CXX03_LANG
2394
2395template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2396template <class _InputIterator>
2397inline void unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) {
2398 for (; __first != __last; ++__first)
2399 __table_.__insert_multi(*__first);
2400}
2401
2402template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2403inline _LIBCPP_HIDE_FROM_ABI void
2404swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2405 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
2406 __x.swap(__y);
2407}
2408
2409# if _LIBCPP_STD_VER >= 20
2410template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc, class _Predicate>
2411inline _LIBCPP_HIDE_FROM_ABI typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::size_type
2412erase_if(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __c, _Predicate __pred) {
2413 return std::__libcpp_erase_if_container(__c, __pred);
2414}
2415# endif
2416
2417template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2418_LIBCPP_HIDE_FROM_ABI bool operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2419 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) {
2420 if (__x.size() != __y.size())
2421 return false;
2422 typedef typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator const_iterator;
2423 typedef pair<const_iterator, const_iterator> _EqRng;
2424 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) {
2425 _EqRng __xeq = __x.equal_range(__i->first);
2426 _EqRng __yeq = __y.equal_range(__i->first);
2427 if (std::distance(__xeq.first, __xeq.second) != std::distance(__yeq.first, __yeq.second) ||
2428 !std::is_permutation(__xeq.first, __xeq.second, __yeq.first))
2429 return false;
2430 __i = __xeq.second;
2431 }
2432 return true;
2433}
2434
2435# if _LIBCPP_STD_VER <= 17
2436
2437template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2438inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2439 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) {
2440 return !(__x == __y);
2441}
2442
2443# endif
2444
2445template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2446struct __container_traits<unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc> > {
2447 // http://eel.is/c++draft/unord.req.except#2
2448 // For unordered associative containers, if an exception is thrown by any operation
2449 // other than the container's hash function from within an insert or emplace function
2450 // inserting a single element, the insertion has no effect.
2451 static _LIBCPP_CONSTEXPR const bool __emplacement_has_strong_exception_safety_guarantee =
2452 __is_nothrow_invocable_v<_Hash, const _Key&>;
2453
2454 static _LIBCPP_CONSTEXPR const bool __reservable = true;
2455};
2456
2457_LIBCPP_END_NAMESPACE_STD
2458
2459# if _LIBCPP_STD_VER >= 17
2460_LIBCPP_BEGIN_NAMESPACE_STD
2461namespace pmr {
2462template <class _KeyT, class _ValueT, class _HashT = std::hash<_KeyT>, class _PredT = std::equal_to<_KeyT>>
2463using unordered_map _LIBCPP_AVAILABILITY_PMR =
2464 std::unordered_map<_KeyT, _ValueT, _HashT, _PredT, polymorphic_allocator<std::pair<const _KeyT, _ValueT>>>;
2465
2466template <class _KeyT, class _ValueT, class _HashT = std::hash<_KeyT>, class _PredT = std::equal_to<_KeyT>>
2467using unordered_multimap _LIBCPP_AVAILABILITY_PMR =
2468 std::unordered_multimap<_KeyT, _ValueT, _HashT, _PredT, polymorphic_allocator<std::pair<const _KeyT, _ValueT>>>;
2469} // namespace pmr
2470_LIBCPP_END_NAMESPACE_STD
2471# endif
2472
2473_LIBCPP_POP_MACROS
2474
2475# if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
2476# include <algorithm>
2477# include <bit>
2478# include <cmath>
2479# include <concepts>
2480# include <cstdlib>
2481# include <iterator>
2482# include <type_traits>
2483# endif
2484#endif // __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS)
2485
2486#endif // _LIBCPP_UNORDERED_MAP
2487