unordered_set revision 278724 
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#include <__debug>
329
330#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
331#pragma GCC system_header
332#endif
333
334_LIBCPP_BEGIN_NAMESPACE_STD
335
336template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>,
337          class _Alloc = allocator<_Value> >
338class _LIBCPP_TYPE_VIS_ONLY unordered_set
339{
340public:
341    // types
342    typedef _Value                                                     key_type;
343    typedef key_type                                                   value_type;
344    typedef _Hash                                                      hasher;
345    typedef _Pred                                                      key_equal;
346    typedef _Alloc                                                     allocator_type;
347    typedef value_type&                                                reference;
348    typedef const value_type&                                          const_reference;
349    static_assert((is_same<value_type, typename allocator_type::value_type>::value),
350                  "Invalid allocator::value_type");
351
352private:
353    typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
354
355    __table __table_;
356
357public:
358    typedef typename __table::pointer         pointer;
359    typedef typename __table::const_pointer   const_pointer;
360    typedef typename __table::size_type       size_type;
361    typedef typename __table::difference_type difference_type;
362
363    typedef typename __table::const_iterator       iterator;
364    typedef typename __table::const_iterator       const_iterator;
365    typedef typename __table::const_local_iterator local_iterator;
366    typedef typename __table::const_local_iterator const_local_iterator;
367
368    _LIBCPP_INLINE_VISIBILITY
369    unordered_set()
370        _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
371        {
372#if _LIBCPP_DEBUG_LEVEL >= 2
373            __get_db()->__insert_c(this);
374#endif
375        }
376    explicit unordered_set(size_type __n, const hasher& __hf = hasher(),
377                           const key_equal& __eql = key_equal());
378#if _LIBCPP_STD_VER > 11
379    inline _LIBCPP_INLINE_VISIBILITY
380    unordered_set(size_type __n, const allocator_type& __a)
381        : unordered_set(__n, hasher(), key_equal(), __a) {}
382    inline _LIBCPP_INLINE_VISIBILITY
383    unordered_set(size_type __n, const hasher& __hf, const allocator_type& __a)
384        : unordered_set(__n, __hf, key_equal(), __a) {}
385#endif
386    unordered_set(size_type __n, const hasher& __hf, const key_equal& __eql,
387                  const allocator_type& __a);
388    template <class _InputIterator>
389        unordered_set(_InputIterator __first, _InputIterator __last);
390    template <class _InputIterator>
391        unordered_set(_InputIterator __first, _InputIterator __last,
392                      size_type __n, const hasher& __hf = hasher(),
393                      const key_equal& __eql = key_equal());
394    template <class _InputIterator>
395        unordered_set(_InputIterator __first, _InputIterator __last,
396                      size_type __n, const hasher& __hf, const key_equal& __eql,
397                      const allocator_type& __a);
398#if _LIBCPP_STD_VER > 11
399    template <class _InputIterator>
400    inline _LIBCPP_INLINE_VISIBILITY
401        unordered_set(_InputIterator __first, _InputIterator __last, 
402                    size_type __n, const allocator_type& __a)
403            : unordered_set(__first, __last, __n, hasher(), key_equal(), __a) {}
404    template <class _InputIterator>
405        unordered_set(_InputIterator __first, _InputIterator __last, 
406                      size_type __n, const hasher& __hf, const allocator_type& __a)
407            : unordered_set(__first, __last, __n, __hf, key_equal(), __a) {}
408#endif
409    explicit unordered_set(const allocator_type& __a);
410    unordered_set(const unordered_set& __u);
411    unordered_set(const unordered_set& __u, const allocator_type& __a);
412#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
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#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
417#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
418    unordered_set(initializer_list<value_type> __il);
419    unordered_set(initializer_list<value_type> __il, size_type __n,
420                  const hasher& __hf = hasher(),
421                  const key_equal& __eql = key_equal());
422    unordered_set(initializer_list<value_type> __il, size_type __n,
423                  const hasher& __hf, const key_equal& __eql,
424                  const allocator_type& __a);
425#if _LIBCPP_STD_VER > 11
426    inline _LIBCPP_INLINE_VISIBILITY
427    unordered_set(initializer_list<value_type> __il, size_type __n,
428                                                      const allocator_type& __a)
429        : unordered_set(__il, __n, hasher(), key_equal(), __a) {}
430    inline _LIBCPP_INLINE_VISIBILITY
431    unordered_set(initializer_list<value_type> __il, size_type __n, 
432                                  const hasher& __hf, const allocator_type& __a)
433        : unordered_set(__il, __n, __hf, key_equal(), __a) {}
434#endif
435#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
436    // ~unordered_set() = default;
437    _LIBCPP_INLINE_VISIBILITY
438    unordered_set& operator=(const unordered_set& __u)
439    {
440        __table_ = __u.__table_;
441        return *this;
442    }
443#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
444    unordered_set& operator=(unordered_set&& __u)
445        _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
446#endif
447#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
448    unordered_set& operator=(initializer_list<value_type> __il);
449#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
450
451    _LIBCPP_INLINE_VISIBILITY
452    allocator_type get_allocator() const _NOEXCEPT
453        {return allocator_type(__table_.__node_alloc());}
454
455    _LIBCPP_INLINE_VISIBILITY
456    bool      empty() const _NOEXCEPT {return __table_.size() == 0;}
457    _LIBCPP_INLINE_VISIBILITY
458    size_type size() const _NOEXCEPT  {return __table_.size();}
459    _LIBCPP_INLINE_VISIBILITY
460    size_type max_size() const _NOEXCEPT {return __table_.max_size();}
461
462    _LIBCPP_INLINE_VISIBILITY
463    iterator       begin() _NOEXCEPT        {return __table_.begin();}
464    _LIBCPP_INLINE_VISIBILITY
465    iterator       end() _NOEXCEPT          {return __table_.end();}
466    _LIBCPP_INLINE_VISIBILITY
467    const_iterator begin()  const _NOEXCEPT {return __table_.begin();}
468    _LIBCPP_INLINE_VISIBILITY
469    const_iterator end()    const _NOEXCEPT {return __table_.end();}
470    _LIBCPP_INLINE_VISIBILITY
471    const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
472    _LIBCPP_INLINE_VISIBILITY
473    const_iterator cend()   const _NOEXCEPT {return __table_.end();}
474
475#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
476    template <class... _Args>
477        _LIBCPP_INLINE_VISIBILITY
478        pair<iterator, bool> emplace(_Args&&... __args)
479            {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...);}
480    template <class... _Args>
481        _LIBCPP_INLINE_VISIBILITY
482#if _LIBCPP_DEBUG_LEVEL >= 2
483        iterator emplace_hint(const_iterator __p, _Args&&... __args)
484        {
485            _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
486                "unordered_set::emplace_hint(const_iterator, args...) called with an iterator not"
487                " referring to this unordered_set");
488            return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first;
489        }
490#else
491        iterator emplace_hint(const_iterator, _Args&&... __args)
492            {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first;}
493#endif
494#endif  // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
495    _LIBCPP_INLINE_VISIBILITY
496    pair<iterator, bool> insert(const value_type& __x)
497        {return __table_.__insert_unique(__x);}
498#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
499    _LIBCPP_INLINE_VISIBILITY
500    pair<iterator, bool> insert(value_type&& __x)
501        {return __table_.__insert_unique(_VSTD::move(__x));}
502#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
503    _LIBCPP_INLINE_VISIBILITY
504#if _LIBCPP_DEBUG_LEVEL >= 2
505    iterator insert(const_iterator __p, const value_type& __x)
506        {
507            _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
508                "unordered_set::insert(const_iterator, const value_type&) called with an iterator not"
509                " referring to this unordered_set");
510            return insert(__x).first;
511        }
512#else
513    iterator insert(const_iterator, const value_type& __x)
514        {return insert(__x).first;}
515#endif
516#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
517    _LIBCPP_INLINE_VISIBILITY
518#if _LIBCPP_DEBUG_LEVEL >= 2
519    iterator insert(const_iterator __p, value_type&& __x)
520        {
521            _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
522                "unordered_set::insert(const_iterator, value_type&&) called with an iterator not"
523                " referring to this unordered_set");
524            return insert(_VSTD::move(__x)).first;
525        }
526#else
527    iterator insert(const_iterator, value_type&& __x)
528        {return insert(_VSTD::move(__x)).first;}
529#endif
530#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
531    template <class _InputIterator>
532        void insert(_InputIterator __first, _InputIterator __last);
533#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
534    _LIBCPP_INLINE_VISIBILITY
535    void insert(initializer_list<value_type> __il)
536        {insert(__il.begin(), __il.end());}
537#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
538
539    _LIBCPP_INLINE_VISIBILITY
540    iterator erase(const_iterator __p) {return __table_.erase(__p);}
541    _LIBCPP_INLINE_VISIBILITY
542    size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
543    _LIBCPP_INLINE_VISIBILITY
544    iterator erase(const_iterator __first, const_iterator __last)
545        {return __table_.erase(__first, __last);}
546    _LIBCPP_INLINE_VISIBILITY
547    void clear() _NOEXCEPT {__table_.clear();}
548
549    _LIBCPP_INLINE_VISIBILITY
550    void swap(unordered_set& __u)
551        _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
552        {__table_.swap(__u.__table_);}
553
554    _LIBCPP_INLINE_VISIBILITY
555    hasher hash_function() const {return __table_.hash_function();}
556    _LIBCPP_INLINE_VISIBILITY
557    key_equal key_eq() const {return __table_.key_eq();}
558
559    _LIBCPP_INLINE_VISIBILITY
560    iterator       find(const key_type& __k)       {return __table_.find(__k);}
561    _LIBCPP_INLINE_VISIBILITY
562    const_iterator find(const key_type& __k) const {return __table_.find(__k);}
563    _LIBCPP_INLINE_VISIBILITY
564    size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
565    _LIBCPP_INLINE_VISIBILITY
566    pair<iterator, iterator>             equal_range(const key_type& __k)
567        {return __table_.__equal_range_unique(__k);}
568    _LIBCPP_INLINE_VISIBILITY
569    pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
570        {return __table_.__equal_range_unique(__k);}
571
572    _LIBCPP_INLINE_VISIBILITY
573    size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
574    _LIBCPP_INLINE_VISIBILITY
575    size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
576
577    _LIBCPP_INLINE_VISIBILITY
578    size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);}
579    _LIBCPP_INLINE_VISIBILITY
580    size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
581
582    _LIBCPP_INLINE_VISIBILITY
583    local_iterator       begin(size_type __n)        {return __table_.begin(__n);}
584    _LIBCPP_INLINE_VISIBILITY
585    local_iterator       end(size_type __n)          {return __table_.end(__n);}
586    _LIBCPP_INLINE_VISIBILITY
587    const_local_iterator begin(size_type __n) const  {return __table_.cbegin(__n);}
588    _LIBCPP_INLINE_VISIBILITY
589    const_local_iterator end(size_type __n) const    {return __table_.cend(__n);}
590    _LIBCPP_INLINE_VISIBILITY
591    const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
592    _LIBCPP_INLINE_VISIBILITY
593    const_local_iterator cend(size_type __n) const   {return __table_.cend(__n);}
594
595    _LIBCPP_INLINE_VISIBILITY
596    float load_factor() const _NOEXCEPT {return __table_.load_factor();}
597    _LIBCPP_INLINE_VISIBILITY
598    float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
599    _LIBCPP_INLINE_VISIBILITY
600    void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
601    _LIBCPP_INLINE_VISIBILITY
602    void rehash(size_type __n) {__table_.rehash(__n);}
603    _LIBCPP_INLINE_VISIBILITY
604    void reserve(size_type __n) {__table_.reserve(__n);}
605
606#if _LIBCPP_DEBUG_LEVEL >= 2
607
608    bool __dereferenceable(const const_iterator* __i) const
609        {return __table_.__dereferenceable(__i);}
610    bool __decrementable(const const_iterator* __i) const
611        {return __table_.__decrementable(__i);}
612    bool __addable(const const_iterator* __i, ptrdiff_t __n) const
613        {return __table_.__addable(__i, __n);}
614    bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
615        {return __table_.__addable(__i, __n);}
616
617#endif  // _LIBCPP_DEBUG_LEVEL >= 2
618
619};
620
621template <class _Value, class _Hash, class _Pred, class _Alloc>
622unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n,
623        const hasher& __hf, const key_equal& __eql)
624    : __table_(__hf, __eql)
625{
626#if _LIBCPP_DEBUG_LEVEL >= 2
627    __get_db()->__insert_c(this);
628#endif
629    __table_.rehash(__n);
630}
631
632template <class _Value, class _Hash, class _Pred, class _Alloc>
633unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n,
634        const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
635    : __table_(__hf, __eql, __a)
636{
637#if _LIBCPP_DEBUG_LEVEL >= 2
638    __get_db()->__insert_c(this);
639#endif
640    __table_.rehash(__n);
641}
642
643template <class _Value, class _Hash, class _Pred, class _Alloc>
644template <class _InputIterator>
645unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
646        _InputIterator __first, _InputIterator __last)
647{
648#if _LIBCPP_DEBUG_LEVEL >= 2
649    __get_db()->__insert_c(this);
650#endif
651    insert(__first, __last);
652}
653
654template <class _Value, class _Hash, class _Pred, class _Alloc>
655template <class _InputIterator>
656unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
657        _InputIterator __first, _InputIterator __last, size_type __n,
658        const hasher& __hf, const key_equal& __eql)
659    : __table_(__hf, __eql)
660{
661#if _LIBCPP_DEBUG_LEVEL >= 2
662    __get_db()->__insert_c(this);
663#endif
664    __table_.rehash(__n);
665    insert(__first, __last);
666}
667
668template <class _Value, class _Hash, class _Pred, class _Alloc>
669template <class _InputIterator>
670unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
671        _InputIterator __first, _InputIterator __last, size_type __n,
672        const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
673    : __table_(__hf, __eql, __a)
674{
675#if _LIBCPP_DEBUG_LEVEL >= 2
676    __get_db()->__insert_c(this);
677#endif
678    __table_.rehash(__n);
679    insert(__first, __last);
680}
681
682template <class _Value, class _Hash, class _Pred, class _Alloc>
683inline _LIBCPP_INLINE_VISIBILITY
684unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
685        const allocator_type& __a)
686    : __table_(__a)
687{
688#if _LIBCPP_DEBUG_LEVEL >= 2
689    __get_db()->__insert_c(this);
690#endif
691}
692
693template <class _Value, class _Hash, class _Pred, class _Alloc>
694unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
695        const unordered_set& __u)
696    : __table_(__u.__table_)
697{
698#if _LIBCPP_DEBUG_LEVEL >= 2
699    __get_db()->__insert_c(this);
700#endif
701    __table_.rehash(__u.bucket_count());
702    insert(__u.begin(), __u.end());
703}
704
705template <class _Value, class _Hash, class _Pred, class _Alloc>
706unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
707        const unordered_set& __u, const allocator_type& __a)
708    : __table_(__u.__table_, __a)
709{
710#if _LIBCPP_DEBUG_LEVEL >= 2
711    __get_db()->__insert_c(this);
712#endif
713    __table_.rehash(__u.bucket_count());
714    insert(__u.begin(), __u.end());
715}
716
717#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
718
719template <class _Value, class _Hash, class _Pred, class _Alloc>
720inline _LIBCPP_INLINE_VISIBILITY
721unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
722        unordered_set&& __u)
723    _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
724    : __table_(_VSTD::move(__u.__table_))
725{
726#if _LIBCPP_DEBUG_LEVEL >= 2
727    __get_db()->__insert_c(this);
728    __get_db()->swap(this, &__u);
729#endif
730}
731
732template <class _Value, class _Hash, class _Pred, class _Alloc>
733unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
734        unordered_set&& __u, const allocator_type& __a)
735    : __table_(_VSTD::move(__u.__table_), __a)
736{
737#if _LIBCPP_DEBUG_LEVEL >= 2
738    __get_db()->__insert_c(this);
739#endif
740    if (__a != __u.get_allocator())
741    {
742        iterator __i = __u.begin();
743        while (__u.size() != 0)
744            __table_.__insert_unique(_VSTD::move(__u.__table_.remove(__i++)->__value_));
745    }
746#if _LIBCPP_DEBUG_LEVEL >= 2
747    else
748        __get_db()->swap(this, &__u);
749#endif
750}
751
752#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
753
754#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
755
756template <class _Value, class _Hash, class _Pred, class _Alloc>
757unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
758        initializer_list<value_type> __il)
759{
760#if _LIBCPP_DEBUG_LEVEL >= 2
761    __get_db()->__insert_c(this);
762#endif
763    insert(__il.begin(), __il.end());
764}
765
766template <class _Value, class _Hash, class _Pred, class _Alloc>
767unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
768        initializer_list<value_type> __il, size_type __n, const hasher& __hf,
769        const key_equal& __eql)
770    : __table_(__hf, __eql)
771{
772#if _LIBCPP_DEBUG_LEVEL >= 2
773    __get_db()->__insert_c(this);
774#endif
775    __table_.rehash(__n);
776    insert(__il.begin(), __il.end());
777}
778
779template <class _Value, class _Hash, class _Pred, class _Alloc>
780unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
781        initializer_list<value_type> __il, size_type __n, const hasher& __hf,
782        const key_equal& __eql, const allocator_type& __a)
783    : __table_(__hf, __eql, __a)
784{
785#if _LIBCPP_DEBUG_LEVEL >= 2
786    __get_db()->__insert_c(this);
787#endif
788    __table_.rehash(__n);
789    insert(__il.begin(), __il.end());
790}
791
792#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
793
794#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
795
796template <class _Value, class _Hash, class _Pred, class _Alloc>
797inline _LIBCPP_INLINE_VISIBILITY
798unordered_set<_Value, _Hash, _Pred, _Alloc>&
799unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(unordered_set&& __u)
800    _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
801{
802    __table_ = _VSTD::move(__u.__table_);
803    return *this;
804}
805
806#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
807
808#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
809
810template <class _Value, class _Hash, class _Pred, class _Alloc>
811inline _LIBCPP_INLINE_VISIBILITY
812unordered_set<_Value, _Hash, _Pred, _Alloc>&
813unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(
814        initializer_list<value_type> __il)
815{
816    __table_.__assign_unique(__il.begin(), __il.end());
817    return *this;
818}
819
820#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
821
822template <class _Value, class _Hash, class _Pred, class _Alloc>
823template <class _InputIterator>
824inline _LIBCPP_INLINE_VISIBILITY
825void
826unordered_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
827                                                    _InputIterator __last)
828{
829    for (; __first != __last; ++__first)
830        __table_.__insert_unique(*__first);
831}
832
833template <class _Value, class _Hash, class _Pred, class _Alloc>
834inline _LIBCPP_INLINE_VISIBILITY
835void
836swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
837     unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
838    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
839{
840    __x.swap(__y);
841}
842
843template <class _Value, class _Hash, class _Pred, class _Alloc>
844bool
845operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
846           const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
847{
848    if (__x.size() != __y.size())
849        return false;
850    typedef typename unordered_set<_Value, _Hash, _Pred, _Alloc>::const_iterator
851                                                                 const_iterator;
852    for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();
853            __i != __ex; ++__i)
854    {
855        const_iterator __j = __y.find(*__i);
856        if (__j == __ey || !(*__i == *__j))
857            return false;
858    }
859    return true;
860}
861
862template <class _Value, class _Hash, class _Pred, class _Alloc>
863inline _LIBCPP_INLINE_VISIBILITY
864bool
865operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
866           const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
867{
868    return !(__x == __y);
869}
870
871template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>,
872          class _Alloc = allocator<_Value> >
873class _LIBCPP_TYPE_VIS_ONLY unordered_multiset
874{
875public:
876    // types
877    typedef _Value                                                     key_type;
878    typedef key_type                                                   value_type;
879    typedef _Hash                                                      hasher;
880    typedef _Pred                                                      key_equal;
881    typedef _Alloc                                                     allocator_type;
882    typedef value_type&                                                reference;
883    typedef const value_type&                                          const_reference;
884    static_assert((is_same<value_type, typename allocator_type::value_type>::value),
885                  "Invalid allocator::value_type");
886
887private:
888    typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
889
890    __table __table_;
891
892public:
893    typedef typename __table::pointer         pointer;
894    typedef typename __table::const_pointer   const_pointer;
895    typedef typename __table::size_type       size_type;
896    typedef typename __table::difference_type difference_type;
897
898    typedef typename __table::const_iterator       iterator;
899    typedef typename __table::const_iterator       const_iterator;
900    typedef typename __table::const_local_iterator local_iterator;
901    typedef typename __table::const_local_iterator const_local_iterator;
902
903    _LIBCPP_INLINE_VISIBILITY
904    unordered_multiset()
905        _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
906        {
907#if _LIBCPP_DEBUG_LEVEL >= 2
908            __get_db()->__insert_c(this);
909#endif
910        }
911    explicit unordered_multiset(size_type __n, const hasher& __hf = hasher(),
912                                const key_equal& __eql = key_equal());
913    unordered_multiset(size_type __n, const hasher& __hf,
914                       const key_equal& __eql, const allocator_type& __a);
915#if _LIBCPP_STD_VER > 11
916    inline _LIBCPP_INLINE_VISIBILITY
917    unordered_multiset(size_type __n, const allocator_type& __a)
918        : unordered_multiset(__n, hasher(), key_equal(), __a) {}
919    inline _LIBCPP_INLINE_VISIBILITY
920    unordered_multiset(size_type __n, const hasher& __hf, const allocator_type& __a)
921        : unordered_multiset(__n, __hf, key_equal(), __a) {}
922#endif
923    template <class _InputIterator>
924        unordered_multiset(_InputIterator __first, _InputIterator __last);
925    template <class _InputIterator>
926        unordered_multiset(_InputIterator __first, _InputIterator __last,
927                      size_type __n, const hasher& __hf = hasher(),
928                      const key_equal& __eql = key_equal());
929    template <class _InputIterator>
930        unordered_multiset(_InputIterator __first, _InputIterator __last,
931                      size_type __n , const hasher& __hf,
932                      const key_equal& __eql, const allocator_type& __a);
933#if _LIBCPP_STD_VER > 11
934    template <class _InputIterator>
935    inline _LIBCPP_INLINE_VISIBILITY
936    unordered_multiset(_InputIterator __first, _InputIterator __last, 
937                       size_type __n, const allocator_type& __a)
938        : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a) {}
939    template <class _InputIterator>
940    inline _LIBCPP_INLINE_VISIBILITY
941    unordered_multiset(_InputIterator __first, _InputIterator __last,
942                       size_type __n, const hasher& __hf, const allocator_type& __a)
943        : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a) {}
944#endif
945    explicit unordered_multiset(const allocator_type& __a);
946    unordered_multiset(const unordered_multiset& __u);
947    unordered_multiset(const unordered_multiset& __u, const allocator_type& __a);
948#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
949    unordered_multiset(unordered_multiset&& __u)
950        _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
951    unordered_multiset(unordered_multiset&& __u, const allocator_type& __a);
952#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
953#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
954    unordered_multiset(initializer_list<value_type> __il);
955    unordered_multiset(initializer_list<value_type> __il, size_type __n,
956                       const hasher& __hf = hasher(),
957                       const key_equal& __eql = key_equal());
958    unordered_multiset(initializer_list<value_type> __il, size_type __n,
959                       const hasher& __hf, const key_equal& __eql,
960                       const allocator_type& __a);
961#if _LIBCPP_STD_VER > 11
962    inline _LIBCPP_INLINE_VISIBILITY
963    unordered_multiset(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)
964      : unordered_multiset(__il, __n, hasher(), key_equal(), __a) {}
965    inline _LIBCPP_INLINE_VISIBILITY
966    unordered_multiset(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a)
967      : unordered_multiset(__il, __n, __hf, key_equal(), __a) {}
968#endif
969#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
970    // ~unordered_multiset() = default;
971    _LIBCPP_INLINE_VISIBILITY
972    unordered_multiset& operator=(const unordered_multiset& __u)
973    {
974        __table_ = __u.__table_;
975        return *this;
976    }
977#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
978    unordered_multiset& operator=(unordered_multiset&& __u)
979        _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
980#endif
981#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
982    unordered_multiset& operator=(initializer_list<value_type> __il);
983#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
984
985    _LIBCPP_INLINE_VISIBILITY
986    allocator_type get_allocator() const _NOEXCEPT
987        {return allocator_type(__table_.__node_alloc());}
988
989    _LIBCPP_INLINE_VISIBILITY
990    bool      empty() const _NOEXCEPT {return __table_.size() == 0;}
991    _LIBCPP_INLINE_VISIBILITY
992    size_type size() const _NOEXCEPT  {return __table_.size();}
993    _LIBCPP_INLINE_VISIBILITY
994    size_type max_size() const _NOEXCEPT {return __table_.max_size();}
995
996    _LIBCPP_INLINE_VISIBILITY
997    iterator       begin() _NOEXCEPT        {return __table_.begin();}
998    _LIBCPP_INLINE_VISIBILITY
999    iterator       end() _NOEXCEPT          {return __table_.end();}
1000    _LIBCPP_INLINE_VISIBILITY
1001    const_iterator begin()  const _NOEXCEPT {return __table_.begin();}
1002    _LIBCPP_INLINE_VISIBILITY
1003    const_iterator end()    const _NOEXCEPT {return __table_.end();}
1004    _LIBCPP_INLINE_VISIBILITY
1005    const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
1006    _LIBCPP_INLINE_VISIBILITY
1007    const_iterator cend()   const _NOEXCEPT {return __table_.end();}
1008
1009#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
1010    template <class... _Args>
1011        _LIBCPP_INLINE_VISIBILITY
1012        iterator emplace(_Args&&... __args)
1013            {return __table_.__emplace_multi(_VSTD::forward<_Args>(__args)...);}
1014    template <class... _Args>
1015        _LIBCPP_INLINE_VISIBILITY
1016        iterator emplace_hint(const_iterator __p, _Args&&... __args)
1017            {return __table_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);}
1018#endif  // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
1019    _LIBCPP_INLINE_VISIBILITY
1020    iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
1021#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1022    _LIBCPP_INLINE_VISIBILITY
1023    iterator insert(value_type&& __x) {return __table_.__insert_multi(_VSTD::move(__x));}
1024#endif
1025    _LIBCPP_INLINE_VISIBILITY
1026    iterator insert(const_iterator __p, const value_type& __x)
1027        {return __table_.__insert_multi(__p, __x);}
1028#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1029    _LIBCPP_INLINE_VISIBILITY
1030    iterator insert(const_iterator __p, value_type&& __x)
1031        {return __table_.__insert_multi(__p, _VSTD::move(__x));}
1032#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1033    template <class _InputIterator>
1034        void insert(_InputIterator __first, _InputIterator __last);
1035#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1036    _LIBCPP_INLINE_VISIBILITY
1037    void insert(initializer_list<value_type> __il)
1038        {insert(__il.begin(), __il.end());}
1039#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1040
1041    _LIBCPP_INLINE_VISIBILITY
1042    iterator erase(const_iterator __p) {return __table_.erase(__p);}
1043    _LIBCPP_INLINE_VISIBILITY
1044    size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
1045    _LIBCPP_INLINE_VISIBILITY
1046    iterator erase(const_iterator __first, const_iterator __last)
1047        {return __table_.erase(__first, __last);}
1048    _LIBCPP_INLINE_VISIBILITY
1049    void clear() _NOEXCEPT {__table_.clear();}
1050
1051    _LIBCPP_INLINE_VISIBILITY
1052    void swap(unordered_multiset& __u)
1053        _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
1054        {__table_.swap(__u.__table_);}
1055
1056    _LIBCPP_INLINE_VISIBILITY
1057    hasher hash_function() const {return __table_.hash_function();}
1058    _LIBCPP_INLINE_VISIBILITY
1059    key_equal key_eq() const {return __table_.key_eq();}
1060
1061    _LIBCPP_INLINE_VISIBILITY
1062    iterator       find(const key_type& __k)       {return __table_.find(__k);}
1063    _LIBCPP_INLINE_VISIBILITY
1064    const_iterator find(const key_type& __k) const {return __table_.find(__k);}
1065    _LIBCPP_INLINE_VISIBILITY
1066    size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
1067    _LIBCPP_INLINE_VISIBILITY
1068    pair<iterator, iterator>             equal_range(const key_type& __k)
1069        {return __table_.__equal_range_multi(__k);}
1070    _LIBCPP_INLINE_VISIBILITY
1071    pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
1072        {return __table_.__equal_range_multi(__k);}
1073
1074    _LIBCPP_INLINE_VISIBILITY
1075    size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
1076    _LIBCPP_INLINE_VISIBILITY
1077    size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
1078
1079    _LIBCPP_INLINE_VISIBILITY
1080    size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);}
1081    _LIBCPP_INLINE_VISIBILITY
1082    size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
1083
1084    _LIBCPP_INLINE_VISIBILITY
1085    local_iterator       begin(size_type __n)        {return __table_.begin(__n);}
1086    _LIBCPP_INLINE_VISIBILITY
1087    local_iterator       end(size_type __n)          {return __table_.end(__n);}
1088    _LIBCPP_INLINE_VISIBILITY
1089    const_local_iterator begin(size_type __n) const  {return __table_.cbegin(__n);}
1090    _LIBCPP_INLINE_VISIBILITY
1091    const_local_iterator end(size_type __n) const    {return __table_.cend(__n);}
1092    _LIBCPP_INLINE_VISIBILITY
1093    const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
1094    _LIBCPP_INLINE_VISIBILITY
1095    const_local_iterator cend(size_type __n) const   {return __table_.cend(__n);}
1096
1097    _LIBCPP_INLINE_VISIBILITY
1098    float load_factor() const _NOEXCEPT {return __table_.load_factor();}
1099    _LIBCPP_INLINE_VISIBILITY
1100    float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
1101    _LIBCPP_INLINE_VISIBILITY
1102    void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
1103    _LIBCPP_INLINE_VISIBILITY
1104    void rehash(size_type __n) {__table_.rehash(__n);}
1105    _LIBCPP_INLINE_VISIBILITY
1106    void reserve(size_type __n) {__table_.reserve(__n);}
1107
1108#if _LIBCPP_DEBUG_LEVEL >= 2
1109
1110    bool __dereferenceable(const const_iterator* __i) const
1111        {return __table_.__dereferenceable(__i);}
1112    bool __decrementable(const const_iterator* __i) const
1113        {return __table_.__decrementable(__i);}
1114    bool __addable(const const_iterator* __i, ptrdiff_t __n) const
1115        {return __table_.__addable(__i, __n);}
1116    bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
1117        {return __table_.__addable(__i, __n);}
1118
1119#endif  // _LIBCPP_DEBUG_LEVEL >= 2
1120
1121};
1122
1123template <class _Value, class _Hash, class _Pred, class _Alloc>
1124unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1125        size_type __n, const hasher& __hf, const key_equal& __eql)
1126    : __table_(__hf, __eql)
1127{
1128#if _LIBCPP_DEBUG_LEVEL >= 2
1129    __get_db()->__insert_c(this);
1130#endif
1131    __table_.rehash(__n);
1132}
1133
1134template <class _Value, class _Hash, class _Pred, class _Alloc>
1135unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1136        size_type __n, const hasher& __hf, const key_equal& __eql,
1137        const allocator_type& __a)
1138    : __table_(__hf, __eql, __a)
1139{
1140#if _LIBCPP_DEBUG_LEVEL >= 2
1141    __get_db()->__insert_c(this);
1142#endif
1143    __table_.rehash(__n);
1144}
1145
1146template <class _Value, class _Hash, class _Pred, class _Alloc>
1147template <class _InputIterator>
1148unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1149        _InputIterator __first, _InputIterator __last)
1150{
1151#if _LIBCPP_DEBUG_LEVEL >= 2
1152    __get_db()->__insert_c(this);
1153#endif
1154    insert(__first, __last);
1155}
1156
1157template <class _Value, class _Hash, class _Pred, class _Alloc>
1158template <class _InputIterator>
1159unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1160        _InputIterator __first, _InputIterator __last, size_type __n,
1161        const hasher& __hf, const key_equal& __eql)
1162    : __table_(__hf, __eql)
1163{
1164#if _LIBCPP_DEBUG_LEVEL >= 2
1165    __get_db()->__insert_c(this);
1166#endif
1167    __table_.rehash(__n);
1168    insert(__first, __last);
1169}
1170
1171template <class _Value, class _Hash, class _Pred, class _Alloc>
1172template <class _InputIterator>
1173unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1174        _InputIterator __first, _InputIterator __last, size_type __n,
1175        const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1176    : __table_(__hf, __eql, __a)
1177{
1178#if _LIBCPP_DEBUG_LEVEL >= 2
1179    __get_db()->__insert_c(this);
1180#endif
1181    __table_.rehash(__n);
1182    insert(__first, __last);
1183}
1184
1185template <class _Value, class _Hash, class _Pred, class _Alloc>
1186inline _LIBCPP_INLINE_VISIBILITY
1187unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1188        const allocator_type& __a)
1189    : __table_(__a)
1190{
1191#if _LIBCPP_DEBUG_LEVEL >= 2
1192    __get_db()->__insert_c(this);
1193#endif
1194}
1195
1196template <class _Value, class _Hash, class _Pred, class _Alloc>
1197unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1198        const unordered_multiset& __u)
1199    : __table_(__u.__table_)
1200{
1201#if _LIBCPP_DEBUG_LEVEL >= 2
1202    __get_db()->__insert_c(this);
1203#endif
1204    __table_.rehash(__u.bucket_count());
1205    insert(__u.begin(), __u.end());
1206}
1207
1208template <class _Value, class _Hash, class _Pred, class _Alloc>
1209unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1210        const unordered_multiset& __u, const allocator_type& __a)
1211    : __table_(__u.__table_, __a)
1212{
1213#if _LIBCPP_DEBUG_LEVEL >= 2
1214    __get_db()->__insert_c(this);
1215#endif
1216    __table_.rehash(__u.bucket_count());
1217    insert(__u.begin(), __u.end());
1218}
1219
1220#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1221
1222template <class _Value, class _Hash, class _Pred, class _Alloc>
1223inline _LIBCPP_INLINE_VISIBILITY
1224unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1225        unordered_multiset&& __u)
1226    _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
1227    : __table_(_VSTD::move(__u.__table_))
1228{
1229#if _LIBCPP_DEBUG_LEVEL >= 2
1230    __get_db()->__insert_c(this);
1231    __get_db()->swap(this, &__u);
1232#endif
1233}
1234
1235template <class _Value, class _Hash, class _Pred, class _Alloc>
1236unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1237        unordered_multiset&& __u, const allocator_type& __a)
1238    : __table_(_VSTD::move(__u.__table_), __a)
1239{
1240#if _LIBCPP_DEBUG_LEVEL >= 2
1241    __get_db()->__insert_c(this);
1242#endif
1243    if (__a != __u.get_allocator())
1244    {
1245        iterator __i = __u.begin();
1246        while (__u.size() != 0)
1247            __table_.__insert_multi(_VSTD::move(__u.__table_.remove(__i++)->__value_));
1248    }
1249#if _LIBCPP_DEBUG_LEVEL >= 2
1250    else
1251        __get_db()->swap(this, &__u);
1252#endif
1253}
1254
1255#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1256
1257#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1258
1259template <class _Value, class _Hash, class _Pred, class _Alloc>
1260unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1261        initializer_list<value_type> __il)
1262{
1263#if _LIBCPP_DEBUG_LEVEL >= 2
1264    __get_db()->__insert_c(this);
1265#endif
1266    insert(__il.begin(), __il.end());
1267}
1268
1269template <class _Value, class _Hash, class _Pred, class _Alloc>
1270unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1271        initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1272        const key_equal& __eql)
1273    : __table_(__hf, __eql)
1274{
1275#if _LIBCPP_DEBUG_LEVEL >= 2
1276    __get_db()->__insert_c(this);
1277#endif
1278    __table_.rehash(__n);
1279    insert(__il.begin(), __il.end());
1280}
1281
1282template <class _Value, class _Hash, class _Pred, class _Alloc>
1283unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1284        initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1285        const key_equal& __eql, const allocator_type& __a)
1286    : __table_(__hf, __eql, __a)
1287{
1288#if _LIBCPP_DEBUG_LEVEL >= 2
1289    __get_db()->__insert_c(this);
1290#endif
1291    __table_.rehash(__n);
1292    insert(__il.begin(), __il.end());
1293}
1294
1295#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1296
1297#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1298
1299template <class _Value, class _Hash, class _Pred, class _Alloc>
1300inline _LIBCPP_INLINE_VISIBILITY
1301unordered_multiset<_Value, _Hash, _Pred, _Alloc>&
1302unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(
1303        unordered_multiset&& __u)
1304    _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
1305{
1306    __table_ = _VSTD::move(__u.__table_);
1307    return *this;
1308}
1309
1310#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1311
1312#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1313
1314template <class _Value, class _Hash, class _Pred, class _Alloc>
1315inline
1316unordered_multiset<_Value, _Hash, _Pred, _Alloc>&
1317unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(
1318        initializer_list<value_type> __il)
1319{
1320    __table_.__assign_multi(__il.begin(), __il.end());
1321    return *this;
1322}
1323
1324#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1325
1326template <class _Value, class _Hash, class _Pred, class _Alloc>
1327template <class _InputIterator>
1328inline _LIBCPP_INLINE_VISIBILITY
1329void
1330unordered_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
1331                                                         _InputIterator __last)
1332{
1333    for (; __first != __last; ++__first)
1334        __table_.__insert_multi(*__first);
1335}
1336
1337template <class _Value, class _Hash, class _Pred, class _Alloc>
1338inline _LIBCPP_INLINE_VISIBILITY
1339void
1340swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1341     unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1342    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1343{
1344    __x.swap(__y);
1345}
1346
1347template <class _Value, class _Hash, class _Pred, class _Alloc>
1348bool
1349operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1350           const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1351{
1352    if (__x.size() != __y.size())
1353        return false;
1354    typedef typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator
1355                                                                 const_iterator;
1356    typedef pair<const_iterator, const_iterator> _EqRng;
1357    for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;)
1358    {
1359        _EqRng __xeq = __x.equal_range(*__i);
1360        _EqRng __yeq = __y.equal_range(*__i);
1361        if (_VSTD::distance(__xeq.first, __xeq.second) !=
1362            _VSTD::distance(__yeq.first, __yeq.second) ||
1363                  !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first))
1364            return false;
1365        __i = __xeq.second;
1366    }
1367    return true;
1368}
1369
1370template <class _Value, class _Hash, class _Pred, class _Alloc>
1371inline _LIBCPP_INLINE_VISIBILITY
1372bool
1373operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1374           const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1375{
1376    return !(__x == __y);
1377}
1378
1379_LIBCPP_END_NAMESPACE_STD
1380
1381#endif  // _LIBCPP_UNORDERED_SET
1382