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