2 //===----------------------------------------------------------------------===//
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__HASH_TABLE
12 #define _LIBCPP__HASH_TABLE
15 #include <initializer_list>
21 #include <type_traits>
25 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
26 #pragma GCC system_header
30 #include <__undef_macros>
33 _LIBCPP_BEGIN_NAMESPACE_STD
35 #ifndef _LIBCPP_CXX03_LANG
36 template <class _Key, class _Tp>
37 union __hash_value_type;
39 template <class _Key, class _Tp>
40 struct __hash_value_type;
43 template <class _Key, class _Cp, class _Hash,
44 bool = is_empty<_Hash>::value && !__libcpp_is_final<_Hash>::value>
45 class __unordered_map_hasher;
47 template <class _Key, class _Cp, class _Pred,
48 bool = is_empty<_Pred>::value && !__libcpp_is_final<_Pred>::value
50 class __unordered_map_equal;
52 #ifndef _LIBCPP_CXX03_LANG
54 struct __is_hash_value_type_imp : false_type {};
56 template <class _Key, class _Value>
57 struct __is_hash_value_type_imp<__hash_value_type<_Key, _Value>> : true_type {};
59 template <class ..._Args>
60 struct __is_hash_value_type : false_type {};
63 struct __is_hash_value_type<_One> : __is_hash_value_type_imp<typename __uncvref<_One>::type> {};
67 size_t __next_prime(size_t __n);
69 template <class _NodePtr>
70 struct __hash_node_base
72 typedef typename pointer_traits<_NodePtr>::element_type __node_type;
73 typedef __hash_node_base __first_node;
74 typedef typename __rebind_pointer<_NodePtr, __first_node>::type __node_base_pointer;
75 typedef _NodePtr __node_pointer;
77 #if defined(_LIBCPP_ABI_FIX_UNORDERED_NODE_POINTER_UB)
78 typedef __node_base_pointer __next_pointer;
80 typedef typename conditional<
81 is_pointer<__node_pointer>::value,
83 __node_pointer>::type __next_pointer;
86 __next_pointer __next_;
88 _LIBCPP_INLINE_VISIBILITY
89 __next_pointer __ptr() _NOEXCEPT {
90 return static_cast<__next_pointer>(
91 pointer_traits<__node_base_pointer>::pointer_to(*this));
94 _LIBCPP_INLINE_VISIBILITY
95 __node_pointer __upcast() _NOEXCEPT {
96 return static_cast<__node_pointer>(
97 pointer_traits<__node_base_pointer>::pointer_to(*this));
100 _LIBCPP_INLINE_VISIBILITY
101 size_t __hash() const _NOEXCEPT {
102 return static_cast<__node_type const&>(*this).__hash_;
105 _LIBCPP_INLINE_VISIBILITY __hash_node_base() _NOEXCEPT : __next_(nullptr) {}
108 template <class _Tp, class _VoidPtr>
110 : public __hash_node_base
112 typename __rebind_pointer<_VoidPtr, __hash_node<_Tp, _VoidPtr> >::type
115 typedef _Tp __node_value_type;
118 __node_value_type __value_;
121 inline _LIBCPP_INLINE_VISIBILITY
123 __is_hash_power2(size_t __bc)
125 return __bc > 2 && !(__bc & (__bc - 1));
128 inline _LIBCPP_INLINE_VISIBILITY
130 __constrain_hash(size_t __h, size_t __bc)
132 return !(__bc & (__bc - 1)) ? __h & (__bc - 1) :
133 (__h < __bc ? __h : __h % __bc);
136 inline _LIBCPP_INLINE_VISIBILITY
138 __next_hash_pow2(size_t __n)
140 return __n < 2 ? __n : (size_t(1) << (std::numeric_limits<size_t>::digits - __clz(__n-1)));
144 template <class _Tp, class _Hash, class _Equal, class _Alloc> class __hash_table;
146 template <class _NodePtr> class _LIBCPP_TEMPLATE_VIS __hash_iterator;
147 template <class _ConstNodePtr> class _LIBCPP_TEMPLATE_VIS __hash_const_iterator;
148 template <class _NodePtr> class _LIBCPP_TEMPLATE_VIS __hash_local_iterator;
149 template <class _ConstNodePtr> class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator;
150 template <class _HashIterator> class _LIBCPP_TEMPLATE_VIS __hash_map_iterator;
151 template <class _HashIterator> class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator;
154 struct __hash_key_value_types {
155 static_assert(!is_reference<_Tp>::value && !is_const<_Tp>::value, "");
156 typedef _Tp key_type;
157 typedef _Tp __node_value_type;
158 typedef _Tp __container_value_type;
159 static const bool __is_map = false;
161 _LIBCPP_INLINE_VISIBILITY
162 static key_type const& __get_key(_Tp const& __v) {
165 _LIBCPP_INLINE_VISIBILITY
166 static __container_value_type const& __get_value(__node_value_type const& __v) {
169 _LIBCPP_INLINE_VISIBILITY
170 static __container_value_type* __get_ptr(__node_value_type& __n) {
171 return _VSTD::addressof(__n);
173 #ifndef _LIBCPP_CXX03_LANG
174 _LIBCPP_INLINE_VISIBILITY
175 static __container_value_type&& __move(__node_value_type& __v) {
176 return _VSTD::move(__v);
181 template <class _Key, class _Tp>
182 struct __hash_key_value_types<__hash_value_type<_Key, _Tp> > {
183 typedef _Key key_type;
184 typedef _Tp mapped_type;
185 typedef __hash_value_type<_Key, _Tp> __node_value_type;
186 typedef pair<const _Key, _Tp> __container_value_type;
187 typedef pair<_Key, _Tp> __nc_value_type;
188 typedef __container_value_type __map_value_type;
189 static const bool __is_map = true;
191 _LIBCPP_INLINE_VISIBILITY
192 static key_type const& __get_key(__container_value_type const& __v) {
197 _LIBCPP_INLINE_VISIBILITY
198 static typename enable_if<__is_same_uncvref<_Up, __node_value_type>::value,
199 __container_value_type const&>::type
200 __get_value(_Up& __t) {
205 _LIBCPP_INLINE_VISIBILITY
206 static typename enable_if<__is_same_uncvref<_Up, __container_value_type>::value,
207 __container_value_type const&>::type
208 __get_value(_Up& __t) {
212 _LIBCPP_INLINE_VISIBILITY
213 static __container_value_type* __get_ptr(__node_value_type& __n) {
214 return _VSTD::addressof(__n.__cc);
216 #ifndef _LIBCPP_CXX03_LANG
217 _LIBCPP_INLINE_VISIBILITY
218 static __nc_value_type&& __move(__node_value_type& __v) {
219 return _VSTD::move(__v.__nc);
225 template <class _Tp, class _AllocPtr, class _KVTypes = __hash_key_value_types<_Tp>,
226 bool = _KVTypes::__is_map>
227 struct __hash_map_pointer_types {};
229 template <class _Tp, class _AllocPtr, class _KVTypes>
230 struct __hash_map_pointer_types<_Tp, _AllocPtr, _KVTypes, true> {
231 typedef typename _KVTypes::__map_value_type _Mv;
232 typedef typename __rebind_pointer<_AllocPtr, _Mv>::type
233 __map_value_type_pointer;
234 typedef typename __rebind_pointer<_AllocPtr, const _Mv>::type
235 __const_map_value_type_pointer;
238 template <class _NodePtr, class _NodeT = typename pointer_traits<_NodePtr>::element_type>
239 struct __hash_node_types;
241 template <class _NodePtr, class _Tp, class _VoidPtr>
242 struct __hash_node_types<_NodePtr, __hash_node<_Tp, _VoidPtr> >
243 : public __hash_key_value_types<_Tp>, __hash_map_pointer_types<_Tp, _VoidPtr>
246 typedef __hash_key_value_types<_Tp> __base;
249 typedef ptrdiff_t difference_type;
250 typedef size_t size_type;
252 typedef typename __rebind_pointer<_NodePtr, void>::type __void_pointer;
254 typedef typename pointer_traits<_NodePtr>::element_type __node_type;
255 typedef _NodePtr __node_pointer;
257 typedef __hash_node_base<__node_pointer> __node_base_type;
258 typedef typename __rebind_pointer<_NodePtr, __node_base_type>::type
261 typedef typename __node_base_type::__next_pointer __next_pointer;
263 typedef _Tp __node_value_type;
264 typedef typename __rebind_pointer<_VoidPtr, __node_value_type>::type
265 __node_value_type_pointer;
266 typedef typename __rebind_pointer<_VoidPtr, const __node_value_type>::type
267 __const_node_value_type_pointer;
270 static_assert(!is_const<__node_type>::value,
271 "_NodePtr should never be a pointer to const");
272 static_assert((is_same<typename pointer_traits<_VoidPtr>::element_type, void>::value),
273 "_VoidPtr does not point to unqualified void type");
274 static_assert((is_same<typename __rebind_pointer<_VoidPtr, __node_type>::type,
275 _NodePtr>::value), "_VoidPtr does not rebind to _NodePtr.");
278 template <class _HashIterator>
279 struct __hash_node_types_from_iterator;
280 template <class _NodePtr>
281 struct __hash_node_types_from_iterator<__hash_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {};
282 template <class _NodePtr>
283 struct __hash_node_types_from_iterator<__hash_const_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {};
284 template <class _NodePtr>
285 struct __hash_node_types_from_iterator<__hash_local_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {};
286 template <class _NodePtr>
287 struct __hash_node_types_from_iterator<__hash_const_local_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {};
290 template <class _NodeValueTp, class _VoidPtr>
291 struct __make_hash_node_types {
292 typedef __hash_node<_NodeValueTp, _VoidPtr> _NodeTp;
293 typedef typename __rebind_pointer<_VoidPtr, _NodeTp>::type _NodePtr;
294 typedef __hash_node_types<_NodePtr> type;
297 template <class _NodePtr>
298 class _LIBCPP_TEMPLATE_VIS __hash_iterator
300 typedef __hash_node_types<_NodePtr> _NodeTypes;
301 typedef _NodePtr __node_pointer;
302 typedef typename _NodeTypes::__next_pointer __next_pointer;
304 __next_pointer __node_;
307 typedef forward_iterator_tag iterator_category;
308 typedef typename _NodeTypes::__node_value_type value_type;
309 typedef typename _NodeTypes::difference_type difference_type;
310 typedef value_type& reference;
311 typedef typename _NodeTypes::__node_value_type_pointer pointer;
313 _LIBCPP_INLINE_VISIBILITY __hash_iterator() _NOEXCEPT : __node_(nullptr) {
314 _LIBCPP_DEBUG_MODE(__get_db()->__insert_i(this));
317 #if _LIBCPP_DEBUG_LEVEL >= 2
318 _LIBCPP_INLINE_VISIBILITY
319 __hash_iterator(const __hash_iterator& __i)
320 : __node_(__i.__node_)
322 __get_db()->__iterator_copy(this, &__i);
325 _LIBCPP_INLINE_VISIBILITY
328 __get_db()->__erase_i(this);
331 _LIBCPP_INLINE_VISIBILITY
332 __hash_iterator& operator=(const __hash_iterator& __i)
336 __get_db()->__iterator_copy(this, &__i);
337 __node_ = __i.__node_;
341 #endif // _LIBCPP_DEBUG_LEVEL >= 2
343 _LIBCPP_INLINE_VISIBILITY
344 reference operator*() const {
345 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
346 "Attempted to dereference a non-dereferenceable unordered container iterator");
347 return __node_->__upcast()->__value_;
350 _LIBCPP_INLINE_VISIBILITY
351 pointer operator->() const {
352 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
353 "Attempted to dereference a non-dereferenceable unordered container iterator");
354 return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__value_);
357 _LIBCPP_INLINE_VISIBILITY
358 __hash_iterator& operator++() {
359 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
360 "Attempted to increment non-incrementable unordered container iterator");
361 __node_ = __node_->__next_;
365 _LIBCPP_INLINE_VISIBILITY
366 __hash_iterator operator++(int)
368 __hash_iterator __t(*this);
373 friend _LIBCPP_INLINE_VISIBILITY
374 bool operator==(const __hash_iterator& __x, const __hash_iterator& __y)
376 return __x.__node_ == __y.__node_;
378 friend _LIBCPP_INLINE_VISIBILITY
379 bool operator!=(const __hash_iterator& __x, const __hash_iterator& __y)
380 {return !(__x == __y);}
383 #if _LIBCPP_DEBUG_LEVEL >= 2
384 _LIBCPP_INLINE_VISIBILITY
385 __hash_iterator(__next_pointer __node, const void* __c) _NOEXCEPT
388 __get_db()->__insert_ic(this, __c);
391 _LIBCPP_INLINE_VISIBILITY
392 __hash_iterator(__next_pointer __node) _NOEXCEPT
396 template <class, class, class, class> friend class __hash_table;
397 template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator;
398 template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_map_iterator;
399 template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_map;
400 template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
403 template <class _NodePtr>
404 class _LIBCPP_TEMPLATE_VIS __hash_const_iterator
406 static_assert(!is_const<typename pointer_traits<_NodePtr>::element_type>::value, "");
407 typedef __hash_node_types<_NodePtr> _NodeTypes;
408 typedef _NodePtr __node_pointer;
409 typedef typename _NodeTypes::__next_pointer __next_pointer;
411 __next_pointer __node_;
414 typedef __hash_iterator<_NodePtr> __non_const_iterator;
416 typedef forward_iterator_tag iterator_category;
417 typedef typename _NodeTypes::__node_value_type value_type;
418 typedef typename _NodeTypes::difference_type difference_type;
419 typedef const value_type& reference;
420 typedef typename _NodeTypes::__const_node_value_type_pointer pointer;
423 _LIBCPP_INLINE_VISIBILITY __hash_const_iterator() _NOEXCEPT : __node_(nullptr) {
424 _LIBCPP_DEBUG_MODE(__get_db()->__insert_i(this));
427 _LIBCPP_INLINE_VISIBILITY
428 __hash_const_iterator(const __non_const_iterator& __x) _NOEXCEPT
429 : __node_(__x.__node_)
431 _LIBCPP_DEBUG_MODE(__get_db()->__iterator_copy(this, &__x));
434 #if _LIBCPP_DEBUG_LEVEL >= 2
435 _LIBCPP_INLINE_VISIBILITY
436 __hash_const_iterator(const __hash_const_iterator& __i)
437 : __node_(__i.__node_)
439 __get_db()->__iterator_copy(this, &__i);
442 _LIBCPP_INLINE_VISIBILITY
443 ~__hash_const_iterator()
445 __get_db()->__erase_i(this);
448 _LIBCPP_INLINE_VISIBILITY
449 __hash_const_iterator& operator=(const __hash_const_iterator& __i)
453 __get_db()->__iterator_copy(this, &__i);
454 __node_ = __i.__node_;
458 #endif // _LIBCPP_DEBUG_LEVEL >= 2
460 _LIBCPP_INLINE_VISIBILITY
461 reference operator*() const {
462 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
463 "Attempted to dereference a non-dereferenceable unordered container const_iterator");
464 return __node_->__upcast()->__value_;
466 _LIBCPP_INLINE_VISIBILITY
467 pointer operator->() const {
468 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
469 "Attempted to dereference a non-dereferenceable unordered container const_iterator");
470 return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__value_);
473 _LIBCPP_INLINE_VISIBILITY
474 __hash_const_iterator& operator++() {
475 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
476 "Attempted to increment non-incrementable unordered container const_iterator");
477 __node_ = __node_->__next_;
481 _LIBCPP_INLINE_VISIBILITY
482 __hash_const_iterator operator++(int)
484 __hash_const_iterator __t(*this);
489 friend _LIBCPP_INLINE_VISIBILITY
490 bool operator==(const __hash_const_iterator& __x, const __hash_const_iterator& __y)
492 return __x.__node_ == __y.__node_;
494 friend _LIBCPP_INLINE_VISIBILITY
495 bool operator!=(const __hash_const_iterator& __x, const __hash_const_iterator& __y)
496 {return !(__x == __y);}
499 #if _LIBCPP_DEBUG_LEVEL >= 2
500 _LIBCPP_INLINE_VISIBILITY
501 __hash_const_iterator(__next_pointer __node, const void* __c) _NOEXCEPT
504 __get_db()->__insert_ic(this, __c);
507 _LIBCPP_INLINE_VISIBILITY
508 __hash_const_iterator(__next_pointer __node) _NOEXCEPT
512 template <class, class, class, class> friend class __hash_table;
513 template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator;
514 template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_map;
515 template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
518 template <class _NodePtr>
519 class _LIBCPP_TEMPLATE_VIS __hash_local_iterator
521 typedef __hash_node_types<_NodePtr> _NodeTypes;
522 typedef _NodePtr __node_pointer;
523 typedef typename _NodeTypes::__next_pointer __next_pointer;
525 __next_pointer __node_;
527 size_t __bucket_count_;
530 typedef forward_iterator_tag iterator_category;
531 typedef typename _NodeTypes::__node_value_type value_type;
532 typedef typename _NodeTypes::difference_type difference_type;
533 typedef value_type& reference;
534 typedef typename _NodeTypes::__node_value_type_pointer pointer;
536 _LIBCPP_INLINE_VISIBILITY __hash_local_iterator() _NOEXCEPT : __node_(nullptr) {
537 _LIBCPP_DEBUG_MODE(__get_db()->__insert_i(this));
540 #if _LIBCPP_DEBUG_LEVEL >= 2
541 _LIBCPP_INLINE_VISIBILITY
542 __hash_local_iterator(const __hash_local_iterator& __i)
543 : __node_(__i.__node_),
544 __bucket_(__i.__bucket_),
545 __bucket_count_(__i.__bucket_count_)
547 __get_db()->__iterator_copy(this, &__i);
550 _LIBCPP_INLINE_VISIBILITY
551 ~__hash_local_iterator()
553 __get_db()->__erase_i(this);
556 _LIBCPP_INLINE_VISIBILITY
557 __hash_local_iterator& operator=(const __hash_local_iterator& __i)
561 __get_db()->__iterator_copy(this, &__i);
562 __node_ = __i.__node_;
563 __bucket_ = __i.__bucket_;
564 __bucket_count_ = __i.__bucket_count_;
568 #endif // _LIBCPP_DEBUG_LEVEL >= 2
570 _LIBCPP_INLINE_VISIBILITY
571 reference operator*() const {
572 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
573 "Attempted to dereference a non-dereferenceable unordered container local_iterator");
574 return __node_->__upcast()->__value_;
577 _LIBCPP_INLINE_VISIBILITY
578 pointer operator->() const {
579 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
580 "Attempted to dereference a non-dereferenceable unordered container local_iterator");
581 return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__value_);
584 _LIBCPP_INLINE_VISIBILITY
585 __hash_local_iterator& operator++() {
586 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
587 "Attempted to increment non-incrementable unordered container local_iterator");
588 __node_ = __node_->__next_;
589 if (__node_ != nullptr && __constrain_hash(__node_->__hash(), __bucket_count_) != __bucket_)
594 _LIBCPP_INLINE_VISIBILITY
595 __hash_local_iterator operator++(int)
597 __hash_local_iterator __t(*this);
602 friend _LIBCPP_INLINE_VISIBILITY
603 bool operator==(const __hash_local_iterator& __x, const __hash_local_iterator& __y)
605 return __x.__node_ == __y.__node_;
607 friend _LIBCPP_INLINE_VISIBILITY
608 bool operator!=(const __hash_local_iterator& __x, const __hash_local_iterator& __y)
609 {return !(__x == __y);}
612 #if _LIBCPP_DEBUG_LEVEL >= 2
613 _LIBCPP_INLINE_VISIBILITY
614 __hash_local_iterator(__next_pointer __node, size_t __bucket,
615 size_t __bucket_count, const void* __c) _NOEXCEPT
618 __bucket_count_(__bucket_count)
620 __get_db()->__insert_ic(this, __c);
621 if (__node_ != nullptr)
622 __node_ = __node_->__next_;
625 _LIBCPP_INLINE_VISIBILITY
626 __hash_local_iterator(__next_pointer __node, size_t __bucket,
627 size_t __bucket_count) _NOEXCEPT
630 __bucket_count_(__bucket_count)
632 if (__node_ != nullptr)
633 __node_ = __node_->__next_;
636 template <class, class, class, class> friend class __hash_table;
637 template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator;
638 template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_map_iterator;
641 template <class _ConstNodePtr>
642 class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator
644 typedef __hash_node_types<_ConstNodePtr> _NodeTypes;
645 typedef _ConstNodePtr __node_pointer;
646 typedef typename _NodeTypes::__next_pointer __next_pointer;
648 __next_pointer __node_;
650 size_t __bucket_count_;
652 typedef pointer_traits<__node_pointer> __pointer_traits;
653 typedef typename __pointer_traits::element_type __node;
654 typedef typename remove_const<__node>::type __non_const_node;
655 typedef typename __rebind_pointer<__node_pointer, __non_const_node>::type
656 __non_const_node_pointer;
658 typedef __hash_local_iterator<__non_const_node_pointer>
659 __non_const_iterator;
661 typedef forward_iterator_tag iterator_category;
662 typedef typename _NodeTypes::__node_value_type value_type;
663 typedef typename _NodeTypes::difference_type difference_type;
664 typedef const value_type& reference;
665 typedef typename _NodeTypes::__const_node_value_type_pointer pointer;
668 _LIBCPP_INLINE_VISIBILITY __hash_const_local_iterator() _NOEXCEPT : __node_(nullptr) {
669 _LIBCPP_DEBUG_MODE(__get_db()->__insert_i(this));
672 _LIBCPP_INLINE_VISIBILITY
673 __hash_const_local_iterator(const __non_const_iterator& __x) _NOEXCEPT
674 : __node_(__x.__node_),
675 __bucket_(__x.__bucket_),
676 __bucket_count_(__x.__bucket_count_)
678 _LIBCPP_DEBUG_MODE(__get_db()->__iterator_copy(this, &__x));
681 #if _LIBCPP_DEBUG_LEVEL >= 2
682 _LIBCPP_INLINE_VISIBILITY
683 __hash_const_local_iterator(const __hash_const_local_iterator& __i)
684 : __node_(__i.__node_),
685 __bucket_(__i.__bucket_),
686 __bucket_count_(__i.__bucket_count_)
688 __get_db()->__iterator_copy(this, &__i);
691 _LIBCPP_INLINE_VISIBILITY
692 ~__hash_const_local_iterator()
694 __get_db()->__erase_i(this);
697 _LIBCPP_INLINE_VISIBILITY
698 __hash_const_local_iterator& operator=(const __hash_const_local_iterator& __i)
702 __get_db()->__iterator_copy(this, &__i);
703 __node_ = __i.__node_;
704 __bucket_ = __i.__bucket_;
705 __bucket_count_ = __i.__bucket_count_;
709 #endif // _LIBCPP_DEBUG_LEVEL >= 2
711 _LIBCPP_INLINE_VISIBILITY
712 reference operator*() const {
713 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
714 "Attempted to dereference a non-dereferenceable unordered container const_local_iterator");
715 return __node_->__upcast()->__value_;
718 _LIBCPP_INLINE_VISIBILITY
719 pointer operator->() const {
720 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
721 "Attempted to dereference a non-dereferenceable unordered container const_local_iterator");
722 return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__value_);
725 _LIBCPP_INLINE_VISIBILITY
726 __hash_const_local_iterator& operator++() {
727 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
728 "Attempted to increment non-incrementable unordered container const_local_iterator");
729 __node_ = __node_->__next_;
730 if (__node_ != nullptr && __constrain_hash(__node_->__hash(), __bucket_count_) != __bucket_)
735 _LIBCPP_INLINE_VISIBILITY
736 __hash_const_local_iterator operator++(int)
738 __hash_const_local_iterator __t(*this);
743 friend _LIBCPP_INLINE_VISIBILITY
744 bool operator==(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y)
746 return __x.__node_ == __y.__node_;
748 friend _LIBCPP_INLINE_VISIBILITY
749 bool operator!=(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y)
750 {return !(__x == __y);}
753 #if _LIBCPP_DEBUG_LEVEL >= 2
754 _LIBCPP_INLINE_VISIBILITY
755 __hash_const_local_iterator(__next_pointer __node, size_t __bucket,
756 size_t __bucket_count, const void* __c) _NOEXCEPT
759 __bucket_count_(__bucket_count)
761 __get_db()->__insert_ic(this, __c);
762 if (__node_ != nullptr)
763 __node_ = __node_->__next_;
766 _LIBCPP_INLINE_VISIBILITY
767 __hash_const_local_iterator(__next_pointer __node, size_t __bucket,
768 size_t __bucket_count) _NOEXCEPT
771 __bucket_count_(__bucket_count)
773 if (__node_ != nullptr)
774 __node_ = __node_->__next_;
777 template <class, class, class, class> friend class __hash_table;
778 template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator;
781 template <class _Alloc>
782 class __bucket_list_deallocator
784 typedef _Alloc allocator_type;
785 typedef allocator_traits<allocator_type> __alloc_traits;
786 typedef typename __alloc_traits::size_type size_type;
788 __compressed_pair<size_type, allocator_type> __data_;
790 typedef typename __alloc_traits::pointer pointer;
792 _LIBCPP_INLINE_VISIBILITY
793 __bucket_list_deallocator()
794 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
797 _LIBCPP_INLINE_VISIBILITY
798 __bucket_list_deallocator(const allocator_type& __a, size_type __size)
799 _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value)
800 : __data_(__size, __a) {}
802 #ifndef _LIBCPP_CXX03_LANG
803 _LIBCPP_INLINE_VISIBILITY
804 __bucket_list_deallocator(__bucket_list_deallocator&& __x)
805 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
806 : __data_(_VSTD::move(__x.__data_))
812 _LIBCPP_INLINE_VISIBILITY
813 size_type& size() _NOEXCEPT {return __data_.first();}
814 _LIBCPP_INLINE_VISIBILITY
815 size_type size() const _NOEXCEPT {return __data_.first();}
817 _LIBCPP_INLINE_VISIBILITY
818 allocator_type& __alloc() _NOEXCEPT {return __data_.second();}
819 _LIBCPP_INLINE_VISIBILITY
820 const allocator_type& __alloc() const _NOEXCEPT {return __data_.second();}
822 _LIBCPP_INLINE_VISIBILITY
823 void operator()(pointer __p) _NOEXCEPT
825 __alloc_traits::deallocate(__alloc(), __p, size());
829 template <class _Alloc> class __hash_map_node_destructor;
831 template <class _Alloc>
832 class __hash_node_destructor
834 typedef _Alloc allocator_type;
835 typedef allocator_traits<allocator_type> __alloc_traits;
838 typedef typename __alloc_traits::pointer pointer;
840 typedef __hash_node_types<pointer> _NodeTypes;
842 allocator_type& __na_;
844 __hash_node_destructor& operator=(const __hash_node_destructor&);
847 bool __value_constructed;
849 _LIBCPP_INLINE_VISIBILITY
850 explicit __hash_node_destructor(allocator_type& __na,
851 bool __constructed = false) _NOEXCEPT
853 __value_constructed(__constructed)
856 _LIBCPP_INLINE_VISIBILITY
857 void operator()(pointer __p) _NOEXCEPT
859 if (__value_constructed)
860 __alloc_traits::destroy(__na_, _NodeTypes::__get_ptr(__p->__value_));
862 __alloc_traits::deallocate(__na_, __p, 1);
865 template <class> friend class __hash_map_node_destructor;
869 #ifndef _LIBCPP_CXX03_LANG
870 template <class _Key, class _Hash, class _Equal, class _Alloc>
871 struct __diagnose_hash_table_helper {
872 static constexpr bool __trigger_diagnostics()
873 _LIBCPP_DIAGNOSE_WARNING(__check_hash_requirements<_Key, _Hash>::value
874 && !__invokable<_Hash const&, _Key const&>::value,
875 "the specified hash functor does not provide a const call operator")
876 _LIBCPP_DIAGNOSE_WARNING(is_copy_constructible<_Equal>::value
877 && !__invokable<_Equal const&, _Key const&, _Key const&>::value,
878 "the specified comparator type does not provide a const call operator")
880 static_assert(__check_hash_requirements<_Key, _Hash>::value,
881 "the specified hash does not meet the Hash requirements");
882 static_assert(is_copy_constructible<_Equal>::value,
883 "the specified comparator is required to be copy constructible");
888 template <class _Key, class _Value, class _Hash, class _Equal, class _Alloc>
889 struct __diagnose_hash_table_helper<
890 __hash_value_type<_Key, _Value>,
891 __unordered_map_hasher<_Key, __hash_value_type<_Key, _Value>, _Hash>,
892 __unordered_map_equal<_Key, __hash_value_type<_Key, _Value>, _Equal>,
894 : __diagnose_hash_table_helper<_Key, _Hash, _Equal, _Alloc>
897 #endif // _LIBCPP_CXX03_LANG
899 template <class _Tp, class _Hash, class _Equal, class _Alloc>
903 typedef _Tp value_type;
904 typedef _Hash hasher;
905 typedef _Equal key_equal;
906 typedef _Alloc allocator_type;
909 typedef allocator_traits<allocator_type> __alloc_traits;
911 __make_hash_node_types<value_type, typename __alloc_traits::void_pointer>::type
915 typedef typename _NodeTypes::__node_value_type __node_value_type;
916 typedef typename _NodeTypes::__container_value_type __container_value_type;
917 typedef typename _NodeTypes::key_type key_type;
918 typedef value_type& reference;
919 typedef const value_type& const_reference;
920 typedef typename __alloc_traits::pointer pointer;
921 typedef typename __alloc_traits::const_pointer const_pointer;
922 #ifndef _LIBCPP_ABI_FIX_UNORDERED_CONTAINER_SIZE_TYPE
923 typedef typename __alloc_traits::size_type size_type;
925 typedef typename _NodeTypes::size_type size_type;
927 typedef typename _NodeTypes::difference_type difference_type;
931 typedef typename _NodeTypes::__node_type __node;
932 typedef typename __rebind_alloc_helper<__alloc_traits, __node>::type __node_allocator;
933 typedef allocator_traits<__node_allocator> __node_traits;
934 typedef typename _NodeTypes::__void_pointer __void_pointer;
935 typedef typename _NodeTypes::__node_pointer __node_pointer;
936 typedef typename _NodeTypes::__node_pointer __node_const_pointer;
937 typedef typename _NodeTypes::__node_base_type __first_node;
938 typedef typename _NodeTypes::__node_base_pointer __node_base_pointer;
939 typedef typename _NodeTypes::__next_pointer __next_pointer;
942 // check for sane allocator pointer rebinding semantics. Rebinding the
943 // allocator for a new pointer type should be exactly the same as rebinding
944 // the pointer using 'pointer_traits'.
945 static_assert((is_same<__node_pointer, typename __node_traits::pointer>::value),
946 "Allocator does not rebind pointers in a sane manner.");
947 typedef typename __rebind_alloc_helper<__node_traits, __first_node>::type
948 __node_base_allocator;
949 typedef allocator_traits<__node_base_allocator> __node_base_traits;
950 static_assert((is_same<__node_base_pointer, typename __node_base_traits::pointer>::value),
951 "Allocator does not rebind pointers in a sane manner.");
955 typedef typename __rebind_alloc_helper<__node_traits, __next_pointer>::type __pointer_allocator;
956 typedef __bucket_list_deallocator<__pointer_allocator> __bucket_list_deleter;
957 typedef unique_ptr<__next_pointer[], __bucket_list_deleter> __bucket_list;
958 typedef allocator_traits<__pointer_allocator> __pointer_alloc_traits;
959 typedef typename __bucket_list_deleter::pointer __node_pointer_pointer;
961 #ifndef _LIBCPP_CXX03_LANG
962 static_assert(__diagnose_hash_table_helper<_Tp, _Hash, _Equal, _Alloc>::__trigger_diagnostics(), "");
965 // --- Member data begin ---
966 __bucket_list __bucket_list_;
967 __compressed_pair<__first_node, __node_allocator> __p1_;
968 __compressed_pair<size_type, hasher> __p2_;
969 __compressed_pair<float, key_equal> __p3_;
970 // --- Member data end ---
972 _LIBCPP_INLINE_VISIBILITY
973 size_type& size() _NOEXCEPT {return __p2_.first();}
975 _LIBCPP_INLINE_VISIBILITY
976 size_type size() const _NOEXCEPT {return __p2_.first();}
978 _LIBCPP_INLINE_VISIBILITY
979 hasher& hash_function() _NOEXCEPT {return __p2_.second();}
980 _LIBCPP_INLINE_VISIBILITY
981 const hasher& hash_function() const _NOEXCEPT {return __p2_.second();}
983 _LIBCPP_INLINE_VISIBILITY
984 float& max_load_factor() _NOEXCEPT {return __p3_.first();}
985 _LIBCPP_INLINE_VISIBILITY
986 float max_load_factor() const _NOEXCEPT {return __p3_.first();}
988 _LIBCPP_INLINE_VISIBILITY
989 key_equal& key_eq() _NOEXCEPT {return __p3_.second();}
990 _LIBCPP_INLINE_VISIBILITY
991 const key_equal& key_eq() const _NOEXCEPT {return __p3_.second();}
993 _LIBCPP_INLINE_VISIBILITY
994 __node_allocator& __node_alloc() _NOEXCEPT {return __p1_.second();}
995 _LIBCPP_INLINE_VISIBILITY
996 const __node_allocator& __node_alloc() const _NOEXCEPT
997 {return __p1_.second();}
1000 typedef __hash_iterator<__node_pointer> iterator;
1001 typedef __hash_const_iterator<__node_pointer> const_iterator;
1002 typedef __hash_local_iterator<__node_pointer> local_iterator;
1003 typedef __hash_const_local_iterator<__node_pointer> const_local_iterator;
1005 _LIBCPP_INLINE_VISIBILITY
1008 is_nothrow_default_constructible<__bucket_list>::value &&
1009 is_nothrow_default_constructible<__first_node>::value &&
1010 is_nothrow_default_constructible<__node_allocator>::value &&
1011 is_nothrow_default_constructible<hasher>::value &&
1012 is_nothrow_default_constructible<key_equal>::value);
1013 _LIBCPP_INLINE_VISIBILITY
1014 __hash_table(const hasher& __hf, const key_equal& __eql);
1015 __hash_table(const hasher& __hf, const key_equal& __eql,
1016 const allocator_type& __a);
1017 explicit __hash_table(const allocator_type& __a);
1018 __hash_table(const __hash_table& __u);
1019 __hash_table(const __hash_table& __u, const allocator_type& __a);
1020 #ifndef _LIBCPP_CXX03_LANG
1021 __hash_table(__hash_table&& __u)
1023 is_nothrow_move_constructible<__bucket_list>::value &&
1024 is_nothrow_move_constructible<__first_node>::value &&
1025 is_nothrow_move_constructible<__node_allocator>::value &&
1026 is_nothrow_move_constructible<hasher>::value &&
1027 is_nothrow_move_constructible<key_equal>::value);
1028 __hash_table(__hash_table&& __u, const allocator_type& __a);
1029 #endif // _LIBCPP_CXX03_LANG
1032 __hash_table& operator=(const __hash_table& __u);
1033 #ifndef _LIBCPP_CXX03_LANG
1034 _LIBCPP_INLINE_VISIBILITY
1035 __hash_table& operator=(__hash_table&& __u)
1037 __node_traits::propagate_on_container_move_assignment::value &&
1038 is_nothrow_move_assignable<__node_allocator>::value &&
1039 is_nothrow_move_assignable<hasher>::value &&
1040 is_nothrow_move_assignable<key_equal>::value);
1042 template <class _InputIterator>
1043 void __assign_unique(_InputIterator __first, _InputIterator __last);
1044 template <class _InputIterator>
1045 void __assign_multi(_InputIterator __first, _InputIterator __last);
1047 _LIBCPP_INLINE_VISIBILITY
1048 size_type max_size() const _NOEXCEPT
1050 return std::min<size_type>(
1051 __node_traits::max_size(__node_alloc()),
1052 numeric_limits<difference_type >::max()
1056 pair<iterator, bool> __node_insert_unique(__node_pointer __nd);
1057 iterator __node_insert_multi(__node_pointer __nd);
1058 iterator __node_insert_multi(const_iterator __p,
1059 __node_pointer __nd);
1061 #ifndef _LIBCPP_CXX03_LANG
1062 template <class _Key, class ..._Args>
1063 _LIBCPP_INLINE_VISIBILITY
1064 pair<iterator, bool> __emplace_unique_key_args(_Key const& __k, _Args&&... __args);
1066 template <class... _Args>
1067 _LIBCPP_INLINE_VISIBILITY
1068 pair<iterator, bool> __emplace_unique_impl(_Args&&... __args);
1070 template <class _Pp>
1071 _LIBCPP_INLINE_VISIBILITY
1072 pair<iterator, bool> __emplace_unique(_Pp&& __x) {
1073 return __emplace_unique_extract_key(_VSTD::forward<_Pp>(__x),
1074 __can_extract_key<_Pp, key_type>());
1077 template <class _First, class _Second>
1078 _LIBCPP_INLINE_VISIBILITY
1080 __can_extract_map_key<_First, key_type, __container_value_type>::value,
1081 pair<iterator, bool>
1082 >::type __emplace_unique(_First&& __f, _Second&& __s) {
1083 return __emplace_unique_key_args(__f, _VSTD::forward<_First>(__f),
1084 _VSTD::forward<_Second>(__s));
1087 template <class... _Args>
1088 _LIBCPP_INLINE_VISIBILITY
1089 pair<iterator, bool> __emplace_unique(_Args&&... __args) {
1090 return __emplace_unique_impl(_VSTD::forward<_Args>(__args)...);
1093 template <class _Pp>
1094 _LIBCPP_INLINE_VISIBILITY
1095 pair<iterator, bool>
1096 __emplace_unique_extract_key(_Pp&& __x, __extract_key_fail_tag) {
1097 return __emplace_unique_impl(_VSTD::forward<_Pp>(__x));
1099 template <class _Pp>
1100 _LIBCPP_INLINE_VISIBILITY
1101 pair<iterator, bool>
1102 __emplace_unique_extract_key(_Pp&& __x, __extract_key_self_tag) {
1103 return __emplace_unique_key_args(__x, _VSTD::forward<_Pp>(__x));
1105 template <class _Pp>
1106 _LIBCPP_INLINE_VISIBILITY
1107 pair<iterator, bool>
1108 __emplace_unique_extract_key(_Pp&& __x, __extract_key_first_tag) {
1109 return __emplace_unique_key_args(__x.first, _VSTD::forward<_Pp>(__x));
1112 template <class... _Args>
1113 _LIBCPP_INLINE_VISIBILITY
1114 iterator __emplace_multi(_Args&&... __args);
1115 template <class... _Args>
1116 _LIBCPP_INLINE_VISIBILITY
1117 iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args);
1120 _LIBCPP_INLINE_VISIBILITY
1121 pair<iterator, bool>
1122 __insert_unique(__container_value_type&& __x) {
1123 return __emplace_unique_key_args(_NodeTypes::__get_key(__x), _VSTD::move(__x));
1126 template <class _Pp, class = typename enable_if<
1127 !__is_same_uncvref<_Pp, __container_value_type>::value
1129 _LIBCPP_INLINE_VISIBILITY
1130 pair<iterator, bool> __insert_unique(_Pp&& __x) {
1131 return __emplace_unique(_VSTD::forward<_Pp>(__x));
1134 template <class _Pp>
1135 _LIBCPP_INLINE_VISIBILITY
1136 iterator __insert_multi(_Pp&& __x) {
1137 return __emplace_multi(_VSTD::forward<_Pp>(__x));
1140 template <class _Pp>
1141 _LIBCPP_INLINE_VISIBILITY
1142 iterator __insert_multi(const_iterator __p, _Pp&& __x) {
1143 return __emplace_hint_multi(__p, _VSTD::forward<_Pp>(__x));
1146 #else // !defined(_LIBCPP_CXX03_LANG)
1147 template <class _Key, class _Args>
1148 _LIBCPP_INLINE_VISIBILITY
1149 pair<iterator, bool> __emplace_unique_key_args(_Key const&, _Args& __args);
1151 iterator __insert_multi(const __container_value_type& __x);
1152 iterator __insert_multi(const_iterator __p, const __container_value_type& __x);
1155 _LIBCPP_INLINE_VISIBILITY
1156 pair<iterator, bool> __insert_unique(const __container_value_type& __x) {
1157 return __emplace_unique_key_args(_NodeTypes::__get_key(__x), __x);
1160 void clear() _NOEXCEPT;
1161 void rehash(size_type __n);
1162 _LIBCPP_INLINE_VISIBILITY void reserve(size_type __n)
1163 {rehash(static_cast<size_type>(ceil(__n / max_load_factor())));}
1165 _LIBCPP_INLINE_VISIBILITY
1166 size_type bucket_count() const _NOEXCEPT
1168 return __bucket_list_.get_deleter().size();
1171 _LIBCPP_INLINE_VISIBILITY
1172 iterator begin() _NOEXCEPT;
1173 _LIBCPP_INLINE_VISIBILITY
1174 iterator end() _NOEXCEPT;
1175 _LIBCPP_INLINE_VISIBILITY
1176 const_iterator begin() const _NOEXCEPT;
1177 _LIBCPP_INLINE_VISIBILITY
1178 const_iterator end() const _NOEXCEPT;
1180 template <class _Key>
1181 _LIBCPP_INLINE_VISIBILITY
1182 size_type bucket(const _Key& __k) const
1184 _LIBCPP_ASSERT(bucket_count() > 0,
1185 "unordered container::bucket(key) called when bucket_count() == 0");
1186 return __constrain_hash(hash_function()(__k), bucket_count());
1189 template <class _Key>
1190 iterator find(const _Key& __x);
1191 template <class _Key>
1192 const_iterator find(const _Key& __x) const;
1194 typedef __hash_node_destructor<__node_allocator> _Dp;
1195 typedef unique_ptr<__node, _Dp> __node_holder;
1197 iterator erase(const_iterator __p);
1198 iterator erase(const_iterator __first, const_iterator __last);
1199 template <class _Key>
1200 size_type __erase_unique(const _Key& __k);
1201 template <class _Key>
1202 size_type __erase_multi(const _Key& __k);
1203 __node_holder remove(const_iterator __p) _NOEXCEPT;
1205 template <class _Key>
1206 _LIBCPP_INLINE_VISIBILITY
1207 size_type __count_unique(const _Key& __k) const;
1208 template <class _Key>
1209 size_type __count_multi(const _Key& __k) const;
1211 template <class _Key>
1212 pair<iterator, iterator>
1213 __equal_range_unique(const _Key& __k);
1214 template <class _Key>
1215 pair<const_iterator, const_iterator>
1216 __equal_range_unique(const _Key& __k) const;
1218 template <class _Key>
1219 pair<iterator, iterator>
1220 __equal_range_multi(const _Key& __k);
1221 template <class _Key>
1222 pair<const_iterator, const_iterator>
1223 __equal_range_multi(const _Key& __k) const;
1225 void swap(__hash_table& __u)
1226 #if _LIBCPP_STD_VER <= 11
1228 __is_nothrow_swappable<hasher>::value && __is_nothrow_swappable<key_equal>::value
1229 && (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value
1230 || __is_nothrow_swappable<__pointer_allocator>::value)
1231 && (!__node_traits::propagate_on_container_swap::value
1232 || __is_nothrow_swappable<__node_allocator>::value)
1235 _NOEXCEPT_DEBUG_(__is_nothrow_swappable<hasher>::value && __is_nothrow_swappable<key_equal>::value);
1238 _LIBCPP_INLINE_VISIBILITY
1239 size_type max_bucket_count() const _NOEXCEPT
1240 {return max_size(); }
1241 size_type bucket_size(size_type __n) const;
1242 _LIBCPP_INLINE_VISIBILITY float load_factor() const _NOEXCEPT
1244 size_type __bc = bucket_count();
1245 return __bc != 0 ? (float)size() / __bc : 0.f;
1247 _LIBCPP_INLINE_VISIBILITY void max_load_factor(float __mlf) _NOEXCEPT
1249 _LIBCPP_ASSERT(__mlf > 0,
1250 "unordered container::max_load_factor(lf) called with lf <= 0");
1251 max_load_factor() = _VSTD::max(__mlf, load_factor());
1254 _LIBCPP_INLINE_VISIBILITY
1256 begin(size_type __n)
1258 _LIBCPP_ASSERT(__n < bucket_count(),
1259 "unordered container::begin(n) called with n >= bucket_count()");
1260 #if _LIBCPP_DEBUG_LEVEL >= 2
1261 return local_iterator(__bucket_list_[__n], __n, bucket_count(), this);
1263 return local_iterator(__bucket_list_[__n], __n, bucket_count());
1267 _LIBCPP_INLINE_VISIBILITY
1271 _LIBCPP_ASSERT(__n < bucket_count(),
1272 "unordered container::end(n) called with n >= bucket_count()");
1273 #if _LIBCPP_DEBUG_LEVEL >= 2
1274 return local_iterator(nullptr, __n, bucket_count(), this);
1276 return local_iterator(nullptr, __n, bucket_count());
1280 _LIBCPP_INLINE_VISIBILITY
1281 const_local_iterator
1282 cbegin(size_type __n) const
1284 _LIBCPP_ASSERT(__n < bucket_count(),
1285 "unordered container::cbegin(n) called with n >= bucket_count()");
1286 #if _LIBCPP_DEBUG_LEVEL >= 2
1287 return const_local_iterator(__bucket_list_[__n], __n, bucket_count(), this);
1289 return const_local_iterator(__bucket_list_[__n], __n, bucket_count());
1293 _LIBCPP_INLINE_VISIBILITY
1294 const_local_iterator
1295 cend(size_type __n) const
1297 _LIBCPP_ASSERT(__n < bucket_count(),
1298 "unordered container::cend(n) called with n >= bucket_count()");
1299 #if _LIBCPP_DEBUG_LEVEL >= 2
1300 return const_local_iterator(nullptr, __n, bucket_count(), this);
1302 return const_local_iterator(nullptr, __n, bucket_count());
1306 #if _LIBCPP_DEBUG_LEVEL >= 2
1308 bool __dereferenceable(const const_iterator* __i) const;
1309 bool __decrementable(const const_iterator* __i) const;
1310 bool __addable(const const_iterator* __i, ptrdiff_t __n) const;
1311 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const;
1313 #endif // _LIBCPP_DEBUG_LEVEL >= 2
1316 void __rehash(size_type __n);
1318 #ifndef _LIBCPP_CXX03_LANG
1319 template <class ..._Args>
1320 __node_holder __construct_node(_Args&& ...__args);
1322 template <class _First, class ..._Rest>
1323 __node_holder __construct_node_hash(size_t __hash, _First&& __f, _Rest&&... __rest);
1324 #else // _LIBCPP_CXX03_LANG
1325 __node_holder __construct_node(const __container_value_type& __v);
1326 __node_holder __construct_node_hash(size_t __hash, const __container_value_type& __v);
1330 _LIBCPP_INLINE_VISIBILITY
1331 void __copy_assign_alloc(const __hash_table& __u)
1332 {__copy_assign_alloc(__u, integral_constant<bool,
1333 __node_traits::propagate_on_container_copy_assignment::value>());}
1334 void __copy_assign_alloc(const __hash_table& __u, true_type);
1335 _LIBCPP_INLINE_VISIBILITY
1336 void __copy_assign_alloc(const __hash_table&, false_type) {}
1338 #ifndef _LIBCPP_CXX03_LANG
1339 void __move_assign(__hash_table& __u, false_type);
1340 void __move_assign(__hash_table& __u, true_type)
1342 is_nothrow_move_assignable<__node_allocator>::value &&
1343 is_nothrow_move_assignable<hasher>::value &&
1344 is_nothrow_move_assignable<key_equal>::value);
1345 _LIBCPP_INLINE_VISIBILITY
1346 void __move_assign_alloc(__hash_table& __u)
1348 !__node_traits::propagate_on_container_move_assignment::value ||
1349 (is_nothrow_move_assignable<__pointer_allocator>::value &&
1350 is_nothrow_move_assignable<__node_allocator>::value))
1351 {__move_assign_alloc(__u, integral_constant<bool,
1352 __node_traits::propagate_on_container_move_assignment::value>());}
1353 _LIBCPP_INLINE_VISIBILITY
1354 void __move_assign_alloc(__hash_table& __u, true_type)
1356 is_nothrow_move_assignable<__pointer_allocator>::value &&
1357 is_nothrow_move_assignable<__node_allocator>::value)
1359 __bucket_list_.get_deleter().__alloc() =
1360 _VSTD::move(__u.__bucket_list_.get_deleter().__alloc());
1361 __node_alloc() = _VSTD::move(__u.__node_alloc());
1363 _LIBCPP_INLINE_VISIBILITY
1364 void __move_assign_alloc(__hash_table&, false_type) _NOEXCEPT {}
1365 #endif // _LIBCPP_CXX03_LANG
1367 void __deallocate_node(__next_pointer __np) _NOEXCEPT;
1368 __next_pointer __detach() _NOEXCEPT;
1370 template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_map;
1371 template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
1374 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1376 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table()
1378 is_nothrow_default_constructible<__bucket_list>::value &&
1379 is_nothrow_default_constructible<__first_node>::value &&
1380 is_nothrow_default_constructible<__node_allocator>::value &&
1381 is_nothrow_default_constructible<hasher>::value &&
1382 is_nothrow_default_constructible<key_equal>::value)
1388 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1390 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf,
1391 const key_equal& __eql)
1392 : __bucket_list_(nullptr, __bucket_list_deleter()),
1399 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1400 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf,
1401 const key_equal& __eql,
1402 const allocator_type& __a)
1403 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
1404 __p1_(__second_tag(), __node_allocator(__a)),
1410 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1411 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const allocator_type& __a)
1412 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
1413 __p1_(__second_tag(), __node_allocator(__a)),
1419 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1420 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u)
1421 : __bucket_list_(nullptr,
1422 __bucket_list_deleter(allocator_traits<__pointer_allocator>::
1423 select_on_container_copy_construction(
1424 __u.__bucket_list_.get_deleter().__alloc()), 0)),
1425 __p1_(__second_tag(), allocator_traits<__node_allocator>::
1426 select_on_container_copy_construction(__u.__node_alloc())),
1427 __p2_(0, __u.hash_function()),
1432 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1433 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u,
1434 const allocator_type& __a)
1435 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
1436 __p1_(__second_tag(), __node_allocator(__a)),
1437 __p2_(0, __u.hash_function()),
1442 #ifndef _LIBCPP_CXX03_LANG
1444 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1445 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u)
1447 is_nothrow_move_constructible<__bucket_list>::value &&
1448 is_nothrow_move_constructible<__first_node>::value &&
1449 is_nothrow_move_constructible<__node_allocator>::value &&
1450 is_nothrow_move_constructible<hasher>::value &&
1451 is_nothrow_move_constructible<key_equal>::value)
1452 : __bucket_list_(_VSTD::move(__u.__bucket_list_)),
1453 __p1_(_VSTD::move(__u.__p1_)),
1454 __p2_(_VSTD::move(__u.__p2_)),
1455 __p3_(_VSTD::move(__u.__p3_))
1459 __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash(), bucket_count())] =
1460 __p1_.first().__ptr();
1461 __u.__p1_.first().__next_ = nullptr;
1466 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1467 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u,
1468 const allocator_type& __a)
1469 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
1470 __p1_(__second_tag(), __node_allocator(__a)),
1471 __p2_(0, _VSTD::move(__u.hash_function())),
1472 __p3_(_VSTD::move(__u.__p3_))
1474 if (__a == allocator_type(__u.__node_alloc()))
1476 __bucket_list_.reset(__u.__bucket_list_.release());
1477 __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size();
1478 __u.__bucket_list_.get_deleter().size() = 0;
1481 __p1_.first().__next_ = __u.__p1_.first().__next_;
1482 __u.__p1_.first().__next_ = nullptr;
1483 __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash(), bucket_count())] =
1484 __p1_.first().__ptr();
1485 size() = __u.size();
1491 #endif // _LIBCPP_CXX03_LANG
1493 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1494 __hash_table<_Tp, _Hash, _Equal, _Alloc>::~__hash_table()
1496 #if defined(_LIBCPP_CXX03_LANG)
1497 static_assert((is_copy_constructible<key_equal>::value),
1498 "Predicate must be copy-constructible.");
1499 static_assert((is_copy_constructible<hasher>::value),
1500 "Hasher must be copy-constructible.");
1503 __deallocate_node(__p1_.first().__next_);
1504 #if _LIBCPP_DEBUG_LEVEL >= 2
1505 __get_db()->__erase_c(this);
1509 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1511 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__copy_assign_alloc(
1512 const __hash_table& __u, true_type)
1514 if (__node_alloc() != __u.__node_alloc())
1517 __bucket_list_.reset();
1518 __bucket_list_.get_deleter().size() = 0;
1520 __bucket_list_.get_deleter().__alloc() = __u.__bucket_list_.get_deleter().__alloc();
1521 __node_alloc() = __u.__node_alloc();
1524 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1525 __hash_table<_Tp, _Hash, _Equal, _Alloc>&
1526 __hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(const __hash_table& __u)
1530 __copy_assign_alloc(__u);
1531 hash_function() = __u.hash_function();
1532 key_eq() = __u.key_eq();
1533 max_load_factor() = __u.max_load_factor();
1534 __assign_multi(__u.begin(), __u.end());
1539 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1541 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__deallocate_node(__next_pointer __np)
1544 __node_allocator& __na = __node_alloc();
1545 while (__np != nullptr)
1547 __next_pointer __next = __np->__next_;
1548 #if _LIBCPP_DEBUG_LEVEL >= 2
1549 __c_node* __c = __get_db()->__find_c_and_lock(this);
1550 for (__i_node** __p = __c->end_; __p != __c->beg_; )
1553 iterator* __i = static_cast<iterator*>((*__p)->__i_);
1554 if (__i->__node_ == __np)
1556 (*__p)->__c_ = nullptr;
1557 if (--__c->end_ != __p)
1558 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
1561 __get_db()->unlock();
1563 __node_pointer __real_np = __np->__upcast();
1564 __node_traits::destroy(__na, _NodeTypes::__get_ptr(__real_np->__value_));
1565 __node_traits::deallocate(__na, __real_np, 1);
1570 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1571 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer
1572 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__detach() _NOEXCEPT
1574 size_type __bc = bucket_count();
1575 for (size_type __i = 0; __i < __bc; ++__i)
1576 __bucket_list_[__i] = nullptr;
1578 __next_pointer __cache = __p1_.first().__next_;
1579 __p1_.first().__next_ = nullptr;
1583 #ifndef _LIBCPP_CXX03_LANG
1585 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1587 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign(
1588 __hash_table& __u, true_type)
1590 is_nothrow_move_assignable<__node_allocator>::value &&
1591 is_nothrow_move_assignable<hasher>::value &&
1592 is_nothrow_move_assignable<key_equal>::value)
1595 __bucket_list_.reset(__u.__bucket_list_.release());
1596 __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size();
1597 __u.__bucket_list_.get_deleter().size() = 0;
1598 __move_assign_alloc(__u);
1599 size() = __u.size();
1600 hash_function() = _VSTD::move(__u.hash_function());
1601 max_load_factor() = __u.max_load_factor();
1602 key_eq() = _VSTD::move(__u.key_eq());
1603 __p1_.first().__next_ = __u.__p1_.first().__next_;
1606 __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash(), bucket_count())] =
1607 __p1_.first().__ptr();
1608 __u.__p1_.first().__next_ = nullptr;
1611 #if _LIBCPP_DEBUG_LEVEL >= 2
1612 __get_db()->swap(this, &__u);
1616 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1618 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign(
1619 __hash_table& __u, false_type)
1621 if (__node_alloc() == __u.__node_alloc())
1622 __move_assign(__u, true_type());
1625 hash_function() = _VSTD::move(__u.hash_function());
1626 key_eq() = _VSTD::move(__u.key_eq());
1627 max_load_factor() = __u.max_load_factor();
1628 if (bucket_count() != 0)
1630 __next_pointer __cache = __detach();
1631 #ifndef _LIBCPP_NO_EXCEPTIONS
1634 #endif // _LIBCPP_NO_EXCEPTIONS
1635 const_iterator __i = __u.begin();
1636 while (__cache != nullptr && __u.size() != 0)
1638 __cache->__upcast()->__value_ =
1639 _VSTD::move(__u.remove(__i++)->__value_);
1640 __next_pointer __next = __cache->__next_;
1641 __node_insert_multi(__cache->__upcast());
1644 #ifndef _LIBCPP_NO_EXCEPTIONS
1648 __deallocate_node(__cache);
1651 #endif // _LIBCPP_NO_EXCEPTIONS
1652 __deallocate_node(__cache);
1654 const_iterator __i = __u.begin();
1655 while (__u.size() != 0)
1657 __node_holder __h = __construct_node(_NodeTypes::__move(__u.remove(__i++)->__value_));
1658 __node_insert_multi(__h.get());
1664 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1666 __hash_table<_Tp, _Hash, _Equal, _Alloc>&
1667 __hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(__hash_table&& __u)
1669 __node_traits::propagate_on_container_move_assignment::value &&
1670 is_nothrow_move_assignable<__node_allocator>::value &&
1671 is_nothrow_move_assignable<hasher>::value &&
1672 is_nothrow_move_assignable<key_equal>::value)
1674 __move_assign(__u, integral_constant<bool,
1675 __node_traits::propagate_on_container_move_assignment::value>());
1679 #endif // _LIBCPP_CXX03_LANG
1681 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1682 template <class _InputIterator>
1684 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_unique(_InputIterator __first,
1685 _InputIterator __last)
1687 typedef iterator_traits<_InputIterator> _ITraits;
1688 typedef typename _ITraits::value_type _ItValueType;
1689 static_assert((is_same<_ItValueType, __container_value_type>::value),
1690 "__assign_unique may only be called with the containers value type");
1692 if (bucket_count() != 0)
1694 __next_pointer __cache = __detach();
1695 #ifndef _LIBCPP_NO_EXCEPTIONS
1698 #endif // _LIBCPP_NO_EXCEPTIONS
1699 for (; __cache != nullptr && __first != __last; ++__first)
1701 __cache->__upcast()->__value_ = *__first;
1702 __next_pointer __next = __cache->__next_;
1703 __node_insert_unique(__cache->__upcast());
1706 #ifndef _LIBCPP_NO_EXCEPTIONS
1710 __deallocate_node(__cache);
1713 #endif // _LIBCPP_NO_EXCEPTIONS
1714 __deallocate_node(__cache);
1716 for (; __first != __last; ++__first)
1717 __insert_unique(*__first);
1720 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1721 template <class _InputIterator>
1723 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_multi(_InputIterator __first,
1724 _InputIterator __last)
1726 typedef iterator_traits<_InputIterator> _ITraits;
1727 typedef typename _ITraits::value_type _ItValueType;
1728 static_assert((is_same<_ItValueType, __container_value_type>::value ||
1729 is_same<_ItValueType, __node_value_type>::value),
1730 "__assign_multi may only be called with the containers value type"
1731 " or the nodes value type");
1732 if (bucket_count() != 0)
1734 __next_pointer __cache = __detach();
1735 #ifndef _LIBCPP_NO_EXCEPTIONS
1738 #endif // _LIBCPP_NO_EXCEPTIONS
1739 for (; __cache != nullptr && __first != __last; ++__first)
1741 __cache->__upcast()->__value_ = *__first;
1742 __next_pointer __next = __cache->__next_;
1743 __node_insert_multi(__cache->__upcast());
1746 #ifndef _LIBCPP_NO_EXCEPTIONS
1750 __deallocate_node(__cache);
1753 #endif // _LIBCPP_NO_EXCEPTIONS
1754 __deallocate_node(__cache);
1756 for (; __first != __last; ++__first)
1757 __insert_multi(_NodeTypes::__get_value(*__first));
1760 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1762 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1763 __hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() _NOEXCEPT
1765 #if _LIBCPP_DEBUG_LEVEL >= 2
1766 return iterator(__p1_.first().__next_, this);
1768 return iterator(__p1_.first().__next_);
1772 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1774 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1775 __hash_table<_Tp, _Hash, _Equal, _Alloc>::end() _NOEXCEPT
1777 #if _LIBCPP_DEBUG_LEVEL >= 2
1778 return iterator(nullptr, this);
1780 return iterator(nullptr);
1784 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1786 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator
1787 __hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() const _NOEXCEPT
1789 #if _LIBCPP_DEBUG_LEVEL >= 2
1790 return const_iterator(__p1_.first().__next_, this);
1792 return const_iterator(__p1_.first().__next_);
1796 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1798 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator
1799 __hash_table<_Tp, _Hash, _Equal, _Alloc>::end() const _NOEXCEPT
1801 #if _LIBCPP_DEBUG_LEVEL >= 2
1802 return const_iterator(nullptr, this);
1804 return const_iterator(nullptr);
1808 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1810 __hash_table<_Tp, _Hash, _Equal, _Alloc>::clear() _NOEXCEPT
1814 __deallocate_node(__p1_.first().__next_);
1815 __p1_.first().__next_ = nullptr;
1816 size_type __bc = bucket_count();
1817 for (size_type __i = 0; __i < __bc; ++__i)
1818 __bucket_list_[__i] = nullptr;
1823 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1824 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
1825 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique(__node_pointer __nd)
1827 __nd->__hash_ = hash_function()(__nd->__value_);
1828 size_type __bc = bucket_count();
1829 bool __inserted = false;
1830 __next_pointer __ndptr;
1834 __chash = __constrain_hash(__nd->__hash_, __bc);
1835 __ndptr = __bucket_list_[__chash];
1836 if (__ndptr != nullptr)
1838 for (__ndptr = __ndptr->__next_; __ndptr != nullptr &&
1839 __constrain_hash(__ndptr->__hash(), __bc) == __chash;
1840 __ndptr = __ndptr->__next_)
1842 if (key_eq()(__ndptr->__upcast()->__value_, __nd->__value_))
1848 if (size()+1 > __bc * max_load_factor() || __bc == 0)
1850 rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc),
1851 size_type(ceil(float(size() + 1) / max_load_factor()))));
1852 __bc = bucket_count();
1853 __chash = __constrain_hash(__nd->__hash_, __bc);
1855 // insert_after __bucket_list_[__chash], or __first_node if bucket is null
1856 __next_pointer __pn = __bucket_list_[__chash];
1857 if (__pn == nullptr)
1859 __pn =__p1_.first().__ptr();
1860 __nd->__next_ = __pn->__next_;
1861 __pn->__next_ = __nd->__ptr();
1862 // fix up __bucket_list_
1863 __bucket_list_[__chash] = __pn;
1864 if (__nd->__next_ != nullptr)
1865 __bucket_list_[__constrain_hash(__nd->__next_->__hash(), __bc)] = __nd->__ptr();
1869 __nd->__next_ = __pn->__next_;
1870 __pn->__next_ = __nd->__ptr();
1872 __ndptr = __nd->__ptr();
1878 #if _LIBCPP_DEBUG_LEVEL >= 2
1879 return pair<iterator, bool>(iterator(__ndptr, this), __inserted);
1881 return pair<iterator, bool>(iterator(__ndptr), __inserted);
1885 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1886 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1887 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __cp)
1889 __cp->__hash_ = hash_function()(__cp->__value_);
1890 size_type __bc = bucket_count();
1891 if (size()+1 > __bc * max_load_factor() || __bc == 0)
1893 rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc),
1894 size_type(ceil(float(size() + 1) / max_load_factor()))));
1895 __bc = bucket_count();
1897 size_t __chash = __constrain_hash(__cp->__hash_, __bc);
1898 __next_pointer __pn = __bucket_list_[__chash];
1899 if (__pn == nullptr)
1901 __pn =__p1_.first().__ptr();
1902 __cp->__next_ = __pn->__next_;
1903 __pn->__next_ = __cp->__ptr();
1904 // fix up __bucket_list_
1905 __bucket_list_[__chash] = __pn;
1906 if (__cp->__next_ != nullptr)
1907 __bucket_list_[__constrain_hash(__cp->__next_->__hash(), __bc)]
1912 for (bool __found = false; __pn->__next_ != nullptr &&
1913 __constrain_hash(__pn->__next_->__hash(), __bc) == __chash;
1914 __pn = __pn->__next_)
1916 // __found key_eq() action
1919 // false true set __found to true
1921 if (__found != (__pn->__next_->__hash() == __cp->__hash_ &&
1922 key_eq()(__pn->__next_->__upcast()->__value_, __cp->__value_)))
1930 __cp->__next_ = __pn->__next_;
1931 __pn->__next_ = __cp->__ptr();
1932 if (__cp->__next_ != nullptr)
1934 size_t __nhash = __constrain_hash(__cp->__next_->__hash(), __bc);
1935 if (__nhash != __chash)
1936 __bucket_list_[__nhash] = __cp->__ptr();
1940 #if _LIBCPP_DEBUG_LEVEL >= 2
1941 return iterator(__cp->__ptr(), this);
1943 return iterator(__cp->__ptr());
1947 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1948 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1949 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(
1950 const_iterator __p, __node_pointer __cp)
1952 #if _LIBCPP_DEBUG_LEVEL >= 2
1953 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1954 "unordered container::emplace_hint(const_iterator, args...) called with an iterator not"
1955 " referring to this unordered container");
1957 if (__p != end() && key_eq()(*__p, __cp->__value_))
1959 __next_pointer __np = __p.__node_;
1960 __cp->__hash_ = __np->__hash();
1961 size_type __bc = bucket_count();
1962 if (size()+1 > __bc * max_load_factor() || __bc == 0)
1964 rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc),
1965 size_type(ceil(float(size() + 1) / max_load_factor()))));
1966 __bc = bucket_count();
1968 size_t __chash = __constrain_hash(__cp->__hash_, __bc);
1969 __next_pointer __pp = __bucket_list_[__chash];
1970 while (__pp->__next_ != __np)
1971 __pp = __pp->__next_;
1972 __cp->__next_ = __np;
1973 __pp->__next_ = static_cast<__next_pointer>(__cp);
1975 #if _LIBCPP_DEBUG_LEVEL >= 2
1976 return iterator(static_cast<__next_pointer>(__cp), this);
1978 return iterator(static_cast<__next_pointer>(__cp));
1981 return __node_insert_multi(__cp);
1986 #ifndef _LIBCPP_CXX03_LANG
1987 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1988 template <class _Key, class ..._Args>
1989 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
1990 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique_key_args(_Key const& __k, _Args&&... __args)
1992 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1993 template <class _Key, class _Args>
1994 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
1995 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique_key_args(_Key const& __k, _Args& __args)
1999 size_t __hash = hash_function()(__k);
2000 size_type __bc = bucket_count();
2001 bool __inserted = false;
2002 __next_pointer __nd;
2006 __chash = __constrain_hash(__hash, __bc);
2007 __nd = __bucket_list_[__chash];
2008 if (__nd != nullptr)
2010 for (__nd = __nd->__next_; __nd != nullptr &&
2011 (__nd->__hash() == __hash || __constrain_hash(__nd->__hash(), __bc) == __chash);
2012 __nd = __nd->__next_)
2014 if (key_eq()(__nd->__upcast()->__value_, __k))
2020 #ifndef _LIBCPP_CXX03_LANG
2021 __node_holder __h = __construct_node_hash(__hash, _VSTD::forward<_Args>(__args)...);
2023 __node_holder __h = __construct_node_hash(__hash, __args);
2025 if (size()+1 > __bc * max_load_factor() || __bc == 0)
2027 rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc),
2028 size_type(ceil(float(size() + 1) / max_load_factor()))));
2029 __bc = bucket_count();
2030 __chash = __constrain_hash(__hash, __bc);
2032 // insert_after __bucket_list_[__chash], or __first_node if bucket is null
2033 __next_pointer __pn = __bucket_list_[__chash];
2034 if (__pn == nullptr)
2036 __pn = __p1_.first().__ptr();
2037 __h->__next_ = __pn->__next_;
2038 __pn->__next_ = __h.get()->__ptr();
2039 // fix up __bucket_list_
2040 __bucket_list_[__chash] = __pn;
2041 if (__h->__next_ != nullptr)
2042 __bucket_list_[__constrain_hash(__h->__next_->__hash(), __bc)]
2043 = __h.get()->__ptr();
2047 __h->__next_ = __pn->__next_;
2048 __pn->__next_ = static_cast<__next_pointer>(__h.get());
2050 __nd = static_cast<__next_pointer>(__h.release());
2056 #if _LIBCPP_DEBUG_LEVEL >= 2
2057 return pair<iterator, bool>(iterator(__nd, this), __inserted);
2059 return pair<iterator, bool>(iterator(__nd), __inserted);
2063 #ifndef _LIBCPP_CXX03_LANG
2065 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2066 template <class... _Args>
2067 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
2068 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique_impl(_Args&&... __args)
2070 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
2071 pair<iterator, bool> __r = __node_insert_unique(__h.get());
2077 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2078 template <class... _Args>
2079 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
2080 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_multi(_Args&&... __args)
2082 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
2083 iterator __r = __node_insert_multi(__h.get());
2088 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2089 template <class... _Args>
2090 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
2091 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_hint_multi(
2092 const_iterator __p, _Args&&... __args)
2094 #if _LIBCPP_DEBUG_LEVEL >= 2
2095 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
2096 "unordered container::emplace_hint(const_iterator, args...) called with an iterator not"
2097 " referring to this unordered container");
2099 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
2100 iterator __r = __node_insert_multi(__p, __h.get());
2105 #else // _LIBCPP_CXX03_LANG
2107 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2108 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
2109 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const __container_value_type& __x)
2111 __node_holder __h = __construct_node(__x);
2112 iterator __r = __node_insert_multi(__h.get());
2117 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2118 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
2119 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const_iterator __p,
2120 const __container_value_type& __x)
2122 #if _LIBCPP_DEBUG_LEVEL >= 2
2123 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
2124 "unordered container::insert(const_iterator, lvalue) called with an iterator not"
2125 " referring to this unordered container");
2127 __node_holder __h = __construct_node(__x);
2128 iterator __r = __node_insert_multi(__p, __h.get());
2133 #endif // _LIBCPP_CXX03_LANG
2135 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2137 __hash_table<_Tp, _Hash, _Equal, _Alloc>::rehash(size_type __n)
2141 else if (__n & (__n - 1))
2142 __n = __next_prime(__n);
2143 size_type __bc = bucket_count();
2146 else if (__n < __bc)
2148 __n = _VSTD::max<size_type>
2151 __is_hash_power2(__bc) ? __next_hash_pow2(size_t(ceil(float(size()) / max_load_factor()))) :
2152 __next_prime(size_t(ceil(float(size()) / max_load_factor())))
2159 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2161 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__rehash(size_type __nbc)
2163 #if _LIBCPP_DEBUG_LEVEL >= 2
2164 __get_db()->__invalidate_all(this);
2165 #endif // _LIBCPP_DEBUG_LEVEL >= 2
2166 __pointer_allocator& __npa = __bucket_list_.get_deleter().__alloc();
2167 __bucket_list_.reset(__nbc > 0 ?
2168 __pointer_alloc_traits::allocate(__npa, __nbc) : nullptr);
2169 __bucket_list_.get_deleter().size() = __nbc;
2172 for (size_type __i = 0; __i < __nbc; ++__i)
2173 __bucket_list_[__i] = nullptr;
2174 __next_pointer __pp = __p1_.first().__ptr();
2175 __next_pointer __cp = __pp->__next_;
2176 if (__cp != nullptr)
2178 size_type __chash = __constrain_hash(__cp->__hash(), __nbc);
2179 __bucket_list_[__chash] = __pp;
2180 size_type __phash = __chash;
2181 for (__pp = __cp, __cp = __cp->__next_; __cp != nullptr;
2182 __cp = __pp->__next_)
2184 __chash = __constrain_hash(__cp->__hash(), __nbc);
2185 if (__chash == __phash)
2189 if (__bucket_list_[__chash] == nullptr)
2191 __bucket_list_[__chash] = __pp;
2197 __next_pointer __np = __cp;
2198 for (; __np->__next_ != nullptr &&
2199 key_eq()(__cp->__upcast()->__value_,
2200 __np->__next_->__upcast()->__value_);
2201 __np = __np->__next_)
2203 __pp->__next_ = __np->__next_;
2204 __np->__next_ = __bucket_list_[__chash]->__next_;
2205 __bucket_list_[__chash]->__next_ = __cp;
2214 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2215 template <class _Key>
2216 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
2217 __hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k)
2219 size_t __hash = hash_function()(__k);
2220 size_type __bc = bucket_count();
2223 size_t __chash = __constrain_hash(__hash, __bc);
2224 __next_pointer __nd = __bucket_list_[__chash];
2225 if (__nd != nullptr)
2227 for (__nd = __nd->__next_; __nd != nullptr &&
2228 (__nd->__hash() == __hash
2229 || __constrain_hash(__nd->__hash(), __bc) == __chash);
2230 __nd = __nd->__next_)
2232 if ((__nd->__hash() == __hash)
2233 && key_eq()(__nd->__upcast()->__value_, __k))
2234 #if _LIBCPP_DEBUG_LEVEL >= 2
2235 return iterator(__nd, this);
2237 return iterator(__nd);
2245 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2246 template <class _Key>
2247 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator
2248 __hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) const
2250 size_t __hash = hash_function()(__k);
2251 size_type __bc = bucket_count();
2254 size_t __chash = __constrain_hash(__hash, __bc);
2255 __next_pointer __nd = __bucket_list_[__chash];
2256 if (__nd != nullptr)
2258 for (__nd = __nd->__next_; __nd != nullptr &&
2259 (__hash == __nd->__hash()
2260 || __constrain_hash(__nd->__hash(), __bc) == __chash);
2261 __nd = __nd->__next_)
2263 if ((__nd->__hash() == __hash)
2264 && key_eq()(__nd->__upcast()->__value_, __k))
2265 #if _LIBCPP_DEBUG_LEVEL >= 2
2266 return const_iterator(__nd, this);
2268 return const_iterator(__nd);
2277 #ifndef _LIBCPP_CXX03_LANG
2279 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2280 template <class ..._Args>
2281 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
2282 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(_Args&& ...__args)
2284 static_assert(!__is_hash_value_type<_Args...>::value,
2285 "Construct cannot be called with a hash value type");
2286 __node_allocator& __na = __node_alloc();
2287 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
2288 __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__value_), _VSTD::forward<_Args>(__args)...);
2289 __h.get_deleter().__value_constructed = true;
2290 __h->__hash_ = hash_function()(__h->__value_);
2291 __h->__next_ = nullptr;
2295 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2296 template <class _First, class ..._Rest>
2297 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
2298 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node_hash(
2299 size_t __hash, _First&& __f, _Rest&& ...__rest)
2301 static_assert(!__is_hash_value_type<_First, _Rest...>::value,
2302 "Construct cannot be called with a hash value type");
2303 __node_allocator& __na = __node_alloc();
2304 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
2305 __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__value_),
2306 _VSTD::forward<_First>(__f),
2307 _VSTD::forward<_Rest>(__rest)...);
2308 __h.get_deleter().__value_constructed = true;
2309 __h->__hash_ = __hash;
2310 __h->__next_ = nullptr;
2314 #else // _LIBCPP_CXX03_LANG
2316 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2317 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
2318 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(const __container_value_type& __v)
2320 __node_allocator& __na = __node_alloc();
2321 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
2322 __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__value_), __v);
2323 __h.get_deleter().__value_constructed = true;
2324 __h->__hash_ = hash_function()(__h->__value_);
2325 __h->__next_ = nullptr;
2326 return _LIBCPP_EXPLICIT_MOVE(__h); // explicitly moved for C++03
2329 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2330 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
2331 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node_hash(size_t __hash,
2332 const __container_value_type& __v)
2334 __node_allocator& __na = __node_alloc();
2335 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
2336 __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__value_), __v);
2337 __h.get_deleter().__value_constructed = true;
2338 __h->__hash_ = __hash;
2339 __h->__next_ = nullptr;
2340 return _LIBCPP_EXPLICIT_MOVE(__h); // explicitly moved for C++03
2343 #endif // _LIBCPP_CXX03_LANG
2345 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2346 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
2347 __hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __p)
2349 __next_pointer __np = __p.__node_;
2350 #if _LIBCPP_DEBUG_LEVEL >= 2
2351 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
2352 "unordered container erase(iterator) called with an iterator not"
2353 " referring to this container");
2354 _LIBCPP_ASSERT(__p != end(),
2355 "unordered container erase(iterator) called with a non-dereferenceable iterator");
2356 iterator __r(__np, this);
2365 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2366 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
2367 __hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __first,
2368 const_iterator __last)
2370 #if _LIBCPP_DEBUG_LEVEL >= 2
2371 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__first) == this,
2372 "unodered container::erase(iterator, iterator) called with an iterator not"
2373 " referring to this unodered container");
2374 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__last) == this,
2375 "unodered container::erase(iterator, iterator) called with an iterator not"
2376 " referring to this unodered container");
2378 for (const_iterator __p = __first; __first != __last; __p = __first)
2383 __next_pointer __np = __last.__node_;
2384 #if _LIBCPP_DEBUG_LEVEL >= 2
2385 return iterator (__np, this);
2387 return iterator (__np);
2391 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2392 template <class _Key>
2393 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
2394 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_unique(const _Key& __k)
2396 iterator __i = find(__k);
2403 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2404 template <class _Key>
2405 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
2406 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_multi(const _Key& __k)
2409 iterator __i = find(__k);
2412 iterator __e = end();
2417 } while (__i != __e && key_eq()(*__i, __k));
2422 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2423 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
2424 __hash_table<_Tp, _Hash, _Equal, _Alloc>::remove(const_iterator __p) _NOEXCEPT
2427 __next_pointer __cn = __p.__node_;
2428 size_type __bc = bucket_count();
2429 size_t __chash = __constrain_hash(__cn->__hash(), __bc);
2430 // find previous node
2431 __next_pointer __pn = __bucket_list_[__chash];
2432 for (; __pn->__next_ != __cn; __pn = __pn->__next_)
2434 // Fix up __bucket_list_
2435 // if __pn is not in same bucket (before begin is not in same bucket) &&
2436 // if __cn->__next_ is not in same bucket (nullptr is not in same bucket)
2437 if (__pn == __p1_.first().__ptr()
2438 || __constrain_hash(__pn->__hash(), __bc) != __chash)
2440 if (__cn->__next_ == nullptr
2441 || __constrain_hash(__cn->__next_->__hash(), __bc) != __chash)
2442 __bucket_list_[__chash] = nullptr;
2444 // if __cn->__next_ is not in same bucket (nullptr is in same bucket)
2445 if (__cn->__next_ != nullptr)
2447 size_t __nhash = __constrain_hash(__cn->__next_->__hash(), __bc);
2448 if (__nhash != __chash)
2449 __bucket_list_[__nhash] = __pn;
2452 __pn->__next_ = __cn->__next_;
2453 __cn->__next_ = nullptr;
2455 #if _LIBCPP_DEBUG_LEVEL >= 2
2456 __c_node* __c = __get_db()->__find_c_and_lock(this);
2457 for (__i_node** __dp = __c->end_; __dp != __c->beg_; )
2460 iterator* __i = static_cast<iterator*>((*__dp)->__i_);
2461 if (__i->__node_ == __cn)
2463 (*__dp)->__c_ = nullptr;
2464 if (--__c->end_ != __dp)
2465 memmove(__dp, __dp+1, (__c->end_ - __dp)*sizeof(__i_node*));
2468 __get_db()->unlock();
2470 return __node_holder(__cn->__upcast(), _Dp(__node_alloc(), true));
2473 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2474 template <class _Key>
2476 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
2477 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_unique(const _Key& __k) const
2479 return static_cast<size_type>(find(__k) != end());
2482 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2483 template <class _Key>
2484 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
2485 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_multi(const _Key& __k) const
2488 const_iterator __i = find(__k);
2491 const_iterator __e = end();
2496 } while (__i != __e && key_eq()(*__i, __k));
2501 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2502 template <class _Key>
2503 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator,
2504 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator>
2505 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique(
2508 iterator __i = find(__k);
2512 return pair<iterator, iterator>(__i, __j);
2515 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2516 template <class _Key>
2517 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator,
2518 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator>
2519 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique(
2520 const _Key& __k) const
2522 const_iterator __i = find(__k);
2523 const_iterator __j = __i;
2526 return pair<const_iterator, const_iterator>(__i, __j);
2529 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2530 template <class _Key>
2531 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator,
2532 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator>
2533 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi(
2536 iterator __i = find(__k);
2540 iterator __e = end();
2544 } while (__j != __e && key_eq()(*__j, __k));
2546 return pair<iterator, iterator>(__i, __j);
2549 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2550 template <class _Key>
2551 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator,
2552 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator>
2553 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi(
2554 const _Key& __k) const
2556 const_iterator __i = find(__k);
2557 const_iterator __j = __i;
2560 const_iterator __e = end();
2564 } while (__j != __e && key_eq()(*__j, __k));
2566 return pair<const_iterator, const_iterator>(__i, __j);
2569 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2571 __hash_table<_Tp, _Hash, _Equal, _Alloc>::swap(__hash_table& __u)
2572 #if _LIBCPP_STD_VER <= 11
2574 __is_nothrow_swappable<hasher>::value && __is_nothrow_swappable<key_equal>::value
2575 && (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value
2576 || __is_nothrow_swappable<__pointer_allocator>::value)
2577 && (!__node_traits::propagate_on_container_swap::value
2578 || __is_nothrow_swappable<__node_allocator>::value)
2581 _NOEXCEPT_DEBUG_(__is_nothrow_swappable<hasher>::value && __is_nothrow_swappable<key_equal>::value)
2584 _LIBCPP_ASSERT(__node_traits::propagate_on_container_swap::value ||
2585 this->__node_alloc() == __u.__node_alloc(),
2586 "list::swap: Either propagate_on_container_swap must be true"
2587 " or the allocators must compare equal");
2589 __node_pointer_pointer __npp = __bucket_list_.release();
2590 __bucket_list_.reset(__u.__bucket_list_.release());
2591 __u.__bucket_list_.reset(__npp);
2593 _VSTD::swap(__bucket_list_.get_deleter().size(), __u.__bucket_list_.get_deleter().size());
2594 __swap_allocator(__bucket_list_.get_deleter().__alloc(),
2595 __u.__bucket_list_.get_deleter().__alloc());
2596 __swap_allocator(__node_alloc(), __u.__node_alloc());
2597 _VSTD::swap(__p1_.first().__next_, __u.__p1_.first().__next_);
2598 __p2_.swap(__u.__p2_);
2599 __p3_.swap(__u.__p3_);
2601 __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash(), bucket_count())] =
2602 __p1_.first().__ptr();
2604 __u.__bucket_list_[__constrain_hash(__u.__p1_.first().__next_->__hash(), __u.bucket_count())] =
2605 __u.__p1_.first().__ptr();
2606 #if _LIBCPP_DEBUG_LEVEL >= 2
2607 __get_db()->swap(this, &__u);
2611 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2612 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
2613 __hash_table<_Tp, _Hash, _Equal, _Alloc>::bucket_size(size_type __n) const
2615 _LIBCPP_ASSERT(__n < bucket_count(),
2616 "unordered container::bucket_size(n) called with n >= bucket_count()");
2617 __next_pointer __np = __bucket_list_[__n];
2618 size_type __bc = bucket_count();
2620 if (__np != nullptr)
2622 for (__np = __np->__next_; __np != nullptr &&
2623 __constrain_hash(__np->__hash(), __bc) == __n;
2624 __np = __np->__next_, ++__r)
2630 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2631 inline _LIBCPP_INLINE_VISIBILITY
2633 swap(__hash_table<_Tp, _Hash, _Equal, _Alloc>& __x,
2634 __hash_table<_Tp, _Hash, _Equal, _Alloc>& __y)
2635 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
2640 #if _LIBCPP_DEBUG_LEVEL >= 2
2642 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2644 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__dereferenceable(const const_iterator* __i) const
2646 return __i->__node_ != nullptr;
2649 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2651 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__decrementable(const const_iterator*) const
2656 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2658 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__addable(const const_iterator*, ptrdiff_t) const
2663 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2665 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__subscriptable(const const_iterator*, ptrdiff_t) const
2670 #endif // _LIBCPP_DEBUG_LEVEL >= 2
2672 _LIBCPP_END_NAMESPACE_STD
2676 #endif // _LIBCPP__HASH_TABLE