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 _Cp, class _Hash, bool = is_empty<_Hash>::value
329 #if __has_feature(is_final)
330 && !__is_final(_Hash)
333 class __unordered_map_hasher
337 _LIBCPP_INLINE_VISIBILITY
338 __unordered_map_hasher()
339 _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value)
341 _LIBCPP_INLINE_VISIBILITY
342 __unordered_map_hasher(const _Hash& __h)
343 _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value)
345 _LIBCPP_INLINE_VISIBILITY
346 const _Hash& hash_function() const _NOEXCEPT {return *this;}
347 _LIBCPP_INLINE_VISIBILITY
348 size_t operator()(const _Cp& __x) const
349 {return static_cast<const _Hash&>(*this)(__x.__cc.first);}
350 _LIBCPP_INLINE_VISIBILITY
351 size_t operator()(const _Key& __x) const
352 {return static_cast<const _Hash&>(*this)(__x);}
355 template <class _Key, class _Cp, class _Hash>
356 class __unordered_map_hasher<_Key, _Cp, _Hash, false>
361 _LIBCPP_INLINE_VISIBILITY
362 __unordered_map_hasher()
363 _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value)
365 _LIBCPP_INLINE_VISIBILITY
366 __unordered_map_hasher(const _Hash& __h)
367 _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value)
369 _LIBCPP_INLINE_VISIBILITY
370 const _Hash& hash_function() const _NOEXCEPT {return __hash_;}
371 _LIBCPP_INLINE_VISIBILITY
372 size_t operator()(const _Cp& __x) const
373 {return __hash_(__x.__cc.first);}
374 _LIBCPP_INLINE_VISIBILITY
375 size_t operator()(const _Key& __x) const
376 {return __hash_(__x);}
379 template <class _Key, class _Cp, class _Pred, bool = is_empty<_Pred>::value
380 #if __has_feature(is_final)
381 && !__is_final(_Pred)
384 class __unordered_map_equal
388 _LIBCPP_INLINE_VISIBILITY
389 __unordered_map_equal()
390 _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value)
392 _LIBCPP_INLINE_VISIBILITY
393 __unordered_map_equal(const _Pred& __p)
394 _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value)
396 _LIBCPP_INLINE_VISIBILITY
397 const _Pred& key_eq() const _NOEXCEPT {return *this;}
398 _LIBCPP_INLINE_VISIBILITY
399 bool operator()(const _Cp& __x, const _Cp& __y) const
400 {return static_cast<const _Pred&>(*this)(__x.__cc.first, __y.__cc.first);}
401 _LIBCPP_INLINE_VISIBILITY
402 bool operator()(const _Cp& __x, const _Key& __y) const
403 {return static_cast<const _Pred&>(*this)(__x.__cc.first, __y);}
404 _LIBCPP_INLINE_VISIBILITY
405 bool operator()(const _Key& __x, const _Cp& __y) const
406 {return static_cast<const _Pred&>(*this)(__x, __y.__cc.first);}
409 template <class _Key, class _Cp, class _Pred>
410 class __unordered_map_equal<_Key, _Cp, _Pred, false>
415 _LIBCPP_INLINE_VISIBILITY
416 __unordered_map_equal()
417 _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value)
419 _LIBCPP_INLINE_VISIBILITY
420 __unordered_map_equal(const _Pred& __p)
421 _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value)
423 _LIBCPP_INLINE_VISIBILITY
424 const _Pred& key_eq() const _NOEXCEPT {return __pred_;}
425 _LIBCPP_INLINE_VISIBILITY
426 bool operator()(const _Cp& __x, const _Cp& __y) const
427 {return __pred_(__x.__cc.first, __y.__cc.first);}
428 _LIBCPP_INLINE_VISIBILITY
429 bool operator()(const _Cp& __x, const _Key& __y) const
430 {return __pred_(__x.__cc.first, __y);}
431 _LIBCPP_INLINE_VISIBILITY
432 bool operator()(const _Key& __x, const _Cp& __y) const
433 {return __pred_(__x, __y.__cc.first);}
436 template <class _Alloc>
437 class __hash_map_node_destructor
439 typedef _Alloc allocator_type;
440 typedef allocator_traits<allocator_type> __alloc_traits;
441 typedef typename __alloc_traits::value_type::value_type value_type;
443 typedef typename __alloc_traits::pointer pointer;
445 typedef typename value_type::value_type::first_type first_type;
446 typedef typename value_type::value_type::second_type second_type;
448 allocator_type& __na_;
450 __hash_map_node_destructor& operator=(const __hash_map_node_destructor&);
453 bool __first_constructed;
454 bool __second_constructed;
456 _LIBCPP_INLINE_VISIBILITY
457 explicit __hash_map_node_destructor(allocator_type& __na) _NOEXCEPT
459 __first_constructed(false),
460 __second_constructed(false)
463 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
464 _LIBCPP_INLINE_VISIBILITY
465 __hash_map_node_destructor(__hash_node_destructor<allocator_type>&& __x)
468 __first_constructed(__x.__value_constructed),
469 __second_constructed(__x.__value_constructed)
471 __x.__value_constructed = false;
473 #else // _LIBCPP_HAS_NO_RVALUE_REFERENCES
474 _LIBCPP_INLINE_VISIBILITY
475 __hash_map_node_destructor(const __hash_node_destructor<allocator_type>& __x)
477 __first_constructed(__x.__value_constructed),
478 __second_constructed(__x.__value_constructed)
480 const_cast<bool&>(__x.__value_constructed) = false;
482 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
484 _LIBCPP_INLINE_VISIBILITY
485 void operator()(pointer __p) _NOEXCEPT
487 if (__second_constructed)
488 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.second));
489 if (__first_constructed)
490 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.first));
492 __alloc_traits::deallocate(__na_, __p, 1);
496 template <class _HashIterator>
497 class _LIBCPP_TYPE_VIS __hash_map_iterator
501 typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits;
502 typedef const typename _HashIterator::value_type::value_type::first_type key_type;
503 typedef typename _HashIterator::value_type::value_type::second_type mapped_type;
505 typedef forward_iterator_tag iterator_category;
506 typedef pair<key_type, mapped_type> value_type;
507 typedef typename _HashIterator::difference_type difference_type;
508 typedef value_type& reference;
509 typedef typename __pointer_traits::template
510 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
513 rebind<value_type>::other
517 _LIBCPP_INLINE_VISIBILITY
518 __hash_map_iterator() _NOEXCEPT {}
520 _LIBCPP_INLINE_VISIBILITY
521 __hash_map_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
523 _LIBCPP_INLINE_VISIBILITY
524 reference operator*() const {return __i_->__cc;}
525 _LIBCPP_INLINE_VISIBILITY
526 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);}
528 _LIBCPP_INLINE_VISIBILITY
529 __hash_map_iterator& operator++() {++__i_; return *this;}
530 _LIBCPP_INLINE_VISIBILITY
531 __hash_map_iterator operator++(int)
533 __hash_map_iterator __t(*this);
538 friend _LIBCPP_INLINE_VISIBILITY
539 bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y)
540 {return __x.__i_ == __y.__i_;}
541 friend _LIBCPP_INLINE_VISIBILITY
542 bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y)
543 {return __x.__i_ != __y.__i_;}
545 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_map;
546 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_multimap;
547 template <class> friend class _LIBCPP_TYPE_VIS __hash_const_iterator;
548 template <class> friend class _LIBCPP_TYPE_VIS __hash_const_local_iterator;
549 template <class> friend class _LIBCPP_TYPE_VIS __hash_map_const_iterator;
552 template <class _HashIterator>
553 class _LIBCPP_TYPE_VIS __hash_map_const_iterator
557 typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits;
558 typedef const typename _HashIterator::value_type::value_type::first_type key_type;
559 typedef typename _HashIterator::value_type::value_type::second_type mapped_type;
561 typedef forward_iterator_tag iterator_category;
562 typedef pair<key_type, mapped_type> value_type;
563 typedef typename _HashIterator::difference_type difference_type;
564 typedef const value_type& reference;
565 typedef typename __pointer_traits::template
566 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
567 rebind<const value_type>
569 rebind<const value_type>::other
573 _LIBCPP_INLINE_VISIBILITY
574 __hash_map_const_iterator() _NOEXCEPT {}
576 _LIBCPP_INLINE_VISIBILITY
577 __hash_map_const_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
578 _LIBCPP_INLINE_VISIBILITY
579 __hash_map_const_iterator(
580 __hash_map_iterator<typename _HashIterator::__non_const_iterator> __i)
584 _LIBCPP_INLINE_VISIBILITY
585 reference operator*() const {return __i_->__cc;}
586 _LIBCPP_INLINE_VISIBILITY
587 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);}
589 _LIBCPP_INLINE_VISIBILITY
590 __hash_map_const_iterator& operator++() {++__i_; return *this;}
591 _LIBCPP_INLINE_VISIBILITY
592 __hash_map_const_iterator operator++(int)
594 __hash_map_const_iterator __t(*this);
599 friend _LIBCPP_INLINE_VISIBILITY
600 bool operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)
601 {return __x.__i_ == __y.__i_;}
602 friend _LIBCPP_INLINE_VISIBILITY
603 bool operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)
604 {return __x.__i_ != __y.__i_;}
606 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_map;
607 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_multimap;
608 template <class> friend class _LIBCPP_TYPE_VIS __hash_const_iterator;
609 template <class> friend class _LIBCPP_TYPE_VIS __hash_const_local_iterator;
612 template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
613 class _Alloc = allocator<pair<const _Key, _Tp> > >
614 class _LIBCPP_TYPE_VIS unordered_map
618 typedef _Key key_type;
619 typedef _Tp mapped_type;
620 typedef _Hash hasher;
621 typedef _Pred key_equal;
622 typedef _Alloc allocator_type;
623 typedef pair<const key_type, mapped_type> value_type;
624 typedef pair<key_type, mapped_type> __nc_value_type;
625 typedef value_type& reference;
626 typedef const value_type& const_reference;
629 #if __cplusplus >= 201103L
632 typedef typename unordered_map::value_type value_type;
633 typedef typename unordered_map::__nc_value_type __nc_value_type;
635 __nc_value_type __nc;
637 template <class ..._Args>
638 __value_type(_Args&& ...__args)
639 : __cc(std::forward<_Args>(__args)...) {}
641 __value_type(const __value_type& __v)
642 : __cc(std::move(__v.__cc)) {}
644 __value_type(__value_type&& __v)
645 : __nc(std::move(__v.__nc)) {}
647 __value_type& operator=(const __value_type& __v)
648 {__nc = __v.__cc; return *this;}
650 __value_type& operator=(__value_type&& __v)
651 {__nc = std::move(__v.__nc); return *this;}
653 ~__value_type() {__cc.~value_type();}
658 typedef typename unordered_map::value_type value_type;
664 __value_type(const _A0& __a0)
667 template <class _A0, class _A1>
668 __value_type(const _A0& __a0, const _A1& __a1)
669 : __cc(__a0, __a1) {}
672 typedef __unordered_map_hasher<key_type, __value_type, hasher> __hasher;
673 typedef __unordered_map_equal<key_type, __value_type, key_equal> __key_equal;
674 typedef typename allocator_traits<allocator_type>::template
675 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
676 rebind_alloc<__value_type>
678 rebind_alloc<__value_type>::other
682 typedef __hash_table<__value_type, __hasher,
683 __key_equal, __allocator_type> __table;
687 typedef typename __table::__node_pointer __node_pointer;
688 typedef typename __table::__node_const_pointer __node_const_pointer;
689 typedef typename __table::__node_traits __node_traits;
690 typedef typename __table::__node_allocator __node_allocator;
691 typedef typename __table::__node __node;
692 typedef __hash_map_node_destructor<__node_allocator> _Dp;
693 typedef unique_ptr<__node, _Dp> __node_holder;
694 typedef allocator_traits<allocator_type> __alloc_traits;
696 typedef typename __alloc_traits::pointer pointer;
697 typedef typename __alloc_traits::const_pointer const_pointer;
698 typedef typename __alloc_traits::size_type size_type;
699 typedef typename __alloc_traits::difference_type difference_type;
701 typedef __hash_map_iterator<typename __table::iterator> iterator;
702 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
703 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
704 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
706 _LIBCPP_INLINE_VISIBILITY
708 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
710 explicit unordered_map(size_type __n, const hasher& __hf = hasher(),
711 const key_equal& __eql = key_equal());
712 unordered_map(size_type __n, const hasher& __hf,
713 const key_equal& __eql,
714 const allocator_type& __a);
715 template <class _InputIterator>
716 unordered_map(_InputIterator __first, _InputIterator __last);
717 template <class _InputIterator>
718 unordered_map(_InputIterator __first, _InputIterator __last,
719 size_type __n, const hasher& __hf = hasher(),
720 const key_equal& __eql = key_equal());
721 template <class _InputIterator>
722 unordered_map(_InputIterator __first, _InputIterator __last,
723 size_type __n, const hasher& __hf,
724 const key_equal& __eql,
725 const allocator_type& __a);
726 explicit unordered_map(const allocator_type& __a);
727 unordered_map(const unordered_map& __u);
728 unordered_map(const unordered_map& __u, const allocator_type& __a);
729 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
730 unordered_map(unordered_map&& __u)
731 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
732 unordered_map(unordered_map&& __u, const allocator_type& __a);
733 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
734 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
735 unordered_map(initializer_list<value_type> __il);
736 unordered_map(initializer_list<value_type> __il, size_type __n,
737 const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
738 unordered_map(initializer_list<value_type> __il, size_type __n,
739 const hasher& __hf, const key_equal& __eql,
740 const allocator_type& __a);
741 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
742 // ~unordered_map() = default;
743 _LIBCPP_INLINE_VISIBILITY
744 unordered_map& operator=(const unordered_map& __u)
746 #if __cplusplus >= 201103L
747 __table_ = __u.__table_;
750 __table_.hash_function() = __u.__table_.hash_function();
751 __table_.key_eq() = __u.__table_.key_eq();
752 __table_.max_load_factor() = __u.__table_.max_load_factor();
753 __table_.__copy_assign_alloc(__u.__table_);
754 insert(__u.begin(), __u.end());
758 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
759 unordered_map& operator=(unordered_map&& __u)
760 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
762 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
763 unordered_map& operator=(initializer_list<value_type> __il);
764 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
766 _LIBCPP_INLINE_VISIBILITY
767 allocator_type get_allocator() const _NOEXCEPT
768 {return allocator_type(__table_.__node_alloc());}
770 _LIBCPP_INLINE_VISIBILITY
771 bool empty() const _NOEXCEPT {return __table_.size() == 0;}
772 _LIBCPP_INLINE_VISIBILITY
773 size_type size() const _NOEXCEPT {return __table_.size();}
774 _LIBCPP_INLINE_VISIBILITY
775 size_type max_size() const _NOEXCEPT {return __table_.max_size();}
777 _LIBCPP_INLINE_VISIBILITY
778 iterator begin() _NOEXCEPT {return __table_.begin();}
779 _LIBCPP_INLINE_VISIBILITY
780 iterator end() _NOEXCEPT {return __table_.end();}
781 _LIBCPP_INLINE_VISIBILITY
782 const_iterator begin() const _NOEXCEPT {return __table_.begin();}
783 _LIBCPP_INLINE_VISIBILITY
784 const_iterator end() const _NOEXCEPT {return __table_.end();}
785 _LIBCPP_INLINE_VISIBILITY
786 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
787 _LIBCPP_INLINE_VISIBILITY
788 const_iterator cend() const _NOEXCEPT {return __table_.end();}
790 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
791 #ifndef _LIBCPP_HAS_NO_VARIADICS
793 template <class... _Args>
794 pair<iterator, bool> emplace(_Args&&... __args);
796 template <class... _Args>
797 _LIBCPP_INLINE_VISIBILITY
798 iterator emplace_hint(const_iterator, _Args&&... __args)
799 {return emplace(_VSTD::forward<_Args>(__args)...).first;}
800 #endif // _LIBCPP_HAS_NO_VARIADICS
801 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
802 _LIBCPP_INLINE_VISIBILITY
803 pair<iterator, bool> insert(const value_type& __x)
804 {return __table_.__insert_unique(__x);}
805 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
807 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
808 _LIBCPP_INLINE_VISIBILITY
809 pair<iterator, bool> insert(_Pp&& __x)
810 {return __table_.__insert_unique(_VSTD::forward<_Pp>(__x));}
811 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
812 _LIBCPP_INLINE_VISIBILITY
813 iterator insert(const_iterator, const value_type& __x)
814 {return insert(__x).first;}
815 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
817 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
818 _LIBCPP_INLINE_VISIBILITY
819 iterator insert(const_iterator, _Pp&& __x)
820 {return insert(_VSTD::forward<_Pp>(__x)).first;}
821 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
822 template <class _InputIterator>
823 void insert(_InputIterator __first, _InputIterator __last);
824 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
825 _LIBCPP_INLINE_VISIBILITY
826 void insert(initializer_list<value_type> __il)
827 {insert(__il.begin(), __il.end());}
828 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
830 _LIBCPP_INLINE_VISIBILITY
831 iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);}
832 _LIBCPP_INLINE_VISIBILITY
833 size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
834 _LIBCPP_INLINE_VISIBILITY
835 iterator erase(const_iterator __first, const_iterator __last)
836 {return __table_.erase(__first.__i_, __last.__i_);}
837 _LIBCPP_INLINE_VISIBILITY
838 void clear() _NOEXCEPT {__table_.clear();}
840 _LIBCPP_INLINE_VISIBILITY
841 void swap(unordered_map& __u)
842 _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
843 {__table_.swap(__u.__table_);}
845 _LIBCPP_INLINE_VISIBILITY
846 hasher hash_function() const
847 {return __table_.hash_function().hash_function();}
848 _LIBCPP_INLINE_VISIBILITY
849 key_equal key_eq() const
850 {return __table_.key_eq().key_eq();}
852 _LIBCPP_INLINE_VISIBILITY
853 iterator find(const key_type& __k) {return __table_.find(__k);}
854 _LIBCPP_INLINE_VISIBILITY
855 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
856 _LIBCPP_INLINE_VISIBILITY
857 size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
858 _LIBCPP_INLINE_VISIBILITY
859 pair<iterator, iterator> equal_range(const key_type& __k)
860 {return __table_.__equal_range_unique(__k);}
861 _LIBCPP_INLINE_VISIBILITY
862 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
863 {return __table_.__equal_range_unique(__k);}
865 mapped_type& operator[](const key_type& __k);
866 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
867 mapped_type& operator[](key_type&& __k);
870 mapped_type& at(const key_type& __k);
871 const mapped_type& at(const key_type& __k) const;
873 _LIBCPP_INLINE_VISIBILITY
874 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
875 _LIBCPP_INLINE_VISIBILITY
876 size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
878 _LIBCPP_INLINE_VISIBILITY
879 size_type bucket_size(size_type __n) const
880 {return __table_.bucket_size(__n);}
881 _LIBCPP_INLINE_VISIBILITY
882 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
884 _LIBCPP_INLINE_VISIBILITY
885 local_iterator begin(size_type __n) {return __table_.begin(__n);}
886 _LIBCPP_INLINE_VISIBILITY
887 local_iterator end(size_type __n) {return __table_.end(__n);}
888 _LIBCPP_INLINE_VISIBILITY
889 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);}
890 _LIBCPP_INLINE_VISIBILITY
891 const_local_iterator end(size_type __n) const {return __table_.cend(__n);}
892 _LIBCPP_INLINE_VISIBILITY
893 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
894 _LIBCPP_INLINE_VISIBILITY
895 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);}
897 _LIBCPP_INLINE_VISIBILITY
898 float load_factor() const _NOEXCEPT {return __table_.load_factor();}
899 _LIBCPP_INLINE_VISIBILITY
900 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
901 _LIBCPP_INLINE_VISIBILITY
902 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
903 _LIBCPP_INLINE_VISIBILITY
904 void rehash(size_type __n) {__table_.rehash(__n);}
905 _LIBCPP_INLINE_VISIBILITY
906 void reserve(size_type __n) {__table_.reserve(__n);}
909 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
910 __node_holder __construct_node();
913 __construct_node(_A0&& __a0);
914 __node_holder __construct_node_with_key(key_type&& __k);
915 #ifndef _LIBCPP_HAS_NO_VARIADICS
916 template <class _A0, class _A1, class ..._Args>
917 __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args);
918 #endif // _LIBCPP_HAS_NO_VARIADICS
919 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
920 __node_holder __construct_node_with_key(const key_type& __k);
923 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
924 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
925 size_type __n, const hasher& __hf, const key_equal& __eql)
926 : __table_(__hf, __eql)
928 __table_.rehash(__n);
931 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
932 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
933 size_type __n, const hasher& __hf, const key_equal& __eql,
934 const allocator_type& __a)
935 : __table_(__hf, __eql, __a)
937 __table_.rehash(__n);
940 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
941 inline _LIBCPP_INLINE_VISIBILITY
942 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
943 const allocator_type& __a)
948 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
949 template <class _InputIterator>
950 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
951 _InputIterator __first, _InputIterator __last)
953 insert(__first, __last);
956 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
957 template <class _InputIterator>
958 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
959 _InputIterator __first, _InputIterator __last, size_type __n,
960 const hasher& __hf, const key_equal& __eql)
961 : __table_(__hf, __eql)
963 __table_.rehash(__n);
964 insert(__first, __last);
967 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
968 template <class _InputIterator>
969 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
970 _InputIterator __first, _InputIterator __last, size_type __n,
971 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
972 : __table_(__hf, __eql, __a)
974 __table_.rehash(__n);
975 insert(__first, __last);
978 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
979 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
980 const unordered_map& __u)
981 : __table_(__u.__table_)
983 __table_.rehash(__u.bucket_count());
984 insert(__u.begin(), __u.end());
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, const allocator_type& __a)
990 : __table_(__u.__table_, __a)
992 __table_.rehash(__u.bucket_count());
993 insert(__u.begin(), __u.end());
996 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
998 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
999 inline _LIBCPP_INLINE_VISIBILITY
1000 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1001 unordered_map&& __u)
1002 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
1003 : __table_(_VSTD::move(__u.__table_))
1007 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1008 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1009 unordered_map&& __u, const allocator_type& __a)
1010 : __table_(_VSTD::move(__u.__table_), __a)
1012 if (__a != __u.get_allocator())
1014 iterator __i = __u.begin();
1015 while (__u.size() != 0)
1016 __table_.__insert_unique(
1017 _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_)
1022 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1024 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1026 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1027 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1028 initializer_list<value_type> __il)
1030 insert(__il.begin(), __il.end());
1033 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1034 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1035 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1036 const key_equal& __eql)
1037 : __table_(__hf, __eql)
1039 __table_.rehash(__n);
1040 insert(__il.begin(), __il.end());
1043 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1044 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1045 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1046 const key_equal& __eql, const allocator_type& __a)
1047 : __table_(__hf, __eql, __a)
1049 __table_.rehash(__n);
1050 insert(__il.begin(), __il.end());
1053 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1055 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1057 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1058 inline _LIBCPP_INLINE_VISIBILITY
1059 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
1060 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_map&& __u)
1061 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
1063 __table_ = _VSTD::move(__u.__table_);
1067 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1069 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1071 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1072 inline _LIBCPP_INLINE_VISIBILITY
1073 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
1074 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(
1075 initializer_list<value_type> __il)
1077 __table_.__assign_unique(__il.begin(), __il.end());
1081 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1083 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1085 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1086 typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1087 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node()
1089 __node_allocator& __na = __table_.__node_alloc();
1090 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1091 __node_traits::construct(__na, _VSTD::addressof(__h->__value_));
1092 __h.get_deleter().__first_constructed = true;
1093 __h.get_deleter().__second_constructed = true;
1097 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1098 template <class _A0>
1099 typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1100 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
1102 __node_allocator& __na = __table_.__node_alloc();
1103 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1104 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1105 _VSTD::forward<_A0>(__a0));
1106 __h.get_deleter().__first_constructed = true;
1107 __h.get_deleter().__second_constructed = true;
1111 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1112 typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1113 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(key_type&& __k)
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_.__cc.first), _VSTD::move(__k));
1118 __h.get_deleter().__first_constructed = true;
1119 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
1120 __h.get_deleter().__second_constructed = true;
1121 return _VSTD::move(__h);
1124 #ifndef _LIBCPP_HAS_NO_VARIADICS
1126 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1127 template <class _A0, class _A1, class ..._Args>
1128 typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1129 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_),
1136 _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1),
1137 _VSTD::forward<_Args>(__args)...);
1138 __h.get_deleter().__first_constructed = true;
1139 __h.get_deleter().__second_constructed = true;
1143 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1144 template <class... _Args>
1145 pair<typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator, bool>
1146 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_Args&&... __args)
1148 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1149 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1155 #endif // _LIBCPP_HAS_NO_VARIADICS
1156 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1158 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1159 typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1160 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(const key_type& __k)
1162 __node_allocator& __na = __table_.__node_alloc();
1163 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1164 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), __k);
1165 __h.get_deleter().__first_constructed = true;
1166 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
1167 __h.get_deleter().__second_constructed = true;
1168 return _VSTD::move(__h);
1171 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1172 template <class _InputIterator>
1173 inline _LIBCPP_INLINE_VISIBILITY
1175 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
1176 _InputIterator __last)
1178 for (; __first != __last; ++__first)
1179 __table_.__insert_unique(*__first);
1182 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1184 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k)
1186 iterator __i = find(__k);
1189 __node_holder __h = __construct_node_with_key(__k);
1190 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1192 return __r.first->second;
1195 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1197 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1199 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&& __k)
1201 iterator __i = find(__k);
1204 __node_holder __h = __construct_node_with_key(_VSTD::move(__k));
1205 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1207 return __r.first->second;
1210 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1212 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1214 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k)
1216 iterator __i = find(__k);
1217 #ifndef _LIBCPP_NO_EXCEPTIONS
1219 throw out_of_range("unordered_map::at: key not found");
1220 #endif // _LIBCPP_NO_EXCEPTIONS
1224 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1226 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) const
1228 const_iterator __i = find(__k);
1229 #ifndef _LIBCPP_NO_EXCEPTIONS
1231 throw out_of_range("unordered_map::at: key not found");
1232 #endif // _LIBCPP_NO_EXCEPTIONS
1236 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1237 inline _LIBCPP_INLINE_VISIBILITY
1239 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1240 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1241 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1246 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1248 operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1249 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1251 if (__x.size() != __y.size())
1253 typedef typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
1255 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();
1258 const_iterator __j = __y.find(__i->first);
1259 if (__j == __ey || !(*__i == *__j))
1265 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1266 inline _LIBCPP_INLINE_VISIBILITY
1268 operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1269 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1271 return !(__x == __y);
1274 template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
1275 class _Alloc = allocator<pair<const _Key, _Tp> > >
1276 class _LIBCPP_TYPE_VIS unordered_multimap
1280 typedef _Key key_type;
1281 typedef _Tp mapped_type;
1282 typedef _Hash hasher;
1283 typedef _Pred key_equal;
1284 typedef _Alloc allocator_type;
1285 typedef pair<const key_type, mapped_type> value_type;
1286 typedef pair<key_type, mapped_type> __nc_value_type;
1287 typedef value_type& reference;
1288 typedef const value_type& const_reference;
1291 #if __cplusplus >= 201103L
1294 typedef typename unordered_multimap::value_type value_type;
1295 typedef typename unordered_multimap::__nc_value_type __nc_value_type;
1297 __nc_value_type __nc;
1299 template <class ..._Args>
1300 __value_type(_Args&& ...__args)
1301 : __cc(std::forward<_Args>(__args)...) {}
1303 __value_type(const __value_type& __v)
1304 : __cc(std::move(__v.__cc)) {}
1306 __value_type(__value_type&& __v)
1307 : __nc(std::move(__v.__nc)) {}
1309 __value_type& operator=(const __value_type& __v)
1310 {__nc = __v.__cc; return *this;}
1312 __value_type& operator=(__value_type&& __v)
1313 {__nc = std::move(__v.__nc); return *this;}
1315 ~__value_type() {__cc.~value_type();}
1320 typedef typename unordered_multimap::value_type value_type;
1325 template <class _A0>
1326 __value_type(const _A0& __a0)
1329 template <class _A0, class _A1>
1330 __value_type(const _A0& __a0, const _A1& __a1)
1331 : __cc(__a0, __a1) {}
1334 typedef __unordered_map_hasher<key_type, __value_type, hasher> __hasher;
1335 typedef __unordered_map_equal<key_type, __value_type, key_equal> __key_equal;
1336 typedef typename allocator_traits<allocator_type>::template
1337 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
1338 rebind_alloc<__value_type>
1340 rebind_alloc<__value_type>::other
1344 typedef __hash_table<__value_type, __hasher,
1345 __key_equal, __allocator_type> __table;
1349 typedef typename __table::__node_traits __node_traits;
1350 typedef typename __table::__node_allocator __node_allocator;
1351 typedef typename __table::__node __node;
1352 typedef __hash_map_node_destructor<__node_allocator> _Dp;
1353 typedef unique_ptr<__node, _Dp> __node_holder;
1354 typedef allocator_traits<allocator_type> __alloc_traits;
1356 typedef typename __alloc_traits::pointer pointer;
1357 typedef typename __alloc_traits::const_pointer const_pointer;
1358 typedef typename __alloc_traits::size_type size_type;
1359 typedef typename __alloc_traits::difference_type difference_type;
1361 typedef __hash_map_iterator<typename __table::iterator> iterator;
1362 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
1363 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
1364 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
1366 _LIBCPP_INLINE_VISIBILITY
1367 unordered_multimap()
1368 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
1370 explicit unordered_multimap(size_type __n, const hasher& __hf = hasher(),
1371 const key_equal& __eql = key_equal());
1372 unordered_multimap(size_type __n, const hasher& __hf,
1373 const key_equal& __eql,
1374 const allocator_type& __a);
1375 template <class _InputIterator>
1376 unordered_multimap(_InputIterator __first, _InputIterator __last);
1377 template <class _InputIterator>
1378 unordered_multimap(_InputIterator __first, _InputIterator __last,
1379 size_type __n, const hasher& __hf = hasher(),
1380 const key_equal& __eql = key_equal());
1381 template <class _InputIterator>
1382 unordered_multimap(_InputIterator __first, _InputIterator __last,
1383 size_type __n, const hasher& __hf,
1384 const key_equal& __eql,
1385 const allocator_type& __a);
1386 explicit unordered_multimap(const allocator_type& __a);
1387 unordered_multimap(const unordered_multimap& __u);
1388 unordered_multimap(const unordered_multimap& __u, const allocator_type& __a);
1389 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1390 unordered_multimap(unordered_multimap&& __u)
1391 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
1392 unordered_multimap(unordered_multimap&& __u, const allocator_type& __a);
1393 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1394 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1395 unordered_multimap(initializer_list<value_type> __il);
1396 unordered_multimap(initializer_list<value_type> __il, size_type __n,
1397 const hasher& __hf = hasher(),
1398 const key_equal& __eql = key_equal());
1399 unordered_multimap(initializer_list<value_type> __il, size_type __n,
1400 const hasher& __hf, const key_equal& __eql,
1401 const allocator_type& __a);
1402 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1403 // ~unordered_multimap() = default;
1404 _LIBCPP_INLINE_VISIBILITY
1405 unordered_multimap& operator=(const unordered_multimap& __u)
1407 #if __cplusplus >= 201103L
1408 __table_ = __u.__table_;
1411 __table_.hash_function() = __u.__table_.hash_function();
1412 __table_.key_eq() = __u.__table_.key_eq();
1413 __table_.max_load_factor() = __u.__table_.max_load_factor();
1414 __table_.__copy_assign_alloc(__u.__table_);
1415 insert(__u.begin(), __u.end());
1419 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1420 unordered_multimap& operator=(unordered_multimap&& __u)
1421 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
1423 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1424 unordered_multimap& operator=(initializer_list<value_type> __il);
1425 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1427 _LIBCPP_INLINE_VISIBILITY
1428 allocator_type get_allocator() const _NOEXCEPT
1429 {return allocator_type(__table_.__node_alloc());}
1431 _LIBCPP_INLINE_VISIBILITY
1432 bool empty() const _NOEXCEPT {return __table_.size() == 0;}
1433 _LIBCPP_INLINE_VISIBILITY
1434 size_type size() const _NOEXCEPT {return __table_.size();}
1435 _LIBCPP_INLINE_VISIBILITY
1436 size_type max_size() const _NOEXCEPT {return __table_.max_size();}
1438 _LIBCPP_INLINE_VISIBILITY
1439 iterator begin() _NOEXCEPT {return __table_.begin();}
1440 _LIBCPP_INLINE_VISIBILITY
1441 iterator end() _NOEXCEPT {return __table_.end();}
1442 _LIBCPP_INLINE_VISIBILITY
1443 const_iterator begin() const _NOEXCEPT {return __table_.begin();}
1444 _LIBCPP_INLINE_VISIBILITY
1445 const_iterator end() const _NOEXCEPT {return __table_.end();}
1446 _LIBCPP_INLINE_VISIBILITY
1447 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
1448 _LIBCPP_INLINE_VISIBILITY
1449 const_iterator cend() const _NOEXCEPT {return __table_.end();}
1451 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1452 #ifndef _LIBCPP_HAS_NO_VARIADICS
1454 template <class... _Args>
1455 iterator emplace(_Args&&... __args);
1457 template <class... _Args>
1458 iterator emplace_hint(const_iterator __p, _Args&&... __args);
1459 #endif // _LIBCPP_HAS_NO_VARIADICS
1460 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1461 _LIBCPP_INLINE_VISIBILITY
1462 iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
1463 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1464 template <class _Pp,
1465 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1466 _LIBCPP_INLINE_VISIBILITY
1467 iterator insert(_Pp&& __x)
1468 {return __table_.__insert_multi(_VSTD::forward<_Pp>(__x));}
1469 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1470 _LIBCPP_INLINE_VISIBILITY
1471 iterator insert(const_iterator __p, const value_type& __x)
1472 {return __table_.__insert_multi(__p.__i_, __x);}
1473 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1474 template <class _Pp,
1475 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1476 _LIBCPP_INLINE_VISIBILITY
1477 iterator insert(const_iterator __p, _Pp&& __x)
1478 {return __table_.__insert_multi(__p.__i_, _VSTD::forward<_Pp>(__x));}
1479 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1480 template <class _InputIterator>
1481 void insert(_InputIterator __first, _InputIterator __last);
1482 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1483 _LIBCPP_INLINE_VISIBILITY
1484 void insert(initializer_list<value_type> __il)
1485 {insert(__il.begin(), __il.end());}
1486 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1488 _LIBCPP_INLINE_VISIBILITY
1489 iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);}
1490 _LIBCPP_INLINE_VISIBILITY
1491 size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
1492 _LIBCPP_INLINE_VISIBILITY
1493 iterator erase(const_iterator __first, const_iterator __last)
1494 {return __table_.erase(__first.__i_, __last.__i_);}
1495 _LIBCPP_INLINE_VISIBILITY
1496 void clear() _NOEXCEPT {__table_.clear();}
1498 _LIBCPP_INLINE_VISIBILITY
1499 void swap(unordered_multimap& __u)
1500 _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
1501 {__table_.swap(__u.__table_);}
1503 _LIBCPP_INLINE_VISIBILITY
1504 hasher hash_function() const
1505 {return __table_.hash_function().hash_function();}
1506 _LIBCPP_INLINE_VISIBILITY
1507 key_equal key_eq() const
1508 {return __table_.key_eq().key_eq();}
1510 _LIBCPP_INLINE_VISIBILITY
1511 iterator find(const key_type& __k) {return __table_.find(__k);}
1512 _LIBCPP_INLINE_VISIBILITY
1513 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
1514 _LIBCPP_INLINE_VISIBILITY
1515 size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
1516 _LIBCPP_INLINE_VISIBILITY
1517 pair<iterator, iterator> equal_range(const key_type& __k)
1518 {return __table_.__equal_range_multi(__k);}
1519 _LIBCPP_INLINE_VISIBILITY
1520 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
1521 {return __table_.__equal_range_multi(__k);}
1523 _LIBCPP_INLINE_VISIBILITY
1524 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
1525 _LIBCPP_INLINE_VISIBILITY
1526 size_type max_bucket_count() const _NOEXCEPT
1527 {return __table_.max_bucket_count();}
1529 _LIBCPP_INLINE_VISIBILITY
1530 size_type bucket_size(size_type __n) const
1531 {return __table_.bucket_size(__n);}
1532 _LIBCPP_INLINE_VISIBILITY
1533 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
1535 _LIBCPP_INLINE_VISIBILITY
1536 local_iterator begin(size_type __n) {return __table_.begin(__n);}
1537 _LIBCPP_INLINE_VISIBILITY
1538 local_iterator end(size_type __n) {return __table_.end(__n);}
1539 _LIBCPP_INLINE_VISIBILITY
1540 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);}
1541 _LIBCPP_INLINE_VISIBILITY
1542 const_local_iterator end(size_type __n) const {return __table_.cend(__n);}
1543 _LIBCPP_INLINE_VISIBILITY
1544 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
1545 _LIBCPP_INLINE_VISIBILITY
1546 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);}
1548 _LIBCPP_INLINE_VISIBILITY
1549 float load_factor() const _NOEXCEPT {return __table_.load_factor();}
1550 _LIBCPP_INLINE_VISIBILITY
1551 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
1552 _LIBCPP_INLINE_VISIBILITY
1553 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
1554 _LIBCPP_INLINE_VISIBILITY
1555 void rehash(size_type __n) {__table_.rehash(__n);}
1556 _LIBCPP_INLINE_VISIBILITY
1557 void reserve(size_type __n) {__table_.reserve(__n);}
1560 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1561 __node_holder __construct_node();
1562 template <class _A0>
1564 __construct_node(_A0&& __a0);
1565 #ifndef _LIBCPP_HAS_NO_VARIADICS
1566 template <class _A0, class _A1, class ..._Args>
1567 __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args);
1568 #endif // _LIBCPP_HAS_NO_VARIADICS
1569 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1572 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1573 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1574 size_type __n, const hasher& __hf, const key_equal& __eql)
1575 : __table_(__hf, __eql)
1577 __table_.rehash(__n);
1580 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1581 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1582 size_type __n, const hasher& __hf, const key_equal& __eql,
1583 const allocator_type& __a)
1584 : __table_(__hf, __eql, __a)
1586 __table_.rehash(__n);
1589 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1590 template <class _InputIterator>
1591 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1592 _InputIterator __first, _InputIterator __last)
1594 insert(__first, __last);
1597 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1598 template <class _InputIterator>
1599 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1600 _InputIterator __first, _InputIterator __last, size_type __n,
1601 const hasher& __hf, const key_equal& __eql)
1602 : __table_(__hf, __eql)
1604 __table_.rehash(__n);
1605 insert(__first, __last);
1608 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1609 template <class _InputIterator>
1610 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1611 _InputIterator __first, _InputIterator __last, size_type __n,
1612 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1613 : __table_(__hf, __eql, __a)
1615 __table_.rehash(__n);
1616 insert(__first, __last);
1619 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1620 inline _LIBCPP_INLINE_VISIBILITY
1621 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1622 const allocator_type& __a)
1627 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1628 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1629 const unordered_multimap& __u)
1630 : __table_(__u.__table_)
1632 __table_.rehash(__u.bucket_count());
1633 insert(__u.begin(), __u.end());
1636 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1637 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1638 const unordered_multimap& __u, const allocator_type& __a)
1639 : __table_(__u.__table_, __a)
1641 __table_.rehash(__u.bucket_count());
1642 insert(__u.begin(), __u.end());
1645 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1647 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1648 inline _LIBCPP_INLINE_VISIBILITY
1649 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1650 unordered_multimap&& __u)
1651 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
1652 : __table_(_VSTD::move(__u.__table_))
1656 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1657 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1658 unordered_multimap&& __u, const allocator_type& __a)
1659 : __table_(_VSTD::move(__u.__table_), __a)
1661 if (__a != __u.get_allocator())
1663 iterator __i = __u.begin();
1664 while (__u.size() != 0)
1666 __table_.__insert_multi(
1667 _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_)
1673 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1675 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1677 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1678 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1679 initializer_list<value_type> __il)
1681 insert(__il.begin(), __il.end());
1684 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1685 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1686 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1687 const key_equal& __eql)
1688 : __table_(__hf, __eql)
1690 __table_.rehash(__n);
1691 insert(__il.begin(), __il.end());
1694 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1695 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1696 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1697 const key_equal& __eql, const allocator_type& __a)
1698 : __table_(__hf, __eql, __a)
1700 __table_.rehash(__n);
1701 insert(__il.begin(), __il.end());
1704 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1706 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1708 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1709 inline _LIBCPP_INLINE_VISIBILITY
1710 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
1711 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_multimap&& __u)
1712 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
1714 __table_ = _VSTD::move(__u.__table_);
1718 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1720 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1722 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1723 inline _LIBCPP_INLINE_VISIBILITY
1724 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
1725 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(
1726 initializer_list<value_type> __il)
1728 __table_.__assign_multi(__il.begin(), __il.end());
1732 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1734 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1736 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1737 typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1738 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node()
1740 __node_allocator& __na = __table_.__node_alloc();
1741 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1742 __node_traits::construct(__na, _VSTD::addressof(__h->__value_));
1743 __h.get_deleter().__first_constructed = true;
1744 __h.get_deleter().__second_constructed = true;
1748 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1749 template <class _A0>
1750 typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1751 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
1753 __node_allocator& __na = __table_.__node_alloc();
1754 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1755 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1756 _VSTD::forward<_A0>(__a0));
1757 __h.get_deleter().__first_constructed = true;
1758 __h.get_deleter().__second_constructed = true;
1762 #ifndef _LIBCPP_HAS_NO_VARIADICS
1764 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1765 template <class _A0, class _A1, class ..._Args>
1766 typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1767 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(
1768 _A0&& __a0, _A1&& __a1, _Args&&... __args)
1770 __node_allocator& __na = __table_.__node_alloc();
1771 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1772 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1773 _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1),
1774 _VSTD::forward<_Args>(__args)...);
1775 __h.get_deleter().__first_constructed = true;
1776 __h.get_deleter().__second_constructed = true;
1780 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1781 template <class... _Args>
1782 typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator
1783 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_Args&&... __args)
1785 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1786 iterator __r = __table_.__node_insert_multi(__h.get());
1791 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1792 template <class... _Args>
1793 typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator
1794 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace_hint(
1795 const_iterator __p, _Args&&... __args)
1797 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1798 iterator __r = __table_.__node_insert_multi(__p.__i_, __h.get());
1803 #endif // _LIBCPP_HAS_NO_VARIADICS
1804 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1806 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1807 template <class _InputIterator>
1808 inline _LIBCPP_INLINE_VISIBILITY
1810 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
1811 _InputIterator __last)
1813 for (; __first != __last; ++__first)
1814 __table_.__insert_multi(*__first);
1817 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1818 inline _LIBCPP_INLINE_VISIBILITY
1820 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1821 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1822 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1827 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1829 operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1830 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1832 if (__x.size() != __y.size())
1834 typedef typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
1836 typedef pair<const_iterator, const_iterator> _EqRng;
1837 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;)
1839 _EqRng __xeq = __x.equal_range(__i->first);
1840 _EqRng __yeq = __y.equal_range(__i->first);
1841 if (_VSTD::distance(__xeq.first, __xeq.second) !=
1842 _VSTD::distance(__yeq.first, __yeq.second) ||
1843 !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first))
1850 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1851 inline _LIBCPP_INLINE_VISIBILITY
1853 operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1854 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1856 return !(__x == __y);
1859 _LIBCPP_END_NAMESPACE_STD
1861 #endif // _LIBCPP_UNORDERED_MAP