2 //===----------------------------------------------------------------------===//
4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5 // See https://llvm.org/LICENSE.txt for license information.
6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
8 //===----------------------------------------------------------------------===//
10 #ifndef _LIBCPP___HASH_TABLE
11 #define _LIBCPP___HASH_TABLE
13 #include <__algorithm/max.h>
14 #include <__algorithm/min.h>
16 #include <__bit/countl.h>
18 #include <__cstddef/ptrdiff_t.h>
19 #include <__functional/hash.h>
20 #include <__iterator/iterator_traits.h>
21 #include <__math/rounding_functions.h>
22 #include <__memory/addressof.h>
23 #include <__memory/allocator_traits.h>
24 #include <__memory/compressed_pair.h>
25 #include <__memory/construct_at.h>
26 #include <__memory/pointer_traits.h>
27 #include <__memory/swap_allocator.h>
28 #include <__memory/unique_ptr.h>
29 #include <__type_traits/can_extract_key.h>
30 #include <__type_traits/conditional.h>
31 #include <__type_traits/enable_if.h>
32 #include <__type_traits/invoke.h>
33 #include <__type_traits/is_const.h>
34 #include <__type_traits/is_constructible.h>
35 #include <__type_traits/is_nothrow_assignable.h>
36 #include <__type_traits/is_nothrow_constructible.h>
37 #include <__type_traits/is_pointer.h>
38 #include <__type_traits/is_reference.h>
39 #include <__type_traits/is_same.h>
40 #include <__type_traits/is_swappable.h>
41 #include <__type_traits/remove_const.h>
42 #include <__type_traits/remove_cvref.h>
43 #include <__utility/forward.h>
44 #include <__utility/move.h>
45 #include <__utility/pair.h>
46 #include <__utility/swap.h>
49 #include <new> // __launder
51 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
52 # pragma GCC system_header
56 #include <__undef_macros>
58 _LIBCPP_BEGIN_NAMESPACE_STD
60 template <class _Key, class _Tp>
61 struct __hash_value_type;
64 struct __is_hash_value_type_imp : false_type {};
66 template <class _Key, class _Value>
67 struct __is_hash_value_type_imp<__hash_value_type<_Key, _Value> > : true_type {};
69 template <class... _Args>
70 struct __is_hash_value_type : false_type {};
73 struct __is_hash_value_type<_One> : __is_hash_value_type_imp<__remove_cvref_t<_One> > {};
75 _LIBCPP_EXPORTED_FROM_ABI size_t __next_prime(size_t __n);
77 template <class _NodePtr>
78 struct __hash_node_base {
79 typedef typename pointer_traits<_NodePtr>::element_type __node_type;
80 typedef __hash_node_base __first_node;
81 typedef __rebind_pointer_t<_NodePtr, __first_node> __node_base_pointer;
82 typedef _NodePtr __node_pointer;
83 typedef __node_base_pointer __next_pointer;
85 // TODO(LLVM 22): Remove this check
86 #ifndef _LIBCPP_ABI_FIX_UNORDERED_NODE_POINTER_UB
87 static_assert(sizeof(__node_base_pointer) == sizeof(__node_pointer) && _LIBCPP_ALIGNOF(__node_base_pointer) ==
88 _LIBCPP_ALIGNOF(__node_pointer),
89 "It looks like you are using std::__hash_table (an implementation detail for the unordered containers) "
90 "with a fancy pointer type that thas a different representation depending on whether it points to a "
91 "__hash_table base pointer or a __hash_table node pointer (both of which are implementation details of "
92 "the standard library). This means that your ABI is being broken between LLVM 19 and LLVM 20. If you "
93 "don't care about your ABI being broken, define the _LIBCPP_ABI_TREE_REMOVE_NODE_POINTER_UB macro to "
94 "silence this diagnostic.");
97 __next_pointer __next_;
99 _LIBCPP_HIDE_FROM_ABI __next_pointer __ptr() _NOEXCEPT {
100 return static_cast<__next_pointer>(pointer_traits<__node_base_pointer>::pointer_to(*this));
103 _LIBCPP_HIDE_FROM_ABI __node_pointer __upcast() _NOEXCEPT {
104 return static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(*this));
107 _LIBCPP_HIDE_FROM_ABI size_t __hash() const _NOEXCEPT { return static_cast<__node_type const&>(*this).__hash_; }
109 _LIBCPP_HIDE_FROM_ABI __hash_node_base() _NOEXCEPT : __next_(nullptr) {}
110 _LIBCPP_HIDE_FROM_ABI explicit __hash_node_base(__next_pointer __next) _NOEXCEPT : __next_(__next) {}
113 template <class _Tp, class _VoidPtr>
114 struct __hash_node : public __hash_node_base< __rebind_pointer_t<_VoidPtr, __hash_node<_Tp, _VoidPtr> > > {
115 typedef _Tp __node_value_type;
116 using _Base = __hash_node_base<__rebind_pointer_t<_VoidPtr, __hash_node<_Tp, _VoidPtr> > >;
117 using __next_pointer = typename _Base::__next_pointer;
121 // We allow starting the lifetime of nodes without initializing the value held by the node,
122 // since that is handled by the hash table itself in order to be allocator-aware.
123 #ifndef _LIBCPP_CXX03_LANG
131 _LIBCPP_HIDE_FROM_ABI _Tp& __get_value() { return __value_; }
135 _ALIGNAS_TYPE(_Tp) char __buffer_[sizeof(_Tp)];
138 _LIBCPP_HIDE_FROM_ABI _Tp& __get_value() { return *std::__launder(reinterpret_cast<_Tp*>(&__buffer_)); }
141 _LIBCPP_HIDE_FROM_ABI explicit __hash_node(__next_pointer __next, size_t __hash) : _Base(__next), __hash_(__hash) {}
142 _LIBCPP_HIDE_FROM_ABI ~__hash_node() {}
145 inline _LIBCPP_HIDE_FROM_ABI bool __is_hash_power2(size_t __bc) { return __bc > 2 && !(__bc & (__bc - 1)); }
147 inline _LIBCPP_HIDE_FROM_ABI size_t __constrain_hash(size_t __h, size_t __bc) {
148 return !(__bc & (__bc - 1)) ? __h & (__bc - 1) : (__h < __bc ? __h : __h % __bc);
151 inline _LIBCPP_HIDE_FROM_ABI size_t __next_hash_pow2(size_t __n) {
152 return __n < 2 ? __n : (size_t(1) << (numeric_limits<size_t>::digits - __libcpp_clz(__n - 1)));
155 template <class _Tp, class _Hash, class _Equal, class _Alloc>
158 template <class _NodePtr>
159 class _LIBCPP_TEMPLATE_VIS __hash_iterator;
160 template <class _ConstNodePtr>
161 class _LIBCPP_TEMPLATE_VIS __hash_const_iterator;
162 template <class _NodePtr>
163 class _LIBCPP_TEMPLATE_VIS __hash_local_iterator;
164 template <class _ConstNodePtr>
165 class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator;
166 template <class _HashIterator>
167 class _LIBCPP_TEMPLATE_VIS __hash_map_iterator;
168 template <class _HashIterator>
169 class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator;
172 struct __hash_key_value_types {
173 static_assert(!is_reference<_Tp>::value && !is_const<_Tp>::value, "");
174 typedef _Tp key_type;
175 typedef _Tp __node_value_type;
176 typedef _Tp __container_value_type;
177 static const bool __is_map = false;
179 _LIBCPP_HIDE_FROM_ABI static key_type const& __get_key(_Tp const& __v) { return __v; }
180 _LIBCPP_HIDE_FROM_ABI static __container_value_type const& __get_value(__node_value_type const& __v) { return __v; }
181 _LIBCPP_HIDE_FROM_ABI static __container_value_type* __get_ptr(__node_value_type& __n) { return std::addressof(__n); }
182 _LIBCPP_HIDE_FROM_ABI static __container_value_type&& __move(__node_value_type& __v) { return std::move(__v); }
185 template <class _Key, class _Tp>
186 struct __hash_key_value_types<__hash_value_type<_Key, _Tp> > {
187 typedef _Key key_type;
188 typedef _Tp mapped_type;
189 typedef __hash_value_type<_Key, _Tp> __node_value_type;
190 typedef pair<const _Key, _Tp> __container_value_type;
191 typedef __container_value_type __map_value_type;
192 static const bool __is_map = true;
194 _LIBCPP_HIDE_FROM_ABI static key_type const& __get_key(__container_value_type const& __v) { return __v.first; }
196 template <class _Up, __enable_if_t<__is_same_uncvref<_Up, __node_value_type>::value, int> = 0>
197 _LIBCPP_HIDE_FROM_ABI static __container_value_type const& __get_value(_Up& __t) {
198 return __t.__get_value();
201 template <class _Up, __enable_if_t<__is_same_uncvref<_Up, __container_value_type>::value, int> = 0>
202 _LIBCPP_HIDE_FROM_ABI static __container_value_type const& __get_value(_Up& __t) {
206 _LIBCPP_HIDE_FROM_ABI static __container_value_type* __get_ptr(__node_value_type& __n) {
207 return std::addressof(__n.__get_value());
209 _LIBCPP_HIDE_FROM_ABI static pair<key_type&&, mapped_type&&> __move(__node_value_type& __v) { return __v.__move(); }
212 template <class _Tp, class _AllocPtr, class _KVTypes = __hash_key_value_types<_Tp>, bool = _KVTypes::__is_map>
213 struct __hash_map_pointer_types {};
215 template <class _Tp, class _AllocPtr, class _KVTypes>
216 struct __hash_map_pointer_types<_Tp, _AllocPtr, _KVTypes, true> {
217 typedef typename _KVTypes::__map_value_type _Mv;
218 typedef __rebind_pointer_t<_AllocPtr, _Mv> __map_value_type_pointer;
219 typedef __rebind_pointer_t<_AllocPtr, const _Mv> __const_map_value_type_pointer;
222 template <class _NodePtr, class _NodeT = typename pointer_traits<_NodePtr>::element_type>
223 struct __hash_node_types;
225 template <class _NodePtr, class _Tp, class _VoidPtr>
226 struct __hash_node_types<_NodePtr, __hash_node<_Tp, _VoidPtr> >
227 : public __hash_key_value_types<_Tp>,
228 __hash_map_pointer_types<_Tp, _VoidPtr>
231 typedef __hash_key_value_types<_Tp> __base;
234 typedef ptrdiff_t difference_type;
235 typedef size_t size_type;
237 typedef __rebind_pointer_t<_NodePtr, void> __void_pointer;
239 typedef typename pointer_traits<_NodePtr>::element_type __node_type;
240 typedef _NodePtr __node_pointer;
242 typedef __hash_node_base<__node_pointer> __node_base_type;
243 typedef __rebind_pointer_t<_NodePtr, __node_base_type> __node_base_pointer;
245 typedef typename __node_base_type::__next_pointer __next_pointer;
247 typedef _Tp __node_value_type;
248 typedef __rebind_pointer_t<_VoidPtr, __node_value_type> __node_value_type_pointer;
249 typedef __rebind_pointer_t<_VoidPtr, const __node_value_type> __const_node_value_type_pointer;
252 static_assert(!is_const<__node_type>::value, "_NodePtr should never be a pointer to const");
253 static_assert(is_same<typename pointer_traits<_VoidPtr>::element_type, void>::value,
254 "_VoidPtr does not point to unqualified void type");
255 static_assert(is_same<__rebind_pointer_t<_VoidPtr, __node_type>, _NodePtr>::value,
256 "_VoidPtr does not rebind to _NodePtr.");
259 template <class _HashIterator>
260 struct __hash_node_types_from_iterator;
261 template <class _NodePtr>
262 struct __hash_node_types_from_iterator<__hash_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {};
263 template <class _NodePtr>
264 struct __hash_node_types_from_iterator<__hash_const_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {};
265 template <class _NodePtr>
266 struct __hash_node_types_from_iterator<__hash_local_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {};
267 template <class _NodePtr>
268 struct __hash_node_types_from_iterator<__hash_const_local_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {};
270 template <class _NodeValueTp, class _VoidPtr>
271 struct __make_hash_node_types {
272 typedef __hash_node<_NodeValueTp, _VoidPtr> _NodeTp;
273 typedef __rebind_pointer_t<_VoidPtr, _NodeTp> _NodePtr;
274 typedef __hash_node_types<_NodePtr> type;
277 template <class _NodePtr>
278 class _LIBCPP_TEMPLATE_VIS __hash_iterator {
279 typedef __hash_node_types<_NodePtr> _NodeTypes;
280 typedef _NodePtr __node_pointer;
281 typedef typename _NodeTypes::__next_pointer __next_pointer;
283 __next_pointer __node_;
286 typedef forward_iterator_tag iterator_category;
287 typedef typename _NodeTypes::__node_value_type value_type;
288 typedef typename _NodeTypes::difference_type difference_type;
289 typedef value_type& reference;
290 typedef typename _NodeTypes::__node_value_type_pointer pointer;
292 _LIBCPP_HIDE_FROM_ABI __hash_iterator() _NOEXCEPT : __node_(nullptr) {}
294 _LIBCPP_HIDE_FROM_ABI reference operator*() const {
295 _LIBCPP_ASSERT_NON_NULL(
296 __node_ != nullptr, "Attempted to dereference a non-dereferenceable unordered container iterator");
297 return __node_->__upcast()->__get_value();
300 _LIBCPP_HIDE_FROM_ABI pointer operator->() const {
301 _LIBCPP_ASSERT_NON_NULL(
302 __node_ != nullptr, "Attempted to dereference a non-dereferenceable unordered container iterator");
303 return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__get_value());
306 _LIBCPP_HIDE_FROM_ABI __hash_iterator& operator++() {
307 _LIBCPP_ASSERT_NON_NULL(
308 __node_ != nullptr, "Attempted to increment a non-incrementable unordered container iterator");
309 __node_ = __node_->__next_;
313 _LIBCPP_HIDE_FROM_ABI __hash_iterator operator++(int) {
314 __hash_iterator __t(*this);
319 friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __hash_iterator& __x, const __hash_iterator& __y) {
320 return __x.__node_ == __y.__node_;
322 friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __hash_iterator& __x, const __hash_iterator& __y) {
323 return !(__x == __y);
327 _LIBCPP_HIDE_FROM_ABI explicit __hash_iterator(__next_pointer __node) _NOEXCEPT : __node_(__node) {}
329 template <class, class, class, class>
330 friend class __hash_table;
332 friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator;
334 friend class _LIBCPP_TEMPLATE_VIS __hash_map_iterator;
335 template <class, class, class, class, class>
336 friend class _LIBCPP_TEMPLATE_VIS unordered_map;
337 template <class, class, class, class, class>
338 friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
341 template <class _NodePtr>
342 class _LIBCPP_TEMPLATE_VIS __hash_const_iterator {
343 static_assert(!is_const<typename pointer_traits<_NodePtr>::element_type>::value, "");
344 typedef __hash_node_types<_NodePtr> _NodeTypes;
345 typedef _NodePtr __node_pointer;
346 typedef typename _NodeTypes::__next_pointer __next_pointer;
348 __next_pointer __node_;
351 typedef __hash_iterator<_NodePtr> __non_const_iterator;
353 typedef forward_iterator_tag iterator_category;
354 typedef typename _NodeTypes::__node_value_type value_type;
355 typedef typename _NodeTypes::difference_type difference_type;
356 typedef const value_type& reference;
357 typedef typename _NodeTypes::__const_node_value_type_pointer pointer;
359 _LIBCPP_HIDE_FROM_ABI __hash_const_iterator() _NOEXCEPT : __node_(nullptr) {}
361 _LIBCPP_HIDE_FROM_ABI __hash_const_iterator(const __non_const_iterator& __x) _NOEXCEPT : __node_(__x.__node_) {}
363 _LIBCPP_HIDE_FROM_ABI reference operator*() const {
364 _LIBCPP_ASSERT_NON_NULL(
365 __node_ != nullptr, "Attempted to dereference a non-dereferenceable unordered container const_iterator");
366 return __node_->__upcast()->__get_value();
368 _LIBCPP_HIDE_FROM_ABI pointer operator->() const {
369 _LIBCPP_ASSERT_NON_NULL(
370 __node_ != nullptr, "Attempted to dereference a non-dereferenceable unordered container const_iterator");
371 return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__get_value());
374 _LIBCPP_HIDE_FROM_ABI __hash_const_iterator& operator++() {
375 _LIBCPP_ASSERT_NON_NULL(
376 __node_ != nullptr, "Attempted to increment a non-incrementable unordered container const_iterator");
377 __node_ = __node_->__next_;
381 _LIBCPP_HIDE_FROM_ABI __hash_const_iterator operator++(int) {
382 __hash_const_iterator __t(*this);
387 friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __hash_const_iterator& __x, const __hash_const_iterator& __y) {
388 return __x.__node_ == __y.__node_;
390 friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __hash_const_iterator& __x, const __hash_const_iterator& __y) {
391 return !(__x == __y);
395 _LIBCPP_HIDE_FROM_ABI explicit __hash_const_iterator(__next_pointer __node) _NOEXCEPT : __node_(__node) {}
397 template <class, class, class, class>
398 friend class __hash_table;
400 friend class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator;
401 template <class, class, class, class, class>
402 friend class _LIBCPP_TEMPLATE_VIS unordered_map;
403 template <class, class, class, class, class>
404 friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
407 template <class _NodePtr>
408 class _LIBCPP_TEMPLATE_VIS __hash_local_iterator {
409 typedef __hash_node_types<_NodePtr> _NodeTypes;
410 typedef _NodePtr __node_pointer;
411 typedef typename _NodeTypes::__next_pointer __next_pointer;
413 __next_pointer __node_;
415 size_t __bucket_count_;
418 typedef forward_iterator_tag iterator_category;
419 typedef typename _NodeTypes::__node_value_type value_type;
420 typedef typename _NodeTypes::difference_type difference_type;
421 typedef value_type& reference;
422 typedef typename _NodeTypes::__node_value_type_pointer pointer;
424 _LIBCPP_HIDE_FROM_ABI __hash_local_iterator() _NOEXCEPT : __node_(nullptr) {}
426 _LIBCPP_HIDE_FROM_ABI reference operator*() const {
427 _LIBCPP_ASSERT_NON_NULL(
428 __node_ != nullptr, "Attempted to dereference a non-dereferenceable unordered container local_iterator");
429 return __node_->__upcast()->__get_value();
432 _LIBCPP_HIDE_FROM_ABI pointer operator->() const {
433 _LIBCPP_ASSERT_NON_NULL(
434 __node_ != nullptr, "Attempted to dereference a non-dereferenceable unordered container local_iterator");
435 return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__get_value());
438 _LIBCPP_HIDE_FROM_ABI __hash_local_iterator& operator++() {
439 _LIBCPP_ASSERT_NON_NULL(
440 __node_ != nullptr, "Attempted to increment a non-incrementable unordered container local_iterator");
441 __node_ = __node_->__next_;
442 if (__node_ != nullptr && std::__constrain_hash(__node_->__hash(), __bucket_count_) != __bucket_)
447 _LIBCPP_HIDE_FROM_ABI __hash_local_iterator operator++(int) {
448 __hash_local_iterator __t(*this);
453 friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __hash_local_iterator& __x, const __hash_local_iterator& __y) {
454 return __x.__node_ == __y.__node_;
456 friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __hash_local_iterator& __x, const __hash_local_iterator& __y) {
457 return !(__x == __y);
461 _LIBCPP_HIDE_FROM_ABI explicit __hash_local_iterator(
462 __next_pointer __node, size_t __bucket, size_t __bucket_count) _NOEXCEPT
465 __bucket_count_(__bucket_count) {
466 if (__node_ != nullptr)
467 __node_ = __node_->__next_;
470 template <class, class, class, class>
471 friend class __hash_table;
473 friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator;
475 friend class _LIBCPP_TEMPLATE_VIS __hash_map_iterator;
478 template <class _ConstNodePtr>
479 class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator {
480 typedef __hash_node_types<_ConstNodePtr> _NodeTypes;
481 typedef _ConstNodePtr __node_pointer;
482 typedef typename _NodeTypes::__next_pointer __next_pointer;
484 __next_pointer __node_;
486 size_t __bucket_count_;
488 typedef pointer_traits<__node_pointer> __pointer_traits;
489 typedef typename __pointer_traits::element_type __node;
490 typedef __remove_const_t<__node> __non_const_node;
491 typedef __rebind_pointer_t<__node_pointer, __non_const_node> __non_const_node_pointer;
494 typedef __hash_local_iterator<__non_const_node_pointer> __non_const_iterator;
496 typedef forward_iterator_tag iterator_category;
497 typedef typename _NodeTypes::__node_value_type value_type;
498 typedef typename _NodeTypes::difference_type difference_type;
499 typedef const value_type& reference;
500 typedef typename _NodeTypes::__const_node_value_type_pointer pointer;
502 _LIBCPP_HIDE_FROM_ABI __hash_const_local_iterator() _NOEXCEPT : __node_(nullptr) {}
504 _LIBCPP_HIDE_FROM_ABI __hash_const_local_iterator(const __non_const_iterator& __x) _NOEXCEPT
505 : __node_(__x.__node_),
506 __bucket_(__x.__bucket_),
507 __bucket_count_(__x.__bucket_count_) {}
509 _LIBCPP_HIDE_FROM_ABI reference operator*() const {
510 _LIBCPP_ASSERT_NON_NULL(
511 __node_ != nullptr, "Attempted to dereference a non-dereferenceable unordered container const_local_iterator");
512 return __node_->__upcast()->__get_value();
515 _LIBCPP_HIDE_FROM_ABI pointer operator->() const {
516 _LIBCPP_ASSERT_NON_NULL(
517 __node_ != nullptr, "Attempted to dereference a non-dereferenceable unordered container const_local_iterator");
518 return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__get_value());
521 _LIBCPP_HIDE_FROM_ABI __hash_const_local_iterator& operator++() {
522 _LIBCPP_ASSERT_NON_NULL(
523 __node_ != nullptr, "Attempted to increment a non-incrementable unordered container const_local_iterator");
524 __node_ = __node_->__next_;
525 if (__node_ != nullptr && std::__constrain_hash(__node_->__hash(), __bucket_count_) != __bucket_)
530 _LIBCPP_HIDE_FROM_ABI __hash_const_local_iterator operator++(int) {
531 __hash_const_local_iterator __t(*this);
536 friend _LIBCPP_HIDE_FROM_ABI bool
537 operator==(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y) {
538 return __x.__node_ == __y.__node_;
540 friend _LIBCPP_HIDE_FROM_ABI bool
541 operator!=(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y) {
542 return !(__x == __y);
546 _LIBCPP_HIDE_FROM_ABI explicit __hash_const_local_iterator(
547 __next_pointer __node_ptr, size_t __bucket, size_t __bucket_count) _NOEXCEPT
548 : __node_(__node_ptr),
550 __bucket_count_(__bucket_count) {
551 if (__node_ != nullptr)
552 __node_ = __node_->__next_;
555 template <class, class, class, class>
556 friend class __hash_table;
558 friend class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator;
561 template <class _Alloc>
562 class __bucket_list_deallocator {
563 typedef _Alloc allocator_type;
564 typedef allocator_traits<allocator_type> __alloc_traits;
565 typedef typename __alloc_traits::size_type size_type;
567 _LIBCPP_COMPRESSED_PAIR(size_type, __size_, allocator_type, __alloc_);
570 typedef typename __alloc_traits::pointer pointer;
572 _LIBCPP_HIDE_FROM_ABI __bucket_list_deallocator() _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
575 _LIBCPP_HIDE_FROM_ABI __bucket_list_deallocator(const allocator_type& __a, size_type __size)
576 _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value)
577 : __size_(__size), __alloc_(__a) {}
579 _LIBCPP_HIDE_FROM_ABI __bucket_list_deallocator(__bucket_list_deallocator&& __x)
580 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
581 : __size_(std::move(__x.__size_)), __alloc_(std::move(__x.__alloc_)) {
585 _LIBCPP_HIDE_FROM_ABI size_type& size() _NOEXCEPT { return __size_; }
586 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __size_; }
588 _LIBCPP_HIDE_FROM_ABI allocator_type& __alloc() _NOEXCEPT { return __alloc_; }
589 _LIBCPP_HIDE_FROM_ABI const allocator_type& __alloc() const _NOEXCEPT { return __alloc_; }
591 _LIBCPP_HIDE_FROM_ABI void operator()(pointer __p) _NOEXCEPT { __alloc_traits::deallocate(__alloc(), __p, size()); }
594 template <class _Alloc>
595 class __hash_map_node_destructor;
597 template <class _Alloc>
598 class __hash_node_destructor {
599 typedef _Alloc allocator_type;
600 typedef allocator_traits<allocator_type> __alloc_traits;
603 typedef typename __alloc_traits::pointer pointer;
606 typedef __hash_node_types<pointer> _NodeTypes;
608 allocator_type& __na_;
611 bool __value_constructed;
613 _LIBCPP_HIDE_FROM_ABI __hash_node_destructor(__hash_node_destructor const&) = default;
614 _LIBCPP_HIDE_FROM_ABI __hash_node_destructor& operator=(const __hash_node_destructor&) = delete;
616 _LIBCPP_HIDE_FROM_ABI explicit __hash_node_destructor(allocator_type& __na, bool __constructed = false) _NOEXCEPT
618 __value_constructed(__constructed) {}
620 _LIBCPP_HIDE_FROM_ABI void operator()(pointer __p) _NOEXCEPT {
621 if (__value_constructed) {
622 __alloc_traits::destroy(__na_, _NodeTypes::__get_ptr(__p->__get_value()));
623 std::__destroy_at(std::addressof(*__p));
626 __alloc_traits::deallocate(__na_, __p, 1);
630 friend class __hash_map_node_destructor;
633 #if _LIBCPP_STD_VER >= 17
634 template <class _NodeType, class _Alloc>
635 struct __generic_container_node_destructor;
637 template <class _Tp, class _VoidPtr, class _Alloc>
638 struct __generic_container_node_destructor<__hash_node<_Tp, _VoidPtr>, _Alloc> : __hash_node_destructor<_Alloc> {
639 using __hash_node_destructor<_Alloc>::__hash_node_destructor;
643 template <class _Key, class _Hash, class _Equal>
644 struct __enforce_unordered_container_requirements {
645 #ifndef _LIBCPP_CXX03_LANG
646 static_assert(__check_hash_requirements<_Key, _Hash>::value,
647 "the specified hash does not meet the Hash requirements");
648 static_assert(is_copy_constructible<_Equal>::value, "the specified comparator is required to be copy constructible");
653 template <class _Key, class _Hash, class _Equal>
654 #ifndef _LIBCPP_CXX03_LANG
655 _LIBCPP_DIAGNOSE_WARNING(!__invokable<_Equal const&, _Key const&, _Key const&>::value,
656 "the specified comparator type does not provide a viable const call operator")
657 _LIBCPP_DIAGNOSE_WARNING(!__invokable<_Hash const&, _Key const&>::value,
658 "the specified hash functor does not provide a viable const call operator")
660 typename __enforce_unordered_container_requirements<_Key, _Hash, _Equal>::type
661 __diagnose_unordered_container_requirements(int);
663 // This dummy overload is used so that the compiler won't emit a spurious
664 // "no matching function for call to __diagnose_unordered_xxx" diagnostic
665 // when the overload above causes a hard error.
666 template <class _Key, class _Hash, class _Equal>
667 int __diagnose_unordered_container_requirements(void*);
669 template <class _Tp, class _Hash, class _Equal, class _Alloc>
672 typedef _Tp value_type;
673 typedef _Hash hasher;
674 typedef _Equal key_equal;
675 typedef _Alloc allocator_type;
678 typedef allocator_traits<allocator_type> __alloc_traits;
679 typedef typename __make_hash_node_types<value_type, typename __alloc_traits::void_pointer>::type _NodeTypes;
682 typedef typename _NodeTypes::__node_value_type __node_value_type;
683 typedef typename _NodeTypes::__container_value_type __container_value_type;
684 typedef typename _NodeTypes::key_type key_type;
685 typedef value_type& reference;
686 typedef const value_type& const_reference;
687 typedef typename __alloc_traits::pointer pointer;
688 typedef typename __alloc_traits::const_pointer const_pointer;
689 #ifndef _LIBCPP_ABI_FIX_UNORDERED_CONTAINER_SIZE_TYPE
690 typedef typename __alloc_traits::size_type size_type;
692 typedef typename _NodeTypes::size_type size_type;
694 typedef typename _NodeTypes::difference_type difference_type;
699 typedef typename _NodeTypes::__node_type __node;
700 typedef __rebind_alloc<__alloc_traits, __node> __node_allocator;
701 typedef allocator_traits<__node_allocator> __node_traits;
702 typedef typename _NodeTypes::__void_pointer __void_pointer;
703 typedef typename _NodeTypes::__node_pointer __node_pointer;
704 typedef typename _NodeTypes::__node_pointer __node_const_pointer;
705 typedef typename _NodeTypes::__node_base_type __first_node;
706 typedef typename _NodeTypes::__node_base_pointer __node_base_pointer;
707 typedef typename _NodeTypes::__next_pointer __next_pointer;
710 // check for sane allocator pointer rebinding semantics. Rebinding the
711 // allocator for a new pointer type should be exactly the same as rebinding
712 // the pointer using 'pointer_traits'.
713 static_assert(is_same<__node_pointer, typename __node_traits::pointer>::value,
714 "Allocator does not rebind pointers in a sane manner.");
715 typedef __rebind_alloc<__node_traits, __first_node> __node_base_allocator;
716 typedef allocator_traits<__node_base_allocator> __node_base_traits;
717 static_assert(is_same<__node_base_pointer, typename __node_base_traits::pointer>::value,
718 "Allocator does not rebind pointers in a sane manner.");
721 typedef __rebind_alloc<__node_traits, __next_pointer> __pointer_allocator;
722 typedef __bucket_list_deallocator<__pointer_allocator> __bucket_list_deleter;
723 typedef unique_ptr<__next_pointer[], __bucket_list_deleter> __bucket_list;
724 typedef allocator_traits<__pointer_allocator> __pointer_alloc_traits;
725 typedef typename __bucket_list_deleter::pointer __node_pointer_pointer;
727 // --- Member data begin ---
728 __bucket_list __bucket_list_;
729 _LIBCPP_COMPRESSED_PAIR(__first_node, __first_node_, __node_allocator, __node_alloc_);
730 _LIBCPP_COMPRESSED_PAIR(size_type, __size_, hasher, __hasher_);
731 _LIBCPP_COMPRESSED_PAIR(float, __max_load_factor_, key_equal, __key_eq_);
732 // --- Member data end ---
734 _LIBCPP_HIDE_FROM_ABI size_type& size() _NOEXCEPT { return __size_; }
737 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __size_; }
739 _LIBCPP_HIDE_FROM_ABI hasher& hash_function() _NOEXCEPT { return __hasher_; }
740 _LIBCPP_HIDE_FROM_ABI const hasher& hash_function() const _NOEXCEPT { return __hasher_; }
742 _LIBCPP_HIDE_FROM_ABI float& max_load_factor() _NOEXCEPT { return __max_load_factor_; }
743 _LIBCPP_HIDE_FROM_ABI float max_load_factor() const _NOEXCEPT { return __max_load_factor_; }
745 _LIBCPP_HIDE_FROM_ABI key_equal& key_eq() _NOEXCEPT { return __key_eq_; }
746 _LIBCPP_HIDE_FROM_ABI const key_equal& key_eq() const _NOEXCEPT { return __key_eq_; }
748 _LIBCPP_HIDE_FROM_ABI __node_allocator& __node_alloc() _NOEXCEPT { return __node_alloc_; }
749 _LIBCPP_HIDE_FROM_ABI const __node_allocator& __node_alloc() const _NOEXCEPT { return __node_alloc_; }
752 typedef __hash_iterator<__node_pointer> iterator;
753 typedef __hash_const_iterator<__node_pointer> const_iterator;
754 typedef __hash_local_iterator<__node_pointer> local_iterator;
755 typedef __hash_const_local_iterator<__node_pointer> const_local_iterator;
757 _LIBCPP_HIDE_FROM_ABI __hash_table() _NOEXCEPT_(
758 is_nothrow_default_constructible<__bucket_list>::value&& is_nothrow_default_constructible<__first_node>::value&&
759 is_nothrow_default_constructible<__node_allocator>::value&& is_nothrow_default_constructible<hasher>::value&&
760 is_nothrow_default_constructible<key_equal>::value);
761 _LIBCPP_HIDE_FROM_ABI __hash_table(const hasher& __hf, const key_equal& __eql);
762 _LIBCPP_HIDE_FROM_ABI __hash_table(const hasher& __hf, const key_equal& __eql, const allocator_type& __a);
763 _LIBCPP_HIDE_FROM_ABI explicit __hash_table(const allocator_type& __a);
764 _LIBCPP_HIDE_FROM_ABI __hash_table(const __hash_table& __u);
765 _LIBCPP_HIDE_FROM_ABI __hash_table(const __hash_table& __u, const allocator_type& __a);
766 _LIBCPP_HIDE_FROM_ABI __hash_table(__hash_table&& __u) _NOEXCEPT_(
767 is_nothrow_move_constructible<__bucket_list>::value&& is_nothrow_move_constructible<__first_node>::value&&
768 is_nothrow_move_constructible<__node_allocator>::value&& is_nothrow_move_constructible<hasher>::value&&
769 is_nothrow_move_constructible<key_equal>::value);
770 _LIBCPP_HIDE_FROM_ABI __hash_table(__hash_table&& __u, const allocator_type& __a);
771 _LIBCPP_HIDE_FROM_ABI ~__hash_table();
773 _LIBCPP_HIDE_FROM_ABI __hash_table& operator=(const __hash_table& __u);
774 _LIBCPP_HIDE_FROM_ABI __hash_table& operator=(__hash_table&& __u)
775 _NOEXCEPT_(__node_traits::propagate_on_container_move_assignment::value&&
776 is_nothrow_move_assignable<__node_allocator>::value&& is_nothrow_move_assignable<hasher>::value&&
777 is_nothrow_move_assignable<key_equal>::value);
778 template <class _InputIterator>
779 _LIBCPP_HIDE_FROM_ABI void __assign_unique(_InputIterator __first, _InputIterator __last);
780 template <class _InputIterator>
781 _LIBCPP_HIDE_FROM_ABI void __assign_multi(_InputIterator __first, _InputIterator __last);
783 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT {
784 return std::min<size_type>(__node_traits::max_size(__node_alloc()), numeric_limits<difference_type >::max());
788 _LIBCPP_HIDE_FROM_ABI __next_pointer __node_insert_multi_prepare(size_t __cp_hash, value_type& __cp_val);
789 _LIBCPP_HIDE_FROM_ABI void __node_insert_multi_perform(__node_pointer __cp, __next_pointer __pn) _NOEXCEPT;
791 _LIBCPP_HIDE_FROM_ABI __next_pointer __node_insert_unique_prepare(size_t __nd_hash, value_type& __nd_val);
792 _LIBCPP_HIDE_FROM_ABI void __node_insert_unique_perform(__node_pointer __ptr) _NOEXCEPT;
795 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __node_insert_unique(__node_pointer __nd);
796 _LIBCPP_HIDE_FROM_ABI iterator __node_insert_multi(__node_pointer __nd);
797 _LIBCPP_HIDE_FROM_ABI iterator __node_insert_multi(const_iterator __p, __node_pointer __nd);
799 template <class _Key, class... _Args>
800 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_key_args(_Key const& __k, _Args&&... __args);
802 template <class... _Args>
803 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_impl(_Args&&... __args);
806 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique(_Pp&& __x) {
807 return __emplace_unique_extract_key(std::forward<_Pp>(__x), __can_extract_key<_Pp, key_type>());
810 template <class _First,
812 __enable_if_t<__can_extract_map_key<_First, key_type, __container_value_type>::value, int> = 0>
813 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique(_First&& __f, _Second&& __s) {
814 return __emplace_unique_key_args(__f, std::forward<_First>(__f), std::forward<_Second>(__s));
817 template <class... _Args>
818 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique(_Args&&... __args) {
819 return __emplace_unique_impl(std::forward<_Args>(__args)...);
823 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_extract_key(_Pp&& __x, __extract_key_fail_tag) {
824 return __emplace_unique_impl(std::forward<_Pp>(__x));
827 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_extract_key(_Pp&& __x, __extract_key_self_tag) {
828 return __emplace_unique_key_args(__x, std::forward<_Pp>(__x));
831 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_extract_key(_Pp&& __x, __extract_key_first_tag) {
832 return __emplace_unique_key_args(__x.first, std::forward<_Pp>(__x));
835 template <class... _Args>
836 _LIBCPP_HIDE_FROM_ABI iterator __emplace_multi(_Args&&... __args);
837 template <class... _Args>
838 _LIBCPP_HIDE_FROM_ABI iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args);
840 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __insert_unique(__container_value_type&& __x) {
841 return __emplace_unique_key_args(_NodeTypes::__get_key(__x), std::move(__x));
844 template <class _Pp, __enable_if_t<!__is_same_uncvref<_Pp, __container_value_type>::value, int> = 0>
845 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __insert_unique(_Pp&& __x) {
846 return __emplace_unique(std::forward<_Pp>(__x));
850 _LIBCPP_HIDE_FROM_ABI iterator __insert_multi(_Pp&& __x) {
851 return __emplace_multi(std::forward<_Pp>(__x));
855 _LIBCPP_HIDE_FROM_ABI iterator __insert_multi(const_iterator __p, _Pp&& __x) {
856 return __emplace_hint_multi(__p, std::forward<_Pp>(__x));
859 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __insert_unique(const __container_value_type& __x) {
860 return __emplace_unique_key_args(_NodeTypes::__get_key(__x), __x);
863 #if _LIBCPP_STD_VER >= 17
864 template <class _NodeHandle, class _InsertReturnType>
865 _LIBCPP_HIDE_FROM_ABI _InsertReturnType __node_handle_insert_unique(_NodeHandle&& __nh);
866 template <class _NodeHandle>
867 _LIBCPP_HIDE_FROM_ABI iterator __node_handle_insert_unique(const_iterator __hint, _NodeHandle&& __nh);
868 template <class _Table>
869 _LIBCPP_HIDE_FROM_ABI void __node_handle_merge_unique(_Table& __source);
871 template <class _NodeHandle>
872 _LIBCPP_HIDE_FROM_ABI iterator __node_handle_insert_multi(_NodeHandle&& __nh);
873 template <class _NodeHandle>
874 _LIBCPP_HIDE_FROM_ABI iterator __node_handle_insert_multi(const_iterator __hint, _NodeHandle&& __nh);
875 template <class _Table>
876 _LIBCPP_HIDE_FROM_ABI void __node_handle_merge_multi(_Table& __source);
878 template <class _NodeHandle>
879 _LIBCPP_HIDE_FROM_ABI _NodeHandle __node_handle_extract(key_type const& __key);
880 template <class _NodeHandle>
881 _LIBCPP_HIDE_FROM_ABI _NodeHandle __node_handle_extract(const_iterator __it);
884 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT;
885 _LIBCPP_HIDE_FROM_ABI void __rehash_unique(size_type __n) { __rehash<true>(__n); }
886 _LIBCPP_HIDE_FROM_ABI void __rehash_multi(size_type __n) { __rehash<false>(__n); }
887 _LIBCPP_HIDE_FROM_ABI void __reserve_unique(size_type __n) {
888 __rehash_unique(static_cast<size_type>(__math::ceil(__n / max_load_factor())));
890 _LIBCPP_HIDE_FROM_ABI void __reserve_multi(size_type __n) {
891 __rehash_multi(static_cast<size_type>(__math::ceil(__n / max_load_factor())));
894 _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const _NOEXCEPT { return __bucket_list_.get_deleter().size(); }
896 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT;
897 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT;
898 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT;
899 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT;
901 template <class _Key>
902 _LIBCPP_HIDE_FROM_ABI size_type bucket(const _Key& __k) const {
903 _LIBCPP_ASSERT_ARGUMENT_WITHIN_DOMAIN(
904 bucket_count() > 0, "unordered container::bucket(key) called when bucket_count() == 0");
905 return std::__constrain_hash(hash_function()(__k), bucket_count());
908 template <class _Key>
909 _LIBCPP_HIDE_FROM_ABI iterator find(const _Key& __x);
910 template <class _Key>
911 _LIBCPP_HIDE_FROM_ABI const_iterator find(const _Key& __x) const;
913 typedef __hash_node_destructor<__node_allocator> _Dp;
914 typedef unique_ptr<__node, _Dp> __node_holder;
916 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p);
917 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last);
918 template <class _Key>
919 _LIBCPP_HIDE_FROM_ABI size_type __erase_unique(const _Key& __k);
920 template <class _Key>
921 _LIBCPP_HIDE_FROM_ABI size_type __erase_multi(const _Key& __k);
922 _LIBCPP_HIDE_FROM_ABI __node_holder remove(const_iterator __p) _NOEXCEPT;
924 template <class _Key>
925 _LIBCPP_HIDE_FROM_ABI size_type __count_unique(const _Key& __k) const;
926 template <class _Key>
927 _LIBCPP_HIDE_FROM_ABI size_type __count_multi(const _Key& __k) const;
929 template <class _Key>
930 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> __equal_range_unique(const _Key& __k);
931 template <class _Key>
932 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> __equal_range_unique(const _Key& __k) const;
934 template <class _Key>
935 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> __equal_range_multi(const _Key& __k);
936 template <class _Key>
937 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> __equal_range_multi(const _Key& __k) const;
939 _LIBCPP_HIDE_FROM_ABI void swap(__hash_table& __u)
940 #if _LIBCPP_STD_VER <= 11
941 _NOEXCEPT_(__is_nothrow_swappable_v<hasher>&& __is_nothrow_swappable_v<key_equal> &&
942 (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value ||
943 __is_nothrow_swappable_v<__pointer_allocator>) &&
944 (!__node_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<__node_allocator>));
946 _NOEXCEPT_(__is_nothrow_swappable_v<hasher>&& __is_nothrow_swappable_v<key_equal>);
949 _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const _NOEXCEPT { return max_size(); }
950 _LIBCPP_HIDE_FROM_ABI size_type bucket_size(size_type __n) const;
951 _LIBCPP_HIDE_FROM_ABI float load_factor() const _NOEXCEPT {
952 size_type __bc = bucket_count();
953 return __bc != 0 ? (float)size() / __bc : 0.f;
955 _LIBCPP_HIDE_FROM_ABI void max_load_factor(float __mlf) _NOEXCEPT {
956 // While passing a non-positive load factor is undefined behavior, in practice the result will be benign (the
957 // call will be equivalent to `max_load_factor(load_factor())`, which is also the case for passing a valid value
958 // less than the current `load_factor`).
959 _LIBCPP_ASSERT_PEDANTIC(__mlf > 0, "unordered container::max_load_factor(lf) called with lf <= 0");
960 max_load_factor() = std::max(__mlf, load_factor());
963 _LIBCPP_HIDE_FROM_ABI local_iterator begin(size_type __n) {
964 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
965 __n < bucket_count(), "unordered container::begin(n) called with n >= bucket_count()");
966 return local_iterator(__bucket_list_[__n], __n, bucket_count());
969 _LIBCPP_HIDE_FROM_ABI local_iterator end(size_type __n) {
970 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
971 __n < bucket_count(), "unordered container::end(n) called with n >= bucket_count()");
972 return local_iterator(nullptr, __n, bucket_count());
975 _LIBCPP_HIDE_FROM_ABI const_local_iterator cbegin(size_type __n) const {
976 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
977 __n < bucket_count(), "unordered container::cbegin(n) called with n >= bucket_count()");
978 return const_local_iterator(__bucket_list_[__n], __n, bucket_count());
981 _LIBCPP_HIDE_FROM_ABI const_local_iterator cend(size_type __n) const {
982 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
983 __n < bucket_count(), "unordered container::cend(n) called with n >= bucket_count()");
984 return const_local_iterator(nullptr, __n, bucket_count());
988 template <bool _UniqueKeys>
989 _LIBCPP_HIDE_FROM_ABI void __rehash(size_type __n);
990 template <bool _UniqueKeys>
991 _LIBCPP_HIDE_FROM_ABI void __do_rehash(size_type __n);
993 template <class... _Args>
994 _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node(_Args&&... __args);
996 template <class _First, class... _Rest>
997 _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node_hash(size_t __hash, _First&& __f, _Rest&&... __rest);
999 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __hash_table& __u) {
1000 __copy_assign_alloc(__u, integral_constant<bool, __node_traits::propagate_on_container_copy_assignment::value>());
1002 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __hash_table& __u, true_type);
1003 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __hash_table&, false_type) {}
1005 _LIBCPP_HIDE_FROM_ABI void __move_assign(__hash_table& __u, false_type);
1006 _LIBCPP_HIDE_FROM_ABI void __move_assign(__hash_table& __u, true_type)
1007 _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value&& is_nothrow_move_assignable<hasher>::value&&
1008 is_nothrow_move_assignable<key_equal>::value);
1009 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__hash_table& __u) _NOEXCEPT_(
1010 !__node_traits::propagate_on_container_move_assignment::value ||
1011 (is_nothrow_move_assignable<__pointer_allocator>::value && is_nothrow_move_assignable<__node_allocator>::value)) {
1012 __move_assign_alloc(__u, integral_constant<bool, __node_traits::propagate_on_container_move_assignment::value>());
1014 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__hash_table& __u, true_type) _NOEXCEPT_(
1015 is_nothrow_move_assignable<__pointer_allocator>::value&& is_nothrow_move_assignable<__node_allocator>::value) {
1016 __bucket_list_.get_deleter().__alloc() = std::move(__u.__bucket_list_.get_deleter().__alloc());
1017 __node_alloc() = std::move(__u.__node_alloc());
1019 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__hash_table&, false_type) _NOEXCEPT {}
1021 _LIBCPP_HIDE_FROM_ABI void __deallocate_node(__next_pointer __np) _NOEXCEPT;
1022 _LIBCPP_HIDE_FROM_ABI __next_pointer __detach() _NOEXCEPT;
1024 template <class, class, class, class, class>
1025 friend class _LIBCPP_TEMPLATE_VIS unordered_map;
1026 template <class, class, class, class, class>
1027 friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
1030 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1031 inline __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table() _NOEXCEPT_(
1032 is_nothrow_default_constructible<__bucket_list>::value&& is_nothrow_default_constructible<__first_node>::value&&
1033 is_nothrow_default_constructible<__node_allocator>::value&& is_nothrow_default_constructible<hasher>::value&&
1034 is_nothrow_default_constructible<key_equal>::value)
1035 : __size_(0), __max_load_factor_(1.0f) {}
1037 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1038 inline __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf, const key_equal& __eql)
1039 : __bucket_list_(nullptr, __bucket_list_deleter()),
1044 __max_load_factor_(1.0f),
1047 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1048 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(
1049 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1050 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
1051 __node_alloc_(__node_allocator(__a)),
1054 __max_load_factor_(1.0f),
1057 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1058 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const allocator_type& __a)
1059 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
1060 __node_alloc_(__node_allocator(__a)),
1062 __max_load_factor_(1.0f) {}
1064 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1065 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u)
1066 : __bucket_list_(nullptr,
1067 __bucket_list_deleter(allocator_traits<__pointer_allocator>::select_on_container_copy_construction(
1068 __u.__bucket_list_.get_deleter().__alloc()),
1070 __node_alloc_(allocator_traits<__node_allocator>::select_on_container_copy_construction(__u.__node_alloc())),
1072 __hasher_(__u.hash_function()),
1073 __max_load_factor_(__u.__max_load_factor_),
1074 __key_eq_(__u.__key_eq_) {}
1076 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1077 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u, const allocator_type& __a)
1078 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
1079 __node_alloc_(__node_allocator(__a)),
1081 __hasher_(__u.hash_function()),
1082 __max_load_factor_(__u.__max_load_factor_),
1083 __key_eq_(__u.__key_eq_) {}
1085 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1086 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u) _NOEXCEPT_(
1087 is_nothrow_move_constructible<__bucket_list>::value&& is_nothrow_move_constructible<__first_node>::value&&
1088 is_nothrow_move_constructible<__node_allocator>::value&& is_nothrow_move_constructible<hasher>::value&&
1089 is_nothrow_move_constructible<key_equal>::value)
1090 : __bucket_list_(std::move(__u.__bucket_list_)),
1091 __first_node_(std::move(__u.__first_node_)),
1092 __node_alloc_(std::move(__u.__node_alloc_)),
1093 __size_(std::move(__u.__size_)),
1094 __hasher_(std::move(__u.__hasher_)),
1095 __max_load_factor_(__u.__max_load_factor_),
1096 __key_eq_(std::move(__u.__key_eq_)) {
1098 __bucket_list_[std::__constrain_hash(__first_node_.__next_->__hash(), bucket_count())] = __first_node_.__ptr();
1099 __u.__first_node_.__next_ = nullptr;
1104 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1105 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u, const allocator_type& __a)
1106 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
1107 __node_alloc_(__node_allocator(__a)),
1109 __hasher_(std::move(__u.__hasher_)),
1110 __max_load_factor_(__u.__max_load_factor_),
1111 __key_eq_(std::move(__u.__key_eq_)) {
1112 if (__a == allocator_type(__u.__node_alloc())) {
1113 __bucket_list_.reset(__u.__bucket_list_.release());
1114 __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size();
1115 __u.__bucket_list_.get_deleter().size() = 0;
1116 if (__u.size() > 0) {
1117 __first_node_.__next_ = __u.__first_node_.__next_;
1118 __u.__first_node_.__next_ = nullptr;
1119 __bucket_list_[std::__constrain_hash(__first_node_.__next_->__hash(), bucket_count())] = __first_node_.__ptr();
1120 size() = __u.size();
1126 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1127 __hash_table<_Tp, _Hash, _Equal, _Alloc>::~__hash_table() {
1128 #if defined(_LIBCPP_CXX03_LANG)
1129 static_assert(is_copy_constructible<key_equal>::value, "Predicate must be copy-constructible.");
1130 static_assert(is_copy_constructible<hasher>::value, "Hasher must be copy-constructible.");
1133 __deallocate_node(__first_node_.__next_);
1136 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1137 void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__copy_assign_alloc(const __hash_table& __u, true_type) {
1138 if (__node_alloc() != __u.__node_alloc()) {
1140 __bucket_list_.reset();
1141 __bucket_list_.get_deleter().size() = 0;
1143 __bucket_list_.get_deleter().__alloc() = __u.__bucket_list_.get_deleter().__alloc();
1144 __node_alloc() = __u.__node_alloc();
1147 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1148 __hash_table<_Tp, _Hash, _Equal, _Alloc>& __hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(const __hash_table& __u) {
1149 if (this != std::addressof(__u)) {
1150 __copy_assign_alloc(__u);
1151 hash_function() = __u.hash_function();
1152 key_eq() = __u.key_eq();
1153 max_load_factor() = __u.max_load_factor();
1154 __assign_multi(__u.begin(), __u.end());
1159 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1160 void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__deallocate_node(__next_pointer __np) _NOEXCEPT {
1161 __node_allocator& __na = __node_alloc();
1162 while (__np != nullptr) {
1163 __next_pointer __next = __np->__next_;
1164 __node_pointer __real_np = __np->__upcast();
1165 __node_traits::destroy(__na, _NodeTypes::__get_ptr(__real_np->__get_value()));
1166 std::__destroy_at(std::addressof(*__real_np));
1167 __node_traits::deallocate(__na, __real_np, 1);
1172 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1173 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer
1174 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__detach() _NOEXCEPT {
1175 size_type __bc = bucket_count();
1176 for (size_type __i = 0; __i < __bc; ++__i)
1177 __bucket_list_[__i] = nullptr;
1179 __next_pointer __cache = __first_node_.__next_;
1180 __first_node_.__next_ = nullptr;
1184 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1185 void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign(__hash_table& __u, true_type)
1186 _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value&& is_nothrow_move_assignable<hasher>::value&&
1187 is_nothrow_move_assignable<key_equal>::value) {
1189 __bucket_list_.reset(__u.__bucket_list_.release());
1190 __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size();
1191 __u.__bucket_list_.get_deleter().size() = 0;
1192 __move_assign_alloc(__u);
1193 size() = __u.size();
1194 hash_function() = std::move(__u.hash_function());
1195 max_load_factor() = __u.max_load_factor();
1196 key_eq() = std::move(__u.key_eq());
1197 __first_node_.__next_ = __u.__first_node_.__next_;
1199 __bucket_list_[std::__constrain_hash(__first_node_.__next_->__hash(), bucket_count())] = __first_node_.__ptr();
1200 __u.__first_node_.__next_ = nullptr;
1205 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1206 void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign(__hash_table& __u, false_type) {
1207 if (__node_alloc() == __u.__node_alloc())
1208 __move_assign(__u, true_type());
1210 hash_function() = std::move(__u.hash_function());
1211 key_eq() = std::move(__u.key_eq());
1212 max_load_factor() = __u.max_load_factor();
1213 if (bucket_count() != 0) {
1214 __next_pointer __cache = __detach();
1215 #if _LIBCPP_HAS_EXCEPTIONS
1217 #endif // _LIBCPP_HAS_EXCEPTIONS
1218 const_iterator __i = __u.begin();
1219 while (__cache != nullptr && __u.size() != 0) {
1220 __cache->__upcast()->__get_value() = std::move(__u.remove(__i++)->__get_value());
1221 __next_pointer __next = __cache->__next_;
1222 __node_insert_multi(__cache->__upcast());
1225 #if _LIBCPP_HAS_EXCEPTIONS
1227 __deallocate_node(__cache);
1230 #endif // _LIBCPP_HAS_EXCEPTIONS
1231 __deallocate_node(__cache);
1233 const_iterator __i = __u.begin();
1234 while (__u.size() != 0) {
1235 __node_holder __h = __construct_node(_NodeTypes::__move(__u.remove(__i++)->__get_value()));
1236 __node_insert_multi(__h.get());
1242 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1243 inline __hash_table<_Tp, _Hash, _Equal, _Alloc>&
1244 __hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(__hash_table&& __u) _NOEXCEPT_(
1245 __node_traits::propagate_on_container_move_assignment::value&& is_nothrow_move_assignable<__node_allocator>::value&&
1246 is_nothrow_move_assignable<hasher>::value&& is_nothrow_move_assignable<key_equal>::value) {
1247 __move_assign(__u, integral_constant<bool, __node_traits::propagate_on_container_move_assignment::value>());
1251 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1252 template <class _InputIterator>
1253 void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_unique(_InputIterator __first, _InputIterator __last) {
1254 typedef iterator_traits<_InputIterator> _ITraits;
1255 typedef typename _ITraits::value_type _ItValueType;
1256 static_assert(is_same<_ItValueType, __container_value_type>::value,
1257 "__assign_unique may only be called with the containers value type");
1259 if (bucket_count() != 0) {
1260 __next_pointer __cache = __detach();
1261 #if _LIBCPP_HAS_EXCEPTIONS
1263 #endif // _LIBCPP_HAS_EXCEPTIONS
1264 for (; __cache != nullptr && __first != __last; ++__first) {
1265 __cache->__upcast()->__get_value() = *__first;
1266 __next_pointer __next = __cache->__next_;
1267 __node_insert_unique(__cache->__upcast());
1270 #if _LIBCPP_HAS_EXCEPTIONS
1272 __deallocate_node(__cache);
1275 #endif // _LIBCPP_HAS_EXCEPTIONS
1276 __deallocate_node(__cache);
1278 for (; __first != __last; ++__first)
1279 __insert_unique(*__first);
1282 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1283 template <class _InputIterator>
1284 void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_multi(_InputIterator __first, _InputIterator __last) {
1285 typedef iterator_traits<_InputIterator> _ITraits;
1286 typedef typename _ITraits::value_type _ItValueType;
1288 (is_same<_ItValueType, __container_value_type>::value || is_same<_ItValueType, __node_value_type>::value),
1289 "__assign_multi may only be called with the containers value type"
1290 " or the nodes value type");
1291 if (bucket_count() != 0) {
1292 __next_pointer __cache = __detach();
1293 #if _LIBCPP_HAS_EXCEPTIONS
1295 #endif // _LIBCPP_HAS_EXCEPTIONS
1296 for (; __cache != nullptr && __first != __last; ++__first) {
1297 __cache->__upcast()->__get_value() = *__first;
1298 __next_pointer __next = __cache->__next_;
1299 __node_insert_multi(__cache->__upcast());
1302 #if _LIBCPP_HAS_EXCEPTIONS
1304 __deallocate_node(__cache);
1307 #endif // _LIBCPP_HAS_EXCEPTIONS
1308 __deallocate_node(__cache);
1310 for (; __first != __last; ++__first)
1311 __insert_multi(_NodeTypes::__get_value(*__first));
1314 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1315 inline typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1316 __hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() _NOEXCEPT {
1317 return iterator(__first_node_.__next_);
1320 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1321 inline typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1322 __hash_table<_Tp, _Hash, _Equal, _Alloc>::end() _NOEXCEPT {
1323 return iterator(nullptr);
1326 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1327 inline typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator
1328 __hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() const _NOEXCEPT {
1329 return const_iterator(__first_node_.__next_);
1332 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1333 inline typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator
1334 __hash_table<_Tp, _Hash, _Equal, _Alloc>::end() const _NOEXCEPT {
1335 return const_iterator(nullptr);
1338 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1339 void __hash_table<_Tp, _Hash, _Equal, _Alloc>::clear() _NOEXCEPT {
1341 __deallocate_node(__first_node_.__next_);
1342 __first_node_.__next_ = nullptr;
1343 size_type __bc = bucket_count();
1344 for (size_type __i = 0; __i < __bc; ++__i)
1345 __bucket_list_[__i] = nullptr;
1350 // Prepare the container for an insertion of the value __value with the hash
1351 // __hash. This does a lookup into the container to see if __value is already
1352 // present, and performs a rehash if necessary. Returns a pointer to the
1353 // existing element if it exists, otherwise nullptr.
1355 // Note that this function does forward exceptions if key_eq() throws, and never
1356 // mutates __value or actually inserts into the map.
1357 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1358 _LIBCPP_HIDE_FROM_ABI typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer
1359 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique_prepare(size_t __hash, value_type& __value) {
1360 size_type __bc = bucket_count();
1363 size_t __chash = std::__constrain_hash(__hash, __bc);
1364 __next_pointer __ndptr = __bucket_list_[__chash];
1365 if (__ndptr != nullptr) {
1366 for (__ndptr = __ndptr->__next_;
1367 __ndptr != nullptr &&
1368 (__ndptr->__hash() == __hash || std::__constrain_hash(__ndptr->__hash(), __bc) == __chash);
1369 __ndptr = __ndptr->__next_) {
1370 if ((__ndptr->__hash() == __hash) && key_eq()(__ndptr->__upcast()->__get_value(), __value))
1375 if (size() + 1 > __bc * max_load_factor() || __bc == 0) {
1376 __rehash_unique(std::max<size_type>(
1377 2 * __bc + !std::__is_hash_power2(__bc), size_type(__math::ceil(float(size() + 1) / max_load_factor()))));
1382 // Insert the node __nd into the container by pushing it into the right bucket,
1383 // and updating size(). Assumes that __nd->__hash is up-to-date, and that
1384 // rehashing has already occurred and that no element with the same key exists
1386 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1387 _LIBCPP_HIDE_FROM_ABI void
1388 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique_perform(__node_pointer __nd) _NOEXCEPT {
1389 size_type __bc = bucket_count();
1390 size_t __chash = std::__constrain_hash(__nd->__hash(), __bc);
1391 // insert_after __bucket_list_[__chash], or __first_node if bucket is null
1392 __next_pointer __pn = __bucket_list_[__chash];
1393 if (__pn == nullptr) {
1394 __pn = __first_node_.__ptr();
1395 __nd->__next_ = __pn->__next_;
1396 __pn->__next_ = __nd->__ptr();
1397 // fix up __bucket_list_
1398 __bucket_list_[__chash] = __pn;
1399 if (__nd->__next_ != nullptr)
1400 __bucket_list_[std::__constrain_hash(__nd->__next_->__hash(), __bc)] = __nd->__ptr();
1402 __nd->__next_ = __pn->__next_;
1403 __pn->__next_ = __nd->__ptr();
1408 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1409 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
1410 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique(__node_pointer __nd) {
1411 __nd->__hash_ = hash_function()(__nd->__get_value());
1412 __next_pointer __existing_node = __node_insert_unique_prepare(__nd->__hash(), __nd->__get_value());
1414 // Insert the node, unless it already exists in the container.
1415 bool __inserted = false;
1416 if (__existing_node == nullptr) {
1417 __node_insert_unique_perform(__nd);
1418 __existing_node = __nd->__ptr();
1421 return pair<iterator, bool>(iterator(__existing_node), __inserted);
1424 // Prepare the container for an insertion of the value __cp_val with the hash
1425 // __cp_hash. This does a lookup into the container to see if __cp_value is
1426 // already present, and performs a rehash if necessary. Returns a pointer to the
1427 // last occurrence of __cp_val in the map.
1429 // Note that this function does forward exceptions if key_eq() throws, and never
1430 // mutates __value or actually inserts into the map.
1431 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1432 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer
1433 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi_prepare(size_t __cp_hash, value_type& __cp_val) {
1434 size_type __bc = bucket_count();
1435 if (size() + 1 > __bc * max_load_factor() || __bc == 0) {
1436 __rehash_multi(std::max<size_type>(
1437 2 * __bc + !std::__is_hash_power2(__bc), size_type(__math::ceil(float(size() + 1) / max_load_factor()))));
1438 __bc = bucket_count();
1440 size_t __chash = std::__constrain_hash(__cp_hash, __bc);
1441 __next_pointer __pn = __bucket_list_[__chash];
1442 if (__pn != nullptr) {
1443 for (bool __found = false;
1444 __pn->__next_ != nullptr && std::__constrain_hash(__pn->__next_->__hash(), __bc) == __chash;
1445 __pn = __pn->__next_) {
1446 // __found key_eq() action
1449 // false true set __found to true
1452 (__pn->__next_->__hash() == __cp_hash && key_eq()(__pn->__next_->__upcast()->__get_value(), __cp_val))) {
1463 // Insert the node __cp into the container after __pn (which is the last node in
1464 // the bucket that compares equal to __cp). Rehashing, and checking for
1465 // uniqueness has already been performed (in __node_insert_multi_prepare), so
1466 // all we need to do is update the bucket and size(). Assumes that __cp->__hash
1468 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1469 void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi_perform(
1470 __node_pointer __cp, __next_pointer __pn) _NOEXCEPT {
1471 size_type __bc = bucket_count();
1472 size_t __chash = std::__constrain_hash(__cp->__hash_, __bc);
1473 if (__pn == nullptr) {
1474 __pn = __first_node_.__ptr();
1475 __cp->__next_ = __pn->__next_;
1476 __pn->__next_ = __cp->__ptr();
1477 // fix up __bucket_list_
1478 __bucket_list_[__chash] = __pn;
1479 if (__cp->__next_ != nullptr)
1480 __bucket_list_[std::__constrain_hash(__cp->__next_->__hash(), __bc)] = __cp->__ptr();
1482 __cp->__next_ = __pn->__next_;
1483 __pn->__next_ = __cp->__ptr();
1484 if (__cp->__next_ != nullptr) {
1485 size_t __nhash = std::__constrain_hash(__cp->__next_->__hash(), __bc);
1486 if (__nhash != __chash)
1487 __bucket_list_[__nhash] = __cp->__ptr();
1493 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1494 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1495 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __cp) {
1496 __cp->__hash_ = hash_function()(__cp->__get_value());
1497 __next_pointer __pn = __node_insert_multi_prepare(__cp->__hash(), __cp->__get_value());
1498 __node_insert_multi_perform(__cp, __pn);
1500 return iterator(__cp->__ptr());
1503 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1504 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1505 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(const_iterator __p, __node_pointer __cp) {
1506 if (__p != end() && key_eq()(*__p, __cp->__get_value())) {
1507 __next_pointer __np = __p.__node_;
1508 __cp->__hash_ = __np->__hash();
1509 size_type __bc = bucket_count();
1510 if (size() + 1 > __bc * max_load_factor() || __bc == 0) {
1511 __rehash_multi(std::max<size_type>(
1512 2 * __bc + !std::__is_hash_power2(__bc), size_type(__math::ceil(float(size() + 1) / max_load_factor()))));
1513 __bc = bucket_count();
1515 size_t __chash = std::__constrain_hash(__cp->__hash_, __bc);
1516 __next_pointer __pp = __bucket_list_[__chash];
1517 while (__pp->__next_ != __np)
1518 __pp = __pp->__next_;
1519 __cp->__next_ = __np;
1520 __pp->__next_ = static_cast<__next_pointer>(__cp);
1522 return iterator(static_cast<__next_pointer>(__cp));
1524 return __node_insert_multi(__cp);
1527 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1528 template <class _Key, class... _Args>
1529 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
1530 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique_key_args(_Key const& __k, _Args&&... __args) {
1531 size_t __hash = hash_function()(__k);
1532 size_type __bc = bucket_count();
1533 bool __inserted = false;
1534 __next_pointer __nd;
1537 __chash = std::__constrain_hash(__hash, __bc);
1538 __nd = __bucket_list_[__chash];
1539 if (__nd != nullptr) {
1540 for (__nd = __nd->__next_;
1541 __nd != nullptr && (__nd->__hash() == __hash || std::__constrain_hash(__nd->__hash(), __bc) == __chash);
1542 __nd = __nd->__next_) {
1543 if ((__nd->__hash() == __hash) && key_eq()(__nd->__upcast()->__get_value(), __k))
1549 __node_holder __h = __construct_node_hash(__hash, std::forward<_Args>(__args)...);
1550 if (size() + 1 > __bc * max_load_factor() || __bc == 0) {
1551 __rehash_unique(std::max<size_type>(
1552 2 * __bc + !std::__is_hash_power2(__bc), size_type(__math::ceil(float(size() + 1) / max_load_factor()))));
1553 __bc = bucket_count();
1554 __chash = std::__constrain_hash(__hash, __bc);
1556 // insert_after __bucket_list_[__chash], or __first_node if bucket is null
1557 __next_pointer __pn = __bucket_list_[__chash];
1558 if (__pn == nullptr) {
1559 __pn = __first_node_.__ptr();
1560 __h->__next_ = __pn->__next_;
1561 __pn->__next_ = __h.get()->__ptr();
1562 // fix up __bucket_list_
1563 __bucket_list_[__chash] = __pn;
1564 if (__h->__next_ != nullptr)
1565 __bucket_list_[std::__constrain_hash(__h->__next_->__hash(), __bc)] = __h.get()->__ptr();
1567 __h->__next_ = __pn->__next_;
1568 __pn->__next_ = static_cast<__next_pointer>(__h.get());
1570 __nd = static_cast<__next_pointer>(__h.release());
1576 return pair<iterator, bool>(iterator(__nd), __inserted);
1579 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1580 template <class... _Args>
1581 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
1582 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique_impl(_Args&&... __args) {
1583 __node_holder __h = __construct_node(std::forward<_Args>(__args)...);
1584 pair<iterator, bool> __r = __node_insert_unique(__h.get());
1590 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1591 template <class... _Args>
1592 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1593 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_multi(_Args&&... __args) {
1594 __node_holder __h = __construct_node(std::forward<_Args>(__args)...);
1595 iterator __r = __node_insert_multi(__h.get());
1600 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1601 template <class... _Args>
1602 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1603 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_hint_multi(const_iterator __p, _Args&&... __args) {
1604 __node_holder __h = __construct_node(std::forward<_Args>(__args)...);
1605 iterator __r = __node_insert_multi(__p, __h.get());
1610 #if _LIBCPP_STD_VER >= 17
1611 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1612 template <class _NodeHandle, class _InsertReturnType>
1613 _LIBCPP_HIDE_FROM_ABI _InsertReturnType
1614 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_unique(_NodeHandle&& __nh) {
1616 return _InsertReturnType{end(), false, _NodeHandle()};
1617 pair<iterator, bool> __result = __node_insert_unique(__nh.__ptr_);
1618 if (__result.second)
1619 __nh.__release_ptr();
1620 return _InsertReturnType{__result.first, __result.second, std::move(__nh)};
1623 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1624 template <class _NodeHandle>
1625 _LIBCPP_HIDE_FROM_ABI typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1626 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_unique(const_iterator, _NodeHandle&& __nh) {
1629 pair<iterator, bool> __result = __node_insert_unique(__nh.__ptr_);
1630 if (__result.second)
1631 __nh.__release_ptr();
1632 return __result.first;
1635 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1636 template <class _NodeHandle>
1637 _LIBCPP_HIDE_FROM_ABI _NodeHandle
1638 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_extract(key_type const& __key) {
1639 iterator __i = find(__key);
1641 return _NodeHandle();
1642 return __node_handle_extract<_NodeHandle>(__i);
1645 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1646 template <class _NodeHandle>
1647 _LIBCPP_HIDE_FROM_ABI _NodeHandle __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_extract(const_iterator __p) {
1648 allocator_type __alloc(__node_alloc());
1649 return _NodeHandle(remove(__p).release(), __alloc);
1652 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1653 template <class _Table>
1654 _LIBCPP_HIDE_FROM_ABI void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_merge_unique(_Table& __source) {
1655 static_assert(is_same<__node, typename _Table::__node>::value, "");
1657 for (typename _Table::iterator __it = __source.begin(); __it != __source.end();) {
1658 __node_pointer __src_ptr = __it.__node_->__upcast();
1659 size_t __hash = hash_function()(__src_ptr->__get_value());
1660 __next_pointer __existing_node = __node_insert_unique_prepare(__hash, __src_ptr->__get_value());
1661 auto __prev_iter = __it++;
1662 if (__existing_node == nullptr) {
1663 (void)__source.remove(__prev_iter).release();
1664 __src_ptr->__hash_ = __hash;
1665 __node_insert_unique_perform(__src_ptr);
1670 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1671 template <class _NodeHandle>
1672 _LIBCPP_HIDE_FROM_ABI typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1673 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_multi(_NodeHandle&& __nh) {
1676 iterator __result = __node_insert_multi(__nh.__ptr_);
1677 __nh.__release_ptr();
1681 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1682 template <class _NodeHandle>
1683 _LIBCPP_HIDE_FROM_ABI typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1684 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_multi(const_iterator __hint, _NodeHandle&& __nh) {
1687 iterator __result = __node_insert_multi(__hint, __nh.__ptr_);
1688 __nh.__release_ptr();
1692 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1693 template <class _Table>
1694 _LIBCPP_HIDE_FROM_ABI void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_merge_multi(_Table& __source) {
1695 static_assert(is_same<typename _Table::__node, __node>::value, "");
1697 for (typename _Table::iterator __it = __source.begin(); __it != __source.end();) {
1698 __node_pointer __src_ptr = __it.__node_->__upcast();
1699 size_t __src_hash = hash_function()(__src_ptr->__get_value());
1700 __next_pointer __pn = __node_insert_multi_prepare(__src_hash, __src_ptr->__get_value());
1701 (void)__source.remove(__it++).release();
1702 __src_ptr->__hash_ = __src_hash;
1703 __node_insert_multi_perform(__src_ptr, __pn);
1706 #endif // _LIBCPP_STD_VER >= 17
1708 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1709 template <bool _UniqueKeys>
1710 void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__rehash(size_type __n) _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK {
1713 else if (__n & (__n - 1))
1714 __n = std::__next_prime(__n);
1715 size_type __bc = bucket_count();
1717 __do_rehash<_UniqueKeys>(__n);
1718 else if (__n < __bc) {
1719 __n = std::max<size_type>(
1721 std::__is_hash_power2(__bc) ? std::__next_hash_pow2(size_t(__math::ceil(float(size()) / max_load_factor())))
1722 : std::__next_prime(size_t(__math::ceil(float(size()) / max_load_factor()))));
1724 __do_rehash<_UniqueKeys>(__n);
1728 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1729 template <bool _UniqueKeys>
1730 void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__do_rehash(size_type __nbc) {
1731 __pointer_allocator& __npa = __bucket_list_.get_deleter().__alloc();
1732 __bucket_list_.reset(__nbc > 0 ? __pointer_alloc_traits::allocate(__npa, __nbc) : nullptr);
1733 __bucket_list_.get_deleter().size() = __nbc;
1735 for (size_type __i = 0; __i < __nbc; ++__i)
1736 __bucket_list_[__i] = nullptr;
1737 __next_pointer __pp = __first_node_.__ptr();
1738 __next_pointer __cp = __pp->__next_;
1739 if (__cp != nullptr) {
1740 size_type __chash = std::__constrain_hash(__cp->__hash(), __nbc);
1741 __bucket_list_[__chash] = __pp;
1742 size_type __phash = __chash;
1743 for (__pp = __cp, void(), __cp = __cp->__next_; __cp != nullptr; __cp = __pp->__next_) {
1744 __chash = std::__constrain_hash(__cp->__hash(), __nbc);
1745 if (__chash == __phash)
1748 if (__bucket_list_[__chash] == nullptr) {
1749 __bucket_list_[__chash] = __pp;
1753 __next_pointer __np = __cp;
1754 if _LIBCPP_CONSTEXPR_SINCE_CXX17 (!_UniqueKeys) {
1755 for (; __np->__next_ != nullptr &&
1756 key_eq()(__cp->__upcast()->__get_value(), __np->__next_->__upcast()->__get_value());
1757 __np = __np->__next_)
1760 __pp->__next_ = __np->__next_;
1761 __np->__next_ = __bucket_list_[__chash]->__next_;
1762 __bucket_list_[__chash]->__next_ = __cp;
1770 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1771 template <class _Key>
1772 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1773 __hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) {
1774 size_t __hash = hash_function()(__k);
1775 size_type __bc = bucket_count();
1777 size_t __chash = std::__constrain_hash(__hash, __bc);
1778 __next_pointer __nd = __bucket_list_[__chash];
1779 if (__nd != nullptr) {
1780 for (__nd = __nd->__next_;
1781 __nd != nullptr && (__nd->__hash() == __hash || std::__constrain_hash(__nd->__hash(), __bc) == __chash);
1782 __nd = __nd->__next_) {
1783 if ((__nd->__hash() == __hash) && key_eq()(__nd->__upcast()->__get_value(), __k))
1784 return iterator(__nd);
1791 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1792 template <class _Key>
1793 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator
1794 __hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) const {
1795 size_t __hash = hash_function()(__k);
1796 size_type __bc = bucket_count();
1798 size_t __chash = std::__constrain_hash(__hash, __bc);
1799 __next_pointer __nd = __bucket_list_[__chash];
1800 if (__nd != nullptr) {
1801 for (__nd = __nd->__next_;
1802 __nd != nullptr && (__hash == __nd->__hash() || std::__constrain_hash(__nd->__hash(), __bc) == __chash);
1803 __nd = __nd->__next_) {
1804 if ((__nd->__hash() == __hash) && key_eq()(__nd->__upcast()->__get_value(), __k))
1805 return const_iterator(__nd);
1812 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1813 template <class... _Args>
1814 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
1815 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(_Args&&... __args) {
1816 static_assert(!__is_hash_value_type<_Args...>::value, "Construct cannot be called with a hash value type");
1817 __node_allocator& __na = __node_alloc();
1818 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1820 // Begin the lifetime of the node itself. Note that this doesn't begin the lifetime of the value
1821 // held inside the node, since we need to use the allocator's construct() method for that.
1823 // We don't use the allocator's construct() method to construct the node itself since the
1824 // Cpp17FooInsertable named requirements don't require the allocator's construct() method
1825 // to work on anything other than the value_type.
1826 std::__construct_at(std::addressof(*__h), /* next = */ nullptr, /* hash = */ 0);
1828 // Now construct the value_type using the allocator's construct() method.
1829 __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__get_value()), std::forward<_Args>(__args)...);
1830 __h.get_deleter().__value_constructed = true;
1832 __h->__hash_ = hash_function()(__h->__get_value());
1836 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1837 template <class _First, class... _Rest>
1838 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
1839 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node_hash(size_t __hash, _First&& __f, _Rest&&... __rest) {
1840 static_assert(!__is_hash_value_type<_First, _Rest...>::value, "Construct cannot be called with a hash value type");
1841 __node_allocator& __na = __node_alloc();
1842 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1843 std::__construct_at(std::addressof(*__h), /* next = */ nullptr, /* hash = */ __hash);
1844 __node_traits::construct(
1845 __na, _NodeTypes::__get_ptr(__h->__get_value()), std::forward<_First>(__f), std::forward<_Rest>(__rest)...);
1846 __h.get_deleter().__value_constructed = true;
1850 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1851 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1852 __hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __p) {
1853 __next_pointer __np = __p.__node_;
1854 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
1855 __p != end(), "unordered container::erase(iterator) called with a non-dereferenceable iterator");
1862 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1863 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1864 __hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __first, const_iterator __last) {
1865 for (const_iterator __p = __first; __first != __last; __p = __first) {
1869 __next_pointer __np = __last.__node_;
1870 return iterator(__np);
1873 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1874 template <class _Key>
1875 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
1876 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_unique(const _Key& __k) {
1877 iterator __i = find(__k);
1884 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1885 template <class _Key>
1886 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
1887 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_multi(const _Key& __k) {
1889 iterator __i = find(__k);
1891 iterator __e = end();
1895 } while (__i != __e && key_eq()(*__i, __k));
1900 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1901 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
1902 __hash_table<_Tp, _Hash, _Equal, _Alloc>::remove(const_iterator __p) _NOEXCEPT {
1904 __next_pointer __cn = __p.__node_;
1905 size_type __bc = bucket_count();
1906 size_t __chash = std::__constrain_hash(__cn->__hash(), __bc);
1907 // find previous node
1908 __next_pointer __pn = __bucket_list_[__chash];
1909 for (; __pn->__next_ != __cn; __pn = __pn->__next_)
1911 // Fix up __bucket_list_
1912 // if __pn is not in same bucket (before begin is not in same bucket) &&
1913 // if __cn->__next_ is not in same bucket (nullptr is not in same bucket)
1914 if (__pn == __first_node_.__ptr() || std::__constrain_hash(__pn->__hash(), __bc) != __chash) {
1915 if (__cn->__next_ == nullptr || std::__constrain_hash(__cn->__next_->__hash(), __bc) != __chash)
1916 __bucket_list_[__chash] = nullptr;
1918 // if __cn->__next_ is not in same bucket (nullptr is in same bucket)
1919 if (__cn->__next_ != nullptr) {
1920 size_t __nhash = std::__constrain_hash(__cn->__next_->__hash(), __bc);
1921 if (__nhash != __chash)
1922 __bucket_list_[__nhash] = __pn;
1925 __pn->__next_ = __cn->__next_;
1926 __cn->__next_ = nullptr;
1928 return __node_holder(__cn->__upcast(), _Dp(__node_alloc(), true));
1931 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1932 template <class _Key>
1933 inline typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
1934 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_unique(const _Key& __k) const {
1935 return static_cast<size_type>(find(__k) != end());
1938 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1939 template <class _Key>
1940 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
1941 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_multi(const _Key& __k) const {
1943 const_iterator __i = find(__k);
1945 const_iterator __e = end();
1949 } while (__i != __e && key_eq()(*__i, __k));
1954 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1955 template <class _Key>
1956 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator,
1957 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator>
1958 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique(const _Key& __k) {
1959 iterator __i = find(__k);
1963 return pair<iterator, iterator>(__i, __j);
1966 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1967 template <class _Key>
1968 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator,
1969 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator>
1970 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique(const _Key& __k) const {
1971 const_iterator __i = find(__k);
1972 const_iterator __j = __i;
1975 return pair<const_iterator, const_iterator>(__i, __j);
1978 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1979 template <class _Key>
1980 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator,
1981 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator>
1982 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi(const _Key& __k) {
1983 iterator __i = find(__k);
1986 iterator __e = end();
1989 } while (__j != __e && key_eq()(*__j, __k));
1991 return pair<iterator, iterator>(__i, __j);
1994 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1995 template <class _Key>
1996 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator,
1997 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator>
1998 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi(const _Key& __k) const {
1999 const_iterator __i = find(__k);
2000 const_iterator __j = __i;
2002 const_iterator __e = end();
2005 } while (__j != __e && key_eq()(*__j, __k));
2007 return pair<const_iterator, const_iterator>(__i, __j);
2010 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2011 void __hash_table<_Tp, _Hash, _Equal, _Alloc>::swap(__hash_table& __u)
2012 #if _LIBCPP_STD_VER <= 11
2013 _NOEXCEPT_(__is_nothrow_swappable_v<hasher>&& __is_nothrow_swappable_v<key_equal> &&
2014 (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value ||
2015 __is_nothrow_swappable_v<__pointer_allocator>) &&
2016 (!__node_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<__node_allocator>))
2018 _NOEXCEPT_(__is_nothrow_swappable_v<hasher>&& __is_nothrow_swappable_v<key_equal>)
2021 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
2022 __node_traits::propagate_on_container_swap::value || this->__node_alloc() == __u.__node_alloc(),
2023 "unordered container::swap: Either propagate_on_container_swap "
2024 "must be true or the allocators must compare equal");
2026 __node_pointer_pointer __npp = __bucket_list_.release();
2027 __bucket_list_.reset(__u.__bucket_list_.release());
2028 __u.__bucket_list_.reset(__npp);
2030 std::swap(__bucket_list_.get_deleter().size(), __u.__bucket_list_.get_deleter().size());
2031 std::__swap_allocator(__bucket_list_.get_deleter().__alloc(), __u.__bucket_list_.get_deleter().__alloc());
2032 std::__swap_allocator(__node_alloc(), __u.__node_alloc());
2033 std::swap(__first_node_.__next_, __u.__first_node_.__next_);
2035 swap(__size_, __u.__size_);
2036 swap(__hasher_, __u.__hasher_);
2037 swap(__max_load_factor_, __u.__max_load_factor_);
2038 swap(__key_eq_, __u.__key_eq_);
2040 __bucket_list_[std::__constrain_hash(__first_node_.__next_->__hash(), bucket_count())] = __first_node_.__ptr();
2042 __u.__bucket_list_[std::__constrain_hash(__u.__first_node_.__next_->__hash(), __u.bucket_count())] =
2043 __u.__first_node_.__ptr();
2046 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2047 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
2048 __hash_table<_Tp, _Hash, _Equal, _Alloc>::bucket_size(size_type __n) const {
2049 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
2050 __n < bucket_count(), "unordered container::bucket_size(n) called with n >= bucket_count()");
2051 __next_pointer __np = __bucket_list_[__n];
2052 size_type __bc = bucket_count();
2054 if (__np != nullptr) {
2055 for (__np = __np->__next_; __np != nullptr && std::__constrain_hash(__np->__hash(), __bc) == __n;
2056 __np = __np->__next_, (void)++__r)
2062 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2063 inline _LIBCPP_HIDE_FROM_ABI void
2064 swap(__hash_table<_Tp, _Hash, _Equal, _Alloc>& __x, __hash_table<_Tp, _Hash, _Equal, _Alloc>& __y)
2065 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
2069 _LIBCPP_END_NAMESPACE_STD
2073 #endif // _LIBCPP___HASH_TABLE