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