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