1// -*- C++ -*-
2//===-------------------------- unordered_set -----------------------------===//
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_UNORDERED_SET
12#define _LIBCPP_UNORDERED_SET
13
14/*
15
16    unordered_set synopsis
17
18#include <initializer_list>
19
20namespace std
21{
22
23template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,
24          class Alloc = allocator<Value>>
25class unordered_set
26{
27public:
28    // types
29    typedef Value                                                      key_type;
30    typedef key_type                                                   value_type;
31    typedef Hash                                                       hasher;
32    typedef Pred                                                       key_equal;
33    typedef Alloc                                                      allocator_type;
34    typedef value_type&                                                reference;
35    typedef const value_type&                                          const_reference;
36    typedef typename allocator_traits<allocator_type>::pointer         pointer;
37    typedef typename allocator_traits<allocator_type>::const_pointer   const_pointer;
38    typedef typename allocator_traits<allocator_type>::size_type       size_type;
39    typedef typename allocator_traits<allocator_type>::difference_type difference_type;
40
41    typedef /unspecified/ iterator;
42    typedef /unspecified/ const_iterator;
43    typedef /unspecified/ local_iterator;
44    typedef /unspecified/ const_local_iterator;
45
46    typedef unspecified node_type unspecified;                            // C++17
47    typedef INSERT_RETURN_TYPE<iterator, node_type> insert_return_type;   // C++17
48
49    unordered_set()
50        noexcept(
51            is_nothrow_default_constructible<hasher>::value &&
52            is_nothrow_default_constructible<key_equal>::value &&
53            is_nothrow_default_constructible<allocator_type>::value);
54    explicit unordered_set(size_type n, const hasher& hf = hasher(),
55                           const key_equal& eql = key_equal(),
56                           const allocator_type& a = allocator_type());
57    template <class InputIterator>
58        unordered_set(InputIterator f, InputIterator l,
59                      size_type n = 0, const hasher& hf = hasher(),
60                      const key_equal& eql = key_equal(),
61                      const allocator_type& a = allocator_type());
62    explicit unordered_set(const allocator_type&);
63    unordered_set(const unordered_set&);
64    unordered_set(const unordered_set&, const Allocator&);
65    unordered_set(unordered_set&&)
66        noexcept(
67            is_nothrow_move_constructible<hasher>::value &&
68            is_nothrow_move_constructible<key_equal>::value &&
69            is_nothrow_move_constructible<allocator_type>::value);
70    unordered_set(unordered_set&&, const Allocator&);
71    unordered_set(initializer_list<value_type>, size_type n = 0,
72                  const hasher& hf = hasher(), const key_equal& eql = key_equal(),
73                  const allocator_type& a = allocator_type());
74    unordered_set(size_type n, const allocator_type& a); // C++14
75    unordered_set(size_type n, const hasher& hf, const allocator_type& a); // C++14
76    template <class InputIterator>
77      unordered_set(InputIterator f, InputIterator l, size_type n, const allocator_type& a); // C++14
78    template <class InputIterator>
79      unordered_set(InputIterator f, InputIterator l, size_type n,
80                    const hasher& hf,  const allocator_type& a); // C++14
81    unordered_set(initializer_list<value_type> il, size_type n, const allocator_type& a); // C++14
82    unordered_set(initializer_list<value_type> il, size_type n,
83                  const hasher& hf,  const allocator_type& a); // C++14
84    ~unordered_set();
85    unordered_set& operator=(const unordered_set&);
86    unordered_set& operator=(unordered_set&&)
87        noexcept(
88            allocator_type::propagate_on_container_move_assignment::value &&
89            is_nothrow_move_assignable<allocator_type>::value &&
90            is_nothrow_move_assignable<hasher>::value &&
91            is_nothrow_move_assignable<key_equal>::value);
92    unordered_set& operator=(initializer_list<value_type>);
93
94    allocator_type get_allocator() const noexcept;
95
96    bool      empty() const noexcept;
97    size_type size() const noexcept;
98    size_type max_size() const noexcept;
99
100    iterator       begin() noexcept;
101    iterator       end() noexcept;
102    const_iterator begin()  const noexcept;
103    const_iterator end()    const noexcept;
104    const_iterator cbegin() const noexcept;
105    const_iterator cend()   const noexcept;
106
107    template <class... Args>
108        pair<iterator, bool> emplace(Args&&... args);
109    template <class... Args>
110        iterator emplace_hint(const_iterator position, Args&&... args);
111    pair<iterator, bool> insert(const value_type& obj);
112    pair<iterator, bool> insert(value_type&& obj);
113    iterator insert(const_iterator hint, const value_type& obj);
114    iterator insert(const_iterator hint, value_type&& obj);
115    template <class InputIterator>
116        void insert(InputIterator first, InputIterator last);
117    void insert(initializer_list<value_type>);
118
119    node_type extract(const_iterator position);                       // C++17
120    node_type extract(const key_type& x);                             // C++17
121    insert_return_type insert(node_type&& nh);                        // C++17
122    iterator           insert(const_iterator hint, node_type&& nh);   // C++17
123
124    iterator erase(const_iterator position);
125    iterator erase(iterator position);  // C++14
126    size_type erase(const key_type& k);
127    iterator erase(const_iterator first, const_iterator last);
128    void clear() noexcept;
129
130    void swap(unordered_set&)
131       noexcept(allocator_traits<Allocator>::is_always_equal::value &&
132                 noexcept(swap(declval<hasher&>(), declval<hasher&>())) &&
133                 noexcept(swap(declval<key_equal&>(), declval<key_equal&>()))); // C++17
134
135    hasher hash_function() const;
136    key_equal key_eq() const;
137
138    iterator       find(const key_type& k);
139    const_iterator find(const key_type& k) const;
140    size_type count(const key_type& k) const;
141    pair<iterator, iterator>             equal_range(const key_type& k);
142    pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
143
144    size_type bucket_count() const noexcept;
145    size_type max_bucket_count() const noexcept;
146
147    size_type bucket_size(size_type n) const;
148    size_type bucket(const key_type& k) const;
149
150    local_iterator       begin(size_type n);
151    local_iterator       end(size_type n);
152    const_local_iterator begin(size_type n) const;
153    const_local_iterator end(size_type n) const;
154    const_local_iterator cbegin(size_type n) const;
155    const_local_iterator cend(size_type n) const;
156
157    float load_factor() const noexcept;
158    float max_load_factor() const noexcept;
159    void max_load_factor(float z);
160    void rehash(size_type n);
161    void reserve(size_type n);
162};
163
164template <class Value, class Hash, class Pred, class Alloc>
165    void swap(unordered_set<Value, Hash, Pred, Alloc>& x,
166              unordered_set<Value, Hash, Pred, Alloc>& y)
167              noexcept(noexcept(x.swap(y)));
168
169template <class Value, class Hash, class Pred, class Alloc>
170    bool
171    operator==(const unordered_set<Value, Hash, Pred, Alloc>& x,
172               const unordered_set<Value, Hash, Pred, Alloc>& y);
173
174template <class Value, class Hash, class Pred, class Alloc>
175    bool
176    operator!=(const unordered_set<Value, Hash, Pred, Alloc>& x,
177               const unordered_set<Value, Hash, Pred, Alloc>& y);
178
179template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,
180          class Alloc = allocator<Value>>
181class unordered_multiset
182{
183public:
184    // types
185    typedef Value                                                      key_type;
186    typedef key_type                                                   value_type;
187    typedef Hash                                                       hasher;
188    typedef Pred                                                       key_equal;
189    typedef Alloc                                                      allocator_type;
190    typedef value_type&                                                reference;
191    typedef const value_type&                                          const_reference;
192    typedef typename allocator_traits<allocator_type>::pointer         pointer;
193    typedef typename allocator_traits<allocator_type>::const_pointer   const_pointer;
194    typedef typename allocator_traits<allocator_type>::size_type       size_type;
195    typedef typename allocator_traits<allocator_type>::difference_type difference_type;
196
197    typedef /unspecified/ iterator;
198    typedef /unspecified/ const_iterator;
199    typedef /unspecified/ local_iterator;
200    typedef /unspecified/ const_local_iterator;
201
202    typedef unspecified node_type unspecified;   // C++17
203
204    unordered_multiset()
205        noexcept(
206            is_nothrow_default_constructible<hasher>::value &&
207            is_nothrow_default_constructible<key_equal>::value &&
208            is_nothrow_default_constructible<allocator_type>::value);
209    explicit unordered_multiset(size_type n, const hasher& hf = hasher(),
210                           const key_equal& eql = key_equal(),
211                           const allocator_type& a = allocator_type());
212    template <class InputIterator>
213        unordered_multiset(InputIterator f, InputIterator l,
214                      size_type n = 0, const hasher& hf = hasher(),
215                      const key_equal& eql = key_equal(),
216                      const allocator_type& a = allocator_type());
217    explicit unordered_multiset(const allocator_type&);
218    unordered_multiset(const unordered_multiset&);
219    unordered_multiset(const unordered_multiset&, const Allocator&);
220    unordered_multiset(unordered_multiset&&)
221        noexcept(
222            is_nothrow_move_constructible<hasher>::value &&
223            is_nothrow_move_constructible<key_equal>::value &&
224            is_nothrow_move_constructible<allocator_type>::value);
225    unordered_multiset(unordered_multiset&&, const Allocator&);
226    unordered_multiset(initializer_list<value_type>, size_type n = /see below/,
227                  const hasher& hf = hasher(), const key_equal& eql = key_equal(),
228                  const allocator_type& a = allocator_type());
229    unordered_multiset(size_type n, const allocator_type& a); // C++14
230    unordered_multiset(size_type n, const hasher& hf, const allocator_type& a); // C++14
231    template <class InputIterator>
232      unordered_multiset(InputIterator f, InputIterator l, size_type n, const allocator_type& a); // C++14
233    template <class InputIterator>
234      unordered_multiset(InputIterator f, InputIterator l, size_type n,
235                         const hasher& hf, const allocator_type& a); // C++14
236    unordered_multiset(initializer_list<value_type> il, size_type n, const allocator_type& a); // C++14
237    unordered_multiset(initializer_list<value_type> il, size_type n,
238                       const hasher& hf,  const allocator_type& a); // C++14
239    ~unordered_multiset();
240    unordered_multiset& operator=(const unordered_multiset&);
241    unordered_multiset& operator=(unordered_multiset&&)
242        noexcept(
243            allocator_type::propagate_on_container_move_assignment::value &&
244            is_nothrow_move_assignable<allocator_type>::value &&
245            is_nothrow_move_assignable<hasher>::value &&
246            is_nothrow_move_assignable<key_equal>::value);
247    unordered_multiset& operator=(initializer_list<value_type>);
248
249    allocator_type get_allocator() const noexcept;
250
251    bool      empty() const noexcept;
252    size_type size() const noexcept;
253    size_type max_size() const noexcept;
254
255    iterator       begin() noexcept;
256    iterator       end() noexcept;
257    const_iterator begin()  const noexcept;
258    const_iterator end()    const noexcept;
259    const_iterator cbegin() const noexcept;
260    const_iterator cend()   const noexcept;
261
262    template <class... Args>
263        iterator emplace(Args&&... args);
264    template <class... Args>
265        iterator emplace_hint(const_iterator position, Args&&... args);
266    iterator insert(const value_type& obj);
267    iterator insert(value_type&& obj);
268    iterator insert(const_iterator hint, const value_type& obj);
269    iterator insert(const_iterator hint, value_type&& obj);
270    template <class InputIterator>
271        void insert(InputIterator first, InputIterator last);
272    void insert(initializer_list<value_type>);
273
274    node_type extract(const_iterator position);             // C++17
275    node_type extract(const key_type& x);                   // C++17
276    iterator insert(node_type&& nh);                        // C++17
277    iterator insert(const_iterator hint, node_type&& nh);   // C++17
278
279    iterator erase(const_iterator position);
280    iterator erase(iterator position);  // C++14
281    size_type erase(const key_type& k);
282    iterator erase(const_iterator first, const_iterator last);
283    void clear() noexcept;
284
285    void swap(unordered_multiset&)
286       noexcept(allocator_traits<Allocator>::is_always_equal::value &&
287                 noexcept(swap(declval<hasher&>(), declval<hasher&>())) &&
288                 noexcept(swap(declval<key_equal&>(), declval<key_equal&>()))); // C++17
289
290    hasher hash_function() const;
291    key_equal key_eq() const;
292
293    iterator       find(const key_type& k);
294    const_iterator find(const key_type& k) const;
295    size_type count(const key_type& k) const;
296    pair<iterator, iterator>             equal_range(const key_type& k);
297    pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
298
299    size_type bucket_count() const noexcept;
300    size_type max_bucket_count() const noexcept;
301
302    size_type bucket_size(size_type n) const;
303    size_type bucket(const key_type& k) const;
304
305    local_iterator       begin(size_type n);
306    local_iterator       end(size_type n);
307    const_local_iterator begin(size_type n) const;
308    const_local_iterator end(size_type n) const;
309    const_local_iterator cbegin(size_type n) const;
310    const_local_iterator cend(size_type n) const;
311
312    float load_factor() const noexcept;
313    float max_load_factor() const noexcept;
314    void max_load_factor(float z);
315    void rehash(size_type n);
316    void reserve(size_type n);
317};
318
319template <class Value, class Hash, class Pred, class Alloc>
320    void swap(unordered_multiset<Value, Hash, Pred, Alloc>& x,
321              unordered_multiset<Value, Hash, Pred, Alloc>& y)
322              noexcept(noexcept(x.swap(y)));
323
324template <class Value, class Hash, class Pred, class Alloc>
325    bool
326    operator==(const unordered_multiset<Value, Hash, Pred, Alloc>& x,
327               const unordered_multiset<Value, Hash, Pred, Alloc>& y);
328
329template <class Value, class Hash, class Pred, class Alloc>
330    bool
331    operator!=(const unordered_multiset<Value, Hash, Pred, Alloc>& x,
332               const unordered_multiset<Value, Hash, Pred, Alloc>& y);
333}  // std
334
335*/
336
337#include <__config>
338#include <__hash_table>
339#include <__node_handle>
340#include <functional>
341
342#include <__debug>
343
344#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
345#pragma GCC system_header
346#endif
347
348_LIBCPP_BEGIN_NAMESPACE_STD
349
350template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>,
351          class _Alloc = allocator<_Value> >
352class _LIBCPP_TEMPLATE_VIS unordered_set
353{
354public:
355    // types
356    typedef _Value                                                     key_type;
357    typedef key_type                                                   value_type;
358    typedef _Hash                                                      hasher;
359    typedef _Pred                                                      key_equal;
360    typedef _Alloc                                                     allocator_type;
361    typedef value_type&                                                reference;
362    typedef const value_type&                                          const_reference;
363    static_assert((is_same<value_type, typename allocator_type::value_type>::value),
364                  "Invalid allocator::value_type");
365
366private:
367    typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
368
369    __table __table_;
370
371public:
372    typedef typename __table::pointer         pointer;
373    typedef typename __table::const_pointer   const_pointer;
374    typedef typename __table::size_type       size_type;
375    typedef typename __table::difference_type difference_type;
376
377    typedef typename __table::const_iterator       iterator;
378    typedef typename __table::const_iterator       const_iterator;
379    typedef typename __table::const_local_iterator local_iterator;
380    typedef typename __table::const_local_iterator const_local_iterator;
381
382#if _LIBCPP_STD_VER > 14
383    typedef __set_node_handle<typename __table::__node, allocator_type> node_type;
384    typedef __insert_return_type<iterator, node_type> insert_return_type;
385#endif
386
387    _LIBCPP_INLINE_VISIBILITY
388    unordered_set()
389        _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
390        {
391#if _LIBCPP_DEBUG_LEVEL >= 2
392            __get_db()->__insert_c(this);
393#endif
394        }
395    explicit unordered_set(size_type __n, const hasher& __hf = hasher(),
396                           const key_equal& __eql = key_equal());
397#if _LIBCPP_STD_VER > 11
398    inline _LIBCPP_INLINE_VISIBILITY
399    unordered_set(size_type __n, const allocator_type& __a)
400        : unordered_set(__n, hasher(), key_equal(), __a) {}
401    inline _LIBCPP_INLINE_VISIBILITY
402    unordered_set(size_type __n, const hasher& __hf, const allocator_type& __a)
403        : unordered_set(__n, __hf, key_equal(), __a) {}
404#endif
405    unordered_set(size_type __n, const hasher& __hf, const key_equal& __eql,
406                  const allocator_type& __a);
407    template <class _InputIterator>
408        unordered_set(_InputIterator __first, _InputIterator __last);
409    template <class _InputIterator>
410        unordered_set(_InputIterator __first, _InputIterator __last,
411                      size_type __n, const hasher& __hf = hasher(),
412                      const key_equal& __eql = key_equal());
413    template <class _InputIterator>
414        unordered_set(_InputIterator __first, _InputIterator __last,
415                      size_type __n, const hasher& __hf, const key_equal& __eql,
416                      const allocator_type& __a);
417#if _LIBCPP_STD_VER > 11
418    template <class _InputIterator>
419    inline _LIBCPP_INLINE_VISIBILITY
420        unordered_set(_InputIterator __first, _InputIterator __last,
421                    size_type __n, const allocator_type& __a)
422            : unordered_set(__first, __last, __n, hasher(), key_equal(), __a) {}
423    template <class _InputIterator>
424        unordered_set(_InputIterator __first, _InputIterator __last,
425                      size_type __n, const hasher& __hf, const allocator_type& __a)
426            : unordered_set(__first, __last, __n, __hf, key_equal(), __a) {}
427#endif
428    _LIBCPP_INLINE_VISIBILITY
429    explicit unordered_set(const allocator_type& __a);
430    unordered_set(const unordered_set& __u);
431    unordered_set(const unordered_set& __u, const allocator_type& __a);
432#ifndef _LIBCPP_CXX03_LANG
433    _LIBCPP_INLINE_VISIBILITY
434    unordered_set(unordered_set&& __u)
435        _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
436    unordered_set(unordered_set&& __u, const allocator_type& __a);
437    unordered_set(initializer_list<value_type> __il);
438    unordered_set(initializer_list<value_type> __il, size_type __n,
439                  const hasher& __hf = hasher(),
440                  const key_equal& __eql = key_equal());
441    unordered_set(initializer_list<value_type> __il, size_type __n,
442                  const hasher& __hf, const key_equal& __eql,
443                  const allocator_type& __a);
444#if _LIBCPP_STD_VER > 11
445    inline _LIBCPP_INLINE_VISIBILITY
446    unordered_set(initializer_list<value_type> __il, size_type __n,
447                                                      const allocator_type& __a)
448        : unordered_set(__il, __n, hasher(), key_equal(), __a) {}
449    inline _LIBCPP_INLINE_VISIBILITY
450    unordered_set(initializer_list<value_type> __il, size_type __n,
451                                  const hasher& __hf, const allocator_type& __a)
452        : unordered_set(__il, __n, __hf, key_equal(), __a) {}
453#endif
454#endif  // _LIBCPP_CXX03_LANG
455    // ~unordered_set() = default;
456    _LIBCPP_INLINE_VISIBILITY
457    unordered_set& operator=(const unordered_set& __u)
458    {
459        __table_ = __u.__table_;
460        return *this;
461    }
462#ifndef _LIBCPP_CXX03_LANG
463    _LIBCPP_INLINE_VISIBILITY
464    unordered_set& operator=(unordered_set&& __u)
465        _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
466    _LIBCPP_INLINE_VISIBILITY
467    unordered_set& operator=(initializer_list<value_type> __il);
468#endif  // _LIBCPP_CXX03_LANG
469
470    _LIBCPP_INLINE_VISIBILITY
471    allocator_type get_allocator() const _NOEXCEPT
472        {return allocator_type(__table_.__node_alloc());}
473
474    _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
475    bool      empty() const _NOEXCEPT {return __table_.size() == 0;}
476    _LIBCPP_INLINE_VISIBILITY
477    size_type size() const _NOEXCEPT  {return __table_.size();}
478    _LIBCPP_INLINE_VISIBILITY
479    size_type max_size() const _NOEXCEPT {return __table_.max_size();}
480
481    _LIBCPP_INLINE_VISIBILITY
482    iterator       begin() _NOEXCEPT        {return __table_.begin();}
483    _LIBCPP_INLINE_VISIBILITY
484    iterator       end() _NOEXCEPT          {return __table_.end();}
485    _LIBCPP_INLINE_VISIBILITY
486    const_iterator begin()  const _NOEXCEPT {return __table_.begin();}
487    _LIBCPP_INLINE_VISIBILITY
488    const_iterator end()    const _NOEXCEPT {return __table_.end();}
489    _LIBCPP_INLINE_VISIBILITY
490    const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
491    _LIBCPP_INLINE_VISIBILITY
492    const_iterator cend()   const _NOEXCEPT {return __table_.end();}
493
494#ifndef _LIBCPP_CXX03_LANG
495    template <class... _Args>
496        _LIBCPP_INLINE_VISIBILITY
497        pair<iterator, bool> emplace(_Args&&... __args)
498            {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...);}
499    template <class... _Args>
500        _LIBCPP_INLINE_VISIBILITY
501#if _LIBCPP_DEBUG_LEVEL >= 2
502        iterator emplace_hint(const_iterator __p, _Args&&... __args)
503        {
504            _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
505                "unordered_set::emplace_hint(const_iterator, args...) called with an iterator not"
506                " referring to this unordered_set");
507            return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first;
508        }
509#else
510        iterator emplace_hint(const_iterator, _Args&&... __args)
511            {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first;}
512#endif
513
514    _LIBCPP_INLINE_VISIBILITY
515    pair<iterator, bool> insert(value_type&& __x)
516        {return __table_.__insert_unique(_VSTD::move(__x));}
517    _LIBCPP_INLINE_VISIBILITY
518#if _LIBCPP_DEBUG_LEVEL >= 2
519    iterator insert(const_iterator __p, value_type&& __x)
520        {
521            _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
522                "unordered_set::insert(const_iterator, value_type&&) called with an iterator not"
523                " referring to this unordered_set");
524            return insert(_VSTD::move(__x)).first;
525        }
526#else
527    iterator insert(const_iterator, value_type&& __x)
528        {return insert(_VSTD::move(__x)).first;}
529#endif
530    _LIBCPP_INLINE_VISIBILITY
531    void insert(initializer_list<value_type> __il)
532        {insert(__il.begin(), __il.end());}
533#endif  // _LIBCPP_CXX03_LANG
534    _LIBCPP_INLINE_VISIBILITY
535    pair<iterator, bool> insert(const value_type& __x)
536        {return __table_.__insert_unique(__x);}
537
538    _LIBCPP_INLINE_VISIBILITY
539#if _LIBCPP_DEBUG_LEVEL >= 2
540    iterator insert(const_iterator __p, const value_type& __x)
541        {
542            _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
543                "unordered_set::insert(const_iterator, const value_type&) called with an iterator not"
544                " referring to this unordered_set");
545            return insert(__x).first;
546        }
547#else
548    iterator insert(const_iterator, const value_type& __x)
549        {return insert(__x).first;}
550#endif
551    template <class _InputIterator>
552        _LIBCPP_INLINE_VISIBILITY
553        void insert(_InputIterator __first, _InputIterator __last);
554
555    _LIBCPP_INLINE_VISIBILITY
556    iterator erase(const_iterator __p) {return __table_.erase(__p);}
557    _LIBCPP_INLINE_VISIBILITY
558    size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
559    _LIBCPP_INLINE_VISIBILITY
560    iterator erase(const_iterator __first, const_iterator __last)
561        {return __table_.erase(__first, __last);}
562    _LIBCPP_INLINE_VISIBILITY
563    void clear() _NOEXCEPT {__table_.clear();}
564
565#if _LIBCPP_STD_VER > 14
566    _LIBCPP_INLINE_VISIBILITY
567    insert_return_type insert(node_type&& __nh)
568    {
569        _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
570            "node_type with incompatible allocator passed to unordered_set::insert()");
571        return __table_.template __node_handle_insert_unique<
572            node_type, insert_return_type>(_VSTD::move(__nh));
573    }
574    _LIBCPP_INLINE_VISIBILITY
575    iterator insert(const_iterator __h, node_type&& __nh)
576    {
577        _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
578            "node_type with incompatible allocator passed to unordered_set::insert()");
579        return __table_.template __node_handle_insert_unique<node_type>(
580            __h, _VSTD::move(__nh));
581    }
582    _LIBCPP_INLINE_VISIBILITY
583    node_type extract(key_type const& __key)
584    {
585        return __table_.template __node_handle_extract<node_type>(__key);
586    }
587    _LIBCPP_INLINE_VISIBILITY
588    node_type extract(const_iterator __it)
589    {
590        return __table_.template __node_handle_extract<node_type>(__it);
591    }
592#endif
593
594    _LIBCPP_INLINE_VISIBILITY
595    void swap(unordered_set& __u)
596        _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
597        {__table_.swap(__u.__table_);}
598
599    _LIBCPP_INLINE_VISIBILITY
600    hasher hash_function() const {return __table_.hash_function();}
601    _LIBCPP_INLINE_VISIBILITY
602    key_equal key_eq() const {return __table_.key_eq();}
603
604    _LIBCPP_INLINE_VISIBILITY
605    iterator       find(const key_type& __k)       {return __table_.find(__k);}
606    _LIBCPP_INLINE_VISIBILITY
607    const_iterator find(const key_type& __k) const {return __table_.find(__k);}
608    _LIBCPP_INLINE_VISIBILITY
609    size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
610    _LIBCPP_INLINE_VISIBILITY
611    pair<iterator, iterator>             equal_range(const key_type& __k)
612        {return __table_.__equal_range_unique(__k);}
613    _LIBCPP_INLINE_VISIBILITY
614    pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
615        {return __table_.__equal_range_unique(__k);}
616
617    _LIBCPP_INLINE_VISIBILITY
618    size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
619    _LIBCPP_INLINE_VISIBILITY
620    size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
621
622    _LIBCPP_INLINE_VISIBILITY
623    size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);}
624    _LIBCPP_INLINE_VISIBILITY
625    size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
626
627    _LIBCPP_INLINE_VISIBILITY
628    local_iterator       begin(size_type __n)        {return __table_.begin(__n);}
629    _LIBCPP_INLINE_VISIBILITY
630    local_iterator       end(size_type __n)          {return __table_.end(__n);}
631    _LIBCPP_INLINE_VISIBILITY
632    const_local_iterator begin(size_type __n) const  {return __table_.cbegin(__n);}
633    _LIBCPP_INLINE_VISIBILITY
634    const_local_iterator end(size_type __n) const    {return __table_.cend(__n);}
635    _LIBCPP_INLINE_VISIBILITY
636    const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
637    _LIBCPP_INLINE_VISIBILITY
638    const_local_iterator cend(size_type __n) const   {return __table_.cend(__n);}
639
640    _LIBCPP_INLINE_VISIBILITY
641    float load_factor() const _NOEXCEPT {return __table_.load_factor();}
642    _LIBCPP_INLINE_VISIBILITY
643    float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
644    _LIBCPP_INLINE_VISIBILITY
645    void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
646    _LIBCPP_INLINE_VISIBILITY
647    void rehash(size_type __n) {__table_.rehash(__n);}
648    _LIBCPP_INLINE_VISIBILITY
649    void reserve(size_type __n) {__table_.reserve(__n);}
650
651#if _LIBCPP_DEBUG_LEVEL >= 2
652
653    bool __dereferenceable(const const_iterator* __i) const
654        {return __table_.__dereferenceable(__i);}
655    bool __decrementable(const const_iterator* __i) const
656        {return __table_.__decrementable(__i);}
657    bool __addable(const const_iterator* __i, ptrdiff_t __n) const
658        {return __table_.__addable(__i, __n);}
659    bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
660        {return __table_.__addable(__i, __n);}
661
662#endif  // _LIBCPP_DEBUG_LEVEL >= 2
663
664};
665
666template <class _Value, class _Hash, class _Pred, class _Alloc>
667unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n,
668        const hasher& __hf, const key_equal& __eql)
669    : __table_(__hf, __eql)
670{
671#if _LIBCPP_DEBUG_LEVEL >= 2
672    __get_db()->__insert_c(this);
673#endif
674    __table_.rehash(__n);
675}
676
677template <class _Value, class _Hash, class _Pred, class _Alloc>
678unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n,
679        const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
680    : __table_(__hf, __eql, __a)
681{
682#if _LIBCPP_DEBUG_LEVEL >= 2
683    __get_db()->__insert_c(this);
684#endif
685    __table_.rehash(__n);
686}
687
688template <class _Value, class _Hash, class _Pred, class _Alloc>
689template <class _InputIterator>
690unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
691        _InputIterator __first, _InputIterator __last)
692{
693#if _LIBCPP_DEBUG_LEVEL >= 2
694    __get_db()->__insert_c(this);
695#endif
696    insert(__first, __last);
697}
698
699template <class _Value, class _Hash, class _Pred, class _Alloc>
700template <class _InputIterator>
701unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
702        _InputIterator __first, _InputIterator __last, size_type __n,
703        const hasher& __hf, const key_equal& __eql)
704    : __table_(__hf, __eql)
705{
706#if _LIBCPP_DEBUG_LEVEL >= 2
707    __get_db()->__insert_c(this);
708#endif
709    __table_.rehash(__n);
710    insert(__first, __last);
711}
712
713template <class _Value, class _Hash, class _Pred, class _Alloc>
714template <class _InputIterator>
715unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
716        _InputIterator __first, _InputIterator __last, size_type __n,
717        const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
718    : __table_(__hf, __eql, __a)
719{
720#if _LIBCPP_DEBUG_LEVEL >= 2
721    __get_db()->__insert_c(this);
722#endif
723    __table_.rehash(__n);
724    insert(__first, __last);
725}
726
727template <class _Value, class _Hash, class _Pred, class _Alloc>
728inline
729unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
730        const allocator_type& __a)
731    : __table_(__a)
732{
733#if _LIBCPP_DEBUG_LEVEL >= 2
734    __get_db()->__insert_c(this);
735#endif
736}
737
738template <class _Value, class _Hash, class _Pred, class _Alloc>
739unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
740        const unordered_set& __u)
741    : __table_(__u.__table_)
742{
743#if _LIBCPP_DEBUG_LEVEL >= 2
744    __get_db()->__insert_c(this);
745#endif
746    __table_.rehash(__u.bucket_count());
747    insert(__u.begin(), __u.end());
748}
749
750template <class _Value, class _Hash, class _Pred, class _Alloc>
751unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
752        const unordered_set& __u, const allocator_type& __a)
753    : __table_(__u.__table_, __a)
754{
755#if _LIBCPP_DEBUG_LEVEL >= 2
756    __get_db()->__insert_c(this);
757#endif
758    __table_.rehash(__u.bucket_count());
759    insert(__u.begin(), __u.end());
760}
761
762#ifndef _LIBCPP_CXX03_LANG
763
764template <class _Value, class _Hash, class _Pred, class _Alloc>
765inline
766unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
767        unordered_set&& __u)
768    _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
769    : __table_(_VSTD::move(__u.__table_))
770{
771#if _LIBCPP_DEBUG_LEVEL >= 2
772    __get_db()->__insert_c(this);
773    __get_db()->swap(this, &__u);
774#endif
775}
776
777template <class _Value, class _Hash, class _Pred, class _Alloc>
778unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
779        unordered_set&& __u, const allocator_type& __a)
780    : __table_(_VSTD::move(__u.__table_), __a)
781{
782#if _LIBCPP_DEBUG_LEVEL >= 2
783    __get_db()->__insert_c(this);
784#endif
785    if (__a != __u.get_allocator())
786    {
787        iterator __i = __u.begin();
788        while (__u.size() != 0)
789            __table_.__insert_unique(_VSTD::move(__u.__table_.remove(__i++)->__value_));
790    }
791#if _LIBCPP_DEBUG_LEVEL >= 2
792    else
793        __get_db()->swap(this, &__u);
794#endif
795}
796
797template <class _Value, class _Hash, class _Pred, class _Alloc>
798unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
799        initializer_list<value_type> __il)
800{
801#if _LIBCPP_DEBUG_LEVEL >= 2
802    __get_db()->__insert_c(this);
803#endif
804    insert(__il.begin(), __il.end());
805}
806
807template <class _Value, class _Hash, class _Pred, class _Alloc>
808unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
809        initializer_list<value_type> __il, size_type __n, const hasher& __hf,
810        const key_equal& __eql)
811    : __table_(__hf, __eql)
812{
813#if _LIBCPP_DEBUG_LEVEL >= 2
814    __get_db()->__insert_c(this);
815#endif
816    __table_.rehash(__n);
817    insert(__il.begin(), __il.end());
818}
819
820template <class _Value, class _Hash, class _Pred, class _Alloc>
821unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
822        initializer_list<value_type> __il, size_type __n, const hasher& __hf,
823        const key_equal& __eql, const allocator_type& __a)
824    : __table_(__hf, __eql, __a)
825{
826#if _LIBCPP_DEBUG_LEVEL >= 2
827    __get_db()->__insert_c(this);
828#endif
829    __table_.rehash(__n);
830    insert(__il.begin(), __il.end());
831}
832
833template <class _Value, class _Hash, class _Pred, class _Alloc>
834inline
835unordered_set<_Value, _Hash, _Pred, _Alloc>&
836unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(unordered_set&& __u)
837    _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
838{
839    __table_ = _VSTD::move(__u.__table_);
840    return *this;
841}
842
843template <class _Value, class _Hash, class _Pred, class _Alloc>
844inline
845unordered_set<_Value, _Hash, _Pred, _Alloc>&
846unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(
847        initializer_list<value_type> __il)
848{
849    __table_.__assign_unique(__il.begin(), __il.end());
850    return *this;
851}
852
853#endif  // _LIBCPP_CXX03_LANG
854
855template <class _Value, class _Hash, class _Pred, class _Alloc>
856template <class _InputIterator>
857inline
858void
859unordered_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
860                                                    _InputIterator __last)
861{
862    for (; __first != __last; ++__first)
863        __table_.__insert_unique(*__first);
864}
865
866template <class _Value, class _Hash, class _Pred, class _Alloc>
867inline _LIBCPP_INLINE_VISIBILITY
868void
869swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
870     unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
871    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
872{
873    __x.swap(__y);
874}
875
876template <class _Value, class _Hash, class _Pred, class _Alloc>
877bool
878operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
879           const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
880{
881    if (__x.size() != __y.size())
882        return false;
883    typedef typename unordered_set<_Value, _Hash, _Pred, _Alloc>::const_iterator
884                                                                 const_iterator;
885    for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();
886            __i != __ex; ++__i)
887    {
888        const_iterator __j = __y.find(*__i);
889        if (__j == __ey || !(*__i == *__j))
890            return false;
891    }
892    return true;
893}
894
895template <class _Value, class _Hash, class _Pred, class _Alloc>
896inline _LIBCPP_INLINE_VISIBILITY
897bool
898operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
899           const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
900{
901    return !(__x == __y);
902}
903
904template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>,
905          class _Alloc = allocator<_Value> >
906class _LIBCPP_TEMPLATE_VIS unordered_multiset
907{
908public:
909    // types
910    typedef _Value                                                     key_type;
911    typedef key_type                                                   value_type;
912    typedef _Hash                                                      hasher;
913    typedef _Pred                                                      key_equal;
914    typedef _Alloc                                                     allocator_type;
915    typedef value_type&                                                reference;
916    typedef const value_type&                                          const_reference;
917    static_assert((is_same<value_type, typename allocator_type::value_type>::value),
918                  "Invalid allocator::value_type");
919
920private:
921    typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
922
923    __table __table_;
924
925public:
926    typedef typename __table::pointer         pointer;
927    typedef typename __table::const_pointer   const_pointer;
928    typedef typename __table::size_type       size_type;
929    typedef typename __table::difference_type difference_type;
930
931    typedef typename __table::const_iterator       iterator;
932    typedef typename __table::const_iterator       const_iterator;
933    typedef typename __table::const_local_iterator local_iterator;
934    typedef typename __table::const_local_iterator const_local_iterator;
935
936#if _LIBCPP_STD_VER > 14
937    typedef __set_node_handle<typename __table::__node, allocator_type> node_type;
938#endif
939
940    _LIBCPP_INLINE_VISIBILITY
941    unordered_multiset()
942        _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
943        {
944#if _LIBCPP_DEBUG_LEVEL >= 2
945            __get_db()->__insert_c(this);
946#endif
947        }
948    explicit unordered_multiset(size_type __n, const hasher& __hf = hasher(),
949                                const key_equal& __eql = key_equal());
950    unordered_multiset(size_type __n, const hasher& __hf,
951                       const key_equal& __eql, const allocator_type& __a);
952#if _LIBCPP_STD_VER > 11
953    inline _LIBCPP_INLINE_VISIBILITY
954    unordered_multiset(size_type __n, const allocator_type& __a)
955        : unordered_multiset(__n, hasher(), key_equal(), __a) {}
956    inline _LIBCPP_INLINE_VISIBILITY
957    unordered_multiset(size_type __n, const hasher& __hf, const allocator_type& __a)
958        : unordered_multiset(__n, __hf, key_equal(), __a) {}
959#endif
960    template <class _InputIterator>
961        unordered_multiset(_InputIterator __first, _InputIterator __last);
962    template <class _InputIterator>
963        unordered_multiset(_InputIterator __first, _InputIterator __last,
964                      size_type __n, const hasher& __hf = hasher(),
965                      const key_equal& __eql = key_equal());
966    template <class _InputIterator>
967        unordered_multiset(_InputIterator __first, _InputIterator __last,
968                      size_type __n , const hasher& __hf,
969                      const key_equal& __eql, const allocator_type& __a);
970#if _LIBCPP_STD_VER > 11
971    template <class _InputIterator>
972    inline _LIBCPP_INLINE_VISIBILITY
973    unordered_multiset(_InputIterator __first, _InputIterator __last,
974                       size_type __n, const allocator_type& __a)
975        : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a) {}
976    template <class _InputIterator>
977    inline _LIBCPP_INLINE_VISIBILITY
978    unordered_multiset(_InputIterator __first, _InputIterator __last,
979                       size_type __n, const hasher& __hf, const allocator_type& __a)
980        : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a) {}
981#endif
982    _LIBCPP_INLINE_VISIBILITY
983    explicit unordered_multiset(const allocator_type& __a);
984    unordered_multiset(const unordered_multiset& __u);
985    unordered_multiset(const unordered_multiset& __u, const allocator_type& __a);
986#ifndef _LIBCPP_CXX03_LANG
987    _LIBCPP_INLINE_VISIBILITY
988    unordered_multiset(unordered_multiset&& __u)
989        _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
990    unordered_multiset(unordered_multiset&& __u, const allocator_type& __a);
991    unordered_multiset(initializer_list<value_type> __il);
992    unordered_multiset(initializer_list<value_type> __il, size_type __n,
993                       const hasher& __hf = hasher(),
994                       const key_equal& __eql = key_equal());
995    unordered_multiset(initializer_list<value_type> __il, size_type __n,
996                       const hasher& __hf, const key_equal& __eql,
997                       const allocator_type& __a);
998#if _LIBCPP_STD_VER > 11
999    inline _LIBCPP_INLINE_VISIBILITY
1000    unordered_multiset(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)
1001      : unordered_multiset(__il, __n, hasher(), key_equal(), __a) {}
1002    inline _LIBCPP_INLINE_VISIBILITY
1003    unordered_multiset(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a)
1004      : unordered_multiset(__il, __n, __hf, key_equal(), __a) {}
1005#endif
1006#endif  // _LIBCPP_CXX03_LANG
1007    // ~unordered_multiset() = default;
1008    _LIBCPP_INLINE_VISIBILITY
1009    unordered_multiset& operator=(const unordered_multiset& __u)
1010    {
1011        __table_ = __u.__table_;
1012        return *this;
1013    }
1014#ifndef _LIBCPP_CXX03_LANG
1015    _LIBCPP_INLINE_VISIBILITY
1016    unordered_multiset& operator=(unordered_multiset&& __u)
1017        _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
1018    unordered_multiset& operator=(initializer_list<value_type> __il);
1019#endif  // _LIBCPP_CXX03_LANG
1020
1021    _LIBCPP_INLINE_VISIBILITY
1022    allocator_type get_allocator() const _NOEXCEPT
1023        {return allocator_type(__table_.__node_alloc());}
1024
1025    _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
1026    bool      empty() const _NOEXCEPT {return __table_.size() == 0;}
1027    _LIBCPP_INLINE_VISIBILITY
1028    size_type size() const _NOEXCEPT  {return __table_.size();}
1029    _LIBCPP_INLINE_VISIBILITY
1030    size_type max_size() const _NOEXCEPT {return __table_.max_size();}
1031
1032    _LIBCPP_INLINE_VISIBILITY
1033    iterator       begin() _NOEXCEPT        {return __table_.begin();}
1034    _LIBCPP_INLINE_VISIBILITY
1035    iterator       end() _NOEXCEPT          {return __table_.end();}
1036    _LIBCPP_INLINE_VISIBILITY
1037    const_iterator begin()  const _NOEXCEPT {return __table_.begin();}
1038    _LIBCPP_INLINE_VISIBILITY
1039    const_iterator end()    const _NOEXCEPT {return __table_.end();}
1040    _LIBCPP_INLINE_VISIBILITY
1041    const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
1042    _LIBCPP_INLINE_VISIBILITY
1043    const_iterator cend()   const _NOEXCEPT {return __table_.end();}
1044
1045#ifndef _LIBCPP_CXX03_LANG
1046    template <class... _Args>
1047        _LIBCPP_INLINE_VISIBILITY
1048        iterator emplace(_Args&&... __args)
1049            {return __table_.__emplace_multi(_VSTD::forward<_Args>(__args)...);}
1050    template <class... _Args>
1051        _LIBCPP_INLINE_VISIBILITY
1052        iterator emplace_hint(const_iterator __p, _Args&&... __args)
1053            {return __table_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);}
1054
1055    _LIBCPP_INLINE_VISIBILITY
1056    iterator insert(value_type&& __x) {return __table_.__insert_multi(_VSTD::move(__x));}
1057    _LIBCPP_INLINE_VISIBILITY
1058    iterator insert(const_iterator __p, value_type&& __x)
1059        {return __table_.__insert_multi(__p, _VSTD::move(__x));}
1060    _LIBCPP_INLINE_VISIBILITY
1061    void insert(initializer_list<value_type> __il)
1062        {insert(__il.begin(), __il.end());}
1063#endif  // _LIBCPP_CXX03_LANG
1064
1065    _LIBCPP_INLINE_VISIBILITY
1066    iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
1067
1068    _LIBCPP_INLINE_VISIBILITY
1069    iterator insert(const_iterator __p, const value_type& __x)
1070        {return __table_.__insert_multi(__p, __x);}
1071
1072    template <class _InputIterator>
1073        _LIBCPP_INLINE_VISIBILITY
1074        void insert(_InputIterator __first, _InputIterator __last);
1075
1076#if _LIBCPP_STD_VER > 14
1077    _LIBCPP_INLINE_VISIBILITY
1078    iterator insert(node_type&& __nh)
1079    {
1080        _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
1081            "node_type with incompatible allocator passed to unordered_multiset::insert()");
1082        return __table_.template __node_handle_insert_multi<node_type>(
1083            _VSTD::move(__nh));
1084    }
1085    _LIBCPP_INLINE_VISIBILITY
1086    iterator insert(const_iterator __hint, node_type&& __nh)
1087    {
1088        _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
1089            "node_type with incompatible allocator passed to unordered_multiset::insert()");
1090        return __table_.template __node_handle_insert_multi<node_type>(
1091            __hint, _VSTD::move(__nh));
1092    }
1093    _LIBCPP_INLINE_VISIBILITY
1094    node_type extract(const_iterator __position)
1095    {
1096        return __table_.template __node_handle_extract<node_type>(
1097            __position);
1098    }
1099    _LIBCPP_INLINE_VISIBILITY
1100    node_type extract(key_type const& __key)
1101    {
1102        return __table_.template __node_handle_extract<node_type>(__key);
1103    }
1104#endif
1105
1106    _LIBCPP_INLINE_VISIBILITY
1107    iterator erase(const_iterator __p) {return __table_.erase(__p);}
1108    _LIBCPP_INLINE_VISIBILITY
1109    size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
1110    _LIBCPP_INLINE_VISIBILITY
1111    iterator erase(const_iterator __first, const_iterator __last)
1112        {return __table_.erase(__first, __last);}
1113    _LIBCPP_INLINE_VISIBILITY
1114    void clear() _NOEXCEPT {__table_.clear();}
1115
1116    _LIBCPP_INLINE_VISIBILITY
1117    void swap(unordered_multiset& __u)
1118        _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
1119        {__table_.swap(__u.__table_);}
1120
1121    _LIBCPP_INLINE_VISIBILITY
1122    hasher hash_function() const {return __table_.hash_function();}
1123    _LIBCPP_INLINE_VISIBILITY
1124    key_equal key_eq() const {return __table_.key_eq();}
1125
1126    _LIBCPP_INLINE_VISIBILITY
1127    iterator       find(const key_type& __k)       {return __table_.find(__k);}
1128    _LIBCPP_INLINE_VISIBILITY
1129    const_iterator find(const key_type& __k) const {return __table_.find(__k);}
1130    _LIBCPP_INLINE_VISIBILITY
1131    size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
1132    _LIBCPP_INLINE_VISIBILITY
1133    pair<iterator, iterator>             equal_range(const key_type& __k)
1134        {return __table_.__equal_range_multi(__k);}
1135    _LIBCPP_INLINE_VISIBILITY
1136    pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
1137        {return __table_.__equal_range_multi(__k);}
1138
1139    _LIBCPP_INLINE_VISIBILITY
1140    size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
1141    _LIBCPP_INLINE_VISIBILITY
1142    size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
1143
1144    _LIBCPP_INLINE_VISIBILITY
1145    size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);}
1146    _LIBCPP_INLINE_VISIBILITY
1147    size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
1148
1149    _LIBCPP_INLINE_VISIBILITY
1150    local_iterator       begin(size_type __n)        {return __table_.begin(__n);}
1151    _LIBCPP_INLINE_VISIBILITY
1152    local_iterator       end(size_type __n)          {return __table_.end(__n);}
1153    _LIBCPP_INLINE_VISIBILITY
1154    const_local_iterator begin(size_type __n) const  {return __table_.cbegin(__n);}
1155    _LIBCPP_INLINE_VISIBILITY
1156    const_local_iterator end(size_type __n) const    {return __table_.cend(__n);}
1157    _LIBCPP_INLINE_VISIBILITY
1158    const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
1159    _LIBCPP_INLINE_VISIBILITY
1160    const_local_iterator cend(size_type __n) const   {return __table_.cend(__n);}
1161
1162    _LIBCPP_INLINE_VISIBILITY
1163    float load_factor() const _NOEXCEPT {return __table_.load_factor();}
1164    _LIBCPP_INLINE_VISIBILITY
1165    float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
1166    _LIBCPP_INLINE_VISIBILITY
1167    void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
1168    _LIBCPP_INLINE_VISIBILITY
1169    void rehash(size_type __n) {__table_.rehash(__n);}
1170    _LIBCPP_INLINE_VISIBILITY
1171    void reserve(size_type __n) {__table_.reserve(__n);}
1172
1173#if _LIBCPP_DEBUG_LEVEL >= 2
1174
1175    bool __dereferenceable(const const_iterator* __i) const
1176        {return __table_.__dereferenceable(__i);}
1177    bool __decrementable(const const_iterator* __i) const
1178        {return __table_.__decrementable(__i);}
1179    bool __addable(const const_iterator* __i, ptrdiff_t __n) const
1180        {return __table_.__addable(__i, __n);}
1181    bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
1182        {return __table_.__addable(__i, __n);}
1183
1184#endif  // _LIBCPP_DEBUG_LEVEL >= 2
1185
1186};
1187
1188template <class _Value, class _Hash, class _Pred, class _Alloc>
1189unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1190        size_type __n, const hasher& __hf, const key_equal& __eql)
1191    : __table_(__hf, __eql)
1192{
1193#if _LIBCPP_DEBUG_LEVEL >= 2
1194    __get_db()->__insert_c(this);
1195#endif
1196    __table_.rehash(__n);
1197}
1198
1199template <class _Value, class _Hash, class _Pred, class _Alloc>
1200unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1201        size_type __n, const hasher& __hf, const key_equal& __eql,
1202        const allocator_type& __a)
1203    : __table_(__hf, __eql, __a)
1204{
1205#if _LIBCPP_DEBUG_LEVEL >= 2
1206    __get_db()->__insert_c(this);
1207#endif
1208    __table_.rehash(__n);
1209}
1210
1211template <class _Value, class _Hash, class _Pred, class _Alloc>
1212template <class _InputIterator>
1213unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1214        _InputIterator __first, _InputIterator __last)
1215{
1216#if _LIBCPP_DEBUG_LEVEL >= 2
1217    __get_db()->__insert_c(this);
1218#endif
1219    insert(__first, __last);
1220}
1221
1222template <class _Value, class _Hash, class _Pred, class _Alloc>
1223template <class _InputIterator>
1224unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1225        _InputIterator __first, _InputIterator __last, size_type __n,
1226        const hasher& __hf, const key_equal& __eql)
1227    : __table_(__hf, __eql)
1228{
1229#if _LIBCPP_DEBUG_LEVEL >= 2
1230    __get_db()->__insert_c(this);
1231#endif
1232    __table_.rehash(__n);
1233    insert(__first, __last);
1234}
1235
1236template <class _Value, class _Hash, class _Pred, class _Alloc>
1237template <class _InputIterator>
1238unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1239        _InputIterator __first, _InputIterator __last, size_type __n,
1240        const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1241    : __table_(__hf, __eql, __a)
1242{
1243#if _LIBCPP_DEBUG_LEVEL >= 2
1244    __get_db()->__insert_c(this);
1245#endif
1246    __table_.rehash(__n);
1247    insert(__first, __last);
1248}
1249
1250template <class _Value, class _Hash, class _Pred, class _Alloc>
1251inline
1252unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1253        const allocator_type& __a)
1254    : __table_(__a)
1255{
1256#if _LIBCPP_DEBUG_LEVEL >= 2
1257    __get_db()->__insert_c(this);
1258#endif
1259}
1260
1261template <class _Value, class _Hash, class _Pred, class _Alloc>
1262unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1263        const unordered_multiset& __u)
1264    : __table_(__u.__table_)
1265{
1266#if _LIBCPP_DEBUG_LEVEL >= 2
1267    __get_db()->__insert_c(this);
1268#endif
1269    __table_.rehash(__u.bucket_count());
1270    insert(__u.begin(), __u.end());
1271}
1272
1273template <class _Value, class _Hash, class _Pred, class _Alloc>
1274unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1275        const unordered_multiset& __u, const allocator_type& __a)
1276    : __table_(__u.__table_, __a)
1277{
1278#if _LIBCPP_DEBUG_LEVEL >= 2
1279    __get_db()->__insert_c(this);
1280#endif
1281    __table_.rehash(__u.bucket_count());
1282    insert(__u.begin(), __u.end());
1283}
1284
1285#ifndef _LIBCPP_CXX03_LANG
1286
1287template <class _Value, class _Hash, class _Pred, class _Alloc>
1288inline
1289unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1290        unordered_multiset&& __u)
1291    _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
1292    : __table_(_VSTD::move(__u.__table_))
1293{
1294#if _LIBCPP_DEBUG_LEVEL >= 2
1295    __get_db()->__insert_c(this);
1296    __get_db()->swap(this, &__u);
1297#endif
1298}
1299
1300template <class _Value, class _Hash, class _Pred, class _Alloc>
1301unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1302        unordered_multiset&& __u, const allocator_type& __a)
1303    : __table_(_VSTD::move(__u.__table_), __a)
1304{
1305#if _LIBCPP_DEBUG_LEVEL >= 2
1306    __get_db()->__insert_c(this);
1307#endif
1308    if (__a != __u.get_allocator())
1309    {
1310        iterator __i = __u.begin();
1311        while (__u.size() != 0)
1312            __table_.__insert_multi(_VSTD::move(__u.__table_.remove(__i++)->__value_));
1313    }
1314#if _LIBCPP_DEBUG_LEVEL >= 2
1315    else
1316        __get_db()->swap(this, &__u);
1317#endif
1318}
1319
1320template <class _Value, class _Hash, class _Pred, class _Alloc>
1321unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1322        initializer_list<value_type> __il)
1323{
1324#if _LIBCPP_DEBUG_LEVEL >= 2
1325    __get_db()->__insert_c(this);
1326#endif
1327    insert(__il.begin(), __il.end());
1328}
1329
1330template <class _Value, class _Hash, class _Pred, class _Alloc>
1331unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1332        initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1333        const key_equal& __eql)
1334    : __table_(__hf, __eql)
1335{
1336#if _LIBCPP_DEBUG_LEVEL >= 2
1337    __get_db()->__insert_c(this);
1338#endif
1339    __table_.rehash(__n);
1340    insert(__il.begin(), __il.end());
1341}
1342
1343template <class _Value, class _Hash, class _Pred, class _Alloc>
1344unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1345        initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1346        const key_equal& __eql, const allocator_type& __a)
1347    : __table_(__hf, __eql, __a)
1348{
1349#if _LIBCPP_DEBUG_LEVEL >= 2
1350    __get_db()->__insert_c(this);
1351#endif
1352    __table_.rehash(__n);
1353    insert(__il.begin(), __il.end());
1354}
1355
1356template <class _Value, class _Hash, class _Pred, class _Alloc>
1357inline
1358unordered_multiset<_Value, _Hash, _Pred, _Alloc>&
1359unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(
1360        unordered_multiset&& __u)
1361    _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
1362{
1363    __table_ = _VSTD::move(__u.__table_);
1364    return *this;
1365}
1366
1367template <class _Value, class _Hash, class _Pred, class _Alloc>
1368inline
1369unordered_multiset<_Value, _Hash, _Pred, _Alloc>&
1370unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(
1371        initializer_list<value_type> __il)
1372{
1373    __table_.__assign_multi(__il.begin(), __il.end());
1374    return *this;
1375}
1376
1377#endif  // _LIBCPP_CXX03_LANG
1378
1379template <class _Value, class _Hash, class _Pred, class _Alloc>
1380template <class _InputIterator>
1381inline
1382void
1383unordered_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
1384                                                         _InputIterator __last)
1385{
1386    for (; __first != __last; ++__first)
1387        __table_.__insert_multi(*__first);
1388}
1389
1390template <class _Value, class _Hash, class _Pred, class _Alloc>
1391inline _LIBCPP_INLINE_VISIBILITY
1392void
1393swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1394     unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1395    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1396{
1397    __x.swap(__y);
1398}
1399
1400template <class _Value, class _Hash, class _Pred, class _Alloc>
1401bool
1402operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1403           const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1404{
1405    if (__x.size() != __y.size())
1406        return false;
1407    typedef typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator
1408                                                                 const_iterator;
1409    typedef pair<const_iterator, const_iterator> _EqRng;
1410    for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;)
1411    {
1412        _EqRng __xeq = __x.equal_range(*__i);
1413        _EqRng __yeq = __y.equal_range(*__i);
1414        if (_VSTD::distance(__xeq.first, __xeq.second) !=
1415            _VSTD::distance(__yeq.first, __yeq.second) ||
1416                  !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first))
1417            return false;
1418        __i = __xeq.second;
1419    }
1420    return true;
1421}
1422
1423template <class _Value, class _Hash, class _Pred, class _Alloc>
1424inline _LIBCPP_INLINE_VISIBILITY
1425bool
1426operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1427           const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1428{
1429    return !(__x == __y);
1430}
1431
1432_LIBCPP_END_NAMESPACE_STD
1433
1434#endif  // _LIBCPP_UNORDERED_SET
1435