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