libcxx/include/__hash_table

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