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#include <version>
342
343#include <__debug>
344
345#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
346#pragma GCC system_header
347#endif
348
349_LIBCPP_BEGIN_NAMESPACE_STD
350
351template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>,
352          class _Alloc = allocator<_Value> >
353class _LIBCPP_TEMPLATE_VIS unordered_set
354{
355public:
356    // types
357    typedef _Value                                                     key_type;
358    typedef key_type                                                   value_type;
359    typedef _Hash                                                      hasher;
360    typedef _Pred                                                      key_equal;
361    typedef _Alloc                                                     allocator_type;
362    typedef value_type&                                                reference;
363    typedef const value_type&                                          const_reference;
364    static_assert((is_same<value_type, typename allocator_type::value_type>::value),
365                  "Invalid allocator::value_type");
366
367private:
368    typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
369
370    __table __table_;
371
372public:
373    typedef typename __table::pointer         pointer;
374    typedef typename __table::const_pointer   const_pointer;
375    typedef typename __table::size_type       size_type;
376    typedef typename __table::difference_type difference_type;
377
378    typedef typename __table::const_iterator       iterator;
379    typedef typename __table::const_iterator       const_iterator;
380    typedef typename __table::const_local_iterator local_iterator;
381    typedef typename __table::const_local_iterator const_local_iterator;
382
383#if _LIBCPP_STD_VER > 14
384    typedef __set_node_handle<typename __table::__node, allocator_type> node_type;
385    typedef __insert_return_type<iterator, node_type> insert_return_type;
386#endif
387
388    _LIBCPP_INLINE_VISIBILITY
389    unordered_set()
390        _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
391        {
392#if _LIBCPP_DEBUG_LEVEL >= 2
393            __get_db()->__insert_c(this);
394#endif
395        }
396    explicit unordered_set(size_type __n, const hasher& __hf = hasher(),
397                           const key_equal& __eql = key_equal());
398#if _LIBCPP_STD_VER > 11
399    inline _LIBCPP_INLINE_VISIBILITY
400    unordered_set(size_type __n, const allocator_type& __a)
401        : unordered_set(__n, hasher(), key_equal(), __a) {}
402    inline _LIBCPP_INLINE_VISIBILITY
403    unordered_set(size_type __n, const hasher& __hf, const allocator_type& __a)
404        : unordered_set(__n, __hf, key_equal(), __a) {}
405#endif
406    unordered_set(size_type __n, const hasher& __hf, const key_equal& __eql,
407                  const allocator_type& __a);
408    template <class _InputIterator>
409        unordered_set(_InputIterator __first, _InputIterator __last);
410    template <class _InputIterator>
411        unordered_set(_InputIterator __first, _InputIterator __last,
412                      size_type __n, const hasher& __hf = hasher(),
413                      const key_equal& __eql = key_equal());
414    template <class _InputIterator>
415        unordered_set(_InputIterator __first, _InputIterator __last,
416                      size_type __n, const hasher& __hf, const key_equal& __eql,
417                      const allocator_type& __a);
418#if _LIBCPP_STD_VER > 11
419    template <class _InputIterator>
420    inline _LIBCPP_INLINE_VISIBILITY
421        unordered_set(_InputIterator __first, _InputIterator __last,
422                    size_type __n, const allocator_type& __a)
423            : unordered_set(__first, __last, __n, hasher(), key_equal(), __a) {}
424    template <class _InputIterator>
425        unordered_set(_InputIterator __first, _InputIterator __last,
426                      size_type __n, const hasher& __hf, const allocator_type& __a)
427            : unordered_set(__first, __last, __n, __hf, key_equal(), __a) {}
428#endif
429    _LIBCPP_INLINE_VISIBILITY
430    explicit unordered_set(const allocator_type& __a);
431    unordered_set(const unordered_set& __u);
432    unordered_set(const unordered_set& __u, const allocator_type& __a);
433#ifndef _LIBCPP_CXX03_LANG
434    _LIBCPP_INLINE_VISIBILITY
435    unordered_set(unordered_set&& __u)
436        _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
437    unordered_set(unordered_set&& __u, const allocator_type& __a);
438    unordered_set(initializer_list<value_type> __il);
439    unordered_set(initializer_list<value_type> __il, size_type __n,
440                  const hasher& __hf = hasher(),
441                  const key_equal& __eql = key_equal());
442    unordered_set(initializer_list<value_type> __il, size_type __n,
443                  const hasher& __hf, const key_equal& __eql,
444                  const allocator_type& __a);
445#if _LIBCPP_STD_VER > 11
446    inline _LIBCPP_INLINE_VISIBILITY
447    unordered_set(initializer_list<value_type> __il, size_type __n,
448                                                      const allocator_type& __a)
449        : unordered_set(__il, __n, hasher(), key_equal(), __a) {}
450    inline _LIBCPP_INLINE_VISIBILITY
451    unordered_set(initializer_list<value_type> __il, size_type __n,
452                                  const hasher& __hf, const allocator_type& __a)
453        : unordered_set(__il, __n, __hf, key_equal(), __a) {}
454#endif
455#endif  // _LIBCPP_CXX03_LANG
456    // ~unordered_set() = default;
457    _LIBCPP_INLINE_VISIBILITY
458    unordered_set& operator=(const unordered_set& __u)
459    {
460        __table_ = __u.__table_;
461        return *this;
462    }
463#ifndef _LIBCPP_CXX03_LANG
464    _LIBCPP_INLINE_VISIBILITY
465    unordered_set& operator=(unordered_set&& __u)
466        _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
467    _LIBCPP_INLINE_VISIBILITY
468    unordered_set& operator=(initializer_list<value_type> __il);
469#endif  // _LIBCPP_CXX03_LANG
470
471    _LIBCPP_INLINE_VISIBILITY
472    allocator_type get_allocator() const _NOEXCEPT
473        {return allocator_type(__table_.__node_alloc());}
474
475    _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
476    bool      empty() const _NOEXCEPT {return __table_.size() == 0;}
477    _LIBCPP_INLINE_VISIBILITY
478    size_type size() const _NOEXCEPT  {return __table_.size();}
479    _LIBCPP_INLINE_VISIBILITY
480    size_type max_size() const _NOEXCEPT {return __table_.max_size();}
481
482    _LIBCPP_INLINE_VISIBILITY
483    iterator       begin() _NOEXCEPT        {return __table_.begin();}
484    _LIBCPP_INLINE_VISIBILITY
485    iterator       end() _NOEXCEPT          {return __table_.end();}
486    _LIBCPP_INLINE_VISIBILITY
487    const_iterator begin()  const _NOEXCEPT {return __table_.begin();}
488    _LIBCPP_INLINE_VISIBILITY
489    const_iterator end()    const _NOEXCEPT {return __table_.end();}
490    _LIBCPP_INLINE_VISIBILITY
491    const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
492    _LIBCPP_INLINE_VISIBILITY
493    const_iterator cend()   const _NOEXCEPT {return __table_.end();}
494
495#ifndef _LIBCPP_CXX03_LANG
496    template <class... _Args>
497        _LIBCPP_INLINE_VISIBILITY
498        pair<iterator, bool> emplace(_Args&&... __args)
499            {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...);}
500    template <class... _Args>
501        _LIBCPP_INLINE_VISIBILITY
502#if _LIBCPP_DEBUG_LEVEL >= 2
503        iterator emplace_hint(const_iterator __p, _Args&&... __args)
504        {
505            _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
506                "unordered_set::emplace_hint(const_iterator, args...) called with an iterator not"
507                " referring to this unordered_set");
508            return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first;
509        }
510#else
511        iterator emplace_hint(const_iterator, _Args&&... __args)
512            {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first;}
513#endif
514
515    _LIBCPP_INLINE_VISIBILITY
516    pair<iterator, bool> insert(value_type&& __x)
517        {return __table_.__insert_unique(_VSTD::move(__x));}
518    _LIBCPP_INLINE_VISIBILITY
519#if _LIBCPP_DEBUG_LEVEL >= 2
520    iterator insert(const_iterator __p, value_type&& __x)
521        {
522            _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
523                "unordered_set::insert(const_iterator, value_type&&) called with an iterator not"
524                " referring to this unordered_set");
525            return insert(_VSTD::move(__x)).first;
526        }
527#else
528    iterator insert(const_iterator, value_type&& __x)
529        {return insert(_VSTD::move(__x)).first;}
530#endif
531    _LIBCPP_INLINE_VISIBILITY
532    void insert(initializer_list<value_type> __il)
533        {insert(__il.begin(), __il.end());}
534#endif  // _LIBCPP_CXX03_LANG
535    _LIBCPP_INLINE_VISIBILITY
536    pair<iterator, bool> insert(const value_type& __x)
537        {return __table_.__insert_unique(__x);}
538
539    _LIBCPP_INLINE_VISIBILITY
540#if _LIBCPP_DEBUG_LEVEL >= 2
541    iterator insert(const_iterator __p, const value_type& __x)
542        {
543            _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
544                "unordered_set::insert(const_iterator, const value_type&) called with an iterator not"
545                " referring to this unordered_set");
546            return insert(__x).first;
547        }
548#else
549    iterator insert(const_iterator, const value_type& __x)
550        {return insert(__x).first;}
551#endif
552    template <class _InputIterator>
553        _LIBCPP_INLINE_VISIBILITY
554        void insert(_InputIterator __first, _InputIterator __last);
555
556    _LIBCPP_INLINE_VISIBILITY
557    iterator erase(const_iterator __p) {return __table_.erase(__p);}
558    _LIBCPP_INLINE_VISIBILITY
559    size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
560    _LIBCPP_INLINE_VISIBILITY
561    iterator erase(const_iterator __first, const_iterator __last)
562        {return __table_.erase(__first, __last);}
563    _LIBCPP_INLINE_VISIBILITY
564    void clear() _NOEXCEPT {__table_.clear();}
565
566#if _LIBCPP_STD_VER > 14
567    _LIBCPP_INLINE_VISIBILITY
568    insert_return_type insert(node_type&& __nh)
569    {
570        _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
571            "node_type with incompatible allocator passed to unordered_set::insert()");
572        return __table_.template __node_handle_insert_unique<
573            node_type, insert_return_type>(_VSTD::move(__nh));
574    }
575    _LIBCPP_INLINE_VISIBILITY
576    iterator insert(const_iterator __h, node_type&& __nh)
577    {
578        _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
579            "node_type with incompatible allocator passed to unordered_set::insert()");
580        return __table_.template __node_handle_insert_unique<node_type>(
581            __h, _VSTD::move(__nh));
582    }
583    _LIBCPP_INLINE_VISIBILITY
584    node_type extract(key_type const& __key)
585    {
586        return __table_.template __node_handle_extract<node_type>(__key);
587    }
588    _LIBCPP_INLINE_VISIBILITY
589    node_type extract(const_iterator __it)
590    {
591        return __table_.template __node_handle_extract<node_type>(__it);
592    }
593#endif
594
595    _LIBCPP_INLINE_VISIBILITY
596    void swap(unordered_set& __u)
597        _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
598        {__table_.swap(__u.__table_);}
599
600    _LIBCPP_INLINE_VISIBILITY
601    hasher hash_function() const {return __table_.hash_function();}
602    _LIBCPP_INLINE_VISIBILITY
603    key_equal key_eq() const {return __table_.key_eq();}
604
605    _LIBCPP_INLINE_VISIBILITY
606    iterator       find(const key_type& __k)       {return __table_.find(__k);}
607    _LIBCPP_INLINE_VISIBILITY
608    const_iterator find(const key_type& __k) const {return __table_.find(__k);}
609    _LIBCPP_INLINE_VISIBILITY
610    size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
611    _LIBCPP_INLINE_VISIBILITY
612    pair<iterator, iterator>             equal_range(const key_type& __k)
613        {return __table_.__equal_range_unique(__k);}
614    _LIBCPP_INLINE_VISIBILITY
615    pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
616        {return __table_.__equal_range_unique(__k);}
617
618    _LIBCPP_INLINE_VISIBILITY
619    size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
620    _LIBCPP_INLINE_VISIBILITY
621    size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
622
623    _LIBCPP_INLINE_VISIBILITY
624    size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);}
625    _LIBCPP_INLINE_VISIBILITY
626    size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
627
628    _LIBCPP_INLINE_VISIBILITY
629    local_iterator       begin(size_type __n)        {return __table_.begin(__n);}
630    _LIBCPP_INLINE_VISIBILITY
631    local_iterator       end(size_type __n)          {return __table_.end(__n);}
632    _LIBCPP_INLINE_VISIBILITY
633    const_local_iterator begin(size_type __n) const  {return __table_.cbegin(__n);}
634    _LIBCPP_INLINE_VISIBILITY
635    const_local_iterator end(size_type __n) const    {return __table_.cend(__n);}
636    _LIBCPP_INLINE_VISIBILITY
637    const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
638    _LIBCPP_INLINE_VISIBILITY
639    const_local_iterator cend(size_type __n) const   {return __table_.cend(__n);}
640
641    _LIBCPP_INLINE_VISIBILITY
642    float load_factor() const _NOEXCEPT {return __table_.load_factor();}
643    _LIBCPP_INLINE_VISIBILITY
644    float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
645    _LIBCPP_INLINE_VISIBILITY
646    void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
647    _LIBCPP_INLINE_VISIBILITY
648    void rehash(size_type __n) {__table_.rehash(__n);}
649    _LIBCPP_INLINE_VISIBILITY
650    void reserve(size_type __n) {__table_.reserve(__n);}
651
652#if _LIBCPP_DEBUG_LEVEL >= 2
653
654    bool __dereferenceable(const const_iterator* __i) const
655        {return __table_.__dereferenceable(__i);}
656    bool __decrementable(const const_iterator* __i) const
657        {return __table_.__decrementable(__i);}
658    bool __addable(const const_iterator* __i, ptrdiff_t __n) const
659        {return __table_.__addable(__i, __n);}
660    bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
661        {return __table_.__addable(__i, __n);}
662
663#endif  // _LIBCPP_DEBUG_LEVEL >= 2
664
665};
666
667template <class _Value, class _Hash, class _Pred, class _Alloc>
668unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n,
669        const hasher& __hf, const key_equal& __eql)
670    : __table_(__hf, __eql)
671{
672#if _LIBCPP_DEBUG_LEVEL >= 2
673    __get_db()->__insert_c(this);
674#endif
675    __table_.rehash(__n);
676}
677
678template <class _Value, class _Hash, class _Pred, class _Alloc>
679unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n,
680        const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
681    : __table_(__hf, __eql, __a)
682{
683#if _LIBCPP_DEBUG_LEVEL >= 2
684    __get_db()->__insert_c(this);
685#endif
686    __table_.rehash(__n);
687}
688
689template <class _Value, class _Hash, class _Pred, class _Alloc>
690template <class _InputIterator>
691unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
692        _InputIterator __first, _InputIterator __last)
693{
694#if _LIBCPP_DEBUG_LEVEL >= 2
695    __get_db()->__insert_c(this);
696#endif
697    insert(__first, __last);
698}
699
700template <class _Value, class _Hash, class _Pred, class _Alloc>
701template <class _InputIterator>
702unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
703        _InputIterator __first, _InputIterator __last, size_type __n,
704        const hasher& __hf, const key_equal& __eql)
705    : __table_(__hf, __eql)
706{
707#if _LIBCPP_DEBUG_LEVEL >= 2
708    __get_db()->__insert_c(this);
709#endif
710    __table_.rehash(__n);
711    insert(__first, __last);
712}
713
714template <class _Value, class _Hash, class _Pred, class _Alloc>
715template <class _InputIterator>
716unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
717        _InputIterator __first, _InputIterator __last, size_type __n,
718        const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
719    : __table_(__hf, __eql, __a)
720{
721#if _LIBCPP_DEBUG_LEVEL >= 2
722    __get_db()->__insert_c(this);
723#endif
724    __table_.rehash(__n);
725    insert(__first, __last);
726}
727
728template <class _Value, class _Hash, class _Pred, class _Alloc>
729inline
730unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
731        const allocator_type& __a)
732    : __table_(__a)
733{
734#if _LIBCPP_DEBUG_LEVEL >= 2
735    __get_db()->__insert_c(this);
736#endif
737}
738
739template <class _Value, class _Hash, class _Pred, class _Alloc>
740unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
741        const unordered_set& __u)
742    : __table_(__u.__table_)
743{
744#if _LIBCPP_DEBUG_LEVEL >= 2
745    __get_db()->__insert_c(this);
746#endif
747    __table_.rehash(__u.bucket_count());
748    insert(__u.begin(), __u.end());
749}
750
751template <class _Value, class _Hash, class _Pred, class _Alloc>
752unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
753        const unordered_set& __u, const allocator_type& __a)
754    : __table_(__u.__table_, __a)
755{
756#if _LIBCPP_DEBUG_LEVEL >= 2
757    __get_db()->__insert_c(this);
758#endif
759    __table_.rehash(__u.bucket_count());
760    insert(__u.begin(), __u.end());
761}
762
763#ifndef _LIBCPP_CXX03_LANG
764
765template <class _Value, class _Hash, class _Pred, class _Alloc>
766inline
767unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
768        unordered_set&& __u)
769    _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
770    : __table_(_VSTD::move(__u.__table_))
771{
772#if _LIBCPP_DEBUG_LEVEL >= 2
773    __get_db()->__insert_c(this);
774    __get_db()->swap(this, &__u);
775#endif
776}
777
778template <class _Value, class _Hash, class _Pred, class _Alloc>
779unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
780        unordered_set&& __u, const allocator_type& __a)
781    : __table_(_VSTD::move(__u.__table_), __a)
782{
783#if _LIBCPP_DEBUG_LEVEL >= 2
784    __get_db()->__insert_c(this);
785#endif
786    if (__a != __u.get_allocator())
787    {
788        iterator __i = __u.begin();
789        while (__u.size() != 0)
790            __table_.__insert_unique(_VSTD::move(__u.__table_.remove(__i++)->__value_));
791    }
792#if _LIBCPP_DEBUG_LEVEL >= 2
793    else
794        __get_db()->swap(this, &__u);
795#endif
796}
797
798template <class _Value, class _Hash, class _Pred, class _Alloc>
799unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
800        initializer_list<value_type> __il)
801{
802#if _LIBCPP_DEBUG_LEVEL >= 2
803    __get_db()->__insert_c(this);
804#endif
805    insert(__il.begin(), __il.end());
806}
807
808template <class _Value, class _Hash, class _Pred, class _Alloc>
809unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
810        initializer_list<value_type> __il, size_type __n, const hasher& __hf,
811        const key_equal& __eql)
812    : __table_(__hf, __eql)
813{
814#if _LIBCPP_DEBUG_LEVEL >= 2
815    __get_db()->__insert_c(this);
816#endif
817    __table_.rehash(__n);
818    insert(__il.begin(), __il.end());
819}
820
821template <class _Value, class _Hash, class _Pred, class _Alloc>
822unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
823        initializer_list<value_type> __il, size_type __n, const hasher& __hf,
824        const key_equal& __eql, const allocator_type& __a)
825    : __table_(__hf, __eql, __a)
826{
827#if _LIBCPP_DEBUG_LEVEL >= 2
828    __get_db()->__insert_c(this);
829#endif
830    __table_.rehash(__n);
831    insert(__il.begin(), __il.end());
832}
833
834template <class _Value, class _Hash, class _Pred, class _Alloc>
835inline
836unordered_set<_Value, _Hash, _Pred, _Alloc>&
837unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(unordered_set&& __u)
838    _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
839{
840    __table_ = _VSTD::move(__u.__table_);
841    return *this;
842}
843
844template <class _Value, class _Hash, class _Pred, class _Alloc>
845inline
846unordered_set<_Value, _Hash, _Pred, _Alloc>&
847unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(
848        initializer_list<value_type> __il)
849{
850    __table_.__assign_unique(__il.begin(), __il.end());
851    return *this;
852}
853
854#endif  // _LIBCPP_CXX03_LANG
855
856template <class _Value, class _Hash, class _Pred, class _Alloc>
857template <class _InputIterator>
858inline
859void
860unordered_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
861                                                    _InputIterator __last)
862{
863    for (; __first != __last; ++__first)
864        __table_.__insert_unique(*__first);
865}
866
867template <class _Value, class _Hash, class _Pred, class _Alloc>
868inline _LIBCPP_INLINE_VISIBILITY
869void
870swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
871     unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
872    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
873{
874    __x.swap(__y);
875}
876
877template <class _Value, class _Hash, class _Pred, class _Alloc>
878bool
879operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
880           const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
881{
882    if (__x.size() != __y.size())
883        return false;
884    typedef typename unordered_set<_Value, _Hash, _Pred, _Alloc>::const_iterator
885                                                                 const_iterator;
886    for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();
887            __i != __ex; ++__i)
888    {
889        const_iterator __j = __y.find(*__i);
890        if (__j == __ey || !(*__i == *__j))
891            return false;
892    }
893    return true;
894}
895
896template <class _Value, class _Hash, class _Pred, class _Alloc>
897inline _LIBCPP_INLINE_VISIBILITY
898bool
899operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
900           const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
901{
902    return !(__x == __y);
903}
904
905template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>,
906          class _Alloc = allocator<_Value> >
907class _LIBCPP_TEMPLATE_VIS unordered_multiset
908{
909public:
910    // types
911    typedef _Value                                                     key_type;
912    typedef key_type                                                   value_type;
913    typedef _Hash                                                      hasher;
914    typedef _Pred                                                      key_equal;
915    typedef _Alloc                                                     allocator_type;
916    typedef value_type&                                                reference;
917    typedef const value_type&                                          const_reference;
918    static_assert((is_same<value_type, typename allocator_type::value_type>::value),
919                  "Invalid allocator::value_type");
920
921private:
922    typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
923
924    __table __table_;
925
926public:
927    typedef typename __table::pointer         pointer;
928    typedef typename __table::const_pointer   const_pointer;
929    typedef typename __table::size_type       size_type;
930    typedef typename __table::difference_type difference_type;
931
932    typedef typename __table::const_iterator       iterator;
933    typedef typename __table::const_iterator       const_iterator;
934    typedef typename __table::const_local_iterator local_iterator;
935    typedef typename __table::const_local_iterator const_local_iterator;
936
937#if _LIBCPP_STD_VER > 14
938    typedef __set_node_handle<typename __table::__node, allocator_type> node_type;
939#endif
940
941    _LIBCPP_INLINE_VISIBILITY
942    unordered_multiset()
943        _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
944        {
945#if _LIBCPP_DEBUG_LEVEL >= 2
946            __get_db()->__insert_c(this);
947#endif
948        }
949    explicit unordered_multiset(size_type __n, const hasher& __hf = hasher(),
950                                const key_equal& __eql = key_equal());
951    unordered_multiset(size_type __n, const hasher& __hf,
952                       const key_equal& __eql, const allocator_type& __a);
953#if _LIBCPP_STD_VER > 11
954    inline _LIBCPP_INLINE_VISIBILITY
955    unordered_multiset(size_type __n, const allocator_type& __a)
956        : unordered_multiset(__n, hasher(), key_equal(), __a) {}
957    inline _LIBCPP_INLINE_VISIBILITY
958    unordered_multiset(size_type __n, const hasher& __hf, const allocator_type& __a)
959        : unordered_multiset(__n, __hf, key_equal(), __a) {}
960#endif
961    template <class _InputIterator>
962        unordered_multiset(_InputIterator __first, _InputIterator __last);
963    template <class _InputIterator>
964        unordered_multiset(_InputIterator __first, _InputIterator __last,
965                      size_type __n, const hasher& __hf = hasher(),
966                      const key_equal& __eql = key_equal());
967    template <class _InputIterator>
968        unordered_multiset(_InputIterator __first, _InputIterator __last,
969                      size_type __n , const hasher& __hf,
970                      const key_equal& __eql, const allocator_type& __a);
971#if _LIBCPP_STD_VER > 11
972    template <class _InputIterator>
973    inline _LIBCPP_INLINE_VISIBILITY
974    unordered_multiset(_InputIterator __first, _InputIterator __last,
975                       size_type __n, const allocator_type& __a)
976        : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a) {}
977    template <class _InputIterator>
978    inline _LIBCPP_INLINE_VISIBILITY
979    unordered_multiset(_InputIterator __first, _InputIterator __last,
980                       size_type __n, const hasher& __hf, const allocator_type& __a)
981        : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a) {}
982#endif
983    _LIBCPP_INLINE_VISIBILITY
984    explicit unordered_multiset(const allocator_type& __a);
985    unordered_multiset(const unordered_multiset& __u);
986    unordered_multiset(const unordered_multiset& __u, const allocator_type& __a);
987#ifndef _LIBCPP_CXX03_LANG
988    _LIBCPP_INLINE_VISIBILITY
989    unordered_multiset(unordered_multiset&& __u)
990        _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
991    unordered_multiset(unordered_multiset&& __u, const allocator_type& __a);
992    unordered_multiset(initializer_list<value_type> __il);
993    unordered_multiset(initializer_list<value_type> __il, size_type __n,
994                       const hasher& __hf = hasher(),
995                       const key_equal& __eql = key_equal());
996    unordered_multiset(initializer_list<value_type> __il, size_type __n,
997                       const hasher& __hf, const key_equal& __eql,
998                       const allocator_type& __a);
999#if _LIBCPP_STD_VER > 11
1000    inline _LIBCPP_INLINE_VISIBILITY
1001    unordered_multiset(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)
1002      : unordered_multiset(__il, __n, hasher(), key_equal(), __a) {}
1003    inline _LIBCPP_INLINE_VISIBILITY
1004    unordered_multiset(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a)
1005      : unordered_multiset(__il, __n, __hf, key_equal(), __a) {}
1006#endif
1007#endif  // _LIBCPP_CXX03_LANG
1008    // ~unordered_multiset() = default;
1009    _LIBCPP_INLINE_VISIBILITY
1010    unordered_multiset& operator=(const unordered_multiset& __u)
1011    {
1012        __table_ = __u.__table_;
1013        return *this;
1014    }
1015#ifndef _LIBCPP_CXX03_LANG
1016    _LIBCPP_INLINE_VISIBILITY
1017    unordered_multiset& operator=(unordered_multiset&& __u)
1018        _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
1019    unordered_multiset& operator=(initializer_list<value_type> __il);
1020#endif  // _LIBCPP_CXX03_LANG
1021
1022    _LIBCPP_INLINE_VISIBILITY
1023    allocator_type get_allocator() const _NOEXCEPT
1024        {return allocator_type(__table_.__node_alloc());}
1025
1026    _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
1027    bool      empty() const _NOEXCEPT {return __table_.size() == 0;}
1028    _LIBCPP_INLINE_VISIBILITY
1029    size_type size() const _NOEXCEPT  {return __table_.size();}
1030    _LIBCPP_INLINE_VISIBILITY
1031    size_type max_size() const _NOEXCEPT {return __table_.max_size();}
1032
1033    _LIBCPP_INLINE_VISIBILITY
1034    iterator       begin() _NOEXCEPT        {return __table_.begin();}
1035    _LIBCPP_INLINE_VISIBILITY
1036    iterator       end() _NOEXCEPT          {return __table_.end();}
1037    _LIBCPP_INLINE_VISIBILITY
1038    const_iterator begin()  const _NOEXCEPT {return __table_.begin();}
1039    _LIBCPP_INLINE_VISIBILITY
1040    const_iterator end()    const _NOEXCEPT {return __table_.end();}
1041    _LIBCPP_INLINE_VISIBILITY
1042    const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
1043    _LIBCPP_INLINE_VISIBILITY
1044    const_iterator cend()   const _NOEXCEPT {return __table_.end();}
1045
1046#ifndef _LIBCPP_CXX03_LANG
1047    template <class... _Args>
1048        _LIBCPP_INLINE_VISIBILITY
1049        iterator emplace(_Args&&... __args)
1050            {return __table_.__emplace_multi(_VSTD::forward<_Args>(__args)...);}
1051    template <class... _Args>
1052        _LIBCPP_INLINE_VISIBILITY
1053        iterator emplace_hint(const_iterator __p, _Args&&... __args)
1054            {return __table_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);}
1055
1056    _LIBCPP_INLINE_VISIBILITY
1057    iterator insert(value_type&& __x) {return __table_.__insert_multi(_VSTD::move(__x));}
1058    _LIBCPP_INLINE_VISIBILITY
1059    iterator insert(const_iterator __p, value_type&& __x)
1060        {return __table_.__insert_multi(__p, _VSTD::move(__x));}
1061    _LIBCPP_INLINE_VISIBILITY
1062    void insert(initializer_list<value_type> __il)
1063        {insert(__il.begin(), __il.end());}
1064#endif  // _LIBCPP_CXX03_LANG
1065
1066    _LIBCPP_INLINE_VISIBILITY
1067    iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
1068
1069    _LIBCPP_INLINE_VISIBILITY
1070    iterator insert(const_iterator __p, const value_type& __x)
1071        {return __table_.__insert_multi(__p, __x);}
1072
1073    template <class _InputIterator>
1074        _LIBCPP_INLINE_VISIBILITY
1075        void insert(_InputIterator __first, _InputIterator __last);
1076
1077#if _LIBCPP_STD_VER > 14
1078    _LIBCPP_INLINE_VISIBILITY
1079    iterator insert(node_type&& __nh)
1080    {
1081        _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
1082            "node_type with incompatible allocator passed to unordered_multiset::insert()");
1083        return __table_.template __node_handle_insert_multi<node_type>(
1084            _VSTD::move(__nh));
1085    }
1086    _LIBCPP_INLINE_VISIBILITY
1087    iterator insert(const_iterator __hint, node_type&& __nh)
1088    {
1089        _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
1090            "node_type with incompatible allocator passed to unordered_multiset::insert()");
1091        return __table_.template __node_handle_insert_multi<node_type>(
1092            __hint, _VSTD::move(__nh));
1093    }
1094    _LIBCPP_INLINE_VISIBILITY
1095    node_type extract(const_iterator __position)
1096    {
1097        return __table_.template __node_handle_extract<node_type>(
1098            __position);
1099    }
1100    _LIBCPP_INLINE_VISIBILITY
1101    node_type extract(key_type const& __key)
1102    {
1103        return __table_.template __node_handle_extract<node_type>(__key);
1104    }
1105#endif
1106
1107    _LIBCPP_INLINE_VISIBILITY
1108    iterator erase(const_iterator __p) {return __table_.erase(__p);}
1109    _LIBCPP_INLINE_VISIBILITY
1110    size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
1111    _LIBCPP_INLINE_VISIBILITY
1112    iterator erase(const_iterator __first, const_iterator __last)
1113        {return __table_.erase(__first, __last);}
1114    _LIBCPP_INLINE_VISIBILITY
1115    void clear() _NOEXCEPT {__table_.clear();}
1116
1117    _LIBCPP_INLINE_VISIBILITY
1118    void swap(unordered_multiset& __u)
1119        _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
1120        {__table_.swap(__u.__table_);}
1121
1122    _LIBCPP_INLINE_VISIBILITY
1123    hasher hash_function() const {return __table_.hash_function();}
1124    _LIBCPP_INLINE_VISIBILITY
1125    key_equal key_eq() const {return __table_.key_eq();}
1126
1127    _LIBCPP_INLINE_VISIBILITY
1128    iterator       find(const key_type& __k)       {return __table_.find(__k);}
1129    _LIBCPP_INLINE_VISIBILITY
1130    const_iterator find(const key_type& __k) const {return __table_.find(__k);}
1131    _LIBCPP_INLINE_VISIBILITY
1132    size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
1133    _LIBCPP_INLINE_VISIBILITY
1134    pair<iterator, iterator>             equal_range(const key_type& __k)
1135        {return __table_.__equal_range_multi(__k);}
1136    _LIBCPP_INLINE_VISIBILITY
1137    pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
1138        {return __table_.__equal_range_multi(__k);}
1139
1140    _LIBCPP_INLINE_VISIBILITY
1141    size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
1142    _LIBCPP_INLINE_VISIBILITY
1143    size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
1144
1145    _LIBCPP_INLINE_VISIBILITY
1146    size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);}
1147    _LIBCPP_INLINE_VISIBILITY
1148    size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
1149
1150    _LIBCPP_INLINE_VISIBILITY
1151    local_iterator       begin(size_type __n)        {return __table_.begin(__n);}
1152    _LIBCPP_INLINE_VISIBILITY
1153    local_iterator       end(size_type __n)          {return __table_.end(__n);}
1154    _LIBCPP_INLINE_VISIBILITY
1155    const_local_iterator begin(size_type __n) const  {return __table_.cbegin(__n);}
1156    _LIBCPP_INLINE_VISIBILITY
1157    const_local_iterator end(size_type __n) const    {return __table_.cend(__n);}
1158    _LIBCPP_INLINE_VISIBILITY
1159    const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
1160    _LIBCPP_INLINE_VISIBILITY
1161    const_local_iterator cend(size_type __n) const   {return __table_.cend(__n);}
1162
1163    _LIBCPP_INLINE_VISIBILITY
1164    float load_factor() const _NOEXCEPT {return __table_.load_factor();}
1165    _LIBCPP_INLINE_VISIBILITY
1166    float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
1167    _LIBCPP_INLINE_VISIBILITY
1168    void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
1169    _LIBCPP_INLINE_VISIBILITY
1170    void rehash(size_type __n) {__table_.rehash(__n);}
1171    _LIBCPP_INLINE_VISIBILITY
1172    void reserve(size_type __n) {__table_.reserve(__n);}
1173
1174#if _LIBCPP_DEBUG_LEVEL >= 2
1175
1176    bool __dereferenceable(const const_iterator* __i) const
1177        {return __table_.__dereferenceable(__i);}
1178    bool __decrementable(const const_iterator* __i) const
1179        {return __table_.__decrementable(__i);}
1180    bool __addable(const const_iterator* __i, ptrdiff_t __n) const
1181        {return __table_.__addable(__i, __n);}
1182    bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
1183        {return __table_.__addable(__i, __n);}
1184
1185#endif  // _LIBCPP_DEBUG_LEVEL >= 2
1186
1187};
1188
1189template <class _Value, class _Hash, class _Pred, class _Alloc>
1190unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1191        size_type __n, const hasher& __hf, const key_equal& __eql)
1192    : __table_(__hf, __eql)
1193{
1194#if _LIBCPP_DEBUG_LEVEL >= 2
1195    __get_db()->__insert_c(this);
1196#endif
1197    __table_.rehash(__n);
1198}
1199
1200template <class _Value, class _Hash, class _Pred, class _Alloc>
1201unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1202        size_type __n, const hasher& __hf, const key_equal& __eql,
1203        const allocator_type& __a)
1204    : __table_(__hf, __eql, __a)
1205{
1206#if _LIBCPP_DEBUG_LEVEL >= 2
1207    __get_db()->__insert_c(this);
1208#endif
1209    __table_.rehash(__n);
1210}
1211
1212template <class _Value, class _Hash, class _Pred, class _Alloc>
1213template <class _InputIterator>
1214unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1215        _InputIterator __first, _InputIterator __last)
1216{
1217#if _LIBCPP_DEBUG_LEVEL >= 2
1218    __get_db()->__insert_c(this);
1219#endif
1220    insert(__first, __last);
1221}
1222
1223template <class _Value, class _Hash, class _Pred, class _Alloc>
1224template <class _InputIterator>
1225unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1226        _InputIterator __first, _InputIterator __last, size_type __n,
1227        const hasher& __hf, const key_equal& __eql)
1228    : __table_(__hf, __eql)
1229{
1230#if _LIBCPP_DEBUG_LEVEL >= 2
1231    __get_db()->__insert_c(this);
1232#endif
1233    __table_.rehash(__n);
1234    insert(__first, __last);
1235}
1236
1237template <class _Value, class _Hash, class _Pred, class _Alloc>
1238template <class _InputIterator>
1239unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1240        _InputIterator __first, _InputIterator __last, size_type __n,
1241        const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1242    : __table_(__hf, __eql, __a)
1243{
1244#if _LIBCPP_DEBUG_LEVEL >= 2
1245    __get_db()->__insert_c(this);
1246#endif
1247    __table_.rehash(__n);
1248    insert(__first, __last);
1249}
1250
1251template <class _Value, class _Hash, class _Pred, class _Alloc>
1252inline
1253unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1254        const allocator_type& __a)
1255    : __table_(__a)
1256{
1257#if _LIBCPP_DEBUG_LEVEL >= 2
1258    __get_db()->__insert_c(this);
1259#endif
1260}
1261
1262template <class _Value, class _Hash, class _Pred, class _Alloc>
1263unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1264        const unordered_multiset& __u)
1265    : __table_(__u.__table_)
1266{
1267#if _LIBCPP_DEBUG_LEVEL >= 2
1268    __get_db()->__insert_c(this);
1269#endif
1270    __table_.rehash(__u.bucket_count());
1271    insert(__u.begin(), __u.end());
1272}
1273
1274template <class _Value, class _Hash, class _Pred, class _Alloc>
1275unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1276        const unordered_multiset& __u, const allocator_type& __a)
1277    : __table_(__u.__table_, __a)
1278{
1279#if _LIBCPP_DEBUG_LEVEL >= 2
1280    __get_db()->__insert_c(this);
1281#endif
1282    __table_.rehash(__u.bucket_count());
1283    insert(__u.begin(), __u.end());
1284}
1285
1286#ifndef _LIBCPP_CXX03_LANG
1287
1288template <class _Value, class _Hash, class _Pred, class _Alloc>
1289inline
1290unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1291        unordered_multiset&& __u)
1292    _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
1293    : __table_(_VSTD::move(__u.__table_))
1294{
1295#if _LIBCPP_DEBUG_LEVEL >= 2
1296    __get_db()->__insert_c(this);
1297    __get_db()->swap(this, &__u);
1298#endif
1299}
1300
1301template <class _Value, class _Hash, class _Pred, class _Alloc>
1302unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1303        unordered_multiset&& __u, const allocator_type& __a)
1304    : __table_(_VSTD::move(__u.__table_), __a)
1305{
1306#if _LIBCPP_DEBUG_LEVEL >= 2
1307    __get_db()->__insert_c(this);
1308#endif
1309    if (__a != __u.get_allocator())
1310    {
1311        iterator __i = __u.begin();
1312        while (__u.size() != 0)
1313            __table_.__insert_multi(_VSTD::move(__u.__table_.remove(__i++)->__value_));
1314    }
1315#if _LIBCPP_DEBUG_LEVEL >= 2
1316    else
1317        __get_db()->swap(this, &__u);
1318#endif
1319}
1320
1321template <class _Value, class _Hash, class _Pred, class _Alloc>
1322unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1323        initializer_list<value_type> __il)
1324{
1325#if _LIBCPP_DEBUG_LEVEL >= 2
1326    __get_db()->__insert_c(this);
1327#endif
1328    insert(__il.begin(), __il.end());
1329}
1330
1331template <class _Value, class _Hash, class _Pred, class _Alloc>
1332unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1333        initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1334        const key_equal& __eql)
1335    : __table_(__hf, __eql)
1336{
1337#if _LIBCPP_DEBUG_LEVEL >= 2
1338    __get_db()->__insert_c(this);
1339#endif
1340    __table_.rehash(__n);
1341    insert(__il.begin(), __il.end());
1342}
1343
1344template <class _Value, class _Hash, class _Pred, class _Alloc>
1345unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1346        initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1347        const key_equal& __eql, const allocator_type& __a)
1348    : __table_(__hf, __eql, __a)
1349{
1350#if _LIBCPP_DEBUG_LEVEL >= 2
1351    __get_db()->__insert_c(this);
1352#endif
1353    __table_.rehash(__n);
1354    insert(__il.begin(), __il.end());
1355}
1356
1357template <class _Value, class _Hash, class _Pred, class _Alloc>
1358inline
1359unordered_multiset<_Value, _Hash, _Pred, _Alloc>&
1360unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(
1361        unordered_multiset&& __u)
1362    _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
1363{
1364    __table_ = _VSTD::move(__u.__table_);
1365    return *this;
1366}
1367
1368template <class _Value, class _Hash, class _Pred, class _Alloc>
1369inline
1370unordered_multiset<_Value, _Hash, _Pred, _Alloc>&
1371unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(
1372        initializer_list<value_type> __il)
1373{
1374    __table_.__assign_multi(__il.begin(), __il.end());
1375    return *this;
1376}
1377
1378#endif  // _LIBCPP_CXX03_LANG
1379
1380template <class _Value, class _Hash, class _Pred, class _Alloc>
1381template <class _InputIterator>
1382inline
1383void
1384unordered_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
1385                                                         _InputIterator __last)
1386{
1387    for (; __first != __last; ++__first)
1388        __table_.__insert_multi(*__first);
1389}
1390
1391template <class _Value, class _Hash, class _Pred, class _Alloc>
1392inline _LIBCPP_INLINE_VISIBILITY
1393void
1394swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1395     unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1396    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1397{
1398    __x.swap(__y);
1399}
1400
1401template <class _Value, class _Hash, class _Pred, class _Alloc>
1402bool
1403operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1404           const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1405{
1406    if (__x.size() != __y.size())
1407        return false;
1408    typedef typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator
1409                                                                 const_iterator;
1410    typedef pair<const_iterator, const_iterator> _EqRng;
1411    for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;)
1412    {
1413        _EqRng __xeq = __x.equal_range(*__i);
1414        _EqRng __yeq = __y.equal_range(*__i);
1415        if (_VSTD::distance(__xeq.first, __xeq.second) !=
1416            _VSTD::distance(__yeq.first, __yeq.second) ||
1417                  !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first))
1418            return false;
1419        __i = __xeq.second;
1420    }
1421    return true;
1422}
1423
1424template <class _Value, class _Hash, class _Pred, class _Alloc>
1425inline _LIBCPP_INLINE_VISIBILITY
1426bool
1427operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1428           const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1429{
1430    return !(__x == __y);
1431}
1432
1433_LIBCPP_END_NAMESPACE_STD
1434
1435#endif  // _LIBCPP_UNORDERED_SET
1436