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    explicit unordered_set(size_type n = 0, const hasher& hf = hasher(),
47                           const key_equal& eql = key_equal(),
48                           const allocator_type& a = allocator_type());
49    template <class InputIterator>
50        unordered_set(InputIterator f, InputIterator l,
51                      size_type n = 0, const hasher& hf = hasher(),
52                      const key_equal& eql = key_equal(),
53                      const allocator_type& a = allocator_type());
54    explicit unordered_set(const allocator_type&);
55    unordered_set(const unordered_set&);
56    unordered_set(const unordered_set&, const Allocator&);
57    unordered_set(unordered_set&&);
58    unordered_set(unordered_set&&, const Allocator&);
59    unordered_set(initializer_list<value_type>, size_type n = 0,
60                  const hasher& hf = hasher(), const key_equal& eql = key_equal(),
61                  const allocator_type& a = allocator_type());
62    ~unordered_set();
63    unordered_set& operator=(const unordered_set&);
64    unordered_set& operator=(unordered_set&&);
65    unordered_set& operator=(initializer_list<value_type>);
66
67    allocator_type get_allocator() const;
68
69    bool      empty() const;
70    size_type size() const;
71    size_type max_size() const;
72
73    iterator       begin();
74    iterator       end();
75    const_iterator begin()  const;
76    const_iterator end()    const;
77    const_iterator cbegin() const;
78    const_iterator cend()   const;
79
80    template <class... Args>
81        pair<iterator, bool> emplace(Args&&... args);
82    template <class... Args>
83        iterator emplace_hint(const_iterator position, Args&&... args);
84    pair<iterator, bool> insert(const value_type& obj);
85    pair<iterator, bool> insert(value_type&& obj);
86    iterator insert(const_iterator hint, const value_type& obj);
87    iterator insert(const_iterator hint, value_type&& obj);
88    template <class InputIterator>
89        void insert(InputIterator first, InputIterator last);
90    void insert(initializer_list<value_type>);
91
92    iterator erase(const_iterator position);
93    size_type erase(const key_type& k);
94    iterator erase(const_iterator first, const_iterator last);
95    void clear();
96
97    void swap(unordered_set&);
98
99    hasher hash_function() const;
100    key_equal key_eq() const;
101
102    iterator       find(const key_type& k);
103    const_iterator find(const key_type& k) const;
104    size_type count(const key_type& k) const;
105    pair<iterator, iterator>             equal_range(const key_type& k);
106    pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
107
108    size_type bucket_count() const;
109    size_type max_bucket_count() const;
110
111    size_type bucket_size(size_type n) const;
112    size_type bucket(const key_type& k) const;
113
114    local_iterator       begin(size_type n);
115    local_iterator       end(size_type n);
116    const_local_iterator begin(size_type n) const;
117    const_local_iterator end(size_type n) const;
118    const_local_iterator cbegin(size_type n) const;
119    const_local_iterator cend(size_type n) const;
120
121    float load_factor() const;
122    float max_load_factor() const;
123    void max_load_factor(float z);
124    void rehash(size_type n);
125    void reserve(size_type n);
126};
127
128template <class Value, class Hash, class Pred, class Alloc>
129    void swap(unordered_set<Value, Hash, Pred, Alloc>& x,
130              unordered_set<Value, Hash, Pred, Alloc>& y);
131
132template <class Value, class Hash, class Pred, class Alloc>
133    bool
134    operator==(const unordered_set<Value, Hash, Pred, Alloc>& x,
135               const unordered_set<Value, Hash, Pred, Alloc>& y);
136
137template <class Value, class Hash, class Pred, class Alloc>
138    bool
139    operator!=(const unordered_set<Value, Hash, Pred, Alloc>& x,
140               const unordered_set<Value, Hash, Pred, Alloc>& y);
141
142template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,
143          class Alloc = allocator<Value>>
144class unordered_multiset
145{
146public:
147    // types
148    typedef Value                                                      key_type;
149    typedef key_type                                                   value_type;
150    typedef Hash                                                       hasher;
151    typedef Pred                                                       key_equal;
152    typedef Alloc                                                      allocator_type;
153    typedef value_type&                                                reference;
154    typedef const value_type&                                          const_reference;
155    typedef typename allocator_traits<allocator_type>::pointer         pointer;
156    typedef typename allocator_traits<allocator_type>::const_pointer   const_pointer;
157    typedef typename allocator_traits<allocator_type>::size_type       size_type;
158    typedef typename allocator_traits<allocator_type>::difference_type difference_type;
159
160    typedef /unspecified/ iterator;
161    typedef /unspecified/ const_iterator;
162    typedef /unspecified/ local_iterator;
163    typedef /unspecified/ const_local_iterator;
164
165    explicit unordered_multiset(size_type n = 0, const hasher& hf = hasher(),
166                           const key_equal& eql = key_equal(),
167                           const allocator_type& a = allocator_type());
168    template <class InputIterator>
169        unordered_multiset(InputIterator f, InputIterator l,
170                      size_type n = 0, const hasher& hf = hasher(),
171                      const key_equal& eql = key_equal(),
172                      const allocator_type& a = allocator_type());
173    explicit unordered_multiset(const allocator_type&);
174    unordered_multiset(const unordered_multiset&);
175    unordered_multiset(const unordered_multiset&, const Allocator&);
176    unordered_multiset(unordered_multiset&&);
177    unordered_multiset(unordered_multiset&&, const Allocator&);
178    unordered_multiset(initializer_list<value_type>, size_type n = /see below/,
179                  const hasher& hf = hasher(), const key_equal& eql = key_equal(),
180                  const allocator_type& a = allocator_type());
181    ~unordered_multiset();
182    unordered_multiset& operator=(const unordered_multiset&);
183    unordered_multiset& operator=(unordered_multiset&&);
184    unordered_multiset& operator=(initializer_list<value_type>);
185
186    allocator_type get_allocator() const;
187
188    bool      empty() const;
189    size_type size() const;
190    size_type max_size() const;
191
192    iterator       begin();
193    iterator       end();
194    const_iterator begin()  const;
195    const_iterator end()    const;
196    const_iterator cbegin() const;
197    const_iterator cend()   const;
198
199    template <class... Args>
200        iterator emplace(Args&&... args);
201    template <class... Args>
202        iterator emplace_hint(const_iterator position, Args&&... args);
203    iterator insert(const value_type& obj);
204    iterator insert(value_type&& obj);
205    iterator insert(const_iterator hint, const value_type& obj);
206    iterator insert(const_iterator hint, value_type&& obj);
207    template <class InputIterator>
208        void insert(InputIterator first, InputIterator last);
209    void insert(initializer_list<value_type>);
210
211    iterator erase(const_iterator position);
212    size_type erase(const key_type& k);
213    iterator erase(const_iterator first, const_iterator last);
214    void clear();
215
216    void swap(unordered_multiset&);
217
218    hasher hash_function() const;
219    key_equal key_eq() const;
220
221    iterator       find(const key_type& k);
222    const_iterator find(const key_type& k) const;
223    size_type count(const key_type& k) const;
224    pair<iterator, iterator>             equal_range(const key_type& k);
225    pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
226
227    size_type bucket_count() const;
228    size_type max_bucket_count() const;
229
230    size_type bucket_size(size_type n) const;
231    size_type bucket(const key_type& k) const;
232
233    local_iterator       begin(size_type n);
234    local_iterator       end(size_type n);
235    const_local_iterator begin(size_type n) const;
236    const_local_iterator end(size_type n) const;
237    const_local_iterator cbegin(size_type n) const;
238    const_local_iterator cend(size_type n) const;
239
240    float load_factor() const;
241    float max_load_factor() const;
242    void max_load_factor(float z);
243    void rehash(size_type n);
244    void reserve(size_type n);
245};
246
247template <class Value, class Hash, class Pred, class Alloc>
248    void swap(unordered_multiset<Value, Hash, Pred, Alloc>& x,
249              unordered_multiset<Value, Hash, Pred, Alloc>& y);
250
251template <class Value, class Hash, class Pred, class Alloc>
252    bool
253    operator==(const unordered_multiset<Value, Hash, Pred, Alloc>& x,
254               const unordered_multiset<Value, Hash, Pred, Alloc>& y);
255
256template <class Value, class Hash, class Pred, class Alloc>
257    bool
258    operator!=(const unordered_multiset<Value, Hash, Pred, Alloc>& x,
259               const unordered_multiset<Value, Hash, Pred, Alloc>& y);
260}  // std
261
262*/
263
264#include <__config>
265#include <__hash_table>
266#include <functional>
267
268#pragma GCC system_header
269
270_LIBCPP_BEGIN_NAMESPACE_STD
271
272template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>,
273          class _Alloc = allocator<_Value> >
274class _LIBCPP_VISIBLE unordered_set
275{
276public:
277    // types
278    typedef _Value                                                     key_type;
279    typedef key_type                                                   value_type;
280    typedef _Hash                                                      hasher;
281    typedef _Pred                                                      key_equal;
282    typedef _Alloc                                                     allocator_type;
283    typedef value_type&                                                reference;
284    typedef const value_type&                                          const_reference;
285
286private:
287    typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
288
289    __table __table_;
290
291public:
292    typedef typename __table::pointer         pointer;
293    typedef typename __table::const_pointer   const_pointer;
294    typedef typename __table::size_type       size_type;
295    typedef typename __table::difference_type difference_type;
296
297    typedef typename __table::const_iterator       iterator;
298    typedef typename __table::const_iterator       const_iterator;
299    typedef typename __table::const_local_iterator local_iterator;
300    typedef typename __table::const_local_iterator const_local_iterator;
301
302    _LIBCPP_INLINE_VISIBILITY
303    unordered_set() {} // = default;
304    explicit unordered_set(size_type __n, const hasher& __hf = hasher(),
305                           const key_equal& __eql = key_equal());
306    unordered_set(size_type __n, const hasher& __hf, const key_equal& __eql,
307                  const allocator_type& __a);
308    template <class _InputIterator>
309        unordered_set(_InputIterator __first, _InputIterator __last);
310    template <class _InputIterator>
311        unordered_set(_InputIterator __first, _InputIterator __last,
312                      size_type __n, const hasher& __hf = hasher(),
313                      const key_equal& __eql = key_equal());
314    template <class _InputIterator>
315        unordered_set(_InputIterator __first, _InputIterator __last,
316                      size_type __n, const hasher& __hf, const key_equal& __eql,
317                      const allocator_type& __a);
318    explicit unordered_set(const allocator_type& __a);
319    unordered_set(const unordered_set& __u);
320    unordered_set(const unordered_set& __u, const allocator_type& __a);
321#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
322    unordered_set(unordered_set&& __u);
323    unordered_set(unordered_set&& __u, const allocator_type& __a);
324#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
325    unordered_set(initializer_list<value_type> __il);
326    unordered_set(initializer_list<value_type> __il, size_type __n,
327                  const hasher& __hf = hasher(),
328                  const key_equal& __eql = key_equal());
329    unordered_set(initializer_list<value_type> __il, size_type __n,
330                  const hasher& __hf, const key_equal& __eql,
331                  const allocator_type& __a);
332    // ~unordered_set() = default;
333    // unordered_set& operator=(const unordered_set& __u) = default;
334#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
335    unordered_set& operator=(unordered_set&& __u);
336#endif
337    unordered_set& operator=(initializer_list<value_type> __il);
338
339    _LIBCPP_INLINE_VISIBILITY
340    allocator_type get_allocator() const
341        {return allocator_type(__table_.__node_alloc());}
342
343    _LIBCPP_INLINE_VISIBILITY
344    bool      empty() const {return __table_.size() == 0;}
345    _LIBCPP_INLINE_VISIBILITY
346    size_type size() const  {return __table_.size();}
347    _LIBCPP_INLINE_VISIBILITY
348    size_type max_size() const {return __table_.max_size();}
349
350    _LIBCPP_INLINE_VISIBILITY
351    iterator       begin()        {return __table_.begin();}
352    _LIBCPP_INLINE_VISIBILITY
353    iterator       end()          {return __table_.end();}
354    _LIBCPP_INLINE_VISIBILITY
355    const_iterator begin()  const {return __table_.begin();}
356    _LIBCPP_INLINE_VISIBILITY
357    const_iterator end()    const {return __table_.end();}
358    _LIBCPP_INLINE_VISIBILITY
359    const_iterator cbegin() const {return __table_.begin();}
360    _LIBCPP_INLINE_VISIBILITY
361    const_iterator cend()   const {return __table_.end();}
362
363#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
364    template <class... _Args>
365        _LIBCPP_INLINE_VISIBILITY
366        pair<iterator, bool> emplace(_Args&&... __args)
367            {return __table_.__emplace_unique(_STD::forward<_Args>(__args)...);}
368    template <class... _Args>
369        _LIBCPP_INLINE_VISIBILITY
370        iterator emplace_hint(const_iterator, _Args&&... __args)
371            {return __table_.__emplace_unique(_STD::forward<_Args>(__args)...).first;}
372#endif  // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
373    _LIBCPP_INLINE_VISIBILITY
374    pair<iterator, bool> insert(const value_type& __x)
375        {return __table_.__insert_unique(__x);}
376#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
377    _LIBCPP_INLINE_VISIBILITY
378    pair<iterator, bool> insert(value_type&& __x)
379        {return __table_.__insert_unique(_STD::move(__x));}
380#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
381    _LIBCPP_INLINE_VISIBILITY
382    iterator insert(const_iterator, const value_type& __x)
383        {return insert(__x).first;}
384#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
385    _LIBCPP_INLINE_VISIBILITY
386    iterator insert(const_iterator, value_type&& __x)
387        {return insert(_STD::move(__x)).first;}
388#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
389    template <class _InputIterator>
390        void insert(_InputIterator __first, _InputIterator __last);
391    _LIBCPP_INLINE_VISIBILITY
392    void insert(initializer_list<value_type> __il)
393        {insert(__il.begin(), __il.end());}
394
395    _LIBCPP_INLINE_VISIBILITY
396    iterator erase(const_iterator __p) {return __table_.erase(__p);}
397    _LIBCPP_INLINE_VISIBILITY
398    size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
399    _LIBCPP_INLINE_VISIBILITY
400    iterator erase(const_iterator __first, const_iterator __last)
401        {return __table_.erase(__first, __last);}
402    _LIBCPP_INLINE_VISIBILITY
403    void clear() {__table_.clear();}
404
405    _LIBCPP_INLINE_VISIBILITY
406    void swap(unordered_set& __u) {__table_.swap(__u.__table_);}
407
408    _LIBCPP_INLINE_VISIBILITY
409    hasher hash_function() const {return __table_.hash_function();}
410    _LIBCPP_INLINE_VISIBILITY
411    key_equal key_eq() const {return __table_.key_eq();}
412
413    _LIBCPP_INLINE_VISIBILITY
414    iterator       find(const key_type& __k)       {return __table_.find(__k);}
415    _LIBCPP_INLINE_VISIBILITY
416    const_iterator find(const key_type& __k) const {return __table_.find(__k);}
417    _LIBCPP_INLINE_VISIBILITY
418    size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
419    _LIBCPP_INLINE_VISIBILITY
420    pair<iterator, iterator>             equal_range(const key_type& __k)
421        {return __table_.__equal_range_unique(__k);}
422    _LIBCPP_INLINE_VISIBILITY
423    pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
424        {return __table_.__equal_range_unique(__k);}
425
426    _LIBCPP_INLINE_VISIBILITY
427    size_type bucket_count() const {return __table_.bucket_count();}
428    _LIBCPP_INLINE_VISIBILITY
429    size_type max_bucket_count() const {return __table_.max_bucket_count();}
430
431    _LIBCPP_INLINE_VISIBILITY
432    size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);}
433    _LIBCPP_INLINE_VISIBILITY
434    size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
435
436    _LIBCPP_INLINE_VISIBILITY
437    local_iterator       begin(size_type __n)        {return __table_.begin(__n);}
438    _LIBCPP_INLINE_VISIBILITY
439    local_iterator       end(size_type __n)          {return __table_.end(__n);}
440    _LIBCPP_INLINE_VISIBILITY
441    const_local_iterator begin(size_type __n) const  {return __table_.cbegin(__n);}
442    _LIBCPP_INLINE_VISIBILITY
443    const_local_iterator end(size_type __n) const    {return __table_.cend(__n);}
444    _LIBCPP_INLINE_VISIBILITY
445    const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
446    _LIBCPP_INLINE_VISIBILITY
447    const_local_iterator cend(size_type __n) const   {return __table_.cend(__n);}
448
449    _LIBCPP_INLINE_VISIBILITY
450    float load_factor() const {return __table_.load_factor();}
451    _LIBCPP_INLINE_VISIBILITY
452    float max_load_factor() const {return __table_.max_load_factor();}
453    _LIBCPP_INLINE_VISIBILITY
454    void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
455    _LIBCPP_INLINE_VISIBILITY
456    void rehash(size_type __n) {__table_.rehash(__n);}
457    _LIBCPP_INLINE_VISIBILITY
458    void reserve(size_type __n) {__table_.reserve(__n);}
459};
460
461template <class _Value, class _Hash, class _Pred, class _Alloc>
462unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n,
463        const hasher& __hf, const key_equal& __eql)
464    : __table_(__hf, __eql)
465{
466    __table_.rehash(__n);
467}
468
469template <class _Value, class _Hash, class _Pred, class _Alloc>
470unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n,
471        const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
472    : __table_(__hf, __eql, __a)
473{
474    __table_.rehash(__n);
475}
476
477template <class _Value, class _Hash, class _Pred, class _Alloc>
478template <class _InputIterator>
479unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
480        _InputIterator __first, _InputIterator __last)
481{
482    insert(__first, __last);
483}
484
485template <class _Value, class _Hash, class _Pred, class _Alloc>
486template <class _InputIterator>
487unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
488        _InputIterator __first, _InputIterator __last, size_type __n,
489        const hasher& __hf, const key_equal& __eql)
490    : __table_(__hf, __eql)
491{
492    __table_.rehash(__n);
493    insert(__first, __last);
494}
495
496template <class _Value, class _Hash, class _Pred, class _Alloc>
497template <class _InputIterator>
498unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
499        _InputIterator __first, _InputIterator __last, size_type __n,
500        const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
501    : __table_(__hf, __eql, __a)
502{
503    __table_.rehash(__n);
504    insert(__first, __last);
505}
506
507template <class _Value, class _Hash, class _Pred, class _Alloc>
508inline _LIBCPP_INLINE_VISIBILITY
509unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
510        const allocator_type& __a)
511    : __table_(__a)
512{
513}
514
515template <class _Value, class _Hash, class _Pred, class _Alloc>
516unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
517        const unordered_set& __u)
518    : __table_(__u.__table_)
519{
520    __table_.rehash(__u.bucket_count());
521    insert(__u.begin(), __u.end());
522}
523
524template <class _Value, class _Hash, class _Pred, class _Alloc>
525unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
526        const unordered_set& __u, const allocator_type& __a)
527    : __table_(__u.__table_, __a)
528{
529    __table_.rehash(__u.bucket_count());
530    insert(__u.begin(), __u.end());
531}
532
533#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
534
535template <class _Value, class _Hash, class _Pred, class _Alloc>
536inline _LIBCPP_INLINE_VISIBILITY
537unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
538        unordered_set&& __u)
539    : __table_(_STD::move(__u.__table_))
540{
541}
542
543template <class _Value, class _Hash, class _Pred, class _Alloc>
544unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
545        unordered_set&& __u, const allocator_type& __a)
546    : __table_(_STD::move(__u.__table_), __a)
547{
548    if (__a != __u.get_allocator())
549    {
550        iterator __i = __u.begin();
551        while (__u.size() != 0)
552            __table_.__insert_unique(_STD::move(__u.__table_.remove(__i++)->__value_));
553    }
554}
555
556#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
557
558template <class _Value, class _Hash, class _Pred, class _Alloc>
559unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
560        initializer_list<value_type> __il)
561{
562    insert(__il.begin(), __il.end());
563}
564
565template <class _Value, class _Hash, class _Pred, class _Alloc>
566unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
567        initializer_list<value_type> __il, size_type __n, const hasher& __hf,
568        const key_equal& __eql)
569    : __table_(__hf, __eql)
570{
571    __table_.rehash(__n);
572    insert(__il.begin(), __il.end());
573}
574
575template <class _Value, class _Hash, class _Pred, class _Alloc>
576unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
577        initializer_list<value_type> __il, size_type __n, const hasher& __hf,
578        const key_equal& __eql, const allocator_type& __a)
579    : __table_(__hf, __eql, __a)
580{
581    __table_.rehash(__n);
582    insert(__il.begin(), __il.end());
583}
584
585#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
586
587template <class _Value, class _Hash, class _Pred, class _Alloc>
588inline _LIBCPP_INLINE_VISIBILITY
589unordered_set<_Value, _Hash, _Pred, _Alloc>&
590unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(unordered_set&& __u)
591{
592    __table_ = _STD::move(__u.__table_);
593    return *this;
594}
595
596#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
597
598template <class _Value, class _Hash, class _Pred, class _Alloc>
599inline _LIBCPP_INLINE_VISIBILITY
600unordered_set<_Value, _Hash, _Pred, _Alloc>&
601unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(
602        initializer_list<value_type> __il)
603{
604    __table_.__assign_unique(__il.begin(), __il.end());
605    return *this;
606}
607
608template <class _Value, class _Hash, class _Pred, class _Alloc>
609template <class _InputIterator>
610inline _LIBCPP_INLINE_VISIBILITY
611void
612unordered_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
613                                                    _InputIterator __last)
614{
615    for (; __first != __last; ++__first)
616        __table_.__insert_unique(*__first);
617}
618
619template <class _Value, class _Hash, class _Pred, class _Alloc>
620inline _LIBCPP_INLINE_VISIBILITY
621void
622swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
623     unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
624{
625    __x.swap(__y);
626}
627
628template <class _Value, class _Hash, class _Pred, class _Alloc>
629bool
630operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
631           const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
632{
633    if (__x.size() != __y.size())
634        return false;
635    typedef typename unordered_set<_Value, _Hash, _Pred, _Alloc>::const_iterator
636                                                                 const_iterator;
637    for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();
638            __i != __ex; ++__i)
639    {
640        const_iterator __j = __y.find(*__i);
641        if (__j == __ey || !(*__i == *__j))
642            return false;
643    }
644    return true;
645}
646
647template <class _Value, class _Hash, class _Pred, class _Alloc>
648inline _LIBCPP_INLINE_VISIBILITY
649bool
650operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
651           const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
652{
653    return !(__x == __y);
654}
655
656template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>,
657          class _Alloc = allocator<_Value> >
658class _LIBCPP_VISIBLE unordered_multiset
659{
660public:
661    // types
662    typedef _Value                                                     key_type;
663    typedef key_type                                                   value_type;
664    typedef _Hash                                                      hasher;
665    typedef _Pred                                                      key_equal;
666    typedef _Alloc                                                     allocator_type;
667    typedef value_type&                                                reference;
668    typedef const value_type&                                          const_reference;
669
670private:
671    typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
672
673    __table __table_;
674
675public:
676    typedef typename __table::pointer         pointer;
677    typedef typename __table::const_pointer   const_pointer;
678    typedef typename __table::size_type       size_type;
679    typedef typename __table::difference_type difference_type;
680
681    typedef typename __table::const_iterator       iterator;
682    typedef typename __table::const_iterator       const_iterator;
683    typedef typename __table::const_local_iterator local_iterator;
684    typedef typename __table::const_local_iterator const_local_iterator;
685
686    _LIBCPP_INLINE_VISIBILITY
687    unordered_multiset() {} // = default
688    explicit unordered_multiset(size_type __n, const hasher& __hf = hasher(),
689                                const key_equal& __eql = key_equal());
690    unordered_multiset(size_type __n, const hasher& __hf,
691                       const key_equal& __eql, const allocator_type& __a);
692    template <class _InputIterator>
693        unordered_multiset(_InputIterator __first, _InputIterator __last);
694    template <class _InputIterator>
695        unordered_multiset(_InputIterator __first, _InputIterator __last,
696                      size_type __n, const hasher& __hf = hasher(),
697                      const key_equal& __eql = key_equal());
698    template <class _InputIterator>
699        unordered_multiset(_InputIterator __first, _InputIterator __last,
700                      size_type __n , const hasher& __hf,
701                      const key_equal& __eql, const allocator_type& __a);
702    explicit unordered_multiset(const allocator_type& __a);
703    unordered_multiset(const unordered_multiset& __u);
704    unordered_multiset(const unordered_multiset& __u, const allocator_type& __a);
705#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
706    unordered_multiset(unordered_multiset&& __u);
707    unordered_multiset(unordered_multiset&& __u, const allocator_type& __a);
708#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
709    unordered_multiset(initializer_list<value_type> __il);
710    unordered_multiset(initializer_list<value_type> __il, size_type __n,
711                       const hasher& __hf = hasher(),
712                       const key_equal& __eql = key_equal());
713    unordered_multiset(initializer_list<value_type> __il, size_type __n,
714                       const hasher& __hf, const key_equal& __eql,
715                       const allocator_type& __a);
716    // ~unordered_multiset() = default;
717    // unordered_multiset& operator=(const unordered_multiset& __u) = default;
718#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
719    unordered_multiset& operator=(unordered_multiset&& __u);
720#endif
721    unordered_multiset& operator=(initializer_list<value_type> __il);
722
723    _LIBCPP_INLINE_VISIBILITY
724    allocator_type get_allocator() const
725        {return allocator_type(__table_.__node_alloc());}
726
727    _LIBCPP_INLINE_VISIBILITY
728    bool      empty() const {return __table_.size() == 0;}
729    _LIBCPP_INLINE_VISIBILITY
730    size_type size() const  {return __table_.size();}
731    _LIBCPP_INLINE_VISIBILITY
732    size_type max_size() const {return __table_.max_size();}
733
734    _LIBCPP_INLINE_VISIBILITY
735    iterator       begin()        {return __table_.begin();}
736    _LIBCPP_INLINE_VISIBILITY
737    iterator       end()          {return __table_.end();}
738    _LIBCPP_INLINE_VISIBILITY
739    const_iterator begin()  const {return __table_.begin();}
740    _LIBCPP_INLINE_VISIBILITY
741    const_iterator end()    const {return __table_.end();}
742    _LIBCPP_INLINE_VISIBILITY
743    const_iterator cbegin() const {return __table_.begin();}
744    _LIBCPP_INLINE_VISIBILITY
745    const_iterator cend()   const {return __table_.end();}
746
747#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
748    template <class... _Args>
749        _LIBCPP_INLINE_VISIBILITY
750        iterator emplace(_Args&&... __args)
751            {return __table_.__emplace_multi(_STD::forward<_Args>(__args)...);}
752    template <class... _Args>
753        _LIBCPP_INLINE_VISIBILITY
754        iterator emplace_hint(const_iterator __p, _Args&&... __args)
755            {return __table_.__emplace_hint_multi(__p, _STD::forward<_Args>(__args)...);}
756#endif  // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
757    _LIBCPP_INLINE_VISIBILITY
758    iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
759#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
760    _LIBCPP_INLINE_VISIBILITY
761    iterator insert(value_type&& __x) {return __table_.__insert_multi(_STD::move(__x));}
762#endif
763    _LIBCPP_INLINE_VISIBILITY
764    iterator insert(const_iterator __p, const value_type& __x)
765        {return __table_.__insert_multi(__p, __x);}
766#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
767    _LIBCPP_INLINE_VISIBILITY
768    iterator insert(const_iterator __p, value_type&& __x)
769        {return __table_.__insert_multi(__p, _STD::move(__x));}
770#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
771    template <class _InputIterator>
772        void insert(_InputIterator __first, _InputIterator __last);
773    _LIBCPP_INLINE_VISIBILITY
774    void insert(initializer_list<value_type> __il)
775        {insert(__il.begin(), __il.end());}
776
777    _LIBCPP_INLINE_VISIBILITY
778    iterator erase(const_iterator __p) {return __table_.erase(__p);}
779    _LIBCPP_INLINE_VISIBILITY
780    size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
781    _LIBCPP_INLINE_VISIBILITY
782    iterator erase(const_iterator __first, const_iterator __last)
783        {return __table_.erase(__first, __last);}
784    _LIBCPP_INLINE_VISIBILITY
785    void clear() {__table_.clear();}
786
787    _LIBCPP_INLINE_VISIBILITY
788    void swap(unordered_multiset& __u) {__table_.swap(__u.__table_);}
789
790    _LIBCPP_INLINE_VISIBILITY
791    hasher hash_function() const {return __table_.hash_function();}
792    _LIBCPP_INLINE_VISIBILITY
793    key_equal key_eq() const {return __table_.key_eq();}
794
795    _LIBCPP_INLINE_VISIBILITY
796    iterator       find(const key_type& __k)       {return __table_.find(__k);}
797    _LIBCPP_INLINE_VISIBILITY
798    const_iterator find(const key_type& __k) const {return __table_.find(__k);}
799    _LIBCPP_INLINE_VISIBILITY
800    size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
801    _LIBCPP_INLINE_VISIBILITY
802    pair<iterator, iterator>             equal_range(const key_type& __k)
803        {return __table_.__equal_range_multi(__k);}
804    _LIBCPP_INLINE_VISIBILITY
805    pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
806        {return __table_.__equal_range_multi(__k);}
807
808    _LIBCPP_INLINE_VISIBILITY
809    size_type bucket_count() const {return __table_.bucket_count();}
810    _LIBCPP_INLINE_VISIBILITY
811    size_type max_bucket_count() const {return __table_.max_bucket_count();}
812
813    _LIBCPP_INLINE_VISIBILITY
814    size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);}
815    _LIBCPP_INLINE_VISIBILITY
816    size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
817
818    _LIBCPP_INLINE_VISIBILITY
819    local_iterator       begin(size_type __n)        {return __table_.begin(__n);}
820    _LIBCPP_INLINE_VISIBILITY
821    local_iterator       end(size_type __n)          {return __table_.end(__n);}
822    _LIBCPP_INLINE_VISIBILITY
823    const_local_iterator begin(size_type __n) const  {return __table_.cbegin(__n);}
824    _LIBCPP_INLINE_VISIBILITY
825    const_local_iterator end(size_type __n) const    {return __table_.cend(__n);}
826    _LIBCPP_INLINE_VISIBILITY
827    const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
828    _LIBCPP_INLINE_VISIBILITY
829    const_local_iterator cend(size_type __n) const   {return __table_.cend(__n);}
830
831    _LIBCPP_INLINE_VISIBILITY
832    float load_factor() const {return __table_.load_factor();}
833    _LIBCPP_INLINE_VISIBILITY
834    float max_load_factor() const {return __table_.max_load_factor();}
835    _LIBCPP_INLINE_VISIBILITY
836    void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
837    _LIBCPP_INLINE_VISIBILITY
838    void rehash(size_type __n) {__table_.rehash(__n);}
839    _LIBCPP_INLINE_VISIBILITY
840    void reserve(size_type __n) {__table_.reserve(__n);}
841};
842
843template <class _Value, class _Hash, class _Pred, class _Alloc>
844unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
845        size_type __n, const hasher& __hf, const key_equal& __eql)
846    : __table_(__hf, __eql)
847{
848    __table_.rehash(__n);
849}
850
851template <class _Value, class _Hash, class _Pred, class _Alloc>
852unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
853        size_type __n, const hasher& __hf, const key_equal& __eql,
854        const allocator_type& __a)
855    : __table_(__hf, __eql, __a)
856{
857    __table_.rehash(__n);
858}
859
860template <class _Value, class _Hash, class _Pred, class _Alloc>
861template <class _InputIterator>
862unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
863        _InputIterator __first, _InputIterator __last)
864{
865    insert(__first, __last);
866}
867
868template <class _Value, class _Hash, class _Pred, class _Alloc>
869template <class _InputIterator>
870unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
871        _InputIterator __first, _InputIterator __last, size_type __n,
872        const hasher& __hf, const key_equal& __eql)
873    : __table_(__hf, __eql)
874{
875    __table_.rehash(__n);
876    insert(__first, __last);
877}
878
879template <class _Value, class _Hash, class _Pred, class _Alloc>
880template <class _InputIterator>
881unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
882        _InputIterator __first, _InputIterator __last, size_type __n,
883        const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
884    : __table_(__hf, __eql, __a)
885{
886    __table_.rehash(__n);
887    insert(__first, __last);
888}
889
890template <class _Value, class _Hash, class _Pred, class _Alloc>
891inline _LIBCPP_INLINE_VISIBILITY
892unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
893        const allocator_type& __a)
894    : __table_(__a)
895{
896}
897
898template <class _Value, class _Hash, class _Pred, class _Alloc>
899unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
900        const unordered_multiset& __u)
901    : __table_(__u.__table_)
902{
903    __table_.rehash(__u.bucket_count());
904    insert(__u.begin(), __u.end());
905}
906
907template <class _Value, class _Hash, class _Pred, class _Alloc>
908unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
909        const unordered_multiset& __u, const allocator_type& __a)
910    : __table_(__u.__table_, __a)
911{
912    __table_.rehash(__u.bucket_count());
913    insert(__u.begin(), __u.end());
914}
915
916#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
917
918template <class _Value, class _Hash, class _Pred, class _Alloc>
919inline _LIBCPP_INLINE_VISIBILITY
920unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
921        unordered_multiset&& __u)
922    : __table_(_STD::move(__u.__table_))
923{
924}
925
926template <class _Value, class _Hash, class _Pred, class _Alloc>
927unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
928        unordered_multiset&& __u, const allocator_type& __a)
929    : __table_(_STD::move(__u.__table_), __a)
930{
931    if (__a != __u.get_allocator())
932    {
933        iterator __i = __u.begin();
934        while (__u.size() != 0)
935            __table_.__insert_multi(_STD::move(__u.__table_.remove(__i++)->__value_));
936    }
937}
938
939#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
940
941template <class _Value, class _Hash, class _Pred, class _Alloc>
942unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
943        initializer_list<value_type> __il)
944{
945    insert(__il.begin(), __il.end());
946}
947
948template <class _Value, class _Hash, class _Pred, class _Alloc>
949unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
950        initializer_list<value_type> __il, size_type __n, const hasher& __hf,
951        const key_equal& __eql)
952    : __table_(__hf, __eql)
953{
954    __table_.rehash(__n);
955    insert(__il.begin(), __il.end());
956}
957
958template <class _Value, class _Hash, class _Pred, class _Alloc>
959unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
960        initializer_list<value_type> __il, size_type __n, const hasher& __hf,
961        const key_equal& __eql, const allocator_type& __a)
962    : __table_(__hf, __eql, __a)
963{
964    __table_.rehash(__n);
965    insert(__il.begin(), __il.end());
966}
967
968#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
969
970template <class _Value, class _Hash, class _Pred, class _Alloc>
971inline _LIBCPP_INLINE_VISIBILITY
972unordered_multiset<_Value, _Hash, _Pred, _Alloc>&
973unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(
974        unordered_multiset&& __u)
975{
976    __table_ = _STD::move(__u.__table_);
977    return *this;
978}
979
980#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
981
982template <class _Value, class _Hash, class _Pred, class _Alloc>
983inline
984unordered_multiset<_Value, _Hash, _Pred, _Alloc>&
985unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(
986        initializer_list<value_type> __il)
987{
988    __table_.__assign_multi(__il.begin(), __il.end());
989    return *this;
990}
991
992template <class _Value, class _Hash, class _Pred, class _Alloc>
993template <class _InputIterator>
994inline _LIBCPP_INLINE_VISIBILITY
995void
996unordered_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
997                                                         _InputIterator __last)
998{
999    for (; __first != __last; ++__first)
1000        __table_.__insert_multi(*__first);
1001}
1002
1003template <class _Value, class _Hash, class _Pred, class _Alloc>
1004inline _LIBCPP_INLINE_VISIBILITY
1005void
1006swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1007     unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1008{
1009    __x.swap(__y);
1010}
1011
1012template <class _Value, class _Hash, class _Pred, class _Alloc>
1013bool
1014operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1015           const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1016{
1017    if (__x.size() != __y.size())
1018        return false;
1019    typedef typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator
1020                                                                 const_iterator;
1021    typedef pair<const_iterator, const_iterator> _EqRng;
1022    for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;)
1023    {
1024        _EqRng __xeq = __x.equal_range(*__i);
1025        _EqRng __yeq = __y.equal_range(*__i);
1026        if (_STD::distance(__xeq.first, __xeq.second) !=
1027            _STD::distance(__yeq.first, __yeq.second) ||
1028                  !_STD::is_permutation(__xeq.first, __xeq.second, __yeq.first))
1029            return false;
1030        __i = __xeq.second;
1031    }
1032    return true;
1033}
1034
1035template <class _Value, class _Hash, class _Pred, class _Alloc>
1036inline _LIBCPP_INLINE_VISIBILITY
1037bool
1038operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1039           const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1040{
1041    return !(__x == __y);
1042}
1043
1044_LIBCPP_END_NAMESPACE_STD
1045
1046#endif  // _LIBCPP_UNORDERED_SET
1047