unordered_set revision 249989 
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#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
309#pragma GCC system_header
310#endif
311
312_LIBCPP_BEGIN_NAMESPACE_STD
313
314template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>,
315          class _Alloc = allocator<_Value> >
316class _LIBCPP_TYPE_VIS unordered_set
317{
318public:
319    // types
320    typedef _Value                                                     key_type;
321    typedef key_type                                                   value_type;
322    typedef _Hash                                                      hasher;
323    typedef _Pred                                                      key_equal;
324    typedef _Alloc                                                     allocator_type;
325    typedef value_type&                                                reference;
326    typedef const value_type&                                          const_reference;
327
328private:
329    typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
330
331    __table __table_;
332
333public:
334    typedef typename __table::pointer         pointer;
335    typedef typename __table::const_pointer   const_pointer;
336    typedef typename __table::size_type       size_type;
337    typedef typename __table::difference_type difference_type;
338
339    typedef typename __table::const_iterator       iterator;
340    typedef typename __table::const_iterator       const_iterator;
341    typedef typename __table::const_local_iterator local_iterator;
342    typedef typename __table::const_local_iterator const_local_iterator;
343
344    _LIBCPP_INLINE_VISIBILITY
345    unordered_set()
346        _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
347        {} // = default;
348    explicit unordered_set(size_type __n, const hasher& __hf = hasher(),
349                           const key_equal& __eql = key_equal());
350    unordered_set(size_type __n, const hasher& __hf, const key_equal& __eql,
351                  const allocator_type& __a);
352    template <class _InputIterator>
353        unordered_set(_InputIterator __first, _InputIterator __last);
354    template <class _InputIterator>
355        unordered_set(_InputIterator __first, _InputIterator __last,
356                      size_type __n, const hasher& __hf = hasher(),
357                      const key_equal& __eql = key_equal());
358    template <class _InputIterator>
359        unordered_set(_InputIterator __first, _InputIterator __last,
360                      size_type __n, const hasher& __hf, const key_equal& __eql,
361                      const allocator_type& __a);
362    explicit unordered_set(const allocator_type& __a);
363    unordered_set(const unordered_set& __u);
364    unordered_set(const unordered_set& __u, const allocator_type& __a);
365#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
366    unordered_set(unordered_set&& __u)
367        _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
368    unordered_set(unordered_set&& __u, const allocator_type& __a);
369#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
370#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
371    unordered_set(initializer_list<value_type> __il);
372    unordered_set(initializer_list<value_type> __il, size_type __n,
373                  const hasher& __hf = hasher(),
374                  const key_equal& __eql = key_equal());
375    unordered_set(initializer_list<value_type> __il, size_type __n,
376                  const hasher& __hf, const key_equal& __eql,
377                  const allocator_type& __a);
378#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
379    // ~unordered_set() = default;
380    _LIBCPP_INLINE_VISIBILITY
381    unordered_set& operator=(const unordered_set& __u)
382    {
383        __table_ = __u.__table_;
384        return *this;
385    }
386#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
387    unordered_set& operator=(unordered_set&& __u)
388        _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
389#endif
390#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
391    unordered_set& operator=(initializer_list<value_type> __il);
392#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
393
394    _LIBCPP_INLINE_VISIBILITY
395    allocator_type get_allocator() const _NOEXCEPT
396        {return allocator_type(__table_.__node_alloc());}
397
398    _LIBCPP_INLINE_VISIBILITY
399    bool      empty() const _NOEXCEPT {return __table_.size() == 0;}
400    _LIBCPP_INLINE_VISIBILITY
401    size_type size() const _NOEXCEPT  {return __table_.size();}
402    _LIBCPP_INLINE_VISIBILITY
403    size_type max_size() const _NOEXCEPT {return __table_.max_size();}
404
405    _LIBCPP_INLINE_VISIBILITY
406    iterator       begin() _NOEXCEPT        {return __table_.begin();}
407    _LIBCPP_INLINE_VISIBILITY
408    iterator       end() _NOEXCEPT          {return __table_.end();}
409    _LIBCPP_INLINE_VISIBILITY
410    const_iterator begin()  const _NOEXCEPT {return __table_.begin();}
411    _LIBCPP_INLINE_VISIBILITY
412    const_iterator end()    const _NOEXCEPT {return __table_.end();}
413    _LIBCPP_INLINE_VISIBILITY
414    const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
415    _LIBCPP_INLINE_VISIBILITY
416    const_iterator cend()   const _NOEXCEPT {return __table_.end();}
417
418#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
419    template <class... _Args>
420        _LIBCPP_INLINE_VISIBILITY
421        pair<iterator, bool> emplace(_Args&&... __args)
422            {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...);}
423    template <class... _Args>
424        _LIBCPP_INLINE_VISIBILITY
425        iterator emplace_hint(const_iterator, _Args&&... __args)
426            {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first;}
427#endif  // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
428    _LIBCPP_INLINE_VISIBILITY
429    pair<iterator, bool> insert(const value_type& __x)
430        {return __table_.__insert_unique(__x);}
431#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
432    _LIBCPP_INLINE_VISIBILITY
433    pair<iterator, bool> insert(value_type&& __x)
434        {return __table_.__insert_unique(_VSTD::move(__x));}
435#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
436    _LIBCPP_INLINE_VISIBILITY
437    iterator insert(const_iterator, const value_type& __x)
438        {return insert(__x).first;}
439#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
440    _LIBCPP_INLINE_VISIBILITY
441    iterator insert(const_iterator, value_type&& __x)
442        {return insert(_VSTD::move(__x)).first;}
443#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
444    template <class _InputIterator>
445        void insert(_InputIterator __first, _InputIterator __last);
446#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
447    _LIBCPP_INLINE_VISIBILITY
448    void insert(initializer_list<value_type> __il)
449        {insert(__il.begin(), __il.end());}
450#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
451
452    _LIBCPP_INLINE_VISIBILITY
453    iterator erase(const_iterator __p) {return __table_.erase(__p);}
454    _LIBCPP_INLINE_VISIBILITY
455    size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
456    _LIBCPP_INLINE_VISIBILITY
457    iterator erase(const_iterator __first, const_iterator __last)
458        {return __table_.erase(__first, __last);}
459    _LIBCPP_INLINE_VISIBILITY
460    void clear() _NOEXCEPT {__table_.clear();}
461
462    _LIBCPP_INLINE_VISIBILITY
463    void swap(unordered_set& __u)
464        _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
465        {__table_.swap(__u.__table_);}
466
467    _LIBCPP_INLINE_VISIBILITY
468    hasher hash_function() const {return __table_.hash_function();}
469    _LIBCPP_INLINE_VISIBILITY
470    key_equal key_eq() const {return __table_.key_eq();}
471
472    _LIBCPP_INLINE_VISIBILITY
473    iterator       find(const key_type& __k)       {return __table_.find(__k);}
474    _LIBCPP_INLINE_VISIBILITY
475    const_iterator find(const key_type& __k) const {return __table_.find(__k);}
476    _LIBCPP_INLINE_VISIBILITY
477    size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
478    _LIBCPP_INLINE_VISIBILITY
479    pair<iterator, iterator>             equal_range(const key_type& __k)
480        {return __table_.__equal_range_unique(__k);}
481    _LIBCPP_INLINE_VISIBILITY
482    pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
483        {return __table_.__equal_range_unique(__k);}
484
485    _LIBCPP_INLINE_VISIBILITY
486    size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
487    _LIBCPP_INLINE_VISIBILITY
488    size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
489
490    _LIBCPP_INLINE_VISIBILITY
491    size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);}
492    _LIBCPP_INLINE_VISIBILITY
493    size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
494
495    _LIBCPP_INLINE_VISIBILITY
496    local_iterator       begin(size_type __n)        {return __table_.begin(__n);}
497    _LIBCPP_INLINE_VISIBILITY
498    local_iterator       end(size_type __n)          {return __table_.end(__n);}
499    _LIBCPP_INLINE_VISIBILITY
500    const_local_iterator begin(size_type __n) const  {return __table_.cbegin(__n);}
501    _LIBCPP_INLINE_VISIBILITY
502    const_local_iterator end(size_type __n) const    {return __table_.cend(__n);}
503    _LIBCPP_INLINE_VISIBILITY
504    const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
505    _LIBCPP_INLINE_VISIBILITY
506    const_local_iterator cend(size_type __n) const   {return __table_.cend(__n);}
507
508    _LIBCPP_INLINE_VISIBILITY
509    float load_factor() const _NOEXCEPT {return __table_.load_factor();}
510    _LIBCPP_INLINE_VISIBILITY
511    float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
512    _LIBCPP_INLINE_VISIBILITY
513    void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
514    _LIBCPP_INLINE_VISIBILITY
515    void rehash(size_type __n) {__table_.rehash(__n);}
516    _LIBCPP_INLINE_VISIBILITY
517    void reserve(size_type __n) {__table_.reserve(__n);}
518};
519
520template <class _Value, class _Hash, class _Pred, class _Alloc>
521unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n,
522        const hasher& __hf, const key_equal& __eql)
523    : __table_(__hf, __eql)
524{
525    __table_.rehash(__n);
526}
527
528template <class _Value, class _Hash, class _Pred, class _Alloc>
529unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n,
530        const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
531    : __table_(__hf, __eql, __a)
532{
533    __table_.rehash(__n);
534}
535
536template <class _Value, class _Hash, class _Pred, class _Alloc>
537template <class _InputIterator>
538unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
539        _InputIterator __first, _InputIterator __last)
540{
541    insert(__first, __last);
542}
543
544template <class _Value, class _Hash, class _Pred, class _Alloc>
545template <class _InputIterator>
546unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
547        _InputIterator __first, _InputIterator __last, size_type __n,
548        const hasher& __hf, const key_equal& __eql)
549    : __table_(__hf, __eql)
550{
551    __table_.rehash(__n);
552    insert(__first, __last);
553}
554
555template <class _Value, class _Hash, class _Pred, class _Alloc>
556template <class _InputIterator>
557unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
558        _InputIterator __first, _InputIterator __last, size_type __n,
559        const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
560    : __table_(__hf, __eql, __a)
561{
562    __table_.rehash(__n);
563    insert(__first, __last);
564}
565
566template <class _Value, class _Hash, class _Pred, class _Alloc>
567inline _LIBCPP_INLINE_VISIBILITY
568unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
569        const allocator_type& __a)
570    : __table_(__a)
571{
572}
573
574template <class _Value, class _Hash, class _Pred, class _Alloc>
575unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
576        const unordered_set& __u)
577    : __table_(__u.__table_)
578{
579    __table_.rehash(__u.bucket_count());
580    insert(__u.begin(), __u.end());
581}
582
583template <class _Value, class _Hash, class _Pred, class _Alloc>
584unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
585        const unordered_set& __u, const allocator_type& __a)
586    : __table_(__u.__table_, __a)
587{
588    __table_.rehash(__u.bucket_count());
589    insert(__u.begin(), __u.end());
590}
591
592#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
593
594template <class _Value, class _Hash, class _Pred, class _Alloc>
595inline _LIBCPP_INLINE_VISIBILITY
596unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
597        unordered_set&& __u)
598    _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
599    : __table_(_VSTD::move(__u.__table_))
600{
601}
602
603template <class _Value, class _Hash, class _Pred, class _Alloc>
604unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
605        unordered_set&& __u, const allocator_type& __a)
606    : __table_(_VSTD::move(__u.__table_), __a)
607{
608    if (__a != __u.get_allocator())
609    {
610        iterator __i = __u.begin();
611        while (__u.size() != 0)
612            __table_.__insert_unique(_VSTD::move(__u.__table_.remove(__i++)->__value_));
613    }
614}
615
616#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
617
618#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
619
620template <class _Value, class _Hash, class _Pred, class _Alloc>
621unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
622        initializer_list<value_type> __il)
623{
624    insert(__il.begin(), __il.end());
625}
626
627template <class _Value, class _Hash, class _Pred, class _Alloc>
628unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
629        initializer_list<value_type> __il, size_type __n, const hasher& __hf,
630        const key_equal& __eql)
631    : __table_(__hf, __eql)
632{
633    __table_.rehash(__n);
634    insert(__il.begin(), __il.end());
635}
636
637template <class _Value, class _Hash, class _Pred, class _Alloc>
638unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
639        initializer_list<value_type> __il, size_type __n, const hasher& __hf,
640        const key_equal& __eql, const allocator_type& __a)
641    : __table_(__hf, __eql, __a)
642{
643    __table_.rehash(__n);
644    insert(__il.begin(), __il.end());
645}
646
647#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
648
649#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
650
651template <class _Value, class _Hash, class _Pred, class _Alloc>
652inline _LIBCPP_INLINE_VISIBILITY
653unordered_set<_Value, _Hash, _Pred, _Alloc>&
654unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(unordered_set&& __u)
655    _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
656{
657    __table_ = _VSTD::move(__u.__table_);
658    return *this;
659}
660
661#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
662
663#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
664
665template <class _Value, class _Hash, class _Pred, class _Alloc>
666inline _LIBCPP_INLINE_VISIBILITY
667unordered_set<_Value, _Hash, _Pred, _Alloc>&
668unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(
669        initializer_list<value_type> __il)
670{
671    __table_.__assign_unique(__il.begin(), __il.end());
672    return *this;
673}
674
675#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
676
677template <class _Value, class _Hash, class _Pred, class _Alloc>
678template <class _InputIterator>
679inline _LIBCPP_INLINE_VISIBILITY
680void
681unordered_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
682                                                    _InputIterator __last)
683{
684    for (; __first != __last; ++__first)
685        __table_.__insert_unique(*__first);
686}
687
688template <class _Value, class _Hash, class _Pred, class _Alloc>
689inline _LIBCPP_INLINE_VISIBILITY
690void
691swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
692     unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
693    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
694{
695    __x.swap(__y);
696}
697
698template <class _Value, class _Hash, class _Pred, class _Alloc>
699bool
700operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
701           const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
702{
703    if (__x.size() != __y.size())
704        return false;
705    typedef typename unordered_set<_Value, _Hash, _Pred, _Alloc>::const_iterator
706                                                                 const_iterator;
707    for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();
708            __i != __ex; ++__i)
709    {
710        const_iterator __j = __y.find(*__i);
711        if (__j == __ey || !(*__i == *__j))
712            return false;
713    }
714    return true;
715}
716
717template <class _Value, class _Hash, class _Pred, class _Alloc>
718inline _LIBCPP_INLINE_VISIBILITY
719bool
720operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
721           const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
722{
723    return !(__x == __y);
724}
725
726template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>,
727          class _Alloc = allocator<_Value> >
728class _LIBCPP_TYPE_VIS unordered_multiset
729{
730public:
731    // types
732    typedef _Value                                                     key_type;
733    typedef key_type                                                   value_type;
734    typedef _Hash                                                      hasher;
735    typedef _Pred                                                      key_equal;
736    typedef _Alloc                                                     allocator_type;
737    typedef value_type&                                                reference;
738    typedef const value_type&                                          const_reference;
739
740private:
741    typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
742
743    __table __table_;
744
745public:
746    typedef typename __table::pointer         pointer;
747    typedef typename __table::const_pointer   const_pointer;
748    typedef typename __table::size_type       size_type;
749    typedef typename __table::difference_type difference_type;
750
751    typedef typename __table::const_iterator       iterator;
752    typedef typename __table::const_iterator       const_iterator;
753    typedef typename __table::const_local_iterator local_iterator;
754    typedef typename __table::const_local_iterator const_local_iterator;
755
756    _LIBCPP_INLINE_VISIBILITY
757    unordered_multiset()
758        _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
759        {} // = default
760    explicit unordered_multiset(size_type __n, const hasher& __hf = hasher(),
761                                const key_equal& __eql = key_equal());
762    unordered_multiset(size_type __n, const hasher& __hf,
763                       const key_equal& __eql, const allocator_type& __a);
764    template <class _InputIterator>
765        unordered_multiset(_InputIterator __first, _InputIterator __last);
766    template <class _InputIterator>
767        unordered_multiset(_InputIterator __first, _InputIterator __last,
768                      size_type __n, const hasher& __hf = hasher(),
769                      const key_equal& __eql = key_equal());
770    template <class _InputIterator>
771        unordered_multiset(_InputIterator __first, _InputIterator __last,
772                      size_type __n , const hasher& __hf,
773                      const key_equal& __eql, const allocator_type& __a);
774    explicit unordered_multiset(const allocator_type& __a);
775    unordered_multiset(const unordered_multiset& __u);
776    unordered_multiset(const unordered_multiset& __u, const allocator_type& __a);
777#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
778    unordered_multiset(unordered_multiset&& __u)
779        _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
780    unordered_multiset(unordered_multiset&& __u, const allocator_type& __a);
781#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
782#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
783    unordered_multiset(initializer_list<value_type> __il);
784    unordered_multiset(initializer_list<value_type> __il, size_type __n,
785                       const hasher& __hf = hasher(),
786                       const key_equal& __eql = key_equal());
787    unordered_multiset(initializer_list<value_type> __il, size_type __n,
788                       const hasher& __hf, const key_equal& __eql,
789                       const allocator_type& __a);
790#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
791    // ~unordered_multiset() = default;
792    _LIBCPP_INLINE_VISIBILITY
793    unordered_multiset& operator=(const unordered_multiset& __u)
794    {
795        __table_ = __u.__table_;
796        return *this;
797    }
798#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
799    unordered_multiset& operator=(unordered_multiset&& __u)
800        _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
801#endif
802#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
803    unordered_multiset& operator=(initializer_list<value_type> __il);
804#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
805
806    _LIBCPP_INLINE_VISIBILITY
807    allocator_type get_allocator() const _NOEXCEPT
808        {return allocator_type(__table_.__node_alloc());}
809
810    _LIBCPP_INLINE_VISIBILITY
811    bool      empty() const _NOEXCEPT {return __table_.size() == 0;}
812    _LIBCPP_INLINE_VISIBILITY
813    size_type size() const _NOEXCEPT  {return __table_.size();}
814    _LIBCPP_INLINE_VISIBILITY
815    size_type max_size() const _NOEXCEPT {return __table_.max_size();}
816
817    _LIBCPP_INLINE_VISIBILITY
818    iterator       begin() _NOEXCEPT        {return __table_.begin();}
819    _LIBCPP_INLINE_VISIBILITY
820    iterator       end() _NOEXCEPT          {return __table_.end();}
821    _LIBCPP_INLINE_VISIBILITY
822    const_iterator begin()  const _NOEXCEPT {return __table_.begin();}
823    _LIBCPP_INLINE_VISIBILITY
824    const_iterator end()    const _NOEXCEPT {return __table_.end();}
825    _LIBCPP_INLINE_VISIBILITY
826    const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
827    _LIBCPP_INLINE_VISIBILITY
828    const_iterator cend()   const _NOEXCEPT {return __table_.end();}
829
830#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
831    template <class... _Args>
832        _LIBCPP_INLINE_VISIBILITY
833        iterator emplace(_Args&&... __args)
834            {return __table_.__emplace_multi(_VSTD::forward<_Args>(__args)...);}
835    template <class... _Args>
836        _LIBCPP_INLINE_VISIBILITY
837        iterator emplace_hint(const_iterator __p, _Args&&... __args)
838            {return __table_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);}
839#endif  // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
840    _LIBCPP_INLINE_VISIBILITY
841    iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
842#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
843    _LIBCPP_INLINE_VISIBILITY
844    iterator insert(value_type&& __x) {return __table_.__insert_multi(_VSTD::move(__x));}
845#endif
846    _LIBCPP_INLINE_VISIBILITY
847    iterator insert(const_iterator __p, const value_type& __x)
848        {return __table_.__insert_multi(__p, __x);}
849#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
850    _LIBCPP_INLINE_VISIBILITY
851    iterator insert(const_iterator __p, value_type&& __x)
852        {return __table_.__insert_multi(__p, _VSTD::move(__x));}
853#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
854    template <class _InputIterator>
855        void insert(_InputIterator __first, _InputIterator __last);
856#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
857    _LIBCPP_INLINE_VISIBILITY
858    void insert(initializer_list<value_type> __il)
859        {insert(__il.begin(), __il.end());}
860#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
861
862    _LIBCPP_INLINE_VISIBILITY
863    iterator erase(const_iterator __p) {return __table_.erase(__p);}
864    _LIBCPP_INLINE_VISIBILITY
865    size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
866    _LIBCPP_INLINE_VISIBILITY
867    iterator erase(const_iterator __first, const_iterator __last)
868        {return __table_.erase(__first, __last);}
869    _LIBCPP_INLINE_VISIBILITY
870    void clear() _NOEXCEPT {__table_.clear();}
871
872    _LIBCPP_INLINE_VISIBILITY
873    void swap(unordered_multiset& __u)
874        _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
875        {__table_.swap(__u.__table_);}
876
877    _LIBCPP_INLINE_VISIBILITY
878    hasher hash_function() const {return __table_.hash_function();}
879    _LIBCPP_INLINE_VISIBILITY
880    key_equal key_eq() const {return __table_.key_eq();}
881
882    _LIBCPP_INLINE_VISIBILITY
883    iterator       find(const key_type& __k)       {return __table_.find(__k);}
884    _LIBCPP_INLINE_VISIBILITY
885    const_iterator find(const key_type& __k) const {return __table_.find(__k);}
886    _LIBCPP_INLINE_VISIBILITY
887    size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
888    _LIBCPP_INLINE_VISIBILITY
889    pair<iterator, iterator>             equal_range(const key_type& __k)
890        {return __table_.__equal_range_multi(__k);}
891    _LIBCPP_INLINE_VISIBILITY
892    pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
893        {return __table_.__equal_range_multi(__k);}
894
895    _LIBCPP_INLINE_VISIBILITY
896    size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
897    _LIBCPP_INLINE_VISIBILITY
898    size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
899
900    _LIBCPP_INLINE_VISIBILITY
901    size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);}
902    _LIBCPP_INLINE_VISIBILITY
903    size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
904
905    _LIBCPP_INLINE_VISIBILITY
906    local_iterator       begin(size_type __n)        {return __table_.begin(__n);}
907    _LIBCPP_INLINE_VISIBILITY
908    local_iterator       end(size_type __n)          {return __table_.end(__n);}
909    _LIBCPP_INLINE_VISIBILITY
910    const_local_iterator begin(size_type __n) const  {return __table_.cbegin(__n);}
911    _LIBCPP_INLINE_VISIBILITY
912    const_local_iterator end(size_type __n) const    {return __table_.cend(__n);}
913    _LIBCPP_INLINE_VISIBILITY
914    const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
915    _LIBCPP_INLINE_VISIBILITY
916    const_local_iterator cend(size_type __n) const   {return __table_.cend(__n);}
917
918    _LIBCPP_INLINE_VISIBILITY
919    float load_factor() const _NOEXCEPT {return __table_.load_factor();}
920    _LIBCPP_INLINE_VISIBILITY
921    float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
922    _LIBCPP_INLINE_VISIBILITY
923    void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
924    _LIBCPP_INLINE_VISIBILITY
925    void rehash(size_type __n) {__table_.rehash(__n);}
926    _LIBCPP_INLINE_VISIBILITY
927    void reserve(size_type __n) {__table_.reserve(__n);}
928};
929
930template <class _Value, class _Hash, class _Pred, class _Alloc>
931unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
932        size_type __n, const hasher& __hf, const key_equal& __eql)
933    : __table_(__hf, __eql)
934{
935    __table_.rehash(__n);
936}
937
938template <class _Value, class _Hash, class _Pred, class _Alloc>
939unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
940        size_type __n, const hasher& __hf, const key_equal& __eql,
941        const allocator_type& __a)
942    : __table_(__hf, __eql, __a)
943{
944    __table_.rehash(__n);
945}
946
947template <class _Value, class _Hash, class _Pred, class _Alloc>
948template <class _InputIterator>
949unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
950        _InputIterator __first, _InputIterator __last)
951{
952    insert(__first, __last);
953}
954
955template <class _Value, class _Hash, class _Pred, class _Alloc>
956template <class _InputIterator>
957unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
958        _InputIterator __first, _InputIterator __last, size_type __n,
959        const hasher& __hf, const key_equal& __eql)
960    : __table_(__hf, __eql)
961{
962    __table_.rehash(__n);
963    insert(__first, __last);
964}
965
966template <class _Value, class _Hash, class _Pred, class _Alloc>
967template <class _InputIterator>
968unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
969        _InputIterator __first, _InputIterator __last, size_type __n,
970        const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
971    : __table_(__hf, __eql, __a)
972{
973    __table_.rehash(__n);
974    insert(__first, __last);
975}
976
977template <class _Value, class _Hash, class _Pred, class _Alloc>
978inline _LIBCPP_INLINE_VISIBILITY
979unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
980        const allocator_type& __a)
981    : __table_(__a)
982{
983}
984
985template <class _Value, class _Hash, class _Pred, class _Alloc>
986unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
987        const unordered_multiset& __u)
988    : __table_(__u.__table_)
989{
990    __table_.rehash(__u.bucket_count());
991    insert(__u.begin(), __u.end());
992}
993
994template <class _Value, class _Hash, class _Pred, class _Alloc>
995unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
996        const unordered_multiset& __u, const allocator_type& __a)
997    : __table_(__u.__table_, __a)
998{
999    __table_.rehash(__u.bucket_count());
1000    insert(__u.begin(), __u.end());
1001}
1002
1003#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1004
1005template <class _Value, class _Hash, class _Pred, class _Alloc>
1006inline _LIBCPP_INLINE_VISIBILITY
1007unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1008        unordered_multiset&& __u)
1009    _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
1010    : __table_(_VSTD::move(__u.__table_))
1011{
1012}
1013
1014template <class _Value, class _Hash, class _Pred, class _Alloc>
1015unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1016        unordered_multiset&& __u, const allocator_type& __a)
1017    : __table_(_VSTD::move(__u.__table_), __a)
1018{
1019    if (__a != __u.get_allocator())
1020    {
1021        iterator __i = __u.begin();
1022        while (__u.size() != 0)
1023            __table_.__insert_multi(_VSTD::move(__u.__table_.remove(__i++)->__value_));
1024    }
1025}
1026
1027#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1028
1029#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1030
1031template <class _Value, class _Hash, class _Pred, class _Alloc>
1032unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1033        initializer_list<value_type> __il)
1034{
1035    insert(__il.begin(), __il.end());
1036}
1037
1038template <class _Value, class _Hash, class _Pred, class _Alloc>
1039unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1040        initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1041        const key_equal& __eql)
1042    : __table_(__hf, __eql)
1043{
1044    __table_.rehash(__n);
1045    insert(__il.begin(), __il.end());
1046}
1047
1048template <class _Value, class _Hash, class _Pred, class _Alloc>
1049unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1050        initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1051        const key_equal& __eql, const allocator_type& __a)
1052    : __table_(__hf, __eql, __a)
1053{
1054    __table_.rehash(__n);
1055    insert(__il.begin(), __il.end());
1056}
1057
1058#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1059
1060#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1061
1062template <class _Value, class _Hash, class _Pred, class _Alloc>
1063inline _LIBCPP_INLINE_VISIBILITY
1064unordered_multiset<_Value, _Hash, _Pred, _Alloc>&
1065unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(
1066        unordered_multiset&& __u)
1067    _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
1068{
1069    __table_ = _VSTD::move(__u.__table_);
1070    return *this;
1071}
1072
1073#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1074
1075#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1076
1077template <class _Value, class _Hash, class _Pred, class _Alloc>
1078inline
1079unordered_multiset<_Value, _Hash, _Pred, _Alloc>&
1080unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(
1081        initializer_list<value_type> __il)
1082{
1083    __table_.__assign_multi(__il.begin(), __il.end());
1084    return *this;
1085}
1086
1087#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1088
1089template <class _Value, class _Hash, class _Pred, class _Alloc>
1090template <class _InputIterator>
1091inline _LIBCPP_INLINE_VISIBILITY
1092void
1093unordered_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
1094                                                         _InputIterator __last)
1095{
1096    for (; __first != __last; ++__first)
1097        __table_.__insert_multi(*__first);
1098}
1099
1100template <class _Value, class _Hash, class _Pred, class _Alloc>
1101inline _LIBCPP_INLINE_VISIBILITY
1102void
1103swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1104     unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1105    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1106{
1107    __x.swap(__y);
1108}
1109
1110template <class _Value, class _Hash, class _Pred, class _Alloc>
1111bool
1112operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1113           const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1114{
1115    if (__x.size() != __y.size())
1116        return false;
1117    typedef typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator
1118                                                                 const_iterator;
1119    typedef pair<const_iterator, const_iterator> _EqRng;
1120    for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;)
1121    {
1122        _EqRng __xeq = __x.equal_range(*__i);
1123        _EqRng __yeq = __y.equal_range(*__i);
1124        if (_VSTD::distance(__xeq.first, __xeq.second) !=
1125            _VSTD::distance(__yeq.first, __yeq.second) ||
1126                  !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first))
1127            return false;
1128        __i = __xeq.second;
1129    }
1130    return true;
1131}
1132
1133template <class _Value, class _Hash, class _Pred, class _Alloc>
1134inline _LIBCPP_INLINE_VISIBILITY
1135bool
1136operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1137           const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1138{
1139    return !(__x == __y);
1140}
1141
1142_LIBCPP_END_NAMESPACE_STD
1143
1144#endif  // _LIBCPP_UNORDERED_SET
1145