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 iterator erase(const_iterator position);
126 size_type erase(const key_type& k);
127 iterator erase(const_iterator first, const_iterator last);
128 void clear() noexcept;
130 void swap(unordered_map&)
132 (!allocator_type::propagate_on_container_swap::value ||
133 __is_nothrow_swappable<allocator_type>::value) &&
134 __is_nothrow_swappable<hasher>::value &&
135 __is_nothrow_swappable<key_equal>::value);
137 hasher hash_function() const;
138 key_equal key_eq() const;
140 iterator find(const key_type& k);
141 const_iterator find(const key_type& k) const;
142 size_type count(const key_type& k) const;
143 pair<iterator, iterator> equal_range(const key_type& k);
144 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
146 mapped_type& operator[](const key_type& k);
147 mapped_type& operator[](key_type&& k);
149 mapped_type& at(const key_type& k);
150 const mapped_type& at(const key_type& k) const;
152 size_type bucket_count() const noexcept;
153 size_type max_bucket_count() const noexcept;
155 size_type bucket_size(size_type n) const;
156 size_type bucket(const key_type& k) const;
158 local_iterator begin(size_type n);
159 local_iterator end(size_type n);
160 const_local_iterator begin(size_type n) const;
161 const_local_iterator end(size_type n) const;
162 const_local_iterator cbegin(size_type n) const;
163 const_local_iterator cend(size_type n) const;
165 float load_factor() const noexcept;
166 float max_load_factor() const noexcept;
167 void max_load_factor(float z);
168 void rehash(size_type n);
169 void reserve(size_type n);
172 template <class Key, class T, class Hash, class Pred, class Alloc>
173 void swap(unordered_map<Key, T, Hash, Pred, Alloc>& x,
174 unordered_map<Key, T, Hash, Pred, Alloc>& y)
175 noexcept(noexcept(x.swap(y)));
177 template <class Key, class T, class Hash, class Pred, class Alloc>
179 operator==(const unordered_map<Key, T, Hash, Pred, Alloc>& x,
180 const unordered_map<Key, T, Hash, Pred, Alloc>& y);
182 template <class Key, class T, class Hash, class Pred, class Alloc>
184 operator!=(const unordered_map<Key, T, Hash, Pred, Alloc>& x,
185 const unordered_map<Key, T, Hash, Pred, Alloc>& y);
187 template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
188 class Alloc = allocator<pair<const Key, T>>>
189 class unordered_multimap
193 typedef Key key_type;
194 typedef T mapped_type;
196 typedef Pred key_equal;
197 typedef Alloc allocator_type;
198 typedef pair<const key_type, mapped_type> value_type;
199 typedef value_type& reference;
200 typedef const value_type& const_reference;
201 typedef typename allocator_traits<allocator_type>::pointer pointer;
202 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
203 typedef typename allocator_traits<allocator_type>::size_type size_type;
204 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
206 typedef /unspecified/ iterator;
207 typedef /unspecified/ const_iterator;
208 typedef /unspecified/ local_iterator;
209 typedef /unspecified/ const_local_iterator;
213 is_nothrow_default_constructible<hasher>::value &&
214 is_nothrow_default_constructible<key_equal>::value &&
215 is_nothrow_default_constructible<allocator_type>::value);
216 explicit unordered_multimap(size_type n, const hasher& hf = hasher(),
217 const key_equal& eql = key_equal(),
218 const allocator_type& a = allocator_type());
219 template <class InputIterator>
220 unordered_multimap(InputIterator f, InputIterator l,
221 size_type n = 0, const hasher& hf = hasher(),
222 const key_equal& eql = key_equal(),
223 const allocator_type& a = allocator_type());
224 explicit unordered_multimap(const allocator_type&);
225 unordered_multimap(const unordered_multimap&);
226 unordered_multimap(const unordered_multimap&, const Allocator&);
227 unordered_multimap(unordered_multimap&&)
229 is_nothrow_move_constructible<hasher>::value &&
230 is_nothrow_move_constructible<key_equal>::value &&
231 is_nothrow_move_constructible<allocator_type>::value);
232 unordered_multimap(unordered_multimap&&, const Allocator&);
233 unordered_multimap(initializer_list<value_type>, size_type n = 0,
234 const hasher& hf = hasher(), const key_equal& eql = key_equal(),
235 const allocator_type& a = allocator_type());
236 unordered_multimap(size_type n, const allocator_type& a)
237 : unordered_multimap(n, hasher(), key_equal(), a) {} // C++14
238 unordered_multimap(size_type n, const hasher& hf, const allocator_type& a)
239 : unordered_multimap(n, hf, key_equal(), a) {} // C++14
240 template <class InputIterator>
241 unordered_multimap(InputIterator f, InputIterator l, size_type n, const allocator_type& a)
242 : unordered_multimap(f, l, n, hasher(), key_equal(), a) {} // C++14
243 template <class InputIterator>
244 unordered_multimap(InputIterator f, InputIterator l, size_type n, const hasher& hf,
245 const allocator_type& a)
246 : unordered_multimap(f, l, n, hf, key_equal(), a) {} // C++14
247 unordered_multimap(initializer_list<value_type> il, size_type n, const allocator_type& a)
248 : unordered_multimap(il, n, hasher(), key_equal(), a) {} // C++14
249 unordered_multimap(initializer_list<value_type> il, size_type n, const hasher& hf,
250 const allocator_type& a)
251 : unordered_multimap(il, n, hf, key_equal(), a) {} // C++14
252 ~unordered_multimap();
253 unordered_multimap& operator=(const unordered_multimap&);
254 unordered_multimap& operator=(unordered_multimap&&)
256 allocator_type::propagate_on_container_move_assignment::value &&
257 is_nothrow_move_assignable<allocator_type>::value &&
258 is_nothrow_move_assignable<hasher>::value &&
259 is_nothrow_move_assignable<key_equal>::value);
260 unordered_multimap& operator=(initializer_list<value_type>);
262 allocator_type get_allocator() const noexcept;
264 bool empty() const noexcept;
265 size_type size() const noexcept;
266 size_type max_size() const noexcept;
268 iterator begin() noexcept;
269 iterator end() noexcept;
270 const_iterator begin() const noexcept;
271 const_iterator end() const noexcept;
272 const_iterator cbegin() const noexcept;
273 const_iterator cend() const noexcept;
275 template <class... Args>
276 iterator emplace(Args&&... args);
277 template <class... Args>
278 iterator emplace_hint(const_iterator position, Args&&... args);
279 iterator insert(const value_type& obj);
281 iterator insert(P&& obj);
282 iterator insert(const_iterator hint, const value_type& obj);
284 iterator insert(const_iterator hint, P&& obj);
285 template <class InputIterator>
286 void insert(InputIterator first, InputIterator last);
287 void insert(initializer_list<value_type>);
289 iterator erase(const_iterator position);
290 size_type erase(const key_type& k);
291 iterator erase(const_iterator first, const_iterator last);
292 void clear() noexcept;
294 void swap(unordered_multimap&)
296 (!allocator_type::propagate_on_container_swap::value ||
297 __is_nothrow_swappable<allocator_type>::value) &&
298 __is_nothrow_swappable<hasher>::value &&
299 __is_nothrow_swappable<key_equal>::value);
301 hasher hash_function() const;
302 key_equal key_eq() const;
304 iterator find(const key_type& k);
305 const_iterator find(const key_type& k) const;
306 size_type count(const key_type& k) const;
307 pair<iterator, iterator> equal_range(const key_type& k);
308 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
310 size_type bucket_count() const noexcept;
311 size_type max_bucket_count() const noexcept;
313 size_type bucket_size(size_type n) const;
314 size_type bucket(const key_type& k) const;
316 local_iterator begin(size_type n);
317 local_iterator end(size_type n);
318 const_local_iterator begin(size_type n) const;
319 const_local_iterator end(size_type n) const;
320 const_local_iterator cbegin(size_type n) const;
321 const_local_iterator cend(size_type n) const;
323 float load_factor() const noexcept;
324 float max_load_factor() const noexcept;
325 void max_load_factor(float z);
326 void rehash(size_type n);
327 void reserve(size_type n);
330 template <class Key, class T, class Hash, class Pred, class Alloc>
331 void swap(unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
332 unordered_multimap<Key, T, Hash, Pred, Alloc>& y)
333 noexcept(noexcept(x.swap(y)));
335 template <class Key, class T, class Hash, class Pred, class Alloc>
337 operator==(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
338 const unordered_multimap<Key, T, Hash, Pred, Alloc>& y);
340 template <class Key, class T, class Hash, class Pred, class Alloc>
342 operator!=(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
343 const unordered_multimap<Key, T, Hash, Pred, Alloc>& y);
350 #include <__hash_table>
351 #include <functional>
356 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
357 #pragma GCC system_header
360 _LIBCPP_BEGIN_NAMESPACE_STD
362 template <class _Key, class _Cp, class _Hash, bool = is_empty<_Hash>::value
363 #if __has_feature(is_final)
364 && !__is_final(_Hash)
367 class __unordered_map_hasher
371 _LIBCPP_INLINE_VISIBILITY
372 __unordered_map_hasher()
373 _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value)
375 _LIBCPP_INLINE_VISIBILITY
376 __unordered_map_hasher(const _Hash& __h)
377 _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value)
379 _LIBCPP_INLINE_VISIBILITY
380 const _Hash& hash_function() const _NOEXCEPT {return *this;}
381 _LIBCPP_INLINE_VISIBILITY
382 size_t operator()(const _Cp& __x) const
383 {return static_cast<const _Hash&>(*this)(__x.__cc.first);}
384 _LIBCPP_INLINE_VISIBILITY
385 size_t operator()(const _Key& __x) const
386 {return static_cast<const _Hash&>(*this)(__x);}
389 template <class _Key, class _Cp, class _Hash>
390 class __unordered_map_hasher<_Key, _Cp, _Hash, false>
395 _LIBCPP_INLINE_VISIBILITY
396 __unordered_map_hasher()
397 _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value)
399 _LIBCPP_INLINE_VISIBILITY
400 __unordered_map_hasher(const _Hash& __h)
401 _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value)
403 _LIBCPP_INLINE_VISIBILITY
404 const _Hash& hash_function() const _NOEXCEPT {return __hash_;}
405 _LIBCPP_INLINE_VISIBILITY
406 size_t operator()(const _Cp& __x) const
407 {return __hash_(__x.__cc.first);}
408 _LIBCPP_INLINE_VISIBILITY
409 size_t operator()(const _Key& __x) const
410 {return __hash_(__x);}
413 template <class _Key, class _Cp, class _Pred, bool = is_empty<_Pred>::value
414 #if __has_feature(is_final)
415 && !__is_final(_Pred)
418 class __unordered_map_equal
422 _LIBCPP_INLINE_VISIBILITY
423 __unordered_map_equal()
424 _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value)
426 _LIBCPP_INLINE_VISIBILITY
427 __unordered_map_equal(const _Pred& __p)
428 _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value)
430 _LIBCPP_INLINE_VISIBILITY
431 const _Pred& key_eq() const _NOEXCEPT {return *this;}
432 _LIBCPP_INLINE_VISIBILITY
433 bool operator()(const _Cp& __x, const _Cp& __y) const
434 {return static_cast<const _Pred&>(*this)(__x.__cc.first, __y.__cc.first);}
435 _LIBCPP_INLINE_VISIBILITY
436 bool operator()(const _Cp& __x, const _Key& __y) const
437 {return static_cast<const _Pred&>(*this)(__x.__cc.first, __y);}
438 _LIBCPP_INLINE_VISIBILITY
439 bool operator()(const _Key& __x, const _Cp& __y) const
440 {return static_cast<const _Pred&>(*this)(__x, __y.__cc.first);}
443 template <class _Key, class _Cp, class _Pred>
444 class __unordered_map_equal<_Key, _Cp, _Pred, false>
449 _LIBCPP_INLINE_VISIBILITY
450 __unordered_map_equal()
451 _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value)
453 _LIBCPP_INLINE_VISIBILITY
454 __unordered_map_equal(const _Pred& __p)
455 _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value)
457 _LIBCPP_INLINE_VISIBILITY
458 const _Pred& key_eq() const _NOEXCEPT {return __pred_;}
459 _LIBCPP_INLINE_VISIBILITY
460 bool operator()(const _Cp& __x, const _Cp& __y) const
461 {return __pred_(__x.__cc.first, __y.__cc.first);}
462 _LIBCPP_INLINE_VISIBILITY
463 bool operator()(const _Cp& __x, const _Key& __y) const
464 {return __pred_(__x.__cc.first, __y);}
465 _LIBCPP_INLINE_VISIBILITY
466 bool operator()(const _Key& __x, const _Cp& __y) const
467 {return __pred_(__x, __y.__cc.first);}
470 template <class _Alloc>
471 class __hash_map_node_destructor
473 typedef _Alloc allocator_type;
474 typedef allocator_traits<allocator_type> __alloc_traits;
475 typedef typename __alloc_traits::value_type::value_type value_type;
477 typedef typename __alloc_traits::pointer pointer;
479 typedef typename value_type::value_type::first_type first_type;
480 typedef typename value_type::value_type::second_type second_type;
482 allocator_type& __na_;
484 __hash_map_node_destructor& operator=(const __hash_map_node_destructor&);
487 bool __first_constructed;
488 bool __second_constructed;
490 _LIBCPP_INLINE_VISIBILITY
491 explicit __hash_map_node_destructor(allocator_type& __na) _NOEXCEPT
493 __first_constructed(false),
494 __second_constructed(false)
497 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
498 _LIBCPP_INLINE_VISIBILITY
499 __hash_map_node_destructor(__hash_node_destructor<allocator_type>&& __x)
502 __first_constructed(__x.__value_constructed),
503 __second_constructed(__x.__value_constructed)
505 __x.__value_constructed = false;
507 #else // _LIBCPP_HAS_NO_RVALUE_REFERENCES
508 _LIBCPP_INLINE_VISIBILITY
509 __hash_map_node_destructor(const __hash_node_destructor<allocator_type>& __x)
511 __first_constructed(__x.__value_constructed),
512 __second_constructed(__x.__value_constructed)
514 const_cast<bool&>(__x.__value_constructed) = false;
516 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
518 _LIBCPP_INLINE_VISIBILITY
519 void operator()(pointer __p) _NOEXCEPT
521 if (__second_constructed)
522 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.second));
523 if (__first_constructed)
524 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.first));
526 __alloc_traits::deallocate(__na_, __p, 1);
530 #if __cplusplus >= 201103L
532 template <class _Key, class _Tp>
533 union __hash_value_type
535 typedef _Key key_type;
536 typedef _Tp mapped_type;
537 typedef pair<const key_type, mapped_type> value_type;
538 typedef pair<key_type, mapped_type> __nc_value_type;
541 __nc_value_type __nc;
543 template <class ..._Args>
544 _LIBCPP_INLINE_VISIBILITY
545 __hash_value_type(_Args&& ...__args)
546 : __cc(std::forward<_Args>(__args)...) {}
548 _LIBCPP_INLINE_VISIBILITY
549 __hash_value_type(const __hash_value_type& __v)
552 _LIBCPP_INLINE_VISIBILITY
553 __hash_value_type(__hash_value_type&& __v)
554 : __nc(std::move(__v.__nc)) {}
556 _LIBCPP_INLINE_VISIBILITY
557 __hash_value_type& operator=(const __hash_value_type& __v)
558 {__nc = __v.__cc; return *this;}
560 _LIBCPP_INLINE_VISIBILITY
561 __hash_value_type& operator=(__hash_value_type&& __v)
562 {__nc = std::move(__v.__nc); return *this;}
564 _LIBCPP_INLINE_VISIBILITY
565 ~__hash_value_type() {__cc.~value_type();}
570 template <class _Key, class _Tp>
571 struct __hash_value_type
573 typedef _Key key_type;
574 typedef _Tp mapped_type;
575 typedef pair<const key_type, mapped_type> value_type;
579 _LIBCPP_INLINE_VISIBILITY
580 __hash_value_type() {}
583 _LIBCPP_INLINE_VISIBILITY
584 __hash_value_type(const _A0& __a0)
587 template <class _A0, class _A1>
588 _LIBCPP_INLINE_VISIBILITY
589 __hash_value_type(const _A0& __a0, const _A1& __a1)
590 : __cc(__a0, __a1) {}
595 template <class _HashIterator>
596 class _LIBCPP_TYPE_VIS_ONLY __hash_map_iterator
600 typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits;
601 typedef const typename _HashIterator::value_type::value_type::first_type key_type;
602 typedef typename _HashIterator::value_type::value_type::second_type mapped_type;
604 typedef forward_iterator_tag iterator_category;
605 typedef pair<key_type, mapped_type> value_type;
606 typedef typename _HashIterator::difference_type difference_type;
607 typedef value_type& reference;
608 typedef typename __pointer_traits::template
609 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
612 rebind<value_type>::other
616 _LIBCPP_INLINE_VISIBILITY
617 __hash_map_iterator() _NOEXCEPT {}
619 _LIBCPP_INLINE_VISIBILITY
620 __hash_map_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
622 _LIBCPP_INLINE_VISIBILITY
623 reference operator*() const {return __i_->__cc;}
624 _LIBCPP_INLINE_VISIBILITY
625 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);}
627 _LIBCPP_INLINE_VISIBILITY
628 __hash_map_iterator& operator++() {++__i_; return *this;}
629 _LIBCPP_INLINE_VISIBILITY
630 __hash_map_iterator operator++(int)
632 __hash_map_iterator __t(*this);
637 friend _LIBCPP_INLINE_VISIBILITY
638 bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y)
639 {return __x.__i_ == __y.__i_;}
640 friend _LIBCPP_INLINE_VISIBILITY
641 bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y)
642 {return __x.__i_ != __y.__i_;}
644 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map;
645 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap;
646 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator;
647 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator;
648 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator;
651 template <class _HashIterator>
652 class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator
656 typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits;
657 typedef const typename _HashIterator::value_type::value_type::first_type key_type;
658 typedef typename _HashIterator::value_type::value_type::second_type mapped_type;
660 typedef forward_iterator_tag iterator_category;
661 typedef pair<key_type, mapped_type> value_type;
662 typedef typename _HashIterator::difference_type difference_type;
663 typedef const value_type& reference;
664 typedef typename __pointer_traits::template
665 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
666 rebind<const value_type>
668 rebind<const value_type>::other
672 _LIBCPP_INLINE_VISIBILITY
673 __hash_map_const_iterator() _NOEXCEPT {}
675 _LIBCPP_INLINE_VISIBILITY
676 __hash_map_const_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
677 _LIBCPP_INLINE_VISIBILITY
678 __hash_map_const_iterator(
679 __hash_map_iterator<typename _HashIterator::__non_const_iterator> __i)
683 _LIBCPP_INLINE_VISIBILITY
684 reference operator*() const {return __i_->__cc;}
685 _LIBCPP_INLINE_VISIBILITY
686 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);}
688 _LIBCPP_INLINE_VISIBILITY
689 __hash_map_const_iterator& operator++() {++__i_; return *this;}
690 _LIBCPP_INLINE_VISIBILITY
691 __hash_map_const_iterator operator++(int)
693 __hash_map_const_iterator __t(*this);
698 friend _LIBCPP_INLINE_VISIBILITY
699 bool operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)
700 {return __x.__i_ == __y.__i_;}
701 friend _LIBCPP_INLINE_VISIBILITY
702 bool operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)
703 {return __x.__i_ != __y.__i_;}
705 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map;
706 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap;
707 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator;
708 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator;
711 template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
712 class _Alloc = allocator<pair<const _Key, _Tp> > >
713 class _LIBCPP_TYPE_VIS_ONLY unordered_map
717 typedef _Key key_type;
718 typedef _Tp mapped_type;
719 typedef _Hash hasher;
720 typedef _Pred key_equal;
721 typedef _Alloc allocator_type;
722 typedef pair<const key_type, mapped_type> value_type;
723 typedef pair<key_type, mapped_type> __nc_value_type;
724 typedef value_type& reference;
725 typedef const value_type& const_reference;
726 static_assert((is_same<value_type, typename allocator_type::value_type>::value),
727 "Invalid allocator::value_type");
730 typedef __hash_value_type<key_type, mapped_type> __value_type;
731 typedef __unordered_map_hasher<key_type, __value_type, hasher> __hasher;
732 typedef __unordered_map_equal<key_type, __value_type, key_equal> __key_equal;
733 typedef typename allocator_traits<allocator_type>::template
734 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
735 rebind_alloc<__value_type>
737 rebind_alloc<__value_type>::other
741 typedef __hash_table<__value_type, __hasher,
742 __key_equal, __allocator_type> __table;
746 typedef typename __table::__node_pointer __node_pointer;
747 typedef typename __table::__node_const_pointer __node_const_pointer;
748 typedef typename __table::__node_traits __node_traits;
749 typedef typename __table::__node_allocator __node_allocator;
750 typedef typename __table::__node __node;
751 typedef __hash_map_node_destructor<__node_allocator> _Dp;
752 typedef unique_ptr<__node, _Dp> __node_holder;
753 typedef allocator_traits<allocator_type> __alloc_traits;
755 typedef typename __alloc_traits::pointer pointer;
756 typedef typename __alloc_traits::const_pointer const_pointer;
757 typedef typename __alloc_traits::size_type size_type;
758 typedef typename __alloc_traits::difference_type difference_type;
760 typedef __hash_map_iterator<typename __table::iterator> iterator;
761 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
762 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
763 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
765 _LIBCPP_INLINE_VISIBILITY
767 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
769 #if _LIBCPP_DEBUG_LEVEL >= 2
770 __get_db()->__insert_c(this);
773 explicit unordered_map(size_type __n, const hasher& __hf = hasher(),
774 const key_equal& __eql = key_equal());
775 unordered_map(size_type __n, const hasher& __hf,
776 const key_equal& __eql,
777 const allocator_type& __a);
778 template <class _InputIterator>
779 unordered_map(_InputIterator __first, _InputIterator __last);
780 template <class _InputIterator>
781 unordered_map(_InputIterator __first, _InputIterator __last,
782 size_type __n, const hasher& __hf = hasher(),
783 const key_equal& __eql = key_equal());
784 template <class _InputIterator>
785 unordered_map(_InputIterator __first, _InputIterator __last,
786 size_type __n, const hasher& __hf,
787 const key_equal& __eql,
788 const allocator_type& __a);
789 explicit unordered_map(const allocator_type& __a);
790 unordered_map(const unordered_map& __u);
791 unordered_map(const unordered_map& __u, const allocator_type& __a);
792 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
793 unordered_map(unordered_map&& __u)
794 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
795 unordered_map(unordered_map&& __u, const allocator_type& __a);
796 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
797 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
798 unordered_map(initializer_list<value_type> __il);
799 unordered_map(initializer_list<value_type> __il, size_type __n,
800 const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
801 unordered_map(initializer_list<value_type> __il, size_type __n,
802 const hasher& __hf, const key_equal& __eql,
803 const allocator_type& __a);
804 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
805 #if _LIBCPP_STD_VER > 11
806 _LIBCPP_INLINE_VISIBILITY
807 unordered_map(size_type __n, const allocator_type& __a)
808 : unordered_map(__n, hasher(), key_equal(), __a) {}
809 _LIBCPP_INLINE_VISIBILITY
810 unordered_map(size_type __n, const hasher& __hf, const allocator_type& __a)
811 : unordered_map(__n, __hf, key_equal(), __a) {}
812 template <class _InputIterator>
813 _LIBCPP_INLINE_VISIBILITY
814 unordered_map(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a)
815 : unordered_map(__first, __last, __n, hasher(), key_equal(), __a) {}
816 template <class _InputIterator>
817 _LIBCPP_INLINE_VISIBILITY
818 unordered_map(_InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf,
819 const allocator_type& __a)
820 : unordered_map(__first, __last, __n, __hf, key_equal(), __a) {}
821 _LIBCPP_INLINE_VISIBILITY
822 unordered_map(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)
823 : unordered_map(__il, __n, hasher(), key_equal(), __a) {}
824 _LIBCPP_INLINE_VISIBILITY
825 unordered_map(initializer_list<value_type> __il, size_type __n, const hasher& __hf,
826 const allocator_type& __a)
827 : unordered_map(__il, __n, __hf, key_equal(), __a) {}
829 // ~unordered_map() = default;
830 _LIBCPP_INLINE_VISIBILITY
831 unordered_map& operator=(const unordered_map& __u)
833 #if __cplusplus >= 201103L
834 __table_ = __u.__table_;
838 __table_.hash_function() = __u.__table_.hash_function();
839 __table_.key_eq() = __u.__table_.key_eq();
840 __table_.max_load_factor() = __u.__table_.max_load_factor();
841 __table_.__copy_assign_alloc(__u.__table_);
842 insert(__u.begin(), __u.end());
847 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
848 unordered_map& operator=(unordered_map&& __u)
849 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
851 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
852 unordered_map& operator=(initializer_list<value_type> __il);
853 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
855 _LIBCPP_INLINE_VISIBILITY
856 allocator_type get_allocator() const _NOEXCEPT
857 {return allocator_type(__table_.__node_alloc());}
859 _LIBCPP_INLINE_VISIBILITY
860 bool empty() const _NOEXCEPT {return __table_.size() == 0;}
861 _LIBCPP_INLINE_VISIBILITY
862 size_type size() const _NOEXCEPT {return __table_.size();}
863 _LIBCPP_INLINE_VISIBILITY
864 size_type max_size() const _NOEXCEPT {return __table_.max_size();}
866 _LIBCPP_INLINE_VISIBILITY
867 iterator begin() _NOEXCEPT {return __table_.begin();}
868 _LIBCPP_INLINE_VISIBILITY
869 iterator end() _NOEXCEPT {return __table_.end();}
870 _LIBCPP_INLINE_VISIBILITY
871 const_iterator begin() const _NOEXCEPT {return __table_.begin();}
872 _LIBCPP_INLINE_VISIBILITY
873 const_iterator end() const _NOEXCEPT {return __table_.end();}
874 _LIBCPP_INLINE_VISIBILITY
875 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
876 _LIBCPP_INLINE_VISIBILITY
877 const_iterator cend() const _NOEXCEPT {return __table_.end();}
879 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
880 #ifndef _LIBCPP_HAS_NO_VARIADICS
882 template <class... _Args>
883 pair<iterator, bool> emplace(_Args&&... __args);
885 template <class... _Args>
886 _LIBCPP_INLINE_VISIBILITY
887 #if _LIBCPP_DEBUG_LEVEL >= 2
888 iterator emplace_hint(const_iterator __p, _Args&&... __args)
890 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
891 "unordered_map::emplace_hint(const_iterator, args...) called with an iterator not"
892 " referring to this unordered_map");
893 return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first;
896 iterator emplace_hint(const_iterator, _Args&&... __args)
897 {return emplace(_VSTD::forward<_Args>(__args)...).first;}
899 #endif // _LIBCPP_HAS_NO_VARIADICS
900 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
901 _LIBCPP_INLINE_VISIBILITY
902 pair<iterator, bool> insert(const value_type& __x)
903 {return __table_.__insert_unique(__x);}
904 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
906 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
907 _LIBCPP_INLINE_VISIBILITY
908 pair<iterator, bool> insert(_Pp&& __x)
909 {return __table_.__insert_unique(_VSTD::forward<_Pp>(__x));}
910 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
911 _LIBCPP_INLINE_VISIBILITY
912 #if _LIBCPP_DEBUG_LEVEL >= 2
913 iterator insert(const_iterator __p, const value_type& __x)
915 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
916 "unordered_map::insert(const_iterator, const value_type&) called with an iterator not"
917 " referring to this unordered_map");
918 return insert(__x).first;
921 iterator insert(const_iterator, const value_type& __x)
922 {return insert(__x).first;}
924 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
926 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
927 _LIBCPP_INLINE_VISIBILITY
928 #if _LIBCPP_DEBUG_LEVEL >= 2
929 iterator insert(const_iterator __p, _Pp&& __x)
931 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
932 "unordered_map::insert(const_iterator, value_type&&) called with an iterator not"
933 " referring to this unordered_map");
934 return insert(_VSTD::forward<_Pp>(__x)).first;
937 iterator insert(const_iterator, _Pp&& __x)
938 {return insert(_VSTD::forward<_Pp>(__x)).first;}
940 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
941 template <class _InputIterator>
942 void insert(_InputIterator __first, _InputIterator __last);
943 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
944 _LIBCPP_INLINE_VISIBILITY
945 void insert(initializer_list<value_type> __il)
946 {insert(__il.begin(), __il.end());}
947 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
949 _LIBCPP_INLINE_VISIBILITY
950 iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);}
951 _LIBCPP_INLINE_VISIBILITY
952 size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
953 _LIBCPP_INLINE_VISIBILITY
954 iterator erase(const_iterator __first, const_iterator __last)
955 {return __table_.erase(__first.__i_, __last.__i_);}
956 _LIBCPP_INLINE_VISIBILITY
957 void clear() _NOEXCEPT {__table_.clear();}
959 _LIBCPP_INLINE_VISIBILITY
960 void swap(unordered_map& __u)
961 _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
962 {__table_.swap(__u.__table_);}
964 _LIBCPP_INLINE_VISIBILITY
965 hasher hash_function() const
966 {return __table_.hash_function().hash_function();}
967 _LIBCPP_INLINE_VISIBILITY
968 key_equal key_eq() const
969 {return __table_.key_eq().key_eq();}
971 _LIBCPP_INLINE_VISIBILITY
972 iterator find(const key_type& __k) {return __table_.find(__k);}
973 _LIBCPP_INLINE_VISIBILITY
974 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
975 _LIBCPP_INLINE_VISIBILITY
976 size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
977 _LIBCPP_INLINE_VISIBILITY
978 pair<iterator, iterator> equal_range(const key_type& __k)
979 {return __table_.__equal_range_unique(__k);}
980 _LIBCPP_INLINE_VISIBILITY
981 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
982 {return __table_.__equal_range_unique(__k);}
984 mapped_type& operator[](const key_type& __k);
985 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
986 mapped_type& operator[](key_type&& __k);
989 mapped_type& at(const key_type& __k);
990 const mapped_type& at(const key_type& __k) const;
992 _LIBCPP_INLINE_VISIBILITY
993 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
994 _LIBCPP_INLINE_VISIBILITY
995 size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
997 _LIBCPP_INLINE_VISIBILITY
998 size_type bucket_size(size_type __n) const
999 {return __table_.bucket_size(__n);}
1000 _LIBCPP_INLINE_VISIBILITY
1001 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
1003 _LIBCPP_INLINE_VISIBILITY
1004 local_iterator begin(size_type __n) {return __table_.begin(__n);}
1005 _LIBCPP_INLINE_VISIBILITY
1006 local_iterator end(size_type __n) {return __table_.end(__n);}
1007 _LIBCPP_INLINE_VISIBILITY
1008 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);}
1009 _LIBCPP_INLINE_VISIBILITY
1010 const_local_iterator end(size_type __n) const {return __table_.cend(__n);}
1011 _LIBCPP_INLINE_VISIBILITY
1012 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
1013 _LIBCPP_INLINE_VISIBILITY
1014 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);}
1016 _LIBCPP_INLINE_VISIBILITY
1017 float load_factor() const _NOEXCEPT {return __table_.load_factor();}
1018 _LIBCPP_INLINE_VISIBILITY
1019 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
1020 _LIBCPP_INLINE_VISIBILITY
1021 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
1022 _LIBCPP_INLINE_VISIBILITY
1023 void rehash(size_type __n) {__table_.rehash(__n);}
1024 _LIBCPP_INLINE_VISIBILITY
1025 void reserve(size_type __n) {__table_.reserve(__n);}
1027 #if _LIBCPP_DEBUG_LEVEL >= 2
1029 bool __dereferenceable(const const_iterator* __i) const
1030 {return __table_.__dereferenceable(&__i->__i_);}
1031 bool __decrementable(const const_iterator* __i) const
1032 {return __table_.__decrementable(&__i->__i_);}
1033 bool __addable(const const_iterator* __i, ptrdiff_t __n) const
1034 {return __table_.__addable(&__i->__i_, __n);}
1035 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
1036 {return __table_.__addable(&__i->__i_, __n);}
1038 #endif // _LIBCPP_DEBUG_LEVEL >= 2
1041 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1042 __node_holder __construct_node();
1043 template <class _A0>
1045 __construct_node(_A0&& __a0);
1046 __node_holder __construct_node_with_key(key_type&& __k);
1047 #ifndef _LIBCPP_HAS_NO_VARIADICS
1048 template <class _A0, class _A1, class ..._Args>
1049 __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args);
1050 #endif // _LIBCPP_HAS_NO_VARIADICS
1051 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1052 __node_holder __construct_node_with_key(const key_type& __k);
1055 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1056 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1057 size_type __n, const hasher& __hf, const key_equal& __eql)
1058 : __table_(__hf, __eql)
1060 #if _LIBCPP_DEBUG_LEVEL >= 2
1061 __get_db()->__insert_c(this);
1063 __table_.rehash(__n);
1066 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1067 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1068 size_type __n, const hasher& __hf, const key_equal& __eql,
1069 const allocator_type& __a)
1070 : __table_(__hf, __eql, __a)
1072 #if _LIBCPP_DEBUG_LEVEL >= 2
1073 __get_db()->__insert_c(this);
1075 __table_.rehash(__n);
1078 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1079 inline _LIBCPP_INLINE_VISIBILITY
1080 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1081 const allocator_type& __a)
1084 #if _LIBCPP_DEBUG_LEVEL >= 2
1085 __get_db()->__insert_c(this);
1089 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1090 template <class _InputIterator>
1091 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1092 _InputIterator __first, _InputIterator __last)
1094 #if _LIBCPP_DEBUG_LEVEL >= 2
1095 __get_db()->__insert_c(this);
1097 insert(__first, __last);
1100 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1101 template <class _InputIterator>
1102 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1103 _InputIterator __first, _InputIterator __last, size_type __n,
1104 const hasher& __hf, const key_equal& __eql)
1105 : __table_(__hf, __eql)
1107 #if _LIBCPP_DEBUG_LEVEL >= 2
1108 __get_db()->__insert_c(this);
1110 __table_.rehash(__n);
1111 insert(__first, __last);
1114 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1115 template <class _InputIterator>
1116 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1117 _InputIterator __first, _InputIterator __last, size_type __n,
1118 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1119 : __table_(__hf, __eql, __a)
1121 #if _LIBCPP_DEBUG_LEVEL >= 2
1122 __get_db()->__insert_c(this);
1124 __table_.rehash(__n);
1125 insert(__first, __last);
1128 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1129 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1130 const unordered_map& __u)
1131 : __table_(__u.__table_)
1133 #if _LIBCPP_DEBUG_LEVEL >= 2
1134 __get_db()->__insert_c(this);
1136 __table_.rehash(__u.bucket_count());
1137 insert(__u.begin(), __u.end());
1140 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1141 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1142 const unordered_map& __u, const allocator_type& __a)
1143 : __table_(__u.__table_, __a)
1145 #if _LIBCPP_DEBUG_LEVEL >= 2
1146 __get_db()->__insert_c(this);
1148 __table_.rehash(__u.bucket_count());
1149 insert(__u.begin(), __u.end());
1152 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1154 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1155 inline _LIBCPP_INLINE_VISIBILITY
1156 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1157 unordered_map&& __u)
1158 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
1159 : __table_(_VSTD::move(__u.__table_))
1161 #if _LIBCPP_DEBUG_LEVEL >= 2
1162 __get_db()->__insert_c(this);
1163 __get_db()->swap(this, &__u);
1167 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1168 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1169 unordered_map&& __u, const allocator_type& __a)
1170 : __table_(_VSTD::move(__u.__table_), __a)
1172 #if _LIBCPP_DEBUG_LEVEL >= 2
1173 __get_db()->__insert_c(this);
1175 if (__a != __u.get_allocator())
1177 iterator __i = __u.begin();
1178 while (__u.size() != 0)
1179 __table_.__insert_unique(
1180 _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_)
1183 #if _LIBCPP_DEBUG_LEVEL >= 2
1185 __get_db()->swap(this, &__u);
1189 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1191 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1193 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1194 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1195 initializer_list<value_type> __il)
1197 #if _LIBCPP_DEBUG_LEVEL >= 2
1198 __get_db()->__insert_c(this);
1200 insert(__il.begin(), __il.end());
1203 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1204 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1205 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1206 const key_equal& __eql)
1207 : __table_(__hf, __eql)
1209 #if _LIBCPP_DEBUG_LEVEL >= 2
1210 __get_db()->__insert_c(this);
1212 __table_.rehash(__n);
1213 insert(__il.begin(), __il.end());
1216 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1217 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1218 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1219 const key_equal& __eql, const allocator_type& __a)
1220 : __table_(__hf, __eql, __a)
1222 #if _LIBCPP_DEBUG_LEVEL >= 2
1223 __get_db()->__insert_c(this);
1225 __table_.rehash(__n);
1226 insert(__il.begin(), __il.end());
1229 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1231 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1233 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1234 inline _LIBCPP_INLINE_VISIBILITY
1235 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
1236 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_map&& __u)
1237 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
1239 __table_ = _VSTD::move(__u.__table_);
1243 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1245 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1247 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1248 inline _LIBCPP_INLINE_VISIBILITY
1249 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
1250 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(
1251 initializer_list<value_type> __il)
1253 __table_.__assign_unique(__il.begin(), __il.end());
1257 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1259 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1261 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1262 typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1263 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node()
1265 __node_allocator& __na = __table_.__node_alloc();
1266 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1267 __node_traits::construct(__na, _VSTD::addressof(__h->__value_));
1268 __h.get_deleter().__first_constructed = true;
1269 __h.get_deleter().__second_constructed = true;
1273 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1274 template <class _A0>
1275 typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1276 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
1278 __node_allocator& __na = __table_.__node_alloc();
1279 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1280 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1281 _VSTD::forward<_A0>(__a0));
1282 __h.get_deleter().__first_constructed = true;
1283 __h.get_deleter().__second_constructed = true;
1287 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1288 typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1289 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(key_type&& __k)
1291 __node_allocator& __na = __table_.__node_alloc();
1292 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1293 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), _VSTD::move(__k));
1294 __h.get_deleter().__first_constructed = true;
1295 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
1296 __h.get_deleter().__second_constructed = true;
1300 #ifndef _LIBCPP_HAS_NO_VARIADICS
1302 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1303 template <class _A0, class _A1, class ..._Args>
1304 typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1305 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0,
1309 __node_allocator& __na = __table_.__node_alloc();
1310 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1311 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1312 _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1),
1313 _VSTD::forward<_Args>(__args)...);
1314 __h.get_deleter().__first_constructed = true;
1315 __h.get_deleter().__second_constructed = true;
1319 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1320 template <class... _Args>
1321 pair<typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator, bool>
1322 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_Args&&... __args)
1324 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1325 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1331 #endif // _LIBCPP_HAS_NO_VARIADICS
1332 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1334 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1335 typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1336 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(const key_type& __k)
1338 __node_allocator& __na = __table_.__node_alloc();
1339 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1340 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), __k);
1341 __h.get_deleter().__first_constructed = true;
1342 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
1343 __h.get_deleter().__second_constructed = true;
1344 return _VSTD::move(__h); // explicitly moved for C++03
1347 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1348 template <class _InputIterator>
1349 inline _LIBCPP_INLINE_VISIBILITY
1351 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
1352 _InputIterator __last)
1354 for (; __first != __last; ++__first)
1355 __table_.__insert_unique(*__first);
1358 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1360 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k)
1362 iterator __i = find(__k);
1365 __node_holder __h = __construct_node_with_key(__k);
1366 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1368 return __r.first->second;
1371 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1373 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1375 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&& __k)
1377 iterator __i = find(__k);
1380 __node_holder __h = __construct_node_with_key(_VSTD::move(__k));
1381 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1383 return __r.first->second;
1386 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1388 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1390 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k)
1392 iterator __i = find(__k);
1393 #ifndef _LIBCPP_NO_EXCEPTIONS
1395 throw out_of_range("unordered_map::at: key not found");
1396 #endif // _LIBCPP_NO_EXCEPTIONS
1400 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1402 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) const
1404 const_iterator __i = find(__k);
1405 #ifndef _LIBCPP_NO_EXCEPTIONS
1407 throw out_of_range("unordered_map::at: key not found");
1408 #endif // _LIBCPP_NO_EXCEPTIONS
1412 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1413 inline _LIBCPP_INLINE_VISIBILITY
1415 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1416 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1417 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1422 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1424 operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1425 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1427 if (__x.size() != __y.size())
1429 typedef typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
1431 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();
1434 const_iterator __j = __y.find(__i->first);
1435 if (__j == __ey || !(*__i == *__j))
1441 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1442 inline _LIBCPP_INLINE_VISIBILITY
1444 operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1445 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1447 return !(__x == __y);
1450 template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
1451 class _Alloc = allocator<pair<const _Key, _Tp> > >
1452 class _LIBCPP_TYPE_VIS_ONLY unordered_multimap
1456 typedef _Key key_type;
1457 typedef _Tp mapped_type;
1458 typedef _Hash hasher;
1459 typedef _Pred key_equal;
1460 typedef _Alloc allocator_type;
1461 typedef pair<const key_type, mapped_type> value_type;
1462 typedef pair<key_type, mapped_type> __nc_value_type;
1463 typedef value_type& reference;
1464 typedef const value_type& const_reference;
1465 static_assert((is_same<value_type, typename allocator_type::value_type>::value),
1466 "Invalid allocator::value_type");
1469 typedef __hash_value_type<key_type, mapped_type> __value_type;
1470 typedef __unordered_map_hasher<key_type, __value_type, hasher> __hasher;
1471 typedef __unordered_map_equal<key_type, __value_type, key_equal> __key_equal;
1472 typedef typename allocator_traits<allocator_type>::template
1473 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
1474 rebind_alloc<__value_type>
1476 rebind_alloc<__value_type>::other
1480 typedef __hash_table<__value_type, __hasher,
1481 __key_equal, __allocator_type> __table;
1485 typedef typename __table::__node_traits __node_traits;
1486 typedef typename __table::__node_allocator __node_allocator;
1487 typedef typename __table::__node __node;
1488 typedef __hash_map_node_destructor<__node_allocator> _Dp;
1489 typedef unique_ptr<__node, _Dp> __node_holder;
1490 typedef allocator_traits<allocator_type> __alloc_traits;
1492 typedef typename __alloc_traits::pointer pointer;
1493 typedef typename __alloc_traits::const_pointer const_pointer;
1494 typedef typename __alloc_traits::size_type size_type;
1495 typedef typename __alloc_traits::difference_type difference_type;
1497 typedef __hash_map_iterator<typename __table::iterator> iterator;
1498 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
1499 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
1500 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
1502 _LIBCPP_INLINE_VISIBILITY
1503 unordered_multimap()
1504 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
1506 #if _LIBCPP_DEBUG_LEVEL >= 2
1507 __get_db()->__insert_c(this);
1510 explicit unordered_multimap(size_type __n, const hasher& __hf = hasher(),
1511 const key_equal& __eql = key_equal());
1512 unordered_multimap(size_type __n, const hasher& __hf,
1513 const key_equal& __eql,
1514 const allocator_type& __a);
1515 template <class _InputIterator>
1516 unordered_multimap(_InputIterator __first, _InputIterator __last);
1517 template <class _InputIterator>
1518 unordered_multimap(_InputIterator __first, _InputIterator __last,
1519 size_type __n, const hasher& __hf = hasher(),
1520 const key_equal& __eql = key_equal());
1521 template <class _InputIterator>
1522 unordered_multimap(_InputIterator __first, _InputIterator __last,
1523 size_type __n, const hasher& __hf,
1524 const key_equal& __eql,
1525 const allocator_type& __a);
1526 explicit unordered_multimap(const allocator_type& __a);
1527 unordered_multimap(const unordered_multimap& __u);
1528 unordered_multimap(const unordered_multimap& __u, const allocator_type& __a);
1529 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1530 unordered_multimap(unordered_multimap&& __u)
1531 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
1532 unordered_multimap(unordered_multimap&& __u, const allocator_type& __a);
1533 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1534 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1535 unordered_multimap(initializer_list<value_type> __il);
1536 unordered_multimap(initializer_list<value_type> __il, size_type __n,
1537 const hasher& __hf = hasher(),
1538 const key_equal& __eql = key_equal());
1539 unordered_multimap(initializer_list<value_type> __il, size_type __n,
1540 const hasher& __hf, const key_equal& __eql,
1541 const allocator_type& __a);
1542 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1543 #if _LIBCPP_STD_VER > 11
1544 _LIBCPP_INLINE_VISIBILITY
1545 unordered_multimap(size_type __n, const allocator_type& __a)
1546 : unordered_multimap(__n, hasher(), key_equal(), __a) {}
1547 _LIBCPP_INLINE_VISIBILITY
1548 unordered_multimap(size_type __n, const hasher& __hf, const allocator_type& __a)
1549 : unordered_multimap(__n, __hf, key_equal(), __a) {}
1550 template <class _InputIterator>
1551 _LIBCPP_INLINE_VISIBILITY
1552 unordered_multimap(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a)
1553 : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a) {}
1554 template <class _InputIterator>
1555 _LIBCPP_INLINE_VISIBILITY
1556 unordered_multimap(_InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf,
1557 const allocator_type& __a)
1558 : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a) {}
1559 _LIBCPP_INLINE_VISIBILITY
1560 unordered_multimap(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)
1561 : unordered_multimap(__il, __n, hasher(), key_equal(), __a) {}
1562 _LIBCPP_INLINE_VISIBILITY
1563 unordered_multimap(initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1564 const allocator_type& __a)
1565 : unordered_multimap(__il, __n, __hf, key_equal(), __a) {}
1567 // ~unordered_multimap() = default;
1568 _LIBCPP_INLINE_VISIBILITY
1569 unordered_multimap& operator=(const unordered_multimap& __u)
1571 #if __cplusplus >= 201103L
1572 __table_ = __u.__table_;
1576 __table_.hash_function() = __u.__table_.hash_function();
1577 __table_.key_eq() = __u.__table_.key_eq();
1578 __table_.max_load_factor() = __u.__table_.max_load_factor();
1579 __table_.__copy_assign_alloc(__u.__table_);
1580 insert(__u.begin(), __u.end());
1585 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1586 unordered_multimap& operator=(unordered_multimap&& __u)
1587 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
1589 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1590 unordered_multimap& operator=(initializer_list<value_type> __il);
1591 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1593 _LIBCPP_INLINE_VISIBILITY
1594 allocator_type get_allocator() const _NOEXCEPT
1595 {return allocator_type(__table_.__node_alloc());}
1597 _LIBCPP_INLINE_VISIBILITY
1598 bool empty() const _NOEXCEPT {return __table_.size() == 0;}
1599 _LIBCPP_INLINE_VISIBILITY
1600 size_type size() const _NOEXCEPT {return __table_.size();}
1601 _LIBCPP_INLINE_VISIBILITY
1602 size_type max_size() const _NOEXCEPT {return __table_.max_size();}
1604 _LIBCPP_INLINE_VISIBILITY
1605 iterator begin() _NOEXCEPT {return __table_.begin();}
1606 _LIBCPP_INLINE_VISIBILITY
1607 iterator end() _NOEXCEPT {return __table_.end();}
1608 _LIBCPP_INLINE_VISIBILITY
1609 const_iterator begin() const _NOEXCEPT {return __table_.begin();}
1610 _LIBCPP_INLINE_VISIBILITY
1611 const_iterator end() const _NOEXCEPT {return __table_.end();}
1612 _LIBCPP_INLINE_VISIBILITY
1613 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
1614 _LIBCPP_INLINE_VISIBILITY
1615 const_iterator cend() const _NOEXCEPT {return __table_.end();}
1617 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1618 #ifndef _LIBCPP_HAS_NO_VARIADICS
1620 template <class... _Args>
1621 iterator emplace(_Args&&... __args);
1623 template <class... _Args>
1624 iterator emplace_hint(const_iterator __p, _Args&&... __args);
1625 #endif // _LIBCPP_HAS_NO_VARIADICS
1626 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1627 _LIBCPP_INLINE_VISIBILITY
1628 iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
1629 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1630 template <class _Pp,
1631 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1632 _LIBCPP_INLINE_VISIBILITY
1633 iterator insert(_Pp&& __x)
1634 {return __table_.__insert_multi(_VSTD::forward<_Pp>(__x));}
1635 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1636 _LIBCPP_INLINE_VISIBILITY
1637 iterator insert(const_iterator __p, const value_type& __x)
1638 {return __table_.__insert_multi(__p.__i_, __x);}
1639 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1640 template <class _Pp,
1641 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1642 _LIBCPP_INLINE_VISIBILITY
1643 iterator insert(const_iterator __p, _Pp&& __x)
1644 {return __table_.__insert_multi(__p.__i_, _VSTD::forward<_Pp>(__x));}
1645 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1646 template <class _InputIterator>
1647 void insert(_InputIterator __first, _InputIterator __last);
1648 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1649 _LIBCPP_INLINE_VISIBILITY
1650 void insert(initializer_list<value_type> __il)
1651 {insert(__il.begin(), __il.end());}
1652 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1654 _LIBCPP_INLINE_VISIBILITY
1655 iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);}
1656 _LIBCPP_INLINE_VISIBILITY
1657 size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
1658 _LIBCPP_INLINE_VISIBILITY
1659 iterator erase(const_iterator __first, const_iterator __last)
1660 {return __table_.erase(__first.__i_, __last.__i_);}
1661 _LIBCPP_INLINE_VISIBILITY
1662 void clear() _NOEXCEPT {__table_.clear();}
1664 _LIBCPP_INLINE_VISIBILITY
1665 void swap(unordered_multimap& __u)
1666 _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
1667 {__table_.swap(__u.__table_);}
1669 _LIBCPP_INLINE_VISIBILITY
1670 hasher hash_function() const
1671 {return __table_.hash_function().hash_function();}
1672 _LIBCPP_INLINE_VISIBILITY
1673 key_equal key_eq() const
1674 {return __table_.key_eq().key_eq();}
1676 _LIBCPP_INLINE_VISIBILITY
1677 iterator find(const key_type& __k) {return __table_.find(__k);}
1678 _LIBCPP_INLINE_VISIBILITY
1679 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
1680 _LIBCPP_INLINE_VISIBILITY
1681 size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
1682 _LIBCPP_INLINE_VISIBILITY
1683 pair<iterator, iterator> equal_range(const key_type& __k)
1684 {return __table_.__equal_range_multi(__k);}
1685 _LIBCPP_INLINE_VISIBILITY
1686 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
1687 {return __table_.__equal_range_multi(__k);}
1689 _LIBCPP_INLINE_VISIBILITY
1690 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
1691 _LIBCPP_INLINE_VISIBILITY
1692 size_type max_bucket_count() const _NOEXCEPT
1693 {return __table_.max_bucket_count();}
1695 _LIBCPP_INLINE_VISIBILITY
1696 size_type bucket_size(size_type __n) const
1697 {return __table_.bucket_size(__n);}
1698 _LIBCPP_INLINE_VISIBILITY
1699 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
1701 _LIBCPP_INLINE_VISIBILITY
1702 local_iterator begin(size_type __n) {return __table_.begin(__n);}
1703 _LIBCPP_INLINE_VISIBILITY
1704 local_iterator end(size_type __n) {return __table_.end(__n);}
1705 _LIBCPP_INLINE_VISIBILITY
1706 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);}
1707 _LIBCPP_INLINE_VISIBILITY
1708 const_local_iterator end(size_type __n) const {return __table_.cend(__n);}
1709 _LIBCPP_INLINE_VISIBILITY
1710 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
1711 _LIBCPP_INLINE_VISIBILITY
1712 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);}
1714 _LIBCPP_INLINE_VISIBILITY
1715 float load_factor() const _NOEXCEPT {return __table_.load_factor();}
1716 _LIBCPP_INLINE_VISIBILITY
1717 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
1718 _LIBCPP_INLINE_VISIBILITY
1719 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
1720 _LIBCPP_INLINE_VISIBILITY
1721 void rehash(size_type __n) {__table_.rehash(__n);}
1722 _LIBCPP_INLINE_VISIBILITY
1723 void reserve(size_type __n) {__table_.reserve(__n);}
1725 #if _LIBCPP_DEBUG_LEVEL >= 2
1727 bool __dereferenceable(const const_iterator* __i) const
1728 {return __table_.__dereferenceable(&__i->__i_);}
1729 bool __decrementable(const const_iterator* __i) const
1730 {return __table_.__decrementable(&__i->__i_);}
1731 bool __addable(const const_iterator* __i, ptrdiff_t __n) const
1732 {return __table_.__addable(&__i->__i_, __n);}
1733 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
1734 {return __table_.__addable(&__i->__i_, __n);}
1736 #endif // _LIBCPP_DEBUG_LEVEL >= 2
1739 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1740 __node_holder __construct_node();
1741 template <class _A0>
1743 __construct_node(_A0&& __a0);
1744 #ifndef _LIBCPP_HAS_NO_VARIADICS
1745 template <class _A0, class _A1, class ..._Args>
1746 __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args);
1747 #endif // _LIBCPP_HAS_NO_VARIADICS
1748 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1751 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1752 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1753 size_type __n, const hasher& __hf, const key_equal& __eql)
1754 : __table_(__hf, __eql)
1756 #if _LIBCPP_DEBUG_LEVEL >= 2
1757 __get_db()->__insert_c(this);
1759 __table_.rehash(__n);
1762 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1763 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1764 size_type __n, const hasher& __hf, const key_equal& __eql,
1765 const allocator_type& __a)
1766 : __table_(__hf, __eql, __a)
1768 #if _LIBCPP_DEBUG_LEVEL >= 2
1769 __get_db()->__insert_c(this);
1771 __table_.rehash(__n);
1774 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1775 template <class _InputIterator>
1776 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1777 _InputIterator __first, _InputIterator __last)
1779 #if _LIBCPP_DEBUG_LEVEL >= 2
1780 __get_db()->__insert_c(this);
1782 insert(__first, __last);
1785 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1786 template <class _InputIterator>
1787 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1788 _InputIterator __first, _InputIterator __last, size_type __n,
1789 const hasher& __hf, const key_equal& __eql)
1790 : __table_(__hf, __eql)
1792 #if _LIBCPP_DEBUG_LEVEL >= 2
1793 __get_db()->__insert_c(this);
1795 __table_.rehash(__n);
1796 insert(__first, __last);
1799 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1800 template <class _InputIterator>
1801 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1802 _InputIterator __first, _InputIterator __last, size_type __n,
1803 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1804 : __table_(__hf, __eql, __a)
1806 #if _LIBCPP_DEBUG_LEVEL >= 2
1807 __get_db()->__insert_c(this);
1809 __table_.rehash(__n);
1810 insert(__first, __last);
1813 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1814 inline _LIBCPP_INLINE_VISIBILITY
1815 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1816 const allocator_type& __a)
1819 #if _LIBCPP_DEBUG_LEVEL >= 2
1820 __get_db()->__insert_c(this);
1824 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1825 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1826 const unordered_multimap& __u)
1827 : __table_(__u.__table_)
1829 #if _LIBCPP_DEBUG_LEVEL >= 2
1830 __get_db()->__insert_c(this);
1832 __table_.rehash(__u.bucket_count());
1833 insert(__u.begin(), __u.end());
1836 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1837 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1838 const unordered_multimap& __u, const allocator_type& __a)
1839 : __table_(__u.__table_, __a)
1841 #if _LIBCPP_DEBUG_LEVEL >= 2
1842 __get_db()->__insert_c(this);
1844 __table_.rehash(__u.bucket_count());
1845 insert(__u.begin(), __u.end());
1848 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1850 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1851 inline _LIBCPP_INLINE_VISIBILITY
1852 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1853 unordered_multimap&& __u)
1854 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
1855 : __table_(_VSTD::move(__u.__table_))
1857 #if _LIBCPP_DEBUG_LEVEL >= 2
1858 __get_db()->__insert_c(this);
1859 __get_db()->swap(this, &__u);
1863 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1864 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1865 unordered_multimap&& __u, const allocator_type& __a)
1866 : __table_(_VSTD::move(__u.__table_), __a)
1868 #if _LIBCPP_DEBUG_LEVEL >= 2
1869 __get_db()->__insert_c(this);
1871 if (__a != __u.get_allocator())
1873 iterator __i = __u.begin();
1874 while (__u.size() != 0)
1876 __table_.__insert_multi(
1877 _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_)
1881 #if _LIBCPP_DEBUG_LEVEL >= 2
1883 __get_db()->swap(this, &__u);
1887 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1889 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1891 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1892 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1893 initializer_list<value_type> __il)
1895 #if _LIBCPP_DEBUG_LEVEL >= 2
1896 __get_db()->__insert_c(this);
1898 insert(__il.begin(), __il.end());
1901 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1902 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1903 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1904 const key_equal& __eql)
1905 : __table_(__hf, __eql)
1907 #if _LIBCPP_DEBUG_LEVEL >= 2
1908 __get_db()->__insert_c(this);
1910 __table_.rehash(__n);
1911 insert(__il.begin(), __il.end());
1914 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1915 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1916 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1917 const key_equal& __eql, const allocator_type& __a)
1918 : __table_(__hf, __eql, __a)
1920 #if _LIBCPP_DEBUG_LEVEL >= 2
1921 __get_db()->__insert_c(this);
1923 __table_.rehash(__n);
1924 insert(__il.begin(), __il.end());
1927 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1929 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1931 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1932 inline _LIBCPP_INLINE_VISIBILITY
1933 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
1934 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_multimap&& __u)
1935 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
1937 __table_ = _VSTD::move(__u.__table_);
1941 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1943 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1945 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1946 inline _LIBCPP_INLINE_VISIBILITY
1947 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
1948 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(
1949 initializer_list<value_type> __il)
1951 __table_.__assign_multi(__il.begin(), __il.end());
1955 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1957 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1959 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1960 typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1961 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node()
1963 __node_allocator& __na = __table_.__node_alloc();
1964 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1965 __node_traits::construct(__na, _VSTD::addressof(__h->__value_));
1966 __h.get_deleter().__first_constructed = true;
1967 __h.get_deleter().__second_constructed = true;
1971 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1972 template <class _A0>
1973 typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1974 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
1976 __node_allocator& __na = __table_.__node_alloc();
1977 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1978 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1979 _VSTD::forward<_A0>(__a0));
1980 __h.get_deleter().__first_constructed = true;
1981 __h.get_deleter().__second_constructed = true;
1985 #ifndef _LIBCPP_HAS_NO_VARIADICS
1987 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1988 template <class _A0, class _A1, class ..._Args>
1989 typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1990 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(
1991 _A0&& __a0, _A1&& __a1, _Args&&... __args)
1993 __node_allocator& __na = __table_.__node_alloc();
1994 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1995 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1996 _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1),
1997 _VSTD::forward<_Args>(__args)...);
1998 __h.get_deleter().__first_constructed = true;
1999 __h.get_deleter().__second_constructed = true;
2003 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2004 template <class... _Args>
2005 typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator
2006 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_Args&&... __args)
2008 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
2009 iterator __r = __table_.__node_insert_multi(__h.get());
2014 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2015 template <class... _Args>
2016 typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator
2017 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace_hint(
2018 const_iterator __p, _Args&&... __args)
2020 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
2021 iterator __r = __table_.__node_insert_multi(__p.__i_, __h.get());
2026 #endif // _LIBCPP_HAS_NO_VARIADICS
2027 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
2029 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2030 template <class _InputIterator>
2031 inline _LIBCPP_INLINE_VISIBILITY
2033 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
2034 _InputIterator __last)
2036 for (; __first != __last; ++__first)
2037 __table_.__insert_multi(*__first);
2040 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2041 inline _LIBCPP_INLINE_VISIBILITY
2043 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2044 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2045 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
2050 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2052 operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2053 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2055 if (__x.size() != __y.size())
2057 typedef typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
2059 typedef pair<const_iterator, const_iterator> _EqRng;
2060 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;)
2062 _EqRng __xeq = __x.equal_range(__i->first);
2063 _EqRng __yeq = __y.equal_range(__i->first);
2064 if (_VSTD::distance(__xeq.first, __xeq.second) !=
2065 _VSTD::distance(__yeq.first, __yeq.second) ||
2066 !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first))
2073 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2074 inline _LIBCPP_INLINE_VISIBILITY
2076 operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2077 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2079 return !(__x == __y);
2082 _LIBCPP_END_NAMESPACE_STD
2084 #endif // _LIBCPP_UNORDERED_MAP