contrib/libc++/include/__hash_table

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