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());
73 unordered_map& operator=(const unordered_map&);
74 unordered_map& operator=(unordered_map&&)
76 allocator_type::propagate_on_container_move_assignment::value &&
77 is_nothrow_move_assignable<allocator_type>::value &&
78 is_nothrow_move_assignable<hasher>::value &&
79 is_nothrow_move_assignable<key_equal>::value);
80 unordered_map& operator=(initializer_list<value_type>);
82 allocator_type get_allocator() const noexcept;
84 bool empty() const noexcept;
85 size_type size() const noexcept;
86 size_type max_size() const noexcept;
88 iterator begin() noexcept;
89 iterator end() noexcept;
90 const_iterator begin() const noexcept;
91 const_iterator end() const noexcept;
92 const_iterator cbegin() const noexcept;
93 const_iterator cend() const noexcept;
95 template <class... Args>
96 pair<iterator, bool> emplace(Args&&... args);
97 template <class... Args>
98 iterator emplace_hint(const_iterator position, Args&&... args);
99 pair<iterator, bool> insert(const value_type& obj);
101 pair<iterator, bool> insert(P&& obj);
102 iterator insert(const_iterator hint, const value_type& obj);
104 iterator insert(const_iterator hint, P&& obj);
105 template <class InputIterator>
106 void insert(InputIterator first, InputIterator last);
107 void insert(initializer_list<value_type>);
109 iterator erase(const_iterator position);
110 size_type erase(const key_type& k);
111 iterator erase(const_iterator first, const_iterator last);
112 void clear() noexcept;
114 void swap(unordered_map&)
116 (!allocator_type::propagate_on_container_swap::value ||
117 __is_nothrow_swappable<allocator_type>::value) &&
118 __is_nothrow_swappable<hasher>::value &&
119 __is_nothrow_swappable<key_equal>::value);
121 hasher hash_function() const;
122 key_equal key_eq() const;
124 iterator find(const key_type& k);
125 const_iterator find(const key_type& k) const;
126 size_type count(const key_type& k) const;
127 pair<iterator, iterator> equal_range(const key_type& k);
128 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
130 mapped_type& operator[](const key_type& k);
131 mapped_type& operator[](key_type&& k);
133 mapped_type& at(const key_type& k);
134 const mapped_type& at(const key_type& k) const;
136 size_type bucket_count() const noexcept;
137 size_type max_bucket_count() const noexcept;
139 size_type bucket_size(size_type n) const;
140 size_type bucket(const key_type& k) const;
142 local_iterator begin(size_type n);
143 local_iterator end(size_type n);
144 const_local_iterator begin(size_type n) const;
145 const_local_iterator end(size_type n) const;
146 const_local_iterator cbegin(size_type n) const;
147 const_local_iterator cend(size_type n) const;
149 float load_factor() const noexcept;
150 float max_load_factor() const noexcept;
151 void max_load_factor(float z);
152 void rehash(size_type n);
153 void reserve(size_type n);
156 template <class Key, class T, class Hash, class Pred, class Alloc>
157 void swap(unordered_map<Key, T, Hash, Pred, Alloc>& x,
158 unordered_map<Key, T, Hash, Pred, Alloc>& y)
159 noexcept(noexcept(x.swap(y)));
161 template <class Key, class T, class Hash, class Pred, class Alloc>
163 operator==(const unordered_map<Key, T, Hash, Pred, Alloc>& x,
164 const unordered_map<Key, T, Hash, Pred, Alloc>& y);
166 template <class Key, class T, class Hash, class Pred, class Alloc>
168 operator!=(const unordered_map<Key, T, Hash, Pred, Alloc>& x,
169 const unordered_map<Key, T, Hash, Pred, Alloc>& y);
171 template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
172 class Alloc = allocator<pair<const Key, T>>>
173 class unordered_multimap
177 typedef Key key_type;
178 typedef T mapped_type;
180 typedef Pred key_equal;
181 typedef Alloc allocator_type;
182 typedef pair<const key_type, mapped_type> value_type;
183 typedef value_type& reference;
184 typedef const value_type& const_reference;
185 typedef typename allocator_traits<allocator_type>::pointer pointer;
186 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
187 typedef typename allocator_traits<allocator_type>::size_type size_type;
188 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
190 typedef /unspecified/ iterator;
191 typedef /unspecified/ const_iterator;
192 typedef /unspecified/ local_iterator;
193 typedef /unspecified/ const_local_iterator;
197 is_nothrow_default_constructible<hasher>::value &&
198 is_nothrow_default_constructible<key_equal>::value &&
199 is_nothrow_default_constructible<allocator_type>::value);
200 explicit unordered_multimap(size_type n, const hasher& hf = hasher(),
201 const key_equal& eql = key_equal(),
202 const allocator_type& a = allocator_type());
203 template <class InputIterator>
204 unordered_multimap(InputIterator f, InputIterator l,
205 size_type n = 0, const hasher& hf = hasher(),
206 const key_equal& eql = key_equal(),
207 const allocator_type& a = allocator_type());
208 explicit unordered_multimap(const allocator_type&);
209 unordered_multimap(const unordered_multimap&);
210 unordered_multimap(const unordered_multimap&, const Allocator&);
211 unordered_multimap(unordered_multimap&&)
213 is_nothrow_move_constructible<hasher>::value &&
214 is_nothrow_move_constructible<key_equal>::value &&
215 is_nothrow_move_constructible<allocator_type>::value);
216 unordered_multimap(unordered_multimap&&, const Allocator&);
217 unordered_multimap(initializer_list<value_type>, size_type n = 0,
218 const hasher& hf = hasher(), const key_equal& eql = key_equal(),
219 const allocator_type& a = allocator_type());
220 ~unordered_multimap();
221 unordered_multimap& operator=(const unordered_multimap&);
222 unordered_multimap& operator=(unordered_multimap&&)
224 allocator_type::propagate_on_container_move_assignment::value &&
225 is_nothrow_move_assignable<allocator_type>::value &&
226 is_nothrow_move_assignable<hasher>::value &&
227 is_nothrow_move_assignable<key_equal>::value);
228 unordered_multimap& operator=(initializer_list<value_type>);
230 allocator_type get_allocator() const noexcept;
232 bool empty() const noexcept;
233 size_type size() const noexcept;
234 size_type max_size() const noexcept;
236 iterator begin() noexcept;
237 iterator end() noexcept;
238 const_iterator begin() const noexcept;
239 const_iterator end() const noexcept;
240 const_iterator cbegin() const noexcept;
241 const_iterator cend() const noexcept;
243 template <class... Args>
244 iterator emplace(Args&&... args);
245 template <class... Args>
246 iterator emplace_hint(const_iterator position, Args&&... args);
247 iterator insert(const value_type& obj);
249 iterator insert(P&& obj);
250 iterator insert(const_iterator hint, const value_type& obj);
252 iterator insert(const_iterator hint, P&& obj);
253 template <class InputIterator>
254 void insert(InputIterator first, InputIterator last);
255 void insert(initializer_list<value_type>);
257 iterator erase(const_iterator position);
258 size_type erase(const key_type& k);
259 iterator erase(const_iterator first, const_iterator last);
260 void clear() noexcept;
262 void swap(unordered_multimap&)
264 (!allocator_type::propagate_on_container_swap::value ||
265 __is_nothrow_swappable<allocator_type>::value) &&
266 __is_nothrow_swappable<hasher>::value &&
267 __is_nothrow_swappable<key_equal>::value);
269 hasher hash_function() const;
270 key_equal key_eq() const;
272 iterator find(const key_type& k);
273 const_iterator find(const key_type& k) const;
274 size_type count(const key_type& k) const;
275 pair<iterator, iterator> equal_range(const key_type& k);
276 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
278 size_type bucket_count() const noexcept;
279 size_type max_bucket_count() const noexcept;
281 size_type bucket_size(size_type n) const;
282 size_type bucket(const key_type& k) const;
284 local_iterator begin(size_type n);
285 local_iterator end(size_type n);
286 const_local_iterator begin(size_type n) const;
287 const_local_iterator end(size_type n) const;
288 const_local_iterator cbegin(size_type n) const;
289 const_local_iterator cend(size_type n) const;
291 float load_factor() const noexcept;
292 float max_load_factor() const noexcept;
293 void max_load_factor(float z);
294 void rehash(size_type n);
295 void reserve(size_type n);
298 template <class Key, class T, class Hash, class Pred, class Alloc>
299 void swap(unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
300 unordered_multimap<Key, T, Hash, Pred, Alloc>& y)
301 noexcept(noexcept(x.swap(y)));
303 template <class Key, class T, class Hash, class Pred, class Alloc>
305 operator==(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
306 const unordered_multimap<Key, T, Hash, Pred, Alloc>& y);
308 template <class Key, class T, class Hash, class Pred, class Alloc>
310 operator!=(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
311 const unordered_multimap<Key, T, Hash, Pred, Alloc>& y);
318 #include <__hash_table>
319 #include <functional>
322 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
323 #pragma GCC system_header
326 _LIBCPP_BEGIN_NAMESPACE_STD
328 template <class _Key, class _Tp, class _Hash, bool = is_empty<_Hash>::value
329 #if __has_feature(is_final)
330 && !__is_final(_Hash)
333 class __unordered_map_hasher
336 typedef pair<typename remove_const<_Key>::type, _Tp> _Pp;
337 typedef pair<const _Key, _Tp> _Cp;
339 _LIBCPP_INLINE_VISIBILITY
340 __unordered_map_hasher()
341 _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value)
343 _LIBCPP_INLINE_VISIBILITY
344 __unordered_map_hasher(const _Hash& __h)
345 _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value)
347 _LIBCPP_INLINE_VISIBILITY
348 const _Hash& hash_function() const _NOEXCEPT {return *this;}
349 _LIBCPP_INLINE_VISIBILITY
350 size_t operator()(const _Pp& __x) const
351 {return static_cast<const _Hash&>(*this)(__x.first);}
352 _LIBCPP_INLINE_VISIBILITY
353 size_t operator()(const _Cp& __x) const
354 {return static_cast<const _Hash&>(*this)(__x.first);}
355 _LIBCPP_INLINE_VISIBILITY
356 size_t operator()(const _Key& __x) const
357 {return static_cast<const _Hash&>(*this)(__x);}
360 template <class _Key, class _Tp, class _Hash>
361 class __unordered_map_hasher<_Key, _Tp, _Hash, false>
365 typedef pair<typename remove_const<_Key>::type, _Tp> _Pp;
366 typedef pair<const _Key, _Tp> _Cp;
368 _LIBCPP_INLINE_VISIBILITY
369 __unordered_map_hasher()
370 _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value)
372 _LIBCPP_INLINE_VISIBILITY
373 __unordered_map_hasher(const _Hash& __h)
374 _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value)
376 _LIBCPP_INLINE_VISIBILITY
377 const _Hash& hash_function() const _NOEXCEPT {return __hash_;}
378 _LIBCPP_INLINE_VISIBILITY
379 size_t operator()(const _Pp& __x) const
380 {return __hash_(__x.first);}
381 _LIBCPP_INLINE_VISIBILITY
382 size_t operator()(const _Cp& __x) const
383 {return __hash_(__x.first);}
384 _LIBCPP_INLINE_VISIBILITY
385 size_t operator()(const _Key& __x) const
386 {return __hash_(__x);}
389 template <class _Key, class _Tp, class _Pred, bool = is_empty<_Pred>::value
390 #if __has_feature(is_final)
391 && !__is_final(_Pred)
394 class __unordered_map_equal
397 typedef pair<typename remove_const<_Key>::type, _Tp> _Pp;
398 typedef pair<const _Key, _Tp> _Cp;
400 _LIBCPP_INLINE_VISIBILITY
401 __unordered_map_equal()
402 _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value)
404 _LIBCPP_INLINE_VISIBILITY
405 __unordered_map_equal(const _Pred& __p)
406 _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value)
408 _LIBCPP_INLINE_VISIBILITY
409 const _Pred& key_eq() const _NOEXCEPT {return *this;}
410 _LIBCPP_INLINE_VISIBILITY
411 bool operator()(const _Pp& __x, const _Pp& __y) const
412 {return static_cast<const _Pred&>(*this)(__x.first, __y.first);}
413 _LIBCPP_INLINE_VISIBILITY
414 bool operator()(const _Pp& __x, const _Cp& __y) const
415 {return static_cast<const _Pred&>(*this)(__x.first, __y.first);}
416 _LIBCPP_INLINE_VISIBILITY
417 bool operator()(const _Pp& __x, const _Key& __y) const
418 {return static_cast<const _Pred&>(*this)(__x.first, __y);}
419 _LIBCPP_INLINE_VISIBILITY
420 bool operator()(const _Cp& __x, const _Pp& __y) const
421 {return static_cast<const _Pred&>(*this)(__x.first, __y.first);}
422 _LIBCPP_INLINE_VISIBILITY
423 bool operator()(const _Cp& __x, const _Cp& __y) const
424 {return static_cast<const _Pred&>(*this)(__x.first, __y.first);}
425 _LIBCPP_INLINE_VISIBILITY
426 bool operator()(const _Cp& __x, const _Key& __y) const
427 {return static_cast<const _Pred&>(*this)(__x.first, __y);}
428 _LIBCPP_INLINE_VISIBILITY
429 bool operator()(const _Key& __x, const _Pp& __y) const
430 {return static_cast<const _Pred&>(*this)(__x, __y.first);}
431 _LIBCPP_INLINE_VISIBILITY
432 bool operator()(const _Key& __x, const _Cp& __y) const
433 {return static_cast<const _Pred&>(*this)(__x, __y.first);}
434 _LIBCPP_INLINE_VISIBILITY
435 bool operator()(const _Key& __x, const _Key& __y) const
436 {return static_cast<const _Pred&>(*this)(__x, __y);}
439 template <class _Key, class _Tp, class _Pred>
440 class __unordered_map_equal<_Key, _Tp, _Pred, false>
444 typedef pair<typename remove_const<_Key>::type, _Tp> _Pp;
445 typedef pair<const _Key, _Tp> _Cp;
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 _Pp& __x, const _Pp& __y) const
459 {return __pred_(__x.first, __y.first);}
460 _LIBCPP_INLINE_VISIBILITY
461 bool operator()(const _Pp& __x, const _Cp& __y) const
462 {return __pred_(__x.first, __y.first);}
463 _LIBCPP_INLINE_VISIBILITY
464 bool operator()(const _Pp& __x, const _Key& __y) const
465 {return __pred_(__x.first, __y);}
466 _LIBCPP_INLINE_VISIBILITY
467 bool operator()(const _Cp& __x, const _Pp& __y) const
468 {return __pred_(__x.first, __y.first);}
469 _LIBCPP_INLINE_VISIBILITY
470 bool operator()(const _Cp& __x, const _Cp& __y) const
471 {return __pred_(__x.first, __y.first);}
472 _LIBCPP_INLINE_VISIBILITY
473 bool operator()(const _Cp& __x, const _Key& __y) const
474 {return __pred_(__x.first, __y);}
475 _LIBCPP_INLINE_VISIBILITY
476 bool operator()(const _Key& __x, const _Pp& __y) const
477 {return __pred_(__x, __y.first);}
478 _LIBCPP_INLINE_VISIBILITY
479 bool operator()(const _Key& __x, const _Cp& __y) const
480 {return __pred_(__x, __y.first);}
481 _LIBCPP_INLINE_VISIBILITY
482 bool operator()(const _Key& __x, const _Key& __y) const
483 {return __pred_(__x, __y);}
486 template <class _Alloc>
487 class __hash_map_node_destructor
489 typedef _Alloc allocator_type;
490 typedef allocator_traits<allocator_type> __alloc_traits;
491 typedef typename __alloc_traits::value_type::value_type value_type;
493 typedef typename __alloc_traits::pointer pointer;
495 typedef typename value_type::first_type first_type;
496 typedef typename value_type::second_type second_type;
498 allocator_type& __na_;
500 __hash_map_node_destructor& operator=(const __hash_map_node_destructor&);
503 bool __first_constructed;
504 bool __second_constructed;
506 _LIBCPP_INLINE_VISIBILITY
507 explicit __hash_map_node_destructor(allocator_type& __na) _NOEXCEPT
509 __first_constructed(false),
510 __second_constructed(false)
513 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
514 _LIBCPP_INLINE_VISIBILITY
515 __hash_map_node_destructor(__hash_node_destructor<allocator_type>&& __x)
518 __first_constructed(__x.__value_constructed),
519 __second_constructed(__x.__value_constructed)
521 __x.__value_constructed = false;
523 #else // _LIBCPP_HAS_NO_RVALUE_REFERENCES
524 _LIBCPP_INLINE_VISIBILITY
525 __hash_map_node_destructor(const __hash_node_destructor<allocator_type>& __x)
527 __first_constructed(__x.__value_constructed),
528 __second_constructed(__x.__value_constructed)
530 const_cast<bool&>(__x.__value_constructed) = false;
532 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
534 _LIBCPP_INLINE_VISIBILITY
535 void operator()(pointer __p) _NOEXCEPT
537 if (__second_constructed)
538 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.second));
539 if (__first_constructed)
540 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.first));
542 __alloc_traits::deallocate(__na_, __p, 1);
546 template <class _HashIterator>
547 class _LIBCPP_VISIBLE __hash_map_iterator
551 typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits;
552 typedef const typename _HashIterator::value_type::first_type key_type;
553 typedef typename _HashIterator::value_type::second_type mapped_type;
555 typedef forward_iterator_tag iterator_category;
556 typedef pair<key_type, mapped_type> value_type;
557 typedef typename _HashIterator::difference_type difference_type;
558 typedef value_type& reference;
559 typedef typename __pointer_traits::template
560 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
563 rebind<value_type>::other
567 _LIBCPP_INLINE_VISIBILITY
568 __hash_map_iterator() _NOEXCEPT {}
570 _LIBCPP_INLINE_VISIBILITY
571 __hash_map_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
573 _LIBCPP_INLINE_VISIBILITY
574 reference operator*() const {return *operator->();}
575 _LIBCPP_INLINE_VISIBILITY
576 pointer operator->() const {return (pointer)__i_.operator->();}
578 _LIBCPP_INLINE_VISIBILITY
579 __hash_map_iterator& operator++() {++__i_; return *this;}
580 _LIBCPP_INLINE_VISIBILITY
581 __hash_map_iterator operator++(int)
583 __hash_map_iterator __t(*this);
588 friend _LIBCPP_INLINE_VISIBILITY
589 bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y)
590 {return __x.__i_ == __y.__i_;}
591 friend _LIBCPP_INLINE_VISIBILITY
592 bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y)
593 {return __x.__i_ != __y.__i_;}
595 template <class, class, class, class, class> friend class _LIBCPP_VISIBLE unordered_map;
596 template <class, class, class, class, class> friend class _LIBCPP_VISIBLE unordered_multimap;
597 template <class> friend class _LIBCPP_VISIBLE __hash_const_iterator;
598 template <class> friend class _LIBCPP_VISIBLE __hash_const_local_iterator;
599 template <class> friend class _LIBCPP_VISIBLE __hash_map_const_iterator;
602 template <class _HashIterator>
603 class _LIBCPP_VISIBLE __hash_map_const_iterator
607 typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits;
608 typedef const typename _HashIterator::value_type::first_type key_type;
609 typedef typename _HashIterator::value_type::second_type mapped_type;
611 typedef forward_iterator_tag iterator_category;
612 typedef pair<key_type, mapped_type> value_type;
613 typedef typename _HashIterator::difference_type difference_type;
614 typedef const value_type& reference;
615 typedef typename __pointer_traits::template
616 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
617 rebind<const value_type>
619 rebind<const value_type>::other
623 _LIBCPP_INLINE_VISIBILITY
624 __hash_map_const_iterator() _NOEXCEPT {}
626 _LIBCPP_INLINE_VISIBILITY
627 __hash_map_const_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
628 _LIBCPP_INLINE_VISIBILITY
629 __hash_map_const_iterator(
630 __hash_map_iterator<typename _HashIterator::__non_const_iterator> __i)
634 _LIBCPP_INLINE_VISIBILITY
635 reference operator*() const {return *operator->();}
636 _LIBCPP_INLINE_VISIBILITY
637 pointer operator->() const {return (pointer)__i_.operator->();}
639 _LIBCPP_INLINE_VISIBILITY
640 __hash_map_const_iterator& operator++() {++__i_; return *this;}
641 _LIBCPP_INLINE_VISIBILITY
642 __hash_map_const_iterator operator++(int)
644 __hash_map_const_iterator __t(*this);
649 friend _LIBCPP_INLINE_VISIBILITY
650 bool operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)
651 {return __x.__i_ == __y.__i_;}
652 friend _LIBCPP_INLINE_VISIBILITY
653 bool operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)
654 {return __x.__i_ != __y.__i_;}
656 template <class, class, class, class, class> friend class _LIBCPP_VISIBLE unordered_map;
657 template <class, class, class, class, class> friend class _LIBCPP_VISIBLE unordered_multimap;
658 template <class> friend class _LIBCPP_VISIBLE __hash_const_iterator;
659 template <class> friend class _LIBCPP_VISIBLE __hash_const_local_iterator;
662 template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
663 class _Alloc = allocator<pair<const _Key, _Tp> > >
664 class _LIBCPP_VISIBLE unordered_map
668 typedef _Key key_type;
669 typedef _Tp mapped_type;
670 typedef _Hash hasher;
671 typedef _Pred key_equal;
672 typedef _Alloc allocator_type;
673 typedef pair<const key_type, mapped_type> value_type;
674 typedef value_type& reference;
675 typedef const value_type& const_reference;
678 typedef pair<key_type, mapped_type> __value_type;
679 typedef __unordered_map_hasher<key_type, mapped_type, hasher> __hasher;
680 typedef __unordered_map_equal<key_type, mapped_type, key_equal> __key_equal;
681 typedef typename allocator_traits<allocator_type>::template
682 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
683 rebind_alloc<__value_type>
685 rebind_alloc<__value_type>::other
689 typedef __hash_table<__value_type, __hasher,
690 __key_equal, __allocator_type> __table;
694 typedef typename __table::__node_pointer __node_pointer;
695 typedef typename __table::__node_const_pointer __node_const_pointer;
696 typedef typename __table::__node_traits __node_traits;
697 typedef typename __table::__node_allocator __node_allocator;
698 typedef typename __table::__node __node;
699 typedef __hash_map_node_destructor<__node_allocator> _Dp;
700 typedef unique_ptr<__node, _Dp> __node_holder;
701 typedef allocator_traits<allocator_type> __alloc_traits;
703 typedef typename __alloc_traits::pointer pointer;
704 typedef typename __alloc_traits::const_pointer const_pointer;
705 typedef typename __alloc_traits::size_type size_type;
706 typedef typename __alloc_traits::difference_type difference_type;
708 typedef __hash_map_iterator<typename __table::iterator> iterator;
709 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
710 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
711 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
713 _LIBCPP_INLINE_VISIBILITY
715 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
717 explicit unordered_map(size_type __n, const hasher& __hf = hasher(),
718 const key_equal& __eql = key_equal());
719 unordered_map(size_type __n, const hasher& __hf,
720 const key_equal& __eql,
721 const allocator_type& __a);
722 template <class _InputIterator>
723 unordered_map(_InputIterator __first, _InputIterator __last);
724 template <class _InputIterator>
725 unordered_map(_InputIterator __first, _InputIterator __last,
726 size_type __n, const hasher& __hf = hasher(),
727 const key_equal& __eql = key_equal());
728 template <class _InputIterator>
729 unordered_map(_InputIterator __first, _InputIterator __last,
730 size_type __n, const hasher& __hf,
731 const key_equal& __eql,
732 const allocator_type& __a);
733 explicit unordered_map(const allocator_type& __a);
734 unordered_map(const unordered_map& __u);
735 unordered_map(const unordered_map& __u, const allocator_type& __a);
736 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
737 unordered_map(unordered_map&& __u)
738 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
739 unordered_map(unordered_map&& __u, const allocator_type& __a);
740 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
741 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
742 unordered_map(initializer_list<value_type> __il);
743 unordered_map(initializer_list<value_type> __il, size_type __n,
744 const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
745 unordered_map(initializer_list<value_type> __il, size_type __n,
746 const hasher& __hf, const key_equal& __eql,
747 const allocator_type& __a);
748 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
749 // ~unordered_map() = default;
750 _LIBCPP_INLINE_VISIBILITY
751 unordered_map& operator=(const unordered_map& __u)
753 __table_ = __u.__table_;
756 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
757 unordered_map& operator=(unordered_map&& __u)
758 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
760 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
761 unordered_map& operator=(initializer_list<value_type> __il);
762 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
764 _LIBCPP_INLINE_VISIBILITY
765 allocator_type get_allocator() const _NOEXCEPT
766 {return allocator_type(__table_.__node_alloc());}
768 _LIBCPP_INLINE_VISIBILITY
769 bool empty() const _NOEXCEPT {return __table_.size() == 0;}
770 _LIBCPP_INLINE_VISIBILITY
771 size_type size() const _NOEXCEPT {return __table_.size();}
772 _LIBCPP_INLINE_VISIBILITY
773 size_type max_size() const _NOEXCEPT {return __table_.max_size();}
775 _LIBCPP_INLINE_VISIBILITY
776 iterator begin() _NOEXCEPT {return __table_.begin();}
777 _LIBCPP_INLINE_VISIBILITY
778 iterator end() _NOEXCEPT {return __table_.end();}
779 _LIBCPP_INLINE_VISIBILITY
780 const_iterator begin() const _NOEXCEPT {return __table_.begin();}
781 _LIBCPP_INLINE_VISIBILITY
782 const_iterator end() const _NOEXCEPT {return __table_.end();}
783 _LIBCPP_INLINE_VISIBILITY
784 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
785 _LIBCPP_INLINE_VISIBILITY
786 const_iterator cend() const _NOEXCEPT {return __table_.end();}
788 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
789 #ifndef _LIBCPP_HAS_NO_VARIADICS
791 template <class... _Args>
792 pair<iterator, bool> emplace(_Args&&... __args);
794 template <class... _Args>
795 _LIBCPP_INLINE_VISIBILITY
796 iterator emplace_hint(const_iterator, _Args&&... __args)
797 {return emplace(_VSTD::forward<_Args>(__args)...).first;}
798 #endif // _LIBCPP_HAS_NO_VARIADICS
799 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
800 _LIBCPP_INLINE_VISIBILITY
801 pair<iterator, bool> insert(const value_type& __x)
802 {return __table_.__insert_unique(__x);}
803 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
805 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
806 _LIBCPP_INLINE_VISIBILITY
807 pair<iterator, bool> insert(_Pp&& __x)
808 {return __table_.__insert_unique(_VSTD::forward<_Pp>(__x));}
809 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
810 _LIBCPP_INLINE_VISIBILITY
811 iterator insert(const_iterator, const value_type& __x)
812 {return insert(__x).first;}
813 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
815 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
816 _LIBCPP_INLINE_VISIBILITY
817 iterator insert(const_iterator, _Pp&& __x)
818 {return insert(_VSTD::forward<_Pp>(__x)).first;}
819 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
820 template <class _InputIterator>
821 void insert(_InputIterator __first, _InputIterator __last);
822 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
823 _LIBCPP_INLINE_VISIBILITY
824 void insert(initializer_list<value_type> __il)
825 {insert(__il.begin(), __il.end());}
826 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
828 _LIBCPP_INLINE_VISIBILITY
829 iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);}
830 _LIBCPP_INLINE_VISIBILITY
831 size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
832 _LIBCPP_INLINE_VISIBILITY
833 iterator erase(const_iterator __first, const_iterator __last)
834 {return __table_.erase(__first.__i_, __last.__i_);}
835 _LIBCPP_INLINE_VISIBILITY
836 void clear() _NOEXCEPT {__table_.clear();}
838 _LIBCPP_INLINE_VISIBILITY
839 void swap(unordered_map& __u)
840 _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
841 {__table_.swap(__u.__table_);}
843 _LIBCPP_INLINE_VISIBILITY
844 hasher hash_function() const
845 {return __table_.hash_function().hash_function();}
846 _LIBCPP_INLINE_VISIBILITY
847 key_equal key_eq() const
848 {return __table_.key_eq().key_eq();}
850 _LIBCPP_INLINE_VISIBILITY
851 iterator find(const key_type& __k) {return __table_.find(__k);}
852 _LIBCPP_INLINE_VISIBILITY
853 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
854 _LIBCPP_INLINE_VISIBILITY
855 size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
856 _LIBCPP_INLINE_VISIBILITY
857 pair<iterator, iterator> equal_range(const key_type& __k)
858 {return __table_.__equal_range_unique(__k);}
859 _LIBCPP_INLINE_VISIBILITY
860 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
861 {return __table_.__equal_range_unique(__k);}
863 mapped_type& operator[](const key_type& __k);
864 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
865 mapped_type& operator[](key_type&& __k);
868 mapped_type& at(const key_type& __k);
869 const mapped_type& at(const key_type& __k) const;
871 _LIBCPP_INLINE_VISIBILITY
872 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
873 _LIBCPP_INLINE_VISIBILITY
874 size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
876 _LIBCPP_INLINE_VISIBILITY
877 size_type bucket_size(size_type __n) const
878 {return __table_.bucket_size(__n);}
879 _LIBCPP_INLINE_VISIBILITY
880 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
882 _LIBCPP_INLINE_VISIBILITY
883 local_iterator begin(size_type __n) {return __table_.begin(__n);}
884 _LIBCPP_INLINE_VISIBILITY
885 local_iterator end(size_type __n) {return __table_.end(__n);}
886 _LIBCPP_INLINE_VISIBILITY
887 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);}
888 _LIBCPP_INLINE_VISIBILITY
889 const_local_iterator end(size_type __n) const {return __table_.cend(__n);}
890 _LIBCPP_INLINE_VISIBILITY
891 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
892 _LIBCPP_INLINE_VISIBILITY
893 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);}
895 _LIBCPP_INLINE_VISIBILITY
896 float load_factor() const _NOEXCEPT {return __table_.load_factor();}
897 _LIBCPP_INLINE_VISIBILITY
898 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
899 _LIBCPP_INLINE_VISIBILITY
900 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
901 _LIBCPP_INLINE_VISIBILITY
902 void rehash(size_type __n) {__table_.rehash(__n);}
903 _LIBCPP_INLINE_VISIBILITY
904 void reserve(size_type __n) {__table_.reserve(__n);}
907 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
908 __node_holder __construct_node();
912 is_constructible<value_type, _A0>::value,
915 __construct_node(_A0&& __a0);
919 is_constructible<key_type, _A0>::value,
922 __construct_node(_A0&& __a0);
923 #ifndef _LIBCPP_HAS_NO_VARIADICS
924 template <class _A0, class _A1, class ..._Args>
925 __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args);
926 #endif // _LIBCPP_HAS_NO_VARIADICS
927 #else // _LIBCPP_HAS_NO_RVALUE_REFERENCES
928 __node_holder __construct_node(const key_type& __k);
932 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
933 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
934 size_type __n, const hasher& __hf, const key_equal& __eql)
935 : __table_(__hf, __eql)
937 __table_.rehash(__n);
940 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
941 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
942 size_type __n, const hasher& __hf, const key_equal& __eql,
943 const allocator_type& __a)
944 : __table_(__hf, __eql, __a)
946 __table_.rehash(__n);
949 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
950 inline _LIBCPP_INLINE_VISIBILITY
951 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
952 const allocator_type& __a)
957 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
958 template <class _InputIterator>
959 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
960 _InputIterator __first, _InputIterator __last)
962 insert(__first, __last);
965 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
966 template <class _InputIterator>
967 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
968 _InputIterator __first, _InputIterator __last, size_type __n,
969 const hasher& __hf, const key_equal& __eql)
970 : __table_(__hf, __eql)
972 __table_.rehash(__n);
973 insert(__first, __last);
976 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
977 template <class _InputIterator>
978 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
979 _InputIterator __first, _InputIterator __last, size_type __n,
980 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
981 : __table_(__hf, __eql, __a)
983 __table_.rehash(__n);
984 insert(__first, __last);
987 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
988 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
989 const unordered_map& __u)
990 : __table_(__u.__table_)
992 __table_.rehash(__u.bucket_count());
993 insert(__u.begin(), __u.end());
996 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
997 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
998 const unordered_map& __u, const allocator_type& __a)
999 : __table_(__u.__table_, __a)
1001 __table_.rehash(__u.bucket_count());
1002 insert(__u.begin(), __u.end());
1005 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1007 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1008 inline _LIBCPP_INLINE_VISIBILITY
1009 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1010 unordered_map&& __u)
1011 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
1012 : __table_(_VSTD::move(__u.__table_))
1016 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1017 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1018 unordered_map&& __u, const allocator_type& __a)
1019 : __table_(_VSTD::move(__u.__table_), __a)
1021 if (__a != __u.get_allocator())
1023 iterator __i = __u.begin();
1024 while (__u.size() != 0)
1025 __table_.__insert_unique(
1026 _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_)
1031 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1033 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1035 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1036 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1037 initializer_list<value_type> __il)
1039 insert(__il.begin(), __il.end());
1042 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1043 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1044 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1045 const key_equal& __eql)
1046 : __table_(__hf, __eql)
1048 __table_.rehash(__n);
1049 insert(__il.begin(), __il.end());
1052 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1053 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1054 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1055 const key_equal& __eql, const allocator_type& __a)
1056 : __table_(__hf, __eql, __a)
1058 __table_.rehash(__n);
1059 insert(__il.begin(), __il.end());
1062 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1064 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1066 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1067 inline _LIBCPP_INLINE_VISIBILITY
1068 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
1069 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_map&& __u)
1070 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
1072 __table_ = _VSTD::move(__u.__table_);
1076 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1078 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1080 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1081 inline _LIBCPP_INLINE_VISIBILITY
1082 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
1083 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(
1084 initializer_list<value_type> __il)
1086 __table_.__assign_unique(__il.begin(), __il.end());
1090 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1092 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1094 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1095 typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1096 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node()
1098 __node_allocator& __na = __table_.__node_alloc();
1099 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1100 __node_traits::construct(__na, _VSTD::addressof(__h->__value_));
1101 __h.get_deleter().__first_constructed = true;
1102 __h.get_deleter().__second_constructed = true;
1106 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1107 template <class _A0>
1110 is_constructible<pair<const _Key, _Tp>, _A0>::value,
1111 typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1113 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
1115 __node_allocator& __na = __table_.__node_alloc();
1116 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1117 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1118 _VSTD::forward<_A0>(__a0));
1119 __h.get_deleter().__first_constructed = true;
1120 __h.get_deleter().__second_constructed = true;
1124 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1125 template <class _A0>
1128 is_constructible<_Key, _A0>::value,
1129 typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1131 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
1133 __node_allocator& __na = __table_.__node_alloc();
1134 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1135 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first),
1136 _VSTD::forward<_A0>(__a0));
1137 __h.get_deleter().__first_constructed = true;
1138 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second));
1139 __h.get_deleter().__second_constructed = true;
1143 #ifndef _LIBCPP_HAS_NO_VARIADICS
1145 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1146 template <class _A0, class _A1, class ..._Args>
1147 typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1148 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0,
1152 __node_allocator& __na = __table_.__node_alloc();
1153 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1154 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1155 _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1),
1156 _VSTD::forward<_Args>(__args)...);
1157 __h.get_deleter().__first_constructed = true;
1158 __h.get_deleter().__second_constructed = true;
1162 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1163 template <class... _Args>
1164 pair<typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator, bool>
1165 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_Args&&... __args)
1167 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1168 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1174 #endif // _LIBCPP_HAS_NO_VARIADICS
1175 #else // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1177 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1178 typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1179 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(const key_type& __k)
1181 __node_allocator& __na = __table_.__node_alloc();
1182 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1183 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first), __k);
1184 __h.get_deleter().__first_constructed = true;
1185 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second));
1186 __h.get_deleter().__second_constructed = true;
1187 return _VSTD::move(__h);
1190 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1192 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1193 template <class _InputIterator>
1194 inline _LIBCPP_INLINE_VISIBILITY
1196 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
1197 _InputIterator __last)
1199 for (; __first != __last; ++__first)
1200 __table_.__insert_unique(*__first);
1203 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1205 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k)
1207 iterator __i = find(__k);
1210 __node_holder __h = __construct_node(__k);
1211 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1213 return __r.first->second;
1216 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1218 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1220 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&& __k)
1222 iterator __i = find(__k);
1225 __node_holder __h = __construct_node(_VSTD::move(__k));
1226 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1228 return __r.first->second;
1231 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1233 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1235 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k)
1237 iterator __i = find(__k);
1238 #ifndef _LIBCPP_NO_EXCEPTIONS
1240 throw out_of_range("unordered_map::at: key not found");
1241 #endif // _LIBCPP_NO_EXCEPTIONS
1245 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1247 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) const
1249 const_iterator __i = find(__k);
1250 #ifndef _LIBCPP_NO_EXCEPTIONS
1252 throw out_of_range("unordered_map::at: key not found");
1253 #endif // _LIBCPP_NO_EXCEPTIONS
1257 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1258 inline _LIBCPP_INLINE_VISIBILITY
1260 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1261 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1262 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1267 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1269 operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1270 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1272 if (__x.size() != __y.size())
1274 typedef typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
1276 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();
1279 const_iterator __j = __y.find(__i->first);
1280 if (__j == __ey || !(*__i == *__j))
1286 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1287 inline _LIBCPP_INLINE_VISIBILITY
1289 operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1290 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1292 return !(__x == __y);
1295 template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
1296 class _Alloc = allocator<pair<const _Key, _Tp> > >
1297 class _LIBCPP_VISIBLE unordered_multimap
1301 typedef _Key key_type;
1302 typedef _Tp mapped_type;
1303 typedef _Hash hasher;
1304 typedef _Pred key_equal;
1305 typedef _Alloc allocator_type;
1306 typedef pair<const key_type, mapped_type> value_type;
1307 typedef value_type& reference;
1308 typedef const value_type& const_reference;
1311 typedef pair<key_type, mapped_type> __value_type;
1312 typedef __unordered_map_hasher<key_type, mapped_type, hasher> __hasher;
1313 typedef __unordered_map_equal<key_type, mapped_type, key_equal> __key_equal;
1314 typedef typename allocator_traits<allocator_type>::template
1315 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
1316 rebind_alloc<__value_type>
1318 rebind_alloc<__value_type>::other
1322 typedef __hash_table<__value_type, __hasher,
1323 __key_equal, __allocator_type> __table;
1327 typedef typename __table::__node_traits __node_traits;
1328 typedef typename __table::__node_allocator __node_allocator;
1329 typedef typename __table::__node __node;
1330 typedef __hash_map_node_destructor<__node_allocator> _Dp;
1331 typedef unique_ptr<__node, _Dp> __node_holder;
1332 typedef allocator_traits<allocator_type> __alloc_traits;
1334 typedef typename __alloc_traits::pointer pointer;
1335 typedef typename __alloc_traits::const_pointer const_pointer;
1336 typedef typename __alloc_traits::size_type size_type;
1337 typedef typename __alloc_traits::difference_type difference_type;
1339 typedef __hash_map_iterator<typename __table::iterator> iterator;
1340 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
1341 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
1342 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
1344 _LIBCPP_INLINE_VISIBILITY
1345 unordered_multimap()
1346 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
1348 explicit unordered_multimap(size_type __n, const hasher& __hf = hasher(),
1349 const key_equal& __eql = key_equal());
1350 unordered_multimap(size_type __n, const hasher& __hf,
1351 const key_equal& __eql,
1352 const allocator_type& __a);
1353 template <class _InputIterator>
1354 unordered_multimap(_InputIterator __first, _InputIterator __last);
1355 template <class _InputIterator>
1356 unordered_multimap(_InputIterator __first, _InputIterator __last,
1357 size_type __n, const hasher& __hf = hasher(),
1358 const key_equal& __eql = key_equal());
1359 template <class _InputIterator>
1360 unordered_multimap(_InputIterator __first, _InputIterator __last,
1361 size_type __n, const hasher& __hf,
1362 const key_equal& __eql,
1363 const allocator_type& __a);
1364 explicit unordered_multimap(const allocator_type& __a);
1365 unordered_multimap(const unordered_multimap& __u);
1366 unordered_multimap(const unordered_multimap& __u, const allocator_type& __a);
1367 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1368 unordered_multimap(unordered_multimap&& __u)
1369 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
1370 unordered_multimap(unordered_multimap&& __u, const allocator_type& __a);
1371 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1372 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1373 unordered_multimap(initializer_list<value_type> __il);
1374 unordered_multimap(initializer_list<value_type> __il, size_type __n,
1375 const hasher& __hf = hasher(),
1376 const key_equal& __eql = key_equal());
1377 unordered_multimap(initializer_list<value_type> __il, size_type __n,
1378 const hasher& __hf, const key_equal& __eql,
1379 const allocator_type& __a);
1380 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1381 // ~unordered_multimap() = default;
1382 _LIBCPP_INLINE_VISIBILITY
1383 unordered_multimap& operator=(const unordered_multimap& __u)
1385 __table_ = __u.__table_;
1388 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1389 unordered_multimap& operator=(unordered_multimap&& __u)
1390 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
1392 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1393 unordered_multimap& operator=(initializer_list<value_type> __il);
1394 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1396 _LIBCPP_INLINE_VISIBILITY
1397 allocator_type get_allocator() const _NOEXCEPT
1398 {return allocator_type(__table_.__node_alloc());}
1400 _LIBCPP_INLINE_VISIBILITY
1401 bool empty() const _NOEXCEPT {return __table_.size() == 0;}
1402 _LIBCPP_INLINE_VISIBILITY
1403 size_type size() const _NOEXCEPT {return __table_.size();}
1404 _LIBCPP_INLINE_VISIBILITY
1405 size_type max_size() const _NOEXCEPT {return __table_.max_size();}
1407 _LIBCPP_INLINE_VISIBILITY
1408 iterator begin() _NOEXCEPT {return __table_.begin();}
1409 _LIBCPP_INLINE_VISIBILITY
1410 iterator end() _NOEXCEPT {return __table_.end();}
1411 _LIBCPP_INLINE_VISIBILITY
1412 const_iterator begin() const _NOEXCEPT {return __table_.begin();}
1413 _LIBCPP_INLINE_VISIBILITY
1414 const_iterator end() const _NOEXCEPT {return __table_.end();}
1415 _LIBCPP_INLINE_VISIBILITY
1416 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
1417 _LIBCPP_INLINE_VISIBILITY
1418 const_iterator cend() const _NOEXCEPT {return __table_.end();}
1420 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1421 #ifndef _LIBCPP_HAS_NO_VARIADICS
1423 template <class... _Args>
1424 iterator emplace(_Args&&... __args);
1426 template <class... _Args>
1427 iterator emplace_hint(const_iterator __p, _Args&&... __args);
1428 #endif // _LIBCPP_HAS_NO_VARIADICS
1429 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1430 _LIBCPP_INLINE_VISIBILITY
1431 iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
1432 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1433 template <class _Pp,
1434 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1435 _LIBCPP_INLINE_VISIBILITY
1436 iterator insert(_Pp&& __x)
1437 {return __table_.__insert_multi(_VSTD::forward<_Pp>(__x));}
1438 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1439 _LIBCPP_INLINE_VISIBILITY
1440 iterator insert(const_iterator __p, const value_type& __x)
1441 {return __table_.__insert_multi(__p.__i_, __x);}
1442 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1443 template <class _Pp,
1444 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1445 _LIBCPP_INLINE_VISIBILITY
1446 iterator insert(const_iterator __p, _Pp&& __x)
1447 {return __table_.__insert_multi(__p.__i_, _VSTD::forward<_Pp>(__x));}
1448 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1449 template <class _InputIterator>
1450 void insert(_InputIterator __first, _InputIterator __last);
1451 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1452 _LIBCPP_INLINE_VISIBILITY
1453 void insert(initializer_list<value_type> __il)
1454 {insert(__il.begin(), __il.end());}
1455 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1457 _LIBCPP_INLINE_VISIBILITY
1458 iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);}
1459 _LIBCPP_INLINE_VISIBILITY
1460 size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
1461 _LIBCPP_INLINE_VISIBILITY
1462 iterator erase(const_iterator __first, const_iterator __last)
1463 {return __table_.erase(__first.__i_, __last.__i_);}
1464 _LIBCPP_INLINE_VISIBILITY
1465 void clear() _NOEXCEPT {__table_.clear();}
1467 _LIBCPP_INLINE_VISIBILITY
1468 void swap(unordered_multimap& __u)
1469 _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
1470 {__table_.swap(__u.__table_);}
1472 _LIBCPP_INLINE_VISIBILITY
1473 hasher hash_function() const
1474 {return __table_.hash_function().hash_function();}
1475 _LIBCPP_INLINE_VISIBILITY
1476 key_equal key_eq() const
1477 {return __table_.key_eq().key_eq();}
1479 _LIBCPP_INLINE_VISIBILITY
1480 iterator find(const key_type& __k) {return __table_.find(__k);}
1481 _LIBCPP_INLINE_VISIBILITY
1482 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
1483 _LIBCPP_INLINE_VISIBILITY
1484 size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
1485 _LIBCPP_INLINE_VISIBILITY
1486 pair<iterator, iterator> equal_range(const key_type& __k)
1487 {return __table_.__equal_range_multi(__k);}
1488 _LIBCPP_INLINE_VISIBILITY
1489 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
1490 {return __table_.__equal_range_multi(__k);}
1492 _LIBCPP_INLINE_VISIBILITY
1493 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
1494 _LIBCPP_INLINE_VISIBILITY
1495 size_type max_bucket_count() const _NOEXCEPT
1496 {return __table_.max_bucket_count();}
1498 _LIBCPP_INLINE_VISIBILITY
1499 size_type bucket_size(size_type __n) const
1500 {return __table_.bucket_size(__n);}
1501 _LIBCPP_INLINE_VISIBILITY
1502 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
1504 _LIBCPP_INLINE_VISIBILITY
1505 local_iterator begin(size_type __n) {return __table_.begin(__n);}
1506 _LIBCPP_INLINE_VISIBILITY
1507 local_iterator end(size_type __n) {return __table_.end(__n);}
1508 _LIBCPP_INLINE_VISIBILITY
1509 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);}
1510 _LIBCPP_INLINE_VISIBILITY
1511 const_local_iterator end(size_type __n) const {return __table_.cend(__n);}
1512 _LIBCPP_INLINE_VISIBILITY
1513 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
1514 _LIBCPP_INLINE_VISIBILITY
1515 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);}
1517 _LIBCPP_INLINE_VISIBILITY
1518 float load_factor() const _NOEXCEPT {return __table_.load_factor();}
1519 _LIBCPP_INLINE_VISIBILITY
1520 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
1521 _LIBCPP_INLINE_VISIBILITY
1522 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
1523 _LIBCPP_INLINE_VISIBILITY
1524 void rehash(size_type __n) {__table_.rehash(__n);}
1525 _LIBCPP_INLINE_VISIBILITY
1526 void reserve(size_type __n) {__table_.reserve(__n);}
1529 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1530 __node_holder __construct_node();
1531 template <class _A0>
1534 is_constructible<value_type, _A0>::value,
1537 __construct_node(_A0&& __a0);
1538 template <class _A0>
1541 is_constructible<key_type, _A0>::value,
1544 __construct_node(_A0&& __a0);
1545 #ifndef _LIBCPP_HAS_NO_VARIADICS
1546 template <class _A0, class _A1, class ..._Args>
1547 __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args);
1548 #endif // _LIBCPP_HAS_NO_VARIADICS
1549 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1552 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1553 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1554 size_type __n, const hasher& __hf, const key_equal& __eql)
1555 : __table_(__hf, __eql)
1557 __table_.rehash(__n);
1560 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1561 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1562 size_type __n, const hasher& __hf, const key_equal& __eql,
1563 const allocator_type& __a)
1564 : __table_(__hf, __eql, __a)
1566 __table_.rehash(__n);
1569 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1570 template <class _InputIterator>
1571 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1572 _InputIterator __first, _InputIterator __last)
1574 insert(__first, __last);
1577 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1578 template <class _InputIterator>
1579 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1580 _InputIterator __first, _InputIterator __last, size_type __n,
1581 const hasher& __hf, const key_equal& __eql)
1582 : __table_(__hf, __eql)
1584 __table_.rehash(__n);
1585 insert(__first, __last);
1588 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1589 template <class _InputIterator>
1590 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1591 _InputIterator __first, _InputIterator __last, size_type __n,
1592 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1593 : __table_(__hf, __eql, __a)
1595 __table_.rehash(__n);
1596 insert(__first, __last);
1599 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1600 inline _LIBCPP_INLINE_VISIBILITY
1601 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1602 const allocator_type& __a)
1607 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1608 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1609 const unordered_multimap& __u)
1610 : __table_(__u.__table_)
1612 __table_.rehash(__u.bucket_count());
1613 insert(__u.begin(), __u.end());
1616 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1617 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1618 const unordered_multimap& __u, const allocator_type& __a)
1619 : __table_(__u.__table_, __a)
1621 __table_.rehash(__u.bucket_count());
1622 insert(__u.begin(), __u.end());
1625 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1627 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1628 inline _LIBCPP_INLINE_VISIBILITY
1629 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1630 unordered_multimap&& __u)
1631 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
1632 : __table_(_VSTD::move(__u.__table_))
1636 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1637 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1638 unordered_multimap&& __u, const allocator_type& __a)
1639 : __table_(_VSTD::move(__u.__table_), __a)
1641 if (__a != __u.get_allocator())
1643 iterator __i = __u.begin();
1644 while (__u.size() != 0)
1646 __table_.__insert_multi(
1647 _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_)
1653 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1655 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1657 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1658 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1659 initializer_list<value_type> __il)
1661 insert(__il.begin(), __il.end());
1664 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1665 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1666 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1667 const key_equal& __eql)
1668 : __table_(__hf, __eql)
1670 __table_.rehash(__n);
1671 insert(__il.begin(), __il.end());
1674 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1675 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1676 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1677 const key_equal& __eql, const allocator_type& __a)
1678 : __table_(__hf, __eql, __a)
1680 __table_.rehash(__n);
1681 insert(__il.begin(), __il.end());
1684 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1686 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1688 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1689 inline _LIBCPP_INLINE_VISIBILITY
1690 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
1691 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_multimap&& __u)
1692 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
1694 __table_ = _VSTD::move(__u.__table_);
1698 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1700 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1702 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1703 inline _LIBCPP_INLINE_VISIBILITY
1704 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
1705 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(
1706 initializer_list<value_type> __il)
1708 __table_.__assign_multi(__il.begin(), __il.end());
1712 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1714 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1716 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1717 typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1718 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node()
1720 __node_allocator& __na = __table_.__node_alloc();
1721 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1722 __node_traits::construct(__na, _VSTD::addressof(__h->__value_));
1723 __h.get_deleter().__first_constructed = true;
1724 __h.get_deleter().__second_constructed = true;
1728 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1729 template <class _A0>
1732 is_constructible<pair<const _Key, _Tp>, _A0>::value,
1733 typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1735 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
1737 __node_allocator& __na = __table_.__node_alloc();
1738 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1739 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1740 _VSTD::forward<_A0>(__a0));
1741 __h.get_deleter().__first_constructed = true;
1742 __h.get_deleter().__second_constructed = true;
1746 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1747 template <class _A0>
1750 is_constructible<_Key, _A0>::value,
1751 typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1753 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
1755 __node_allocator& __na = __table_.__node_alloc();
1756 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1757 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first),
1758 _VSTD::forward<_A0>(__a0));
1759 __h.get_deleter().__first_constructed = true;
1760 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second));
1761 __h.get_deleter().__second_constructed = true;
1765 #ifndef _LIBCPP_HAS_NO_VARIADICS
1767 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1768 template <class _A0, class _A1, class ..._Args>
1769 typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1770 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(
1771 _A0&& __a0, _A1&& __a1, _Args&&... __args)
1773 __node_allocator& __na = __table_.__node_alloc();
1774 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1775 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1776 _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1),
1777 _VSTD::forward<_Args>(__args)...);
1778 __h.get_deleter().__first_constructed = true;
1779 __h.get_deleter().__second_constructed = true;
1783 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1784 template <class... _Args>
1785 typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator
1786 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_Args&&... __args)
1788 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1789 iterator __r = __table_.__node_insert_multi(__h.get());
1794 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1795 template <class... _Args>
1796 typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator
1797 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace_hint(
1798 const_iterator __p, _Args&&... __args)
1800 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1801 iterator __r = __table_.__node_insert_multi(__p.__i_, __h.get());
1806 #endif // _LIBCPP_HAS_NO_VARIADICS
1807 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1809 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1810 template <class _InputIterator>
1811 inline _LIBCPP_INLINE_VISIBILITY
1813 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
1814 _InputIterator __last)
1816 for (; __first != __last; ++__first)
1817 __table_.__insert_multi(*__first);
1820 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1821 inline _LIBCPP_INLINE_VISIBILITY
1823 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1824 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1825 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1830 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1832 operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1833 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1835 if (__x.size() != __y.size())
1837 typedef typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
1839 typedef pair<const_iterator, const_iterator> _EqRng;
1840 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;)
1842 _EqRng __xeq = __x.equal_range(__i->first);
1843 _EqRng __yeq = __y.equal_range(__i->first);
1844 if (_VSTD::distance(__xeq.first, __xeq.second) !=
1845 _VSTD::distance(__yeq.first, __yeq.second) ||
1846 !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first))
1853 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1854 inline _LIBCPP_INLINE_VISIBILITY
1856 operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1857 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1859 return !(__x == __y);
1862 _LIBCPP_END_NAMESPACE_STD
1864 #endif // _LIBCPP_UNORDERED_MAP