hash_set revision 249998 
1// -*- C++ -*-
2//===------------------------- hash_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_HASH_SET
12#define _LIBCPP_HASH_SET
13
14/*
15
16    hash_set synopsis
17
18namespace __gnu_cxx
19{
20
21template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,
22          class Alloc = allocator<Value>>
23class hash_set
24{
25public:
26    // types
27    typedef Value                                                      key_type;
28    typedef key_type                                                   value_type;
29    typedef Hash                                                       hasher;
30    typedef Pred                                                       key_equal;
31    typedef Alloc                                                      allocator_type;
32    typedef value_type&                                                reference;
33    typedef const value_type&                                          const_reference;
34    typedef typename allocator_traits<allocator_type>::pointer         pointer;
35    typedef typename allocator_traits<allocator_type>::const_pointer   const_pointer;
36    typedef typename allocator_traits<allocator_type>::size_type       size_type;
37    typedef typename allocator_traits<allocator_type>::difference_type difference_type;
38
39    typedef /unspecified/ iterator;
40    typedef /unspecified/ const_iterator;
41
42    explicit hash_set(size_type n = 193, const hasher& hf = hasher(),
43                           const key_equal& eql = key_equal(),
44                           const allocator_type& a = allocator_type());
45    template <class InputIterator>
46        hash_set(InputIterator f, InputIterator l,
47                      size_type n = 193, const hasher& hf = hasher(),
48                      const key_equal& eql = key_equal(),
49                      const allocator_type& a = allocator_type());
50    hash_set(const hash_set&);
51    ~hash_set();
52    hash_set& operator=(const hash_set&);
53
54    allocator_type get_allocator() const;
55
56    bool      empty() const;
57    size_type size() const;
58    size_type max_size() const;
59
60    iterator       begin();
61    iterator       end();
62    const_iterator begin()  const;
63    const_iterator end()    const;
64
65    pair<iterator, bool> insert(const value_type& obj);
66    template <class InputIterator>
67        void insert(InputIterator first, InputIterator last);
68
69    void erase(const_iterator position);
70    size_type erase(const key_type& k);
71    void erase(const_iterator first, const_iterator last);
72    void clear();
73
74    void swap(hash_set&);
75
76    hasher hash_funct() const;
77    key_equal key_eq() const;
78
79    iterator       find(const key_type& k);
80    const_iterator find(const key_type& k) const;
81    size_type count(const key_type& k) const;
82    pair<iterator, iterator>             equal_range(const key_type& k);
83    pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
84
85    size_type bucket_count() const;
86    size_type max_bucket_count() const;
87
88    size_type elems_in_bucket(size_type n) const;
89
90    void resize(size_type n);
91};
92
93template <class Value, class Hash, class Pred, class Alloc>
94    void swap(hash_set<Value, Hash, Pred, Alloc>& x,
95              hash_set<Value, Hash, Pred, Alloc>& y);
96
97template <class Value, class Hash, class Pred, class Alloc>
98    bool
99    operator==(const hash_set<Value, Hash, Pred, Alloc>& x,
100               const hash_set<Value, Hash, Pred, Alloc>& y);
101
102template <class Value, class Hash, class Pred, class Alloc>
103    bool
104    operator!=(const hash_set<Value, Hash, Pred, Alloc>& x,
105               const hash_set<Value, Hash, Pred, Alloc>& y);
106
107template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,
108          class Alloc = allocator<Value>>
109class hash_multiset
110{
111public:
112    // types
113    typedef Value                                                      key_type;
114    typedef key_type                                                   value_type;
115    typedef Hash                                                       hasher;
116    typedef Pred                                                       key_equal;
117    typedef Alloc                                                      allocator_type;
118    typedef value_type&                                                reference;
119    typedef const value_type&                                          const_reference;
120    typedef typename allocator_traits<allocator_type>::pointer         pointer;
121    typedef typename allocator_traits<allocator_type>::const_pointer   const_pointer;
122    typedef typename allocator_traits<allocator_type>::size_type       size_type;
123    typedef typename allocator_traits<allocator_type>::difference_type difference_type;
124
125    typedef /unspecified/ iterator;
126    typedef /unspecified/ const_iterator;
127
128    explicit hash_multiset(size_type n = 193, const hasher& hf = hasher(),
129                           const key_equal& eql = key_equal(),
130                           const allocator_type& a = allocator_type());
131    template <class InputIterator>
132        hash_multiset(InputIterator f, InputIterator l,
133                      size_type n = 193, const hasher& hf = hasher(),
134                      const key_equal& eql = key_equal(),
135                      const allocator_type& a = allocator_type());
136    hash_multiset(const hash_multiset&);
137    ~hash_multiset();
138    hash_multiset& operator=(const hash_multiset&);
139
140    allocator_type get_allocator() const;
141
142    bool      empty() const;
143    size_type size() const;
144    size_type max_size() const;
145
146    iterator       begin();
147    iterator       end();
148    const_iterator begin()  const;
149    const_iterator end()    const;
150
151    iterator insert(const value_type& obj);
152    template <class InputIterator>
153        void insert(InputIterator first, InputIterator last);
154
155    void erase(const_iterator position);
156    size_type erase(const key_type& k);
157    void erase(const_iterator first, const_iterator last);
158    void clear();
159
160    void swap(hash_multiset&);
161
162    hasher hash_funct() const;
163    key_equal key_eq() const;
164
165    iterator       find(const key_type& k);
166    const_iterator find(const key_type& k) const;
167    size_type count(const key_type& k) const;
168    pair<iterator, iterator>             equal_range(const key_type& k);
169    pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
170
171    size_type bucket_count() const;
172    size_type max_bucket_count() const;
173
174    size_type elems_in_bucket(size_type n) const;
175
176    void resize(size_type n);
177};
178
179template <class Value, class Hash, class Pred, class Alloc>
180    void swap(hash_multiset<Value, Hash, Pred, Alloc>& x,
181              hash_multiset<Value, Hash, Pred, Alloc>& y);
182
183template <class Value, class Hash, class Pred, class Alloc>
184    bool
185    operator==(const hash_multiset<Value, Hash, Pred, Alloc>& x,
186               const hash_multiset<Value, Hash, Pred, Alloc>& y);
187
188template <class Value, class Hash, class Pred, class Alloc>
189    bool
190    operator!=(const hash_multiset<Value, Hash, Pred, Alloc>& x,
191               const hash_multiset<Value, Hash, Pred, Alloc>& y);
192}  // __gnu_cxx
193
194*/
195
196#include <__config>
197#include <__hash_table>
198#include <functional>
199#include <ext/__hash>
200
201#if __DEPRECATED
202#warning Use of the header <ext/hash_set> is deprecated.  Migrate to <unordered_set>
203#endif
204
205namespace __gnu_cxx {
206
207using namespace std;
208
209template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>,
210          class _Alloc = allocator<_Value> >
211class _LIBCPP_TYPE_VIS hash_set
212{
213public:
214    // types
215    typedef _Value                                                     key_type;
216    typedef key_type                                                   value_type;
217    typedef _Hash                                                      hasher;
218    typedef _Pred                                                      key_equal;
219    typedef _Alloc                                                     allocator_type;
220    typedef value_type&                                                reference;
221    typedef const value_type&                                          const_reference;
222
223private:
224    typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
225
226    __table __table_;
227
228public:
229    typedef typename __table::pointer         pointer;
230    typedef typename __table::const_pointer   const_pointer;
231    typedef typename __table::size_type       size_type;
232    typedef typename __table::difference_type difference_type;
233
234    typedef typename __table::const_iterator       iterator;
235    typedef typename __table::const_iterator       const_iterator;
236
237    _LIBCPP_INLINE_VISIBILITY
238    hash_set() {__table_.rehash(193);}
239    explicit hash_set(size_type __n, const hasher& __hf = hasher(),
240                           const key_equal& __eql = key_equal());
241    hash_set(size_type __n, const hasher& __hf, const key_equal& __eql,
242                  const allocator_type& __a);
243    template <class _InputIterator>
244        hash_set(_InputIterator __first, _InputIterator __last);
245    template <class _InputIterator>
246        hash_set(_InputIterator __first, _InputIterator __last,
247                      size_type __n, const hasher& __hf = hasher(),
248                      const key_equal& __eql = key_equal());
249    template <class _InputIterator>
250        hash_set(_InputIterator __first, _InputIterator __last,
251                      size_type __n, const hasher& __hf, const key_equal& __eql,
252                      const allocator_type& __a);
253    hash_set(const hash_set& __u);
254
255    _LIBCPP_INLINE_VISIBILITY
256    allocator_type get_allocator() const
257        {return allocator_type(__table_.__node_alloc());}
258
259    _LIBCPP_INLINE_VISIBILITY
260    bool      empty() const {return __table_.size() == 0;}
261    _LIBCPP_INLINE_VISIBILITY
262    size_type size() const  {return __table_.size();}
263    _LIBCPP_INLINE_VISIBILITY
264    size_type max_size() const {return __table_.max_size();}
265
266    _LIBCPP_INLINE_VISIBILITY
267    iterator       begin()        {return __table_.begin();}
268    _LIBCPP_INLINE_VISIBILITY
269    iterator       end()          {return __table_.end();}
270    _LIBCPP_INLINE_VISIBILITY
271    const_iterator begin()  const {return __table_.begin();}
272    _LIBCPP_INLINE_VISIBILITY
273    const_iterator end()    const {return __table_.end();}
274
275    _LIBCPP_INLINE_VISIBILITY
276    pair<iterator, bool> insert(const value_type& __x)
277        {return __table_.__insert_unique(__x);}
278    _LIBCPP_INLINE_VISIBILITY
279    iterator insert(const_iterator, const value_type& __x) {return insert(__x).first;}
280    template <class _InputIterator>
281        void insert(_InputIterator __first, _InputIterator __last);
282
283    _LIBCPP_INLINE_VISIBILITY
284    void erase(const_iterator __p) {__table_.erase(__p);}
285    _LIBCPP_INLINE_VISIBILITY
286    size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
287    _LIBCPP_INLINE_VISIBILITY
288    void erase(const_iterator __first, const_iterator __last)
289        {__table_.erase(__first, __last);}
290    _LIBCPP_INLINE_VISIBILITY
291    void clear() {__table_.clear();}
292
293    _LIBCPP_INLINE_VISIBILITY
294    void swap(hash_set& __u) {__table_.swap(__u.__table_);}
295
296    _LIBCPP_INLINE_VISIBILITY
297    hasher hash_funct() const {return __table_.hash_function();}
298    _LIBCPP_INLINE_VISIBILITY
299    key_equal key_eq() const {return __table_.key_eq();}
300
301    _LIBCPP_INLINE_VISIBILITY
302    iterator       find(const key_type& __k)       {return __table_.find(__k);}
303    _LIBCPP_INLINE_VISIBILITY
304    const_iterator find(const key_type& __k) const {return __table_.find(__k);}
305    _LIBCPP_INLINE_VISIBILITY
306    size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
307    _LIBCPP_INLINE_VISIBILITY
308    pair<iterator, iterator>             equal_range(const key_type& __k)
309        {return __table_.__equal_range_unique(__k);}
310    _LIBCPP_INLINE_VISIBILITY
311    pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
312        {return __table_.__equal_range_unique(__k);}
313
314    _LIBCPP_INLINE_VISIBILITY
315    size_type bucket_count() const {return __table_.bucket_count();}
316    _LIBCPP_INLINE_VISIBILITY
317    size_type max_bucket_count() const {return __table_.max_bucket_count();}
318
319    _LIBCPP_INLINE_VISIBILITY
320    size_type elems_in_bucket(size_type __n) const {return __table_.bucket_size(__n);}
321
322    _LIBCPP_INLINE_VISIBILITY
323    void resize(size_type __n) {__table_.rehash(__n);}
324};
325
326template <class _Value, class _Hash, class _Pred, class _Alloc>
327hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(size_type __n,
328        const hasher& __hf, const key_equal& __eql)
329    : __table_(__hf, __eql)
330{
331    __table_.rehash(__n);
332}
333
334template <class _Value, class _Hash, class _Pred, class _Alloc>
335hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(size_type __n,
336        const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
337    : __table_(__hf, __eql, __a)
338{
339    __table_.rehash(__n);
340}
341
342template <class _Value, class _Hash, class _Pred, class _Alloc>
343template <class _InputIterator>
344hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(
345        _InputIterator __first, _InputIterator __last)
346{
347    __table_.rehash(193);
348    insert(__first, __last);
349}
350
351template <class _Value, class _Hash, class _Pred, class _Alloc>
352template <class _InputIterator>
353hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(
354        _InputIterator __first, _InputIterator __last, size_type __n,
355        const hasher& __hf, const key_equal& __eql)
356    : __table_(__hf, __eql)
357{
358    __table_.rehash(__n);
359    insert(__first, __last);
360}
361
362template <class _Value, class _Hash, class _Pred, class _Alloc>
363template <class _InputIterator>
364hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(
365        _InputIterator __first, _InputIterator __last, size_type __n,
366        const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
367    : __table_(__hf, __eql, __a)
368{
369    __table_.rehash(__n);
370    insert(__first, __last);
371}
372
373template <class _Value, class _Hash, class _Pred, class _Alloc>
374hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(
375        const hash_set& __u)
376    : __table_(__u.__table_)
377{
378    __table_.rehash(__u.bucket_count());
379    insert(__u.begin(), __u.end());
380}
381
382template <class _Value, class _Hash, class _Pred, class _Alloc>
383template <class _InputIterator>
384inline _LIBCPP_INLINE_VISIBILITY
385void
386hash_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
387                                                    _InputIterator __last)
388{
389    for (; __first != __last; ++__first)
390        __table_.__insert_unique(*__first);
391}
392
393template <class _Value, class _Hash, class _Pred, class _Alloc>
394inline _LIBCPP_INLINE_VISIBILITY
395void
396swap(hash_set<_Value, _Hash, _Pred, _Alloc>& __x,
397     hash_set<_Value, _Hash, _Pred, _Alloc>& __y)
398{
399    __x.swap(__y);
400}
401
402template <class _Value, class _Hash, class _Pred, class _Alloc>
403bool
404operator==(const hash_set<_Value, _Hash, _Pred, _Alloc>& __x,
405           const hash_set<_Value, _Hash, _Pred, _Alloc>& __y)
406{
407    if (__x.size() != __y.size())
408        return false;
409    typedef typename hash_set<_Value, _Hash, _Pred, _Alloc>::const_iterator
410                                                                 const_iterator;
411    for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();
412            __i != __ex; ++__i)
413    {
414        const_iterator __j = __y.find(*__i);
415        if (__j == __ey || !(*__i == *__j))
416            return false;
417    }
418    return true;
419}
420
421template <class _Value, class _Hash, class _Pred, class _Alloc>
422inline _LIBCPP_INLINE_VISIBILITY
423bool
424operator!=(const hash_set<_Value, _Hash, _Pred, _Alloc>& __x,
425           const hash_set<_Value, _Hash, _Pred, _Alloc>& __y)
426{
427    return !(__x == __y);
428}
429
430template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>,
431          class _Alloc = allocator<_Value> >
432class _LIBCPP_TYPE_VIS hash_multiset
433{
434public:
435    // types
436    typedef _Value                                                     key_type;
437    typedef key_type                                                   value_type;
438    typedef _Hash                                                      hasher;
439    typedef _Pred                                                      key_equal;
440    typedef _Alloc                                                     allocator_type;
441    typedef value_type&                                                reference;
442    typedef const value_type&                                          const_reference;
443
444private:
445    typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
446
447    __table __table_;
448
449public:
450    typedef typename __table::pointer         pointer;
451    typedef typename __table::const_pointer   const_pointer;
452    typedef typename __table::size_type       size_type;
453    typedef typename __table::difference_type difference_type;
454
455    typedef typename __table::const_iterator       iterator;
456    typedef typename __table::const_iterator       const_iterator;
457
458    _LIBCPP_INLINE_VISIBILITY
459    hash_multiset() {__table_.rehash(193);}
460    explicit hash_multiset(size_type __n, const hasher& __hf = hasher(),
461                                const key_equal& __eql = key_equal());
462    hash_multiset(size_type __n, const hasher& __hf,
463                       const key_equal& __eql, const allocator_type& __a);
464    template <class _InputIterator>
465        hash_multiset(_InputIterator __first, _InputIterator __last);
466    template <class _InputIterator>
467        hash_multiset(_InputIterator __first, _InputIterator __last,
468                      size_type __n, const hasher& __hf = hasher(),
469                      const key_equal& __eql = key_equal());
470    template <class _InputIterator>
471        hash_multiset(_InputIterator __first, _InputIterator __last,
472                      size_type __n , const hasher& __hf,
473                      const key_equal& __eql, const allocator_type& __a);
474    hash_multiset(const hash_multiset& __u);
475
476    _LIBCPP_INLINE_VISIBILITY
477    allocator_type get_allocator() const
478        {return allocator_type(__table_.__node_alloc());}
479
480    _LIBCPP_INLINE_VISIBILITY
481    bool      empty() const {return __table_.size() == 0;}
482    _LIBCPP_INLINE_VISIBILITY
483    size_type size() const  {return __table_.size();}
484    _LIBCPP_INLINE_VISIBILITY
485    size_type max_size() const {return __table_.max_size();}
486
487    _LIBCPP_INLINE_VISIBILITY
488    iterator       begin()        {return __table_.begin();}
489    _LIBCPP_INLINE_VISIBILITY
490    iterator       end()          {return __table_.end();}
491    _LIBCPP_INLINE_VISIBILITY
492    const_iterator begin()  const {return __table_.begin();}
493    _LIBCPP_INLINE_VISIBILITY
494    const_iterator end()    const {return __table_.end();}
495
496    _LIBCPP_INLINE_VISIBILITY
497    iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
498    _LIBCPP_INLINE_VISIBILITY
499    iterator insert(const_iterator, const value_type& __x) {return insert(__x);}
500    template <class _InputIterator>
501        void insert(_InputIterator __first, _InputIterator __last);
502
503    _LIBCPP_INLINE_VISIBILITY
504    void erase(const_iterator __p) {__table_.erase(__p);}
505    _LIBCPP_INLINE_VISIBILITY
506    size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
507    _LIBCPP_INLINE_VISIBILITY
508    void erase(const_iterator __first, const_iterator __last)
509        {__table_.erase(__first, __last);}
510    _LIBCPP_INLINE_VISIBILITY
511    void clear() {__table_.clear();}
512
513    _LIBCPP_INLINE_VISIBILITY
514    void swap(hash_multiset& __u) {__table_.swap(__u.__table_);}
515
516    _LIBCPP_INLINE_VISIBILITY
517    hasher hash_funct() const {return __table_.hash_function();}
518    _LIBCPP_INLINE_VISIBILITY
519    key_equal key_eq() const {return __table_.key_eq();}
520
521    _LIBCPP_INLINE_VISIBILITY
522    iterator       find(const key_type& __k)       {return __table_.find(__k);}
523    _LIBCPP_INLINE_VISIBILITY
524    const_iterator find(const key_type& __k) const {return __table_.find(__k);}
525    _LIBCPP_INLINE_VISIBILITY
526    size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
527    _LIBCPP_INLINE_VISIBILITY
528    pair<iterator, iterator>             equal_range(const key_type& __k)
529        {return __table_.__equal_range_multi(__k);}
530    _LIBCPP_INLINE_VISIBILITY
531    pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
532        {return __table_.__equal_range_multi(__k);}
533
534    _LIBCPP_INLINE_VISIBILITY
535    size_type bucket_count() const {return __table_.bucket_count();}
536    _LIBCPP_INLINE_VISIBILITY
537    size_type max_bucket_count() const {return __table_.max_bucket_count();}
538
539    _LIBCPP_INLINE_VISIBILITY
540    size_type elems_in_bucket(size_type __n) const {return __table_.bucket_size(__n);}
541
542    _LIBCPP_INLINE_VISIBILITY
543    void resize(size_type __n) {__table_.rehash(__n);}
544};
545
546template <class _Value, class _Hash, class _Pred, class _Alloc>
547hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
548        size_type __n, const hasher& __hf, const key_equal& __eql)
549    : __table_(__hf, __eql)
550{
551    __table_.rehash(__n);
552}
553
554template <class _Value, class _Hash, class _Pred, class _Alloc>
555hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
556        size_type __n, const hasher& __hf, const key_equal& __eql,
557        const allocator_type& __a)
558    : __table_(__hf, __eql, __a)
559{
560    __table_.rehash(__n);
561}
562
563template <class _Value, class _Hash, class _Pred, class _Alloc>
564template <class _InputIterator>
565hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
566        _InputIterator __first, _InputIterator __last)
567{
568    __table_.rehash(193);
569    insert(__first, __last);
570}
571
572template <class _Value, class _Hash, class _Pred, class _Alloc>
573template <class _InputIterator>
574hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
575        _InputIterator __first, _InputIterator __last, size_type __n,
576        const hasher& __hf, const key_equal& __eql)
577    : __table_(__hf, __eql)
578{
579    __table_.rehash(__n);
580    insert(__first, __last);
581}
582
583template <class _Value, class _Hash, class _Pred, class _Alloc>
584template <class _InputIterator>
585hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
586        _InputIterator __first, _InputIterator __last, size_type __n,
587        const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
588    : __table_(__hf, __eql, __a)
589{
590    __table_.rehash(__n);
591    insert(__first, __last);
592}
593
594template <class _Value, class _Hash, class _Pred, class _Alloc>
595hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
596        const hash_multiset& __u)
597    : __table_(__u.__table_)
598{
599    __table_.rehash(__u.bucket_count());
600    insert(__u.begin(), __u.end());
601}
602
603template <class _Value, class _Hash, class _Pred, class _Alloc>
604template <class _InputIterator>
605inline _LIBCPP_INLINE_VISIBILITY
606void
607hash_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
608                                                         _InputIterator __last)
609{
610    for (; __first != __last; ++__first)
611        __table_.__insert_multi(*__first);
612}
613
614template <class _Value, class _Hash, class _Pred, class _Alloc>
615inline _LIBCPP_INLINE_VISIBILITY
616void
617swap(hash_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
618     hash_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
619{
620    __x.swap(__y);
621}
622
623template <class _Value, class _Hash, class _Pred, class _Alloc>
624bool
625operator==(const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
626           const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
627{
628    if (__x.size() != __y.size())
629        return false;
630    typedef typename hash_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator
631                                                                 const_iterator;
632    typedef pair<const_iterator, const_iterator> _EqRng;
633    for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;)
634    {
635        _EqRng __xeq = __x.equal_range(*__i);
636        _EqRng __yeq = __y.equal_range(*__i);
637        if (_VSTD::distance(__xeq.first, __xeq.second) !=
638            _VSTD::distance(__yeq.first, __yeq.second) ||
639                  !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first))
640            return false;
641        __i = __xeq.second;
642    }
643    return true;
644}
645
646template <class _Value, class _Hash, class _Pred, class _Alloc>
647inline _LIBCPP_INLINE_VISIBILITY
648bool
649operator!=(const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
650           const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
651{
652    return !(__x == __y);
653}
654
655} // __gnu_cxx
656
657#endif  // _LIBCPP_HASH_SET
658