contrib/llvm-project/libcxx/include/__hash_table

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