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