contrib/libc++/include/__hash_table

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