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