contrib/libc++/include/__hash_table

   1 // -*- C++ -*-
   2 //===----------------------------------------------------------------------===//
   3 //
   4 //                     The LLVM Compiler Infrastructure
   5 //
   6 // This file is dual licensed under the MIT and the University of Illinois Open
   7 // Source Licenses. See LICENSE.TXT for details.
   8 //
   9 //===----------------------------------------------------------------------===//
  10
  11 #ifndef _LIBCPP__HASH_TABLE
  12 #define _LIBCPP__HASH_TABLE
  13
  14 #include <__config>
  15 #include <initializer_list>
  16 #include <memory>
  17 #include <iterator>
  18 #include <algorithm>
  19 #include <cmath>
  20
  21 #include <__undef_min_max>
  22
  23 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
  24 #pragma GCC system_header
  25 #endif
  26
  27 _LIBCPP_BEGIN_NAMESPACE_STD
  28
  29 _LIBCPP_FUNC_VIS
  30 size_t __next_prime(size_t __n);
  31
  32 template <class _NodePtr>
  33 struct __hash_node_base
  34 {
  35     typedef __hash_node_base __first_node;
  36
  37     _NodePtr    __next_;
  38
  39     _LIBCPP_INLINE_VISIBILITY __hash_node_base() _NOEXCEPT : __next_(nullptr) {}
  40 };
  41
  42 template <class _Tp, class _VoidPtr>
  43 struct __hash_node
  44     : public __hash_node_base
  45              <
  46                  typename pointer_traits<_VoidPtr>::template
  47 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
  48                      rebind<__hash_node<_Tp, _VoidPtr> >
  49 #else
  50                      rebind<__hash_node<_Tp, _VoidPtr> >::other
  51 #endif
  52              >
  53 {
  54     typedef _Tp value_type;
  55
  56     size_t     __hash_;
  57     value_type __value_;
  58 };
  59
  60 inline _LIBCPP_INLINE_VISIBILITY
  61 bool
  62 __is_power2(size_t __bc)
  63 {
  64     return __bc > 2 && !(__bc & (__bc - 1));
  65 }
  66
  67 inline _LIBCPP_INLINE_VISIBILITY
  68 size_t
  69 __constrain_hash(size_t __h, size_t __bc)
  70 {
  71     return !(__bc & (__bc - 1)) ? __h & (__bc - 1) : __h % __bc;
  72 }
  73
  74 inline _LIBCPP_INLINE_VISIBILITY
  75 size_t
  76 __next_pow2(size_t __n)
  77 {
  78     return size_t(1) << (std::numeric_limits<size_t>::digits - __clz(__n-1));
  79 }
  80
  81 template <class _Tp, class _Hash, class _Equal, class _Alloc> class __hash_table;
  82 template <class _ConstNodePtr> class _LIBCPP_TYPE_VIS __hash_const_iterator;
  83 template <class _HashIterator> class _LIBCPP_TYPE_VIS __hash_map_iterator;
  84 template <class _HashIterator> class _LIBCPP_TYPE_VIS __hash_map_const_iterator;
  85 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
  86     class _LIBCPP_TYPE_VIS unordered_map;
  87
  88 template <class _NodePtr>
  89 class _LIBCPP_TYPE_VIS __hash_iterator
  90 {
  91     typedef _NodePtr __node_pointer;
  92
  93     __node_pointer            __node_;
  94
  95 public:
  96     typedef forward_iterator_tag                         iterator_category;
  97     typedef typename pointer_traits<__node_pointer>::element_type::value_type value_type;
  98     typedef typename pointer_traits<__node_pointer>::difference_type difference_type;
  99     typedef value_type&                                  reference;
 100     typedef typename pointer_traits<__node_pointer>::template
 101 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
 102                      rebind<value_type>
 103 #else
 104                      rebind<value_type>::other
 105 #endif
 106                                                          pointer;
 107
 108     _LIBCPP_INLINE_VISIBILITY __hash_iterator() _NOEXCEPT {}
 109
 110     _LIBCPP_INLINE_VISIBILITY
 111         reference operator*() const {return __node_->__value_;}
 112     _LIBCPP_INLINE_VISIBILITY
 113         pointer operator->() const {return pointer_traits<pointer>::pointer_to(__node_->__value_);}
 114
 115     _LIBCPP_INLINE_VISIBILITY
 116     __hash_iterator& operator++()
 117     {
 118         __node_ = __node_->__next_;
 119         return *this;
 120     }
 121
 122     _LIBCPP_INLINE_VISIBILITY
 123     __hash_iterator operator++(int)
 124     {
 125         __hash_iterator __t(*this);
 126         ++(*this);
 127         return __t;
 128     }
 129
 130     friend _LIBCPP_INLINE_VISIBILITY
 131     bool operator==(const __hash_iterator& __x, const __hash_iterator& __y)
 132         {return __x.__node_ == __y.__node_;}
 133     friend _LIBCPP_INLINE_VISIBILITY
 134     bool operator!=(const __hash_iterator& __x, const __hash_iterator& __y)
 135         {return __x.__node_ != __y.__node_;}
 136
 137 private:
 138     _LIBCPP_INLINE_VISIBILITY
 139     __hash_iterator(__node_pointer __node) _NOEXCEPT
 140         : __node_(__node)
 141         {}
 142
 143     template <class, class, class, class> friend class __hash_table;
 144     template <class> friend class _LIBCPP_TYPE_VIS __hash_const_iterator;
 145     template <class> friend class _LIBCPP_TYPE_VIS __hash_map_iterator;
 146     template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_map;
 147     template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_multimap;
 148 };
 149
 150 template <class _ConstNodePtr>
 151 class _LIBCPP_TYPE_VIS __hash_const_iterator
 152 {
 153     typedef _ConstNodePtr __node_pointer;
 154
 155     __node_pointer         __node_;
 156
 157     typedef typename remove_const<
 158         typename pointer_traits<__node_pointer>::element_type
 159                                  >::type __node;
 160
 161 public:
 162     typedef forward_iterator_tag                       iterator_category;
 163     typedef typename __node::value_type                value_type;
 164     typedef typename pointer_traits<__node_pointer>::difference_type difference_type;
 165     typedef const value_type&                          reference;
 166     typedef typename pointer_traits<__node_pointer>::template
 167 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
 168             rebind<const value_type>
 169 #else
 170             rebind<const value_type>::other
 171 #endif
 172                                                        pointer;
 173     typedef typename pointer_traits<__node_pointer>::template
 174 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
 175             rebind<__node>
 176 #else
 177             rebind<__node>::other
 178 #endif
 179                                                       __non_const_node_pointer;
 180     typedef __hash_iterator<__non_const_node_pointer> __non_const_iterator;
 181
 182     _LIBCPP_INLINE_VISIBILITY __hash_const_iterator() _NOEXCEPT {}
 183     _LIBCPP_INLINE_VISIBILITY
 184     __hash_const_iterator(const __non_const_iterator& __x) _NOEXCEPT
 185         : __node_(__x.__node_)
 186         {}
 187
 188     _LIBCPP_INLINE_VISIBILITY
 189         reference operator*() const {return __node_->__value_;}
 190     _LIBCPP_INLINE_VISIBILITY
 191         pointer operator->() const {return pointer_traits<pointer>::pointer_to(__node_->__value_);}
 192
 193     _LIBCPP_INLINE_VISIBILITY
 194     __hash_const_iterator& operator++()
 195     {
 196         __node_ = __node_->__next_;
 197         return *this;
 198     }
 199
 200     _LIBCPP_INLINE_VISIBILITY
 201     __hash_const_iterator operator++(int)
 202     {
 203         __hash_const_iterator __t(*this);
 204         ++(*this);
 205         return __t;
 206     }
 207
 208     friend _LIBCPP_INLINE_VISIBILITY
 209     bool operator==(const __hash_const_iterator& __x, const __hash_const_iterator& __y)
 210         {return __x.__node_ == __y.__node_;}
 211     friend _LIBCPP_INLINE_VISIBILITY
 212     bool operator!=(const __hash_const_iterator& __x, const __hash_const_iterator& __y)
 213         {return __x.__node_ != __y.__node_;}
 214
 215 private:
 216     _LIBCPP_INLINE_VISIBILITY
 217     __hash_const_iterator(__node_pointer __node) _NOEXCEPT
 218         : __node_(__node)
 219         {}
 220
 221     template <class, class, class, class> friend class __hash_table;
 222     template <class> friend class _LIBCPP_TYPE_VIS __hash_map_const_iterator;
 223     template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_map;
 224     template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_multimap;
 225 };
 226
 227 template <class _ConstNodePtr> class _LIBCPP_TYPE_VIS __hash_const_local_iterator;
 228
 229 template <class _NodePtr>
 230 class _LIBCPP_TYPE_VIS __hash_local_iterator
 231 {
 232     typedef _NodePtr __node_pointer;
 233
 234     __node_pointer         __node_;
 235     size_t                 __bucket_;
 236     size_t                 __bucket_count_;
 237
 238     typedef pointer_traits<__node_pointer>          __pointer_traits;
 239 public:
 240     typedef forward_iterator_tag                                iterator_category;
 241     typedef typename __pointer_traits::element_type::value_type value_type;
 242     typedef typename __pointer_traits::difference_type          difference_type;
 243     typedef value_type&                                         reference;
 244     typedef typename __pointer_traits::template
 245 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
 246             rebind<value_type>
 247 #else
 248             rebind<value_type>::other
 249 #endif
 250                                                                 pointer;
 251
 252     _LIBCPP_INLINE_VISIBILITY __hash_local_iterator() _NOEXCEPT {}
 253
 254     _LIBCPP_INLINE_VISIBILITY
 255         reference operator*() const {return __node_->__value_;}
 256     _LIBCPP_INLINE_VISIBILITY
 257         pointer operator->() const {return pointer_traits<pointer>::pointer_to(__node_->__value_);}
 258
 259     _LIBCPP_INLINE_VISIBILITY
 260     __hash_local_iterator& operator++()
 261     {
 262         __node_ = __node_->__next_;
 263         if (__node_ != nullptr && __constrain_hash(__node_->__hash_, __bucket_count_) != __bucket_)
 264             __node_ = nullptr;
 265         return *this;
 266     }
 267
 268     _LIBCPP_INLINE_VISIBILITY
 269     __hash_local_iterator operator++(int)
 270     {
 271         __hash_local_iterator __t(*this);
 272         ++(*this);
 273         return __t;
 274     }
 275
 276     friend _LIBCPP_INLINE_VISIBILITY
 277     bool operator==(const __hash_local_iterator& __x, const __hash_local_iterator& __y)
 278         {return __x.__node_ == __y.__node_;}
 279     friend _LIBCPP_INLINE_VISIBILITY
 280     bool operator!=(const __hash_local_iterator& __x, const __hash_local_iterator& __y)
 281         {return __x.__node_ != __y.__node_;}
 282
 283 private:
 284     _LIBCPP_INLINE_VISIBILITY
 285     __hash_local_iterator(__node_pointer __node, size_t __bucket,
 286                           size_t __bucket_count) _NOEXCEPT
 287         : __node_(__node),
 288           __bucket_(__bucket),
 289           __bucket_count_(__bucket_count)
 290         {
 291             if (__node_ != nullptr)
 292                 __node_ = __node_->__next_;
 293         }
 294
 295     template <class, class, class, class> friend class __hash_table;
 296     template <class> friend class _LIBCPP_TYPE_VIS __hash_const_local_iterator;
 297     template <class> friend class _LIBCPP_TYPE_VIS __hash_map_iterator;
 298 };
 299
 300 template <class _ConstNodePtr>
 301 class _LIBCPP_TYPE_VIS __hash_const_local_iterator
 302 {
 303     typedef _ConstNodePtr __node_pointer;
 304
 305     __node_pointer         __node_;
 306     size_t                 __bucket_;
 307     size_t                 __bucket_count_;
 308
 309     typedef pointer_traits<__node_pointer>          __pointer_traits;
 310     typedef typename __pointer_traits::element_type __node;
 311     typedef typename remove_const<__node>::type     __non_const_node;
 312     typedef typename pointer_traits<__node_pointer>::template
 313 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
 314             rebind<__non_const_node>
 315 #else
 316             rebind<__non_const_node>::other
 317 #endif
 318                                                     __non_const_node_pointer;
 319     typedef __hash_local_iterator<__non_const_node_pointer>
 320                                                     __non_const_iterator;
 321 public:
 322     typedef forward_iterator_tag                       iterator_category;
 323     typedef typename remove_const<
 324                         typename __pointer_traits::element_type::value_type
 325                      >::type                           value_type;
 326     typedef typename __pointer_traits::difference_type difference_type;
 327     typedef const value_type&                          reference;
 328     typedef typename __pointer_traits::template
 329 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
 330             rebind<const value_type>
 331 #else
 332             rebind<const value_type>::other
 333 #endif
 334                                                        pointer;
 335
 336     _LIBCPP_INLINE_VISIBILITY __hash_const_local_iterator() _NOEXCEPT {}
 337     _LIBCPP_INLINE_VISIBILITY
 338     __hash_const_local_iterator(const __non_const_iterator& __x) _NOEXCEPT
 339         : __node_(__x.__node_),
 340           __bucket_(__x.__bucket_),
 341           __bucket_count_(__x.__bucket_count_)
 342         {}
 343
 344     _LIBCPP_INLINE_VISIBILITY
 345         reference operator*() const {return __node_->__value_;}
 346     _LIBCPP_INLINE_VISIBILITY
 347         pointer operator->() const {return pointer_traits<pointer>::pointer_to(__node_->__value_);}
 348
 349     _LIBCPP_INLINE_VISIBILITY
 350     __hash_const_local_iterator& operator++()
 351     {
 352         __node_ = __node_->__next_;
 353         if (__node_ != nullptr && __constrain_hash(__node_->__hash_, __bucket_count_) != __bucket_)
 354             __node_ = nullptr;
 355         return *this;
 356     }
 357
 358     _LIBCPP_INLINE_VISIBILITY
 359     __hash_const_local_iterator operator++(int)
 360     {
 361         __hash_const_local_iterator __t(*this);
 362         ++(*this);
 363         return __t;
 364     }
 365
 366     friend _LIBCPP_INLINE_VISIBILITY
 367     bool operator==(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y)
 368         {return __x.__node_ == __y.__node_;}
 369     friend _LIBCPP_INLINE_VISIBILITY
 370     bool operator!=(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y)
 371         {return __x.__node_ != __y.__node_;}
 372
 373 private:
 374     _LIBCPP_INLINE_VISIBILITY
 375     __hash_const_local_iterator(__node_pointer __node, size_t __bucket,
 376                                 size_t __bucket_count) _NOEXCEPT
 377         : __node_(__node),
 378           __bucket_(__bucket),
 379           __bucket_count_(__bucket_count)
 380         {
 381             if (__node_ != nullptr)
 382                 __node_ = __node_->__next_;
 383         }
 384
 385     template <class, class, class, class> friend class __hash_table;
 386     template <class> friend class _LIBCPP_TYPE_VIS __hash_map_const_iterator;
 387 };
 388
 389 template <class _Alloc>
 390 class __bucket_list_deallocator
 391 {
 392     typedef _Alloc                                          allocator_type;
 393     typedef allocator_traits<allocator_type>                __alloc_traits;
 394     typedef typename __alloc_traits::size_type              size_type;
 395
 396     __compressed_pair<size_type, allocator_type> __data_;
 397 public:
 398     typedef typename __alloc_traits::pointer pointer;
 399
 400     _LIBCPP_INLINE_VISIBILITY
 401     __bucket_list_deallocator()
 402         _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
 403         : __data_(0) {}
 404
 405     _LIBCPP_INLINE_VISIBILITY
 406     __bucket_list_deallocator(const allocator_type& __a, size_type __size)
 407         _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value)
 408         : __data_(__size, __a) {}
 409
 410 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 411
 412     _LIBCPP_INLINE_VISIBILITY
 413     __bucket_list_deallocator(__bucket_list_deallocator&& __x)
 414         _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
 415         : __data_(_VSTD::move(__x.__data_))
 416     {
 417         __x.size() = 0;
 418     }
 419
 420 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 421
 422     _LIBCPP_INLINE_VISIBILITY
 423     size_type& size() _NOEXCEPT {return __data_.first();}
 424     _LIBCPP_INLINE_VISIBILITY
 425     size_type  size() const _NOEXCEPT {return __data_.first();}
 426
 427     _LIBCPP_INLINE_VISIBILITY
 428     allocator_type& __alloc() _NOEXCEPT {return __data_.second();}
 429     _LIBCPP_INLINE_VISIBILITY
 430     const allocator_type& __alloc() const _NOEXCEPT {return __data_.second();}
 431
 432     _LIBCPP_INLINE_VISIBILITY
 433     void operator()(pointer __p) _NOEXCEPT
 434     {
 435         __alloc_traits::deallocate(__alloc(), __p, size());
 436     }
 437 };
 438
 439 template <class _Alloc> class __hash_map_node_destructor;
 440
 441 template <class _Alloc>
 442 class __hash_node_destructor
 443 {
 444     typedef _Alloc                                          allocator_type;
 445     typedef allocator_traits<allocator_type>                __alloc_traits;
 446     typedef typename __alloc_traits::value_type::value_type value_type;
 447 public:
 448     typedef typename __alloc_traits::pointer                pointer;
 449 private:
 450
 451     allocator_type& __na_;
 452
 453     __hash_node_destructor& operator=(const __hash_node_destructor&);
 454
 455 public:
 456     bool __value_constructed;
 457
 458     _LIBCPP_INLINE_VISIBILITY
 459     explicit __hash_node_destructor(allocator_type& __na,
 460                                     bool __constructed = false) _NOEXCEPT
 461         : __na_(__na),
 462           __value_constructed(__constructed)
 463         {}
 464
 465     _LIBCPP_INLINE_VISIBILITY
 466     void operator()(pointer __p) _NOEXCEPT
 467     {
 468         if (__value_constructed)
 469             __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_));
 470         if (__p)
 471             __alloc_traits::deallocate(__na_, __p, 1);
 472     }
 473
 474     template <class> friend class __hash_map_node_destructor;
 475 };
 476
 477 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 478 class __hash_table
 479 {
 480 public:
 481     typedef _Tp    value_type;
 482     typedef _Hash  hasher;
 483     typedef _Equal key_equal;
 484     typedef _Alloc allocator_type;
 485
 486 private:
 487     typedef allocator_traits<allocator_type> __alloc_traits;
 488 public:
 489     typedef value_type&                              reference;
 490     typedef const value_type&                        const_reference;
 491     typedef typename __alloc_traits::pointer         pointer;
 492     typedef typename __alloc_traits::const_pointer   const_pointer;
 493     typedef typename __alloc_traits::size_type       size_type;
 494     typedef typename __alloc_traits::difference_type difference_type;
 495 public:
 496     // Create __node
 497     typedef __hash_node<value_type, typename __alloc_traits::void_pointer> __node;
 498     typedef typename __alloc_traits::template
 499 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
 500             rebind_alloc<__node>
 501 #else
 502             rebind_alloc<__node>::other
 503 #endif
 504                                                      __node_allocator;
 505     typedef allocator_traits<__node_allocator>       __node_traits;
 506     typedef typename __node_traits::pointer          __node_pointer;
 507     typedef typename __node_traits::pointer          __node_const_pointer;
 508     typedef __hash_node_base<__node_pointer>         __first_node;
 509     typedef typename pointer_traits<__node_pointer>::template
 510 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
 511             rebind<__first_node>
 512 #else
 513             rebind<__first_node>::other
 514 #endif
 515                                                      __node_base_pointer;
 516
 517 private:
 518
 519     typedef typename __node_traits::template
 520 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
 521             rebind_alloc<__node_pointer>
 522 #else
 523             rebind_alloc<__node_pointer>::other
 524 #endif
 525                                                             __pointer_allocator;
 526     typedef __bucket_list_deallocator<__pointer_allocator> __bucket_list_deleter;
 527     typedef unique_ptr<__node_pointer[], __bucket_list_deleter> __bucket_list;
 528     typedef allocator_traits<__pointer_allocator>          __pointer_alloc_traits;
 529     typedef typename __bucket_list_deleter::pointer __node_pointer_pointer;
 530
 531     // --- Member data begin ---
 532     __bucket_list                                     __bucket_list_;
 533     __compressed_pair<__first_node, __node_allocator> __p1_;
 534     __compressed_pair<size_type, hasher>              __p2_;
 535     __compressed_pair<float, key_equal>               __p3_;
 536     // --- Member data end ---
 537
 538     _LIBCPP_INLINE_VISIBILITY
 539     size_type& size() _NOEXCEPT {return __p2_.first();}
 540 public:
 541     _LIBCPP_INLINE_VISIBILITY
 542     size_type  size() const _NOEXCEPT {return __p2_.first();}
 543
 544     _LIBCPP_INLINE_VISIBILITY
 545     hasher& hash_function() _NOEXCEPT {return __p2_.second();}
 546     _LIBCPP_INLINE_VISIBILITY
 547     const hasher& hash_function() const _NOEXCEPT {return __p2_.second();}
 548
 549     _LIBCPP_INLINE_VISIBILITY
 550     float& max_load_factor() _NOEXCEPT {return __p3_.first();}
 551     _LIBCPP_INLINE_VISIBILITY
 552     float  max_load_factor() const _NOEXCEPT {return __p3_.first();}
 553
 554     _LIBCPP_INLINE_VISIBILITY
 555     key_equal& key_eq() _NOEXCEPT {return __p3_.second();}
 556     _LIBCPP_INLINE_VISIBILITY
 557     const key_equal& key_eq() const _NOEXCEPT {return __p3_.second();}
 558
 559     _LIBCPP_INLINE_VISIBILITY
 560     __node_allocator& __node_alloc() _NOEXCEPT {return __p1_.second();}
 561     _LIBCPP_INLINE_VISIBILITY
 562     const __node_allocator& __node_alloc() const _NOEXCEPT
 563         {return __p1_.second();}
 564
 565 public:
 566     typedef __hash_iterator<__node_pointer>                   iterator;
 567     typedef __hash_const_iterator<__node_pointer>             const_iterator;
 568     typedef __hash_local_iterator<__node_pointer>             local_iterator;
 569     typedef __hash_const_local_iterator<__node_pointer>       const_local_iterator;
 570
 571     __hash_table()
 572         _NOEXCEPT_(
 573             is_nothrow_default_constructible<__bucket_list>::value &&
 574             is_nothrow_default_constructible<__first_node>::value &&
 575             is_nothrow_default_constructible<__node_allocator>::value &&
 576             is_nothrow_default_constructible<hasher>::value &&
 577             is_nothrow_default_constructible<key_equal>::value);
 578     __hash_table(const hasher& __hf, const key_equal& __eql);
 579     __hash_table(const hasher& __hf, const key_equal& __eql,
 580                  const allocator_type& __a);
 581     explicit __hash_table(const allocator_type& __a);
 582     __hash_table(const __hash_table& __u);
 583     __hash_table(const __hash_table& __u, const allocator_type& __a);
 584 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 585     __hash_table(__hash_table&& __u)
 586         _NOEXCEPT_(
 587             is_nothrow_move_constructible<__bucket_list>::value &&
 588             is_nothrow_move_constructible<__first_node>::value &&
 589             is_nothrow_move_constructible<__node_allocator>::value &&
 590             is_nothrow_move_constructible<hasher>::value &&
 591             is_nothrow_move_constructible<key_equal>::value);
 592     __hash_table(__hash_table&& __u, const allocator_type& __a);
 593 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 594     ~__hash_table();
 595
 596     __hash_table& operator=(const __hash_table& __u);
 597 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 598     __hash_table& operator=(__hash_table&& __u)
 599         _NOEXCEPT_(
 600             __node_traits::propagate_on_container_move_assignment::value &&
 601             is_nothrow_move_assignable<__node_allocator>::value &&
 602             is_nothrow_move_assignable<hasher>::value &&
 603             is_nothrow_move_assignable<key_equal>::value);
 604 #endif
 605     template <class _InputIterator>
 606         void __assign_unique(_InputIterator __first, _InputIterator __last);
 607     template <class _InputIterator>
 608         void __assign_multi(_InputIterator __first, _InputIterator __last);
 609
 610     _LIBCPP_INLINE_VISIBILITY
 611     size_type max_size() const _NOEXCEPT
 612     {
 613         return allocator_traits<__pointer_allocator>::max_size(
 614             __bucket_list_.get_deleter().__alloc());
 615     }
 616
 617     pair<iterator, bool> __node_insert_unique(__node_pointer __nd);
 618     iterator             __node_insert_multi(__node_pointer __nd);
 619     iterator             __node_insert_multi(const_iterator __p,
 620                                              __node_pointer __nd);
 621
 622 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
 623     template <class... _Args>
 624         pair<iterator, bool> __emplace_unique(_Args&&... __args);
 625     template <class... _Args>
 626         iterator __emplace_multi(_Args&&... __args);
 627     template <class... _Args>
 628         iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args);
 629 #endif  // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
 630
 631     pair<iterator, bool> __insert_unique(const value_type& __x);
 632
 633 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 634     template <class _Pp>
 635         pair<iterator, bool> __insert_unique(_Pp&& __x);
 636 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 637
 638 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 639     template <class _Pp>
 640         iterator __insert_multi(_Pp&& __x);
 641     template <class _Pp>
 642         iterator __insert_multi(const_iterator __p, _Pp&& __x);
 643 #else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 644     iterator __insert_multi(const value_type& __x);
 645     iterator __insert_multi(const_iterator __p, const value_type& __x);
 646 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 647
 648     void clear() _NOEXCEPT;
 649     void rehash(size_type __n);
 650     _LIBCPP_INLINE_VISIBILITY void reserve(size_type __n)
 651         {rehash(static_cast<size_type>(ceil(__n / max_load_factor())));}
 652
 653     _LIBCPP_INLINE_VISIBILITY
 654     size_type bucket_count() const _NOEXCEPT
 655     {
 656         return __bucket_list_.get_deleter().size();
 657     }
 658
 659     iterator       begin() _NOEXCEPT;
 660     iterator       end() _NOEXCEPT;
 661     const_iterator begin() const _NOEXCEPT;
 662     const_iterator end() const _NOEXCEPT;
 663
 664     template <class _Key>
 665         _LIBCPP_INLINE_VISIBILITY
 666         size_type bucket(const _Key& __k) const
 667             {return __constrain_hash(hash_function()(__k), bucket_count());}
 668
 669     template <class _Key>
 670         iterator       find(const _Key& __x);
 671     template <class _Key>
 672         const_iterator find(const _Key& __x) const;
 673
 674     typedef __hash_node_destructor<__node_allocator> _Dp;
 675     typedef unique_ptr<__node, _Dp> __node_holder;
 676
 677     iterator erase(const_iterator __p);
 678     iterator erase(const_iterator __first, const_iterator __last);
 679     template <class _Key>
 680         size_type __erase_unique(const _Key& __k);
 681     template <class _Key>
 682         size_type __erase_multi(const _Key& __k);
 683     __node_holder remove(const_iterator __p) _NOEXCEPT;
 684
 685     template <class _Key>
 686         size_type __count_unique(const _Key& __k) const;
 687     template <class _Key>
 688         size_type __count_multi(const _Key& __k) const;
 689
 690     template <class _Key>
 691         pair<iterator, iterator>
 692         __equal_range_unique(const _Key& __k);
 693     template <class _Key>
 694         pair<const_iterator, const_iterator>
 695         __equal_range_unique(const _Key& __k) const;
 696
 697     template <class _Key>
 698         pair<iterator, iterator>
 699         __equal_range_multi(const _Key& __k);
 700     template <class _Key>
 701         pair<const_iterator, const_iterator>
 702         __equal_range_multi(const _Key& __k) const;
 703
 704     void swap(__hash_table& __u)
 705         _NOEXCEPT_(
 706             (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value ||
 707              __is_nothrow_swappable<__pointer_allocator>::value) &&
 708             (!__node_traits::propagate_on_container_swap::value ||
 709              __is_nothrow_swappable<__node_allocator>::value) &&
 710             __is_nothrow_swappable<hasher>::value &&
 711             __is_nothrow_swappable<key_equal>::value);
 712
 713     _LIBCPP_INLINE_VISIBILITY
 714     size_type max_bucket_count() const _NOEXCEPT
 715         {return __pointer_alloc_traits::max_size(__bucket_list_.get_deleter().__alloc());}
 716     size_type bucket_size(size_type __n) const;
 717     _LIBCPP_INLINE_VISIBILITY float load_factor() const _NOEXCEPT
 718     {
 719         size_type __bc = bucket_count();
 720         return __bc != 0 ? (float)size() / __bc : 0.f;
 721     }
 722     _LIBCPP_INLINE_VISIBILITY void max_load_factor(float __mlf) _NOEXCEPT
 723         {max_load_factor() = _VSTD::max(__mlf, load_factor());}
 724
 725     _LIBCPP_INLINE_VISIBILITY local_iterator       begin(size_type __n)
 726         {return local_iterator(__bucket_list_[__n], __n, bucket_count());}
 727     _LIBCPP_INLINE_VISIBILITY local_iterator       end(size_type __n)
 728         {return local_iterator(nullptr, __n, bucket_count());}
 729     _LIBCPP_INLINE_VISIBILITY const_local_iterator cbegin(size_type __n) const
 730         {return const_local_iterator(__bucket_list_[__n], __n, bucket_count());}
 731     _LIBCPP_INLINE_VISIBILITY const_local_iterator cend(size_type __n) const
 732         {return const_local_iterator(nullptr, __n, bucket_count());}
 733 private:
 734     void __rehash(size_type __n);
 735
 736 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 737 #ifndef _LIBCPP_HAS_NO_VARIADICS
 738     template <class ..._Args>
 739         __node_holder __construct_node(_Args&& ...__args);
 740 #endif  // _LIBCPP_HAS_NO_VARIADICS
 741     __node_holder __construct_node(value_type&& __v, size_t __hash);
 742 #else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 743     __node_holder __construct_node(const value_type& __v);
 744 #endif
 745     __node_holder __construct_node(const value_type& __v, size_t __hash);
 746
 747     _LIBCPP_INLINE_VISIBILITY
 748     void __copy_assign_alloc(const __hash_table& __u)
 749         {__copy_assign_alloc(__u, integral_constant<bool,
 750              __node_traits::propagate_on_container_copy_assignment::value>());}
 751     void __copy_assign_alloc(const __hash_table& __u, true_type);
 752     _LIBCPP_INLINE_VISIBILITY
 753         void __copy_assign_alloc(const __hash_table&, false_type) {}
 754
 755     void __move_assign(__hash_table& __u, false_type);
 756     void __move_assign(__hash_table& __u, true_type)
 757         _NOEXCEPT_(
 758             is_nothrow_move_assignable<__node_allocator>::value &&
 759             is_nothrow_move_assignable<hasher>::value &&
 760             is_nothrow_move_assignable<key_equal>::value);
 761     _LIBCPP_INLINE_VISIBILITY
 762     void __move_assign_alloc(__hash_table& __u)
 763         _NOEXCEPT_(
 764             !__node_traits::propagate_on_container_move_assignment::value ||
 765             (is_nothrow_move_assignable<__pointer_allocator>::value &&
 766              is_nothrow_move_assignable<__node_allocator>::value))
 767         {__move_assign_alloc(__u, integral_constant<bool,
 768              __node_traits::propagate_on_container_move_assignment::value>());}
 769     _LIBCPP_INLINE_VISIBILITY
 770     void __move_assign_alloc(__hash_table& __u, true_type)
 771         _NOEXCEPT_(
 772             is_nothrow_move_assignable<__pointer_allocator>::value &&
 773             is_nothrow_move_assignable<__node_allocator>::value)
 774     {
 775         __bucket_list_.get_deleter().__alloc() =
 776                 _VSTD::move(__u.__bucket_list_.get_deleter().__alloc());
 777         __node_alloc() = _VSTD::move(__u.__node_alloc());
 778     }
 779     _LIBCPP_INLINE_VISIBILITY
 780         void __move_assign_alloc(__hash_table&, false_type) _NOEXCEPT {}
 781
 782     template <class _Ap>
 783     _LIBCPP_INLINE_VISIBILITY
 784     static
 785     void
 786     __swap_alloc(_Ap& __x, _Ap& __y)
 787         _NOEXCEPT_(
 788             !allocator_traits<_Ap>::propagate_on_container_swap::value ||
 789             __is_nothrow_swappable<_Ap>::value)
 790     {
 791         __swap_alloc(__x, __y,
 792                      integral_constant<bool,
 793                         allocator_traits<_Ap>::propagate_on_container_swap::value
 794                                       >());
 795     }
 796
 797     template <class _Ap>
 798     _LIBCPP_INLINE_VISIBILITY
 799     static
 800     void
 801     __swap_alloc(_Ap& __x, _Ap& __y, true_type)
 802         _NOEXCEPT_(__is_nothrow_swappable<_Ap>::value)
 803     {
 804         using _VSTD::swap;
 805         swap(__x, __y);
 806     }
 807
 808     template <class _Ap>
 809     _LIBCPP_INLINE_VISIBILITY
 810     static
 811     void
 812     __swap_alloc(_Ap&, _Ap&, false_type) _NOEXCEPT {}
 813
 814     void __deallocate(__node_pointer __np) _NOEXCEPT;
 815     __node_pointer __detach() _NOEXCEPT;
 816
 817     template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_map;
 818     template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_multimap;
 819 };
 820
 821 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 822 inline _LIBCPP_INLINE_VISIBILITY
 823 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table()
 824     _NOEXCEPT_(
 825         is_nothrow_default_constructible<__bucket_list>::value &&
 826         is_nothrow_default_constructible<__first_node>::value &&
 827         is_nothrow_default_constructible<hasher>::value &&
 828         is_nothrow_default_constructible<key_equal>::value)
 829     : __p2_(0),
 830       __p3_(1.0f)
 831 {
 832 }
 833
 834 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 835 inline _LIBCPP_INLINE_VISIBILITY
 836 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf,
 837                                                        const key_equal& __eql)
 838     : __bucket_list_(nullptr, __bucket_list_deleter()),
 839       __p1_(),
 840       __p2_(0, __hf),
 841       __p3_(1.0f, __eql)
 842 {
 843 }
 844
 845 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 846 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf,
 847                                                        const key_equal& __eql,
 848                                                        const allocator_type& __a)
 849     : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
 850       __p1_(__node_allocator(__a)),
 851       __p2_(0, __hf),
 852       __p3_(1.0f, __eql)
 853 {
 854 }
 855
 856 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 857 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const allocator_type& __a)
 858     : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
 859       __p1_(__node_allocator(__a)),
 860       __p2_(0),
 861       __p3_(1.0f)
 862 {
 863 }
 864
 865 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 866 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u)
 867     : __bucket_list_(nullptr,
 868           __bucket_list_deleter(allocator_traits<__pointer_allocator>::
 869               select_on_container_copy_construction(
 870                   __u.__bucket_list_.get_deleter().__alloc()), 0)),
 871       __p1_(allocator_traits<__node_allocator>::
 872           select_on_container_copy_construction(__u.__node_alloc())),
 873       __p2_(0, __u.hash_function()),
 874       __p3_(__u.__p3_)
 875 {
 876 }
 877
 878 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 879 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u,
 880                                                        const allocator_type& __a)
 881     : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
 882       __p1_(__node_allocator(__a)),
 883       __p2_(0, __u.hash_function()),
 884       __p3_(__u.__p3_)
 885 {
 886 }
 887
 888 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 889
 890 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 891 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u)
 892         _NOEXCEPT_(
 893             is_nothrow_move_constructible<__bucket_list>::value &&
 894             is_nothrow_move_constructible<__first_node>::value &&
 895             is_nothrow_move_constructible<hasher>::value &&
 896             is_nothrow_move_constructible<key_equal>::value)
 897     : __bucket_list_(_VSTD::move(__u.__bucket_list_)),
 898       __p1_(_VSTD::move(__u.__p1_)),
 899       __p2_(_VSTD::move(__u.__p2_)),
 900       __p3_(_VSTD::move(__u.__p3_))
 901 {
 902     if (size() > 0)
 903     {
 904         __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] =
 905             static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()));
 906         __u.__p1_.first().__next_ = nullptr;
 907         __u.size() = 0;
 908     }
 909 }
 910
 911 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 912 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u,
 913                                                        const allocator_type& __a)
 914     : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
 915       __p1_(__node_allocator(__a)),
 916       __p2_(0, _VSTD::move(__u.hash_function())),
 917       __p3_(_VSTD::move(__u.__p3_))
 918 {
 919     if (__a == allocator_type(__u.__node_alloc()))
 920     {
 921         __bucket_list_.reset(__u.__bucket_list_.release());
 922         __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size();
 923         __u.__bucket_list_.get_deleter().size() = 0;
 924         if (__u.size() > 0)
 925         {
 926             __p1_.first().__next_ = __u.__p1_.first().__next_;
 927             __u.__p1_.first().__next_ = nullptr;
 928             __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] =
 929                 static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()));
 930             size() = __u.size();
 931             __u.size() = 0;
 932         }
 933     }
 934 }
 935
 936 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 937
 938 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 939 __hash_table<_Tp, _Hash, _Equal, _Alloc>::~__hash_table()
 940 {
 941     __deallocate(__p1_.first().__next_);
 942 }
 943
 944 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 945 void
 946 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__copy_assign_alloc(
 947         const __hash_table& __u, true_type)
 948 {
 949     if (__node_alloc() != __u.__node_alloc())
 950     {
 951         clear();
 952         __bucket_list_.reset();
 953         __bucket_list_.get_deleter().size() = 0;
 954     }
 955     __bucket_list_.get_deleter().__alloc() = __u.__bucket_list_.get_deleter().__alloc();
 956     __node_alloc() = __u.__node_alloc();
 957 }
 958
 959 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 960 __hash_table<_Tp, _Hash, _Equal, _Alloc>&
 961 __hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(const __hash_table& __u)
 962 {
 963     if (this != &__u)
 964     {
 965         __copy_assign_alloc(__u);
 966         hash_function() = __u.hash_function();
 967         key_eq() = __u.key_eq();
 968         max_load_factor() = __u.max_load_factor();
 969         __assign_multi(__u.begin(), __u.end());
 970     }
 971     return *this;
 972 }
 973
 974 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 975 void
 976 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__deallocate(__node_pointer __np)
 977     _NOEXCEPT
 978 {
 979     __node_allocator& __na = __node_alloc();
 980     while (__np != nullptr)
 981     {
 982         __node_pointer __next = __np->__next_;
 983         __node_traits::destroy(__na, _VSTD::addressof(__np->__value_));
 984         __node_traits::deallocate(__na, __np, 1);
 985         __np = __next;
 986     }
 987 }
 988
 989 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 990 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_pointer
 991 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__detach() _NOEXCEPT
 992 {
 993     size_type __bc = bucket_count();
 994     for (size_type __i = 0; __i < __bc; ++__i)
 995         __bucket_list_[__i] = nullptr;
 996     size() = 0;
 997     __node_pointer __cache = __p1_.first().__next_;
 998     __p1_.first().__next_ = nullptr;
 999     return __cache;
1000 }
1001
1002 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1003
1004 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1005 void
1006 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign(
1007         __hash_table& __u, true_type)
1008     _NOEXCEPT_(
1009         is_nothrow_move_assignable<__node_allocator>::value &&
1010         is_nothrow_move_assignable<hasher>::value &&
1011         is_nothrow_move_assignable<key_equal>::value)
1012 {
1013     clear();
1014     __bucket_list_.reset(__u.__bucket_list_.release());
1015     __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size();
1016     __u.__bucket_list_.get_deleter().size() = 0;
1017     __move_assign_alloc(__u);
1018     size() = __u.size();
1019     hash_function() = _VSTD::move(__u.hash_function());
1020     max_load_factor() = __u.max_load_factor();
1021     key_eq() = _VSTD::move(__u.key_eq());
1022     __p1_.first().__next_ = __u.__p1_.first().__next_;
1023     if (size() > 0)
1024     {
1025         __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] =
1026             static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()));
1027         __u.__p1_.first().__next_ = nullptr;
1028         __u.size() = 0;
1029     }
1030 }
1031
1032 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1033 void
1034 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign(
1035         __hash_table& __u, false_type)
1036 {
1037     if (__node_alloc() == __u.__node_alloc())
1038         __move_assign(__u, true_type());
1039     else
1040     {
1041         hash_function() = _VSTD::move(__u.hash_function());
1042         key_eq() = _VSTD::move(__u.key_eq());
1043         max_load_factor() = __u.max_load_factor();
1044         if (bucket_count() != 0)
1045         {
1046             __node_pointer __cache = __detach();
1047 #ifndef _LIBCPP_NO_EXCEPTIONS
1048             try
1049             {
1050 #endif  // _LIBCPP_NO_EXCEPTIONS
1051                 const_iterator __i = __u.begin();
1052                 while (__cache != nullptr && __u.size() != 0)
1053                 {
1054                     __cache->__value_ = _VSTD::move(__u.remove(__i++)->__value_);
1055                     __node_pointer __next = __cache->__next_;
1056                     __node_insert_multi(__cache);
1057                     __cache = __next;
1058                 }
1059 #ifndef _LIBCPP_NO_EXCEPTIONS
1060             }
1061             catch (...)
1062             {
1063                 __deallocate(__cache);
1064                 throw;
1065             }
1066 #endif  // _LIBCPP_NO_EXCEPTIONS
1067             __deallocate(__cache);
1068         }
1069         const_iterator __i = __u.begin();
1070         while (__u.size() != 0)
1071         {
1072             __node_holder __h =
1073                     __construct_node(_VSTD::move(__u.remove(__i++)->__value_));
1074             __node_insert_multi(__h.get());
1075             __h.release();
1076         }
1077     }
1078 }
1079
1080 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1081 inline _LIBCPP_INLINE_VISIBILITY
1082 __hash_table<_Tp, _Hash, _Equal, _Alloc>&
1083 __hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(__hash_table&& __u)
1084     _NOEXCEPT_(
1085         __node_traits::propagate_on_container_move_assignment::value &&
1086         is_nothrow_move_assignable<__node_allocator>::value &&
1087         is_nothrow_move_assignable<hasher>::value &&
1088         is_nothrow_move_assignable<key_equal>::value)
1089 {
1090     __move_assign(__u, integral_constant<bool,
1091                   __node_traits::propagate_on_container_move_assignment::value>());
1092     return *this;
1093 }
1094
1095 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1096
1097 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1098 template <class _InputIterator>
1099 void
1100 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_unique(_InputIterator __first,
1101                                                           _InputIterator __last)
1102 {
1103     if (bucket_count() != 0)
1104     {
1105         __node_pointer __cache = __detach();
1106 #ifndef _LIBCPP_NO_EXCEPTIONS
1107         try
1108         {
1109 #endif  // _LIBCPP_NO_EXCEPTIONS
1110             for (; __cache != nullptr && __first != __last; ++__first)
1111             {
1112                 __cache->__value_ = *__first;
1113                 __node_pointer __next = __cache->__next_;
1114                 __node_insert_unique(__cache);
1115                 __cache = __next;
1116             }
1117 #ifndef _LIBCPP_NO_EXCEPTIONS
1118         }
1119         catch (...)
1120         {
1121             __deallocate(__cache);
1122             throw;
1123         }
1124 #endif  // _LIBCPP_NO_EXCEPTIONS
1125         __deallocate(__cache);
1126     }
1127     for (; __first != __last; ++__first)
1128         __insert_unique(*__first);
1129 }
1130
1131 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1132 template <class _InputIterator>
1133 void
1134 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_multi(_InputIterator __first,
1135                                                          _InputIterator __last)
1136 {
1137     if (bucket_count() != 0)
1138     {
1139         __node_pointer __cache = __detach();
1140 #ifndef _LIBCPP_NO_EXCEPTIONS
1141         try
1142         {
1143 #endif  // _LIBCPP_NO_EXCEPTIONS
1144             for (; __cache != nullptr && __first != __last; ++__first)
1145             {
1146                 __cache->__value_ = *__first;
1147                 __node_pointer __next = __cache->__next_;
1148                 __node_insert_multi(__cache);
1149                 __cache = __next;
1150             }
1151 #ifndef _LIBCPP_NO_EXCEPTIONS
1152         }
1153         catch (...)
1154         {
1155             __deallocate(__cache);
1156             throw;
1157         }
1158 #endif  // _LIBCPP_NO_EXCEPTIONS
1159         __deallocate(__cache);
1160     }
1161     for (; __first != __last; ++__first)
1162         __insert_multi(*__first);
1163 }
1164
1165 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1166 inline _LIBCPP_INLINE_VISIBILITY
1167 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1168 __hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() _NOEXCEPT
1169 {
1170     return iterator(__p1_.first().__next_);
1171 }
1172
1173 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1174 inline _LIBCPP_INLINE_VISIBILITY
1175 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1176 __hash_table<_Tp, _Hash, _Equal, _Alloc>::end() _NOEXCEPT
1177 {
1178     return iterator(nullptr);
1179 }
1180
1181 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1182 inline _LIBCPP_INLINE_VISIBILITY
1183 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator
1184 __hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() const _NOEXCEPT
1185 {
1186     return const_iterator(__p1_.first().__next_);
1187 }
1188
1189 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1190 inline _LIBCPP_INLINE_VISIBILITY
1191 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator
1192 __hash_table<_Tp, _Hash, _Equal, _Alloc>::end() const _NOEXCEPT
1193 {
1194     return const_iterator(nullptr);
1195 }
1196
1197 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1198 void
1199 __hash_table<_Tp, _Hash, _Equal, _Alloc>::clear() _NOEXCEPT
1200 {
1201     if (size() > 0)
1202     {
1203         __deallocate(__p1_.first().__next_);
1204         __p1_.first().__next_ = nullptr;
1205         size_type __bc = bucket_count();
1206         for (size_type __i = 0; __i < __bc; ++__i)
1207             __bucket_list_[__i] = nullptr;
1208         size() = 0;
1209     }
1210 }
1211
1212 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1213 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
1214 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique(__node_pointer __nd)
1215 {
1216     __nd->__hash_ = hash_function()(__nd->__value_);
1217     size_type __bc = bucket_count();
1218     bool __inserted = false;
1219     __node_pointer __ndptr;
1220     size_t __chash;
1221     if (__bc != 0)
1222     {
1223         __chash = __constrain_hash(__nd->__hash_, __bc);
1224         __ndptr = __bucket_list_[__chash];
1225         if (__ndptr != nullptr)
1226         {
1227             for (__ndptr = __ndptr->__next_; __ndptr != nullptr &&
1228                                              __constrain_hash(__ndptr->__hash_, __bc) == __chash;
1229                                                      __ndptr = __ndptr->__next_)
1230             {
1231                 if (key_eq()(__ndptr->__value_, __nd->__value_))
1232                     goto __done;
1233             }
1234         }
1235     }
1236     {
1237         if (size()+1 > __bc * max_load_factor() || __bc == 0)
1238         {
1239             rehash(_VSTD::max<size_type>(2 * __bc + !__is_power2(__bc),
1240                            size_type(ceil(float(size() + 1) / max_load_factor()))));
1241             __bc = bucket_count();
1242             __chash = __constrain_hash(__nd->__hash_, __bc);
1243         }
1244         // insert_after __bucket_list_[__chash], or __first_node if bucket is null
1245         __node_pointer __pn = __bucket_list_[__chash];
1246         if (__pn == nullptr)
1247         {
1248             __pn = static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()));
1249             __nd->__next_ = __pn->__next_;
1250             __pn->__next_ = __nd;
1251             // fix up __bucket_list_
1252             __bucket_list_[__chash] = __pn;
1253             if (__nd->__next_ != nullptr)
1254                 __bucket_list_[__constrain_hash(__nd->__next_->__hash_, __bc)] = __nd;
1255         }
1256         else
1257         {
1258             __nd->__next_ = __pn->__next_;
1259             __pn->__next_ = __nd;
1260         }
1261         __ndptr = __nd;
1262         // increment size
1263         ++size();
1264         __inserted = true;
1265     }
1266 __done:
1267     return pair<iterator, bool>(iterator(__ndptr), __inserted);
1268 }
1269
1270 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1271 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1272 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __cp)
1273 {
1274     __cp->__hash_ = hash_function()(__cp->__value_);
1275     size_type __bc = bucket_count();
1276     if (size()+1 > __bc * max_load_factor() || __bc == 0)
1277     {
1278         rehash(_VSTD::max<size_type>(2 * __bc + !__is_power2(__bc),
1279                        size_type(ceil(float(size() + 1) / max_load_factor()))));
1280         __bc = bucket_count();
1281     }
1282     size_t __chash = __constrain_hash(__cp->__hash_, __bc);
1283     __node_pointer __pn = __bucket_list_[__chash];
1284     if (__pn == nullptr)
1285     {
1286         __pn = static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()));
1287         __cp->__next_ = __pn->__next_;
1288         __pn->__next_ = __cp;
1289         // fix up __bucket_list_
1290         __bucket_list_[__chash] = __pn;
1291         if (__cp->__next_ != nullptr)
1292             __bucket_list_[__constrain_hash(__cp->__next_->__hash_, __bc)] = __cp;
1293     }
1294     else
1295     {
1296         for (bool __found = false; __pn->__next_ != nullptr &&
1297                                    __constrain_hash(__pn->__next_->__hash_, __bc) == __chash;
1298                                                            __pn = __pn->__next_)
1299         {
1300             //      __found    key_eq()     action
1301             //      false       false       loop
1302             //      true        true        loop
1303             //      false       true        set __found to true
1304             //      true        false       break
1305             if (__found != (__pn->__next_->__hash_ == __cp->__hash_ &&
1306                             key_eq()(__pn->__next_->__value_, __cp->__value_)))
1307             {
1308                 if (!__found)
1309                     __found = true;
1310                 else
1311                     break;
1312             }
1313         }
1314         __cp->__next_ = __pn->__next_;
1315         __pn->__next_ = __cp;
1316         if (__cp->__next_ != nullptr)
1317         {
1318             size_t __nhash = __constrain_hash(__cp->__next_->__hash_, __bc);
1319             if (__nhash != __chash)
1320                 __bucket_list_[__nhash] = __cp;
1321         }
1322     }
1323     ++size();
1324     return iterator(__cp);
1325 }
1326
1327 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1328 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1329 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(
1330         const_iterator __p, __node_pointer __cp)
1331 {
1332     if (__p != end() && key_eq()(*__p, __cp->__value_))
1333     {
1334         __node_pointer __np = __p.__node_;
1335         __cp->__hash_ = __np->__hash_;
1336         size_type __bc = bucket_count();
1337         if (size()+1 > __bc * max_load_factor() || __bc == 0)
1338         {
1339             rehash(_VSTD::max<size_type>(2 * __bc + !__is_power2(__bc),
1340                            size_type(ceil(float(size() + 1) / max_load_factor()))));
1341             __bc = bucket_count();
1342         }
1343         size_t __chash = __constrain_hash(__cp->__hash_, __bc);
1344         __node_pointer __pp = __bucket_list_[__chash];
1345         while (__pp->__next_ != __np)
1346             __pp = __pp->__next_;
1347         __cp->__next_ = __np;
1348         __pp->__next_ = __cp;
1349         ++size();
1350         return iterator(__cp);
1351     }
1352     return __node_insert_multi(__cp);
1353 }
1354
1355 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1356 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
1357 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique(const value_type& __x)
1358 {
1359     size_t __hash = hash_function()(__x);
1360     size_type __bc = bucket_count();
1361     bool __inserted = false;
1362     __node_pointer __nd;
1363     size_t __chash;
1364     if (__bc != 0)
1365     {
1366         __chash = __constrain_hash(__hash, __bc);
1367         __nd = __bucket_list_[__chash];
1368         if (__nd != nullptr)
1369         {
1370             for (__nd = __nd->__next_; __nd != nullptr &&
1371                                        __constrain_hash(__nd->__hash_, __bc) == __chash;
1372                                                            __nd = __nd->__next_)
1373             {
1374                 if (key_eq()(__nd->__value_, __x))
1375                     goto __done;
1376             }
1377         }
1378     }
1379     {
1380         __node_holder __h = __construct_node(__x, __hash);
1381         if (size()+1 > __bc * max_load_factor() || __bc == 0)
1382         {
1383             rehash(_VSTD::max<size_type>(2 * __bc + !__is_power2(__bc),
1384                            size_type(ceil(float(size() + 1) / max_load_factor()))));
1385             __bc = bucket_count();
1386             __chash = __constrain_hash(__hash, __bc);
1387         }
1388         // insert_after __bucket_list_[__chash], or __first_node if bucket is null
1389         __node_pointer __pn = __bucket_list_[__chash];
1390         if (__pn == nullptr)
1391         {
1392             __pn = static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()));
1393             __h->__next_ = __pn->__next_;
1394             __pn->__next_ = __h.get();
1395             // fix up __bucket_list_
1396             __bucket_list_[__chash] = __pn;
1397             if (__h->__next_ != nullptr)
1398                 __bucket_list_[__constrain_hash(__h->__next_->__hash_, __bc)] = __h.get();
1399         }
1400         else
1401         {
1402             __h->__next_ = __pn->__next_;
1403             __pn->__next_ = __h.get();
1404         }
1405         __nd = __h.release();
1406         // increment size
1407         ++size();
1408         __inserted = true;
1409     }
1410 __done:
1411     return pair<iterator, bool>(iterator(__nd), __inserted);
1412 }
1413
1414 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1415 #ifndef _LIBCPP_HAS_NO_VARIADICS
1416
1417 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1418 template <class... _Args>
1419 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
1420 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique(_Args&&... __args)
1421 {
1422     __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1423     pair<iterator, bool> __r = __node_insert_unique(__h.get());
1424     if (__r.second)
1425         __h.release();
1426     return __r;
1427 }
1428
1429 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1430 template <class... _Args>
1431 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1432 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_multi(_Args&&... __args)
1433 {
1434     __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1435     iterator __r = __node_insert_multi(__h.get());
1436     __h.release();
1437     return __r;
1438 }
1439
1440 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1441 template <class... _Args>
1442 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1443 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_hint_multi(
1444         const_iterator __p, _Args&&... __args)
1445 {
1446     __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1447     iterator __r = __node_insert_multi(__p, __h.get());
1448     __h.release();
1449     return __r;
1450 }
1451
1452 #endif  // _LIBCPP_HAS_NO_VARIADICS
1453
1454 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1455 template <class _Pp>
1456 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
1457 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique(_Pp&& __x)
1458 {
1459     __node_holder __h = __construct_node(_VSTD::forward<_Pp>(__x));
1460     pair<iterator, bool> __r = __node_insert_unique(__h.get());
1461     if (__r.second)
1462         __h.release();
1463     return __r;
1464 }
1465
1466 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1467
1468 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1469
1470 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1471 template <class _Pp>
1472 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1473 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(_Pp&& __x)
1474 {
1475     __node_holder __h = __construct_node(_VSTD::forward<_Pp>(__x));
1476     iterator __r = __node_insert_multi(__h.get());
1477     __h.release();
1478     return __r;
1479 }
1480
1481 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1482 template <class _Pp>
1483 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1484 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const_iterator __p,
1485                                                          _Pp&& __x)
1486 {
1487     __node_holder __h = __construct_node(_VSTD::forward<_Pp>(__x));
1488     iterator __r = __node_insert_multi(__p, __h.get());
1489     __h.release();
1490     return __r;
1491 }
1492
1493 #else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1494
1495 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1496 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1497 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const value_type& __x)
1498 {
1499     __node_holder __h = __construct_node(__x);
1500     iterator __r = __node_insert_multi(__h.get());
1501     __h.release();
1502     return __r;
1503 }
1504
1505 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1506 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1507 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const_iterator __p,
1508                                                          const value_type& __x)
1509 {
1510     __node_holder __h = __construct_node(__x);
1511     iterator __r = __node_insert_multi(__p, __h.get());
1512     __h.release();
1513     return __r;
1514 }
1515
1516 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1517
1518 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1519 void
1520 __hash_table<_Tp, _Hash, _Equal, _Alloc>::rehash(size_type __n)
1521 {
1522     if (__n == 1)
1523         __n = 2;
1524     else if (__n & (__n - 1))
1525         __n = __next_prime(__n);
1526     size_type __bc = bucket_count();
1527     if (__n > __bc)
1528         __rehash(__n);
1529     else if (__n < __bc)
1530     {
1531         __n = _VSTD::max<size_type>
1532               (
1533                   __n,
1534                   __is_power2(__bc) ? __next_pow2(size_t(ceil(float(size()) / max_load_factor()))) :
1535                                       __next_prime(size_t(ceil(float(size()) / max_load_factor())))
1536               );
1537         if (__n < __bc)
1538             __rehash(__n);
1539     }
1540 }
1541
1542 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1543 void
1544 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__rehash(size_type __nbc)
1545 {
1546     __pointer_allocator& __npa = __bucket_list_.get_deleter().__alloc();
1547     __bucket_list_.reset(__nbc > 0 ?
1548                       __pointer_alloc_traits::allocate(__npa, __nbc) : nullptr);
1549     __bucket_list_.get_deleter().size() = __nbc;
1550     if (__nbc > 0)
1551     {
1552         for (size_type __i = 0; __i < __nbc; ++__i)
1553             __bucket_list_[__i] = nullptr;
1554         __node_pointer __pp(static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())));
1555         __node_pointer __cp = __pp->__next_;
1556         if (__cp != nullptr)
1557         {
1558             size_type __chash = __constrain_hash(__cp->__hash_, __nbc);
1559             __bucket_list_[__chash] = __pp;
1560             size_type __phash = __chash;
1561             for (__pp = __cp, __cp = __cp->__next_; __cp != nullptr;
1562                                                            __cp = __pp->__next_)
1563             {
1564                 __chash = __constrain_hash(__cp->__hash_, __nbc);
1565                 if (__chash == __phash)
1566                     __pp = __cp;
1567                 else
1568                 {
1569                     if (__bucket_list_[__chash] == nullptr)
1570                     {
1571                         __bucket_list_[__chash] = __pp;
1572                         __pp = __cp;
1573                         __phash = __chash;
1574                     }
1575                     else
1576                     {
1577                         __node_pointer __np = __cp;
1578                         for (; __np->__next_ != nullptr &&
1579                                key_eq()(__cp->__value_, __np->__next_->__value_);
1580                                                            __np = __np->__next_)
1581                             ;
1582                         __pp->__next_ = __np->__next_;
1583                         __np->__next_ = __bucket_list_[__chash]->__next_;
1584                         __bucket_list_[__chash]->__next_ = __cp;
1585
1586                     }
1587                 }
1588             }
1589         }
1590     }
1591 }
1592
1593 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1594 template <class _Key>
1595 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1596 __hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k)
1597 {
1598     size_t __hash = hash_function()(__k);
1599     size_type __bc = bucket_count();
1600     if (__bc != 0)
1601     {
1602         size_t __chash = __constrain_hash(__hash, __bc);
1603         __node_pointer __nd = __bucket_list_[__chash];
1604         if (__nd != nullptr)
1605         {
1606             for (__nd = __nd->__next_; __nd != nullptr &&
1607                                        __constrain_hash(__nd->__hash_, __bc) == __chash;
1608                                                            __nd = __nd->__next_)
1609             {
1610                 if (key_eq()(__nd->__value_, __k))
1611                     return iterator(__nd);
1612             }
1613         }
1614     }
1615     return end();
1616 }
1617
1618 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1619 template <class _Key>
1620 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator
1621 __hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) const
1622 {
1623     size_t __hash = hash_function()(__k);
1624     size_type __bc = bucket_count();
1625     if (__bc != 0)
1626     {
1627         size_t __chash = __constrain_hash(__hash, __bc);
1628         __node_const_pointer __nd = __bucket_list_[__chash];
1629         if (__nd != nullptr)
1630         {
1631             for (__nd = __nd->__next_; __nd != nullptr &&
1632                                            __constrain_hash(__nd->__hash_, __bc) == __chash;
1633                                                            __nd = __nd->__next_)
1634             {
1635                 if (key_eq()(__nd->__value_, __k))
1636                     return const_iterator(__nd);
1637             }
1638         }
1639
1640     }
1641     return end();
1642 }
1643
1644 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1645 #ifndef _LIBCPP_HAS_NO_VARIADICS
1646
1647 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1648 template <class ..._Args>
1649 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
1650 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(_Args&& ...__args)
1651 {
1652     __node_allocator& __na = __node_alloc();
1653     __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1654     __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::forward<_Args>(__args)...);
1655     __h.get_deleter().__value_constructed = true;
1656     __h->__hash_ = hash_function()(__h->__value_);
1657     __h->__next_ = nullptr;
1658     return __h;
1659 }
1660
1661 #endif  // _LIBCPP_HAS_NO_VARIADICS
1662
1663 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1664 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
1665 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(value_type&& __v,
1666                                                            size_t __hash)
1667 {
1668     __node_allocator& __na = __node_alloc();
1669     __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1670     __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::move(__v));
1671     __h.get_deleter().__value_constructed = true;
1672     __h->__hash_ = __hash;
1673     __h->__next_ = nullptr;
1674     return _VSTD::move(__h);
1675 }
1676
1677 #else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1678
1679 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1680 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
1681 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(const value_type& __v)
1682 {
1683     __node_allocator& __na = __node_alloc();
1684     __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1685     __node_traits::construct(__na, _VSTD::addressof(__h->__value_), __v);
1686     __h.get_deleter().__value_constructed = true;
1687     __h->__hash_ = hash_function()(__h->__value_);
1688     __h->__next_ = nullptr;
1689     return _VSTD::move(__h);
1690 }
1691
1692 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1693
1694 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1695 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
1696 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(const value_type& __v,
1697                                                            size_t __hash)
1698 {
1699     __node_allocator& __na = __node_alloc();
1700     __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1701     __node_traits::construct(__na, _VSTD::addressof(__h->__value_), __v);
1702     __h.get_deleter().__value_constructed = true;
1703     __h->__hash_ = __hash;
1704     __h->__next_ = nullptr;
1705     return _VSTD::move(__h);
1706 }
1707
1708 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1709 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1710 __hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __p)
1711 {
1712     __node_pointer __np = __p.__node_;
1713     iterator __r(__np);
1714     ++__r;
1715     remove(__p);
1716     return __r;
1717 }
1718
1719 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1720 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1721 __hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __first,
1722                                                 const_iterator __last)
1723 {
1724     for (const_iterator __p = __first; __first != __last; __p = __first)
1725     {
1726         ++__first;
1727         erase(__p);
1728     }
1729     __node_pointer __np = __last.__node_;
1730     return iterator (__np);
1731 }
1732
1733 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1734 template <class _Key>
1735 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
1736 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_unique(const _Key& __k)
1737 {
1738     iterator __i = find(__k);
1739     if (__i == end())
1740         return 0;
1741     erase(__i);
1742     return 1;
1743 }
1744
1745 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1746 template <class _Key>
1747 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
1748 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_multi(const _Key& __k)
1749 {
1750     size_type __r = 0;
1751     iterator __i = find(__k);
1752     if (__i != end())
1753     {
1754         iterator __e = end();
1755         do
1756         {
1757             erase(__i++);
1758             ++__r;
1759         } while (__i != __e && key_eq()(*__i, __k));
1760     }
1761     return __r;
1762 }
1763
1764 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1765 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
1766 __hash_table<_Tp, _Hash, _Equal, _Alloc>::remove(const_iterator __p) _NOEXCEPT
1767 {
1768     // current node
1769     __node_pointer __cn = __p.__node_;
1770     size_type __bc = bucket_count();
1771     size_t __chash = __constrain_hash(__cn->__hash_, __bc);
1772     // find previous node
1773     __node_pointer __pn = __bucket_list_[__chash];
1774     for (; __pn->__next_ != __cn; __pn = __pn->__next_)
1775         ;
1776     // Fix up __bucket_list_
1777         // if __pn is not in same bucket (before begin is not in same bucket) &&
1778         //    if __cn->__next_ is not in same bucket (nullptr is not in same bucket)
1779     if (__pn == static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()))
1780                             || __constrain_hash(__pn->__hash_, __bc) != __chash)
1781     {
1782         if (__cn->__next_ == nullptr || __constrain_hash(__cn->__next_->__hash_, __bc) != __chash)
1783             __bucket_list_[__chash] = nullptr;
1784     }
1785         // if __cn->__next_ is not in same bucket (nullptr is in same bucket)
1786     if (__cn->__next_ != nullptr)
1787     {
1788         size_t __nhash = __constrain_hash(__cn->__next_->__hash_, __bc);
1789         if (__nhash != __chash)
1790             __bucket_list_[__nhash] = __pn;
1791     }
1792     // remove __cn
1793     __pn->__next_ = __cn->__next_;
1794     __cn->__next_ = nullptr;
1795     --size();
1796     return __node_holder(__cn, _Dp(__node_alloc(), true));
1797 }
1798
1799 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1800 template <class _Key>
1801 inline _LIBCPP_INLINE_VISIBILITY
1802 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
1803 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_unique(const _Key& __k) const
1804 {
1805     return static_cast<size_type>(find(__k) != end());
1806 }
1807
1808 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1809 template <class _Key>
1810 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
1811 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_multi(const _Key& __k) const
1812 {
1813     size_type __r = 0;
1814     const_iterator __i = find(__k);
1815     if (__i != end())
1816     {
1817         const_iterator __e = end();
1818         do
1819         {
1820             ++__i;
1821             ++__r;
1822         } while (__i != __e && key_eq()(*__i, __k));
1823     }
1824     return __r;
1825 }
1826
1827 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1828 template <class _Key>
1829 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator,
1830      typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator>
1831 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique(
1832         const _Key& __k)
1833 {
1834     iterator __i = find(__k);
1835     iterator __j = __i;
1836     if (__i != end())
1837         ++__j;
1838     return pair<iterator, iterator>(__i, __j);
1839 }
1840
1841 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1842 template <class _Key>
1843 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator,
1844      typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator>
1845 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique(
1846         const _Key& __k) const
1847 {
1848     const_iterator __i = find(__k);
1849     const_iterator __j = __i;
1850     if (__i != end())
1851         ++__j;
1852     return pair<const_iterator, const_iterator>(__i, __j);
1853 }
1854
1855 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1856 template <class _Key>
1857 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator,
1858      typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator>
1859 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi(
1860         const _Key& __k)
1861 {
1862     iterator __i = find(__k);
1863     iterator __j = __i;
1864     if (__i != end())
1865     {
1866         iterator __e = end();
1867         do
1868         {
1869             ++__j;
1870         } while (__j != __e && key_eq()(*__j, __k));
1871     }
1872     return pair<iterator, iterator>(__i, __j);
1873 }
1874
1875 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1876 template <class _Key>
1877 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator,
1878      typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator>
1879 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi(
1880         const _Key& __k) const
1881 {
1882     const_iterator __i = find(__k);
1883     const_iterator __j = __i;
1884     if (__i != end())
1885     {
1886         const_iterator __e = end();
1887         do
1888         {
1889             ++__j;
1890         } while (__j != __e && key_eq()(*__j, __k));
1891     }
1892     return pair<const_iterator, const_iterator>(__i, __j);
1893 }
1894
1895 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1896 void
1897 __hash_table<_Tp, _Hash, _Equal, _Alloc>::swap(__hash_table& __u)
1898     _NOEXCEPT_(
1899         (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value ||
1900          __is_nothrow_swappable<__pointer_allocator>::value) &&
1901         (!__node_traits::propagate_on_container_swap::value ||
1902          __is_nothrow_swappable<__node_allocator>::value) &&
1903         __is_nothrow_swappable<hasher>::value &&
1904         __is_nothrow_swappable<key_equal>::value)
1905 {
1906     {
1907     __node_pointer_pointer __npp = __bucket_list_.release();
1908     __bucket_list_.reset(__u.__bucket_list_.release());
1909     __u.__bucket_list_.reset(__npp);
1910     }
1911     _VSTD::swap(__bucket_list_.get_deleter().size(), __u.__bucket_list_.get_deleter().size());
1912     __swap_alloc(__bucket_list_.get_deleter().__alloc(),
1913              __u.__bucket_list_.get_deleter().__alloc());
1914     __swap_alloc(__node_alloc(), __u.__node_alloc());
1915     _VSTD::swap(__p1_.first().__next_, __u.__p1_.first().__next_);
1916     __p2_.swap(__u.__p2_);
1917     __p3_.swap(__u.__p3_);
1918     if (size() > 0)
1919         __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] =
1920             static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()));
1921     if (__u.size() > 0)
1922         __u.__bucket_list_[__constrain_hash(__u.__p1_.first().__next_->__hash_, __u.bucket_count())] =
1923             static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__u.__p1_.first()));
1924 }
1925
1926 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1927 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
1928 __hash_table<_Tp, _Hash, _Equal, _Alloc>::bucket_size(size_type __n) const
1929 {
1930     __node_const_pointer __np = __bucket_list_[__n];
1931     size_type __bc = bucket_count();
1932     size_type __r = 0;
1933     if (__np != nullptr)
1934     {
1935         for (__np = __np->__next_; __np != nullptr &&
1936                                    __constrain_hash(__np->__hash_, __bc) == __n;
1937                                                     __np = __np->__next_, ++__r)
1938             ;
1939     }
1940     return __r;
1941 }
1942
1943 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1944 inline _LIBCPP_INLINE_VISIBILITY
1945 void
1946 swap(__hash_table<_Tp, _Hash, _Equal, _Alloc>& __x,
1947      __hash_table<_Tp, _Hash, _Equal, _Alloc>& __y)
1948     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1949 {
1950     __x.swap(__y);
1951 }
1952
1953 _LIBCPP_END_NAMESPACE_STD
1954
1955 #endif  // _LIBCPP__HASH_TABLE