contrib/libc++/include/__hash_table

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