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