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#include <__algorithm/is_permutation.h>
587#include <__assert>
588#include <__config>
589#include <__functional/is_transparent.h>
590#include <__functional/operations.h>
591#include <__hash_table>
592#include <__iterator/distance.h>
593#include <__iterator/erase_if_container.h>
594#include <__iterator/iterator_traits.h>
595#include <__iterator/ranges_iterator_traits.h>
596#include <__memory/addressof.h>
597#include <__memory/allocator.h>
598#include <__memory_resource/polymorphic_allocator.h>
599#include <__node_handle>
600#include <__ranges/concepts.h>
601#include <__ranges/container_compatible_range.h>
602#include <__ranges/from_range.h>
603#include <__type_traits/is_allocator.h>
604#include <__type_traits/type_identity.h>
605#include <__utility/forward.h>
606#include <stdexcept>
607#include <tuple>
608#include <version>
609
610// standard-mandated includes
611
612// [iterator.range]
613#include <__iterator/access.h>
614#include <__iterator/data.h>
615#include <__iterator/empty.h>
616#include <__iterator/reverse_access.h>
617#include <__iterator/size.h>
618
619// [unord.map.syn]
620#include <compare>
621#include <initializer_list>
622
623#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
624# pragma GCC system_header
625#endif
626
627_LIBCPP_PUSH_MACROS
628#include <__undef_macros>
629
630_LIBCPP_BEGIN_NAMESPACE_STD
631
632template <class _Key,
633 class _Cp,
634 class _Hash,
635 class _Pred,
636 bool = is_empty<_Hash>::value && !__libcpp_is_final<_Hash>::value>
637class __unordered_map_hasher : private _Hash {
638public:
639 _LIBCPP_HIDE_FROM_ABI __unordered_map_hasher() _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value) : _Hash() {}
640 _LIBCPP_HIDE_FROM_ABI __unordered_map_hasher(const _Hash& __h) _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value)
641 : _Hash(__h) {}
642 _LIBCPP_HIDE_FROM_ABI const _Hash& hash_function() const _NOEXCEPT { return *this; }
643 _LIBCPP_HIDE_FROM_ABI size_t operator()(const _Cp& __x) const {
644 return static_cast<const _Hash&>(*this)(__x.__get_value().first);
645 }
646 _LIBCPP_HIDE_FROM_ABI size_t operator()(const _Key& __x) const { return static_cast<const _Hash&>(*this)(__x); }
647#if _LIBCPP_STD_VER >= 20
648 template <typename _K2>
649 _LIBCPP_HIDE_FROM_ABI size_t operator()(const _K2& __x) const {
650 return static_cast<const _Hash&>(*this)(__x);
651 }
652#endif
653 _LIBCPP_HIDE_FROM_ABI void swap(__unordered_map_hasher& __y) _NOEXCEPT_(__is_nothrow_swappable_v<_Hash>) {
654 using std::swap;
655 swap(static_cast<_Hash&>(*this), static_cast<_Hash&>(__y));
656 }
657};
658
659template <class _Key, class _Cp, class _Hash, class _Pred>
660class __unordered_map_hasher<_Key, _Cp, _Hash, _Pred, false> {
661 _Hash __hash_;
662
663public:
664 _LIBCPP_HIDE_FROM_ABI __unordered_map_hasher() _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value)
665 : __hash_() {}
666 _LIBCPP_HIDE_FROM_ABI __unordered_map_hasher(const _Hash& __h) _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value)
667 : __hash_(__h) {}
668 _LIBCPP_HIDE_FROM_ABI const _Hash& hash_function() const _NOEXCEPT { return __hash_; }
669 _LIBCPP_HIDE_FROM_ABI size_t operator()(const _Cp& __x) const { return __hash_(__x.__get_value().first); }
670 _LIBCPP_HIDE_FROM_ABI size_t operator()(const _Key& __x) const { return __hash_(__x); }
671#if _LIBCPP_STD_VER >= 20
672 template <typename _K2>
673 _LIBCPP_HIDE_FROM_ABI size_t operator()(const _K2& __x) const {
674 return __hash_(__x);
675 }
676#endif
677 _LIBCPP_HIDE_FROM_ABI void swap(__unordered_map_hasher& __y) _NOEXCEPT_(__is_nothrow_swappable_v<_Hash>) {
678 using std::swap;
679 swap(__hash_, __y.__hash_);
680 }
681};
682
683template <class _Key, class _Cp, class _Hash, class _Pred, bool __b>
684inline _LIBCPP_HIDE_FROM_ABI void
685swap(__unordered_map_hasher<_Key, _Cp, _Hash, _Pred, __b>& __x,
686 __unordered_map_hasher<_Key, _Cp, _Hash, _Pred, __b>& __y) _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
687 __x.swap(__y);
688}
689
690template <class _Key,
691 class _Cp,
692 class _Pred,
693 class _Hash,
694 bool = is_empty<_Pred>::value && !__libcpp_is_final<_Pred>::value>
695class __unordered_map_equal : private _Pred {
696public:
697 _LIBCPP_HIDE_FROM_ABI __unordered_map_equal() _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value) : _Pred() {}
698 _LIBCPP_HIDE_FROM_ABI __unordered_map_equal(const _Pred& __p) _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value)
699 : _Pred(__p) {}
700 _LIBCPP_HIDE_FROM_ABI const _Pred& key_eq() const _NOEXCEPT { return *this; }
701 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Cp& __x, const _Cp& __y) const {
702 return static_cast<const _Pred&>(*this)(__x.__get_value().first, __y.__get_value().first);
703 }
704 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Cp& __x, const _Key& __y) const {
705 return static_cast<const _Pred&>(*this)(__x.__get_value().first, __y);
706 }
707 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Key& __x, const _Cp& __y) const {
708 return static_cast<const _Pred&>(*this)(__x, __y.__get_value().first);
709 }
710#if _LIBCPP_STD_VER >= 20
711 template <typename _K2>
712 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Cp& __x, const _K2& __y) const {
713 return static_cast<const _Pred&>(*this)(__x.__get_value().first, __y);
714 }
715 template <typename _K2>
716 _LIBCPP_HIDE_FROM_ABI bool operator()(const _K2& __x, const _Cp& __y) const {
717 return static_cast<const _Pred&>(*this)(__x, __y.__get_value().first);
718 }
719 template <typename _K2>
720 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Key& __x, const _K2& __y) const {
721 return static_cast<const _Pred&>(*this)(__x, __y);
722 }
723 template <typename _K2>
724 _LIBCPP_HIDE_FROM_ABI bool operator()(const _K2& __x, const _Key& __y) const {
725 return static_cast<const _Pred&>(*this)(__x, __y);
726 }
727#endif
728 _LIBCPP_HIDE_FROM_ABI void swap(__unordered_map_equal& __y) _NOEXCEPT_(__is_nothrow_swappable_v<_Pred>) {
729 using std::swap;
730 swap(static_cast<_Pred&>(*this), static_cast<_Pred&>(__y));
731 }
732};
733
734template <class _Key, class _Cp, class _Pred, class _Hash>
735class __unordered_map_equal<_Key, _Cp, _Pred, _Hash, false> {
736 _Pred __pred_;
737
738public:
739 _LIBCPP_HIDE_FROM_ABI __unordered_map_equal() _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value)
740 : __pred_() {}
741 _LIBCPP_HIDE_FROM_ABI __unordered_map_equal(const _Pred& __p) _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value)
742 : __pred_(__p) {}
743 _LIBCPP_HIDE_FROM_ABI const _Pred& key_eq() const _NOEXCEPT { return __pred_; }
744 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Cp& __x, const _Cp& __y) const {
745 return __pred_(__x.__get_value().first, __y.__get_value().first);
746 }
747 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Cp& __x, const _Key& __y) const {
748 return __pred_(__x.__get_value().first, __y);
749 }
750 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Key& __x, const _Cp& __y) const {
751 return __pred_(__x, __y.__get_value().first);
752 }
753#if _LIBCPP_STD_VER >= 20
754 template <typename _K2>
755 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Cp& __x, const _K2& __y) const {
756 return __pred_(__x.__get_value().first, __y);
757 }
758 template <typename _K2>
759 _LIBCPP_HIDE_FROM_ABI bool operator()(const _K2& __x, const _Cp& __y) const {
760 return __pred_(__x, __y.__get_value().first);
761 }
762 template <typename _K2>
763 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Key& __x, const _K2& __y) const {
764 return __pred_(__x, __y);
765 }
766 template <typename _K2>
767 _LIBCPP_HIDE_FROM_ABI bool operator()(const _K2& __x, const _Key& __y) const {
768 return __pred_(__x, __y);
769 }
770#endif
771 _LIBCPP_HIDE_FROM_ABI void swap(__unordered_map_equal& __y) _NOEXCEPT_(__is_nothrow_swappable_v<_Pred>) {
772 using std::swap;
773 swap(__pred_, __y.__pred_);
774 }
775};
776
777template <class _Key, class _Cp, class _Pred, class _Hash, bool __b>
778inline _LIBCPP_HIDE_FROM_ABI void
779swap(__unordered_map_equal<_Key, _Cp, _Pred, _Hash, __b>& __x, __unordered_map_equal<_Key, _Cp, _Pred, _Hash, __b>& __y)
780 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
781 __x.swap(__y);
782}
783
784template <class _Alloc>
785class __hash_map_node_destructor {
786 typedef _Alloc allocator_type;
787 typedef allocator_traits<allocator_type> __alloc_traits;
788
789public:
790 typedef typename __alloc_traits::pointer pointer;
791
792private:
793 allocator_type& __na_;
794
795public:
796 bool __first_constructed;
797 bool __second_constructed;
798
799 __hash_map_node_destructor& operator=(const __hash_map_node_destructor&) = delete;
800
801 _LIBCPP_HIDE_FROM_ABI explicit __hash_map_node_destructor(allocator_type& __na) _NOEXCEPT
802 : __na_(__na),
803 __first_constructed(false),
804 __second_constructed(false) {}
805
806#ifndef _LIBCPP_CXX03_LANG
807 _LIBCPP_HIDE_FROM_ABI __hash_map_node_destructor(__hash_node_destructor<allocator_type>&& __x) _NOEXCEPT
808 : __na_(__x.__na_),
809 __first_constructed(__x.__value_constructed),
810 __second_constructed(__x.__value_constructed) {
811 __x.__value_constructed = false;
812 }
813#else // _LIBCPP_CXX03_LANG
814 _LIBCPP_HIDE_FROM_ABI __hash_map_node_destructor(const __hash_node_destructor<allocator_type>& __x)
815 : __na_(__x.__na_), __first_constructed(__x.__value_constructed), __second_constructed(__x.__value_constructed) {
816 const_cast<bool&>(__x.__value_constructed) = false;
817 }
818#endif // _LIBCPP_CXX03_LANG
819
820 _LIBCPP_HIDE_FROM_ABI void operator()(pointer __p) _NOEXCEPT {
821 if (__second_constructed)
822 __alloc_traits::destroy(__na_, std::addressof(__p->__get_value().__get_value().second));
823 if (__first_constructed)
824 __alloc_traits::destroy(__na_, std::addressof(__p->__get_value().__get_value().first));
825 if (__p)
826 __alloc_traits::deallocate(__na_, __p, 1);
827 }
828};
829
830#ifndef _LIBCPP_CXX03_LANG
831template <class _Key, class _Tp>
832struct _LIBCPP_STANDALONE_DEBUG __hash_value_type {
833 typedef _Key key_type;
834 typedef _Tp mapped_type;
835 typedef pair<const key_type, mapped_type> value_type;
836 typedef pair<key_type&, mapped_type&> __nc_ref_pair_type;
837 typedef pair<key_type&&, mapped_type&&> __nc_rref_pair_type;
838
839private:
840 value_type __cc_;
841
842public:
843 _LIBCPP_HIDE_FROM_ABI value_type& __get_value() {
844# if _LIBCPP_STD_VER >= 17
845 return *std::launder(std::addressof(__cc_));
846# else
847 return __cc_;
848# endif
849 }
850
851 _LIBCPP_HIDE_FROM_ABI const value_type& __get_value() const {
852# if _LIBCPP_STD_VER >= 17
853 return *std::launder(std::addressof(__cc_));
854# else
855 return __cc_;
856# endif
857 }
858
859 _LIBCPP_HIDE_FROM_ABI __nc_ref_pair_type __ref() {
860 value_type& __v = __get_value();
861 return __nc_ref_pair_type(const_cast<key_type&>(__v.first), __v.second);
862 }
863
864 _LIBCPP_HIDE_FROM_ABI __nc_rref_pair_type __move() {
865 value_type& __v = __get_value();
866 return __nc_rref_pair_type(std::move(const_cast<key_type&>(__v.first)), std::move(__v.second));
867 }
868
869 _LIBCPP_HIDE_FROM_ABI __hash_value_type& operator=(const __hash_value_type& __v) {
870 __ref() = __v.__get_value();
871 return *this;
872 }
873
874 _LIBCPP_HIDE_FROM_ABI __hash_value_type& operator=(__hash_value_type&& __v) {
875 __ref() = __v.__move();
876 return *this;
877 }
878
879 template <class _ValueTp, __enable_if_t<__is_same_uncvref<_ValueTp, value_type>::value, int> = 0>
880 _LIBCPP_HIDE_FROM_ABI __hash_value_type& operator=(_ValueTp&& __v) {
881 __ref() = std::forward<_ValueTp>(__v);
882 return *this;
883 }
884
885 __hash_value_type(const __hash_value_type& __v) = delete;
886 __hash_value_type(__hash_value_type&& __v) = delete;
887 template <class... _Args>
888 explicit __hash_value_type(_Args&&... __args) = delete;
889
890 ~__hash_value_type() = delete;
891};
892
893#else
894
895template <class _Key, class _Tp>
896struct __hash_value_type {
897 typedef _Key key_type;
898 typedef _Tp mapped_type;
899 typedef pair<const key_type, mapped_type> value_type;
900
901private:
902 value_type __cc_;
903
904public:
905 _LIBCPP_HIDE_FROM_ABI value_type& __get_value() { return __cc_; }
906 _LIBCPP_HIDE_FROM_ABI const value_type& __get_value() const { return __cc_; }
907
908 ~__hash_value_type() = delete;
909};
910
911#endif
912
913template <class _HashIterator>
914class _LIBCPP_TEMPLATE_VIS __hash_map_iterator {
915 _HashIterator __i_;
916
917 typedef __hash_node_types_from_iterator<_HashIterator> _NodeTypes;
918
919public:
920 typedef forward_iterator_tag iterator_category;
921 typedef typename _NodeTypes::__map_value_type value_type;
922 typedef typename _NodeTypes::difference_type difference_type;
923 typedef value_type& reference;
924 typedef typename _NodeTypes::__map_value_type_pointer pointer;
925
926 _LIBCPP_HIDE_FROM_ABI __hash_map_iterator() _NOEXCEPT {}
927
928 _LIBCPP_HIDE_FROM_ABI __hash_map_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
929
930 _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __i_->__get_value(); }
931 _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return pointer_traits<pointer>::pointer_to(__i_->__get_value()); }
932
933 _LIBCPP_HIDE_FROM_ABI __hash_map_iterator& operator++() {
934 ++__i_;
935 return *this;
936 }
937 _LIBCPP_HIDE_FROM_ABI __hash_map_iterator operator++(int) {
938 __hash_map_iterator __t(*this);
939 ++(*this);
940 return __t;
941 }
942
943 friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y) {
944 return __x.__i_ == __y.__i_;
945 }
946#if _LIBCPP_STD_VER <= 17
947 friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y) {
948 return __x.__i_ != __y.__i_;
949 }
950#endif
951
952 template <class, class, class, class, class>
953 friend class _LIBCPP_TEMPLATE_VIS unordered_map;
954 template <class, class, class, class, class>
955 friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
956 template <class>
957 friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator;
958 template <class>
959 friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator;
960 template <class>
961 friend class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator;
962};
963
964template <class _HashIterator>
965class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator {
966 _HashIterator __i_;
967
968 typedef __hash_node_types_from_iterator<_HashIterator> _NodeTypes;
969
970public:
971 typedef forward_iterator_tag iterator_category;
972 typedef typename _NodeTypes::__map_value_type value_type;
973 typedef typename _NodeTypes::difference_type difference_type;
974 typedef const value_type& reference;
975 typedef typename _NodeTypes::__const_map_value_type_pointer pointer;
976
977 _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator() _NOEXCEPT {}
978
979 _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
980 _LIBCPP_HIDE_FROM_ABI
981 __hash_map_const_iterator(__hash_map_iterator<typename _HashIterator::__non_const_iterator> __i) _NOEXCEPT
982 : __i_(__i.__i_) {}
983
984 _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __i_->__get_value(); }
985 _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return pointer_traits<pointer>::pointer_to(__i_->__get_value()); }
986
987 _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator& operator++() {
988 ++__i_;
989 return *this;
990 }
991 _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator operator++(int) {
992 __hash_map_const_iterator __t(*this);
993 ++(*this);
994 return __t;
995 }
996
997 friend _LIBCPP_HIDE_FROM_ABI bool
998 operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) {
999 return __x.__i_ == __y.__i_;
1000 }
1001#if _LIBCPP_STD_VER <= 17
1002 friend _LIBCPP_HIDE_FROM_ABI bool
1003 operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) {
1004 return __x.__i_ != __y.__i_;
1005 }
1006#endif
1007
1008 template <class, class, class, class, class>
1009 friend class _LIBCPP_TEMPLATE_VIS unordered_map;
1010 template <class, class, class, class, class>
1011 friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
1012 template <class>
1013 friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator;
1014 template <class>
1015 friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator;
1016};
1017
1018template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1019class unordered_multimap;
1020
1021template <class _Key,
1022 class _Tp,
1023 class _Hash = hash<_Key>,
1024 class _Pred = equal_to<_Key>,
1025 class _Alloc = allocator<pair<const _Key, _Tp> > >
1026class _LIBCPP_TEMPLATE_VIS unordered_map {
1027public:
1028 // types
1029 typedef _Key key_type;
1030 typedef _Tp mapped_type;
1031 typedef __type_identity_t<_Hash> hasher;
1032 typedef __type_identity_t<_Pred> key_equal;
1033 typedef __type_identity_t<_Alloc> allocator_type;
1034 typedef pair<const key_type, mapped_type> value_type;
1035 typedef value_type& reference;
1036 typedef const value_type& const_reference;
1037 static_assert(is_same<value_type, typename allocator_type::value_type>::value,
1038 "Allocator::value_type must be same type as value_type");
1039
1040private:
1041 typedef __hash_value_type<key_type, mapped_type> __value_type;
1042 typedef __unordered_map_hasher<key_type, __value_type, hasher, key_equal> __hasher;
1043 typedef __unordered_map_equal<key_type, __value_type, key_equal, hasher> __key_equal;
1044 typedef __rebind_alloc<allocator_traits<allocator_type>, __value_type> __allocator_type;
1045
1046 typedef __hash_table<__value_type, __hasher, __key_equal, __allocator_type> __table;
1047
1048 __table __table_;
1049
1050 typedef typename __table::_NodeTypes _NodeTypes;
1051 typedef typename __table::__node_pointer __node_pointer;
1052 typedef typename __table::__node_const_pointer __node_const_pointer;
1053 typedef typename __table::__node_traits __node_traits;
1054 typedef typename __table::__node_allocator __node_allocator;
1055 typedef typename __table::__node __node;
1056 typedef __hash_map_node_destructor<__node_allocator> _Dp;
1057 typedef unique_ptr<__node, _Dp> __node_holder;
1058 typedef allocator_traits<allocator_type> __alloc_traits;
1059
1060 static_assert(__check_valid_allocator<allocator_type>::value, "");
1061
1062 static_assert(is_same<typename __table::__container_value_type, value_type>::value, "");
1063 static_assert(is_same<typename __table::__node_value_type, __value_type>::value, "");
1064
1065public:
1066 typedef typename __alloc_traits::pointer pointer;
1067 typedef typename __alloc_traits::const_pointer const_pointer;
1068 typedef typename __table::size_type size_type;
1069 typedef typename __table::difference_type difference_type;
1070
1071 typedef __hash_map_iterator<typename __table::iterator> iterator;
1072 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
1073 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
1074 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
1075
1076#if _LIBCPP_STD_VER >= 17
1077 typedef __map_node_handle<__node, allocator_type> node_type;
1078 typedef __insert_return_type<iterator, node_type> insert_return_type;
1079#endif
1080
1081 template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2>
1082 friend class _LIBCPP_TEMPLATE_VIS unordered_map;
1083 template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2>
1084 friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
1085
1086 _LIBCPP_HIDE_FROM_ABI unordered_map() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) {}
1087 explicit _LIBCPP_HIDE_FROM_ABI
1088 unordered_map(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
1089 _LIBCPP_HIDE_FROM_ABI
1090 unordered_map(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a);
1091 template <class _InputIterator>
1092 _LIBCPP_HIDE_FROM_ABI unordered_map(_InputIterator __first, _InputIterator __last);
1093 template <class _InputIterator>
1094 _LIBCPP_HIDE_FROM_ABI
1095 unordered_map(_InputIterator __first,
1096 _InputIterator __last,
1097 size_type __n,
1098 const hasher& __hf = hasher(),
1099 const key_equal& __eql = key_equal());
1100 template <class _InputIterator>
1101 _LIBCPP_HIDE_FROM_ABI unordered_map(
1102 _InputIterator __first,
1103 _InputIterator __last,
1104 size_type __n,
1105 const hasher& __hf,
1106 const key_equal& __eql,
1107 const allocator_type& __a);
1108
1109#if _LIBCPP_STD_VER >= 23
1110 template <_ContainerCompatibleRange<value_type> _Range>
1111 _LIBCPP_HIDE_FROM_ABI unordered_map(
1112 from_range_t,
1113 _Range&& __range,
1114 size_type __n = /*implementation-defined*/ 0,
1115 const hasher& __hf = hasher(),
1116 const key_equal& __eql = key_equal(),
1117 const allocator_type& __a = allocator_type())
1118 : __table_(__hf, __eql, typename __table::allocator_type(__a)) {
1119 if (__n > 0) {
1120 __table_.__rehash_unique(__n);
1121 }
1122 insert_range(std::forward<_Range>(__range));
1123 }
1124#endif
1125
1126 _LIBCPP_HIDE_FROM_ABI explicit unordered_map(const allocator_type& __a);
1127 _LIBCPP_HIDE_FROM_ABI unordered_map(const unordered_map& __u);
1128 _LIBCPP_HIDE_FROM_ABI unordered_map(const unordered_map& __u, const allocator_type& __a);
1129#ifndef _LIBCPP_CXX03_LANG
1130 _LIBCPP_HIDE_FROM_ABI unordered_map(unordered_map&& __u) _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
1131 _LIBCPP_HIDE_FROM_ABI unordered_map(unordered_map&& __u, const allocator_type& __a);
1132 _LIBCPP_HIDE_FROM_ABI unordered_map(initializer_list<value_type> __il);
1133 _LIBCPP_HIDE_FROM_ABI
1134 unordered_map(initializer_list<value_type> __il,
1135 size_type __n,
1136 const hasher& __hf = hasher(),
1137 const key_equal& __eql = key_equal());
1138 _LIBCPP_HIDE_FROM_ABI unordered_map(
1139 initializer_list<value_type> __il,
1140 size_type __n,
1141 const hasher& __hf,
1142 const key_equal& __eql,
1143 const allocator_type& __a);
1144#endif // _LIBCPP_CXX03_LANG
1145#if _LIBCPP_STD_VER >= 14
1146 _LIBCPP_HIDE_FROM_ABI unordered_map(size_type __n, const allocator_type& __a)
1147 : unordered_map(__n, hasher(), key_equal(), __a) {}
1148 _LIBCPP_HIDE_FROM_ABI unordered_map(size_type __n, const hasher& __hf, const allocator_type& __a)
1149 : unordered_map(__n, __hf, key_equal(), __a) {}
1150 template <class _InputIterator>
1151 _LIBCPP_HIDE_FROM_ABI
1152 unordered_map(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a)
1153 : unordered_map(__first, __last, __n, hasher(), key_equal(), __a) {}
1154 template <class _InputIterator>
1155 _LIBCPP_HIDE_FROM_ABI unordered_map(
1156 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const allocator_type& __a)
1157 : unordered_map(__first, __last, __n, __hf, key_equal(), __a) {}
1158
1159# if _LIBCPP_STD_VER >= 23
1160 template <_ContainerCompatibleRange<value_type> _Range>
1161 _LIBCPP_HIDE_FROM_ABI unordered_map(from_range_t, _Range&& __range, size_type __n, const allocator_type& __a)
1162 : unordered_map(from_range, std::forward<_Range>(__range), __n, hasher(), key_equal(), __a) {}
1163
1164 template <_ContainerCompatibleRange<value_type> _Range>
1165 _LIBCPP_HIDE_FROM_ABI
1166 unordered_map(from_range_t, _Range&& __range, size_type __n, const hasher& __hf, const allocator_type& __a)
1167 : unordered_map(from_range, std::forward<_Range>(__range), __n, __hf, key_equal(), __a) {}
1168# endif
1169
1170 _LIBCPP_HIDE_FROM_ABI unordered_map(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)
1171 : unordered_map(__il, __n, hasher(), key_equal(), __a) {}
1172 _LIBCPP_HIDE_FROM_ABI
1173 unordered_map(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a)
1174 : unordered_map(__il, __n, __hf, key_equal(), __a) {}
1175#endif
1176 _LIBCPP_HIDE_FROM_ABI ~unordered_map() {
1177 static_assert(sizeof(std::__diagnose_unordered_container_requirements<_Key, _Hash, _Pred>(0)), "");
1178 }
1179
1180 _LIBCPP_HIDE_FROM_ABI unordered_map& operator=(const unordered_map& __u) {
1181#ifndef _LIBCPP_CXX03_LANG
1182 __table_ = __u.__table_;
1183#else
1184 if (this != std::addressof(__u)) {
1185 __table_.clear();
1186 __table_.hash_function() = __u.__table_.hash_function();
1187 __table_.key_eq() = __u.__table_.key_eq();
1188 __table_.max_load_factor() = __u.__table_.max_load_factor();
1189 __table_.__copy_assign_alloc(__u.__table_);
1190 insert(__u.begin(), __u.end());
1191 }
1192#endif
1193 return *this;
1194 }
1195#ifndef _LIBCPP_CXX03_LANG
1196 _LIBCPP_HIDE_FROM_ABI unordered_map& operator=(unordered_map&& __u)
1197 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
1198 _LIBCPP_HIDE_FROM_ABI unordered_map& operator=(initializer_list<value_type> __il);
1199#endif // _LIBCPP_CXX03_LANG
1200
1201 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT {
1202 return allocator_type(__table_.__node_alloc());
1203 }
1204
1205 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __table_.size() == 0; }
1206 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __table_.size(); }
1207 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __table_.max_size(); }
1208
1209 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __table_.begin(); }
1210 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __table_.end(); }
1211 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __table_.begin(); }
1212 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __table_.end(); }
1213 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return __table_.begin(); }
1214 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return __table_.end(); }
1215
1216 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(const value_type& __x) { return __table_.__insert_unique(__x); }
1217
1218 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, const value_type& __x) { return insert(__x).first; }
1219
1220 template <class _InputIterator>
1221 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last);
1222
1223#if _LIBCPP_STD_VER >= 23
1224 template <_ContainerCompatibleRange<value_type> _Range>
1225 _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) {
1226 for (auto&& __element : __range) {
1227 __table_.__insert_unique(std::forward<decltype(__element)>(__element));
1228 }
1229 }
1230#endif
1231
1232#ifndef _LIBCPP_CXX03_LANG
1233 _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); }
1234
1235 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(value_type&& __x) {
1236 return __table_.__insert_unique(std::move(__x));
1237 }
1238
1239 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, value_type&& __x) {
1240 return __table_.__insert_unique(std::move(__x)).first;
1241 }
1242
1243 template <class _Pp, __enable_if_t<is_constructible<value_type, _Pp>::value, int> = 0>
1244 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(_Pp&& __x) {
1245 return __table_.__insert_unique(std::forward<_Pp>(__x));
1246 }
1247
1248 template <class _Pp, __enable_if_t<is_constructible<value_type, _Pp>::value, int> = 0>
1249 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, _Pp&& __x) {
1250 return insert(std::forward<_Pp>(__x)).first;
1251 }
1252
1253 template <class... _Args>
1254 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> emplace(_Args&&... __args) {
1255 return __table_.__emplace_unique(std::forward<_Args>(__args)...);
1256 }
1257
1258 template <class... _Args>
1259 _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator, _Args&&... __args) {
1260 return __table_.__emplace_unique(std::forward<_Args>(__args)...).first;
1261 }
1262
1263#endif // _LIBCPP_CXX03_LANG
1264
1265#if _LIBCPP_STD_VER >= 17
1266 template <class... _Args>
1267 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args) {
1268 return __table_.__emplace_unique_key_args(
1269 __k, piecewise_construct, std::forward_as_tuple(__k), std::forward_as_tuple(std::forward<_Args>(__args)...));
1270 }
1271
1272 template <class... _Args>
1273 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args) {
1274 return __table_.__emplace_unique_key_args(
1275 __k,
1276 piecewise_construct,
1277 std::forward_as_tuple(std::move(__k)),
1278 std::forward_as_tuple(std::forward<_Args>(__args)...));
1279 }
1280
1281 template <class... _Args>
1282 _LIBCPP_HIDE_FROM_ABI iterator try_emplace(const_iterator, const key_type& __k, _Args&&... __args) {
1283 return try_emplace(__k, std::forward<_Args>(__args)...).first;
1284 }
1285
1286 template <class... _Args>
1287 _LIBCPP_HIDE_FROM_ABI iterator try_emplace(const_iterator, key_type&& __k, _Args&&... __args) {
1288 return try_emplace(std::move(__k), std::forward<_Args>(__args)...).first;
1289 }
1290
1291 template <class _Vp>
1292 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert_or_assign(const key_type& __k, _Vp&& __v) {
1293 pair<iterator, bool> __res = __table_.__emplace_unique_key_args(__k, __k, std::forward<_Vp>(__v));
1294 if (!__res.second) {
1295 __res.first->second = std::forward<_Vp>(__v);
1296 }
1297 return __res;
1298 }
1299
1300 template <class _Vp>
1301 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert_or_assign(key_type&& __k, _Vp&& __v) {
1302 pair<iterator, bool> __res = __table_.__emplace_unique_key_args(__k, std::move(__k), std::forward<_Vp>(__v));
1303 if (!__res.second) {
1304 __res.first->second = std::forward<_Vp>(__v);
1305 }
1306 return __res;
1307 }
1308
1309 template <class _Vp>
1310 _LIBCPP_HIDE_FROM_ABI iterator insert_or_assign(const_iterator, const key_type& __k, _Vp&& __v) {
1311 return insert_or_assign(__k, std::forward<_Vp>(__v)).first;
1312 }
1313
1314 template <class _Vp>
1315 _LIBCPP_HIDE_FROM_ABI iterator insert_or_assign(const_iterator, key_type&& __k, _Vp&& __v) {
1316 return insert_or_assign(std::move(__k), std::forward<_Vp>(__v)).first;
1317 }
1318#endif // _LIBCPP_STD_VER >= 17
1319
1320 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __table_.erase(__p.__i_); }
1321 _LIBCPP_HIDE_FROM_ABI iterator erase(iterator __p) { return __table_.erase(__p.__i_); }
1322 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_unique(__k); }
1323 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last) {
1324 return __table_.erase(__first.__i_, __last.__i_);
1325 }
1326 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __table_.clear(); }
1327
1328#if _LIBCPP_STD_VER >= 17
1329 _LIBCPP_HIDE_FROM_ABI insert_return_type insert(node_type&& __nh) {
1330 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
1331 "node_type with incompatible allocator passed to unordered_map::insert()");
1332 return __table_.template __node_handle_insert_unique< node_type, insert_return_type>(std::move(__nh));
1333 }
1334 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, node_type&& __nh) {
1335 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
1336 "node_type with incompatible allocator passed to unordered_map::insert()");
1337 return __table_.template __node_handle_insert_unique<node_type>(__hint.__i_, std::move(__nh));
1338 }
1339 _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) {
1340 return __table_.template __node_handle_extract<node_type>(__key);
1341 }
1342 _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __it) {
1343 return __table_.template __node_handle_extract<node_type>(__it.__i_);
1344 }
1345
1346 template <class _H2, class _P2>
1347 _LIBCPP_HIDE_FROM_ABI void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>& __source) {
1348 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1349 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1350 return __table_.__node_handle_merge_unique(__source.__table_);
1351 }
1352 template <class _H2, class _P2>
1353 _LIBCPP_HIDE_FROM_ABI void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>&& __source) {
1354 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1355 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1356 return __table_.__node_handle_merge_unique(__source.__table_);
1357 }
1358 template <class _H2, class _P2>
1359 _LIBCPP_HIDE_FROM_ABI void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>& __source) {
1360 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1361 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1362 return __table_.__node_handle_merge_unique(__source.__table_);
1363 }
1364 template <class _H2, class _P2>
1365 _LIBCPP_HIDE_FROM_ABI void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>&& __source) {
1366 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1367 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1368 return __table_.__node_handle_merge_unique(__source.__table_);
1369 }
1370#endif
1371
1372 _LIBCPP_HIDE_FROM_ABI void swap(unordered_map& __u) _NOEXCEPT_(__is_nothrow_swappable_v<__table>) {
1373 __table_.swap(__u.__table_);
1374 }
1375
1376 _LIBCPP_HIDE_FROM_ABI hasher hash_function() const { return __table_.hash_function().hash_function(); }
1377 _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq().key_eq(); }
1378
1379 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); }
1380 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); }
1381#if _LIBCPP_STD_VER >= 20
1382 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
1383 _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) {
1384 return __table_.find(__k);
1385 }
1386 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
1387 _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const {
1388 return __table_.find(__k);
1389 }
1390#endif // _LIBCPP_STD_VER >= 20
1391
1392 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_unique(__k); }
1393#if _LIBCPP_STD_VER >= 20
1394 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
1395 _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const {
1396 return __table_.__count_unique(__k);
1397 }
1398#endif // _LIBCPP_STD_VER >= 20
1399
1400#if _LIBCPP_STD_VER >= 20
1401 _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); }
1402
1403 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
1404 _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const {
1405 return find(__k) != end();
1406 }
1407#endif // _LIBCPP_STD_VER >= 20
1408
1409 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {
1410 return __table_.__equal_range_unique(__k);
1411 }
1412 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
1413 return __table_.__equal_range_unique(__k);
1414 }
1415#if _LIBCPP_STD_VER >= 20
1416 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
1417 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) {
1418 return __table_.__equal_range_unique(__k);
1419 }
1420 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
1421 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const {
1422 return __table_.__equal_range_unique(__k);
1423 }
1424#endif // _LIBCPP_STD_VER >= 20
1425
1426 _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](const key_type& __k);
1427#ifndef _LIBCPP_CXX03_LANG
1428 _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](key_type&& __k);
1429#endif
1430
1431 _LIBCPP_HIDE_FROM_ABI mapped_type& at(const key_type& __k);
1432 _LIBCPP_HIDE_FROM_ABI const mapped_type& at(const key_type& __k) const;
1433
1434 _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const _NOEXCEPT { return __table_.bucket_count(); }
1435 _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const _NOEXCEPT { return __table_.max_bucket_count(); }
1436
1437 _LIBCPP_HIDE_FROM_ABI size_type bucket_size(size_type __n) const { return __table_.bucket_size(__n); }
1438 _LIBCPP_HIDE_FROM_ABI size_type bucket(const key_type& __k) const { return __table_.bucket(__k); }
1439
1440 _LIBCPP_HIDE_FROM_ABI local_iterator begin(size_type __n) { return __table_.begin(__n); }
1441 _LIBCPP_HIDE_FROM_ABI local_iterator end(size_type __n) { return __table_.end(__n); }
1442 _LIBCPP_HIDE_FROM_ABI const_local_iterator begin(size_type __n) const { return __table_.cbegin(__n); }
1443 _LIBCPP_HIDE_FROM_ABI const_local_iterator end(size_type __n) const { return __table_.cend(__n); }
1444 _LIBCPP_HIDE_FROM_ABI const_local_iterator cbegin(size_type __n) const { return __table_.cbegin(__n); }
1445 _LIBCPP_HIDE_FROM_ABI const_local_iterator cend(size_type __n) const { return __table_.cend(__n); }
1446
1447 _LIBCPP_HIDE_FROM_ABI float load_factor() const _NOEXCEPT { return __table_.load_factor(); }
1448 _LIBCPP_HIDE_FROM_ABI float max_load_factor() const _NOEXCEPT { return __table_.max_load_factor(); }
1449 _LIBCPP_HIDE_FROM_ABI void max_load_factor(float __mlf) { __table_.max_load_factor(__mlf); }
1450 _LIBCPP_HIDE_FROM_ABI void rehash(size_type __n) { __table_.__rehash_unique(__n); }
1451 _LIBCPP_HIDE_FROM_ABI void reserve(size_type __n) { __table_.__reserve_unique(__n); }
1452
1453private:
1454#ifdef _LIBCPP_CXX03_LANG
1455 _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node_with_key(const key_type& __k);
1456#endif
1457};
1458
1459#if _LIBCPP_STD_VER >= 17
1460template <class _InputIterator,
1461 class _Hash = hash<__iter_key_type<_InputIterator>>,
1462 class _Pred = equal_to<__iter_key_type<_InputIterator>>,
1463 class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>,
1464 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
1465 class = enable_if_t<!__is_allocator<_Hash>::value>,
1466 class = enable_if_t<!is_integral<_Hash>::value>,
1467 class = enable_if_t<!__is_allocator<_Pred>::value>,
1468 class = enable_if_t<__is_allocator<_Allocator>::value>>
1469unordered_map(_InputIterator,
1470 _InputIterator,
1471 typename allocator_traits<_Allocator>::size_type = 0,
1472 _Hash = _Hash(),
1473 _Pred = _Pred(),
1474 _Allocator = _Allocator())
1475 -> unordered_map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Hash, _Pred, _Allocator>;
1476
1477# if _LIBCPP_STD_VER >= 23
1478template <ranges::input_range _Range,
1479 class _Hash = hash<__range_key_type<_Range>>,
1480 class _Pred = equal_to<__range_key_type<_Range>>,
1481 class _Allocator = allocator<__range_to_alloc_type<_Range>>,
1482 class = enable_if_t<!__is_allocator<_Hash>::value>,
1483 class = enable_if_t<!is_integral<_Hash>::value>,
1484 class = enable_if_t<!__is_allocator<_Pred>::value>,
1485 class = enable_if_t<__is_allocator<_Allocator>::value>>
1486unordered_map(from_range_t,
1487 _Range&&,
1488 typename allocator_traits<_Allocator>::size_type = 0,
1489 _Hash = _Hash(),
1490 _Pred = _Pred(),
1491 _Allocator = _Allocator())
1492 -> unordered_map<__range_key_type<_Range>, __range_mapped_type<_Range>, _Hash, _Pred, _Allocator>; // C++23
1493# endif
1494
1495template <class _Key,
1496 class _Tp,
1497 class _Hash = hash<remove_const_t<_Key>>,
1498 class _Pred = equal_to<remove_const_t<_Key>>,
1499 class _Allocator = allocator<pair<const _Key, _Tp>>,
1500 class = enable_if_t<!__is_allocator<_Hash>::value>,
1501 class = enable_if_t<!is_integral<_Hash>::value>,
1502 class = enable_if_t<!__is_allocator<_Pred>::value>,
1503 class = enable_if_t<__is_allocator<_Allocator>::value>>
1504unordered_map(initializer_list<pair<_Key, _Tp>>,
1505 typename allocator_traits<_Allocator>::size_type = 0,
1506 _Hash = _Hash(),
1507 _Pred = _Pred(),
1508 _Allocator = _Allocator()) -> unordered_map<remove_const_t<_Key>, _Tp, _Hash, _Pred, _Allocator>;
1509
1510template <class _InputIterator,
1511 class _Allocator,
1512 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
1513 class = enable_if_t<__is_allocator<_Allocator>::value>>
1514unordered_map(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Allocator)
1515 -> unordered_map<__iter_key_type<_InputIterator>,
1516 __iter_mapped_type<_InputIterator>,
1517 hash<__iter_key_type<_InputIterator>>,
1518 equal_to<__iter_key_type<_InputIterator>>,
1519 _Allocator>;
1520
1521template <class _InputIterator,
1522 class _Allocator,
1523 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
1524 class = enable_if_t<__is_allocator<_Allocator>::value>>
1525unordered_map(_InputIterator, _InputIterator, _Allocator)
1526 -> unordered_map<__iter_key_type<_InputIterator>,
1527 __iter_mapped_type<_InputIterator>,
1528 hash<__iter_key_type<_InputIterator>>,
1529 equal_to<__iter_key_type<_InputIterator>>,
1530 _Allocator>;
1531
1532template <class _InputIterator,
1533 class _Hash,
1534 class _Allocator,
1535 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
1536 class = enable_if_t<!__is_allocator<_Hash>::value>,
1537 class = enable_if_t<!is_integral<_Hash>::value>,
1538 class = enable_if_t<__is_allocator<_Allocator>::value>>
1539unordered_map(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
1540 -> unordered_map<__iter_key_type<_InputIterator>,
1541 __iter_mapped_type<_InputIterator>,
1542 _Hash,
1543 equal_to<__iter_key_type<_InputIterator>>,
1544 _Allocator>;
1545
1546# if _LIBCPP_STD_VER >= 23
1547
1548template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
1549unordered_map(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Allocator)
1550 -> unordered_map<__range_key_type<_Range>,
1551 __range_mapped_type<_Range>,
1552 hash<__range_key_type<_Range>>,
1553 equal_to<__range_key_type<_Range>>,
1554 _Allocator>;
1555
1556template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
1557unordered_map(from_range_t, _Range&&, _Allocator)
1558 -> unordered_map<__range_key_type<_Range>,
1559 __range_mapped_type<_Range>,
1560 hash<__range_key_type<_Range>>,
1561 equal_to<__range_key_type<_Range>>,
1562 _Allocator>;
1563
1564template <ranges::input_range _Range,
1565 class _Hash,
1566 class _Allocator,
1567 class = enable_if_t<!__is_allocator<_Hash>::value>,
1568 class = enable_if_t<!is_integral<_Hash>::value>,
1569 class = enable_if_t<__is_allocator<_Allocator>::value>>
1570unordered_map(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
1571 -> unordered_map<__range_key_type<_Range>,
1572 __range_mapped_type<_Range>,
1573 _Hash,
1574 equal_to<__range_key_type<_Range>>,
1575 _Allocator>;
1576
1577# endif
1578
1579template <class _Key, class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
1580unordered_map(initializer_list<pair<_Key, _Tp>>, typename allocator_traits<_Allocator>::size_type, _Allocator)
1581 -> unordered_map<remove_const_t<_Key>, _Tp, hash<remove_const_t<_Key>>, equal_to<remove_const_t<_Key>>, _Allocator>;
1582
1583template <class _Key, class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
1584unordered_map(initializer_list<pair<_Key, _Tp>>, _Allocator)
1585 -> unordered_map<remove_const_t<_Key>, _Tp, hash<remove_const_t<_Key>>, equal_to<remove_const_t<_Key>>, _Allocator>;
1586
1587template <class _Key,
1588 class _Tp,
1589 class _Hash,
1590 class _Allocator,
1591 class = enable_if_t<!__is_allocator<_Hash>::value>,
1592 class = enable_if_t<!is_integral<_Hash>::value>,
1593 class = enable_if_t<__is_allocator<_Allocator>::value>>
1594unordered_map(initializer_list<pair<_Key, _Tp>>, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
1595 -> unordered_map<remove_const_t<_Key>, _Tp, _Hash, equal_to<remove_const_t<_Key>>, _Allocator>;
1596#endif
1597
1598template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1599unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(size_type __n, const hasher& __hf, const key_equal& __eql)
1600 : __table_(__hf, __eql) {
1601 __table_.__rehash_unique(__n);
1602}
1603
1604template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1605unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1606 size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1607 : __table_(__hf, __eql, typename __table::allocator_type(__a)) {
1608 __table_.__rehash_unique(__n);
1609}
1610
1611template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1612inline unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(const allocator_type& __a)
1613 : __table_(typename __table::allocator_type(__a)) {}
1614
1615template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1616template <class _InputIterator>
1617unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(_InputIterator __first, _InputIterator __last) {
1618 insert(__first, __last);
1619}
1620
1621template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1622template <class _InputIterator>
1623unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1624 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql)
1625 : __table_(__hf, __eql) {
1626 __table_.__rehash_unique(__n);
1627 insert(__first, __last);
1628}
1629
1630template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1631template <class _InputIterator>
1632unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1633 _InputIterator __first,
1634 _InputIterator __last,
1635 size_type __n,
1636 const hasher& __hf,
1637 const key_equal& __eql,
1638 const allocator_type& __a)
1639 : __table_(__hf, __eql, typename __table::allocator_type(__a)) {
1640 __table_.__rehash_unique(__n);
1641 insert(__first, __last);
1642}
1643
1644template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1645unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(const unordered_map& __u) : __table_(__u.__table_) {
1646 __table_.__rehash_unique(__u.bucket_count());
1647 insert(__u.begin(), __u.end());
1648}
1649
1650template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1651unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(const unordered_map& __u, const allocator_type& __a)
1652 : __table_(__u.__table_, typename __table::allocator_type(__a)) {
1653 __table_.__rehash_unique(__u.bucket_count());
1654 insert(__u.begin(), __u.end());
1655}
1656
1657#ifndef _LIBCPP_CXX03_LANG
1658
1659template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1660inline unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(unordered_map&& __u)
1661 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
1662 : __table_(std::move(__u.__table_)) {}
1663
1664template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1665unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(unordered_map&& __u, const allocator_type& __a)
1666 : __table_(std::move(__u.__table_), typename __table::allocator_type(__a)) {
1667 if (__a != __u.get_allocator()) {
1668 iterator __i = __u.begin();
1669 while (__u.size() != 0) {
1670 __table_.__emplace_unique(__u.__table_.remove((__i++).__i_)->__get_value().__move());
1671 }
1672 }
1673}
1674
1675template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1676unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(initializer_list<value_type> __il) {
1677 insert(__il.begin(), __il.end());
1678}
1679
1680template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1681unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1682 initializer_list<value_type> __il, size_type __n, const hasher& __hf, const key_equal& __eql)
1683 : __table_(__hf, __eql) {
1684 __table_.__rehash_unique(__n);
1685 insert(__il.begin(), __il.end());
1686}
1687
1688template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1689unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1690 initializer_list<value_type> __il,
1691 size_type __n,
1692 const hasher& __hf,
1693 const key_equal& __eql,
1694 const allocator_type& __a)
1695 : __table_(__hf, __eql, typename __table::allocator_type(__a)) {
1696 __table_.__rehash_unique(__n);
1697 insert(__il.begin(), __il.end());
1698}
1699
1700template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1701inline unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
1702unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_map&& __u)
1703 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) {
1704 __table_ = std::move(__u.__table_);
1705 return *this;
1706}
1707
1708template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1709inline unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
1710unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(initializer_list<value_type> __il) {
1711 __table_.__assign_unique(__il.begin(), __il.end());
1712 return *this;
1713}
1714
1715#endif // _LIBCPP_CXX03_LANG
1716
1717template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1718template <class _InputIterator>
1719inline void unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) {
1720 for (; __first != __last; ++__first)
1721 __table_.__insert_unique(*__first);
1722}
1723
1724#ifndef _LIBCPP_CXX03_LANG
1725
1726template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1727_Tp& unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k) {
1728 return __table_
1729 .__emplace_unique_key_args(__k, piecewise_construct, std::forward_as_tuple(__k), std::forward_as_tuple())
1730 .first->__get_value()
1731 .second;
1732}
1733
1734template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1735_Tp& unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&& __k) {
1736 return __table_
1737 .__emplace_unique_key_args(
1738 __k, piecewise_construct, std::forward_as_tuple(std::move(__k)), std::forward_as_tuple())
1739 .first->__get_value()
1740 .second;
1741}
1742#else // _LIBCPP_CXX03_LANG
1743
1744template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1745typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1746unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(const key_type& __k) {
1747 __node_allocator& __na = __table_.__node_alloc();
1748 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1749 __node_traits::construct(__na, std::addressof(__h->__get_value().__get_value().first), __k);
1750 __h.get_deleter().__first_constructed = true;
1751 __node_traits::construct(__na, std::addressof(__h->__get_value().__get_value().second));
1752 __h.get_deleter().__second_constructed = true;
1753 return __h;
1754}
1755
1756template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1757_Tp& unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k) {
1758 iterator __i = find(__k);
1759 if (__i != end())
1760 return __i->second;
1761 __node_holder __h = __construct_node_with_key(__k);
1762 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1763 __h.release();
1764 return __r.first->second;
1765}
1766
1767#endif // _LIBCPP_CXX03_LANG
1768
1769template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1770_Tp& unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) {
1771 iterator __i = find(__k);
1772 if (__i == end())
1773 __throw_out_of_range("unordered_map::at: key not found");
1774 return __i->second;
1775}
1776
1777template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1778const _Tp& unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) const {
1779 const_iterator __i = find(__k);
1780 if (__i == end())
1781 __throw_out_of_range("unordered_map::at: key not found");
1782 return __i->second;
1783}
1784
1785template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1786inline _LIBCPP_HIDE_FROM_ABI void
1787swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1788 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
1789 __x.swap(__y);
1790}
1791
1792#if _LIBCPP_STD_VER >= 20
1793template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc, class _Predicate>
1794inline _LIBCPP_HIDE_FROM_ABI typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::size_type
1795erase_if(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __c, _Predicate __pred) {
1796 return std::__libcpp_erase_if_container(__c, __pred);
1797}
1798#endif
1799
1800template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1801_LIBCPP_HIDE_FROM_ABI bool operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1802 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) {
1803 if (__x.size() != __y.size())
1804 return false;
1805 typedef typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator const_iterator;
1806 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); __i != __ex; ++__i) {
1807 const_iterator __j = __y.find(__i->first);
1808 if (__j == __ey || !(*__i == *__j))
1809 return false;
1810 }
1811 return true;
1812}
1813
1814#if _LIBCPP_STD_VER <= 17
1815
1816template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1817inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1818 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) {
1819 return !(__x == __y);
1820}
1821
1822#endif
1823
1824template <class _Key,
1825 class _Tp,
1826 class _Hash = hash<_Key>,
1827 class _Pred = equal_to<_Key>,
1828 class _Alloc = allocator<pair<const _Key, _Tp> > >
1829class _LIBCPP_TEMPLATE_VIS unordered_multimap {
1830public:
1831 // types
1832 typedef _Key key_type;
1833 typedef _Tp mapped_type;
1834 typedef __type_identity_t<_Hash> hasher;
1835 typedef __type_identity_t<_Pred> key_equal;
1836 typedef __type_identity_t<_Alloc> allocator_type;
1837 typedef pair<const key_type, mapped_type> value_type;
1838 typedef value_type& reference;
1839 typedef const value_type& const_reference;
1840 static_assert(__check_valid_allocator<allocator_type>::value, "");
1841 static_assert(is_same<value_type, typename allocator_type::value_type>::value,
1842 "Allocator::value_type must be same type as value_type");
1843
1844private:
1845 typedef __hash_value_type<key_type, mapped_type> __value_type;
1846 typedef __unordered_map_hasher<key_type, __value_type, hasher, key_equal> __hasher;
1847 typedef __unordered_map_equal<key_type, __value_type, key_equal, hasher> __key_equal;
1848 typedef __rebind_alloc<allocator_traits<allocator_type>, __value_type> __allocator_type;
1849
1850 typedef __hash_table<__value_type, __hasher, __key_equal, __allocator_type> __table;
1851
1852 __table __table_;
1853
1854 typedef typename __table::_NodeTypes _NodeTypes;
1855 typedef typename __table::__node_traits __node_traits;
1856 typedef typename __table::__node_allocator __node_allocator;
1857 typedef typename __table::__node __node;
1858 typedef __hash_map_node_destructor<__node_allocator> _Dp;
1859 typedef unique_ptr<__node, _Dp> __node_holder;
1860 typedef allocator_traits<allocator_type> __alloc_traits;
1861 static_assert(is_same<typename __node_traits::size_type, typename __alloc_traits::size_type>::value,
1862 "Allocator uses different size_type for different types");
1863
1864public:
1865 typedef typename __alloc_traits::pointer pointer;
1866 typedef typename __alloc_traits::const_pointer const_pointer;
1867 typedef typename __table::size_type size_type;
1868 typedef typename __table::difference_type difference_type;
1869
1870 typedef __hash_map_iterator<typename __table::iterator> iterator;
1871 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
1872 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
1873 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
1874
1875#if _LIBCPP_STD_VER >= 17
1876 typedef __map_node_handle<__node, allocator_type> node_type;
1877#endif
1878
1879 template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2>
1880 friend class _LIBCPP_TEMPLATE_VIS unordered_map;
1881 template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2>
1882 friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
1883
1884 _LIBCPP_HIDE_FROM_ABI unordered_multimap() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) {}
1885 explicit _LIBCPP_HIDE_FROM_ABI
1886 unordered_multimap(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
1887 _LIBCPP_HIDE_FROM_ABI
1888 unordered_multimap(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a);
1889 template <class _InputIterator>
1890 _LIBCPP_HIDE_FROM_ABI unordered_multimap(_InputIterator __first, _InputIterator __last);
1891 template <class _InputIterator>
1892 _LIBCPP_HIDE_FROM_ABI unordered_multimap(
1893 _InputIterator __first,
1894 _InputIterator __last,
1895 size_type __n,
1896 const hasher& __hf = hasher(),
1897 const key_equal& __eql = key_equal());
1898 template <class _InputIterator>
1899 _LIBCPP_HIDE_FROM_ABI unordered_multimap(
1900 _InputIterator __first,
1901 _InputIterator __last,
1902 size_type __n,
1903 const hasher& __hf,
1904 const key_equal& __eql,
1905 const allocator_type& __a);
1906
1907#if _LIBCPP_STD_VER >= 23
1908 template <_ContainerCompatibleRange<value_type> _Range>
1909 _LIBCPP_HIDE_FROM_ABI unordered_multimap(
1910 from_range_t,
1911 _Range&& __range,
1912 size_type __n = /*implementation-defined*/ 0,
1913 const hasher& __hf = hasher(),
1914 const key_equal& __eql = key_equal(),
1915 const allocator_type& __a = allocator_type())
1916 : __table_(__hf, __eql, typename __table::allocator_type(__a)) {
1917 if (__n > 0) {
1918 __table_.__rehash_multi(__n);
1919 }
1920 insert_range(std::forward<_Range>(__range));
1921 }
1922#endif
1923
1924 _LIBCPP_HIDE_FROM_ABI explicit unordered_multimap(const allocator_type& __a);
1925 _LIBCPP_HIDE_FROM_ABI unordered_multimap(const unordered_multimap& __u);
1926 _LIBCPP_HIDE_FROM_ABI unordered_multimap(const unordered_multimap& __u, const allocator_type& __a);
1927#ifndef _LIBCPP_CXX03_LANG
1928 _LIBCPP_HIDE_FROM_ABI unordered_multimap(unordered_multimap&& __u)
1929 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
1930 _LIBCPP_HIDE_FROM_ABI unordered_multimap(unordered_multimap&& __u, const allocator_type& __a);
1931 _LIBCPP_HIDE_FROM_ABI unordered_multimap(initializer_list<value_type> __il);
1932 _LIBCPP_HIDE_FROM_ABI unordered_multimap(
1933 initializer_list<value_type> __il,
1934 size_type __n,
1935 const hasher& __hf = hasher(),
1936 const key_equal& __eql = key_equal());
1937 _LIBCPP_HIDE_FROM_ABI unordered_multimap(
1938 initializer_list<value_type> __il,
1939 size_type __n,
1940 const hasher& __hf,
1941 const key_equal& __eql,
1942 const allocator_type& __a);
1943#endif // _LIBCPP_CXX03_LANG
1944#if _LIBCPP_STD_VER >= 14
1945 _LIBCPP_HIDE_FROM_ABI unordered_multimap(size_type __n, const allocator_type& __a)
1946 : unordered_multimap(__n, hasher(), key_equal(), __a) {}
1947 _LIBCPP_HIDE_FROM_ABI unordered_multimap(size_type __n, const hasher& __hf, const allocator_type& __a)
1948 : unordered_multimap(__n, __hf, key_equal(), __a) {}
1949 template <class _InputIterator>
1950 _LIBCPP_HIDE_FROM_ABI
1951 unordered_multimap(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a)
1952 : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a) {}
1953 template <class _InputIterator>
1954 _LIBCPP_HIDE_FROM_ABI unordered_multimap(
1955 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const allocator_type& __a)
1956 : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a) {}
1957
1958# if _LIBCPP_STD_VER >= 23
1959 template <_ContainerCompatibleRange<value_type> _Range>
1960 _LIBCPP_HIDE_FROM_ABI unordered_multimap(from_range_t, _Range&& __range, size_type __n, const allocator_type& __a)
1961 : unordered_multimap(from_range, std::forward<_Range>(__range), __n, hasher(), key_equal(), __a) {}
1962
1963 template <_ContainerCompatibleRange<value_type> _Range>
1964 _LIBCPP_HIDE_FROM_ABI
1965 unordered_multimap(from_range_t, _Range&& __range, size_type __n, const hasher& __hf, const allocator_type& __a)
1966 : unordered_multimap(from_range, std::forward<_Range>(__range), __n, __hf, key_equal(), __a) {}
1967# endif
1968
1969 _LIBCPP_HIDE_FROM_ABI unordered_multimap(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)
1970 : unordered_multimap(__il, __n, hasher(), key_equal(), __a) {}
1971 _LIBCPP_HIDE_FROM_ABI
1972 unordered_multimap(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a)
1973 : unordered_multimap(__il, __n, __hf, key_equal(), __a) {}
1974#endif
1975 _LIBCPP_HIDE_FROM_ABI ~unordered_multimap() {
1976 static_assert(sizeof(std::__diagnose_unordered_container_requirements<_Key, _Hash, _Pred>(0)), "");
1977 }
1978
1979 _LIBCPP_HIDE_FROM_ABI unordered_multimap& operator=(const unordered_multimap& __u) {
1980#ifndef _LIBCPP_CXX03_LANG
1981 __table_ = __u.__table_;
1982#else
1983 if (this != std::addressof(__u)) {
1984 __table_.clear();
1985 __table_.hash_function() = __u.__table_.hash_function();
1986 __table_.key_eq() = __u.__table_.key_eq();
1987 __table_.max_load_factor() = __u.__table_.max_load_factor();
1988 __table_.__copy_assign_alloc(__u.__table_);
1989 insert(__u.begin(), __u.end());
1990 }
1991#endif
1992 return *this;
1993 }
1994#ifndef _LIBCPP_CXX03_LANG
1995 _LIBCPP_HIDE_FROM_ABI unordered_multimap& operator=(unordered_multimap&& __u)
1996 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
1997 _LIBCPP_HIDE_FROM_ABI unordered_multimap& operator=(initializer_list<value_type> __il);
1998#endif // _LIBCPP_CXX03_LANG
1999
2000 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT {
2001 return allocator_type(__table_.__node_alloc());
2002 }
2003
2004 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __table_.size() == 0; }
2005 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __table_.size(); }
2006 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __table_.max_size(); }
2007
2008 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __table_.begin(); }
2009 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __table_.end(); }
2010 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __table_.begin(); }
2011 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __table_.end(); }
2012 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return __table_.begin(); }
2013 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return __table_.end(); }
2014
2015 _LIBCPP_HIDE_FROM_ABI iterator insert(const value_type& __x) { return __table_.__insert_multi(__x); }
2016
2017 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __x) {
2018 return __table_.__insert_multi(__p.__i_, __x);
2019 }
2020
2021 template <class _InputIterator>
2022 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last);
2023
2024#if _LIBCPP_STD_VER >= 23
2025 template <_ContainerCompatibleRange<value_type> _Range>
2026 _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) {
2027 for (auto&& __element : __range) {
2028 __table_.__insert_multi(std::forward<decltype(__element)>(__element));
2029 }
2030 }
2031#endif
2032
2033#ifndef _LIBCPP_CXX03_LANG
2034 _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); }
2035 _LIBCPP_HIDE_FROM_ABI iterator insert(value_type&& __x) { return __table_.__insert_multi(std::move(__x)); }
2036
2037 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __x) {
2038 return __table_.__insert_multi(__p.__i_, std::move(__x));
2039 }
2040
2041 template <class _Pp, __enable_if_t<is_constructible<value_type, _Pp>::value, int> = 0>
2042 _LIBCPP_HIDE_FROM_ABI iterator insert(_Pp&& __x) {
2043 return __table_.__insert_multi(std::forward<_Pp>(__x));
2044 }
2045
2046 template <class _Pp, __enable_if_t<is_constructible<value_type, _Pp>::value, int> = 0>
2047 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, _Pp&& __x) {
2048 return __table_.__insert_multi(__p.__i_, std::forward<_Pp>(__x));
2049 }
2050
2051 template <class... _Args>
2052 _LIBCPP_HIDE_FROM_ABI iterator emplace(_Args&&... __args) {
2053 return __table_.__emplace_multi(std::forward<_Args>(__args)...);
2054 }
2055
2056 template <class... _Args>
2057 _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __p, _Args&&... __args) {
2058 return __table_.__emplace_hint_multi(__p.__i_, std::forward<_Args>(__args)...);
2059 }
2060#endif // _LIBCPP_CXX03_LANG
2061
2062 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __table_.erase(__p.__i_); }
2063 _LIBCPP_HIDE_FROM_ABI iterator erase(iterator __p) { return __table_.erase(__p.__i_); }
2064 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_multi(__k); }
2065 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last) {
2066 return __table_.erase(__first.__i_, __last.__i_);
2067 }
2068 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __table_.clear(); }
2069
2070#if _LIBCPP_STD_VER >= 17
2071 _LIBCPP_HIDE_FROM_ABI iterator insert(node_type&& __nh) {
2072 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
2073 "node_type with incompatible allocator passed to unordered_multimap::insert()");
2074 return __table_.template __node_handle_insert_multi<node_type>(std::move(__nh));
2075 }
2076 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, node_type&& __nh) {
2077 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
2078 "node_type with incompatible allocator passed to unordered_multimap::insert()");
2079 return __table_.template __node_handle_insert_multi<node_type>(__hint.__i_, std::move(__nh));
2080 }
2081 _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) {
2082 return __table_.template __node_handle_extract<node_type>(__key);
2083 }
2084 _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __it) {
2085 return __table_.template __node_handle_extract<node_type>(__it.__i_);
2086 }
2087
2088 template <class _H2, class _P2>
2089 _LIBCPP_HIDE_FROM_ABI void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>& __source) {
2090 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
2091 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
2092 return __table_.__node_handle_merge_multi(__source.__table_);
2093 }
2094 template <class _H2, class _P2>
2095 _LIBCPP_HIDE_FROM_ABI void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>&& __source) {
2096 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
2097 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
2098 return __table_.__node_handle_merge_multi(__source.__table_);
2099 }
2100 template <class _H2, class _P2>
2101 _LIBCPP_HIDE_FROM_ABI void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>& __source) {
2102 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
2103 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
2104 return __table_.__node_handle_merge_multi(__source.__table_);
2105 }
2106 template <class _H2, class _P2>
2107 _LIBCPP_HIDE_FROM_ABI void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>&& __source) {
2108 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
2109 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
2110 return __table_.__node_handle_merge_multi(__source.__table_);
2111 }
2112#endif
2113
2114 _LIBCPP_HIDE_FROM_ABI void swap(unordered_multimap& __u) _NOEXCEPT_(__is_nothrow_swappable_v<__table>) {
2115 __table_.swap(__u.__table_);
2116 }
2117
2118 _LIBCPP_HIDE_FROM_ABI hasher hash_function() const { return __table_.hash_function().hash_function(); }
2119 _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq().key_eq(); }
2120
2121 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); }
2122 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); }
2123#if _LIBCPP_STD_VER >= 20
2124 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
2125 _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) {
2126 return __table_.find(__k);
2127 }
2128 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
2129 _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const {
2130 return __table_.find(__k);
2131 }
2132#endif // _LIBCPP_STD_VER >= 20
2133
2134 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_multi(__k); }
2135#if _LIBCPP_STD_VER >= 20
2136 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
2137 _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const {
2138 return __table_.__count_multi(__k);
2139 }
2140#endif // _LIBCPP_STD_VER >= 20
2141
2142#if _LIBCPP_STD_VER >= 20
2143 _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); }
2144
2145 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
2146 _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const {
2147 return find(__k) != end();
2148 }
2149#endif // _LIBCPP_STD_VER >= 20
2150
2151 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {
2152 return __table_.__equal_range_multi(__k);
2153 }
2154 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
2155 return __table_.__equal_range_multi(__k);
2156 }
2157#if _LIBCPP_STD_VER >= 20
2158 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
2159 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) {
2160 return __table_.__equal_range_multi(__k);
2161 }
2162 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
2163 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const {
2164 return __table_.__equal_range_multi(__k);
2165 }
2166#endif // _LIBCPP_STD_VER >= 20
2167
2168 _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const _NOEXCEPT { return __table_.bucket_count(); }
2169 _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const _NOEXCEPT { return __table_.max_bucket_count(); }
2170
2171 _LIBCPP_HIDE_FROM_ABI size_type bucket_size(size_type __n) const { return __table_.bucket_size(__n); }
2172 _LIBCPP_HIDE_FROM_ABI size_type bucket(const key_type& __k) const { return __table_.bucket(__k); }
2173
2174 _LIBCPP_HIDE_FROM_ABI local_iterator begin(size_type __n) { return __table_.begin(__n); }
2175 _LIBCPP_HIDE_FROM_ABI local_iterator end(size_type __n) { return __table_.end(__n); }
2176 _LIBCPP_HIDE_FROM_ABI const_local_iterator begin(size_type __n) const { return __table_.cbegin(__n); }
2177 _LIBCPP_HIDE_FROM_ABI const_local_iterator end(size_type __n) const { return __table_.cend(__n); }
2178 _LIBCPP_HIDE_FROM_ABI const_local_iterator cbegin(size_type __n) const { return __table_.cbegin(__n); }
2179 _LIBCPP_HIDE_FROM_ABI const_local_iterator cend(size_type __n) const { return __table_.cend(__n); }
2180
2181 _LIBCPP_HIDE_FROM_ABI float load_factor() const _NOEXCEPT { return __table_.load_factor(); }
2182 _LIBCPP_HIDE_FROM_ABI float max_load_factor() const _NOEXCEPT { return __table_.max_load_factor(); }
2183 _LIBCPP_HIDE_FROM_ABI void max_load_factor(float __mlf) { __table_.max_load_factor(__mlf); }
2184 _LIBCPP_HIDE_FROM_ABI void rehash(size_type __n) { __table_.__rehash_multi(__n); }
2185 _LIBCPP_HIDE_FROM_ABI void reserve(size_type __n) { __table_.__reserve_multi(__n); }
2186};
2187
2188#if _LIBCPP_STD_VER >= 17
2189template <class _InputIterator,
2190 class _Hash = hash<__iter_key_type<_InputIterator>>,
2191 class _Pred = equal_to<__iter_key_type<_InputIterator>>,
2192 class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>,
2193 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
2194 class = enable_if_t<!__is_allocator<_Hash>::value>,
2195 class = enable_if_t<!is_integral<_Hash>::value>,
2196 class = enable_if_t<!__is_allocator<_Pred>::value>,
2197 class = enable_if_t<__is_allocator<_Allocator>::value>>
2198unordered_multimap(_InputIterator,
2199 _InputIterator,
2200 typename allocator_traits<_Allocator>::size_type = 0,
2201 _Hash = _Hash(),
2202 _Pred = _Pred(),
2203 _Allocator = _Allocator())
2204 -> unordered_multimap<__iter_key_type<_InputIterator>,
2205 __iter_mapped_type<_InputIterator>,
2206 _Hash,
2207 _Pred,
2208 _Allocator>;
2209
2210# if _LIBCPP_STD_VER >= 23
2211template <ranges::input_range _Range,
2212 class _Hash = hash<__range_key_type<_Range>>,
2213 class _Pred = equal_to<__range_key_type<_Range>>,
2214 class _Allocator = allocator<__range_to_alloc_type<_Range>>,
2215 class = enable_if_t<!__is_allocator<_Hash>::value>,
2216 class = enable_if_t<!is_integral<_Hash>::value>,
2217 class = enable_if_t<!__is_allocator<_Pred>::value>,
2218 class = enable_if_t<__is_allocator<_Allocator>::value>>
2219unordered_multimap(from_range_t,
2220 _Range&&,
2221 typename allocator_traits<_Allocator>::size_type = 0,
2222 _Hash = _Hash(),
2223 _Pred = _Pred(),
2224 _Allocator = _Allocator())
2225 -> unordered_multimap<__range_key_type<_Range>, __range_mapped_type<_Range>, _Hash, _Pred, _Allocator>;
2226# endif
2227
2228template <class _Key,
2229 class _Tp,
2230 class _Hash = hash<remove_const_t<_Key>>,
2231 class _Pred = equal_to<remove_const_t<_Key>>,
2232 class _Allocator = allocator<pair<const _Key, _Tp>>,
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<_Pred>::value>,
2236 class = enable_if_t<__is_allocator<_Allocator>::value>>
2237unordered_multimap(
2238 initializer_list<pair<_Key, _Tp>>,
2239 typename allocator_traits<_Allocator>::size_type = 0,
2240 _Hash = _Hash(),
2241 _Pred = _Pred(),
2242 _Allocator = _Allocator()) -> unordered_multimap<remove_const_t<_Key>, _Tp, _Hash, _Pred, _Allocator>;
2243
2244template <class _InputIterator,
2245 class _Allocator,
2246 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
2247 class = enable_if_t<__is_allocator<_Allocator>::value>>
2248unordered_multimap(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Allocator)
2249 -> unordered_multimap<__iter_key_type<_InputIterator>,
2250 __iter_mapped_type<_InputIterator>,
2251 hash<__iter_key_type<_InputIterator>>,
2252 equal_to<__iter_key_type<_InputIterator>>,
2253 _Allocator>;
2254
2255template <class _InputIterator,
2256 class _Allocator,
2257 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
2258 class = enable_if_t<__is_allocator<_Allocator>::value>>
2259unordered_multimap(_InputIterator, _InputIterator, _Allocator)
2260 -> unordered_multimap<__iter_key_type<_InputIterator>,
2261 __iter_mapped_type<_InputIterator>,
2262 hash<__iter_key_type<_InputIterator>>,
2263 equal_to<__iter_key_type<_InputIterator>>,
2264 _Allocator>;
2265
2266template <class _InputIterator,
2267 class _Hash,
2268 class _Allocator,
2269 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
2270 class = enable_if_t<!__is_allocator<_Hash>::value>,
2271 class = enable_if_t<!is_integral<_Hash>::value>,
2272 class = enable_if_t<__is_allocator<_Allocator>::value>>
2273unordered_multimap(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
2274 -> unordered_multimap<__iter_key_type<_InputIterator>,
2275 __iter_mapped_type<_InputIterator>,
2276 _Hash,
2277 equal_to<__iter_key_type<_InputIterator>>,
2278 _Allocator>;
2279
2280# if _LIBCPP_STD_VER >= 23
2281
2282template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
2283unordered_multimap(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Allocator)
2284 -> unordered_multimap<__range_key_type<_Range>,
2285 __range_mapped_type<_Range>,
2286 hash<__range_key_type<_Range>>,
2287 equal_to<__range_key_type<_Range>>,
2288 _Allocator>;
2289
2290template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
2291unordered_multimap(from_range_t, _Range&&, _Allocator)
2292 -> unordered_multimap<__range_key_type<_Range>,
2293 __range_mapped_type<_Range>,
2294 hash<__range_key_type<_Range>>,
2295 equal_to<__range_key_type<_Range>>,
2296 _Allocator>;
2297
2298template <ranges::input_range _Range,
2299 class _Hash,
2300 class _Allocator,
2301 class = enable_if_t<!__is_allocator<_Hash>::value>,
2302 class = enable_if_t<!is_integral<_Hash>::value>,
2303 class = enable_if_t<__is_allocator<_Allocator>::value>>
2304unordered_multimap(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
2305 -> unordered_multimap<__range_key_type<_Range>,
2306 __range_mapped_type<_Range>,
2307 _Hash,
2308 equal_to<__range_key_type<_Range>>,
2309 _Allocator>;
2310
2311# endif
2312
2313template <class _Key, class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
2314unordered_multimap(initializer_list<pair<_Key, _Tp>>, typename allocator_traits<_Allocator>::size_type, _Allocator)
2315 -> unordered_multimap<remove_const_t<_Key>,
2316 _Tp,
2317 hash<remove_const_t<_Key>>,
2318 equal_to<remove_const_t<_Key>>,
2319 _Allocator>;
2320
2321template <class _Key, class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
2322unordered_multimap(initializer_list<pair<_Key, _Tp>>, _Allocator)
2323 -> unordered_multimap<remove_const_t<_Key>,
2324 _Tp,
2325 hash<remove_const_t<_Key>>,
2326 equal_to<remove_const_t<_Key>>,
2327 _Allocator>;
2328
2329template <class _Key,
2330 class _Tp,
2331 class _Hash,
2332 class _Allocator,
2333 class = enable_if_t<!__is_allocator<_Hash>::value>,
2334 class = enable_if_t<!is_integral<_Hash>::value>,
2335 class = enable_if_t<__is_allocator<_Allocator>::value>>
2336unordered_multimap(
2337 initializer_list<pair<_Key, _Tp>>, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
2338 -> unordered_multimap<remove_const_t<_Key>, _Tp, _Hash, equal_to<remove_const_t<_Key>>, _Allocator>;
2339#endif
2340
2341template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2342unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2343 size_type __n, const hasher& __hf, const key_equal& __eql)
2344 : __table_(__hf, __eql) {
2345 __table_.__rehash_multi(__n);
2346}
2347
2348template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2349unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2350 size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
2351 : __table_(__hf, __eql, typename __table::allocator_type(__a)) {
2352 __table_.__rehash_multi(__n);
2353}
2354
2355template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2356template <class _InputIterator>
2357unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(_InputIterator __first, _InputIterator __last) {
2358 insert(__first, __last);
2359}
2360
2361template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2362template <class _InputIterator>
2363unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2364 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql)
2365 : __table_(__hf, __eql) {
2366 __table_.__rehash_multi(__n);
2367 insert(__first, __last);
2368}
2369
2370template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2371template <class _InputIterator>
2372unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2373 _InputIterator __first,
2374 _InputIterator __last,
2375 size_type __n,
2376 const hasher& __hf,
2377 const key_equal& __eql,
2378 const allocator_type& __a)
2379 : __table_(__hf, __eql, typename __table::allocator_type(__a)) {
2380 __table_.__rehash_multi(__n);
2381 insert(__first, __last);
2382}
2383
2384template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2385inline unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(const allocator_type& __a)
2386 : __table_(typename __table::allocator_type(__a)) {}
2387
2388template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2389unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(const unordered_multimap& __u)
2390 : __table_(__u.__table_) {
2391 __table_.__rehash_multi(__u.bucket_count());
2392 insert(__u.begin(), __u.end());
2393}
2394
2395template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2396unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2397 const unordered_multimap& __u, const allocator_type& __a)
2398 : __table_(__u.__table_, typename __table::allocator_type(__a)) {
2399 __table_.__rehash_multi(__u.bucket_count());
2400 insert(__u.begin(), __u.end());
2401}
2402
2403#ifndef _LIBCPP_CXX03_LANG
2404
2405template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2406inline unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(unordered_multimap&& __u)
2407 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
2408 : __table_(std::move(__u.__table_)) {}
2409
2410template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2411unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2412 unordered_multimap&& __u, const allocator_type& __a)
2413 : __table_(std::move(__u.__table_), typename __table::allocator_type(__a)) {
2414 if (__a != __u.get_allocator()) {
2415 iterator __i = __u.begin();
2416 while (__u.size() != 0) {
2417 __table_.__insert_multi(__u.__table_.remove((__i++).__i_)->__get_value().__move());
2418 }
2419 }
2420}
2421
2422template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2423unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(initializer_list<value_type> __il) {
2424 insert(__il.begin(), __il.end());
2425}
2426
2427template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2428unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2429 initializer_list<value_type> __il, size_type __n, const hasher& __hf, const key_equal& __eql)
2430 : __table_(__hf, __eql) {
2431 __table_.__rehash_multi(__n);
2432 insert(__il.begin(), __il.end());
2433}
2434
2435template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2436unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2437 initializer_list<value_type> __il,
2438 size_type __n,
2439 const hasher& __hf,
2440 const key_equal& __eql,
2441 const allocator_type& __a)
2442 : __table_(__hf, __eql, typename __table::allocator_type(__a)) {
2443 __table_.__rehash_multi(__n);
2444 insert(__il.begin(), __il.end());
2445}
2446
2447template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2448inline unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
2449unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_multimap&& __u)
2450 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) {
2451 __table_ = std::move(__u.__table_);
2452 return *this;
2453}
2454
2455template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2456inline unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
2457unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(initializer_list<value_type> __il) {
2458 __table_.__assign_multi(__il.begin(), __il.end());
2459 return *this;
2460}
2461
2462#endif // _LIBCPP_CXX03_LANG
2463
2464template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2465template <class _InputIterator>
2466inline void unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) {
2467 for (; __first != __last; ++__first)
2468 __table_.__insert_multi(*__first);
2469}
2470
2471template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2472inline _LIBCPP_HIDE_FROM_ABI void
2473swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2474 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
2475 __x.swap(__y);
2476}
2477
2478#if _LIBCPP_STD_VER >= 20
2479template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc, class _Predicate>
2480inline _LIBCPP_HIDE_FROM_ABI typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::size_type
2481erase_if(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __c, _Predicate __pred) {
2482 return std::__libcpp_erase_if_container(__c, __pred);
2483}
2484#endif
2485
2486template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2487_LIBCPP_HIDE_FROM_ABI bool operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2488 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) {
2489 if (__x.size() != __y.size())
2490 return false;
2491 typedef typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator const_iterator;
2492 typedef pair<const_iterator, const_iterator> _EqRng;
2493 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) {
2494 _EqRng __xeq = __x.equal_range(__i->first);
2495 _EqRng __yeq = __y.equal_range(__i->first);
2496 if (std::distance(__xeq.first, __xeq.second) != std::distance(__yeq.first, __yeq.second) ||
2497 !std::is_permutation(__xeq.first, __xeq.second, __yeq.first))
2498 return false;
2499 __i = __xeq.second;
2500 }
2501 return true;
2502}
2503
2504#if _LIBCPP_STD_VER <= 17
2505
2506template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2507inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2508 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) {
2509 return !(__x == __y);
2510}
2511
2512#endif
2513
2514_LIBCPP_END_NAMESPACE_STD
2515
2516#if _LIBCPP_STD_VER >= 17
2517_LIBCPP_BEGIN_NAMESPACE_STD
2518namespace pmr {
2519template <class _KeyT, class _ValueT, class _HashT = std::hash<_KeyT>, class _PredT = std::equal_to<_KeyT>>
2520using unordered_map _LIBCPP_AVAILABILITY_PMR =
2521 std::unordered_map<_KeyT, _ValueT, _HashT, _PredT, polymorphic_allocator<std::pair<const _KeyT, _ValueT>>>;
2522
2523template <class _KeyT, class _ValueT, class _HashT = std::hash<_KeyT>, class _PredT = std::equal_to<_KeyT>>
2524using unordered_multimap _LIBCPP_AVAILABILITY_PMR =
2525 std::unordered_multimap<_KeyT, _ValueT, _HashT, _PredT, polymorphic_allocator<std::pair<const _KeyT, _ValueT>>>;
2526} // namespace pmr
2527_LIBCPP_END_NAMESPACE_STD
2528#endif
2529
2530_LIBCPP_POP_MACROS
2531
2532#if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
2533# include <algorithm>
2534# include <bit>
2535# include <concepts>
2536# include <cstdlib>
2537# include <iterator>
2538# include <type_traits>
2539#endif
2540
2541#endif // _LIBCPP_UNORDERED_MAP
2542