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>
354 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
355 #pragma GCC system_header
358 _LIBCPP_BEGIN_NAMESPACE_STD
360 template <class _Key, class _Cp, class _Hash, bool = is_empty<_Hash>::value
361 #if __has_feature(is_final)
362 && !__is_final(_Hash)
365 class __unordered_map_hasher
369 _LIBCPP_INLINE_VISIBILITY
370 __unordered_map_hasher()
371 _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value)
373 _LIBCPP_INLINE_VISIBILITY
374 __unordered_map_hasher(const _Hash& __h)
375 _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value)
377 _LIBCPP_INLINE_VISIBILITY
378 const _Hash& hash_function() const _NOEXCEPT {return *this;}
379 _LIBCPP_INLINE_VISIBILITY
380 size_t operator()(const _Cp& __x) const
381 {return static_cast<const _Hash&>(*this)(__x.__cc.first);}
382 _LIBCPP_INLINE_VISIBILITY
383 size_t operator()(const _Key& __x) const
384 {return static_cast<const _Hash&>(*this)(__x);}
387 template <class _Key, class _Cp, class _Hash>
388 class __unordered_map_hasher<_Key, _Cp, _Hash, false>
393 _LIBCPP_INLINE_VISIBILITY
394 __unordered_map_hasher()
395 _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value)
397 _LIBCPP_INLINE_VISIBILITY
398 __unordered_map_hasher(const _Hash& __h)
399 _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value)
401 _LIBCPP_INLINE_VISIBILITY
402 const _Hash& hash_function() const _NOEXCEPT {return __hash_;}
403 _LIBCPP_INLINE_VISIBILITY
404 size_t operator()(const _Cp& __x) const
405 {return __hash_(__x.__cc.first);}
406 _LIBCPP_INLINE_VISIBILITY
407 size_t operator()(const _Key& __x) const
408 {return __hash_(__x);}
411 template <class _Key, class _Cp, class _Pred, bool = is_empty<_Pred>::value
412 #if __has_feature(is_final)
413 && !__is_final(_Pred)
416 class __unordered_map_equal
420 _LIBCPP_INLINE_VISIBILITY
421 __unordered_map_equal()
422 _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value)
424 _LIBCPP_INLINE_VISIBILITY
425 __unordered_map_equal(const _Pred& __p)
426 _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value)
428 _LIBCPP_INLINE_VISIBILITY
429 const _Pred& key_eq() const _NOEXCEPT {return *this;}
430 _LIBCPP_INLINE_VISIBILITY
431 bool operator()(const _Cp& __x, const _Cp& __y) const
432 {return static_cast<const _Pred&>(*this)(__x.__cc.first, __y.__cc.first);}
433 _LIBCPP_INLINE_VISIBILITY
434 bool operator()(const _Cp& __x, const _Key& __y) const
435 {return static_cast<const _Pred&>(*this)(__x.__cc.first, __y);}
436 _LIBCPP_INLINE_VISIBILITY
437 bool operator()(const _Key& __x, const _Cp& __y) const
438 {return static_cast<const _Pred&>(*this)(__x, __y.__cc.first);}
441 template <class _Key, class _Cp, class _Pred>
442 class __unordered_map_equal<_Key, _Cp, _Pred, false>
447 _LIBCPP_INLINE_VISIBILITY
448 __unordered_map_equal()
449 _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value)
451 _LIBCPP_INLINE_VISIBILITY
452 __unordered_map_equal(const _Pred& __p)
453 _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value)
455 _LIBCPP_INLINE_VISIBILITY
456 const _Pred& key_eq() const _NOEXCEPT {return __pred_;}
457 _LIBCPP_INLINE_VISIBILITY
458 bool operator()(const _Cp& __x, const _Cp& __y) const
459 {return __pred_(__x.__cc.first, __y.__cc.first);}
460 _LIBCPP_INLINE_VISIBILITY
461 bool operator()(const _Cp& __x, const _Key& __y) const
462 {return __pred_(__x.__cc.first, __y);}
463 _LIBCPP_INLINE_VISIBILITY
464 bool operator()(const _Key& __x, const _Cp& __y) const
465 {return __pred_(__x, __y.__cc.first);}
468 template <class _Alloc>
469 class __hash_map_node_destructor
471 typedef _Alloc allocator_type;
472 typedef allocator_traits<allocator_type> __alloc_traits;
473 typedef typename __alloc_traits::value_type::value_type value_type;
475 typedef typename __alloc_traits::pointer pointer;
477 typedef typename value_type::value_type::first_type first_type;
478 typedef typename value_type::value_type::second_type second_type;
480 allocator_type& __na_;
482 __hash_map_node_destructor& operator=(const __hash_map_node_destructor&);
485 bool __first_constructed;
486 bool __second_constructed;
488 _LIBCPP_INLINE_VISIBILITY
489 explicit __hash_map_node_destructor(allocator_type& __na) _NOEXCEPT
491 __first_constructed(false),
492 __second_constructed(false)
495 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
496 _LIBCPP_INLINE_VISIBILITY
497 __hash_map_node_destructor(__hash_node_destructor<allocator_type>&& __x)
500 __first_constructed(__x.__value_constructed),
501 __second_constructed(__x.__value_constructed)
503 __x.__value_constructed = false;
505 #else // _LIBCPP_HAS_NO_RVALUE_REFERENCES
506 _LIBCPP_INLINE_VISIBILITY
507 __hash_map_node_destructor(const __hash_node_destructor<allocator_type>& __x)
509 __first_constructed(__x.__value_constructed),
510 __second_constructed(__x.__value_constructed)
512 const_cast<bool&>(__x.__value_constructed) = false;
514 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
516 _LIBCPP_INLINE_VISIBILITY
517 void operator()(pointer __p) _NOEXCEPT
519 if (__second_constructed)
520 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.second));
521 if (__first_constructed)
522 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.first));
524 __alloc_traits::deallocate(__na_, __p, 1);
528 #if __cplusplus >= 201103L
530 template <class _Key, class _Tp>
531 union __hash_value_type
533 typedef _Key key_type;
534 typedef _Tp mapped_type;
535 typedef pair<const key_type, mapped_type> value_type;
536 typedef pair<key_type, mapped_type> __nc_value_type;
539 __nc_value_type __nc;
541 template <class ..._Args>
542 _LIBCPP_INLINE_VISIBILITY
543 __hash_value_type(_Args&& ...__args)
544 : __cc(std::forward<_Args>(__args)...) {}
546 _LIBCPP_INLINE_VISIBILITY
547 __hash_value_type(const __hash_value_type& __v)
550 _LIBCPP_INLINE_VISIBILITY
551 __hash_value_type(__hash_value_type&& __v)
552 : __nc(std::move(__v.__nc)) {}
554 _LIBCPP_INLINE_VISIBILITY
555 __hash_value_type& operator=(const __hash_value_type& __v)
556 {__nc = __v.__cc; return *this;}
558 _LIBCPP_INLINE_VISIBILITY
559 __hash_value_type& operator=(__hash_value_type&& __v)
560 {__nc = std::move(__v.__nc); return *this;}
562 _LIBCPP_INLINE_VISIBILITY
563 ~__hash_value_type() {__cc.~value_type();}
568 template <class _Key, class _Tp>
569 struct __hash_value_type
571 typedef _Key key_type;
572 typedef _Tp mapped_type;
573 typedef pair<const key_type, mapped_type> value_type;
577 _LIBCPP_INLINE_VISIBILITY
578 __hash_value_type() {}
581 _LIBCPP_INLINE_VISIBILITY
582 __hash_value_type(const _A0& __a0)
585 template <class _A0, class _A1>
586 _LIBCPP_INLINE_VISIBILITY
587 __hash_value_type(const _A0& __a0, const _A1& __a1)
588 : __cc(__a0, __a1) {}
593 template <class _HashIterator>
594 class _LIBCPP_TYPE_VIS_ONLY __hash_map_iterator
598 typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits;
599 typedef const typename _HashIterator::value_type::value_type::first_type key_type;
600 typedef typename _HashIterator::value_type::value_type::second_type mapped_type;
602 typedef forward_iterator_tag iterator_category;
603 typedef pair<key_type, mapped_type> value_type;
604 typedef typename _HashIterator::difference_type difference_type;
605 typedef value_type& reference;
606 typedef typename __pointer_traits::template
607 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
610 rebind<value_type>::other
614 _LIBCPP_INLINE_VISIBILITY
615 __hash_map_iterator() _NOEXCEPT {}
617 _LIBCPP_INLINE_VISIBILITY
618 __hash_map_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
620 _LIBCPP_INLINE_VISIBILITY
621 reference operator*() const {return __i_->__cc;}
622 _LIBCPP_INLINE_VISIBILITY
623 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);}
625 _LIBCPP_INLINE_VISIBILITY
626 __hash_map_iterator& operator++() {++__i_; return *this;}
627 _LIBCPP_INLINE_VISIBILITY
628 __hash_map_iterator operator++(int)
630 __hash_map_iterator __t(*this);
635 friend _LIBCPP_INLINE_VISIBILITY
636 bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y)
637 {return __x.__i_ == __y.__i_;}
638 friend _LIBCPP_INLINE_VISIBILITY
639 bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y)
640 {return __x.__i_ != __y.__i_;}
642 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map;
643 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap;
644 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator;
645 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator;
646 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator;
649 template <class _HashIterator>
650 class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator
654 typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits;
655 typedef const typename _HashIterator::value_type::value_type::first_type key_type;
656 typedef typename _HashIterator::value_type::value_type::second_type mapped_type;
658 typedef forward_iterator_tag iterator_category;
659 typedef pair<key_type, mapped_type> value_type;
660 typedef typename _HashIterator::difference_type difference_type;
661 typedef const value_type& reference;
662 typedef typename __pointer_traits::template
663 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
664 rebind<const value_type>
666 rebind<const value_type>::other
670 _LIBCPP_INLINE_VISIBILITY
671 __hash_map_const_iterator() _NOEXCEPT {}
673 _LIBCPP_INLINE_VISIBILITY
674 __hash_map_const_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
675 _LIBCPP_INLINE_VISIBILITY
676 __hash_map_const_iterator(
677 __hash_map_iterator<typename _HashIterator::__non_const_iterator> __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_const_iterator& operator++() {++__i_; return *this;}
688 _LIBCPP_INLINE_VISIBILITY
689 __hash_map_const_iterator operator++(int)
691 __hash_map_const_iterator __t(*this);
696 friend _LIBCPP_INLINE_VISIBILITY
697 bool operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)
698 {return __x.__i_ == __y.__i_;}
699 friend _LIBCPP_INLINE_VISIBILITY
700 bool operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_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;
709 template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
710 class _Alloc = allocator<pair<const _Key, _Tp> > >
711 class _LIBCPP_TYPE_VIS_ONLY unordered_map
715 typedef _Key key_type;
716 typedef _Tp mapped_type;
717 typedef _Hash hasher;
718 typedef _Pred key_equal;
719 typedef _Alloc allocator_type;
720 typedef pair<const key_type, mapped_type> value_type;
721 typedef pair<key_type, mapped_type> __nc_value_type;
722 typedef value_type& reference;
723 typedef const value_type& const_reference;
724 static_assert((is_same<value_type, typename allocator_type::value_type>::value),
725 "Invalid allocator::value_type");
728 typedef __hash_value_type<key_type, mapped_type> __value_type;
729 typedef __unordered_map_hasher<key_type, __value_type, hasher> __hasher;
730 typedef __unordered_map_equal<key_type, __value_type, key_equal> __key_equal;
731 typedef typename allocator_traits<allocator_type>::template
732 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
733 rebind_alloc<__value_type>
735 rebind_alloc<__value_type>::other
739 typedef __hash_table<__value_type, __hasher,
740 __key_equal, __allocator_type> __table;
744 typedef typename __table::__node_pointer __node_pointer;
745 typedef typename __table::__node_const_pointer __node_const_pointer;
746 typedef typename __table::__node_traits __node_traits;
747 typedef typename __table::__node_allocator __node_allocator;
748 typedef typename __table::__node __node;
749 typedef __hash_map_node_destructor<__node_allocator> _Dp;
750 typedef unique_ptr<__node, _Dp> __node_holder;
751 typedef allocator_traits<allocator_type> __alloc_traits;
753 typedef typename __alloc_traits::pointer pointer;
754 typedef typename __alloc_traits::const_pointer const_pointer;
755 typedef typename __alloc_traits::size_type size_type;
756 typedef typename __alloc_traits::difference_type difference_type;
758 typedef __hash_map_iterator<typename __table::iterator> iterator;
759 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
760 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
761 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
763 _LIBCPP_INLINE_VISIBILITY
765 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
767 #if _LIBCPP_DEBUG_LEVEL >= 2
768 __get_db()->__insert_c(this);
771 explicit unordered_map(size_type __n, const hasher& __hf = hasher(),
772 const key_equal& __eql = key_equal());
773 unordered_map(size_type __n, const hasher& __hf,
774 const key_equal& __eql,
775 const allocator_type& __a);
776 template <class _InputIterator>
777 unordered_map(_InputIterator __first, _InputIterator __last);
778 template <class _InputIterator>
779 unordered_map(_InputIterator __first, _InputIterator __last,
780 size_type __n, const hasher& __hf = hasher(),
781 const key_equal& __eql = key_equal());
782 template <class _InputIterator>
783 unordered_map(_InputIterator __first, _InputIterator __last,
784 size_type __n, const hasher& __hf,
785 const key_equal& __eql,
786 const allocator_type& __a);
787 explicit unordered_map(const allocator_type& __a);
788 unordered_map(const unordered_map& __u);
789 unordered_map(const unordered_map& __u, const allocator_type& __a);
790 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
791 unordered_map(unordered_map&& __u)
792 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
793 unordered_map(unordered_map&& __u, const allocator_type& __a);
794 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
795 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
796 unordered_map(initializer_list<value_type> __il);
797 unordered_map(initializer_list<value_type> __il, size_type __n,
798 const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
799 unordered_map(initializer_list<value_type> __il, size_type __n,
800 const hasher& __hf, const key_equal& __eql,
801 const allocator_type& __a);
802 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
803 #if _LIBCPP_STD_VER > 11
804 _LIBCPP_INLINE_VISIBILITY
805 unordered_map(size_type __n, const allocator_type& __a)
806 : unordered_map(__n, hasher(), key_equal(), __a) {}
807 _LIBCPP_INLINE_VISIBILITY
808 unordered_map(size_type __n, const hasher& __hf, const allocator_type& __a)
809 : unordered_map(__n, __hf, key_equal(), __a) {}
810 template <class _InputIterator>
811 _LIBCPP_INLINE_VISIBILITY
812 unordered_map(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a)
813 : unordered_map(__first, __last, __n, hasher(), key_equal(), __a) {}
814 template <class _InputIterator>
815 _LIBCPP_INLINE_VISIBILITY
816 unordered_map(_InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf,
817 const allocator_type& __a)
818 : unordered_map(__first, __last, __n, __hf, key_equal(), __a) {}
819 _LIBCPP_INLINE_VISIBILITY
820 unordered_map(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)
821 : unordered_map(__il, __n, hasher(), key_equal(), __a) {}
822 _LIBCPP_INLINE_VISIBILITY
823 unordered_map(initializer_list<value_type> __il, size_type __n, const hasher& __hf,
824 const allocator_type& __a)
825 : unordered_map(__il, __n, __hf, key_equal(), __a) {}
827 // ~unordered_map() = default;
828 _LIBCPP_INLINE_VISIBILITY
829 unordered_map& operator=(const unordered_map& __u)
831 #if __cplusplus >= 201103L
832 __table_ = __u.__table_;
836 __table_.hash_function() = __u.__table_.hash_function();
837 __table_.key_eq() = __u.__table_.key_eq();
838 __table_.max_load_factor() = __u.__table_.max_load_factor();
839 __table_.__copy_assign_alloc(__u.__table_);
840 insert(__u.begin(), __u.end());
845 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
846 unordered_map& operator=(unordered_map&& __u)
847 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
849 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
850 unordered_map& operator=(initializer_list<value_type> __il);
851 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
853 _LIBCPP_INLINE_VISIBILITY
854 allocator_type get_allocator() const _NOEXCEPT
855 {return allocator_type(__table_.__node_alloc());}
857 _LIBCPP_INLINE_VISIBILITY
858 bool empty() const _NOEXCEPT {return __table_.size() == 0;}
859 _LIBCPP_INLINE_VISIBILITY
860 size_type size() const _NOEXCEPT {return __table_.size();}
861 _LIBCPP_INLINE_VISIBILITY
862 size_type max_size() const _NOEXCEPT {return __table_.max_size();}
864 _LIBCPP_INLINE_VISIBILITY
865 iterator begin() _NOEXCEPT {return __table_.begin();}
866 _LIBCPP_INLINE_VISIBILITY
867 iterator end() _NOEXCEPT {return __table_.end();}
868 _LIBCPP_INLINE_VISIBILITY
869 const_iterator begin() const _NOEXCEPT {return __table_.begin();}
870 _LIBCPP_INLINE_VISIBILITY
871 const_iterator end() const _NOEXCEPT {return __table_.end();}
872 _LIBCPP_INLINE_VISIBILITY
873 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
874 _LIBCPP_INLINE_VISIBILITY
875 const_iterator cend() const _NOEXCEPT {return __table_.end();}
877 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
878 #ifndef _LIBCPP_HAS_NO_VARIADICS
880 template <class... _Args>
881 pair<iterator, bool> emplace(_Args&&... __args);
883 template <class... _Args>
884 _LIBCPP_INLINE_VISIBILITY
885 #if _LIBCPP_DEBUG_LEVEL >= 2
886 iterator emplace_hint(const_iterator __p, _Args&&... __args)
888 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
889 "unordered_map::emplace_hint(const_iterator, args...) called with an iterator not"
890 " referring to this unordered_map");
891 return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first;
894 iterator emplace_hint(const_iterator, _Args&&... __args)
895 {return emplace(_VSTD::forward<_Args>(__args)...).first;}
897 #endif // _LIBCPP_HAS_NO_VARIADICS
898 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
899 _LIBCPP_INLINE_VISIBILITY
900 pair<iterator, bool> insert(const value_type& __x)
901 {return __table_.__insert_unique(__x);}
902 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
904 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
905 _LIBCPP_INLINE_VISIBILITY
906 pair<iterator, bool> insert(_Pp&& __x)
907 {return __table_.__insert_unique(_VSTD::forward<_Pp>(__x));}
908 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
909 _LIBCPP_INLINE_VISIBILITY
910 #if _LIBCPP_DEBUG_LEVEL >= 2
911 iterator insert(const_iterator __p, const value_type& __x)
913 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
914 "unordered_map::insert(const_iterator, const value_type&) called with an iterator not"
915 " referring to this unordered_map");
916 return insert(__x).first;
919 iterator insert(const_iterator, const value_type& __x)
920 {return insert(__x).first;}
922 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
924 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
925 _LIBCPP_INLINE_VISIBILITY
926 #if _LIBCPP_DEBUG_LEVEL >= 2
927 iterator insert(const_iterator __p, _Pp&& __x)
929 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
930 "unordered_map::insert(const_iterator, value_type&&) called with an iterator not"
931 " referring to this unordered_map");
932 return insert(_VSTD::forward<_Pp>(__x)).first;
935 iterator insert(const_iterator, _Pp&& __x)
936 {return insert(_VSTD::forward<_Pp>(__x)).first;}
938 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
939 template <class _InputIterator>
940 void insert(_InputIterator __first, _InputIterator __last);
941 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
942 _LIBCPP_INLINE_VISIBILITY
943 void insert(initializer_list<value_type> __il)
944 {insert(__il.begin(), __il.end());}
945 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
947 _LIBCPP_INLINE_VISIBILITY
948 iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);}
949 _LIBCPP_INLINE_VISIBILITY
950 size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
951 _LIBCPP_INLINE_VISIBILITY
952 iterator erase(const_iterator __first, const_iterator __last)
953 {return __table_.erase(__first.__i_, __last.__i_);}
954 _LIBCPP_INLINE_VISIBILITY
955 void clear() _NOEXCEPT {__table_.clear();}
957 _LIBCPP_INLINE_VISIBILITY
958 void swap(unordered_map& __u)
959 _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
960 {__table_.swap(__u.__table_);}
962 _LIBCPP_INLINE_VISIBILITY
963 hasher hash_function() const
964 {return __table_.hash_function().hash_function();}
965 _LIBCPP_INLINE_VISIBILITY
966 key_equal key_eq() const
967 {return __table_.key_eq().key_eq();}
969 _LIBCPP_INLINE_VISIBILITY
970 iterator find(const key_type& __k) {return __table_.find(__k);}
971 _LIBCPP_INLINE_VISIBILITY
972 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
973 _LIBCPP_INLINE_VISIBILITY
974 size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
975 _LIBCPP_INLINE_VISIBILITY
976 pair<iterator, iterator> equal_range(const key_type& __k)
977 {return __table_.__equal_range_unique(__k);}
978 _LIBCPP_INLINE_VISIBILITY
979 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
980 {return __table_.__equal_range_unique(__k);}
982 mapped_type& operator[](const key_type& __k);
983 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
984 mapped_type& operator[](key_type&& __k);
987 mapped_type& at(const key_type& __k);
988 const mapped_type& at(const key_type& __k) const;
990 _LIBCPP_INLINE_VISIBILITY
991 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
992 _LIBCPP_INLINE_VISIBILITY
993 size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
995 _LIBCPP_INLINE_VISIBILITY
996 size_type bucket_size(size_type __n) const
997 {return __table_.bucket_size(__n);}
998 _LIBCPP_INLINE_VISIBILITY
999 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
1001 _LIBCPP_INLINE_VISIBILITY
1002 local_iterator begin(size_type __n) {return __table_.begin(__n);}
1003 _LIBCPP_INLINE_VISIBILITY
1004 local_iterator end(size_type __n) {return __table_.end(__n);}
1005 _LIBCPP_INLINE_VISIBILITY
1006 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);}
1007 _LIBCPP_INLINE_VISIBILITY
1008 const_local_iterator end(size_type __n) const {return __table_.cend(__n);}
1009 _LIBCPP_INLINE_VISIBILITY
1010 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
1011 _LIBCPP_INLINE_VISIBILITY
1012 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);}
1014 _LIBCPP_INLINE_VISIBILITY
1015 float load_factor() const _NOEXCEPT {return __table_.load_factor();}
1016 _LIBCPP_INLINE_VISIBILITY
1017 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
1018 _LIBCPP_INLINE_VISIBILITY
1019 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
1020 _LIBCPP_INLINE_VISIBILITY
1021 void rehash(size_type __n) {__table_.rehash(__n);}
1022 _LIBCPP_INLINE_VISIBILITY
1023 void reserve(size_type __n) {__table_.reserve(__n);}
1025 #if _LIBCPP_DEBUG_LEVEL >= 2
1027 bool __dereferenceable(const const_iterator* __i) const
1028 {return __table_.__dereferenceable(&__i->__i_);}
1029 bool __decrementable(const const_iterator* __i) const
1030 {return __table_.__decrementable(&__i->__i_);}
1031 bool __addable(const const_iterator* __i, ptrdiff_t __n) const
1032 {return __table_.__addable(&__i->__i_, __n);}
1033 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
1034 {return __table_.__addable(&__i->__i_, __n);}
1036 #endif // _LIBCPP_DEBUG_LEVEL >= 2
1039 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1040 __node_holder __construct_node();
1041 template <class _A0>
1043 __construct_node(_A0&& __a0);
1044 __node_holder __construct_node_with_key(key_type&& __k);
1045 #ifndef _LIBCPP_HAS_NO_VARIADICS
1046 template <class _A0, class _A1, class ..._Args>
1047 __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args);
1048 #endif // _LIBCPP_HAS_NO_VARIADICS
1049 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1050 __node_holder __construct_node_with_key(const key_type& __k);
1053 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1054 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1055 size_type __n, const hasher& __hf, const key_equal& __eql)
1056 : __table_(__hf, __eql)
1058 #if _LIBCPP_DEBUG_LEVEL >= 2
1059 __get_db()->__insert_c(this);
1061 __table_.rehash(__n);
1064 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1065 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1066 size_type __n, const hasher& __hf, const key_equal& __eql,
1067 const allocator_type& __a)
1068 : __table_(__hf, __eql, __a)
1070 #if _LIBCPP_DEBUG_LEVEL >= 2
1071 __get_db()->__insert_c(this);
1073 __table_.rehash(__n);
1076 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1077 inline _LIBCPP_INLINE_VISIBILITY
1078 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1079 const allocator_type& __a)
1082 #if _LIBCPP_DEBUG_LEVEL >= 2
1083 __get_db()->__insert_c(this);
1087 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1088 template <class _InputIterator>
1089 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1090 _InputIterator __first, _InputIterator __last)
1092 #if _LIBCPP_DEBUG_LEVEL >= 2
1093 __get_db()->__insert_c(this);
1095 insert(__first, __last);
1098 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1099 template <class _InputIterator>
1100 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1101 _InputIterator __first, _InputIterator __last, size_type __n,
1102 const hasher& __hf, const key_equal& __eql)
1103 : __table_(__hf, __eql)
1105 #if _LIBCPP_DEBUG_LEVEL >= 2
1106 __get_db()->__insert_c(this);
1108 __table_.rehash(__n);
1109 insert(__first, __last);
1112 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1113 template <class _InputIterator>
1114 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1115 _InputIterator __first, _InputIterator __last, size_type __n,
1116 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1117 : __table_(__hf, __eql, __a)
1119 #if _LIBCPP_DEBUG_LEVEL >= 2
1120 __get_db()->__insert_c(this);
1122 __table_.rehash(__n);
1123 insert(__first, __last);
1126 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1127 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1128 const unordered_map& __u)
1129 : __table_(__u.__table_)
1131 #if _LIBCPP_DEBUG_LEVEL >= 2
1132 __get_db()->__insert_c(this);
1134 __table_.rehash(__u.bucket_count());
1135 insert(__u.begin(), __u.end());
1138 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1139 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1140 const unordered_map& __u, const allocator_type& __a)
1141 : __table_(__u.__table_, __a)
1143 #if _LIBCPP_DEBUG_LEVEL >= 2
1144 __get_db()->__insert_c(this);
1146 __table_.rehash(__u.bucket_count());
1147 insert(__u.begin(), __u.end());
1150 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1152 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1153 inline _LIBCPP_INLINE_VISIBILITY
1154 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1155 unordered_map&& __u)
1156 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
1157 : __table_(_VSTD::move(__u.__table_))
1159 #if _LIBCPP_DEBUG_LEVEL >= 2
1160 __get_db()->__insert_c(this);
1161 __get_db()->swap(this, &__u);
1165 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1166 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1167 unordered_map&& __u, const allocator_type& __a)
1168 : __table_(_VSTD::move(__u.__table_), __a)
1170 #if _LIBCPP_DEBUG_LEVEL >= 2
1171 __get_db()->__insert_c(this);
1173 if (__a != __u.get_allocator())
1175 iterator __i = __u.begin();
1176 while (__u.size() != 0)
1177 __table_.__insert_unique(
1178 _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_)
1181 #if _LIBCPP_DEBUG_LEVEL >= 2
1183 __get_db()->swap(this, &__u);
1187 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1189 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1191 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1192 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1193 initializer_list<value_type> __il)
1195 #if _LIBCPP_DEBUG_LEVEL >= 2
1196 __get_db()->__insert_c(this);
1198 insert(__il.begin(), __il.end());
1201 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1202 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1203 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1204 const key_equal& __eql)
1205 : __table_(__hf, __eql)
1207 #if _LIBCPP_DEBUG_LEVEL >= 2
1208 __get_db()->__insert_c(this);
1210 __table_.rehash(__n);
1211 insert(__il.begin(), __il.end());
1214 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1215 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1216 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1217 const key_equal& __eql, const allocator_type& __a)
1218 : __table_(__hf, __eql, __a)
1220 #if _LIBCPP_DEBUG_LEVEL >= 2
1221 __get_db()->__insert_c(this);
1223 __table_.rehash(__n);
1224 insert(__il.begin(), __il.end());
1227 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1229 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1231 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1232 inline _LIBCPP_INLINE_VISIBILITY
1233 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
1234 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_map&& __u)
1235 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
1237 __table_ = _VSTD::move(__u.__table_);
1241 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1243 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1245 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1246 inline _LIBCPP_INLINE_VISIBILITY
1247 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
1248 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(
1249 initializer_list<value_type> __il)
1251 __table_.__assign_unique(__il.begin(), __il.end());
1255 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1257 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1259 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1260 typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1261 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node()
1263 __node_allocator& __na = __table_.__node_alloc();
1264 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1265 __node_traits::construct(__na, _VSTD::addressof(__h->__value_));
1266 __h.get_deleter().__first_constructed = true;
1267 __h.get_deleter().__second_constructed = true;
1271 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1272 template <class _A0>
1273 typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1274 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
1276 __node_allocator& __na = __table_.__node_alloc();
1277 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1278 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1279 _VSTD::forward<_A0>(__a0));
1280 __h.get_deleter().__first_constructed = true;
1281 __h.get_deleter().__second_constructed = true;
1285 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1286 typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1287 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(key_type&& __k)
1289 __node_allocator& __na = __table_.__node_alloc();
1290 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1291 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), _VSTD::move(__k));
1292 __h.get_deleter().__first_constructed = true;
1293 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
1294 __h.get_deleter().__second_constructed = true;
1298 #ifndef _LIBCPP_HAS_NO_VARIADICS
1300 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1301 template <class _A0, class _A1, class ..._Args>
1302 typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1303 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0,
1307 __node_allocator& __na = __table_.__node_alloc();
1308 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1309 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1310 _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1),
1311 _VSTD::forward<_Args>(__args)...);
1312 __h.get_deleter().__first_constructed = true;
1313 __h.get_deleter().__second_constructed = true;
1317 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1318 template <class... _Args>
1319 pair<typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator, bool>
1320 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_Args&&... __args)
1322 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1323 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1329 #endif // _LIBCPP_HAS_NO_VARIADICS
1330 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1332 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1333 typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1334 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(const key_type& __k)
1336 __node_allocator& __na = __table_.__node_alloc();
1337 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1338 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), __k);
1339 __h.get_deleter().__first_constructed = true;
1340 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
1341 __h.get_deleter().__second_constructed = true;
1342 return _VSTD::move(__h); // explicitly moved for C++03
1345 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1346 template <class _InputIterator>
1347 inline _LIBCPP_INLINE_VISIBILITY
1349 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
1350 _InputIterator __last)
1352 for (; __first != __last; ++__first)
1353 __table_.__insert_unique(*__first);
1356 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1358 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k)
1360 iterator __i = find(__k);
1363 __node_holder __h = __construct_node_with_key(__k);
1364 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1366 return __r.first->second;
1369 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1371 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1373 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&& __k)
1375 iterator __i = find(__k);
1378 __node_holder __h = __construct_node_with_key(_VSTD::move(__k));
1379 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1381 return __r.first->second;
1384 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1386 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1388 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k)
1390 iterator __i = find(__k);
1391 #ifndef _LIBCPP_NO_EXCEPTIONS
1393 throw out_of_range("unordered_map::at: key not found");
1394 #endif // _LIBCPP_NO_EXCEPTIONS
1398 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1400 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) const
1402 const_iterator __i = find(__k);
1403 #ifndef _LIBCPP_NO_EXCEPTIONS
1405 throw out_of_range("unordered_map::at: key not found");
1406 #endif // _LIBCPP_NO_EXCEPTIONS
1410 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1411 inline _LIBCPP_INLINE_VISIBILITY
1413 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1414 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1415 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1420 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1422 operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1423 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1425 if (__x.size() != __y.size())
1427 typedef typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
1429 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();
1432 const_iterator __j = __y.find(__i->first);
1433 if (__j == __ey || !(*__i == *__j))
1439 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1440 inline _LIBCPP_INLINE_VISIBILITY
1442 operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1443 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1445 return !(__x == __y);
1448 template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
1449 class _Alloc = allocator<pair<const _Key, _Tp> > >
1450 class _LIBCPP_TYPE_VIS_ONLY unordered_multimap
1454 typedef _Key key_type;
1455 typedef _Tp mapped_type;
1456 typedef _Hash hasher;
1457 typedef _Pred key_equal;
1458 typedef _Alloc allocator_type;
1459 typedef pair<const key_type, mapped_type> value_type;
1460 typedef pair<key_type, mapped_type> __nc_value_type;
1461 typedef value_type& reference;
1462 typedef const value_type& const_reference;
1463 static_assert((is_same<value_type, typename allocator_type::value_type>::value),
1464 "Invalid allocator::value_type");
1467 typedef __hash_value_type<key_type, mapped_type> __value_type;
1468 typedef __unordered_map_hasher<key_type, __value_type, hasher> __hasher;
1469 typedef __unordered_map_equal<key_type, __value_type, key_equal> __key_equal;
1470 typedef typename allocator_traits<allocator_type>::template
1471 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
1472 rebind_alloc<__value_type>
1474 rebind_alloc<__value_type>::other
1478 typedef __hash_table<__value_type, __hasher,
1479 __key_equal, __allocator_type> __table;
1483 typedef typename __table::__node_traits __node_traits;
1484 typedef typename __table::__node_allocator __node_allocator;
1485 typedef typename __table::__node __node;
1486 typedef __hash_map_node_destructor<__node_allocator> _Dp;
1487 typedef unique_ptr<__node, _Dp> __node_holder;
1488 typedef allocator_traits<allocator_type> __alloc_traits;
1490 typedef typename __alloc_traits::pointer pointer;
1491 typedef typename __alloc_traits::const_pointer const_pointer;
1492 typedef typename __alloc_traits::size_type size_type;
1493 typedef typename __alloc_traits::difference_type difference_type;
1495 typedef __hash_map_iterator<typename __table::iterator> iterator;
1496 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
1497 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
1498 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
1500 _LIBCPP_INLINE_VISIBILITY
1501 unordered_multimap()
1502 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
1504 #if _LIBCPP_DEBUG_LEVEL >= 2
1505 __get_db()->__insert_c(this);
1508 explicit unordered_multimap(size_type __n, const hasher& __hf = hasher(),
1509 const key_equal& __eql = key_equal());
1510 unordered_multimap(size_type __n, const hasher& __hf,
1511 const key_equal& __eql,
1512 const allocator_type& __a);
1513 template <class _InputIterator>
1514 unordered_multimap(_InputIterator __first, _InputIterator __last);
1515 template <class _InputIterator>
1516 unordered_multimap(_InputIterator __first, _InputIterator __last,
1517 size_type __n, const hasher& __hf = hasher(),
1518 const key_equal& __eql = key_equal());
1519 template <class _InputIterator>
1520 unordered_multimap(_InputIterator __first, _InputIterator __last,
1521 size_type __n, const hasher& __hf,
1522 const key_equal& __eql,
1523 const allocator_type& __a);
1524 explicit unordered_multimap(const allocator_type& __a);
1525 unordered_multimap(const unordered_multimap& __u);
1526 unordered_multimap(const unordered_multimap& __u, const allocator_type& __a);
1527 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1528 unordered_multimap(unordered_multimap&& __u)
1529 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
1530 unordered_multimap(unordered_multimap&& __u, const allocator_type& __a);
1531 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1532 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1533 unordered_multimap(initializer_list<value_type> __il);
1534 unordered_multimap(initializer_list<value_type> __il, size_type __n,
1535 const hasher& __hf = hasher(),
1536 const key_equal& __eql = key_equal());
1537 unordered_multimap(initializer_list<value_type> __il, size_type __n,
1538 const hasher& __hf, const key_equal& __eql,
1539 const allocator_type& __a);
1540 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1541 #if _LIBCPP_STD_VER > 11
1542 _LIBCPP_INLINE_VISIBILITY
1543 unordered_multimap(size_type __n, const allocator_type& __a)
1544 : unordered_multimap(__n, hasher(), key_equal(), __a) {}
1545 _LIBCPP_INLINE_VISIBILITY
1546 unordered_multimap(size_type __n, const hasher& __hf, const allocator_type& __a)
1547 : unordered_multimap(__n, __hf, key_equal(), __a) {}
1548 template <class _InputIterator>
1549 _LIBCPP_INLINE_VISIBILITY
1550 unordered_multimap(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a)
1551 : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a) {}
1552 template <class _InputIterator>
1553 _LIBCPP_INLINE_VISIBILITY
1554 unordered_multimap(_InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf,
1555 const allocator_type& __a)
1556 : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a) {}
1557 _LIBCPP_INLINE_VISIBILITY
1558 unordered_multimap(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)
1559 : unordered_multimap(__il, __n, hasher(), key_equal(), __a) {}
1560 _LIBCPP_INLINE_VISIBILITY
1561 unordered_multimap(initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1562 const allocator_type& __a)
1563 : unordered_multimap(__il, __n, __hf, key_equal(), __a) {}
1565 // ~unordered_multimap() = default;
1566 _LIBCPP_INLINE_VISIBILITY
1567 unordered_multimap& operator=(const unordered_multimap& __u)
1569 #if __cplusplus >= 201103L
1570 __table_ = __u.__table_;
1574 __table_.hash_function() = __u.__table_.hash_function();
1575 __table_.key_eq() = __u.__table_.key_eq();
1576 __table_.max_load_factor() = __u.__table_.max_load_factor();
1577 __table_.__copy_assign_alloc(__u.__table_);
1578 insert(__u.begin(), __u.end());
1583 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1584 unordered_multimap& operator=(unordered_multimap&& __u)
1585 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
1587 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1588 unordered_multimap& operator=(initializer_list<value_type> __il);
1589 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1591 _LIBCPP_INLINE_VISIBILITY
1592 allocator_type get_allocator() const _NOEXCEPT
1593 {return allocator_type(__table_.__node_alloc());}
1595 _LIBCPP_INLINE_VISIBILITY
1596 bool empty() const _NOEXCEPT {return __table_.size() == 0;}
1597 _LIBCPP_INLINE_VISIBILITY
1598 size_type size() const _NOEXCEPT {return __table_.size();}
1599 _LIBCPP_INLINE_VISIBILITY
1600 size_type max_size() const _NOEXCEPT {return __table_.max_size();}
1602 _LIBCPP_INLINE_VISIBILITY
1603 iterator begin() _NOEXCEPT {return __table_.begin();}
1604 _LIBCPP_INLINE_VISIBILITY
1605 iterator end() _NOEXCEPT {return __table_.end();}
1606 _LIBCPP_INLINE_VISIBILITY
1607 const_iterator begin() const _NOEXCEPT {return __table_.begin();}
1608 _LIBCPP_INLINE_VISIBILITY
1609 const_iterator end() const _NOEXCEPT {return __table_.end();}
1610 _LIBCPP_INLINE_VISIBILITY
1611 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
1612 _LIBCPP_INLINE_VISIBILITY
1613 const_iterator cend() const _NOEXCEPT {return __table_.end();}
1615 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1616 #ifndef _LIBCPP_HAS_NO_VARIADICS
1618 template <class... _Args>
1619 iterator emplace(_Args&&... __args);
1621 template <class... _Args>
1622 iterator emplace_hint(const_iterator __p, _Args&&... __args);
1623 #endif // _LIBCPP_HAS_NO_VARIADICS
1624 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1625 _LIBCPP_INLINE_VISIBILITY
1626 iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
1627 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1628 template <class _Pp,
1629 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1630 _LIBCPP_INLINE_VISIBILITY
1631 iterator insert(_Pp&& __x)
1632 {return __table_.__insert_multi(_VSTD::forward<_Pp>(__x));}
1633 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1634 _LIBCPP_INLINE_VISIBILITY
1635 iterator insert(const_iterator __p, const value_type& __x)
1636 {return __table_.__insert_multi(__p.__i_, __x);}
1637 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1638 template <class _Pp,
1639 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1640 _LIBCPP_INLINE_VISIBILITY
1641 iterator insert(const_iterator __p, _Pp&& __x)
1642 {return __table_.__insert_multi(__p.__i_, _VSTD::forward<_Pp>(__x));}
1643 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1644 template <class _InputIterator>
1645 void insert(_InputIterator __first, _InputIterator __last);
1646 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1647 _LIBCPP_INLINE_VISIBILITY
1648 void insert(initializer_list<value_type> __il)
1649 {insert(__il.begin(), __il.end());}
1650 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1652 _LIBCPP_INLINE_VISIBILITY
1653 iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);}
1654 _LIBCPP_INLINE_VISIBILITY
1655 size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
1656 _LIBCPP_INLINE_VISIBILITY
1657 iterator erase(const_iterator __first, const_iterator __last)
1658 {return __table_.erase(__first.__i_, __last.__i_);}
1659 _LIBCPP_INLINE_VISIBILITY
1660 void clear() _NOEXCEPT {__table_.clear();}
1662 _LIBCPP_INLINE_VISIBILITY
1663 void swap(unordered_multimap& __u)
1664 _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
1665 {__table_.swap(__u.__table_);}
1667 _LIBCPP_INLINE_VISIBILITY
1668 hasher hash_function() const
1669 {return __table_.hash_function().hash_function();}
1670 _LIBCPP_INLINE_VISIBILITY
1671 key_equal key_eq() const
1672 {return __table_.key_eq().key_eq();}
1674 _LIBCPP_INLINE_VISIBILITY
1675 iterator find(const key_type& __k) {return __table_.find(__k);}
1676 _LIBCPP_INLINE_VISIBILITY
1677 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
1678 _LIBCPP_INLINE_VISIBILITY
1679 size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
1680 _LIBCPP_INLINE_VISIBILITY
1681 pair<iterator, iterator> equal_range(const key_type& __k)
1682 {return __table_.__equal_range_multi(__k);}
1683 _LIBCPP_INLINE_VISIBILITY
1684 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
1685 {return __table_.__equal_range_multi(__k);}
1687 _LIBCPP_INLINE_VISIBILITY
1688 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
1689 _LIBCPP_INLINE_VISIBILITY
1690 size_type max_bucket_count() const _NOEXCEPT
1691 {return __table_.max_bucket_count();}
1693 _LIBCPP_INLINE_VISIBILITY
1694 size_type bucket_size(size_type __n) const
1695 {return __table_.bucket_size(__n);}
1696 _LIBCPP_INLINE_VISIBILITY
1697 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
1699 _LIBCPP_INLINE_VISIBILITY
1700 local_iterator begin(size_type __n) {return __table_.begin(__n);}
1701 _LIBCPP_INLINE_VISIBILITY
1702 local_iterator end(size_type __n) {return __table_.end(__n);}
1703 _LIBCPP_INLINE_VISIBILITY
1704 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);}
1705 _LIBCPP_INLINE_VISIBILITY
1706 const_local_iterator end(size_type __n) const {return __table_.cend(__n);}
1707 _LIBCPP_INLINE_VISIBILITY
1708 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
1709 _LIBCPP_INLINE_VISIBILITY
1710 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);}
1712 _LIBCPP_INLINE_VISIBILITY
1713 float load_factor() const _NOEXCEPT {return __table_.load_factor();}
1714 _LIBCPP_INLINE_VISIBILITY
1715 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
1716 _LIBCPP_INLINE_VISIBILITY
1717 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
1718 _LIBCPP_INLINE_VISIBILITY
1719 void rehash(size_type __n) {__table_.rehash(__n);}
1720 _LIBCPP_INLINE_VISIBILITY
1721 void reserve(size_type __n) {__table_.reserve(__n);}
1723 #if _LIBCPP_DEBUG_LEVEL >= 2
1725 bool __dereferenceable(const const_iterator* __i) const
1726 {return __table_.__dereferenceable(&__i->__i_);}
1727 bool __decrementable(const const_iterator* __i) const
1728 {return __table_.__decrementable(&__i->__i_);}
1729 bool __addable(const const_iterator* __i, ptrdiff_t __n) const
1730 {return __table_.__addable(&__i->__i_, __n);}
1731 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
1732 {return __table_.__addable(&__i->__i_, __n);}
1734 #endif // _LIBCPP_DEBUG_LEVEL >= 2
1737 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1738 __node_holder __construct_node();
1739 template <class _A0>
1741 __construct_node(_A0&& __a0);
1742 #ifndef _LIBCPP_HAS_NO_VARIADICS
1743 template <class _A0, class _A1, class ..._Args>
1744 __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args);
1745 #endif // _LIBCPP_HAS_NO_VARIADICS
1746 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1749 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1750 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1751 size_type __n, const hasher& __hf, const key_equal& __eql)
1752 : __table_(__hf, __eql)
1754 #if _LIBCPP_DEBUG_LEVEL >= 2
1755 __get_db()->__insert_c(this);
1757 __table_.rehash(__n);
1760 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1761 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1762 size_type __n, const hasher& __hf, const key_equal& __eql,
1763 const allocator_type& __a)
1764 : __table_(__hf, __eql, __a)
1766 #if _LIBCPP_DEBUG_LEVEL >= 2
1767 __get_db()->__insert_c(this);
1769 __table_.rehash(__n);
1772 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1773 template <class _InputIterator>
1774 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1775 _InputIterator __first, _InputIterator __last)
1777 #if _LIBCPP_DEBUG_LEVEL >= 2
1778 __get_db()->__insert_c(this);
1780 insert(__first, __last);
1783 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1784 template <class _InputIterator>
1785 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1786 _InputIterator __first, _InputIterator __last, size_type __n,
1787 const hasher& __hf, const key_equal& __eql)
1788 : __table_(__hf, __eql)
1790 #if _LIBCPP_DEBUG_LEVEL >= 2
1791 __get_db()->__insert_c(this);
1793 __table_.rehash(__n);
1794 insert(__first, __last);
1797 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1798 template <class _InputIterator>
1799 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1800 _InputIterator __first, _InputIterator __last, size_type __n,
1801 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1802 : __table_(__hf, __eql, __a)
1804 #if _LIBCPP_DEBUG_LEVEL >= 2
1805 __get_db()->__insert_c(this);
1807 __table_.rehash(__n);
1808 insert(__first, __last);
1811 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1812 inline _LIBCPP_INLINE_VISIBILITY
1813 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1814 const allocator_type& __a)
1817 #if _LIBCPP_DEBUG_LEVEL >= 2
1818 __get_db()->__insert_c(this);
1822 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1823 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1824 const unordered_multimap& __u)
1825 : __table_(__u.__table_)
1827 #if _LIBCPP_DEBUG_LEVEL >= 2
1828 __get_db()->__insert_c(this);
1830 __table_.rehash(__u.bucket_count());
1831 insert(__u.begin(), __u.end());
1834 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1835 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1836 const unordered_multimap& __u, const allocator_type& __a)
1837 : __table_(__u.__table_, __a)
1839 #if _LIBCPP_DEBUG_LEVEL >= 2
1840 __get_db()->__insert_c(this);
1842 __table_.rehash(__u.bucket_count());
1843 insert(__u.begin(), __u.end());
1846 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1848 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1849 inline _LIBCPP_INLINE_VISIBILITY
1850 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1851 unordered_multimap&& __u)
1852 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
1853 : __table_(_VSTD::move(__u.__table_))
1855 #if _LIBCPP_DEBUG_LEVEL >= 2
1856 __get_db()->__insert_c(this);
1857 __get_db()->swap(this, &__u);
1861 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1862 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1863 unordered_multimap&& __u, const allocator_type& __a)
1864 : __table_(_VSTD::move(__u.__table_), __a)
1866 #if _LIBCPP_DEBUG_LEVEL >= 2
1867 __get_db()->__insert_c(this);
1869 if (__a != __u.get_allocator())
1871 iterator __i = __u.begin();
1872 while (__u.size() != 0)
1874 __table_.__insert_multi(
1875 _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_)
1879 #if _LIBCPP_DEBUG_LEVEL >= 2
1881 __get_db()->swap(this, &__u);
1885 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1887 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1889 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1890 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1891 initializer_list<value_type> __il)
1893 #if _LIBCPP_DEBUG_LEVEL >= 2
1894 __get_db()->__insert_c(this);
1896 insert(__il.begin(), __il.end());
1899 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1900 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1901 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1902 const key_equal& __eql)
1903 : __table_(__hf, __eql)
1905 #if _LIBCPP_DEBUG_LEVEL >= 2
1906 __get_db()->__insert_c(this);
1908 __table_.rehash(__n);
1909 insert(__il.begin(), __il.end());
1912 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1913 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1914 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1915 const key_equal& __eql, const allocator_type& __a)
1916 : __table_(__hf, __eql, __a)
1918 #if _LIBCPP_DEBUG_LEVEL >= 2
1919 __get_db()->__insert_c(this);
1921 __table_.rehash(__n);
1922 insert(__il.begin(), __il.end());
1925 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1927 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1929 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1930 inline _LIBCPP_INLINE_VISIBILITY
1931 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
1932 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_multimap&& __u)
1933 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
1935 __table_ = _VSTD::move(__u.__table_);
1939 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1941 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1943 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1944 inline _LIBCPP_INLINE_VISIBILITY
1945 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
1946 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(
1947 initializer_list<value_type> __il)
1949 __table_.__assign_multi(__il.begin(), __il.end());
1953 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1955 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1957 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1958 typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1959 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node()
1961 __node_allocator& __na = __table_.__node_alloc();
1962 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1963 __node_traits::construct(__na, _VSTD::addressof(__h->__value_));
1964 __h.get_deleter().__first_constructed = true;
1965 __h.get_deleter().__second_constructed = true;
1969 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1970 template <class _A0>
1971 typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1972 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
1974 __node_allocator& __na = __table_.__node_alloc();
1975 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1976 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1977 _VSTD::forward<_A0>(__a0));
1978 __h.get_deleter().__first_constructed = true;
1979 __h.get_deleter().__second_constructed = true;
1983 #ifndef _LIBCPP_HAS_NO_VARIADICS
1985 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1986 template <class _A0, class _A1, class ..._Args>
1987 typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1988 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(
1989 _A0&& __a0, _A1&& __a1, _Args&&... __args)
1991 __node_allocator& __na = __table_.__node_alloc();
1992 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1993 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1994 _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1),
1995 _VSTD::forward<_Args>(__args)...);
1996 __h.get_deleter().__first_constructed = true;
1997 __h.get_deleter().__second_constructed = true;
2001 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2002 template <class... _Args>
2003 typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator
2004 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_Args&&... __args)
2006 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
2007 iterator __r = __table_.__node_insert_multi(__h.get());
2012 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2013 template <class... _Args>
2014 typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator
2015 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace_hint(
2016 const_iterator __p, _Args&&... __args)
2018 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
2019 iterator __r = __table_.__node_insert_multi(__p.__i_, __h.get());
2024 #endif // _LIBCPP_HAS_NO_VARIADICS
2025 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
2027 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2028 template <class _InputIterator>
2029 inline _LIBCPP_INLINE_VISIBILITY
2031 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
2032 _InputIterator __last)
2034 for (; __first != __last; ++__first)
2035 __table_.__insert_multi(*__first);
2038 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2039 inline _LIBCPP_INLINE_VISIBILITY
2041 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2042 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2043 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
2048 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2050 operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2051 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2053 if (__x.size() != __y.size())
2055 typedef typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
2057 typedef pair<const_iterator, const_iterator> _EqRng;
2058 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;)
2060 _EqRng __xeq = __x.equal_range(__i->first);
2061 _EqRng __yeq = __y.equal_range(__i->first);
2062 if (_VSTD::distance(__xeq.first, __xeq.second) !=
2063 _VSTD::distance(__yeq.first, __yeq.second) ||
2064 !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first))
2071 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2072 inline _LIBCPP_INLINE_VISIBILITY
2074 operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2075 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2077 return !(__x == __y);
2080 _LIBCPP_END_NAMESPACE_STD
2082 #endif // _LIBCPP_UNORDERED_MAP