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