2 //===-------------------------- unordered_map -----------------------------===//
4 // The LLVM Compiler Infrastructure
6 // This file is dual licensed under the MIT and the University of Illinois Open
7 // Source Licenses. See LICENSE.TXT for details.
9 //===----------------------------------------------------------------------===//
11 #ifndef _LIBCPP_UNORDERED_MAP
12 #define _LIBCPP_UNORDERED_MAP
16 unordered_map synopsis
18 #include <initializer_list>
23 template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
24 class Alloc = allocator<pair<const Key, T>>>
30 typedef T mapped_type;
32 typedef Pred key_equal;
33 typedef Alloc allocator_type;
34 typedef pair<const key_type, mapped_type> value_type;
35 typedef value_type& reference;
36 typedef const value_type& const_reference;
37 typedef typename allocator_traits<allocator_type>::pointer pointer;
38 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
39 typedef typename allocator_traits<allocator_type>::size_type size_type;
40 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
42 typedef /unspecified/ iterator;
43 typedef /unspecified/ const_iterator;
44 typedef /unspecified/ local_iterator;
45 typedef /unspecified/ const_local_iterator;
49 is_nothrow_default_constructible<hasher>::value &&
50 is_nothrow_default_constructible<key_equal>::value &&
51 is_nothrow_default_constructible<allocator_type>::value);
52 explicit unordered_map(size_type n, const hasher& hf = hasher(),
53 const key_equal& eql = key_equal(),
54 const allocator_type& a = allocator_type());
55 template <class InputIterator>
56 unordered_map(InputIterator f, InputIterator l,
57 size_type n = 0, const hasher& hf = hasher(),
58 const key_equal& eql = key_equal(),
59 const allocator_type& a = allocator_type());
60 explicit unordered_map(const allocator_type&);
61 unordered_map(const unordered_map&);
62 unordered_map(const unordered_map&, const Allocator&);
63 unordered_map(unordered_map&&)
65 is_nothrow_move_constructible<hasher>::value &&
66 is_nothrow_move_constructible<key_equal>::value &&
67 is_nothrow_move_constructible<allocator_type>::value);
68 unordered_map(unordered_map&&, const Allocator&);
69 unordered_map(initializer_list<value_type>, size_type n = 0,
70 const hasher& hf = hasher(), const key_equal& eql = key_equal(),
71 const allocator_type& a = allocator_type());
72 unordered_map(size_type n, const allocator_type& a)
73 : unordered_map(n, hasher(), key_equal(), a) {} // C++14
74 unordered_map(size_type n, const hasher& hf, const allocator_type& a)
75 : unordered_map(n, hf, key_equal(), a) {} // C++14
76 template <class InputIterator>
77 unordered_map(InputIterator f, InputIterator l, size_type n, const allocator_type& a)
78 : unordered_map(f, l, n, hasher(), key_equal(), a) {} // C++14
79 template <class InputIterator>
80 unordered_map(InputIterator f, InputIterator l, size_type n, const hasher& hf,
81 const allocator_type& a)
82 : unordered_map(f, l, n, hf, key_equal(), a) {} // C++14
83 unordered_map(initializer_list<value_type> il, size_type n, const allocator_type& a)
84 : unordered_map(il, n, hasher(), key_equal(), a) {} // C++14
85 unordered_map(initializer_list<value_type> il, size_type n, const hasher& hf,
86 const allocator_type& a)
87 : unordered_map(il, n, hf, key_equal(), a) {} // C++14
89 unordered_map& operator=(const unordered_map&);
90 unordered_map& operator=(unordered_map&&)
92 allocator_type::propagate_on_container_move_assignment::value &&
93 is_nothrow_move_assignable<allocator_type>::value &&
94 is_nothrow_move_assignable<hasher>::value &&
95 is_nothrow_move_assignable<key_equal>::value);
96 unordered_map& operator=(initializer_list<value_type>);
98 allocator_type get_allocator() const noexcept;
100 bool empty() const noexcept;
101 size_type size() const noexcept;
102 size_type max_size() const noexcept;
104 iterator begin() noexcept;
105 iterator end() noexcept;
106 const_iterator begin() const noexcept;
107 const_iterator end() const noexcept;
108 const_iterator cbegin() const noexcept;
109 const_iterator cend() const noexcept;
111 template <class... Args>
112 pair<iterator, bool> emplace(Args&&... args);
113 template <class... Args>
114 iterator emplace_hint(const_iterator position, Args&&... args);
115 pair<iterator, bool> insert(const value_type& obj);
117 pair<iterator, bool> insert(P&& obj);
118 iterator insert(const_iterator hint, const value_type& obj);
120 iterator insert(const_iterator hint, P&& obj);
121 template <class InputIterator>
122 void insert(InputIterator first, InputIterator last);
123 void insert(initializer_list<value_type>);
125 template <class... Args>
126 pair<iterator, bool> try_emplace(const key_type& k, Args&&... args); // C++17
127 template <class... Args>
128 pair<iterator, bool> try_emplace(key_type&& k, Args&&... args); // C++17
129 template <class... Args>
130 iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args); // C++17
131 template <class... Args>
132 iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args); // C++17
134 pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj); // C++17
136 pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj); // C++17
138 iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj); // C++17
140 iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj); // C++17
142 iterator erase(const_iterator position);
143 iterator erase(iterator position); // C++14
144 size_type erase(const key_type& k);
145 iterator erase(const_iterator first, const_iterator last);
146 void clear() noexcept;
148 void swap(unordered_map&)
150 (!allocator_type::propagate_on_container_swap::value ||
151 __is_nothrow_swappable<allocator_type>::value) &&
152 __is_nothrow_swappable<hasher>::value &&
153 __is_nothrow_swappable<key_equal>::value);
155 hasher hash_function() const;
156 key_equal key_eq() const;
158 iterator find(const key_type& k);
159 const_iterator find(const key_type& k) const;
160 size_type count(const key_type& k) const;
161 pair<iterator, iterator> equal_range(const key_type& k);
162 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
164 mapped_type& operator[](const key_type& k);
165 mapped_type& operator[](key_type&& k);
167 mapped_type& at(const key_type& k);
168 const mapped_type& at(const key_type& k) const;
170 size_type bucket_count() const noexcept;
171 size_type max_bucket_count() const noexcept;
173 size_type bucket_size(size_type n) const;
174 size_type bucket(const key_type& k) const;
176 local_iterator begin(size_type n);
177 local_iterator end(size_type n);
178 const_local_iterator begin(size_type n) const;
179 const_local_iterator end(size_type n) const;
180 const_local_iterator cbegin(size_type n) const;
181 const_local_iterator cend(size_type n) const;
183 float load_factor() const noexcept;
184 float max_load_factor() const noexcept;
185 void max_load_factor(float z);
186 void rehash(size_type n);
187 void reserve(size_type n);
190 template <class Key, class T, class Hash, class Pred, class Alloc>
191 void swap(unordered_map<Key, T, Hash, Pred, Alloc>& x,
192 unordered_map<Key, T, Hash, Pred, Alloc>& y)
193 noexcept(noexcept(x.swap(y)));
195 template <class Key, class T, class Hash, class Pred, class Alloc>
197 operator==(const unordered_map<Key, T, Hash, Pred, Alloc>& x,
198 const unordered_map<Key, T, Hash, Pred, Alloc>& y);
200 template <class Key, class T, class Hash, class Pred, class Alloc>
202 operator!=(const unordered_map<Key, T, Hash, Pred, Alloc>& x,
203 const unordered_map<Key, T, Hash, Pred, Alloc>& y);
205 template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
206 class Alloc = allocator<pair<const Key, T>>>
207 class unordered_multimap
211 typedef Key key_type;
212 typedef T mapped_type;
214 typedef Pred key_equal;
215 typedef Alloc allocator_type;
216 typedef pair<const key_type, mapped_type> value_type;
217 typedef value_type& reference;
218 typedef const value_type& const_reference;
219 typedef typename allocator_traits<allocator_type>::pointer pointer;
220 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
221 typedef typename allocator_traits<allocator_type>::size_type size_type;
222 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
224 typedef /unspecified/ iterator;
225 typedef /unspecified/ const_iterator;
226 typedef /unspecified/ local_iterator;
227 typedef /unspecified/ const_local_iterator;
231 is_nothrow_default_constructible<hasher>::value &&
232 is_nothrow_default_constructible<key_equal>::value &&
233 is_nothrow_default_constructible<allocator_type>::value);
234 explicit unordered_multimap(size_type n, const hasher& hf = hasher(),
235 const key_equal& eql = key_equal(),
236 const allocator_type& a = allocator_type());
237 template <class InputIterator>
238 unordered_multimap(InputIterator f, InputIterator l,
239 size_type n = 0, const hasher& hf = hasher(),
240 const key_equal& eql = key_equal(),
241 const allocator_type& a = allocator_type());
242 explicit unordered_multimap(const allocator_type&);
243 unordered_multimap(const unordered_multimap&);
244 unordered_multimap(const unordered_multimap&, const Allocator&);
245 unordered_multimap(unordered_multimap&&)
247 is_nothrow_move_constructible<hasher>::value &&
248 is_nothrow_move_constructible<key_equal>::value &&
249 is_nothrow_move_constructible<allocator_type>::value);
250 unordered_multimap(unordered_multimap&&, const Allocator&);
251 unordered_multimap(initializer_list<value_type>, size_type n = 0,
252 const hasher& hf = hasher(), const key_equal& eql = key_equal(),
253 const allocator_type& a = allocator_type());
254 unordered_multimap(size_type n, const allocator_type& a)
255 : unordered_multimap(n, hasher(), key_equal(), a) {} // C++14
256 unordered_multimap(size_type n, const hasher& hf, const allocator_type& a)
257 : unordered_multimap(n, hf, key_equal(), a) {} // C++14
258 template <class InputIterator>
259 unordered_multimap(InputIterator f, InputIterator l, size_type n, const allocator_type& a)
260 : unordered_multimap(f, l, n, hasher(), key_equal(), a) {} // C++14
261 template <class InputIterator>
262 unordered_multimap(InputIterator f, InputIterator l, size_type n, const hasher& hf,
263 const allocator_type& a)
264 : unordered_multimap(f, l, n, hf, key_equal(), a) {} // C++14
265 unordered_multimap(initializer_list<value_type> il, size_type n, const allocator_type& a)
266 : unordered_multimap(il, n, hasher(), key_equal(), a) {} // C++14
267 unordered_multimap(initializer_list<value_type> il, size_type n, const hasher& hf,
268 const allocator_type& a)
269 : unordered_multimap(il, n, hf, key_equal(), a) {} // C++14
270 ~unordered_multimap();
271 unordered_multimap& operator=(const unordered_multimap&);
272 unordered_multimap& operator=(unordered_multimap&&)
274 allocator_type::propagate_on_container_move_assignment::value &&
275 is_nothrow_move_assignable<allocator_type>::value &&
276 is_nothrow_move_assignable<hasher>::value &&
277 is_nothrow_move_assignable<key_equal>::value);
278 unordered_multimap& operator=(initializer_list<value_type>);
280 allocator_type get_allocator() const noexcept;
282 bool empty() const noexcept;
283 size_type size() const noexcept;
284 size_type max_size() const noexcept;
286 iterator begin() noexcept;
287 iterator end() noexcept;
288 const_iterator begin() const noexcept;
289 const_iterator end() const noexcept;
290 const_iterator cbegin() const noexcept;
291 const_iterator cend() const noexcept;
293 template <class... Args>
294 iterator emplace(Args&&... args);
295 template <class... Args>
296 iterator emplace_hint(const_iterator position, Args&&... args);
297 iterator insert(const value_type& obj);
299 iterator insert(P&& obj);
300 iterator insert(const_iterator hint, const value_type& obj);
302 iterator insert(const_iterator hint, P&& obj);
303 template <class InputIterator>
304 void insert(InputIterator first, InputIterator last);
305 void insert(initializer_list<value_type>);
307 iterator erase(const_iterator position);
308 iterator erase(iterator position); // C++14
309 size_type erase(const key_type& k);
310 iterator erase(const_iterator first, const_iterator last);
311 void clear() noexcept;
313 void swap(unordered_multimap&)
315 (!allocator_type::propagate_on_container_swap::value ||
316 __is_nothrow_swappable<allocator_type>::value) &&
317 __is_nothrow_swappable<hasher>::value &&
318 __is_nothrow_swappable<key_equal>::value);
320 hasher hash_function() const;
321 key_equal key_eq() const;
323 iterator find(const key_type& k);
324 const_iterator find(const key_type& k) const;
325 size_type count(const key_type& k) const;
326 pair<iterator, iterator> equal_range(const key_type& k);
327 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
329 size_type bucket_count() const noexcept;
330 size_type max_bucket_count() const noexcept;
332 size_type bucket_size(size_type n) const;
333 size_type bucket(const key_type& k) const;
335 local_iterator begin(size_type n);
336 local_iterator end(size_type n);
337 const_local_iterator begin(size_type n) const;
338 const_local_iterator end(size_type n) const;
339 const_local_iterator cbegin(size_type n) const;
340 const_local_iterator cend(size_type n) const;
342 float load_factor() const noexcept;
343 float max_load_factor() const noexcept;
344 void max_load_factor(float z);
345 void rehash(size_type n);
346 void reserve(size_type n);
349 template <class Key, class T, class Hash, class Pred, class Alloc>
350 void swap(unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
351 unordered_multimap<Key, T, Hash, Pred, Alloc>& y)
352 noexcept(noexcept(x.swap(y)));
354 template <class Key, class T, class Hash, class Pred, class Alloc>
356 operator==(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
357 const unordered_multimap<Key, T, Hash, Pred, Alloc>& y);
359 template <class Key, class T, class Hash, class Pred, class Alloc>
361 operator!=(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
362 const unordered_multimap<Key, T, Hash, Pred, Alloc>& y);
369 #include <__hash_table>
370 #include <functional>
375 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
376 #pragma GCC system_header
379 _LIBCPP_BEGIN_NAMESPACE_STD
381 template <class _Key, class _Cp, class _Hash,
382 bool = is_empty<_Hash>::value && !__libcpp_is_final<_Hash>::value
384 class __unordered_map_hasher
388 _LIBCPP_INLINE_VISIBILITY
389 __unordered_map_hasher()
390 _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value)
392 _LIBCPP_INLINE_VISIBILITY
393 __unordered_map_hasher(const _Hash& __h)
394 _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value)
396 _LIBCPP_INLINE_VISIBILITY
397 const _Hash& hash_function() const _NOEXCEPT {return *this;}
398 _LIBCPP_INLINE_VISIBILITY
399 size_t operator()(const _Cp& __x) const
400 {return static_cast<const _Hash&>(*this)(__x.__cc.first);}
401 _LIBCPP_INLINE_VISIBILITY
402 size_t operator()(const _Key& __x) const
403 {return static_cast<const _Hash&>(*this)(__x);}
404 void swap(__unordered_map_hasher&__y)
405 _NOEXCEPT_(__is_nothrow_swappable<_Hash>::value)
408 swap(static_cast<const _Hash&>(*this), static_cast<const _Hash&>(__y));
412 template <class _Key, class _Cp, class _Hash>
413 class __unordered_map_hasher<_Key, _Cp, _Hash, false>
418 _LIBCPP_INLINE_VISIBILITY
419 __unordered_map_hasher()
420 _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value)
422 _LIBCPP_INLINE_VISIBILITY
423 __unordered_map_hasher(const _Hash& __h)
424 _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value)
426 _LIBCPP_INLINE_VISIBILITY
427 const _Hash& hash_function() const _NOEXCEPT {return __hash_;}
428 _LIBCPP_INLINE_VISIBILITY
429 size_t operator()(const _Cp& __x) const
430 {return __hash_(__x.__cc.first);}
431 _LIBCPP_INLINE_VISIBILITY
432 size_t operator()(const _Key& __x) const
433 {return __hash_(__x);}
434 void swap(__unordered_map_hasher&__y)
435 _NOEXCEPT_(__is_nothrow_swappable<_Hash>::value)
438 swap(__hash_, __y.__hash_);
442 template <class _Key, class _Cp, class _Hash, bool __b>
443 inline _LIBCPP_INLINE_VISIBILITY
445 swap(__unordered_map_hasher<_Key, _Cp, _Hash, __b>& __x,
446 __unordered_map_hasher<_Key, _Cp, _Hash, __b>& __y)
447 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
452 template <class _Key, class _Cp, class _Pred,
453 bool = is_empty<_Pred>::value && !__libcpp_is_final<_Pred>::value
455 class __unordered_map_equal
459 _LIBCPP_INLINE_VISIBILITY
460 __unordered_map_equal()
461 _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value)
463 _LIBCPP_INLINE_VISIBILITY
464 __unordered_map_equal(const _Pred& __p)
465 _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value)
467 _LIBCPP_INLINE_VISIBILITY
468 const _Pred& key_eq() const _NOEXCEPT {return *this;}
469 _LIBCPP_INLINE_VISIBILITY
470 bool operator()(const _Cp& __x, const _Cp& __y) const
471 {return static_cast<const _Pred&>(*this)(__x.__cc.first, __y.__cc.first);}
472 _LIBCPP_INLINE_VISIBILITY
473 bool operator()(const _Cp& __x, const _Key& __y) const
474 {return static_cast<const _Pred&>(*this)(__x.__cc.first, __y);}
475 _LIBCPP_INLINE_VISIBILITY
476 bool operator()(const _Key& __x, const _Cp& __y) const
477 {return static_cast<const _Pred&>(*this)(__x, __y.__cc.first);}
478 void swap(__unordered_map_equal&__y)
479 _NOEXCEPT_(__is_nothrow_swappable<_Pred>::value)
482 swap(static_cast<const _Pred&>(*this), static_cast<const _Pred&>(__y));
486 template <class _Key, class _Cp, class _Pred>
487 class __unordered_map_equal<_Key, _Cp, _Pred, false>
492 _LIBCPP_INLINE_VISIBILITY
493 __unordered_map_equal()
494 _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value)
496 _LIBCPP_INLINE_VISIBILITY
497 __unordered_map_equal(const _Pred& __p)
498 _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value)
500 _LIBCPP_INLINE_VISIBILITY
501 const _Pred& key_eq() const _NOEXCEPT {return __pred_;}
502 _LIBCPP_INLINE_VISIBILITY
503 bool operator()(const _Cp& __x, const _Cp& __y) const
504 {return __pred_(__x.__cc.first, __y.__cc.first);}
505 _LIBCPP_INLINE_VISIBILITY
506 bool operator()(const _Cp& __x, const _Key& __y) const
507 {return __pred_(__x.__cc.first, __y);}
508 _LIBCPP_INLINE_VISIBILITY
509 bool operator()(const _Key& __x, const _Cp& __y) const
510 {return __pred_(__x, __y.__cc.first);}
511 void swap(__unordered_map_equal&__y)
512 _NOEXCEPT_(__is_nothrow_swappable<_Pred>::value)
515 swap(__pred_, __y.__pred_);
519 template <class _Key, class _Cp, class _Pred, bool __b>
520 inline _LIBCPP_INLINE_VISIBILITY
522 swap(__unordered_map_equal<_Key, _Cp, _Pred, __b>& __x,
523 __unordered_map_equal<_Key, _Cp, _Pred, __b>& __y)
524 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
529 template <class _Alloc>
530 class __hash_map_node_destructor
532 typedef _Alloc allocator_type;
533 typedef allocator_traits<allocator_type> __alloc_traits;
534 typedef typename __alloc_traits::value_type::value_type value_type;
536 typedef typename __alloc_traits::pointer pointer;
538 typedef typename value_type::value_type::first_type first_type;
539 typedef typename value_type::value_type::second_type second_type;
541 allocator_type& __na_;
543 __hash_map_node_destructor& operator=(const __hash_map_node_destructor&);
546 bool __first_constructed;
547 bool __second_constructed;
549 _LIBCPP_INLINE_VISIBILITY
550 explicit __hash_map_node_destructor(allocator_type& __na) _NOEXCEPT
552 __first_constructed(false),
553 __second_constructed(false)
556 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
557 _LIBCPP_INLINE_VISIBILITY
558 __hash_map_node_destructor(__hash_node_destructor<allocator_type>&& __x)
561 __first_constructed(__x.__value_constructed),
562 __second_constructed(__x.__value_constructed)
564 __x.__value_constructed = false;
566 #else // _LIBCPP_HAS_NO_RVALUE_REFERENCES
567 _LIBCPP_INLINE_VISIBILITY
568 __hash_map_node_destructor(const __hash_node_destructor<allocator_type>& __x)
570 __first_constructed(__x.__value_constructed),
571 __second_constructed(__x.__value_constructed)
573 const_cast<bool&>(__x.__value_constructed) = false;
575 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
577 _LIBCPP_INLINE_VISIBILITY
578 void operator()(pointer __p) _NOEXCEPT
580 if (__second_constructed)
581 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.second));
582 if (__first_constructed)
583 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.first));
585 __alloc_traits::deallocate(__na_, __p, 1);
589 #if __cplusplus >= 201103L
591 template <class _Key, class _Tp>
592 union __hash_value_type
594 typedef _Key key_type;
595 typedef _Tp mapped_type;
596 typedef pair<const key_type, mapped_type> value_type;
597 typedef pair<key_type, mapped_type> __nc_value_type;
600 __nc_value_type __nc;
602 template <class ..._Args>
603 _LIBCPP_INLINE_VISIBILITY
604 __hash_value_type(_Args&& ...__args)
605 : __cc(std::forward<_Args>(__args)...) {}
607 _LIBCPP_INLINE_VISIBILITY
608 __hash_value_type(const __hash_value_type& __v)
611 _LIBCPP_INLINE_VISIBILITY
612 __hash_value_type(__hash_value_type&& __v)
613 : __nc(_VSTD::move(__v.__nc)) {}
615 _LIBCPP_INLINE_VISIBILITY
616 __hash_value_type& operator=(const __hash_value_type& __v)
617 {__nc = __v.__cc; return *this;}
619 _LIBCPP_INLINE_VISIBILITY
620 __hash_value_type& operator=(__hash_value_type&& __v)
621 {__nc = _VSTD::move(__v.__nc); return *this;}
623 _LIBCPP_INLINE_VISIBILITY
624 ~__hash_value_type() {__cc.~value_type();}
629 template <class _Key, class _Tp>
630 struct __hash_value_type
632 typedef _Key key_type;
633 typedef _Tp mapped_type;
634 typedef pair<const key_type, mapped_type> value_type;
638 _LIBCPP_INLINE_VISIBILITY
639 __hash_value_type() {}
642 _LIBCPP_INLINE_VISIBILITY
643 __hash_value_type(const _A0& __a0)
646 template <class _A0, class _A1>
647 _LIBCPP_INLINE_VISIBILITY
648 __hash_value_type(const _A0& __a0, const _A1& __a1)
649 : __cc(__a0, __a1) {}
654 template <class _HashIterator>
655 class _LIBCPP_TYPE_VIS_ONLY __hash_map_iterator
659 typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits;
660 typedef const typename _HashIterator::value_type::value_type::first_type key_type;
661 typedef typename _HashIterator::value_type::value_type::second_type mapped_type;
663 typedef forward_iterator_tag iterator_category;
664 typedef pair<key_type, mapped_type> value_type;
665 typedef typename _HashIterator::difference_type difference_type;
666 typedef value_type& reference;
667 typedef typename __pointer_traits::template
668 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
671 rebind<value_type>::other
675 _LIBCPP_INLINE_VISIBILITY
676 __hash_map_iterator() _NOEXCEPT {}
678 _LIBCPP_INLINE_VISIBILITY
679 __hash_map_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
681 _LIBCPP_INLINE_VISIBILITY
682 reference operator*() const {return __i_->__cc;}
683 _LIBCPP_INLINE_VISIBILITY
684 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);}
686 _LIBCPP_INLINE_VISIBILITY
687 __hash_map_iterator& operator++() {++__i_; return *this;}
688 _LIBCPP_INLINE_VISIBILITY
689 __hash_map_iterator operator++(int)
691 __hash_map_iterator __t(*this);
696 friend _LIBCPP_INLINE_VISIBILITY
697 bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y)
698 {return __x.__i_ == __y.__i_;}
699 friend _LIBCPP_INLINE_VISIBILITY
700 bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y)
701 {return __x.__i_ != __y.__i_;}
703 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map;
704 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap;
705 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator;
706 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator;
707 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator;
710 template <class _HashIterator>
711 class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator
715 typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits;
716 typedef const typename _HashIterator::value_type::value_type::first_type key_type;
717 typedef typename _HashIterator::value_type::value_type::second_type mapped_type;
719 typedef forward_iterator_tag iterator_category;
720 typedef pair<key_type, mapped_type> value_type;
721 typedef typename _HashIterator::difference_type difference_type;
722 typedef const value_type& reference;
723 typedef typename __pointer_traits::template
724 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
725 rebind<const value_type>
727 rebind<const value_type>::other
731 _LIBCPP_INLINE_VISIBILITY
732 __hash_map_const_iterator() _NOEXCEPT {}
734 _LIBCPP_INLINE_VISIBILITY
735 __hash_map_const_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
736 _LIBCPP_INLINE_VISIBILITY
737 __hash_map_const_iterator(
738 __hash_map_iterator<typename _HashIterator::__non_const_iterator> __i)
742 _LIBCPP_INLINE_VISIBILITY
743 reference operator*() const {return __i_->__cc;}
744 _LIBCPP_INLINE_VISIBILITY
745 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);}
747 _LIBCPP_INLINE_VISIBILITY
748 __hash_map_const_iterator& operator++() {++__i_; return *this;}
749 _LIBCPP_INLINE_VISIBILITY
750 __hash_map_const_iterator operator++(int)
752 __hash_map_const_iterator __t(*this);
757 friend _LIBCPP_INLINE_VISIBILITY
758 bool operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)
759 {return __x.__i_ == __y.__i_;}
760 friend _LIBCPP_INLINE_VISIBILITY
761 bool operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)
762 {return __x.__i_ != __y.__i_;}
764 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map;
765 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap;
766 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator;
767 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator;
770 template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
771 class _Alloc = allocator<pair<const _Key, _Tp> > >
772 class _LIBCPP_TYPE_VIS_ONLY unordered_map
776 typedef _Key key_type;
777 typedef _Tp mapped_type;
778 typedef _Hash hasher;
779 typedef _Pred key_equal;
780 typedef _Alloc allocator_type;
781 typedef pair<const key_type, mapped_type> value_type;
782 typedef pair<key_type, mapped_type> __nc_value_type;
783 typedef value_type& reference;
784 typedef const value_type& const_reference;
785 static_assert((is_same<value_type, typename allocator_type::value_type>::value),
786 "Invalid allocator::value_type");
789 typedef __hash_value_type<key_type, mapped_type> __value_type;
790 typedef __unordered_map_hasher<key_type, __value_type, hasher> __hasher;
791 typedef __unordered_map_equal<key_type, __value_type, key_equal> __key_equal;
792 typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>,
793 __value_type>::type __allocator_type;
795 typedef __hash_table<__value_type, __hasher,
796 __key_equal, __allocator_type> __table;
800 typedef typename __table::__node_pointer __node_pointer;
801 typedef typename __table::__node_const_pointer __node_const_pointer;
802 typedef typename __table::__node_traits __node_traits;
803 typedef typename __table::__node_allocator __node_allocator;
804 typedef typename __table::__node __node;
805 typedef __hash_map_node_destructor<__node_allocator> _Dp;
806 typedef unique_ptr<__node, _Dp> __node_holder;
807 typedef allocator_traits<allocator_type> __alloc_traits;
809 typedef typename __alloc_traits::pointer pointer;
810 typedef typename __alloc_traits::const_pointer const_pointer;
811 typedef typename __alloc_traits::size_type size_type;
812 typedef typename __alloc_traits::difference_type difference_type;
814 typedef __hash_map_iterator<typename __table::iterator> iterator;
815 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
816 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
817 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
819 _LIBCPP_INLINE_VISIBILITY
821 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
823 #if _LIBCPP_DEBUG_LEVEL >= 2
824 __get_db()->__insert_c(this);
827 explicit unordered_map(size_type __n, const hasher& __hf = hasher(),
828 const key_equal& __eql = key_equal());
829 unordered_map(size_type __n, const hasher& __hf,
830 const key_equal& __eql,
831 const allocator_type& __a);
832 template <class _InputIterator>
833 unordered_map(_InputIterator __first, _InputIterator __last);
834 template <class _InputIterator>
835 unordered_map(_InputIterator __first, _InputIterator __last,
836 size_type __n, const hasher& __hf = hasher(),
837 const key_equal& __eql = key_equal());
838 template <class _InputIterator>
839 unordered_map(_InputIterator __first, _InputIterator __last,
840 size_type __n, const hasher& __hf,
841 const key_equal& __eql,
842 const allocator_type& __a);
843 explicit unordered_map(const allocator_type& __a);
844 unordered_map(const unordered_map& __u);
845 unordered_map(const unordered_map& __u, const allocator_type& __a);
846 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
847 unordered_map(unordered_map&& __u)
848 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
849 unordered_map(unordered_map&& __u, const allocator_type& __a);
850 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
851 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
852 unordered_map(initializer_list<value_type> __il);
853 unordered_map(initializer_list<value_type> __il, size_type __n,
854 const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
855 unordered_map(initializer_list<value_type> __il, size_type __n,
856 const hasher& __hf, const key_equal& __eql,
857 const allocator_type& __a);
858 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
859 #if _LIBCPP_STD_VER > 11
860 _LIBCPP_INLINE_VISIBILITY
861 unordered_map(size_type __n, const allocator_type& __a)
862 : unordered_map(__n, hasher(), key_equal(), __a) {}
863 _LIBCPP_INLINE_VISIBILITY
864 unordered_map(size_type __n, const hasher& __hf, const allocator_type& __a)
865 : unordered_map(__n, __hf, key_equal(), __a) {}
866 template <class _InputIterator>
867 _LIBCPP_INLINE_VISIBILITY
868 unordered_map(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a)
869 : unordered_map(__first, __last, __n, hasher(), key_equal(), __a) {}
870 template <class _InputIterator>
871 _LIBCPP_INLINE_VISIBILITY
872 unordered_map(_InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf,
873 const allocator_type& __a)
874 : unordered_map(__first, __last, __n, __hf, key_equal(), __a) {}
875 _LIBCPP_INLINE_VISIBILITY
876 unordered_map(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)
877 : unordered_map(__il, __n, hasher(), key_equal(), __a) {}
878 _LIBCPP_INLINE_VISIBILITY
879 unordered_map(initializer_list<value_type> __il, size_type __n, const hasher& __hf,
880 const allocator_type& __a)
881 : unordered_map(__il, __n, __hf, key_equal(), __a) {}
883 // ~unordered_map() = default;
884 _LIBCPP_INLINE_VISIBILITY
885 unordered_map& operator=(const unordered_map& __u)
887 #if __cplusplus >= 201103L
888 __table_ = __u.__table_;
892 __table_.hash_function() = __u.__table_.hash_function();
893 __table_.key_eq() = __u.__table_.key_eq();
894 __table_.max_load_factor() = __u.__table_.max_load_factor();
895 __table_.__copy_assign_alloc(__u.__table_);
896 insert(__u.begin(), __u.end());
901 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
902 unordered_map& operator=(unordered_map&& __u)
903 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
905 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
906 unordered_map& operator=(initializer_list<value_type> __il);
907 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
909 _LIBCPP_INLINE_VISIBILITY
910 allocator_type get_allocator() const _NOEXCEPT
911 {return allocator_type(__table_.__node_alloc());}
913 _LIBCPP_INLINE_VISIBILITY
914 bool empty() const _NOEXCEPT {return __table_.size() == 0;}
915 _LIBCPP_INLINE_VISIBILITY
916 size_type size() const _NOEXCEPT {return __table_.size();}
917 _LIBCPP_INLINE_VISIBILITY
918 size_type max_size() const _NOEXCEPT {return __table_.max_size();}
920 _LIBCPP_INLINE_VISIBILITY
921 iterator begin() _NOEXCEPT {return __table_.begin();}
922 _LIBCPP_INLINE_VISIBILITY
923 iterator end() _NOEXCEPT {return __table_.end();}
924 _LIBCPP_INLINE_VISIBILITY
925 const_iterator begin() const _NOEXCEPT {return __table_.begin();}
926 _LIBCPP_INLINE_VISIBILITY
927 const_iterator end() const _NOEXCEPT {return __table_.end();}
928 _LIBCPP_INLINE_VISIBILITY
929 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
930 _LIBCPP_INLINE_VISIBILITY
931 const_iterator cend() const _NOEXCEPT {return __table_.end();}
933 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
934 #ifndef _LIBCPP_HAS_NO_VARIADICS
936 template <class... _Args>
937 pair<iterator, bool> emplace(_Args&&... __args);
939 template <class... _Args>
940 _LIBCPP_INLINE_VISIBILITY
941 #if _LIBCPP_DEBUG_LEVEL >= 2
942 iterator emplace_hint(const_iterator __p, _Args&&... __args)
944 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
945 "unordered_map::emplace_hint(const_iterator, args...) called with an iterator not"
946 " referring to this unordered_map");
947 return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first;
950 iterator emplace_hint(const_iterator, _Args&&... __args)
951 {return emplace(_VSTD::forward<_Args>(__args)...).first;}
953 #endif // _LIBCPP_HAS_NO_VARIADICS
954 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
955 _LIBCPP_INLINE_VISIBILITY
956 pair<iterator, bool> insert(const value_type& __x)
957 {return __table_.__insert_unique(__x);}
958 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
960 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
961 _LIBCPP_INLINE_VISIBILITY
962 pair<iterator, bool> insert(_Pp&& __x)
963 {return __table_.__insert_unique(_VSTD::forward<_Pp>(__x));}
964 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
965 _LIBCPP_INLINE_VISIBILITY
966 #if _LIBCPP_DEBUG_LEVEL >= 2
967 iterator insert(const_iterator __p, const value_type& __x)
969 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
970 "unordered_map::insert(const_iterator, const value_type&) called with an iterator not"
971 " referring to this unordered_map");
972 return insert(__x).first;
975 iterator insert(const_iterator, const value_type& __x)
976 {return insert(__x).first;}
978 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
980 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
981 _LIBCPP_INLINE_VISIBILITY
982 #if _LIBCPP_DEBUG_LEVEL >= 2
983 iterator insert(const_iterator __p, _Pp&& __x)
985 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
986 "unordered_map::insert(const_iterator, value_type&&) called with an iterator not"
987 " referring to this unordered_map");
988 return insert(_VSTD::forward<_Pp>(__x)).first;
991 iterator insert(const_iterator, _Pp&& __x)
992 {return insert(_VSTD::forward<_Pp>(__x)).first;}
994 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
995 template <class _InputIterator>
996 void insert(_InputIterator __first, _InputIterator __last);
997 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
998 _LIBCPP_INLINE_VISIBILITY
999 void insert(initializer_list<value_type> __il)
1000 {insert(__il.begin(), __il.end());}
1001 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1003 #if _LIBCPP_STD_VER > 14
1004 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1005 #ifndef _LIBCPP_HAS_NO_VARIADICS
1006 template <class... _Args>
1007 _LIBCPP_INLINE_VISIBILITY
1008 pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args)
1010 iterator __p = __table_.find(__k);
1012 return _VSTD::make_pair(__p, false);
1014 return _VSTD::make_pair(
1016 _VSTD::piecewise_construct, _VSTD::forward_as_tuple(__k),
1017 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)),
1021 template <class... _Args>
1022 _LIBCPP_INLINE_VISIBILITY
1023 pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args)
1025 iterator __p = __table_.find(__k);
1027 return _VSTD::make_pair(__p, false);
1029 return _VSTD::make_pair(
1031 _VSTD::piecewise_construct, _VSTD::forward_as_tuple(_VSTD::move(__k)),
1032 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)),
1036 template <class... _Args>
1037 _LIBCPP_INLINE_VISIBILITY
1038 iterator try_emplace(const_iterator __h, const key_type& __k, _Args&&... __args)
1040 iterator __p = __table_.find(__k);
1044 return emplace_hint(__h,
1045 _VSTD::piecewise_construct, _VSTD::forward_as_tuple(__k),
1046 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
1049 template <class... _Args>
1050 _LIBCPP_INLINE_VISIBILITY
1051 iterator try_emplace(const_iterator __h, key_type&& __k, _Args&&... __args)
1053 iterator __p = __table_.find(__k);
1057 return emplace_hint(__h,
1058 _VSTD::piecewise_construct, _VSTD::forward_as_tuple(_VSTD::move(__k)),
1059 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
1062 template <class _Vp>
1063 _LIBCPP_INLINE_VISIBILITY
1064 pair<iterator, bool> insert_or_assign(const key_type& __k, _Vp&& __v)
1066 iterator __p = __table_.find(__k);
1069 __p->second = _VSTD::move(__v);
1070 return _VSTD::make_pair(__p, false);
1072 return _VSTD::make_pair(emplace_hint(__p, __k, _VSTD::forward<_Vp>(__v)), true);
1075 template <class _Vp>
1076 _LIBCPP_INLINE_VISIBILITY
1077 pair<iterator, bool> insert_or_assign(key_type&& __k, _Vp&& __v)
1079 iterator __p = __table_.find(__k);
1082 __p->second = _VSTD::move(__v);
1083 return _VSTD::make_pair(__p, false);
1085 return _VSTD::make_pair(emplace_hint(__p, _VSTD::forward<key_type>(__k), _VSTD::forward<_Vp>(__v)), true);
1088 template <class _Vp>
1089 _LIBCPP_INLINE_VISIBILITY
1090 iterator insert_or_assign(const_iterator __h, const key_type& __k, _Vp&& __v)
1092 iterator __p = __table_.find(__k);
1095 __p->second = _VSTD::move(__v);
1098 return emplace_hint(__h, __k, _VSTD::forward<_Vp>(__v));
1101 template <class _Vp>
1102 _LIBCPP_INLINE_VISIBILITY
1103 iterator insert_or_assign(const_iterator __h, key_type&& __k, _Vp&& __v)
1105 iterator __p = __table_.find(__k);
1108 __p->second = _VSTD::move(__v);
1111 return emplace_hint(__h, _VSTD::forward<key_type>(__k), _VSTD::forward<_Vp>(__v));
1117 _LIBCPP_INLINE_VISIBILITY
1118 iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);}
1119 _LIBCPP_INLINE_VISIBILITY
1120 iterator erase(iterator __p) {return __table_.erase(__p.__i_);}
1121 _LIBCPP_INLINE_VISIBILITY
1122 size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
1123 _LIBCPP_INLINE_VISIBILITY
1124 iterator erase(const_iterator __first, const_iterator __last)
1125 {return __table_.erase(__first.__i_, __last.__i_);}
1126 _LIBCPP_INLINE_VISIBILITY
1127 void clear() _NOEXCEPT {__table_.clear();}
1129 _LIBCPP_INLINE_VISIBILITY
1130 void swap(unordered_map& __u)
1131 _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
1132 {__table_.swap(__u.__table_);}
1134 _LIBCPP_INLINE_VISIBILITY
1135 hasher hash_function() const
1136 {return __table_.hash_function().hash_function();}
1137 _LIBCPP_INLINE_VISIBILITY
1138 key_equal key_eq() const
1139 {return __table_.key_eq().key_eq();}
1141 _LIBCPP_INLINE_VISIBILITY
1142 iterator find(const key_type& __k) {return __table_.find(__k);}
1143 _LIBCPP_INLINE_VISIBILITY
1144 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
1145 _LIBCPP_INLINE_VISIBILITY
1146 size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
1147 _LIBCPP_INLINE_VISIBILITY
1148 pair<iterator, iterator> equal_range(const key_type& __k)
1149 {return __table_.__equal_range_unique(__k);}
1150 _LIBCPP_INLINE_VISIBILITY
1151 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
1152 {return __table_.__equal_range_unique(__k);}
1154 mapped_type& operator[](const key_type& __k);
1155 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1156 mapped_type& operator[](key_type&& __k);
1159 mapped_type& at(const key_type& __k);
1160 const mapped_type& at(const key_type& __k) const;
1162 _LIBCPP_INLINE_VISIBILITY
1163 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
1164 _LIBCPP_INLINE_VISIBILITY
1165 size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
1167 _LIBCPP_INLINE_VISIBILITY
1168 size_type bucket_size(size_type __n) const
1169 {return __table_.bucket_size(__n);}
1170 _LIBCPP_INLINE_VISIBILITY
1171 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
1173 _LIBCPP_INLINE_VISIBILITY
1174 local_iterator begin(size_type __n) {return __table_.begin(__n);}
1175 _LIBCPP_INLINE_VISIBILITY
1176 local_iterator end(size_type __n) {return __table_.end(__n);}
1177 _LIBCPP_INLINE_VISIBILITY
1178 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);}
1179 _LIBCPP_INLINE_VISIBILITY
1180 const_local_iterator end(size_type __n) const {return __table_.cend(__n);}
1181 _LIBCPP_INLINE_VISIBILITY
1182 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
1183 _LIBCPP_INLINE_VISIBILITY
1184 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);}
1186 _LIBCPP_INLINE_VISIBILITY
1187 float load_factor() const _NOEXCEPT {return __table_.load_factor();}
1188 _LIBCPP_INLINE_VISIBILITY
1189 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
1190 _LIBCPP_INLINE_VISIBILITY
1191 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
1192 _LIBCPP_INLINE_VISIBILITY
1193 void rehash(size_type __n) {__table_.rehash(__n);}
1194 _LIBCPP_INLINE_VISIBILITY
1195 void reserve(size_type __n) {__table_.reserve(__n);}
1197 #if _LIBCPP_DEBUG_LEVEL >= 2
1199 bool __dereferenceable(const const_iterator* __i) const
1200 {return __table_.__dereferenceable(&__i->__i_);}
1201 bool __decrementable(const const_iterator* __i) const
1202 {return __table_.__decrementable(&__i->__i_);}
1203 bool __addable(const const_iterator* __i, ptrdiff_t __n) const
1204 {return __table_.__addable(&__i->__i_, __n);}
1205 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
1206 {return __table_.__addable(&__i->__i_, __n);}
1208 #endif // _LIBCPP_DEBUG_LEVEL >= 2
1211 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1212 __node_holder __construct_node();
1213 template <class _A0>
1215 __construct_node(_A0&& __a0);
1216 __node_holder __construct_node_with_key(key_type&& __k);
1217 #ifndef _LIBCPP_HAS_NO_VARIADICS
1218 template <class _A0, class _A1, class ..._Args>
1219 __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args);
1220 #endif // _LIBCPP_HAS_NO_VARIADICS
1221 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1222 __node_holder __construct_node_with_key(const key_type& __k);
1225 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1226 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1227 size_type __n, const hasher& __hf, const key_equal& __eql)
1228 : __table_(__hf, __eql)
1230 #if _LIBCPP_DEBUG_LEVEL >= 2
1231 __get_db()->__insert_c(this);
1233 __table_.rehash(__n);
1236 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1237 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1238 size_type __n, const hasher& __hf, const key_equal& __eql,
1239 const allocator_type& __a)
1240 : __table_(__hf, __eql, __a)
1242 #if _LIBCPP_DEBUG_LEVEL >= 2
1243 __get_db()->__insert_c(this);
1245 __table_.rehash(__n);
1248 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1249 inline _LIBCPP_INLINE_VISIBILITY
1250 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1251 const allocator_type& __a)
1254 #if _LIBCPP_DEBUG_LEVEL >= 2
1255 __get_db()->__insert_c(this);
1259 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1260 template <class _InputIterator>
1261 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1262 _InputIterator __first, _InputIterator __last)
1264 #if _LIBCPP_DEBUG_LEVEL >= 2
1265 __get_db()->__insert_c(this);
1267 insert(__first, __last);
1270 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1271 template <class _InputIterator>
1272 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1273 _InputIterator __first, _InputIterator __last, size_type __n,
1274 const hasher& __hf, const key_equal& __eql)
1275 : __table_(__hf, __eql)
1277 #if _LIBCPP_DEBUG_LEVEL >= 2
1278 __get_db()->__insert_c(this);
1280 __table_.rehash(__n);
1281 insert(__first, __last);
1284 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1285 template <class _InputIterator>
1286 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1287 _InputIterator __first, _InputIterator __last, size_type __n,
1288 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1289 : __table_(__hf, __eql, __a)
1291 #if _LIBCPP_DEBUG_LEVEL >= 2
1292 __get_db()->__insert_c(this);
1294 __table_.rehash(__n);
1295 insert(__first, __last);
1298 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1299 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1300 const unordered_map& __u)
1301 : __table_(__u.__table_)
1303 #if _LIBCPP_DEBUG_LEVEL >= 2
1304 __get_db()->__insert_c(this);
1306 __table_.rehash(__u.bucket_count());
1307 insert(__u.begin(), __u.end());
1310 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1311 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1312 const unordered_map& __u, const allocator_type& __a)
1313 : __table_(__u.__table_, __a)
1315 #if _LIBCPP_DEBUG_LEVEL >= 2
1316 __get_db()->__insert_c(this);
1318 __table_.rehash(__u.bucket_count());
1319 insert(__u.begin(), __u.end());
1322 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1324 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1325 inline _LIBCPP_INLINE_VISIBILITY
1326 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1327 unordered_map&& __u)
1328 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
1329 : __table_(_VSTD::move(__u.__table_))
1331 #if _LIBCPP_DEBUG_LEVEL >= 2
1332 __get_db()->__insert_c(this);
1333 __get_db()->swap(this, &__u);
1337 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1338 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1339 unordered_map&& __u, const allocator_type& __a)
1340 : __table_(_VSTD::move(__u.__table_), __a)
1342 #if _LIBCPP_DEBUG_LEVEL >= 2
1343 __get_db()->__insert_c(this);
1345 if (__a != __u.get_allocator())
1347 iterator __i = __u.begin();
1348 while (__u.size() != 0)
1349 __table_.__insert_unique(
1350 _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_)
1353 #if _LIBCPP_DEBUG_LEVEL >= 2
1355 __get_db()->swap(this, &__u);
1359 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1361 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1363 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1364 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1365 initializer_list<value_type> __il)
1367 #if _LIBCPP_DEBUG_LEVEL >= 2
1368 __get_db()->__insert_c(this);
1370 insert(__il.begin(), __il.end());
1373 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1374 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1375 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1376 const key_equal& __eql)
1377 : __table_(__hf, __eql)
1379 #if _LIBCPP_DEBUG_LEVEL >= 2
1380 __get_db()->__insert_c(this);
1382 __table_.rehash(__n);
1383 insert(__il.begin(), __il.end());
1386 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1387 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1388 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1389 const key_equal& __eql, const allocator_type& __a)
1390 : __table_(__hf, __eql, __a)
1392 #if _LIBCPP_DEBUG_LEVEL >= 2
1393 __get_db()->__insert_c(this);
1395 __table_.rehash(__n);
1396 insert(__il.begin(), __il.end());
1399 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1401 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1403 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1404 inline _LIBCPP_INLINE_VISIBILITY
1405 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
1406 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_map&& __u)
1407 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
1409 __table_ = _VSTD::move(__u.__table_);
1413 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1415 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1417 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1418 inline _LIBCPP_INLINE_VISIBILITY
1419 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
1420 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(
1421 initializer_list<value_type> __il)
1423 __table_.__assign_unique(__il.begin(), __il.end());
1427 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1429 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1431 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1432 typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1433 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node()
1435 __node_allocator& __na = __table_.__node_alloc();
1436 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1437 __node_traits::construct(__na, _VSTD::addressof(__h->__value_));
1438 __h.get_deleter().__first_constructed = true;
1439 __h.get_deleter().__second_constructed = true;
1443 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1444 template <class _A0>
1445 typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1446 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
1448 __node_allocator& __na = __table_.__node_alloc();
1449 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1450 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1451 _VSTD::forward<_A0>(__a0));
1452 __h.get_deleter().__first_constructed = true;
1453 __h.get_deleter().__second_constructed = true;
1457 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1458 typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1459 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(key_type&& __k)
1461 __node_allocator& __na = __table_.__node_alloc();
1462 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1463 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), _VSTD::move(__k));
1464 __h.get_deleter().__first_constructed = true;
1465 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
1466 __h.get_deleter().__second_constructed = true;
1470 #ifndef _LIBCPP_HAS_NO_VARIADICS
1472 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1473 template <class _A0, class _A1, class ..._Args>
1474 typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1475 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0,
1479 __node_allocator& __na = __table_.__node_alloc();
1480 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1481 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1482 _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1),
1483 _VSTD::forward<_Args>(__args)...);
1484 __h.get_deleter().__first_constructed = true;
1485 __h.get_deleter().__second_constructed = true;
1489 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1490 template <class... _Args>
1491 pair<typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator, bool>
1492 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_Args&&... __args)
1494 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1495 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1501 #endif // _LIBCPP_HAS_NO_VARIADICS
1502 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1504 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1505 typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1506 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(const key_type& __k)
1508 __node_allocator& __na = __table_.__node_alloc();
1509 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1510 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), __k);
1511 __h.get_deleter().__first_constructed = true;
1512 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
1513 __h.get_deleter().__second_constructed = true;
1514 return _LIBCPP_EXPLICIT_MOVE(__h); // explicitly moved for C++03
1517 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1518 template <class _InputIterator>
1519 inline _LIBCPP_INLINE_VISIBILITY
1521 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
1522 _InputIterator __last)
1524 for (; __first != __last; ++__first)
1525 __table_.__insert_unique(*__first);
1528 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1530 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k)
1532 iterator __i = find(__k);
1535 __node_holder __h = __construct_node_with_key(__k);
1536 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1538 return __r.first->second;
1541 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1543 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1545 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&& __k)
1547 iterator __i = find(__k);
1550 __node_holder __h = __construct_node_with_key(_VSTD::move(__k));
1551 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1553 return __r.first->second;
1556 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1558 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1560 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k)
1562 iterator __i = find(__k);
1563 #ifndef _LIBCPP_NO_EXCEPTIONS
1565 throw out_of_range("unordered_map::at: key not found");
1566 #endif // _LIBCPP_NO_EXCEPTIONS
1570 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1572 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) const
1574 const_iterator __i = find(__k);
1575 #ifndef _LIBCPP_NO_EXCEPTIONS
1577 throw out_of_range("unordered_map::at: key not found");
1578 #endif // _LIBCPP_NO_EXCEPTIONS
1582 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1583 inline _LIBCPP_INLINE_VISIBILITY
1585 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1586 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1587 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1592 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1594 operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1595 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1597 if (__x.size() != __y.size())
1599 typedef typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
1601 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();
1604 const_iterator __j = __y.find(__i->first);
1605 if (__j == __ey || !(*__i == *__j))
1611 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1612 inline _LIBCPP_INLINE_VISIBILITY
1614 operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1615 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1617 return !(__x == __y);
1620 template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
1621 class _Alloc = allocator<pair<const _Key, _Tp> > >
1622 class _LIBCPP_TYPE_VIS_ONLY unordered_multimap
1626 typedef _Key key_type;
1627 typedef _Tp mapped_type;
1628 typedef _Hash hasher;
1629 typedef _Pred key_equal;
1630 typedef _Alloc allocator_type;
1631 typedef pair<const key_type, mapped_type> value_type;
1632 typedef pair<key_type, mapped_type> __nc_value_type;
1633 typedef value_type& reference;
1634 typedef const value_type& const_reference;
1635 static_assert((is_same<value_type, typename allocator_type::value_type>::value),
1636 "Invalid allocator::value_type");
1639 typedef __hash_value_type<key_type, mapped_type> __value_type;
1640 typedef __unordered_map_hasher<key_type, __value_type, hasher> __hasher;
1641 typedef __unordered_map_equal<key_type, __value_type, key_equal> __key_equal;
1642 typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>,
1643 __value_type>::type __allocator_type;
1645 typedef __hash_table<__value_type, __hasher,
1646 __key_equal, __allocator_type> __table;
1650 typedef typename __table::__node_traits __node_traits;
1651 typedef typename __table::__node_allocator __node_allocator;
1652 typedef typename __table::__node __node;
1653 typedef __hash_map_node_destructor<__node_allocator> _Dp;
1654 typedef unique_ptr<__node, _Dp> __node_holder;
1655 typedef allocator_traits<allocator_type> __alloc_traits;
1657 typedef typename __alloc_traits::pointer pointer;
1658 typedef typename __alloc_traits::const_pointer const_pointer;
1659 typedef typename __alloc_traits::size_type size_type;
1660 typedef typename __alloc_traits::difference_type difference_type;
1662 typedef __hash_map_iterator<typename __table::iterator> iterator;
1663 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
1664 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
1665 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
1667 _LIBCPP_INLINE_VISIBILITY
1668 unordered_multimap()
1669 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
1671 #if _LIBCPP_DEBUG_LEVEL >= 2
1672 __get_db()->__insert_c(this);
1675 explicit unordered_multimap(size_type __n, const hasher& __hf = hasher(),
1676 const key_equal& __eql = key_equal());
1677 unordered_multimap(size_type __n, const hasher& __hf,
1678 const key_equal& __eql,
1679 const allocator_type& __a);
1680 template <class _InputIterator>
1681 unordered_multimap(_InputIterator __first, _InputIterator __last);
1682 template <class _InputIterator>
1683 unordered_multimap(_InputIterator __first, _InputIterator __last,
1684 size_type __n, const hasher& __hf = hasher(),
1685 const key_equal& __eql = key_equal());
1686 template <class _InputIterator>
1687 unordered_multimap(_InputIterator __first, _InputIterator __last,
1688 size_type __n, const hasher& __hf,
1689 const key_equal& __eql,
1690 const allocator_type& __a);
1691 explicit unordered_multimap(const allocator_type& __a);
1692 unordered_multimap(const unordered_multimap& __u);
1693 unordered_multimap(const unordered_multimap& __u, const allocator_type& __a);
1694 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1695 unordered_multimap(unordered_multimap&& __u)
1696 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
1697 unordered_multimap(unordered_multimap&& __u, const allocator_type& __a);
1698 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1699 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1700 unordered_multimap(initializer_list<value_type> __il);
1701 unordered_multimap(initializer_list<value_type> __il, size_type __n,
1702 const hasher& __hf = hasher(),
1703 const key_equal& __eql = key_equal());
1704 unordered_multimap(initializer_list<value_type> __il, size_type __n,
1705 const hasher& __hf, const key_equal& __eql,
1706 const allocator_type& __a);
1707 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1708 #if _LIBCPP_STD_VER > 11
1709 _LIBCPP_INLINE_VISIBILITY
1710 unordered_multimap(size_type __n, const allocator_type& __a)
1711 : unordered_multimap(__n, hasher(), key_equal(), __a) {}
1712 _LIBCPP_INLINE_VISIBILITY
1713 unordered_multimap(size_type __n, const hasher& __hf, const allocator_type& __a)
1714 : unordered_multimap(__n, __hf, key_equal(), __a) {}
1715 template <class _InputIterator>
1716 _LIBCPP_INLINE_VISIBILITY
1717 unordered_multimap(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a)
1718 : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a) {}
1719 template <class _InputIterator>
1720 _LIBCPP_INLINE_VISIBILITY
1721 unordered_multimap(_InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf,
1722 const allocator_type& __a)
1723 : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a) {}
1724 _LIBCPP_INLINE_VISIBILITY
1725 unordered_multimap(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)
1726 : unordered_multimap(__il, __n, hasher(), key_equal(), __a) {}
1727 _LIBCPP_INLINE_VISIBILITY
1728 unordered_multimap(initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1729 const allocator_type& __a)
1730 : unordered_multimap(__il, __n, __hf, key_equal(), __a) {}
1732 // ~unordered_multimap() = default;
1733 _LIBCPP_INLINE_VISIBILITY
1734 unordered_multimap& operator=(const unordered_multimap& __u)
1736 #if __cplusplus >= 201103L
1737 __table_ = __u.__table_;
1741 __table_.hash_function() = __u.__table_.hash_function();
1742 __table_.key_eq() = __u.__table_.key_eq();
1743 __table_.max_load_factor() = __u.__table_.max_load_factor();
1744 __table_.__copy_assign_alloc(__u.__table_);
1745 insert(__u.begin(), __u.end());
1750 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1751 unordered_multimap& operator=(unordered_multimap&& __u)
1752 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
1754 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1755 unordered_multimap& operator=(initializer_list<value_type> __il);
1756 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1758 _LIBCPP_INLINE_VISIBILITY
1759 allocator_type get_allocator() const _NOEXCEPT
1760 {return allocator_type(__table_.__node_alloc());}
1762 _LIBCPP_INLINE_VISIBILITY
1763 bool empty() const _NOEXCEPT {return __table_.size() == 0;}
1764 _LIBCPP_INLINE_VISIBILITY
1765 size_type size() const _NOEXCEPT {return __table_.size();}
1766 _LIBCPP_INLINE_VISIBILITY
1767 size_type max_size() const _NOEXCEPT {return __table_.max_size();}
1769 _LIBCPP_INLINE_VISIBILITY
1770 iterator begin() _NOEXCEPT {return __table_.begin();}
1771 _LIBCPP_INLINE_VISIBILITY
1772 iterator end() _NOEXCEPT {return __table_.end();}
1773 _LIBCPP_INLINE_VISIBILITY
1774 const_iterator begin() const _NOEXCEPT {return __table_.begin();}
1775 _LIBCPP_INLINE_VISIBILITY
1776 const_iterator end() const _NOEXCEPT {return __table_.end();}
1777 _LIBCPP_INLINE_VISIBILITY
1778 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
1779 _LIBCPP_INLINE_VISIBILITY
1780 const_iterator cend() const _NOEXCEPT {return __table_.end();}
1782 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1783 #ifndef _LIBCPP_HAS_NO_VARIADICS
1785 template <class... _Args>
1786 iterator emplace(_Args&&... __args);
1788 template <class... _Args>
1789 iterator emplace_hint(const_iterator __p, _Args&&... __args);
1790 #endif // _LIBCPP_HAS_NO_VARIADICS
1791 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1792 _LIBCPP_INLINE_VISIBILITY
1793 iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
1794 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1795 template <class _Pp,
1796 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1797 _LIBCPP_INLINE_VISIBILITY
1798 iterator insert(_Pp&& __x)
1799 {return __table_.__insert_multi(_VSTD::forward<_Pp>(__x));}
1800 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1801 _LIBCPP_INLINE_VISIBILITY
1802 iterator insert(const_iterator __p, const value_type& __x)
1803 {return __table_.__insert_multi(__p.__i_, __x);}
1804 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1805 template <class _Pp,
1806 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1807 _LIBCPP_INLINE_VISIBILITY
1808 iterator insert(const_iterator __p, _Pp&& __x)
1809 {return __table_.__insert_multi(__p.__i_, _VSTD::forward<_Pp>(__x));}
1810 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1811 template <class _InputIterator>
1812 void insert(_InputIterator __first, _InputIterator __last);
1813 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1814 _LIBCPP_INLINE_VISIBILITY
1815 void insert(initializer_list<value_type> __il)
1816 {insert(__il.begin(), __il.end());}
1817 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1819 _LIBCPP_INLINE_VISIBILITY
1820 iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);}
1821 _LIBCPP_INLINE_VISIBILITY
1822 iterator erase(iterator __p) {return __table_.erase(__p.__i_);}
1823 _LIBCPP_INLINE_VISIBILITY
1824 size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
1825 _LIBCPP_INLINE_VISIBILITY
1826 iterator erase(const_iterator __first, const_iterator __last)
1827 {return __table_.erase(__first.__i_, __last.__i_);}
1828 _LIBCPP_INLINE_VISIBILITY
1829 void clear() _NOEXCEPT {__table_.clear();}
1831 _LIBCPP_INLINE_VISIBILITY
1832 void swap(unordered_multimap& __u)
1833 _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
1834 {__table_.swap(__u.__table_);}
1836 _LIBCPP_INLINE_VISIBILITY
1837 hasher hash_function() const
1838 {return __table_.hash_function().hash_function();}
1839 _LIBCPP_INLINE_VISIBILITY
1840 key_equal key_eq() const
1841 {return __table_.key_eq().key_eq();}
1843 _LIBCPP_INLINE_VISIBILITY
1844 iterator find(const key_type& __k) {return __table_.find(__k);}
1845 _LIBCPP_INLINE_VISIBILITY
1846 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
1847 _LIBCPP_INLINE_VISIBILITY
1848 size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
1849 _LIBCPP_INLINE_VISIBILITY
1850 pair<iterator, iterator> equal_range(const key_type& __k)
1851 {return __table_.__equal_range_multi(__k);}
1852 _LIBCPP_INLINE_VISIBILITY
1853 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
1854 {return __table_.__equal_range_multi(__k);}
1856 _LIBCPP_INLINE_VISIBILITY
1857 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
1858 _LIBCPP_INLINE_VISIBILITY
1859 size_type max_bucket_count() const _NOEXCEPT
1860 {return __table_.max_bucket_count();}
1862 _LIBCPP_INLINE_VISIBILITY
1863 size_type bucket_size(size_type __n) const
1864 {return __table_.bucket_size(__n);}
1865 _LIBCPP_INLINE_VISIBILITY
1866 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
1868 _LIBCPP_INLINE_VISIBILITY
1869 local_iterator begin(size_type __n) {return __table_.begin(__n);}
1870 _LIBCPP_INLINE_VISIBILITY
1871 local_iterator end(size_type __n) {return __table_.end(__n);}
1872 _LIBCPP_INLINE_VISIBILITY
1873 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);}
1874 _LIBCPP_INLINE_VISIBILITY
1875 const_local_iterator end(size_type __n) const {return __table_.cend(__n);}
1876 _LIBCPP_INLINE_VISIBILITY
1877 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
1878 _LIBCPP_INLINE_VISIBILITY
1879 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);}
1881 _LIBCPP_INLINE_VISIBILITY
1882 float load_factor() const _NOEXCEPT {return __table_.load_factor();}
1883 _LIBCPP_INLINE_VISIBILITY
1884 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
1885 _LIBCPP_INLINE_VISIBILITY
1886 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
1887 _LIBCPP_INLINE_VISIBILITY
1888 void rehash(size_type __n) {__table_.rehash(__n);}
1889 _LIBCPP_INLINE_VISIBILITY
1890 void reserve(size_type __n) {__table_.reserve(__n);}
1892 #if _LIBCPP_DEBUG_LEVEL >= 2
1894 bool __dereferenceable(const const_iterator* __i) const
1895 {return __table_.__dereferenceable(&__i->__i_);}
1896 bool __decrementable(const const_iterator* __i) const
1897 {return __table_.__decrementable(&__i->__i_);}
1898 bool __addable(const const_iterator* __i, ptrdiff_t __n) const
1899 {return __table_.__addable(&__i->__i_, __n);}
1900 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
1901 {return __table_.__addable(&__i->__i_, __n);}
1903 #endif // _LIBCPP_DEBUG_LEVEL >= 2
1906 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1907 __node_holder __construct_node();
1908 template <class _A0>
1910 __construct_node(_A0&& __a0);
1911 #ifndef _LIBCPP_HAS_NO_VARIADICS
1912 template <class _A0, class _A1, class ..._Args>
1913 __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args);
1914 #endif // _LIBCPP_HAS_NO_VARIADICS
1915 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1918 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1919 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1920 size_type __n, const hasher& __hf, const key_equal& __eql)
1921 : __table_(__hf, __eql)
1923 #if _LIBCPP_DEBUG_LEVEL >= 2
1924 __get_db()->__insert_c(this);
1926 __table_.rehash(__n);
1929 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1930 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1931 size_type __n, const hasher& __hf, const key_equal& __eql,
1932 const allocator_type& __a)
1933 : __table_(__hf, __eql, __a)
1935 #if _LIBCPP_DEBUG_LEVEL >= 2
1936 __get_db()->__insert_c(this);
1938 __table_.rehash(__n);
1941 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1942 template <class _InputIterator>
1943 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1944 _InputIterator __first, _InputIterator __last)
1946 #if _LIBCPP_DEBUG_LEVEL >= 2
1947 __get_db()->__insert_c(this);
1949 insert(__first, __last);
1952 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1953 template <class _InputIterator>
1954 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1955 _InputIterator __first, _InputIterator __last, size_type __n,
1956 const hasher& __hf, const key_equal& __eql)
1957 : __table_(__hf, __eql)
1959 #if _LIBCPP_DEBUG_LEVEL >= 2
1960 __get_db()->__insert_c(this);
1962 __table_.rehash(__n);
1963 insert(__first, __last);
1966 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1967 template <class _InputIterator>
1968 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1969 _InputIterator __first, _InputIterator __last, size_type __n,
1970 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1971 : __table_(__hf, __eql, __a)
1973 #if _LIBCPP_DEBUG_LEVEL >= 2
1974 __get_db()->__insert_c(this);
1976 __table_.rehash(__n);
1977 insert(__first, __last);
1980 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1981 inline _LIBCPP_INLINE_VISIBILITY
1982 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1983 const allocator_type& __a)
1986 #if _LIBCPP_DEBUG_LEVEL >= 2
1987 __get_db()->__insert_c(this);
1991 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1992 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1993 const unordered_multimap& __u)
1994 : __table_(__u.__table_)
1996 #if _LIBCPP_DEBUG_LEVEL >= 2
1997 __get_db()->__insert_c(this);
1999 __table_.rehash(__u.bucket_count());
2000 insert(__u.begin(), __u.end());
2003 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2004 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2005 const unordered_multimap& __u, const allocator_type& __a)
2006 : __table_(__u.__table_, __a)
2008 #if _LIBCPP_DEBUG_LEVEL >= 2
2009 __get_db()->__insert_c(this);
2011 __table_.rehash(__u.bucket_count());
2012 insert(__u.begin(), __u.end());
2015 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
2017 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2018 inline _LIBCPP_INLINE_VISIBILITY
2019 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2020 unordered_multimap&& __u)
2021 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
2022 : __table_(_VSTD::move(__u.__table_))
2024 #if _LIBCPP_DEBUG_LEVEL >= 2
2025 __get_db()->__insert_c(this);
2026 __get_db()->swap(this, &__u);
2030 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2031 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2032 unordered_multimap&& __u, const allocator_type& __a)
2033 : __table_(_VSTD::move(__u.__table_), __a)
2035 #if _LIBCPP_DEBUG_LEVEL >= 2
2036 __get_db()->__insert_c(this);
2038 if (__a != __u.get_allocator())
2040 iterator __i = __u.begin();
2041 while (__u.size() != 0)
2043 __table_.__insert_multi(
2044 _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_)
2048 #if _LIBCPP_DEBUG_LEVEL >= 2
2050 __get_db()->swap(this, &__u);
2054 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
2056 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2058 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2059 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2060 initializer_list<value_type> __il)
2062 #if _LIBCPP_DEBUG_LEVEL >= 2
2063 __get_db()->__insert_c(this);
2065 insert(__il.begin(), __il.end());
2068 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2069 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2070 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
2071 const key_equal& __eql)
2072 : __table_(__hf, __eql)
2074 #if _LIBCPP_DEBUG_LEVEL >= 2
2075 __get_db()->__insert_c(this);
2077 __table_.rehash(__n);
2078 insert(__il.begin(), __il.end());
2081 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2082 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2083 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
2084 const key_equal& __eql, const allocator_type& __a)
2085 : __table_(__hf, __eql, __a)
2087 #if _LIBCPP_DEBUG_LEVEL >= 2
2088 __get_db()->__insert_c(this);
2090 __table_.rehash(__n);
2091 insert(__il.begin(), __il.end());
2094 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2096 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
2098 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2099 inline _LIBCPP_INLINE_VISIBILITY
2100 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
2101 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_multimap&& __u)
2102 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
2104 __table_ = _VSTD::move(__u.__table_);
2108 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
2110 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2112 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2113 inline _LIBCPP_INLINE_VISIBILITY
2114 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
2115 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(
2116 initializer_list<value_type> __il)
2118 __table_.__assign_multi(__il.begin(), __il.end());
2122 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2124 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
2126 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2127 typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
2128 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node()
2130 __node_allocator& __na = __table_.__node_alloc();
2131 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
2132 __node_traits::construct(__na, _VSTD::addressof(__h->__value_));
2133 __h.get_deleter().__first_constructed = true;
2134 __h.get_deleter().__second_constructed = true;
2138 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2139 template <class _A0>
2140 typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
2141 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
2143 __node_allocator& __na = __table_.__node_alloc();
2144 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
2145 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
2146 _VSTD::forward<_A0>(__a0));
2147 __h.get_deleter().__first_constructed = true;
2148 __h.get_deleter().__second_constructed = true;
2152 #ifndef _LIBCPP_HAS_NO_VARIADICS
2154 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2155 template <class _A0, class _A1, class ..._Args>
2156 typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
2157 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(
2158 _A0&& __a0, _A1&& __a1, _Args&&... __args)
2160 __node_allocator& __na = __table_.__node_alloc();
2161 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
2162 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
2163 _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1),
2164 _VSTD::forward<_Args>(__args)...);
2165 __h.get_deleter().__first_constructed = true;
2166 __h.get_deleter().__second_constructed = true;
2170 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2171 template <class... _Args>
2172 typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator
2173 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_Args&&... __args)
2175 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
2176 iterator __r = __table_.__node_insert_multi(__h.get());
2181 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2182 template <class... _Args>
2183 typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator
2184 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace_hint(
2185 const_iterator __p, _Args&&... __args)
2187 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
2188 iterator __r = __table_.__node_insert_multi(__p.__i_, __h.get());
2193 #endif // _LIBCPP_HAS_NO_VARIADICS
2194 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
2196 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2197 template <class _InputIterator>
2198 inline _LIBCPP_INLINE_VISIBILITY
2200 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
2201 _InputIterator __last)
2203 for (; __first != __last; ++__first)
2204 __table_.__insert_multi(*__first);
2207 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2208 inline _LIBCPP_INLINE_VISIBILITY
2210 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2211 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2212 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
2217 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2219 operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2220 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2222 if (__x.size() != __y.size())
2224 typedef typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
2226 typedef pair<const_iterator, const_iterator> _EqRng;
2227 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;)
2229 _EqRng __xeq = __x.equal_range(__i->first);
2230 _EqRng __yeq = __y.equal_range(__i->first);
2231 if (_VSTD::distance(__xeq.first, __xeq.second) !=
2232 _VSTD::distance(__yeq.first, __yeq.second) ||
2233 !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first))
2240 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2241 inline _LIBCPP_INLINE_VISIBILITY
2243 operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2244 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2246 return !(__x == __y);
2249 _LIBCPP_END_NAMESPACE_STD
2251 #endif // _LIBCPP_UNORDERED_MAP