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