xref: /freebsd/contrib/llvm-project/libcxx/include/unordered_set (revision f976241773df2260e6170317080761d1c5814fe5)
1// -*- C++ -*-
2//===-------------------------- unordered_set -----------------------------===//
3//
4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5// See https://llvm.org/LICENSE.txt for license information.
6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7//
8//===----------------------------------------------------------------------===//
9
10#ifndef _LIBCPP_UNORDERED_SET
11#define _LIBCPP_UNORDERED_SET
12
13/*
14
15    unordered_set synopsis
16
17#include <initializer_list>
18
19namespace std
20{
21
22template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,
23          class Alloc = allocator<Value>>
24class unordered_set
25{
26public:
27    // types
28    typedef Value                                                      key_type;
29    typedef key_type                                                   value_type;
30    typedef Hash                                                       hasher;
31    typedef Pred                                                       key_equal;
32    typedef Alloc                                                      allocator_type;
33    typedef value_type&                                                reference;
34    typedef const value_type&                                          const_reference;
35    typedef typename allocator_traits<allocator_type>::pointer         pointer;
36    typedef typename allocator_traits<allocator_type>::const_pointer   const_pointer;
37    typedef typename allocator_traits<allocator_type>::size_type       size_type;
38    typedef typename allocator_traits<allocator_type>::difference_type difference_type;
39
40    typedef /unspecified/ iterator;
41    typedef /unspecified/ const_iterator;
42    typedef /unspecified/ local_iterator;
43    typedef /unspecified/ const_local_iterator;
44
45    typedef unspecified node_type unspecified;                            // C++17
46    typedef INSERT_RETURN_TYPE<iterator, node_type> insert_return_type;   // C++17
47
48    unordered_set()
49        noexcept(
50            is_nothrow_default_constructible<hasher>::value &&
51            is_nothrow_default_constructible<key_equal>::value &&
52            is_nothrow_default_constructible<allocator_type>::value);
53    explicit unordered_set(size_type n, const hasher& hf = hasher(),
54                           const key_equal& eql = key_equal(),
55                           const allocator_type& a = allocator_type());
56    template <class InputIterator>
57        unordered_set(InputIterator f, InputIterator l,
58                      size_type n = 0, const hasher& hf = hasher(),
59                      const key_equal& eql = key_equal(),
60                      const allocator_type& a = allocator_type());
61    explicit unordered_set(const allocator_type&);
62    unordered_set(const unordered_set&);
63    unordered_set(const unordered_set&, const Allocator&);
64    unordered_set(unordered_set&&)
65        noexcept(
66            is_nothrow_move_constructible<hasher>::value &&
67            is_nothrow_move_constructible<key_equal>::value &&
68            is_nothrow_move_constructible<allocator_type>::value);
69    unordered_set(unordered_set&&, const Allocator&);
70    unordered_set(initializer_list<value_type>, size_type n = 0,
71                  const hasher& hf = hasher(), const key_equal& eql = key_equal(),
72                  const allocator_type& a = allocator_type());
73    unordered_set(size_type n, const allocator_type& a); // C++14
74    unordered_set(size_type n, const hasher& hf, const allocator_type& a); // C++14
75    template <class InputIterator>
76      unordered_set(InputIterator f, InputIterator l, size_type n, const allocator_type& a); // C++14
77    template <class InputIterator>
78      unordered_set(InputIterator f, InputIterator l, size_type n,
79                    const hasher& hf,  const allocator_type& a); // C++14
80    unordered_set(initializer_list<value_type> il, size_type n, const allocator_type& a); // C++14
81    unordered_set(initializer_list<value_type> il, size_type n,
82                  const hasher& hf,  const allocator_type& a); // C++14
83    ~unordered_set();
84    unordered_set& operator=(const unordered_set&);
85    unordered_set& operator=(unordered_set&&)
86        noexcept(
87            allocator_type::propagate_on_container_move_assignment::value &&
88            is_nothrow_move_assignable<allocator_type>::value &&
89            is_nothrow_move_assignable<hasher>::value &&
90            is_nothrow_move_assignable<key_equal>::value);
91    unordered_set& operator=(initializer_list<value_type>);
92
93    allocator_type get_allocator() const noexcept;
94
95    bool      empty() const noexcept;
96    size_type size() const noexcept;
97    size_type max_size() const noexcept;
98
99    iterator       begin() noexcept;
100    iterator       end() noexcept;
101    const_iterator begin()  const noexcept;
102    const_iterator end()    const noexcept;
103    const_iterator cbegin() const noexcept;
104    const_iterator cend()   const noexcept;
105
106    template <class... Args>
107        pair<iterator, bool> emplace(Args&&... args);
108    template <class... Args>
109        iterator emplace_hint(const_iterator position, Args&&... args);
110    pair<iterator, bool> insert(const value_type& obj);
111    pair<iterator, bool> insert(value_type&& obj);
112    iterator insert(const_iterator hint, const value_type& obj);
113    iterator insert(const_iterator hint, value_type&& obj);
114    template <class InputIterator>
115        void insert(InputIterator first, InputIterator last);
116    void insert(initializer_list<value_type>);
117
118    node_type extract(const_iterator position);                       // C++17
119    node_type extract(const key_type& x);                             // C++17
120    insert_return_type insert(node_type&& nh);                        // C++17
121    iterator           insert(const_iterator hint, node_type&& nh);   // C++17
122
123    iterator erase(const_iterator position);
124    iterator erase(iterator position);  // C++14
125    size_type erase(const key_type& k);
126    iterator erase(const_iterator first, const_iterator last);
127    void clear() noexcept;
128
129    template<class H2, class P2>
130      void merge(unordered_set<Key, H2, P2, Allocator>& source);         // C++17
131    template<class H2, class P2>
132      void merge(unordered_set<Key, H2, P2, Allocator>&& source);        // C++17
133    template<class H2, class P2>
134      void merge(unordered_multiset<Key, H2, P2, Allocator>& source);    // C++17
135    template<class H2, class P2>
136      void merge(unordered_multiset<Key, H2, P2, Allocator>&& source);   // C++17
137
138    void swap(unordered_set&)
139       noexcept(allocator_traits<Allocator>::is_always_equal::value &&
140                 noexcept(swap(declval<hasher&>(), declval<hasher&>())) &&
141                 noexcept(swap(declval<key_equal&>(), declval<key_equal&>()))); // C++17
142
143    hasher hash_function() const;
144    key_equal key_eq() const;
145
146    iterator       find(const key_type& k);
147    const_iterator find(const key_type& k) const;
148    size_type count(const key_type& k) const;
149    bool contains(const key_type& k) const; // C++20
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    bool contains(const key_type& k) const; // C++20
315    pair<iterator, iterator>             equal_range(const key_type& k);
316    pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
317
318    size_type bucket_count() const noexcept;
319    size_type max_bucket_count() const noexcept;
320
321    size_type bucket_size(size_type n) const;
322    size_type bucket(const key_type& k) const;
323
324    local_iterator       begin(size_type n);
325    local_iterator       end(size_type n);
326    const_local_iterator begin(size_type n) const;
327    const_local_iterator end(size_type n) const;
328    const_local_iterator cbegin(size_type n) const;
329    const_local_iterator cend(size_type n) const;
330
331    float load_factor() const noexcept;
332    float max_load_factor() const noexcept;
333    void max_load_factor(float z);
334    void rehash(size_type n);
335    void reserve(size_type n);
336};
337
338template <class Value, class Hash, class Pred, class Alloc>
339    void swap(unordered_multiset<Value, Hash, Pred, Alloc>& x,
340              unordered_multiset<Value, Hash, Pred, Alloc>& y)
341              noexcept(noexcept(x.swap(y)));
342
343template <class K, class T, class H, class P, class A, class Predicate>
344    void erase_if(unordered_set<K, T, H, P, A>& c, Predicate pred);       // C++20
345
346template <class K, class T, class H, class P, class A, class Predicate>
347    void erase_if(unordered_multiset<K, T, H, P, A>& c, Predicate pred);  // C++20
348
349
350template <class Value, class Hash, class Pred, class Alloc>
351    bool
352    operator==(const unordered_multiset<Value, Hash, Pred, Alloc>& x,
353               const unordered_multiset<Value, Hash, Pred, Alloc>& y);
354
355template <class Value, class Hash, class Pred, class Alloc>
356    bool
357    operator!=(const unordered_multiset<Value, Hash, Pred, Alloc>& x,
358               const unordered_multiset<Value, Hash, Pred, Alloc>& y);
359}  // std
360
361*/
362
363#include <__config>
364#include <__hash_table>
365#include <__node_handle>
366#include <functional>
367#include <version>
368
369#include <__debug>
370
371#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
372#pragma GCC system_header
373#endif
374
375_LIBCPP_BEGIN_NAMESPACE_STD
376
377template <class _Value, class _Hash, class _Pred, class _Alloc>
378class unordered_multiset;
379
380template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>,
381          class _Alloc = allocator<_Value> >
382class _LIBCPP_TEMPLATE_VIS unordered_set
383{
384public:
385    // types
386    typedef _Value                                                     key_type;
387    typedef key_type                                                   value_type;
388    typedef typename __identity<_Hash>::type                           hasher;
389    typedef typename __identity<_Pred>::type                           key_equal;
390    typedef typename __identity<_Alloc>::type                          allocator_type;
391    typedef value_type&                                                reference;
392    typedef const value_type&                                          const_reference;
393    static_assert((is_same<value_type, typename allocator_type::value_type>::value),
394                  "Invalid allocator::value_type");
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    _LIBCPP_INLINE_VISIBILITY
491    ~unordered_set() {
492        static_assert(sizeof(__diagnose_unordered_container_requirements<_Value, _Hash, _Pred>(0)), "");
493    }
494
495    _LIBCPP_INLINE_VISIBILITY
496    unordered_set& operator=(const unordered_set& __u)
497    {
498        __table_ = __u.__table_;
499        return *this;
500    }
501#ifndef _LIBCPP_CXX03_LANG
502    _LIBCPP_INLINE_VISIBILITY
503    unordered_set& operator=(unordered_set&& __u)
504        _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
505    _LIBCPP_INLINE_VISIBILITY
506    unordered_set& operator=(initializer_list<value_type> __il);
507#endif  // _LIBCPP_CXX03_LANG
508
509    _LIBCPP_INLINE_VISIBILITY
510    allocator_type get_allocator() const _NOEXCEPT
511        {return allocator_type(__table_.__node_alloc());}
512
513    _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
514    bool      empty() const _NOEXCEPT {return __table_.size() == 0;}
515    _LIBCPP_INLINE_VISIBILITY
516    size_type size() const _NOEXCEPT  {return __table_.size();}
517    _LIBCPP_INLINE_VISIBILITY
518    size_type max_size() const _NOEXCEPT {return __table_.max_size();}
519
520    _LIBCPP_INLINE_VISIBILITY
521    iterator       begin() _NOEXCEPT        {return __table_.begin();}
522    _LIBCPP_INLINE_VISIBILITY
523    iterator       end() _NOEXCEPT          {return __table_.end();}
524    _LIBCPP_INLINE_VISIBILITY
525    const_iterator begin()  const _NOEXCEPT {return __table_.begin();}
526    _LIBCPP_INLINE_VISIBILITY
527    const_iterator end()    const _NOEXCEPT {return __table_.end();}
528    _LIBCPP_INLINE_VISIBILITY
529    const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
530    _LIBCPP_INLINE_VISIBILITY
531    const_iterator cend()   const _NOEXCEPT {return __table_.end();}
532
533#ifndef _LIBCPP_CXX03_LANG
534    template <class... _Args>
535        _LIBCPP_INLINE_VISIBILITY
536        pair<iterator, bool> emplace(_Args&&... __args)
537            {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...);}
538    template <class... _Args>
539        _LIBCPP_INLINE_VISIBILITY
540#if _LIBCPP_DEBUG_LEVEL >= 2
541        iterator emplace_hint(const_iterator __p, _Args&&... __args)
542        {
543            _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
544                "unordered_set::emplace_hint(const_iterator, args...) called with an iterator not"
545                " referring to this unordered_set");
546            return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first;
547        }
548#else
549        iterator emplace_hint(const_iterator, _Args&&... __args)
550            {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first;}
551#endif
552
553    _LIBCPP_INLINE_VISIBILITY
554    pair<iterator, bool> insert(value_type&& __x)
555        {return __table_.__insert_unique(_VSTD::move(__x));}
556    _LIBCPP_INLINE_VISIBILITY
557#if _LIBCPP_DEBUG_LEVEL >= 2
558    iterator insert(const_iterator __p, value_type&& __x)
559        {
560            _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
561                "unordered_set::insert(const_iterator, value_type&&) called with an iterator not"
562                " referring to this unordered_set");
563            return insert(_VSTD::move(__x)).first;
564        }
565#else
566    iterator insert(const_iterator, value_type&& __x)
567        {return insert(_VSTD::move(__x)).first;}
568#endif
569    _LIBCPP_INLINE_VISIBILITY
570    void insert(initializer_list<value_type> __il)
571        {insert(__il.begin(), __il.end());}
572#endif  // _LIBCPP_CXX03_LANG
573    _LIBCPP_INLINE_VISIBILITY
574    pair<iterator, bool> insert(const value_type& __x)
575        {return __table_.__insert_unique(__x);}
576
577    _LIBCPP_INLINE_VISIBILITY
578#if _LIBCPP_DEBUG_LEVEL >= 2
579    iterator insert(const_iterator __p, const value_type& __x)
580        {
581            _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
582                "unordered_set::insert(const_iterator, const value_type&) called with an iterator not"
583                " referring to this unordered_set");
584            return insert(__x).first;
585        }
586#else
587    iterator insert(const_iterator, const value_type& __x)
588        {return insert(__x).first;}
589#endif
590    template <class _InputIterator>
591        _LIBCPP_INLINE_VISIBILITY
592        void insert(_InputIterator __first, _InputIterator __last);
593
594    _LIBCPP_INLINE_VISIBILITY
595    iterator erase(const_iterator __p) {return __table_.erase(__p);}
596    _LIBCPP_INLINE_VISIBILITY
597    size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
598    _LIBCPP_INLINE_VISIBILITY
599    iterator erase(const_iterator __first, const_iterator __last)
600        {return __table_.erase(__first, __last);}
601    _LIBCPP_INLINE_VISIBILITY
602    void clear() _NOEXCEPT {__table_.clear();}
603
604#if _LIBCPP_STD_VER > 14
605    _LIBCPP_INLINE_VISIBILITY
606    insert_return_type insert(node_type&& __nh)
607    {
608        _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
609            "node_type with incompatible allocator passed to unordered_set::insert()");
610        return __table_.template __node_handle_insert_unique<
611            node_type, insert_return_type>(_VSTD::move(__nh));
612    }
613    _LIBCPP_INLINE_VISIBILITY
614    iterator insert(const_iterator __h, node_type&& __nh)
615    {
616        _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
617            "node_type with incompatible allocator passed to unordered_set::insert()");
618        return __table_.template __node_handle_insert_unique<node_type>(
619            __h, _VSTD::move(__nh));
620    }
621    _LIBCPP_INLINE_VISIBILITY
622    node_type extract(key_type const& __key)
623    {
624        return __table_.template __node_handle_extract<node_type>(__key);
625    }
626    _LIBCPP_INLINE_VISIBILITY
627    node_type extract(const_iterator __it)
628    {
629        return __table_.template __node_handle_extract<node_type>(__it);
630    }
631
632    template<class _H2, class _P2>
633    _LIBCPP_INLINE_VISIBILITY
634    void merge(unordered_set<key_type, _H2, _P2, allocator_type>& __source)
635    {
636        _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
637                       "merging container with incompatible allocator");
638        __table_.__node_handle_merge_unique(__source.__table_);
639    }
640    template<class _H2, class _P2>
641    _LIBCPP_INLINE_VISIBILITY
642    void merge(unordered_set<key_type, _H2, _P2, allocator_type>&& __source)
643    {
644        _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
645                       "merging container with incompatible allocator");
646        __table_.__node_handle_merge_unique(__source.__table_);
647    }
648    template<class _H2, class _P2>
649    _LIBCPP_INLINE_VISIBILITY
650    void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>& __source)
651    {
652        _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
653                       "merging container with incompatible allocator");
654        __table_.__node_handle_merge_unique(__source.__table_);
655    }
656    template<class _H2, class _P2>
657    _LIBCPP_INLINE_VISIBILITY
658    void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>&& __source)
659    {
660        _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
661                       "merging container with incompatible allocator");
662        __table_.__node_handle_merge_unique(__source.__table_);
663    }
664#endif
665
666    _LIBCPP_INLINE_VISIBILITY
667    void swap(unordered_set& __u)
668        _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
669        {__table_.swap(__u.__table_);}
670
671    _LIBCPP_INLINE_VISIBILITY
672    hasher hash_function() const {return __table_.hash_function();}
673    _LIBCPP_INLINE_VISIBILITY
674    key_equal key_eq() const {return __table_.key_eq();}
675
676    _LIBCPP_INLINE_VISIBILITY
677    iterator       find(const key_type& __k)       {return __table_.find(__k);}
678    _LIBCPP_INLINE_VISIBILITY
679    const_iterator find(const key_type& __k) const {return __table_.find(__k);}
680    _LIBCPP_INLINE_VISIBILITY
681    size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
682    #if _LIBCPP_STD_VER > 17
683        _LIBCPP_INLINE_VISIBILITY
684        bool contains(const key_type& __k) const {return find(__k) != end();}
685    #endif // _LIBCPP_STD_VER > 17
686    _LIBCPP_INLINE_VISIBILITY
687    pair<iterator, iterator>             equal_range(const key_type& __k)
688        {return __table_.__equal_range_unique(__k);}
689    _LIBCPP_INLINE_VISIBILITY
690    pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
691        {return __table_.__equal_range_unique(__k);}
692
693    _LIBCPP_INLINE_VISIBILITY
694    size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
695    _LIBCPP_INLINE_VISIBILITY
696    size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
697
698    _LIBCPP_INLINE_VISIBILITY
699    size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);}
700    _LIBCPP_INLINE_VISIBILITY
701    size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
702
703    _LIBCPP_INLINE_VISIBILITY
704    local_iterator       begin(size_type __n)        {return __table_.begin(__n);}
705    _LIBCPP_INLINE_VISIBILITY
706    local_iterator       end(size_type __n)          {return __table_.end(__n);}
707    _LIBCPP_INLINE_VISIBILITY
708    const_local_iterator begin(size_type __n) const  {return __table_.cbegin(__n);}
709    _LIBCPP_INLINE_VISIBILITY
710    const_local_iterator end(size_type __n) const    {return __table_.cend(__n);}
711    _LIBCPP_INLINE_VISIBILITY
712    const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
713    _LIBCPP_INLINE_VISIBILITY
714    const_local_iterator cend(size_type __n) const   {return __table_.cend(__n);}
715
716    _LIBCPP_INLINE_VISIBILITY
717    float load_factor() const _NOEXCEPT {return __table_.load_factor();}
718    _LIBCPP_INLINE_VISIBILITY
719    float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
720    _LIBCPP_INLINE_VISIBILITY
721    void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
722    _LIBCPP_INLINE_VISIBILITY
723    void rehash(size_type __n) {__table_.rehash(__n);}
724    _LIBCPP_INLINE_VISIBILITY
725    void reserve(size_type __n) {__table_.reserve(__n);}
726
727#if _LIBCPP_DEBUG_LEVEL >= 2
728
729    bool __dereferenceable(const const_iterator* __i) const
730        {return __table_.__dereferenceable(__i);}
731    bool __decrementable(const const_iterator* __i) const
732        {return __table_.__decrementable(__i);}
733    bool __addable(const const_iterator* __i, ptrdiff_t __n) const
734        {return __table_.__addable(__i, __n);}
735    bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
736        {return __table_.__addable(__i, __n);}
737
738#endif  // _LIBCPP_DEBUG_LEVEL >= 2
739
740};
741
742#ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES
743template<class _InputIterator,
744         class _Hash = hash<__iter_value_type<_InputIterator>>,
745         class _Pred = equal_to<__iter_value_type<_InputIterator>>,
746         class _Allocator = allocator<__iter_value_type<_InputIterator>>,
747         class = _EnableIf<!__is_allocator<_Hash>::value>,
748         class = _EnableIf<!is_integral<_Hash>::value>,
749         class = _EnableIf<!__is_allocator<_Pred>::value>,
750         class = _EnableIf<__is_allocator<_Allocator>::value>>
751unordered_set(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type = 0,
752              _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
753  -> unordered_set<__iter_value_type<_InputIterator>, _Hash, _Pred, _Allocator>;
754
755template<class _Tp, class _Hash = hash<_Tp>,
756         class _Pred = equal_to<_Tp>,
757         class _Allocator = allocator<_Tp>,
758         class = _EnableIf<!__is_allocator<_Hash>::value>,
759         class = _EnableIf<!is_integral<_Hash>::value>,
760         class = _EnableIf<!__is_allocator<_Pred>::value>,
761         class = _EnableIf<__is_allocator<_Allocator>::value>>
762unordered_set(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type = 0,
763              _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
764  -> unordered_set<_Tp, _Hash, _Pred, _Allocator>;
765
766template<class _InputIterator, class _Allocator,
767         class = _EnableIf<__is_allocator<_Allocator>::value>>
768unordered_set(_InputIterator, _InputIterator,
769              typename allocator_traits<_Allocator>::size_type, _Allocator)
770  -> unordered_set<__iter_value_type<_InputIterator>,
771                   hash<__iter_value_type<_InputIterator>>,
772                   equal_to<__iter_value_type<_InputIterator>>,
773                   _Allocator>;
774
775template<class _InputIterator, class _Hash, class _Allocator,
776         class = _EnableIf<!__is_allocator<_Hash>::value>,
777         class = _EnableIf<!is_integral<_Hash>::value>,
778         class = _EnableIf<__is_allocator<_Allocator>::value>>
779unordered_set(_InputIterator, _InputIterator,
780              typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
781  -> unordered_set<__iter_value_type<_InputIterator>, _Hash,
782                   equal_to<__iter_value_type<_InputIterator>>,
783                   _Allocator>;
784
785template<class _Tp, class _Allocator,
786         class = _EnableIf<__is_allocator<_Allocator>::value>>
787unordered_set(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Allocator)
788  -> unordered_set<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
789
790template<class _Tp, class _Hash, class _Allocator,
791         class = _EnableIf<!__is_allocator<_Hash>::value>,
792         class = _EnableIf<!is_integral<_Hash>::value>,
793         class = _EnableIf<__is_allocator<_Allocator>::value>>
794unordered_set(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
795  -> unordered_set<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
796#endif
797
798template <class _Value, class _Hash, class _Pred, class _Alloc>
799unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n,
800        const hasher& __hf, const key_equal& __eql)
801    : __table_(__hf, __eql)
802{
803#if _LIBCPP_DEBUG_LEVEL >= 2
804    __get_db()->__insert_c(this);
805#endif
806    __table_.rehash(__n);
807}
808
809template <class _Value, class _Hash, class _Pred, class _Alloc>
810unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n,
811        const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
812    : __table_(__hf, __eql, __a)
813{
814#if _LIBCPP_DEBUG_LEVEL >= 2
815    __get_db()->__insert_c(this);
816#endif
817    __table_.rehash(__n);
818}
819
820template <class _Value, class _Hash, class _Pred, class _Alloc>
821template <class _InputIterator>
822unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
823        _InputIterator __first, _InputIterator __last)
824{
825#if _LIBCPP_DEBUG_LEVEL >= 2
826    __get_db()->__insert_c(this);
827#endif
828    insert(__first, __last);
829}
830
831template <class _Value, class _Hash, class _Pred, class _Alloc>
832template <class _InputIterator>
833unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
834        _InputIterator __first, _InputIterator __last, size_type __n,
835        const hasher& __hf, const key_equal& __eql)
836    : __table_(__hf, __eql)
837{
838#if _LIBCPP_DEBUG_LEVEL >= 2
839    __get_db()->__insert_c(this);
840#endif
841    __table_.rehash(__n);
842    insert(__first, __last);
843}
844
845template <class _Value, class _Hash, class _Pred, class _Alloc>
846template <class _InputIterator>
847unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
848        _InputIterator __first, _InputIterator __last, size_type __n,
849        const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
850    : __table_(__hf, __eql, __a)
851{
852#if _LIBCPP_DEBUG_LEVEL >= 2
853    __get_db()->__insert_c(this);
854#endif
855    __table_.rehash(__n);
856    insert(__first, __last);
857}
858
859template <class _Value, class _Hash, class _Pred, class _Alloc>
860inline
861unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
862        const allocator_type& __a)
863    : __table_(__a)
864{
865#if _LIBCPP_DEBUG_LEVEL >= 2
866    __get_db()->__insert_c(this);
867#endif
868}
869
870template <class _Value, class _Hash, class _Pred, class _Alloc>
871unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
872        const unordered_set& __u)
873    : __table_(__u.__table_)
874{
875#if _LIBCPP_DEBUG_LEVEL >= 2
876    __get_db()->__insert_c(this);
877#endif
878    __table_.rehash(__u.bucket_count());
879    insert(__u.begin(), __u.end());
880}
881
882template <class _Value, class _Hash, class _Pred, class _Alloc>
883unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
884        const unordered_set& __u, const allocator_type& __a)
885    : __table_(__u.__table_, __a)
886{
887#if _LIBCPP_DEBUG_LEVEL >= 2
888    __get_db()->__insert_c(this);
889#endif
890    __table_.rehash(__u.bucket_count());
891    insert(__u.begin(), __u.end());
892}
893
894#ifndef _LIBCPP_CXX03_LANG
895
896template <class _Value, class _Hash, class _Pred, class _Alloc>
897inline
898unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
899        unordered_set&& __u)
900    _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
901    : __table_(_VSTD::move(__u.__table_))
902{
903#if _LIBCPP_DEBUG_LEVEL >= 2
904    __get_db()->__insert_c(this);
905    __get_db()->swap(this, &__u);
906#endif
907}
908
909template <class _Value, class _Hash, class _Pred, class _Alloc>
910unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
911        unordered_set&& __u, const allocator_type& __a)
912    : __table_(_VSTD::move(__u.__table_), __a)
913{
914#if _LIBCPP_DEBUG_LEVEL >= 2
915    __get_db()->__insert_c(this);
916#endif
917    if (__a != __u.get_allocator())
918    {
919        iterator __i = __u.begin();
920        while (__u.size() != 0)
921            __table_.__insert_unique(_VSTD::move(__u.__table_.remove(__i++)->__value_));
922    }
923#if _LIBCPP_DEBUG_LEVEL >= 2
924    else
925        __get_db()->swap(this, &__u);
926#endif
927}
928
929template <class _Value, class _Hash, class _Pred, class _Alloc>
930unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
931        initializer_list<value_type> __il)
932{
933#if _LIBCPP_DEBUG_LEVEL >= 2
934    __get_db()->__insert_c(this);
935#endif
936    insert(__il.begin(), __il.end());
937}
938
939template <class _Value, class _Hash, class _Pred, class _Alloc>
940unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
941        initializer_list<value_type> __il, size_type __n, const hasher& __hf,
942        const key_equal& __eql)
943    : __table_(__hf, __eql)
944{
945#if _LIBCPP_DEBUG_LEVEL >= 2
946    __get_db()->__insert_c(this);
947#endif
948    __table_.rehash(__n);
949    insert(__il.begin(), __il.end());
950}
951
952template <class _Value, class _Hash, class _Pred, class _Alloc>
953unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
954        initializer_list<value_type> __il, size_type __n, const hasher& __hf,
955        const key_equal& __eql, const allocator_type& __a)
956    : __table_(__hf, __eql, __a)
957{
958#if _LIBCPP_DEBUG_LEVEL >= 2
959    __get_db()->__insert_c(this);
960#endif
961    __table_.rehash(__n);
962    insert(__il.begin(), __il.end());
963}
964
965template <class _Value, class _Hash, class _Pred, class _Alloc>
966inline
967unordered_set<_Value, _Hash, _Pred, _Alloc>&
968unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(unordered_set&& __u)
969    _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
970{
971    __table_ = _VSTD::move(__u.__table_);
972    return *this;
973}
974
975template <class _Value, class _Hash, class _Pred, class _Alloc>
976inline
977unordered_set<_Value, _Hash, _Pred, _Alloc>&
978unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(
979        initializer_list<value_type> __il)
980{
981    __table_.__assign_unique(__il.begin(), __il.end());
982    return *this;
983}
984
985#endif  // _LIBCPP_CXX03_LANG
986
987template <class _Value, class _Hash, class _Pred, class _Alloc>
988template <class _InputIterator>
989inline
990void
991unordered_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
992                                                    _InputIterator __last)
993{
994    for (; __first != __last; ++__first)
995        __table_.__insert_unique(*__first);
996}
997
998template <class _Value, class _Hash, class _Pred, class _Alloc>
999inline _LIBCPP_INLINE_VISIBILITY
1000void
1001swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
1002     unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
1003    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1004{
1005    __x.swap(__y);
1006}
1007
1008#if _LIBCPP_STD_VER > 17
1009template <class _Value, class _Hash, class _Pred, class _Alloc, class _Predicate>
1010inline _LIBCPP_INLINE_VISIBILITY
1011void erase_if(unordered_set<_Value, _Hash, _Pred, _Alloc>& __c, _Predicate __pred)
1012{ __libcpp_erase_if_container(__c, __pred); }
1013#endif
1014
1015template <class _Value, class _Hash, class _Pred, class _Alloc>
1016bool
1017operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
1018           const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
1019{
1020    if (__x.size() != __y.size())
1021        return false;
1022    typedef typename unordered_set<_Value, _Hash, _Pred, _Alloc>::const_iterator
1023                                                                 const_iterator;
1024    for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();
1025            __i != __ex; ++__i)
1026    {
1027        const_iterator __j = __y.find(*__i);
1028        if (__j == __ey || !(*__i == *__j))
1029            return false;
1030    }
1031    return true;
1032}
1033
1034template <class _Value, class _Hash, class _Pred, class _Alloc>
1035inline _LIBCPP_INLINE_VISIBILITY
1036bool
1037operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
1038           const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
1039{
1040    return !(__x == __y);
1041}
1042
1043template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>,
1044          class _Alloc = allocator<_Value> >
1045class _LIBCPP_TEMPLATE_VIS unordered_multiset
1046{
1047public:
1048    // types
1049    typedef _Value                                                     key_type;
1050    typedef key_type                                                   value_type;
1051    typedef typename __identity<_Hash>::type                           hasher;
1052    typedef typename __identity<_Pred>::type                           key_equal;
1053    typedef typename __identity<_Alloc>::type                          allocator_type;
1054    typedef value_type&                                                reference;
1055    typedef const value_type&                                          const_reference;
1056    static_assert((is_same<value_type, typename allocator_type::value_type>::value),
1057                  "Invalid allocator::value_type");
1058
1059private:
1060    typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
1061
1062    __table __table_;
1063
1064public:
1065    typedef typename __table::pointer         pointer;
1066    typedef typename __table::const_pointer   const_pointer;
1067    typedef typename __table::size_type       size_type;
1068    typedef typename __table::difference_type difference_type;
1069
1070    typedef typename __table::const_iterator       iterator;
1071    typedef typename __table::const_iterator       const_iterator;
1072    typedef typename __table::const_local_iterator local_iterator;
1073    typedef typename __table::const_local_iterator const_local_iterator;
1074
1075#if _LIBCPP_STD_VER > 14
1076    typedef __set_node_handle<typename __table::__node, allocator_type> node_type;
1077#endif
1078
1079    template <class _Value2, class _Hash2, class _Pred2, class _Alloc2>
1080        friend class _LIBCPP_TEMPLATE_VIS unordered_set;
1081    template <class _Value2, class _Hash2, class _Pred2, class _Alloc2>
1082        friend class _LIBCPP_TEMPLATE_VIS unordered_multiset;
1083
1084    _LIBCPP_INLINE_VISIBILITY
1085    unordered_multiset()
1086        _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
1087        {
1088#if _LIBCPP_DEBUG_LEVEL >= 2
1089            __get_db()->__insert_c(this);
1090#endif
1091        }
1092    explicit unordered_multiset(size_type __n, const hasher& __hf = hasher(),
1093                                const key_equal& __eql = key_equal());
1094    unordered_multiset(size_type __n, const hasher& __hf,
1095                       const key_equal& __eql, const allocator_type& __a);
1096#if _LIBCPP_STD_VER > 11
1097    inline _LIBCPP_INLINE_VISIBILITY
1098    unordered_multiset(size_type __n, const allocator_type& __a)
1099        : unordered_multiset(__n, hasher(), key_equal(), __a) {}
1100    inline _LIBCPP_INLINE_VISIBILITY
1101    unordered_multiset(size_type __n, const hasher& __hf, const allocator_type& __a)
1102        : unordered_multiset(__n, __hf, key_equal(), __a) {}
1103#endif
1104    template <class _InputIterator>
1105        unordered_multiset(_InputIterator __first, _InputIterator __last);
1106    template <class _InputIterator>
1107        unordered_multiset(_InputIterator __first, _InputIterator __last,
1108                      size_type __n, const hasher& __hf = hasher(),
1109                      const key_equal& __eql = key_equal());
1110    template <class _InputIterator>
1111        unordered_multiset(_InputIterator __first, _InputIterator __last,
1112                      size_type __n , const hasher& __hf,
1113                      const key_equal& __eql, const allocator_type& __a);
1114#if _LIBCPP_STD_VER > 11
1115    template <class _InputIterator>
1116    inline _LIBCPP_INLINE_VISIBILITY
1117    unordered_multiset(_InputIterator __first, _InputIterator __last,
1118                       size_type __n, const allocator_type& __a)
1119        : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a) {}
1120    template <class _InputIterator>
1121    inline _LIBCPP_INLINE_VISIBILITY
1122    unordered_multiset(_InputIterator __first, _InputIterator __last,
1123                       size_type __n, const hasher& __hf, const allocator_type& __a)
1124        : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a) {}
1125#endif
1126    _LIBCPP_INLINE_VISIBILITY
1127    explicit unordered_multiset(const allocator_type& __a);
1128    unordered_multiset(const unordered_multiset& __u);
1129    unordered_multiset(const unordered_multiset& __u, const allocator_type& __a);
1130#ifndef _LIBCPP_CXX03_LANG
1131    _LIBCPP_INLINE_VISIBILITY
1132    unordered_multiset(unordered_multiset&& __u)
1133        _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
1134    unordered_multiset(unordered_multiset&& __u, const allocator_type& __a);
1135    unordered_multiset(initializer_list<value_type> __il);
1136    unordered_multiset(initializer_list<value_type> __il, size_type __n,
1137                       const hasher& __hf = hasher(),
1138                       const key_equal& __eql = key_equal());
1139    unordered_multiset(initializer_list<value_type> __il, size_type __n,
1140                       const hasher& __hf, const key_equal& __eql,
1141                       const allocator_type& __a);
1142#if _LIBCPP_STD_VER > 11
1143    inline _LIBCPP_INLINE_VISIBILITY
1144    unordered_multiset(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)
1145      : unordered_multiset(__il, __n, hasher(), key_equal(), __a) {}
1146    inline _LIBCPP_INLINE_VISIBILITY
1147    unordered_multiset(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a)
1148      : unordered_multiset(__il, __n, __hf, key_equal(), __a) {}
1149#endif
1150#endif  // _LIBCPP_CXX03_LANG
1151    _LIBCPP_INLINE_VISIBILITY
1152    ~unordered_multiset() {
1153        static_assert(sizeof(__diagnose_unordered_container_requirements<_Value, _Hash, _Pred>(0)), "");
1154    }
1155
1156    _LIBCPP_INLINE_VISIBILITY
1157    unordered_multiset& operator=(const unordered_multiset& __u)
1158    {
1159        __table_ = __u.__table_;
1160        return *this;
1161    }
1162#ifndef _LIBCPP_CXX03_LANG
1163    _LIBCPP_INLINE_VISIBILITY
1164    unordered_multiset& operator=(unordered_multiset&& __u)
1165        _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
1166    unordered_multiset& operator=(initializer_list<value_type> __il);
1167#endif  // _LIBCPP_CXX03_LANG
1168
1169    _LIBCPP_INLINE_VISIBILITY
1170    allocator_type get_allocator() const _NOEXCEPT
1171        {return allocator_type(__table_.__node_alloc());}
1172
1173    _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
1174    bool      empty() const _NOEXCEPT {return __table_.size() == 0;}
1175    _LIBCPP_INLINE_VISIBILITY
1176    size_type size() const _NOEXCEPT  {return __table_.size();}
1177    _LIBCPP_INLINE_VISIBILITY
1178    size_type max_size() const _NOEXCEPT {return __table_.max_size();}
1179
1180    _LIBCPP_INLINE_VISIBILITY
1181    iterator       begin() _NOEXCEPT        {return __table_.begin();}
1182    _LIBCPP_INLINE_VISIBILITY
1183    iterator       end() _NOEXCEPT          {return __table_.end();}
1184    _LIBCPP_INLINE_VISIBILITY
1185    const_iterator begin()  const _NOEXCEPT {return __table_.begin();}
1186    _LIBCPP_INLINE_VISIBILITY
1187    const_iterator end()    const _NOEXCEPT {return __table_.end();}
1188    _LIBCPP_INLINE_VISIBILITY
1189    const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
1190    _LIBCPP_INLINE_VISIBILITY
1191    const_iterator cend()   const _NOEXCEPT {return __table_.end();}
1192
1193#ifndef _LIBCPP_CXX03_LANG
1194    template <class... _Args>
1195        _LIBCPP_INLINE_VISIBILITY
1196        iterator emplace(_Args&&... __args)
1197            {return __table_.__emplace_multi(_VSTD::forward<_Args>(__args)...);}
1198    template <class... _Args>
1199        _LIBCPP_INLINE_VISIBILITY
1200        iterator emplace_hint(const_iterator __p, _Args&&... __args)
1201            {return __table_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);}
1202
1203    _LIBCPP_INLINE_VISIBILITY
1204    iterator insert(value_type&& __x) {return __table_.__insert_multi(_VSTD::move(__x));}
1205    _LIBCPP_INLINE_VISIBILITY
1206    iterator insert(const_iterator __p, value_type&& __x)
1207        {return __table_.__insert_multi(__p, _VSTD::move(__x));}
1208    _LIBCPP_INLINE_VISIBILITY
1209    void insert(initializer_list<value_type> __il)
1210        {insert(__il.begin(), __il.end());}
1211#endif  // _LIBCPP_CXX03_LANG
1212
1213    _LIBCPP_INLINE_VISIBILITY
1214    iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
1215
1216    _LIBCPP_INLINE_VISIBILITY
1217    iterator insert(const_iterator __p, const value_type& __x)
1218        {return __table_.__insert_multi(__p, __x);}
1219
1220    template <class _InputIterator>
1221        _LIBCPP_INLINE_VISIBILITY
1222        void insert(_InputIterator __first, _InputIterator __last);
1223
1224#if _LIBCPP_STD_VER > 14
1225    _LIBCPP_INLINE_VISIBILITY
1226    iterator insert(node_type&& __nh)
1227    {
1228        _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
1229            "node_type with incompatible allocator passed to unordered_multiset::insert()");
1230        return __table_.template __node_handle_insert_multi<node_type>(
1231            _VSTD::move(__nh));
1232    }
1233    _LIBCPP_INLINE_VISIBILITY
1234    iterator insert(const_iterator __hint, node_type&& __nh)
1235    {
1236        _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
1237            "node_type with incompatible allocator passed to unordered_multiset::insert()");
1238        return __table_.template __node_handle_insert_multi<node_type>(
1239            __hint, _VSTD::move(__nh));
1240    }
1241    _LIBCPP_INLINE_VISIBILITY
1242    node_type extract(const_iterator __position)
1243    {
1244        return __table_.template __node_handle_extract<node_type>(
1245            __position);
1246    }
1247    _LIBCPP_INLINE_VISIBILITY
1248    node_type extract(key_type const& __key)
1249    {
1250        return __table_.template __node_handle_extract<node_type>(__key);
1251    }
1252
1253    template <class _H2, class _P2>
1254    _LIBCPP_INLINE_VISIBILITY
1255    void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>& __source)
1256    {
1257        _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1258                       "merging container with incompatible allocator");
1259        return __table_.__node_handle_merge_multi(__source.__table_);
1260    }
1261    template <class _H2, class _P2>
1262    _LIBCPP_INLINE_VISIBILITY
1263    void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>&& __source)
1264    {
1265        _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1266                       "merging container with incompatible allocator");
1267        return __table_.__node_handle_merge_multi(__source.__table_);
1268    }
1269    template <class _H2, class _P2>
1270    _LIBCPP_INLINE_VISIBILITY
1271    void merge(unordered_set<key_type, _H2, _P2, allocator_type>& __source)
1272    {
1273        _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1274                       "merging container with incompatible allocator");
1275        return __table_.__node_handle_merge_multi(__source.__table_);
1276    }
1277    template <class _H2, class _P2>
1278    _LIBCPP_INLINE_VISIBILITY
1279    void merge(unordered_set<key_type, _H2, _P2, allocator_type>&& __source)
1280    {
1281        _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1282                       "merging container with incompatible allocator");
1283        return __table_.__node_handle_merge_multi(__source.__table_);
1284    }
1285#endif
1286
1287    _LIBCPP_INLINE_VISIBILITY
1288    iterator erase(const_iterator __p) {return __table_.erase(__p);}
1289    _LIBCPP_INLINE_VISIBILITY
1290    size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
1291    _LIBCPP_INLINE_VISIBILITY
1292    iterator erase(const_iterator __first, const_iterator __last)
1293        {return __table_.erase(__first, __last);}
1294    _LIBCPP_INLINE_VISIBILITY
1295    void clear() _NOEXCEPT {__table_.clear();}
1296
1297    _LIBCPP_INLINE_VISIBILITY
1298    void swap(unordered_multiset& __u)
1299        _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
1300        {__table_.swap(__u.__table_);}
1301
1302    _LIBCPP_INLINE_VISIBILITY
1303    hasher hash_function() const {return __table_.hash_function();}
1304    _LIBCPP_INLINE_VISIBILITY
1305    key_equal key_eq() const {return __table_.key_eq();}
1306
1307    _LIBCPP_INLINE_VISIBILITY
1308    iterator       find(const key_type& __k)       {return __table_.find(__k);}
1309    _LIBCPP_INLINE_VISIBILITY
1310    const_iterator find(const key_type& __k) const {return __table_.find(__k);}
1311    _LIBCPP_INLINE_VISIBILITY
1312    size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
1313    #if _LIBCPP_STD_VER > 17
1314        _LIBCPP_INLINE_VISIBILITY
1315        bool contains(const key_type& __k) const {return find(__k) != end();}
1316    #endif // _LIBCPP_STD_VER > 17
1317    _LIBCPP_INLINE_VISIBILITY
1318    pair<iterator, iterator>             equal_range(const key_type& __k)
1319        {return __table_.__equal_range_multi(__k);}
1320    _LIBCPP_INLINE_VISIBILITY
1321    pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
1322        {return __table_.__equal_range_multi(__k);}
1323
1324    _LIBCPP_INLINE_VISIBILITY
1325    size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
1326    _LIBCPP_INLINE_VISIBILITY
1327    size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
1328
1329    _LIBCPP_INLINE_VISIBILITY
1330    size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);}
1331    _LIBCPP_INLINE_VISIBILITY
1332    size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
1333
1334    _LIBCPP_INLINE_VISIBILITY
1335    local_iterator       begin(size_type __n)        {return __table_.begin(__n);}
1336    _LIBCPP_INLINE_VISIBILITY
1337    local_iterator       end(size_type __n)          {return __table_.end(__n);}
1338    _LIBCPP_INLINE_VISIBILITY
1339    const_local_iterator begin(size_type __n) const  {return __table_.cbegin(__n);}
1340    _LIBCPP_INLINE_VISIBILITY
1341    const_local_iterator end(size_type __n) const    {return __table_.cend(__n);}
1342    _LIBCPP_INLINE_VISIBILITY
1343    const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
1344    _LIBCPP_INLINE_VISIBILITY
1345    const_local_iterator cend(size_type __n) const   {return __table_.cend(__n);}
1346
1347    _LIBCPP_INLINE_VISIBILITY
1348    float load_factor() const _NOEXCEPT {return __table_.load_factor();}
1349    _LIBCPP_INLINE_VISIBILITY
1350    float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
1351    _LIBCPP_INLINE_VISIBILITY
1352    void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
1353    _LIBCPP_INLINE_VISIBILITY
1354    void rehash(size_type __n) {__table_.rehash(__n);}
1355    _LIBCPP_INLINE_VISIBILITY
1356    void reserve(size_type __n) {__table_.reserve(__n);}
1357
1358#if _LIBCPP_DEBUG_LEVEL >= 2
1359
1360    bool __dereferenceable(const const_iterator* __i) const
1361        {return __table_.__dereferenceable(__i);}
1362    bool __decrementable(const const_iterator* __i) const
1363        {return __table_.__decrementable(__i);}
1364    bool __addable(const const_iterator* __i, ptrdiff_t __n) const
1365        {return __table_.__addable(__i, __n);}
1366    bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
1367        {return __table_.__addable(__i, __n);}
1368
1369#endif  // _LIBCPP_DEBUG_LEVEL >= 2
1370
1371};
1372
1373#ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES
1374template<class _InputIterator,
1375         class _Hash = hash<__iter_value_type<_InputIterator>>,
1376         class _Pred = equal_to<__iter_value_type<_InputIterator>>,
1377         class _Allocator = allocator<__iter_value_type<_InputIterator>>,
1378         class = _EnableIf<!__is_allocator<_Hash>::value>,
1379         class = _EnableIf<!is_integral<_Hash>::value>,
1380         class = _EnableIf<!__is_allocator<_Pred>::value>,
1381         class = _EnableIf<__is_allocator<_Allocator>::value>>
1382unordered_multiset(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type = 0,
1383              _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
1384  -> unordered_multiset<__iter_value_type<_InputIterator>, _Hash, _Pred, _Allocator>;
1385
1386template<class _Tp, class _Hash = hash<_Tp>,
1387         class _Pred = equal_to<_Tp>, class _Allocator = allocator<_Tp>,
1388         class = _EnableIf<!__is_allocator<_Hash>::value>,
1389         class = _EnableIf<!is_integral<_Hash>::value>,
1390         class = _EnableIf<!__is_allocator<_Pred>::value>,
1391         class = _EnableIf<__is_allocator<_Allocator>::value>>
1392unordered_multiset(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type = 0,
1393              _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
1394  -> unordered_multiset<_Tp, _Hash, _Pred, _Allocator>;
1395
1396template<class _InputIterator, class _Allocator,
1397         class = _EnableIf<__is_allocator<_Allocator>::value>>
1398unordered_multiset(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Allocator)
1399  -> unordered_multiset<__iter_value_type<_InputIterator>,
1400                   hash<__iter_value_type<_InputIterator>>,
1401                   equal_to<__iter_value_type<_InputIterator>>,
1402                   _Allocator>;
1403
1404template<class _InputIterator, class _Hash, class _Allocator,
1405         class = _EnableIf<!__is_allocator<_Hash>::value>,
1406         class = _EnableIf<!is_integral<_Hash>::value>,
1407         class = _EnableIf<__is_allocator<_Allocator>::value>>
1408unordered_multiset(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type,
1409              _Hash, _Allocator)
1410  -> unordered_multiset<__iter_value_type<_InputIterator>, _Hash,
1411                   equal_to<__iter_value_type<_InputIterator>>,
1412                   _Allocator>;
1413
1414template<class _Tp, class _Allocator,
1415         class = _EnableIf<__is_allocator<_Allocator>::value>>
1416unordered_multiset(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Allocator)
1417  -> unordered_multiset<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
1418
1419template<class _Tp, class _Hash, class _Allocator,
1420         class = _EnableIf<!__is_allocator<_Hash>::value>,
1421         class = _EnableIf<!is_integral<_Hash>::value>,
1422         class = _EnableIf<__is_allocator<_Allocator>::value>>
1423unordered_multiset(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
1424  -> unordered_multiset<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
1425#endif
1426
1427template <class _Value, class _Hash, class _Pred, class _Alloc>
1428unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1429        size_type __n, const hasher& __hf, const key_equal& __eql)
1430    : __table_(__hf, __eql)
1431{
1432#if _LIBCPP_DEBUG_LEVEL >= 2
1433    __get_db()->__insert_c(this);
1434#endif
1435    __table_.rehash(__n);
1436}
1437
1438template <class _Value, class _Hash, class _Pred, class _Alloc>
1439unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1440        size_type __n, const hasher& __hf, const key_equal& __eql,
1441        const allocator_type& __a)
1442    : __table_(__hf, __eql, __a)
1443{
1444#if _LIBCPP_DEBUG_LEVEL >= 2
1445    __get_db()->__insert_c(this);
1446#endif
1447    __table_.rehash(__n);
1448}
1449
1450template <class _Value, class _Hash, class _Pred, class _Alloc>
1451template <class _InputIterator>
1452unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1453        _InputIterator __first, _InputIterator __last)
1454{
1455#if _LIBCPP_DEBUG_LEVEL >= 2
1456    __get_db()->__insert_c(this);
1457#endif
1458    insert(__first, __last);
1459}
1460
1461template <class _Value, class _Hash, class _Pred, class _Alloc>
1462template <class _InputIterator>
1463unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1464        _InputIterator __first, _InputIterator __last, size_type __n,
1465        const hasher& __hf, const key_equal& __eql)
1466    : __table_(__hf, __eql)
1467{
1468#if _LIBCPP_DEBUG_LEVEL >= 2
1469    __get_db()->__insert_c(this);
1470#endif
1471    __table_.rehash(__n);
1472    insert(__first, __last);
1473}
1474
1475template <class _Value, class _Hash, class _Pred, class _Alloc>
1476template <class _InputIterator>
1477unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1478        _InputIterator __first, _InputIterator __last, size_type __n,
1479        const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1480    : __table_(__hf, __eql, __a)
1481{
1482#if _LIBCPP_DEBUG_LEVEL >= 2
1483    __get_db()->__insert_c(this);
1484#endif
1485    __table_.rehash(__n);
1486    insert(__first, __last);
1487}
1488
1489template <class _Value, class _Hash, class _Pred, class _Alloc>
1490inline
1491unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1492        const allocator_type& __a)
1493    : __table_(__a)
1494{
1495#if _LIBCPP_DEBUG_LEVEL >= 2
1496    __get_db()->__insert_c(this);
1497#endif
1498}
1499
1500template <class _Value, class _Hash, class _Pred, class _Alloc>
1501unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1502        const unordered_multiset& __u)
1503    : __table_(__u.__table_)
1504{
1505#if _LIBCPP_DEBUG_LEVEL >= 2
1506    __get_db()->__insert_c(this);
1507#endif
1508    __table_.rehash(__u.bucket_count());
1509    insert(__u.begin(), __u.end());
1510}
1511
1512template <class _Value, class _Hash, class _Pred, class _Alloc>
1513unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1514        const unordered_multiset& __u, const allocator_type& __a)
1515    : __table_(__u.__table_, __a)
1516{
1517#if _LIBCPP_DEBUG_LEVEL >= 2
1518    __get_db()->__insert_c(this);
1519#endif
1520    __table_.rehash(__u.bucket_count());
1521    insert(__u.begin(), __u.end());
1522}
1523
1524#ifndef _LIBCPP_CXX03_LANG
1525
1526template <class _Value, class _Hash, class _Pred, class _Alloc>
1527inline
1528unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1529        unordered_multiset&& __u)
1530    _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
1531    : __table_(_VSTD::move(__u.__table_))
1532{
1533#if _LIBCPP_DEBUG_LEVEL >= 2
1534    __get_db()->__insert_c(this);
1535    __get_db()->swap(this, &__u);
1536#endif
1537}
1538
1539template <class _Value, class _Hash, class _Pred, class _Alloc>
1540unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1541        unordered_multiset&& __u, const allocator_type& __a)
1542    : __table_(_VSTD::move(__u.__table_), __a)
1543{
1544#if _LIBCPP_DEBUG_LEVEL >= 2
1545    __get_db()->__insert_c(this);
1546#endif
1547    if (__a != __u.get_allocator())
1548    {
1549        iterator __i = __u.begin();
1550        while (__u.size() != 0)
1551            __table_.__insert_multi(_VSTD::move(__u.__table_.remove(__i++)->__value_));
1552    }
1553#if _LIBCPP_DEBUG_LEVEL >= 2
1554    else
1555        __get_db()->swap(this, &__u);
1556#endif
1557}
1558
1559template <class _Value, class _Hash, class _Pred, class _Alloc>
1560unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1561        initializer_list<value_type> __il)
1562{
1563#if _LIBCPP_DEBUG_LEVEL >= 2
1564    __get_db()->__insert_c(this);
1565#endif
1566    insert(__il.begin(), __il.end());
1567}
1568
1569template <class _Value, class _Hash, class _Pred, class _Alloc>
1570unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1571        initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1572        const key_equal& __eql)
1573    : __table_(__hf, __eql)
1574{
1575#if _LIBCPP_DEBUG_LEVEL >= 2
1576    __get_db()->__insert_c(this);
1577#endif
1578    __table_.rehash(__n);
1579    insert(__il.begin(), __il.end());
1580}
1581
1582template <class _Value, class _Hash, class _Pred, class _Alloc>
1583unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1584        initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1585        const key_equal& __eql, const allocator_type& __a)
1586    : __table_(__hf, __eql, __a)
1587{
1588#if _LIBCPP_DEBUG_LEVEL >= 2
1589    __get_db()->__insert_c(this);
1590#endif
1591    __table_.rehash(__n);
1592    insert(__il.begin(), __il.end());
1593}
1594
1595template <class _Value, class _Hash, class _Pred, class _Alloc>
1596inline
1597unordered_multiset<_Value, _Hash, _Pred, _Alloc>&
1598unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(
1599        unordered_multiset&& __u)
1600    _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
1601{
1602    __table_ = _VSTD::move(__u.__table_);
1603    return *this;
1604}
1605
1606template <class _Value, class _Hash, class _Pred, class _Alloc>
1607inline
1608unordered_multiset<_Value, _Hash, _Pred, _Alloc>&
1609unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(
1610        initializer_list<value_type> __il)
1611{
1612    __table_.__assign_multi(__il.begin(), __il.end());
1613    return *this;
1614}
1615
1616#endif  // _LIBCPP_CXX03_LANG
1617
1618template <class _Value, class _Hash, class _Pred, class _Alloc>
1619template <class _InputIterator>
1620inline
1621void
1622unordered_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
1623                                                         _InputIterator __last)
1624{
1625    for (; __first != __last; ++__first)
1626        __table_.__insert_multi(*__first);
1627}
1628
1629template <class _Value, class _Hash, class _Pred, class _Alloc>
1630inline _LIBCPP_INLINE_VISIBILITY
1631void
1632swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1633     unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1634    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1635{
1636    __x.swap(__y);
1637}
1638
1639#if _LIBCPP_STD_VER > 17
1640template <class _Value, class _Hash, class _Pred, class _Alloc, class _Predicate>
1641inline _LIBCPP_INLINE_VISIBILITY
1642void erase_if(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __c, _Predicate __pred)
1643{ __libcpp_erase_if_container(__c, __pred); }
1644#endif
1645
1646template <class _Value, class _Hash, class _Pred, class _Alloc>
1647bool
1648operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1649           const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1650{
1651    if (__x.size() != __y.size())
1652        return false;
1653    typedef typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator
1654                                                                 const_iterator;
1655    typedef pair<const_iterator, const_iterator> _EqRng;
1656    for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;)
1657    {
1658        _EqRng __xeq = __x.equal_range(*__i);
1659        _EqRng __yeq = __y.equal_range(*__i);
1660        if (_VSTD::distance(__xeq.first, __xeq.second) !=
1661            _VSTD::distance(__yeq.first, __yeq.second) ||
1662                  !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first))
1663            return false;
1664        __i = __xeq.second;
1665    }
1666    return true;
1667}
1668
1669template <class _Value, class _Hash, class _Pred, class _Alloc>
1670inline _LIBCPP_INLINE_VISIBILITY
1671bool
1672operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1673           const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1674{
1675    return !(__x == __y);
1676}
1677
1678_LIBCPP_END_NAMESPACE_STD
1679
1680#endif  // _LIBCPP_UNORDERED_SET
1681