libcxx/include/__hash_table

   1 // -*- C++ -*-
   2 //===----------------------------------------------------------------------===//
   3 //
   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
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #ifndef _LIBCPP___HASH_TABLE
  11 #define _LIBCPP___HASH_TABLE
  12
  13 #include <__algorithm/max.h>
  14 #include <__algorithm/min.h>
  15 #include <__assert>
  16 #include <__bit/countl.h>
  17 #include <__config>
  18 #include <__functional/hash.h>
  19 #include <__functional/invoke.h>
  20 #include <__iterator/iterator_traits.h>
  21 #include <__memory/addressof.h>
  22 #include <__memory/allocator_traits.h>
  23 #include <__memory/compressed_pair.h>
  24 #include <__memory/construct_at.h>
  25 #include <__memory/pointer_traits.h>
  26 #include <__memory/swap_allocator.h>
  27 #include <__memory/unique_ptr.h>
  28 #include <__type_traits/can_extract_key.h>
  29 #include <__type_traits/conditional.h>
  30 #include <__type_traits/is_const.h>
  31 #include <__type_traits/is_copy_constructible.h>
  32 #include <__type_traits/is_nothrow_constructible.h>
  33 #include <__type_traits/is_nothrow_copy_constructible.h>
  34 #include <__type_traits/is_nothrow_default_constructible.h>
  35 #include <__type_traits/is_nothrow_move_assignable.h>
  36 #include <__type_traits/is_nothrow_move_constructible.h>
  37 #include <__type_traits/is_pointer.h>
  38 #include <__type_traits/is_reference.h>
  39 #include <__type_traits/is_swappable.h>
  40 #include <__type_traits/remove_const.h>
  41 #include <__type_traits/remove_cvref.h>
  42 #include <__utility/forward.h>
  43 #include <__utility/move.h>
  44 #include <__utility/pair.h>
  45 #include <__utility/swap.h>
  46 #include <cmath>
  47 #include <cstring>
  48 #include <initializer_list>
  49 #include <new> // __launder
  50
  51 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
  52 #  pragma GCC system_header
  53 #endif
  54
  55 _LIBCPP_PUSH_MACROS
  56 #include <__undef_macros>
  57
  58
  59 _LIBCPP_BEGIN_NAMESPACE_STD
  60
  61 template <class _Key, class _Tp>
  62 struct __hash_value_type;
  63
  64 template <class _Tp>
  65 struct __is_hash_value_type_imp : false_type {};
  66
  67 template <class _Key, class _Value>
  68 struct __is_hash_value_type_imp<__hash_value_type<_Key, _Value> > : true_type {};
  69
  70 template <class ..._Args>
  71 struct __is_hash_value_type : false_type {};
  72
  73 template <class _One>
  74 struct __is_hash_value_type<_One> : __is_hash_value_type_imp<__remove_cvref_t<_One> > {};
  75
  76 _LIBCPP_EXPORTED_FROM_ABI size_t __next_prime(size_t __n);
  77
  78 template <class _NodePtr>
  79 struct __hash_node_base
  80 {
  81     typedef typename pointer_traits<_NodePtr>::element_type __node_type;
  82     typedef __hash_node_base __first_node;
  83     typedef __rebind_pointer_t<_NodePtr, __first_node> __node_base_pointer;
  84     typedef _NodePtr __node_pointer;
  85
  86 #if defined(_LIBCPP_ABI_FIX_UNORDERED_NODE_POINTER_UB)
  87   typedef __node_base_pointer __next_pointer;
  88 #else
  89     typedef __conditional_t<is_pointer<__node_pointer>::value, __node_base_pointer, __node_pointer> __next_pointer;
  90 #endif
  91
  92     __next_pointer    __next_;
  93
  94     _LIBCPP_INLINE_VISIBILITY
  95     __next_pointer __ptr() _NOEXCEPT {
  96         return static_cast<__next_pointer>(
  97             pointer_traits<__node_base_pointer>::pointer_to(*this));
  98     }
  99
 100     _LIBCPP_INLINE_VISIBILITY
 101     __node_pointer __upcast() _NOEXCEPT {
 102         return static_cast<__node_pointer>(
 103             pointer_traits<__node_base_pointer>::pointer_to(*this));
 104     }
 105
 106     _LIBCPP_INLINE_VISIBILITY
 107     size_t __hash() const _NOEXCEPT {
 108         return static_cast<__node_type const&>(*this).__hash_;
 109     }
 110
 111     _LIBCPP_INLINE_VISIBILITY __hash_node_base() _NOEXCEPT : __next_(nullptr) {}
 112     _LIBCPP_HIDE_FROM_ABI explicit __hash_node_base(__next_pointer __next) _NOEXCEPT : __next_(__next) {}
 113 };
 114
 115 template <class _Tp, class _VoidPtr>
 116 struct __hash_node
 117     : public __hash_node_base
 118              <
 119                  __rebind_pointer_t<_VoidPtr, __hash_node<_Tp, _VoidPtr> >
 120              >
 121 {
 122     typedef _Tp __node_value_type;
 123     using _Base = __hash_node_base<__rebind_pointer_t<_VoidPtr, __hash_node<_Tp, _VoidPtr> > >;
 124     using __next_pointer = typename _Base::__next_pointer;
 125
 126     size_t            __hash_;
 127
 128     // We allow starting the lifetime of nodes without initializing the value held by the node,
 129     // since that is handled by the hash table itself in order to be allocator-aware.
 130 #ifndef _LIBCPP_CXX03_LANG
 131 private:
 132     union {
 133         _Tp __value_;
 134     };
 135
 136 public:
 137     _LIBCPP_HIDE_FROM_ABI _Tp& __get_value() { return __value_; }
 138 #else
 139 private:
 140     _ALIGNAS_TYPE(_Tp) char __buffer_[sizeof(_Tp)];
 141
 142 public:
 143     _LIBCPP_HIDE_FROM_ABI _Tp& __get_value() {
 144         return *std::__launder(reinterpret_cast<_Tp*>(&__buffer_));
 145     }
 146 #endif
 147
 148     _LIBCPP_HIDE_FROM_ABI explicit __hash_node(__next_pointer __next, size_t __hash) : _Base(__next), __hash_(__hash) {}
 149     _LIBCPP_HIDE_FROM_ABI ~__hash_node() {}
 150 };
 151
 152 inline _LIBCPP_INLINE_VISIBILITY
 153 bool
 154 __is_hash_power2(size_t __bc)
 155 {
 156     return __bc > 2 && !(__bc & (__bc - 1));
 157 }
 158
 159 inline _LIBCPP_INLINE_VISIBILITY
 160 size_t
 161 __constrain_hash(size_t __h, size_t __bc)
 162 {
 163     return !(__bc & (__bc - 1)) ? __h & (__bc - 1) :
 164         (__h < __bc ? __h : __h % __bc);
 165 }
 166
 167 inline _LIBCPP_INLINE_VISIBILITY
 168 size_t
 169 __next_hash_pow2(size_t __n)
 170 {
 171     return __n < 2 ? __n : (size_t(1) << (numeric_limits<size_t>::digits - __libcpp_clz(__n-1)));
 172 }
 173
 174
 175 template <class _Tp, class _Hash, class _Equal, class _Alloc> class __hash_table;
 176
 177 template <class _NodePtr>      class _LIBCPP_TEMPLATE_VIS __hash_iterator;
 178 template <class _ConstNodePtr> class _LIBCPP_TEMPLATE_VIS __hash_const_iterator;
 179 template <class _NodePtr>      class _LIBCPP_TEMPLATE_VIS __hash_local_iterator;
 180 template <class _ConstNodePtr> class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator;
 181 template <class _HashIterator> class _LIBCPP_TEMPLATE_VIS __hash_map_iterator;
 182 template <class _HashIterator> class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator;
 183
 184 template <class _Tp>
 185 struct __hash_key_value_types {
 186   static_assert(!is_reference<_Tp>::value && !is_const<_Tp>::value, "");
 187   typedef _Tp key_type;
 188   typedef _Tp __node_value_type;
 189   typedef _Tp __container_value_type;
 190   static const bool __is_map = false;
 191
 192   _LIBCPP_INLINE_VISIBILITY
 193   static key_type const& __get_key(_Tp const& __v) {
 194     return __v;
 195   }
 196   _LIBCPP_INLINE_VISIBILITY
 197   static __container_value_type const& __get_value(__node_value_type const& __v) {
 198     return __v;
 199   }
 200   _LIBCPP_INLINE_VISIBILITY
 201   static __container_value_type* __get_ptr(__node_value_type& __n) {
 202     return _VSTD::addressof(__n);
 203   }
 204   _LIBCPP_INLINE_VISIBILITY
 205   static __container_value_type&& __move(__node_value_type& __v) {
 206     return _VSTD::move(__v);
 207   }
 208 };
 209
 210 template <class _Key, class _Tp>
 211 struct __hash_key_value_types<__hash_value_type<_Key, _Tp> > {
 212   typedef _Key                                         key_type;
 213   typedef _Tp                                          mapped_type;
 214   typedef __hash_value_type<_Key, _Tp>                 __node_value_type;
 215   typedef pair<const _Key, _Tp>                        __container_value_type;
 216   typedef __container_value_type                       __map_value_type;
 217   static const bool __is_map = true;
 218
 219   _LIBCPP_INLINE_VISIBILITY
 220   static key_type const& __get_key(__container_value_type const& __v) {
 221     return __v.first;
 222   }
 223
 224   template <class _Up, __enable_if_t<__is_same_uncvref<_Up, __node_value_type>::value, int> = 0>
 225   _LIBCPP_INLINE_VISIBILITY
 226   static __container_value_type const&
 227   __get_value(_Up& __t) {
 228     return __t.__get_value();
 229   }
 230
 231   template <class _Up, __enable_if_t<__is_same_uncvref<_Up, __container_value_type>::value, int> = 0>
 232   _LIBCPP_INLINE_VISIBILITY
 233   static __container_value_type const&
 234   __get_value(_Up& __t) {
 235     return __t;
 236   }
 237
 238   _LIBCPP_INLINE_VISIBILITY
 239   static __container_value_type* __get_ptr(__node_value_type& __n) {
 240     return _VSTD::addressof(__n.__get_value());
 241   }
 242   _LIBCPP_INLINE_VISIBILITY
 243   static pair<key_type&&, mapped_type&&> __move(__node_value_type& __v) {
 244     return __v.__move();
 245   }
 246 };
 247
 248 template <class _Tp, class _AllocPtr, class _KVTypes = __hash_key_value_types<_Tp>,
 249           bool = _KVTypes::__is_map>
 250 struct __hash_map_pointer_types {};
 251
 252 template <class _Tp, class _AllocPtr, class _KVTypes>
 253 struct __hash_map_pointer_types<_Tp, _AllocPtr, _KVTypes, true> {
 254   typedef typename _KVTypes::__map_value_type   _Mv;
 255   typedef __rebind_pointer_t<_AllocPtr, _Mv>
 256                                                        __map_value_type_pointer;
 257   typedef __rebind_pointer_t<_AllocPtr, const _Mv>
 258                                                  __const_map_value_type_pointer;
 259 };
 260
 261 template <class _NodePtr, class _NodeT = typename pointer_traits<_NodePtr>::element_type>
 262 struct __hash_node_types;
 263
 264 template <class _NodePtr, class _Tp, class _VoidPtr>
 265 struct __hash_node_types<_NodePtr, __hash_node<_Tp, _VoidPtr> >
 266     : public __hash_key_value_types<_Tp>, __hash_map_pointer_types<_Tp, _VoidPtr>
 267
 268 {
 269   typedef __hash_key_value_types<_Tp>           __base;
 270
 271 public:
 272   typedef ptrdiff_t difference_type;
 273   typedef size_t size_type;
 274
 275   typedef __rebind_pointer_t<_NodePtr, void>       __void_pointer;
 276
 277   typedef typename pointer_traits<_NodePtr>::element_type       __node_type;
 278   typedef _NodePtr                                              __node_pointer;
 279
 280   typedef __hash_node_base<__node_pointer>                      __node_base_type;
 281   typedef __rebind_pointer_t<_NodePtr, __node_base_type>
 282                                                              __node_base_pointer;
 283
 284   typedef typename __node_base_type::__next_pointer          __next_pointer;
 285
 286   typedef _Tp                                                 __node_value_type;
 287   typedef __rebind_pointer_t<_VoidPtr, __node_value_type>
 288                                                       __node_value_type_pointer;
 289   typedef __rebind_pointer_t<_VoidPtr, const __node_value_type>
 290                                                 __const_node_value_type_pointer;
 291
 292 private:
 293     static_assert(!is_const<__node_type>::value,
 294                 "_NodePtr should never be a pointer to const");
 295     static_assert((is_same<typename pointer_traits<_VoidPtr>::element_type, void>::value),
 296                   "_VoidPtr does not point to unqualified void type");
 297     static_assert((is_same<__rebind_pointer_t<_VoidPtr, __node_type>,
 298                           _NodePtr>::value), "_VoidPtr does not rebind to _NodePtr.");
 299 };
 300
 301 template <class _HashIterator>
 302 struct __hash_node_types_from_iterator;
 303 template <class _NodePtr>
 304 struct __hash_node_types_from_iterator<__hash_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {};
 305 template <class _NodePtr>
 306 struct __hash_node_types_from_iterator<__hash_const_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {};
 307 template <class _NodePtr>
 308 struct __hash_node_types_from_iterator<__hash_local_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {};
 309 template <class _NodePtr>
 310 struct __hash_node_types_from_iterator<__hash_const_local_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {};
 311
 312
 313 template <class _NodeValueTp, class _VoidPtr>
 314 struct __make_hash_node_types {
 315   typedef __hash_node<_NodeValueTp, _VoidPtr> _NodeTp;
 316   typedef __rebind_pointer_t<_VoidPtr, _NodeTp> _NodePtr;
 317   typedef __hash_node_types<_NodePtr> type;
 318 };
 319
 320 template <class _NodePtr>
 321 class _LIBCPP_TEMPLATE_VIS __hash_iterator
 322 {
 323     typedef __hash_node_types<_NodePtr> _NodeTypes;
 324     typedef _NodePtr                            __node_pointer;
 325     typedef typename _NodeTypes::__next_pointer __next_pointer;
 326
 327     __next_pointer            __node_;
 328
 329 public:
 330     typedef forward_iterator_tag                           iterator_category;
 331     typedef typename _NodeTypes::__node_value_type         value_type;
 332     typedef typename _NodeTypes::difference_type           difference_type;
 333     typedef value_type&                                    reference;
 334     typedef typename _NodeTypes::__node_value_type_pointer pointer;
 335
 336     _LIBCPP_INLINE_VISIBILITY __hash_iterator() _NOEXCEPT : __node_(nullptr) {
 337     }
 338
 339     _LIBCPP_INLINE_VISIBILITY
 340     reference operator*() const {
 341         return __node_->__upcast()->__get_value();
 342     }
 343
 344     _LIBCPP_INLINE_VISIBILITY
 345     pointer operator->() const {
 346         return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__get_value());
 347     }
 348
 349     _LIBCPP_INLINE_VISIBILITY
 350     __hash_iterator& operator++() {
 351         __node_ = __node_->__next_;
 352         return *this;
 353     }
 354
 355     _LIBCPP_INLINE_VISIBILITY
 356     __hash_iterator operator++(int)
 357     {
 358         __hash_iterator __t(*this);
 359         ++(*this);
 360         return __t;
 361     }
 362
 363     friend _LIBCPP_INLINE_VISIBILITY
 364     bool operator==(const __hash_iterator& __x, const __hash_iterator& __y)
 365     {
 366         return __x.__node_ == __y.__node_;
 367     }
 368     friend _LIBCPP_INLINE_VISIBILITY
 369     bool operator!=(const __hash_iterator& __x, const __hash_iterator& __y)
 370         {return !(__x == __y);}
 371
 372 private:
 373     _LIBCPP_INLINE_VISIBILITY
 374     explicit __hash_iterator(__next_pointer __node) _NOEXCEPT
 375         : __node_(__node)
 376         {
 377         }
 378
 379     template <class, class, class, class> friend class __hash_table;
 380     template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator;
 381     template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_map_iterator;
 382     template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_map;
 383     template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
 384 };
 385
 386 template <class _NodePtr>
 387 class _LIBCPP_TEMPLATE_VIS __hash_const_iterator
 388 {
 389     static_assert(!is_const<typename pointer_traits<_NodePtr>::element_type>::value, "");
 390     typedef __hash_node_types<_NodePtr> _NodeTypes;
 391     typedef _NodePtr                            __node_pointer;
 392     typedef typename _NodeTypes::__next_pointer __next_pointer;
 393
 394     __next_pointer __node_;
 395
 396 public:
 397     typedef __hash_iterator<_NodePtr> __non_const_iterator;
 398
 399     typedef forward_iterator_tag                                 iterator_category;
 400     typedef typename _NodeTypes::__node_value_type               value_type;
 401     typedef typename _NodeTypes::difference_type                 difference_type;
 402     typedef const value_type&                                    reference;
 403     typedef typename _NodeTypes::__const_node_value_type_pointer pointer;
 404
 405
 406     _LIBCPP_INLINE_VISIBILITY __hash_const_iterator() _NOEXCEPT : __node_(nullptr) {
 407     }
 408
 409     _LIBCPP_INLINE_VISIBILITY
 410     __hash_const_iterator(const __non_const_iterator& __x) _NOEXCEPT
 411         : __node_(__x.__node_)
 412     {
 413     }
 414
 415     _LIBCPP_INLINE_VISIBILITY
 416     reference operator*() const {
 417         return __node_->__upcast()->__get_value();
 418     }
 419     _LIBCPP_INLINE_VISIBILITY
 420     pointer operator->() const {
 421         return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__get_value());
 422     }
 423
 424     _LIBCPP_INLINE_VISIBILITY
 425     __hash_const_iterator& operator++() {
 426         __node_ = __node_->__next_;
 427         return *this;
 428     }
 429
 430     _LIBCPP_INLINE_VISIBILITY
 431     __hash_const_iterator operator++(int)
 432     {
 433         __hash_const_iterator __t(*this);
 434         ++(*this);
 435         return __t;
 436     }
 437
 438     friend _LIBCPP_INLINE_VISIBILITY
 439     bool operator==(const __hash_const_iterator& __x, const __hash_const_iterator& __y)
 440     {
 441         return __x.__node_ == __y.__node_;
 442     }
 443     friend _LIBCPP_INLINE_VISIBILITY
 444     bool operator!=(const __hash_const_iterator& __x, const __hash_const_iterator& __y)
 445         {return !(__x == __y);}
 446
 447 private:
 448     _LIBCPP_INLINE_VISIBILITY
 449     explicit __hash_const_iterator(__next_pointer __node) _NOEXCEPT
 450         : __node_(__node)
 451         {
 452         }
 453
 454     template <class, class, class, class> friend class __hash_table;
 455     template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator;
 456     template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_map;
 457     template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
 458 };
 459
 460 template <class _NodePtr>
 461 class _LIBCPP_TEMPLATE_VIS __hash_local_iterator
 462 {
 463     typedef __hash_node_types<_NodePtr> _NodeTypes;
 464     typedef _NodePtr                            __node_pointer;
 465     typedef typename _NodeTypes::__next_pointer __next_pointer;
 466
 467     __next_pointer         __node_;
 468     size_t                 __bucket_;
 469     size_t                 __bucket_count_;
 470
 471 public:
 472     typedef forward_iterator_tag                                iterator_category;
 473     typedef typename _NodeTypes::__node_value_type              value_type;
 474     typedef typename _NodeTypes::difference_type                difference_type;
 475     typedef value_type&                                         reference;
 476     typedef typename _NodeTypes::__node_value_type_pointer      pointer;
 477
 478     _LIBCPP_INLINE_VISIBILITY __hash_local_iterator() _NOEXCEPT : __node_(nullptr) {
 479     }
 480
 481     _LIBCPP_INLINE_VISIBILITY
 482     reference operator*() const {
 483         return __node_->__upcast()->__get_value();
 484     }
 485
 486     _LIBCPP_INLINE_VISIBILITY
 487     pointer operator->() const {
 488         return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__get_value());
 489     }
 490
 491     _LIBCPP_INLINE_VISIBILITY
 492     __hash_local_iterator& operator++() {
 493         __node_ = __node_->__next_;
 494         if (__node_ != nullptr && std::__constrain_hash(__node_->__hash(), __bucket_count_) != __bucket_)
 495             __node_ = nullptr;
 496         return *this;
 497     }
 498
 499     _LIBCPP_INLINE_VISIBILITY
 500     __hash_local_iterator operator++(int)
 501     {
 502         __hash_local_iterator __t(*this);
 503         ++(*this);
 504         return __t;
 505     }
 506
 507     friend _LIBCPP_INLINE_VISIBILITY
 508     bool operator==(const __hash_local_iterator& __x, const __hash_local_iterator& __y)
 509     {
 510         return __x.__node_ == __y.__node_;
 511     }
 512     friend _LIBCPP_INLINE_VISIBILITY
 513     bool operator!=(const __hash_local_iterator& __x, const __hash_local_iterator& __y)
 514         {return !(__x == __y);}
 515
 516 private:
 517     _LIBCPP_INLINE_VISIBILITY
 518     explicit __hash_local_iterator(__next_pointer __node, size_t __bucket,
 519                                    size_t __bucket_count) _NOEXCEPT
 520         : __node_(__node),
 521           __bucket_(__bucket),
 522           __bucket_count_(__bucket_count)
 523         {
 524             if (__node_ != nullptr)
 525                 __node_ = __node_->__next_;
 526         }
 527
 528     template <class, class, class, class> friend class __hash_table;
 529     template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator;
 530     template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_map_iterator;
 531 };
 532
 533 template <class _ConstNodePtr>
 534 class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator
 535 {
 536     typedef __hash_node_types<_ConstNodePtr> _NodeTypes;
 537     typedef _ConstNodePtr                       __node_pointer;
 538     typedef typename _NodeTypes::__next_pointer __next_pointer;
 539
 540     __next_pointer         __node_;
 541     size_t                 __bucket_;
 542     size_t                 __bucket_count_;
 543
 544     typedef pointer_traits<__node_pointer>          __pointer_traits;
 545     typedef typename __pointer_traits::element_type __node;
 546     typedef __remove_const_t<__node>                  __non_const_node;
 547     typedef __rebind_pointer_t<__node_pointer, __non_const_node>
 548         __non_const_node_pointer;
 549 public:
 550     typedef __hash_local_iterator<__non_const_node_pointer>
 551                                                     __non_const_iterator;
 552
 553     typedef forward_iterator_tag                                 iterator_category;
 554     typedef typename _NodeTypes::__node_value_type               value_type;
 555     typedef typename _NodeTypes::difference_type                 difference_type;
 556     typedef const value_type&                                    reference;
 557     typedef typename _NodeTypes::__const_node_value_type_pointer pointer;
 558
 559
 560     _LIBCPP_INLINE_VISIBILITY __hash_const_local_iterator() _NOEXCEPT : __node_(nullptr) {
 561     }
 562
 563     _LIBCPP_INLINE_VISIBILITY
 564     __hash_const_local_iterator(const __non_const_iterator& __x) _NOEXCEPT
 565         : __node_(__x.__node_),
 566           __bucket_(__x.__bucket_),
 567           __bucket_count_(__x.__bucket_count_)
 568     {
 569     }
 570
 571     _LIBCPP_INLINE_VISIBILITY
 572     reference operator*() const {
 573         return __node_->__upcast()->__get_value();
 574     }
 575
 576     _LIBCPP_INLINE_VISIBILITY
 577     pointer operator->() const {
 578         return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__get_value());
 579     }
 580
 581     _LIBCPP_INLINE_VISIBILITY
 582     __hash_const_local_iterator& operator++() {
 583         __node_ = __node_->__next_;
 584         if (__node_ != nullptr && std::__constrain_hash(__node_->__hash(), __bucket_count_) != __bucket_)
 585             __node_ = nullptr;
 586         return *this;
 587     }
 588
 589     _LIBCPP_INLINE_VISIBILITY
 590     __hash_const_local_iterator operator++(int)
 591     {
 592         __hash_const_local_iterator __t(*this);
 593         ++(*this);
 594         return __t;
 595     }
 596
 597     friend _LIBCPP_INLINE_VISIBILITY
 598     bool operator==(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y)
 599     {
 600         return __x.__node_ == __y.__node_;
 601     }
 602     friend _LIBCPP_INLINE_VISIBILITY
 603     bool operator!=(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y)
 604         {return !(__x == __y);}
 605
 606 private:
 607     _LIBCPP_INLINE_VISIBILITY
 608     explicit __hash_const_local_iterator(__next_pointer __node_ptr, size_t __bucket,
 609                                          size_t __bucket_count) _NOEXCEPT
 610         : __node_(__node_ptr),
 611           __bucket_(__bucket),
 612           __bucket_count_(__bucket_count)
 613         {
 614             if (__node_ != nullptr)
 615                 __node_ = __node_->__next_;
 616         }
 617
 618     template <class, class, class, class> friend class __hash_table;
 619     template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator;
 620 };
 621
 622 template <class _Alloc>
 623 class __bucket_list_deallocator
 624 {
 625     typedef _Alloc                                          allocator_type;
 626     typedef allocator_traits<allocator_type>                __alloc_traits;
 627     typedef typename __alloc_traits::size_type              size_type;
 628
 629     __compressed_pair<size_type, allocator_type> __data_;
 630 public:
 631     typedef typename __alloc_traits::pointer pointer;
 632
 633     _LIBCPP_INLINE_VISIBILITY
 634     __bucket_list_deallocator()
 635         _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
 636         : __data_(0, __default_init_tag()) {}
 637
 638     _LIBCPP_INLINE_VISIBILITY
 639     __bucket_list_deallocator(const allocator_type& __a, size_type __size)
 640         _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value)
 641         : __data_(__size, __a) {}
 642
 643     _LIBCPP_INLINE_VISIBILITY
 644     __bucket_list_deallocator(__bucket_list_deallocator&& __x)
 645         _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
 646         : __data_(_VSTD::move(__x.__data_))
 647     {
 648         __x.size() = 0;
 649     }
 650
 651     _LIBCPP_INLINE_VISIBILITY
 652     size_type& size() _NOEXCEPT {return __data_.first();}
 653     _LIBCPP_INLINE_VISIBILITY
 654     size_type  size() const _NOEXCEPT {return __data_.first();}
 655
 656     _LIBCPP_INLINE_VISIBILITY
 657     allocator_type& __alloc() _NOEXCEPT {return __data_.second();}
 658     _LIBCPP_INLINE_VISIBILITY
 659     const allocator_type& __alloc() const _NOEXCEPT {return __data_.second();}
 660
 661     _LIBCPP_INLINE_VISIBILITY
 662     void operator()(pointer __p) _NOEXCEPT
 663     {
 664         __alloc_traits::deallocate(__alloc(), __p, size());
 665     }
 666 };
 667
 668 template <class _Alloc> class __hash_map_node_destructor;
 669
 670 template <class _Alloc>
 671 class __hash_node_destructor
 672 {
 673     typedef _Alloc                                          allocator_type;
 674     typedef allocator_traits<allocator_type>                __alloc_traits;
 675
 676 public:
 677     typedef typename __alloc_traits::pointer                pointer;
 678 private:
 679     typedef __hash_node_types<pointer> _NodeTypes;
 680
 681     allocator_type& __na_;
 682
 683 public:
 684     bool __value_constructed;
 685
 686     _LIBCPP_HIDE_FROM_ABI __hash_node_destructor(__hash_node_destructor const&) = default;
 687     _LIBCPP_HIDE_FROM_ABI __hash_node_destructor& operator=(const __hash_node_destructor&) = delete;
 688
 689
 690     _LIBCPP_INLINE_VISIBILITY
 691     explicit __hash_node_destructor(allocator_type& __na,
 692                                     bool __constructed = false) _NOEXCEPT
 693         : __na_(__na),
 694           __value_constructed(__constructed)
 695         {}
 696
 697     _LIBCPP_INLINE_VISIBILITY
 698     void operator()(pointer __p) _NOEXCEPT
 699     {
 700         if (__value_constructed) {
 701             __alloc_traits::destroy(__na_, _NodeTypes::__get_ptr(__p->__get_value()));
 702             std::__destroy_at(std::addressof(*__p));
 703         }
 704         if (__p)
 705             __alloc_traits::deallocate(__na_, __p, 1);
 706     }
 707
 708     template <class> friend class __hash_map_node_destructor;
 709 };
 710
 711 #if _LIBCPP_STD_VER >= 17
 712 template <class _NodeType, class _Alloc>
 713 struct __generic_container_node_destructor;
 714
 715 template <class _Tp, class _VoidPtr, class _Alloc>
 716 struct __generic_container_node_destructor<__hash_node<_Tp, _VoidPtr>, _Alloc>
 717     : __hash_node_destructor<_Alloc>
 718 {
 719     using __hash_node_destructor<_Alloc>::__hash_node_destructor;
 720 };
 721 #endif
 722
 723 template <class _Key, class _Hash, class _Equal>
 724 struct __enforce_unordered_container_requirements {
 725 #ifndef _LIBCPP_CXX03_LANG
 726     static_assert(__check_hash_requirements<_Key, _Hash>::value,
 727     "the specified hash does not meet the Hash requirements");
 728     static_assert(is_copy_constructible<_Equal>::value,
 729     "the specified comparator is required to be copy constructible");
 730 #endif
 731     typedef int type;
 732 };
 733
 734 template <class _Key, class _Hash, class _Equal>
 735 #ifndef _LIBCPP_CXX03_LANG
 736     _LIBCPP_DIAGNOSE_WARNING(!__invokable<_Equal const&, _Key const&, _Key const&>::value,
 737     "the specified comparator type does not provide a viable const call operator")
 738     _LIBCPP_DIAGNOSE_WARNING(!__invokable<_Hash const&, _Key const&>::value,
 739     "the specified hash functor does not provide a viable const call operator")
 740 #endif
 741 typename __enforce_unordered_container_requirements<_Key, _Hash, _Equal>::type
 742 __diagnose_unordered_container_requirements(int);
 743
 744 // This dummy overload is used so that the compiler won't emit a spurious
 745 // "no matching function for call to __diagnose_unordered_xxx" diagnostic
 746 // when the overload above causes a hard error.
 747 template <class _Key, class _Hash, class _Equal>
 748 int __diagnose_unordered_container_requirements(void*);
 749
 750 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 751 class __hash_table
 752 {
 753 public:
 754     typedef _Tp    value_type;
 755     typedef _Hash  hasher;
 756     typedef _Equal key_equal;
 757     typedef _Alloc allocator_type;
 758
 759 private:
 760     typedef allocator_traits<allocator_type> __alloc_traits;
 761     typedef typename
 762       __make_hash_node_types<value_type, typename __alloc_traits::void_pointer>::type
 763                                                                      _NodeTypes;
 764 public:
 765
 766     typedef typename _NodeTypes::__node_value_type           __node_value_type;
 767     typedef typename _NodeTypes::__container_value_type      __container_value_type;
 768     typedef typename _NodeTypes::key_type                    key_type;
 769     typedef value_type&                              reference;
 770     typedef const value_type&                        const_reference;
 771     typedef typename __alloc_traits::pointer         pointer;
 772     typedef typename __alloc_traits::const_pointer   const_pointer;
 773 #ifndef _LIBCPP_ABI_FIX_UNORDERED_CONTAINER_SIZE_TYPE
 774     typedef typename __alloc_traits::size_type       size_type;
 775 #else
 776     typedef typename _NodeTypes::size_type           size_type;
 777 #endif
 778     typedef typename _NodeTypes::difference_type     difference_type;
 779 public:
 780     // Create __node
 781
 782     typedef typename _NodeTypes::__node_type __node;
 783     typedef __rebind_alloc<__alloc_traits, __node>   __node_allocator;
 784     typedef allocator_traits<__node_allocator>       __node_traits;
 785     typedef typename _NodeTypes::__void_pointer      __void_pointer;
 786     typedef typename _NodeTypes::__node_pointer      __node_pointer;
 787     typedef typename _NodeTypes::__node_pointer      __node_const_pointer;
 788     typedef typename _NodeTypes::__node_base_type    __first_node;
 789     typedef typename _NodeTypes::__node_base_pointer __node_base_pointer;
 790     typedef typename _NodeTypes::__next_pointer      __next_pointer;
 791
 792 private:
 793     // check for sane allocator pointer rebinding semantics. Rebinding the
 794     // allocator for a new pointer type should be exactly the same as rebinding
 795     // the pointer using 'pointer_traits'.
 796     static_assert((is_same<__node_pointer, typename __node_traits::pointer>::value),
 797                   "Allocator does not rebind pointers in a sane manner.");
 798     typedef __rebind_alloc<__node_traits, __first_node> __node_base_allocator;
 799     typedef allocator_traits<__node_base_allocator> __node_base_traits;
 800     static_assert((is_same<__node_base_pointer, typename __node_base_traits::pointer>::value),
 801                  "Allocator does not rebind pointers in a sane manner.");
 802
 803 private:
 804
 805     typedef __rebind_alloc<__node_traits, __next_pointer>  __pointer_allocator;
 806     typedef __bucket_list_deallocator<__pointer_allocator> __bucket_list_deleter;
 807     typedef unique_ptr<__next_pointer[], __bucket_list_deleter> __bucket_list;
 808     typedef allocator_traits<__pointer_allocator>          __pointer_alloc_traits;
 809     typedef typename __bucket_list_deleter::pointer       __node_pointer_pointer;
 810
 811     // --- Member data begin ---
 812     __bucket_list                                         __bucket_list_;
 813     __compressed_pair<__first_node, __node_allocator>     __p1_;
 814     __compressed_pair<size_type, hasher>                  __p2_;
 815     __compressed_pair<float, key_equal>                   __p3_;
 816     // --- Member data end ---
 817
 818     _LIBCPP_INLINE_VISIBILITY
 819     size_type& size() _NOEXCEPT {return __p2_.first();}
 820 public:
 821     _LIBCPP_INLINE_VISIBILITY
 822     size_type  size() const _NOEXCEPT {return __p2_.first();}
 823
 824     _LIBCPP_INLINE_VISIBILITY
 825     hasher& hash_function() _NOEXCEPT {return __p2_.second();}
 826     _LIBCPP_INLINE_VISIBILITY
 827     const hasher& hash_function() const _NOEXCEPT {return __p2_.second();}
 828
 829     _LIBCPP_INLINE_VISIBILITY
 830     float& max_load_factor() _NOEXCEPT {return __p3_.first();}
 831     _LIBCPP_INLINE_VISIBILITY
 832     float  max_load_factor() const _NOEXCEPT {return __p3_.first();}
 833
 834     _LIBCPP_INLINE_VISIBILITY
 835     key_equal& key_eq() _NOEXCEPT {return __p3_.second();}
 836     _LIBCPP_INLINE_VISIBILITY
 837     const key_equal& key_eq() const _NOEXCEPT {return __p3_.second();}
 838
 839     _LIBCPP_INLINE_VISIBILITY
 840     __node_allocator& __node_alloc() _NOEXCEPT {return __p1_.second();}
 841     _LIBCPP_INLINE_VISIBILITY
 842     const __node_allocator& __node_alloc() const _NOEXCEPT
 843         {return __p1_.second();}
 844
 845 public:
 846     typedef __hash_iterator<__node_pointer>                   iterator;
 847     typedef __hash_const_iterator<__node_pointer>             const_iterator;
 848     typedef __hash_local_iterator<__node_pointer>             local_iterator;
 849     typedef __hash_const_local_iterator<__node_pointer>       const_local_iterator;
 850
 851     _LIBCPP_INLINE_VISIBILITY
 852     __hash_table()
 853         _NOEXCEPT_(
 854             is_nothrow_default_constructible<__bucket_list>::value &&
 855             is_nothrow_default_constructible<__first_node>::value &&
 856             is_nothrow_default_constructible<__node_allocator>::value &&
 857             is_nothrow_default_constructible<hasher>::value &&
 858             is_nothrow_default_constructible<key_equal>::value);
 859     _LIBCPP_INLINE_VISIBILITY
 860     __hash_table(const hasher& __hf, const key_equal& __eql);
 861     _LIBCPP_HIDE_FROM_ABI __hash_table(const hasher& __hf, const key_equal& __eql,
 862                  const allocator_type& __a);
 863     _LIBCPP_HIDE_FROM_ABI explicit __hash_table(const allocator_type& __a);
 864     _LIBCPP_HIDE_FROM_ABI __hash_table(const __hash_table& __u);
 865     _LIBCPP_HIDE_FROM_ABI __hash_table(const __hash_table& __u, const allocator_type& __a);
 866     _LIBCPP_HIDE_FROM_ABI __hash_table(__hash_table&& __u)
 867         _NOEXCEPT_(
 868             is_nothrow_move_constructible<__bucket_list>::value &&
 869             is_nothrow_move_constructible<__first_node>::value &&
 870             is_nothrow_move_constructible<__node_allocator>::value &&
 871             is_nothrow_move_constructible<hasher>::value &&
 872             is_nothrow_move_constructible<key_equal>::value);
 873     _LIBCPP_HIDE_FROM_ABI __hash_table(__hash_table&& __u, const allocator_type& __a);
 874     _LIBCPP_HIDE_FROM_ABI ~__hash_table();
 875
 876     _LIBCPP_HIDE_FROM_ABI __hash_table& operator=(const __hash_table& __u);
 877     _LIBCPP_INLINE_VISIBILITY
 878     __hash_table& operator=(__hash_table&& __u)
 879         _NOEXCEPT_(
 880             __node_traits::propagate_on_container_move_assignment::value &&
 881             is_nothrow_move_assignable<__node_allocator>::value &&
 882             is_nothrow_move_assignable<hasher>::value &&
 883             is_nothrow_move_assignable<key_equal>::value);
 884     template <class _InputIterator>
 885     _LIBCPP_HIDE_FROM_ABI void __assign_unique(_InputIterator __first, _InputIterator __last);
 886     template <class _InputIterator>
 887     _LIBCPP_HIDE_FROM_ABI void __assign_multi(_InputIterator __first, _InputIterator __last);
 888
 889     _LIBCPP_INLINE_VISIBILITY
 890     size_type max_size() const _NOEXCEPT
 891     {
 892         return _VSTD::min<size_type>(
 893             __node_traits::max_size(__node_alloc()),
 894             numeric_limits<difference_type >::max()
 895         );
 896     }
 897
 898 private:
 899     _LIBCPP_INLINE_VISIBILITY
 900     __next_pointer __node_insert_multi_prepare(size_t __cp_hash,
 901                                                value_type& __cp_val);
 902     _LIBCPP_INLINE_VISIBILITY
 903     void __node_insert_multi_perform(__node_pointer __cp,
 904                                      __next_pointer __pn) _NOEXCEPT;
 905
 906     _LIBCPP_INLINE_VISIBILITY
 907     __next_pointer __node_insert_unique_prepare(size_t __nd_hash,
 908                                                 value_type& __nd_val);
 909     _LIBCPP_INLINE_VISIBILITY
 910     void __node_insert_unique_perform(__node_pointer __ptr) _NOEXCEPT;
 911
 912 public:
 913     _LIBCPP_INLINE_VISIBILITY
 914     pair<iterator, bool> __node_insert_unique(__node_pointer __nd);
 915     _LIBCPP_INLINE_VISIBILITY
 916     iterator             __node_insert_multi(__node_pointer __nd);
 917     _LIBCPP_INLINE_VISIBILITY
 918     iterator             __node_insert_multi(const_iterator __p,
 919                                              __node_pointer __nd);
 920
 921     template <class _Key, class ..._Args>
 922     _LIBCPP_INLINE_VISIBILITY
 923     pair<iterator, bool> __emplace_unique_key_args(_Key const& __k, _Args&&... __args);
 924
 925     template <class... _Args>
 926     _LIBCPP_INLINE_VISIBILITY
 927     pair<iterator, bool> __emplace_unique_impl(_Args&&... __args);
 928
 929     template <class _Pp>
 930     _LIBCPP_INLINE_VISIBILITY
 931     pair<iterator, bool> __emplace_unique(_Pp&& __x) {
 932       return __emplace_unique_extract_key(_VSTD::forward<_Pp>(__x),
 933                                           __can_extract_key<_Pp, key_type>());
 934     }
 935
 936     template <class _First, class _Second,
 937               __enable_if_t<__can_extract_map_key<_First, key_type, __container_value_type>::value, int> = 0>
 938     _LIBCPP_INLINE_VISIBILITY
 939     pair<iterator, bool>
 940     __emplace_unique(_First&& __f, _Second&& __s) {
 941         return __emplace_unique_key_args(__f, _VSTD::forward<_First>(__f),
 942                                               _VSTD::forward<_Second>(__s));
 943     }
 944
 945     template <class... _Args>
 946     _LIBCPP_INLINE_VISIBILITY
 947     pair<iterator, bool> __emplace_unique(_Args&&... __args) {
 948       return __emplace_unique_impl(_VSTD::forward<_Args>(__args)...);
 949     }
 950
 951     template <class _Pp>
 952     _LIBCPP_INLINE_VISIBILITY
 953     pair<iterator, bool>
 954     __emplace_unique_extract_key(_Pp&& __x, __extract_key_fail_tag) {
 955       return __emplace_unique_impl(_VSTD::forward<_Pp>(__x));
 956     }
 957     template <class _Pp>
 958     _LIBCPP_INLINE_VISIBILITY
 959     pair<iterator, bool>
 960     __emplace_unique_extract_key(_Pp&& __x, __extract_key_self_tag) {
 961       return __emplace_unique_key_args(__x, _VSTD::forward<_Pp>(__x));
 962     }
 963     template <class _Pp>
 964     _LIBCPP_INLINE_VISIBILITY
 965     pair<iterator, bool>
 966     __emplace_unique_extract_key(_Pp&& __x, __extract_key_first_tag) {
 967       return __emplace_unique_key_args(__x.first, _VSTD::forward<_Pp>(__x));
 968     }
 969
 970     template <class... _Args>
 971     _LIBCPP_INLINE_VISIBILITY
 972     iterator __emplace_multi(_Args&&... __args);
 973     template <class... _Args>
 974     _LIBCPP_INLINE_VISIBILITY
 975     iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args);
 976
 977
 978     _LIBCPP_INLINE_VISIBILITY
 979     pair<iterator, bool>
 980     __insert_unique(__container_value_type&& __x) {
 981       return __emplace_unique_key_args(_NodeTypes::__get_key(__x), _VSTD::move(__x));
 982     }
 983
 984     template <class _Pp, class = __enable_if_t<!__is_same_uncvref<_Pp, __container_value_type>::value> >
 985     _LIBCPP_INLINE_VISIBILITY
 986     pair<iterator, bool> __insert_unique(_Pp&& __x) {
 987       return __emplace_unique(_VSTD::forward<_Pp>(__x));
 988     }
 989
 990     template <class _Pp>
 991     _LIBCPP_INLINE_VISIBILITY
 992     iterator __insert_multi(_Pp&& __x) {
 993       return __emplace_multi(_VSTD::forward<_Pp>(__x));
 994     }
 995
 996     template <class _Pp>
 997     _LIBCPP_INLINE_VISIBILITY
 998     iterator __insert_multi(const_iterator __p, _Pp&& __x) {
 999         return __emplace_hint_multi(__p, _VSTD::forward<_Pp>(__x));
1000     }
1001
1002     _LIBCPP_INLINE_VISIBILITY
1003     pair<iterator, bool> __insert_unique(const __container_value_type& __x) {
1004         return __emplace_unique_key_args(_NodeTypes::__get_key(__x), __x);
1005     }
1006
1007 #if _LIBCPP_STD_VER >= 17
1008     template <class _NodeHandle, class _InsertReturnType>
1009     _LIBCPP_INLINE_VISIBILITY
1010     _InsertReturnType __node_handle_insert_unique(_NodeHandle&& __nh);
1011     template <class _NodeHandle>
1012     _LIBCPP_INLINE_VISIBILITY
1013     iterator __node_handle_insert_unique(const_iterator __hint,
1014                                          _NodeHandle&& __nh);
1015     template <class _Table>
1016     _LIBCPP_INLINE_VISIBILITY
1017     void __node_handle_merge_unique(_Table& __source);
1018
1019     template <class _NodeHandle>
1020     _LIBCPP_INLINE_VISIBILITY
1021     iterator __node_handle_insert_multi(_NodeHandle&& __nh);
1022     template <class _NodeHandle>
1023     _LIBCPP_INLINE_VISIBILITY
1024     iterator __node_handle_insert_multi(const_iterator __hint, _NodeHandle&& __nh);
1025     template <class _Table>
1026     _LIBCPP_INLINE_VISIBILITY
1027     void __node_handle_merge_multi(_Table& __source);
1028
1029     template <class _NodeHandle>
1030     _LIBCPP_INLINE_VISIBILITY
1031     _NodeHandle __node_handle_extract(key_type const& __key);
1032     template <class _NodeHandle>
1033     _LIBCPP_INLINE_VISIBILITY
1034     _NodeHandle __node_handle_extract(const_iterator __it);
1035 #endif
1036
1037     _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT;
1038     _LIBCPP_INLINE_VISIBILITY void __rehash_unique(size_type __n) { __rehash<true>(__n); }
1039     _LIBCPP_INLINE_VISIBILITY void __rehash_multi(size_type __n) { __rehash<false>(__n); }
1040     _LIBCPP_INLINE_VISIBILITY void __reserve_unique(size_type __n)
1041     {
1042         __rehash_unique(static_cast<size_type>(std::ceil(__n / max_load_factor())));
1043     }
1044     _LIBCPP_INLINE_VISIBILITY void __reserve_multi(size_type __n)
1045     {
1046         __rehash_multi(static_cast<size_type>(std::ceil(__n / max_load_factor())));
1047     }
1048
1049     _LIBCPP_INLINE_VISIBILITY
1050     size_type bucket_count() const _NOEXCEPT
1051     {
1052         return __bucket_list_.get_deleter().size();
1053     }
1054
1055     _LIBCPP_INLINE_VISIBILITY
1056     iterator       begin() _NOEXCEPT;
1057     _LIBCPP_INLINE_VISIBILITY
1058     iterator       end() _NOEXCEPT;
1059     _LIBCPP_INLINE_VISIBILITY
1060     const_iterator begin() const _NOEXCEPT;
1061     _LIBCPP_INLINE_VISIBILITY
1062     const_iterator end() const _NOEXCEPT;
1063
1064     template <class _Key>
1065         _LIBCPP_INLINE_VISIBILITY
1066         size_type bucket(const _Key& __k) const
1067         {
1068             _LIBCPP_ASSERT_UNCATEGORIZED(bucket_count() > 0,
1069                 "unordered container::bucket(key) called when bucket_count() == 0");
1070             return std::__constrain_hash(hash_function()(__k), bucket_count());
1071         }
1072
1073     template <class _Key>
1074     _LIBCPP_HIDE_FROM_ABI iterator       find(const _Key& __x);
1075     template <class _Key>
1076     _LIBCPP_HIDE_FROM_ABI const_iterator find(const _Key& __x) const;
1077
1078     typedef __hash_node_destructor<__node_allocator> _Dp;
1079     typedef unique_ptr<__node, _Dp> __node_holder;
1080
1081     _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p);
1082     _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last);
1083     template <class _Key>
1084     _LIBCPP_HIDE_FROM_ABI size_type __erase_unique(const _Key& __k);
1085     template <class _Key>
1086     _LIBCPP_HIDE_FROM_ABI size_type __erase_multi(const _Key& __k);
1087     _LIBCPP_HIDE_FROM_ABI __node_holder remove(const_iterator __p) _NOEXCEPT;
1088
1089     template <class _Key>
1090         _LIBCPP_INLINE_VISIBILITY
1091         size_type __count_unique(const _Key& __k) const;
1092     template <class _Key>
1093     _LIBCPP_HIDE_FROM_ABI size_type __count_multi(const _Key& __k) const;
1094
1095     template <class _Key>
1096     _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator>
1097         __equal_range_unique(const _Key& __k);
1098     template <class _Key>
1099     _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator>
1100         __equal_range_unique(const _Key& __k) const;
1101
1102     template <class _Key>
1103     _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator>
1104         __equal_range_multi(const _Key& __k);
1105     template <class _Key>
1106     _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator>
1107         __equal_range_multi(const _Key& __k) const;
1108
1109     _LIBCPP_HIDE_FROM_ABI void swap(__hash_table& __u)
1110 #if _LIBCPP_STD_VER <= 11
1111         _NOEXCEPT_(
1112             __is_nothrow_swappable<hasher>::value && __is_nothrow_swappable<key_equal>::value
1113             && (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value
1114                   || __is_nothrow_swappable<__pointer_allocator>::value)
1115             && (!__node_traits::propagate_on_container_swap::value
1116                   || __is_nothrow_swappable<__node_allocator>::value)
1117             );
1118 #else
1119      _NOEXCEPT_(__is_nothrow_swappable<hasher>::value && __is_nothrow_swappable<key_equal>::value);
1120 #endif
1121
1122     _LIBCPP_INLINE_VISIBILITY
1123     size_type max_bucket_count() const _NOEXCEPT
1124         {return max_size(); }
1125     _LIBCPP_HIDE_FROM_ABI size_type bucket_size(size_type __n) const;
1126     _LIBCPP_INLINE_VISIBILITY float load_factor() const _NOEXCEPT
1127     {
1128         size_type __bc = bucket_count();
1129         return __bc != 0 ? (float)size() / __bc : 0.f;
1130     }
1131     _LIBCPP_INLINE_VISIBILITY void max_load_factor(float __mlf) _NOEXCEPT
1132     {
1133         _LIBCPP_ASSERT_UNCATEGORIZED(__mlf > 0,
1134             "unordered container::max_load_factor(lf) called with lf <= 0");
1135         max_load_factor() = _VSTD::max(__mlf, load_factor());
1136     }
1137
1138     _LIBCPP_INLINE_VISIBILITY
1139     local_iterator
1140     begin(size_type __n)
1141     {
1142         _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(__n < bucket_count(),
1143             "unordered container::begin(n) called with n >= bucket_count()");
1144         return local_iterator(__bucket_list_[__n], __n, bucket_count());
1145     }
1146
1147     _LIBCPP_INLINE_VISIBILITY
1148     local_iterator
1149     end(size_type __n)
1150     {
1151         _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(__n < bucket_count(),
1152             "unordered container::end(n) called with n >= bucket_count()");
1153         return local_iterator(nullptr, __n, bucket_count());
1154     }
1155
1156     _LIBCPP_INLINE_VISIBILITY
1157     const_local_iterator
1158     cbegin(size_type __n) const
1159     {
1160         _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(__n < bucket_count(),
1161             "unordered container::cbegin(n) called with n >= bucket_count()");
1162         return const_local_iterator(__bucket_list_[__n], __n, bucket_count());
1163     }
1164
1165     _LIBCPP_INLINE_VISIBILITY
1166     const_local_iterator
1167     cend(size_type __n) const
1168     {
1169         _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(__n < bucket_count(),
1170             "unordered container::cend(n) called with n >= bucket_count()");
1171         return const_local_iterator(nullptr, __n, bucket_count());
1172     }
1173
1174 private:
1175     template <bool _UniqueKeys>
1176     _LIBCPP_HIDE_FROM_ABI void __rehash(size_type __n);
1177     template <bool _UniqueKeys>
1178     _LIBCPP_HIDE_FROM_ABI void __do_rehash(size_type __n);
1179
1180     template <class ..._Args>
1181     _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node(_Args&& ...__args);
1182
1183     template <class _First, class ..._Rest>
1184     _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node_hash(size_t __hash, _First&& __f, _Rest&&... __rest);
1185
1186
1187     _LIBCPP_INLINE_VISIBILITY
1188     void __copy_assign_alloc(const __hash_table& __u)
1189         {__copy_assign_alloc(__u, integral_constant<bool,
1190              __node_traits::propagate_on_container_copy_assignment::value>());}
1191     _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __hash_table& __u, true_type);
1192     _LIBCPP_INLINE_VISIBILITY
1193         void __copy_assign_alloc(const __hash_table&, false_type) {}
1194
1195     _LIBCPP_HIDE_FROM_ABI void __move_assign(__hash_table& __u, false_type);
1196     _LIBCPP_HIDE_FROM_ABI void __move_assign(__hash_table& __u, true_type)
1197         _NOEXCEPT_(
1198             is_nothrow_move_assignable<__node_allocator>::value &&
1199             is_nothrow_move_assignable<hasher>::value &&
1200             is_nothrow_move_assignable<key_equal>::value);
1201     _LIBCPP_INLINE_VISIBILITY
1202     void __move_assign_alloc(__hash_table& __u)
1203         _NOEXCEPT_(
1204             !__node_traits::propagate_on_container_move_assignment::value ||
1205             (is_nothrow_move_assignable<__pointer_allocator>::value &&
1206              is_nothrow_move_assignable<__node_allocator>::value))
1207         {__move_assign_alloc(__u, integral_constant<bool,
1208              __node_traits::propagate_on_container_move_assignment::value>());}
1209     _LIBCPP_INLINE_VISIBILITY
1210     void __move_assign_alloc(__hash_table& __u, true_type)
1211         _NOEXCEPT_(
1212             is_nothrow_move_assignable<__pointer_allocator>::value &&
1213             is_nothrow_move_assignable<__node_allocator>::value)
1214     {
1215         __bucket_list_.get_deleter().__alloc() =
1216                 _VSTD::move(__u.__bucket_list_.get_deleter().__alloc());
1217         __node_alloc() = _VSTD::move(__u.__node_alloc());
1218     }
1219     _LIBCPP_INLINE_VISIBILITY
1220         void __move_assign_alloc(__hash_table&, false_type) _NOEXCEPT {}
1221
1222     _LIBCPP_HIDE_FROM_ABI void __deallocate_node(__next_pointer __np) _NOEXCEPT;
1223     _LIBCPP_HIDE_FROM_ABI __next_pointer __detach() _NOEXCEPT;
1224
1225     template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_map;
1226     template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
1227 };
1228
1229 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1230 inline
1231 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table()
1232     _NOEXCEPT_(
1233         is_nothrow_default_constructible<__bucket_list>::value &&
1234         is_nothrow_default_constructible<__first_node>::value &&
1235         is_nothrow_default_constructible<__node_allocator>::value &&
1236         is_nothrow_default_constructible<hasher>::value &&
1237         is_nothrow_default_constructible<key_equal>::value)
1238     : __p2_(0, __default_init_tag()),
1239       __p3_(1.0f, __default_init_tag())
1240 {
1241 }
1242
1243 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1244 inline
1245 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf,
1246                                                        const key_equal& __eql)
1247     : __bucket_list_(nullptr, __bucket_list_deleter()),
1248       __p1_(),
1249       __p2_(0, __hf),
1250       __p3_(1.0f, __eql)
1251 {
1252 }
1253
1254 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1255 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf,
1256                                                        const key_equal& __eql,
1257                                                        const allocator_type& __a)
1258     : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
1259       __p1_(__default_init_tag(), __node_allocator(__a)),
1260       __p2_(0, __hf),
1261       __p3_(1.0f, __eql)
1262 {
1263 }
1264
1265 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1266 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const allocator_type& __a)
1267     : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
1268       __p1_(__default_init_tag(), __node_allocator(__a)),
1269       __p2_(0, __default_init_tag()),
1270       __p3_(1.0f, __default_init_tag())
1271 {
1272 }
1273
1274 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1275 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u)
1276     : __bucket_list_(nullptr,
1277           __bucket_list_deleter(allocator_traits<__pointer_allocator>::
1278               select_on_container_copy_construction(
1279                   __u.__bucket_list_.get_deleter().__alloc()), 0)),
1280       __p1_(__default_init_tag(), allocator_traits<__node_allocator>::
1281           select_on_container_copy_construction(__u.__node_alloc())),
1282       __p2_(0, __u.hash_function()),
1283       __p3_(__u.__p3_)
1284 {
1285 }
1286
1287 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1288 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u,
1289                                                        const allocator_type& __a)
1290     : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
1291       __p1_(__default_init_tag(), __node_allocator(__a)),
1292       __p2_(0, __u.hash_function()),
1293       __p3_(__u.__p3_)
1294 {
1295 }
1296
1297 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1298 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u)
1299         _NOEXCEPT_(
1300             is_nothrow_move_constructible<__bucket_list>::value &&
1301             is_nothrow_move_constructible<__first_node>::value &&
1302             is_nothrow_move_constructible<__node_allocator>::value &&
1303             is_nothrow_move_constructible<hasher>::value &&
1304             is_nothrow_move_constructible<key_equal>::value)
1305     : __bucket_list_(_VSTD::move(__u.__bucket_list_)),
1306       __p1_(_VSTD::move(__u.__p1_)),
1307       __p2_(_VSTD::move(__u.__p2_)),
1308       __p3_(_VSTD::move(__u.__p3_))
1309 {
1310     if (size() > 0)
1311     {
1312         __bucket_list_[std::__constrain_hash(__p1_.first().__next_->__hash(), bucket_count())] =
1313             __p1_.first().__ptr();
1314         __u.__p1_.first().__next_ = nullptr;
1315         __u.size() = 0;
1316     }
1317 }
1318
1319 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1320 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u,
1321                                                        const allocator_type& __a)
1322     : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
1323       __p1_(__default_init_tag(), __node_allocator(__a)),
1324       __p2_(0, _VSTD::move(__u.hash_function())),
1325       __p3_(_VSTD::move(__u.__p3_))
1326 {
1327     if (__a == allocator_type(__u.__node_alloc()))
1328     {
1329         __bucket_list_.reset(__u.__bucket_list_.release());
1330         __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size();
1331         __u.__bucket_list_.get_deleter().size() = 0;
1332         if (__u.size() > 0)
1333         {
1334             __p1_.first().__next_ = __u.__p1_.first().__next_;
1335             __u.__p1_.first().__next_ = nullptr;
1336             __bucket_list_[std::__constrain_hash(__p1_.first().__next_->__hash(), bucket_count())] =
1337                 __p1_.first().__ptr();
1338             size() = __u.size();
1339             __u.size() = 0;
1340         }
1341     }
1342 }
1343
1344 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1345 __hash_table<_Tp, _Hash, _Equal, _Alloc>::~__hash_table()
1346 {
1347 #if defined(_LIBCPP_CXX03_LANG)
1348     static_assert((is_copy_constructible<key_equal>::value),
1349                  "Predicate must be copy-constructible.");
1350     static_assert((is_copy_constructible<hasher>::value),
1351                  "Hasher must be copy-constructible.");
1352 #endif
1353
1354     __deallocate_node(__p1_.first().__next_);
1355 }
1356
1357 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1358 void
1359 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__copy_assign_alloc(
1360         const __hash_table& __u, true_type)
1361 {
1362     if (__node_alloc() != __u.__node_alloc())
1363     {
1364         clear();
1365         __bucket_list_.reset();
1366         __bucket_list_.get_deleter().size() = 0;
1367     }
1368     __bucket_list_.get_deleter().__alloc() = __u.__bucket_list_.get_deleter().__alloc();
1369     __node_alloc() = __u.__node_alloc();
1370 }
1371
1372 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1373 __hash_table<_Tp, _Hash, _Equal, _Alloc>&
1374 __hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(const __hash_table& __u)
1375 {
1376     if (this != _VSTD::addressof(__u))
1377     {
1378         __copy_assign_alloc(__u);
1379         hash_function() = __u.hash_function();
1380         key_eq() = __u.key_eq();
1381         max_load_factor() = __u.max_load_factor();
1382         __assign_multi(__u.begin(), __u.end());
1383     }
1384     return *this;
1385 }
1386
1387 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1388 void
1389 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__deallocate_node(__next_pointer __np)
1390     _NOEXCEPT
1391 {
1392     __node_allocator& __na = __node_alloc();
1393     while (__np != nullptr)
1394     {
1395         __next_pointer __next = __np->__next_;
1396         __node_pointer __real_np = __np->__upcast();
1397         __node_traits::destroy(__na, _NodeTypes::__get_ptr(__real_np->__get_value()));
1398         std::__destroy_at(std::addressof(*__real_np));
1399         __node_traits::deallocate(__na, __real_np, 1);
1400         __np = __next;
1401     }
1402 }
1403
1404 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1405 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer
1406 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__detach() _NOEXCEPT
1407 {
1408     size_type __bc = bucket_count();
1409     for (size_type __i = 0; __i < __bc; ++__i)
1410         __bucket_list_[__i] = nullptr;
1411     size() = 0;
1412     __next_pointer __cache = __p1_.first().__next_;
1413     __p1_.first().__next_ = nullptr;
1414     return __cache;
1415 }
1416
1417 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1418 void
1419 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign(
1420         __hash_table& __u, true_type)
1421     _NOEXCEPT_(
1422         is_nothrow_move_assignable<__node_allocator>::value &&
1423         is_nothrow_move_assignable<hasher>::value &&
1424         is_nothrow_move_assignable<key_equal>::value)
1425 {
1426     clear();
1427     __bucket_list_.reset(__u.__bucket_list_.release());
1428     __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size();
1429     __u.__bucket_list_.get_deleter().size() = 0;
1430     __move_assign_alloc(__u);
1431     size() = __u.size();
1432     hash_function() = _VSTD::move(__u.hash_function());
1433     max_load_factor() = __u.max_load_factor();
1434     key_eq() = _VSTD::move(__u.key_eq());
1435     __p1_.first().__next_ = __u.__p1_.first().__next_;
1436     if (size() > 0)
1437     {
1438         __bucket_list_[std::__constrain_hash(__p1_.first().__next_->__hash(), bucket_count())] =
1439             __p1_.first().__ptr();
1440         __u.__p1_.first().__next_ = nullptr;
1441         __u.size() = 0;
1442     }
1443 }
1444
1445 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1446 void
1447 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign(
1448         __hash_table& __u, false_type)
1449 {
1450     if (__node_alloc() == __u.__node_alloc())
1451         __move_assign(__u, true_type());
1452     else
1453     {
1454         hash_function() = _VSTD::move(__u.hash_function());
1455         key_eq() = _VSTD::move(__u.key_eq());
1456         max_load_factor() = __u.max_load_factor();
1457         if (bucket_count() != 0)
1458         {
1459             __next_pointer __cache = __detach();
1460 #ifndef _LIBCPP_HAS_NO_EXCEPTIONS
1461             try
1462             {
1463 #endif // _LIBCPP_HAS_NO_EXCEPTIONS
1464                 const_iterator __i = __u.begin();
1465                 while (__cache != nullptr && __u.size() != 0)
1466                 {
1467                     __cache->__upcast()->__get_value() =
1468                         _VSTD::move(__u.remove(__i++)->__get_value());
1469                     __next_pointer __next = __cache->__next_;
1470                     __node_insert_multi(__cache->__upcast());
1471                     __cache = __next;
1472                 }
1473 #ifndef _LIBCPP_HAS_NO_EXCEPTIONS
1474             }
1475             catch (...)
1476             {
1477                 __deallocate_node(__cache);
1478                 throw;
1479             }
1480 #endif // _LIBCPP_HAS_NO_EXCEPTIONS
1481             __deallocate_node(__cache);
1482         }
1483         const_iterator __i = __u.begin();
1484         while (__u.size() != 0)
1485         {
1486             __node_holder __h = __construct_node(_NodeTypes::__move(__u.remove(__i++)->__get_value()));
1487             __node_insert_multi(__h.get());
1488             __h.release();
1489         }
1490     }
1491 }
1492
1493 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1494 inline
1495 __hash_table<_Tp, _Hash, _Equal, _Alloc>&
1496 __hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(__hash_table&& __u)
1497     _NOEXCEPT_(
1498         __node_traits::propagate_on_container_move_assignment::value &&
1499         is_nothrow_move_assignable<__node_allocator>::value &&
1500         is_nothrow_move_assignable<hasher>::value &&
1501         is_nothrow_move_assignable<key_equal>::value)
1502 {
1503     __move_assign(__u, integral_constant<bool,
1504                   __node_traits::propagate_on_container_move_assignment::value>());
1505     return *this;
1506 }
1507
1508 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1509 template <class _InputIterator>
1510 void
1511 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_unique(_InputIterator __first,
1512                                                           _InputIterator __last)
1513 {
1514     typedef iterator_traits<_InputIterator> _ITraits;
1515     typedef typename _ITraits::value_type _ItValueType;
1516     static_assert((is_same<_ItValueType, __container_value_type>::value),
1517                   "__assign_unique may only be called with the containers value type");
1518
1519     if (bucket_count() != 0)
1520     {
1521         __next_pointer __cache = __detach();
1522 #ifndef _LIBCPP_HAS_NO_EXCEPTIONS
1523         try
1524         {
1525 #endif // _LIBCPP_HAS_NO_EXCEPTIONS
1526             for (; __cache != nullptr && __first != __last; ++__first)
1527             {
1528                 __cache->__upcast()->__get_value() = *__first;
1529                 __next_pointer __next = __cache->__next_;
1530                 __node_insert_unique(__cache->__upcast());
1531                 __cache = __next;
1532             }
1533 #ifndef _LIBCPP_HAS_NO_EXCEPTIONS
1534         }
1535         catch (...)
1536         {
1537             __deallocate_node(__cache);
1538             throw;
1539         }
1540 #endif // _LIBCPP_HAS_NO_EXCEPTIONS
1541         __deallocate_node(__cache);
1542     }
1543     for (; __first != __last; ++__first)
1544         __insert_unique(*__first);
1545 }
1546
1547 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1548 template <class _InputIterator>
1549 void
1550 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_multi(_InputIterator __first,
1551                                                          _InputIterator __last)
1552 {
1553     typedef iterator_traits<_InputIterator> _ITraits;
1554     typedef typename _ITraits::value_type _ItValueType;
1555     static_assert((is_same<_ItValueType, __container_value_type>::value ||
1556                   is_same<_ItValueType, __node_value_type>::value),
1557                   "__assign_multi may only be called with the containers value type"
1558                   " or the nodes value type");
1559     if (bucket_count() != 0)
1560     {
1561         __next_pointer __cache = __detach();
1562 #ifndef _LIBCPP_HAS_NO_EXCEPTIONS
1563         try
1564         {
1565 #endif // _LIBCPP_HAS_NO_EXCEPTIONS
1566             for (; __cache != nullptr && __first != __last; ++__first)
1567             {
1568                 __cache->__upcast()->__get_value() = *__first;
1569                 __next_pointer __next = __cache->__next_;
1570                 __node_insert_multi(__cache->__upcast());
1571                 __cache = __next;
1572             }
1573 #ifndef _LIBCPP_HAS_NO_EXCEPTIONS
1574         }
1575         catch (...)
1576         {
1577             __deallocate_node(__cache);
1578             throw;
1579         }
1580 #endif // _LIBCPP_HAS_NO_EXCEPTIONS
1581         __deallocate_node(__cache);
1582     }
1583     for (; __first != __last; ++__first)
1584         __insert_multi(_NodeTypes::__get_value(*__first));
1585 }
1586
1587 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1588 inline
1589 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1590 __hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() _NOEXCEPT
1591 {
1592     return iterator(__p1_.first().__next_);
1593 }
1594
1595 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1596 inline
1597 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1598 __hash_table<_Tp, _Hash, _Equal, _Alloc>::end() _NOEXCEPT
1599 {
1600     return iterator(nullptr);
1601 }
1602
1603 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1604 inline
1605 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator
1606 __hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() const _NOEXCEPT
1607 {
1608     return const_iterator(__p1_.first().__next_);
1609 }
1610
1611 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1612 inline
1613 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator
1614 __hash_table<_Tp, _Hash, _Equal, _Alloc>::end() const _NOEXCEPT
1615 {
1616     return const_iterator(nullptr);
1617 }
1618
1619 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1620 void
1621 __hash_table<_Tp, _Hash, _Equal, _Alloc>::clear() _NOEXCEPT
1622 {
1623     if (size() > 0)
1624     {
1625         __deallocate_node(__p1_.first().__next_);
1626         __p1_.first().__next_ = nullptr;
1627         size_type __bc = bucket_count();
1628         for (size_type __i = 0; __i < __bc; ++__i)
1629             __bucket_list_[__i] = nullptr;
1630         size() = 0;
1631     }
1632 }
1633
1634
1635 // Prepare the container for an insertion of the value __value with the hash
1636 // __hash. This does a lookup into the container to see if __value is already
1637 // present, and performs a rehash if necessary. Returns a pointer to the
1638 // existing element if it exists, otherwise nullptr.
1639 //
1640 // Note that this function does forward exceptions if key_eq() throws, and never
1641 // mutates __value or actually inserts into the map.
1642 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1643 _LIBCPP_INLINE_VISIBILITY
1644 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer
1645 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique_prepare(
1646     size_t __hash, value_type& __value)
1647 {
1648     size_type __bc = bucket_count();
1649
1650     if (__bc != 0)
1651     {
1652         size_t __chash = std::__constrain_hash(__hash, __bc);
1653         __next_pointer __ndptr = __bucket_list_[__chash];
1654         if (__ndptr != nullptr)
1655         {
1656             for (__ndptr = __ndptr->__next_; __ndptr != nullptr &&
1657                     (__ndptr->__hash() == __hash ||
1658                      std::__constrain_hash(__ndptr->__hash(), __bc) == __chash);
1659                                                      __ndptr = __ndptr->__next_)
1660             {
1661                 if ((__ndptr->__hash() == __hash) &&
1662                     key_eq()(__ndptr->__upcast()->__get_value(), __value))
1663                     return __ndptr;
1664             }
1665         }
1666     }
1667     if (size()+1 > __bc * max_load_factor() || __bc == 0)
1668     {
1669         __rehash_unique(_VSTD::max<size_type>(2 * __bc + !std::__is_hash_power2(__bc),
1670                                      size_type(std::ceil(float(size() + 1) / max_load_factor()))));
1671     }
1672     return nullptr;
1673 }
1674
1675 // Insert the node __nd into the container by pushing it into the right bucket,
1676 // and updating size(). Assumes that __nd->__hash is up-to-date, and that
1677 // rehashing has already occurred and that no element with the same key exists
1678 // in the map.
1679 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1680 _LIBCPP_INLINE_VISIBILITY
1681 void
1682 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique_perform(
1683     __node_pointer __nd) _NOEXCEPT
1684 {
1685     size_type __bc = bucket_count();
1686     size_t __chash = std::__constrain_hash(__nd->__hash(), __bc);
1687     // insert_after __bucket_list_[__chash], or __first_node if bucket is null
1688     __next_pointer __pn = __bucket_list_[__chash];
1689     if (__pn == nullptr)
1690     {
1691         __pn =__p1_.first().__ptr();
1692         __nd->__next_ = __pn->__next_;
1693         __pn->__next_ = __nd->__ptr();
1694         // fix up __bucket_list_
1695         __bucket_list_[__chash] = __pn;
1696         if (__nd->__next_ != nullptr)
1697             __bucket_list_[std::__constrain_hash(__nd->__next_->__hash(), __bc)] = __nd->__ptr();
1698     }
1699     else
1700     {
1701         __nd->__next_ = __pn->__next_;
1702         __pn->__next_ = __nd->__ptr();
1703     }
1704     ++size();
1705 }
1706
1707 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1708 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
1709 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique(__node_pointer __nd)
1710 {
1711     __nd->__hash_ = hash_function()(__nd->__get_value());
1712     __next_pointer __existing_node =
1713         __node_insert_unique_prepare(__nd->__hash(), __nd->__get_value());
1714
1715     // Insert the node, unless it already exists in the container.
1716     bool __inserted = false;
1717     if (__existing_node == nullptr)
1718     {
1719         __node_insert_unique_perform(__nd);
1720         __existing_node = __nd->__ptr();
1721         __inserted = true;
1722     }
1723     return pair<iterator, bool>(iterator(__existing_node), __inserted);
1724 }
1725
1726 // Prepare the container for an insertion of the value __cp_val with the hash
1727 // __cp_hash. This does a lookup into the container to see if __cp_value is
1728 // already present, and performs a rehash if necessary. Returns a pointer to the
1729 // last occurrence of __cp_val in the map.
1730 //
1731 // Note that this function does forward exceptions if key_eq() throws, and never
1732 // mutates __value or actually inserts into the map.
1733 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1734 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer
1735 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi_prepare(
1736     size_t __cp_hash, value_type& __cp_val)
1737 {
1738     size_type __bc = bucket_count();
1739     if (size()+1 > __bc * max_load_factor() || __bc == 0)
1740     {
1741         __rehash_multi(_VSTD::max<size_type>(2 * __bc + !std::__is_hash_power2(__bc),
1742                        size_type(std::ceil(float(size() + 1) / max_load_factor()))));
1743         __bc = bucket_count();
1744     }
1745     size_t __chash = std::__constrain_hash(__cp_hash, __bc);
1746     __next_pointer __pn = __bucket_list_[__chash];
1747     if (__pn != nullptr)
1748     {
1749         for (bool __found = false; __pn->__next_ != nullptr &&
1750                                    std::__constrain_hash(__pn->__next_->__hash(), __bc) == __chash;
1751                                                            __pn = __pn->__next_)
1752         {
1753             //      __found    key_eq()     action
1754             //      false       false       loop
1755             //      true        true        loop
1756             //      false       true        set __found to true
1757             //      true        false       break
1758             if (__found != (__pn->__next_->__hash() == __cp_hash &&
1759                             key_eq()(__pn->__next_->__upcast()->__get_value(), __cp_val)))
1760             {
1761                 if (!__found)
1762                     __found = true;
1763                 else
1764                     break;
1765             }
1766         }
1767     }
1768     return __pn;
1769 }
1770
1771 // Insert the node __cp into the container after __pn (which is the last node in
1772 // the bucket that compares equal to __cp). Rehashing, and checking for
1773 // uniqueness has already been performed (in __node_insert_multi_prepare), so
1774 // all we need to do is update the bucket and size(). Assumes that __cp->__hash
1775 // is up-to-date.
1776 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1777 void
1778 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi_perform(
1779     __node_pointer __cp, __next_pointer __pn) _NOEXCEPT
1780 {
1781     size_type __bc = bucket_count();
1782     size_t __chash = std::__constrain_hash(__cp->__hash_, __bc);
1783     if (__pn == nullptr)
1784     {
1785         __pn =__p1_.first().__ptr();
1786         __cp->__next_ = __pn->__next_;
1787         __pn->__next_ = __cp->__ptr();
1788         // fix up __bucket_list_
1789         __bucket_list_[__chash] = __pn;
1790         if (__cp->__next_ != nullptr)
1791             __bucket_list_[std::__constrain_hash(__cp->__next_->__hash(), __bc)]
1792                 = __cp->__ptr();
1793     }
1794     else
1795     {
1796         __cp->__next_ = __pn->__next_;
1797         __pn->__next_ = __cp->__ptr();
1798         if (__cp->__next_ != nullptr)
1799         {
1800             size_t __nhash = std::__constrain_hash(__cp->__next_->__hash(), __bc);
1801             if (__nhash != __chash)
1802                 __bucket_list_[__nhash] = __cp->__ptr();
1803         }
1804     }
1805     ++size();
1806 }
1807
1808
1809 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1810 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1811 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __cp)
1812 {
1813     __cp->__hash_ = hash_function()(__cp->__get_value());
1814     __next_pointer __pn = __node_insert_multi_prepare(__cp->__hash(), __cp->__get_value());
1815     __node_insert_multi_perform(__cp, __pn);
1816
1817     return iterator(__cp->__ptr());
1818 }
1819
1820 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1821 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1822 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(
1823         const_iterator __p, __node_pointer __cp)
1824 {
1825     if (__p != end() && key_eq()(*__p, __cp->__get_value()))
1826     {
1827         __next_pointer __np = __p.__node_;
1828         __cp->__hash_ = __np->__hash();
1829         size_type __bc = bucket_count();
1830         if (size()+1 > __bc * max_load_factor() || __bc == 0)
1831         {
1832             __rehash_multi(_VSTD::max<size_type>(2 * __bc + !std::__is_hash_power2(__bc),
1833                            size_type(std::ceil(float(size() + 1) / max_load_factor()))));
1834             __bc = bucket_count();
1835         }
1836         size_t __chash = std::__constrain_hash(__cp->__hash_, __bc);
1837         __next_pointer __pp = __bucket_list_[__chash];
1838         while (__pp->__next_ != __np)
1839             __pp = __pp->__next_;
1840         __cp->__next_ = __np;
1841         __pp->__next_ = static_cast<__next_pointer>(__cp);
1842         ++size();
1843         return iterator(static_cast<__next_pointer>(__cp));
1844     }
1845     return __node_insert_multi(__cp);
1846 }
1847
1848
1849
1850 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1851 template <class _Key, class ..._Args>
1852 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
1853 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique_key_args(_Key const& __k, _Args&&... __args)
1854 {
1855
1856     size_t __hash = hash_function()(__k);
1857     size_type __bc = bucket_count();
1858     bool __inserted = false;
1859     __next_pointer __nd;
1860     size_t __chash;
1861     if (__bc != 0)
1862     {
1863         __chash = std::__constrain_hash(__hash, __bc);
1864         __nd = __bucket_list_[__chash];
1865         if (__nd != nullptr)
1866         {
1867             for (__nd = __nd->__next_; __nd != nullptr &&
1868                 (__nd->__hash() == __hash || std::__constrain_hash(__nd->__hash(), __bc) == __chash);
1869                                                            __nd = __nd->__next_)
1870             {
1871                 if ((__nd->__hash() == __hash) &&
1872                     key_eq()(__nd->__upcast()->__get_value(), __k))
1873                     goto __done;
1874             }
1875         }
1876     }
1877     {
1878         __node_holder __h = __construct_node_hash(__hash, _VSTD::forward<_Args>(__args)...);
1879         if (size()+1 > __bc * max_load_factor() || __bc == 0)
1880         {
1881             __rehash_unique(_VSTD::max<size_type>(2 * __bc + !std::__is_hash_power2(__bc),
1882                            size_type(std::ceil(float(size() + 1) / max_load_factor()))));
1883             __bc = bucket_count();
1884             __chash = std::__constrain_hash(__hash, __bc);
1885         }
1886         // insert_after __bucket_list_[__chash], or __first_node if bucket is null
1887         __next_pointer __pn = __bucket_list_[__chash];
1888         if (__pn == nullptr)
1889         {
1890             __pn = __p1_.first().__ptr();
1891             __h->__next_ = __pn->__next_;
1892             __pn->__next_ = __h.get()->__ptr();
1893             // fix up __bucket_list_
1894             __bucket_list_[__chash] = __pn;
1895             if (__h->__next_ != nullptr)
1896                 __bucket_list_[std::__constrain_hash(__h->__next_->__hash(), __bc)]
1897                     = __h.get()->__ptr();
1898         }
1899         else
1900         {
1901             __h->__next_ = __pn->__next_;
1902             __pn->__next_ = static_cast<__next_pointer>(__h.get());
1903         }
1904         __nd = static_cast<__next_pointer>(__h.release());
1905         // increment size
1906         ++size();
1907         __inserted = true;
1908     }
1909 __done:
1910     return pair<iterator, bool>(iterator(__nd), __inserted);
1911 }
1912
1913 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1914 template <class... _Args>
1915 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
1916 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique_impl(_Args&&... __args)
1917 {
1918     __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1919     pair<iterator, bool> __r = __node_insert_unique(__h.get());
1920     if (__r.second)
1921         __h.release();
1922     return __r;
1923 }
1924
1925 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1926 template <class... _Args>
1927 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1928 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_multi(_Args&&... __args)
1929 {
1930     __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1931     iterator __r = __node_insert_multi(__h.get());
1932     __h.release();
1933     return __r;
1934 }
1935
1936 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1937 template <class... _Args>
1938 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1939 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_hint_multi(
1940         const_iterator __p, _Args&&... __args)
1941 {
1942     __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1943     iterator __r = __node_insert_multi(__p, __h.get());
1944     __h.release();
1945     return __r;
1946 }
1947
1948 #if _LIBCPP_STD_VER >= 17
1949 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1950 template <class _NodeHandle, class _InsertReturnType>
1951 _LIBCPP_INLINE_VISIBILITY
1952 _InsertReturnType
1953 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_unique(
1954     _NodeHandle&& __nh)
1955 {
1956     if (__nh.empty())
1957         return _InsertReturnType{end(), false, _NodeHandle()};
1958     pair<iterator, bool> __result = __node_insert_unique(__nh.__ptr_);
1959     if (__result.second)
1960         __nh.__release_ptr();
1961     return _InsertReturnType{__result.first, __result.second, _VSTD::move(__nh)};
1962 }
1963
1964 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1965 template <class _NodeHandle>
1966 _LIBCPP_INLINE_VISIBILITY
1967 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1968 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_unique(
1969     const_iterator, _NodeHandle&& __nh)
1970 {
1971     if (__nh.empty())
1972         return end();
1973     pair<iterator, bool> __result = __node_insert_unique(__nh.__ptr_);
1974     if (__result.second)
1975         __nh.__release_ptr();
1976     return __result.first;
1977 }
1978
1979 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1980 template <class _NodeHandle>
1981 _LIBCPP_INLINE_VISIBILITY
1982 _NodeHandle
1983 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_extract(
1984     key_type const& __key)
1985 {
1986     iterator __i = find(__key);
1987     if (__i == end())
1988         return _NodeHandle();
1989     return __node_handle_extract<_NodeHandle>(__i);
1990 }
1991
1992 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1993 template <class _NodeHandle>
1994 _LIBCPP_INLINE_VISIBILITY
1995 _NodeHandle
1996 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_extract(
1997     const_iterator __p)
1998 {
1999     allocator_type __alloc(__node_alloc());
2000     return _NodeHandle(remove(__p).release(), __alloc);
2001 }
2002
2003 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2004 template <class _Table>
2005 _LIBCPP_INLINE_VISIBILITY
2006 void
2007 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_merge_unique(
2008     _Table& __source)
2009 {
2010     static_assert(is_same<__node, typename _Table::__node>::value, "");
2011
2012     for (typename _Table::iterator __it = __source.begin();
2013          __it != __source.end();)
2014     {
2015         __node_pointer __src_ptr = __it.__node_->__upcast();
2016         size_t __hash = hash_function()(__src_ptr->__get_value());
2017         __next_pointer __existing_node =
2018             __node_insert_unique_prepare(__hash, __src_ptr->__get_value());
2019         auto __prev_iter = __it++;
2020         if (__existing_node == nullptr)
2021         {
2022             (void)__source.remove(__prev_iter).release();
2023             __src_ptr->__hash_ = __hash;
2024             __node_insert_unique_perform(__src_ptr);
2025         }
2026     }
2027 }
2028
2029 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2030 template <class _NodeHandle>
2031 _LIBCPP_INLINE_VISIBILITY
2032 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
2033 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_multi(
2034     _NodeHandle&& __nh)
2035 {
2036     if (__nh.empty())
2037         return end();
2038     iterator __result = __node_insert_multi(__nh.__ptr_);
2039     __nh.__release_ptr();
2040     return __result;
2041 }
2042
2043 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2044 template <class _NodeHandle>
2045 _LIBCPP_INLINE_VISIBILITY
2046 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
2047 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_multi(
2048     const_iterator __hint, _NodeHandle&& __nh)
2049 {
2050     if (__nh.empty())
2051         return end();
2052     iterator __result = __node_insert_multi(__hint, __nh.__ptr_);
2053     __nh.__release_ptr();
2054     return __result;
2055 }
2056
2057 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2058 template <class _Table>
2059 _LIBCPP_INLINE_VISIBILITY
2060 void
2061 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_merge_multi(
2062     _Table& __source)
2063 {
2064     static_assert(is_same<typename _Table::__node, __node>::value, "");
2065
2066     for (typename _Table::iterator __it = __source.begin();
2067          __it != __source.end();)
2068     {
2069         __node_pointer __src_ptr = __it.__node_->__upcast();
2070         size_t __src_hash = hash_function()(__src_ptr->__get_value());
2071         __next_pointer __pn =
2072             __node_insert_multi_prepare(__src_hash, __src_ptr->__get_value());
2073         (void)__source.remove(__it++).release();
2074         __src_ptr->__hash_ = __src_hash;
2075         __node_insert_multi_perform(__src_ptr, __pn);
2076     }
2077 }
2078 #endif // _LIBCPP_STD_VER >= 17
2079
2080 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2081 template <bool _UniqueKeys>
2082 void
2083 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__rehash(size_type __n)
2084 _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK
2085 {
2086     if (__n == 1)
2087         __n = 2;
2088     else if (__n & (__n - 1))
2089         __n = std::__next_prime(__n);
2090     size_type __bc = bucket_count();
2091     if (__n > __bc)
2092         __do_rehash<_UniqueKeys>(__n);
2093     else if (__n < __bc)
2094     {
2095         __n = _VSTD::max<size_type>
2096               (
2097                   __n,
2098                   std::__is_hash_power2(__bc) ? std::__next_hash_pow2(size_t(std::ceil(float(size()) / max_load_factor()))) :
2099                                            std::__next_prime(size_t(std::ceil(float(size()) / max_load_factor())))
2100               );
2101         if (__n < __bc)
2102             __do_rehash<_UniqueKeys>(__n);
2103     }
2104 }
2105
2106 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2107 template <bool _UniqueKeys>
2108 void
2109 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__do_rehash(size_type __nbc)
2110 {
2111     __pointer_allocator& __npa = __bucket_list_.get_deleter().__alloc();
2112     __bucket_list_.reset(__nbc > 0 ?
2113                       __pointer_alloc_traits::allocate(__npa, __nbc) : nullptr);
2114     __bucket_list_.get_deleter().size() = __nbc;
2115     if (__nbc > 0)
2116     {
2117         for (size_type __i = 0; __i < __nbc; ++__i)
2118             __bucket_list_[__i] = nullptr;
2119         __next_pointer __pp = __p1_.first().__ptr();
2120         __next_pointer __cp = __pp->__next_;
2121         if (__cp != nullptr)
2122         {
2123             size_type __chash = std::__constrain_hash(__cp->__hash(), __nbc);
2124             __bucket_list_[__chash] = __pp;
2125             size_type __phash = __chash;
2126             for (__pp = __cp, void(), __cp = __cp->__next_; __cp != nullptr;
2127                                                            __cp = __pp->__next_)
2128             {
2129                 __chash = std::__constrain_hash(__cp->__hash(), __nbc);
2130                 if (__chash == __phash)
2131                     __pp = __cp;
2132                 else
2133                 {
2134                     if (__bucket_list_[__chash] == nullptr)
2135                     {
2136                         __bucket_list_[__chash] = __pp;
2137                         __pp = __cp;
2138                         __phash = __chash;
2139                     }
2140                     else
2141                     {
2142                         __next_pointer __np = __cp;
2143                         if _LIBCPP_CONSTEXPR_SINCE_CXX17 (!_UniqueKeys)
2144                         {
2145                             for (; __np->__next_ != nullptr &&
2146                                    key_eq()(__cp->__upcast()->__get_value(),
2147                                             __np->__next_->__upcast()->__get_value());
2148                                                                __np = __np->__next_)
2149                                 ;
2150                         }
2151                         __pp->__next_ = __np->__next_;
2152                         __np->__next_ = __bucket_list_[__chash]->__next_;
2153                         __bucket_list_[__chash]->__next_ = __cp;
2154
2155                     }
2156                 }
2157             }
2158         }
2159     }
2160 }
2161
2162 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2163 template <class _Key>
2164 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
2165 __hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k)
2166 {
2167     size_t __hash = hash_function()(__k);
2168     size_type __bc = bucket_count();
2169     if (__bc != 0)
2170     {
2171         size_t __chash = std::__constrain_hash(__hash, __bc);
2172         __next_pointer __nd = __bucket_list_[__chash];
2173         if (__nd != nullptr)
2174         {
2175             for (__nd = __nd->__next_; __nd != nullptr &&
2176                 (__nd->__hash() == __hash
2177                   || std::__constrain_hash(__nd->__hash(), __bc) == __chash);
2178                                                            __nd = __nd->__next_)
2179             {
2180                 if ((__nd->__hash() == __hash)
2181                     && key_eq()(__nd->__upcast()->__get_value(), __k))
2182                     return iterator(__nd);
2183             }
2184         }
2185     }
2186     return end();
2187 }
2188
2189 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2190 template <class _Key>
2191 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator
2192 __hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) const
2193 {
2194     size_t __hash = hash_function()(__k);
2195     size_type __bc = bucket_count();
2196     if (__bc != 0)
2197     {
2198         size_t __chash = std::__constrain_hash(__hash, __bc);
2199         __next_pointer __nd = __bucket_list_[__chash];
2200         if (__nd != nullptr)
2201         {
2202             for (__nd = __nd->__next_; __nd != nullptr &&
2203                 (__hash == __nd->__hash()
2204                     || std::__constrain_hash(__nd->__hash(), __bc) == __chash);
2205                                                            __nd = __nd->__next_)
2206             {
2207                 if ((__nd->__hash() == __hash)
2208                     && key_eq()(__nd->__upcast()->__get_value(), __k))
2209                     return const_iterator(__nd);
2210             }
2211         }
2212
2213     }
2214     return end();
2215 }
2216
2217 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2218 template <class ..._Args>
2219 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
2220 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(_Args&& ...__args)
2221 {
2222     static_assert(!__is_hash_value_type<_Args...>::value,
2223                   "Construct cannot be called with a hash value type");
2224     __node_allocator& __na = __node_alloc();
2225     __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
2226
2227     // Begin the lifetime of the node itself. Note that this doesn't begin the lifetime of the value
2228     // held inside the node, since we need to use the allocator's construct() method for that.
2229     //
2230     // We don't use the allocator's construct() method to construct the node itself since the
2231     // Cpp17FooInsertable named requirements don't require the allocator's construct() method
2232     // to work on anything other than the value_type.
2233     std::__construct_at(std::addressof(*__h), /* next = */nullptr, /* hash = */0);
2234
2235     // Now construct the value_type using the allocator's construct() method.
2236     __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__get_value()), _VSTD::forward<_Args>(__args)...);
2237     __h.get_deleter().__value_constructed = true;
2238
2239     __h->__hash_ = hash_function()(__h->__get_value());
2240     return __h;
2241 }
2242
2243 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2244 template <class _First, class ..._Rest>
2245 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
2246 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node_hash(
2247     size_t __hash, _First&& __f, _Rest&& ...__rest)
2248 {
2249     static_assert(!__is_hash_value_type<_First, _Rest...>::value,
2250                   "Construct cannot be called with a hash value type");
2251     __node_allocator& __na = __node_alloc();
2252     __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
2253     std::__construct_at(std::addressof(*__h), /* next = */nullptr, /* hash = */__hash);
2254     __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__get_value()),
2255                              _VSTD::forward<_First>(__f),
2256                              _VSTD::forward<_Rest>(__rest)...);
2257     __h.get_deleter().__value_constructed = true;
2258     return __h;
2259 }
2260
2261 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2262 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
2263 __hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __p)
2264 {
2265     __next_pointer __np = __p.__node_;
2266     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(__p != end(),
2267         "unordered container::erase(iterator) called with a non-dereferenceable iterator");
2268     iterator __r(__np);
2269     ++__r;
2270     remove(__p);
2271     return __r;
2272 }
2273
2274 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2275 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
2276 __hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __first,
2277                                                 const_iterator __last)
2278 {
2279     for (const_iterator __p = __first; __first != __last; __p = __first)
2280     {
2281         ++__first;
2282         erase(__p);
2283     }
2284     __next_pointer __np = __last.__node_;
2285     return iterator (__np);
2286 }
2287
2288 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2289 template <class _Key>
2290 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
2291 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_unique(const _Key& __k)
2292 {
2293     iterator __i = find(__k);
2294     if (__i == end())
2295         return 0;
2296     erase(__i);
2297     return 1;
2298 }
2299
2300 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2301 template <class _Key>
2302 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
2303 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_multi(const _Key& __k)
2304 {
2305     size_type __r = 0;
2306     iterator __i = find(__k);
2307     if (__i != end())
2308     {
2309         iterator __e = end();
2310         do
2311         {
2312             erase(__i++);
2313             ++__r;
2314         } while (__i != __e && key_eq()(*__i, __k));
2315     }
2316     return __r;
2317 }
2318
2319 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2320 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
2321 __hash_table<_Tp, _Hash, _Equal, _Alloc>::remove(const_iterator __p) _NOEXCEPT
2322 {
2323     // current node
2324     __next_pointer __cn = __p.__node_;
2325     size_type __bc = bucket_count();
2326     size_t __chash = std::__constrain_hash(__cn->__hash(), __bc);
2327     // find previous node
2328     __next_pointer __pn = __bucket_list_[__chash];
2329     for (; __pn->__next_ != __cn; __pn = __pn->__next_)
2330         ;
2331     // Fix up __bucket_list_
2332         // if __pn is not in same bucket (before begin is not in same bucket) &&
2333         //    if __cn->__next_ is not in same bucket (nullptr is not in same bucket)
2334     if (__pn == __p1_.first().__ptr()
2335             || std::__constrain_hash(__pn->__hash(), __bc) != __chash)
2336     {
2337         if (__cn->__next_ == nullptr
2338             || std::__constrain_hash(__cn->__next_->__hash(), __bc) != __chash)
2339             __bucket_list_[__chash] = nullptr;
2340     }
2341         // if __cn->__next_ is not in same bucket (nullptr is in same bucket)
2342     if (__cn->__next_ != nullptr)
2343     {
2344         size_t __nhash = std::__constrain_hash(__cn->__next_->__hash(), __bc);
2345         if (__nhash != __chash)
2346             __bucket_list_[__nhash] = __pn;
2347     }
2348     // remove __cn
2349     __pn->__next_ = __cn->__next_;
2350     __cn->__next_ = nullptr;
2351     --size();
2352     return __node_holder(__cn->__upcast(), _Dp(__node_alloc(), true));
2353 }
2354
2355 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2356 template <class _Key>
2357 inline
2358 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
2359 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_unique(const _Key& __k) const
2360 {
2361     return static_cast<size_type>(find(__k) != end());
2362 }
2363
2364 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2365 template <class _Key>
2366 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
2367 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_multi(const _Key& __k) const
2368 {
2369     size_type __r = 0;
2370     const_iterator __i = find(__k);
2371     if (__i != end())
2372     {
2373         const_iterator __e = end();
2374         do
2375         {
2376             ++__i;
2377             ++__r;
2378         } while (__i != __e && key_eq()(*__i, __k));
2379     }
2380     return __r;
2381 }
2382
2383 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2384 template <class _Key>
2385 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator,
2386      typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator>
2387 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique(
2388         const _Key& __k)
2389 {
2390     iterator __i = find(__k);
2391     iterator __j = __i;
2392     if (__i != end())
2393         ++__j;
2394     return pair<iterator, iterator>(__i, __j);
2395 }
2396
2397 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2398 template <class _Key>
2399 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator,
2400      typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator>
2401 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique(
2402         const _Key& __k) const
2403 {
2404     const_iterator __i = find(__k);
2405     const_iterator __j = __i;
2406     if (__i != end())
2407         ++__j;
2408     return pair<const_iterator, const_iterator>(__i, __j);
2409 }
2410
2411 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2412 template <class _Key>
2413 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator,
2414      typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator>
2415 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi(
2416         const _Key& __k)
2417 {
2418     iterator __i = find(__k);
2419     iterator __j = __i;
2420     if (__i != end())
2421     {
2422         iterator __e = end();
2423         do
2424         {
2425             ++__j;
2426         } while (__j != __e && key_eq()(*__j, __k));
2427     }
2428     return pair<iterator, iterator>(__i, __j);
2429 }
2430
2431 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2432 template <class _Key>
2433 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator,
2434      typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator>
2435 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi(
2436         const _Key& __k) const
2437 {
2438     const_iterator __i = find(__k);
2439     const_iterator __j = __i;
2440     if (__i != end())
2441     {
2442         const_iterator __e = end();
2443         do
2444         {
2445             ++__j;
2446         } while (__j != __e && key_eq()(*__j, __k));
2447     }
2448     return pair<const_iterator, const_iterator>(__i, __j);
2449 }
2450
2451 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2452 void
2453 __hash_table<_Tp, _Hash, _Equal, _Alloc>::swap(__hash_table& __u)
2454 #if _LIBCPP_STD_VER <= 11
2455     _NOEXCEPT_(
2456         __is_nothrow_swappable<hasher>::value && __is_nothrow_swappable<key_equal>::value
2457         && (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value
2458               || __is_nothrow_swappable<__pointer_allocator>::value)
2459         && (!__node_traits::propagate_on_container_swap::value
2460               || __is_nothrow_swappable<__node_allocator>::value)
2461             )
2462 #else
2463   _NOEXCEPT_(__is_nothrow_swappable<hasher>::value && __is_nothrow_swappable<key_equal>::value)
2464 #endif
2465 {
2466     _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__node_traits::propagate_on_container_swap::value ||
2467                                         this->__node_alloc() == __u.__node_alloc(),
2468                                         "unordered container::swap: Either propagate_on_container_swap "
2469                                         "must be true or the allocators must compare equal");
2470     {
2471     __node_pointer_pointer __npp = __bucket_list_.release();
2472     __bucket_list_.reset(__u.__bucket_list_.release());
2473     __u.__bucket_list_.reset(__npp);
2474     }
2475     _VSTD::swap(__bucket_list_.get_deleter().size(), __u.__bucket_list_.get_deleter().size());
2476     _VSTD::__swap_allocator(__bucket_list_.get_deleter().__alloc(),
2477              __u.__bucket_list_.get_deleter().__alloc());
2478     _VSTD::__swap_allocator(__node_alloc(), __u.__node_alloc());
2479     _VSTD::swap(__p1_.first().__next_, __u.__p1_.first().__next_);
2480     __p2_.swap(__u.__p2_);
2481     __p3_.swap(__u.__p3_);
2482     if (size() > 0)
2483         __bucket_list_[std::__constrain_hash(__p1_.first().__next_->__hash(), bucket_count())] =
2484             __p1_.first().__ptr();
2485     if (__u.size() > 0)
2486         __u.__bucket_list_[std::__constrain_hash(__u.__p1_.first().__next_->__hash(), __u.bucket_count())] =
2487             __u.__p1_.first().__ptr();
2488 }
2489
2490 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2491 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
2492 __hash_table<_Tp, _Hash, _Equal, _Alloc>::bucket_size(size_type __n) const
2493 {
2494     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(__n < bucket_count(),
2495         "unordered container::bucket_size(n) called with n >= bucket_count()");
2496     __next_pointer __np = __bucket_list_[__n];
2497     size_type __bc = bucket_count();
2498     size_type __r = 0;
2499     if (__np != nullptr)
2500     {
2501         for (__np = __np->__next_; __np != nullptr &&
2502                                    std::__constrain_hash(__np->__hash(), __bc) == __n;
2503                                                          __np = __np->__next_, (void) ++__r)
2504             ;
2505     }
2506     return __r;
2507 }
2508
2509 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2510 inline _LIBCPP_INLINE_VISIBILITY
2511 void
2512 swap(__hash_table<_Tp, _Hash, _Equal, _Alloc>& __x,
2513      __hash_table<_Tp, _Hash, _Equal, _Alloc>& __y)
2514     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
2515 {
2516     __x.swap(__y);
2517 }
2518
2519 _LIBCPP_END_NAMESPACE_STD
2520
2521 _LIBCPP_POP_MACROS
2522
2523 #endif // _LIBCPP___HASH_TABLE