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