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