• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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#if defined(_LIBCPP_WARNING)
203    _LIBCPP_WARNING("Use of the header <ext/hash_set> is deprecated.  Migrate to <unordered_set>")
204#else
205#   warning Use of the header <ext/hash_set> is deprecated.  Migrate to <unordered_set>
206#endif
207#endif
208
209namespace __gnu_cxx {
210
211using namespace std;
212
213template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>,
214          class _Alloc = allocator<_Value> >
215class _LIBCPP_TEMPLATE_VIS hash_set
216{
217public:
218    // types
219    typedef _Value                                                     key_type;
220    typedef key_type                                                   value_type;
221    typedef _Hash                                                      hasher;
222    typedef _Pred                                                      key_equal;
223    typedef _Alloc                                                     allocator_type;
224    typedef value_type&                                                reference;
225    typedef const value_type&                                          const_reference;
226
227private:
228    typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
229
230    __table __table_;
231
232public:
233    typedef typename __table::pointer         pointer;
234    typedef typename __table::const_pointer   const_pointer;
235    typedef typename __table::size_type       size_type;
236    typedef typename __table::difference_type difference_type;
237
238    typedef typename __table::const_iterator       iterator;
239    typedef typename __table::const_iterator       const_iterator;
240
241    _LIBCPP_INLINE_VISIBILITY
242    hash_set() {__table_.rehash(193);}
243    explicit hash_set(size_type __n, const hasher& __hf = hasher(),
244                           const key_equal& __eql = key_equal());
245    hash_set(size_type __n, const hasher& __hf, const key_equal& __eql,
246                  const allocator_type& __a);
247    template <class _InputIterator>
248        hash_set(_InputIterator __first, _InputIterator __last);
249    template <class _InputIterator>
250        hash_set(_InputIterator __first, _InputIterator __last,
251                      size_type __n, const hasher& __hf = hasher(),
252                      const key_equal& __eql = key_equal());
253    template <class _InputIterator>
254        hash_set(_InputIterator __first, _InputIterator __last,
255                      size_type __n, const hasher& __hf, const key_equal& __eql,
256                      const allocator_type& __a);
257    hash_set(const hash_set& __u);
258
259    _LIBCPP_INLINE_VISIBILITY
260    allocator_type get_allocator() const
261        {return allocator_type(__table_.__node_alloc());}
262
263    _LIBCPP_INLINE_VISIBILITY
264    bool      empty() const {return __table_.size() == 0;}
265    _LIBCPP_INLINE_VISIBILITY
266    size_type size() const  {return __table_.size();}
267    _LIBCPP_INLINE_VISIBILITY
268    size_type max_size() const {return __table_.max_size();}
269
270    _LIBCPP_INLINE_VISIBILITY
271    iterator       begin()        {return __table_.begin();}
272    _LIBCPP_INLINE_VISIBILITY
273    iterator       end()          {return __table_.end();}
274    _LIBCPP_INLINE_VISIBILITY
275    const_iterator begin()  const {return __table_.begin();}
276    _LIBCPP_INLINE_VISIBILITY
277    const_iterator end()    const {return __table_.end();}
278
279    _LIBCPP_INLINE_VISIBILITY
280    pair<iterator, bool> insert(const value_type& __x)
281        {return __table_.__insert_unique(__x);}
282    _LIBCPP_INLINE_VISIBILITY
283    iterator insert(const_iterator, const value_type& __x) {return insert(__x).first;}
284    template <class _InputIterator>
285        _LIBCPP_INLINE_VISIBILITY
286        void insert(_InputIterator __first, _InputIterator __last);
287
288    _LIBCPP_INLINE_VISIBILITY
289    void erase(const_iterator __p) {__table_.erase(__p);}
290    _LIBCPP_INLINE_VISIBILITY
291    size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
292    _LIBCPP_INLINE_VISIBILITY
293    void erase(const_iterator __first, const_iterator __last)
294        {__table_.erase(__first, __last);}
295    _LIBCPP_INLINE_VISIBILITY
296    void clear() {__table_.clear();}
297
298    _LIBCPP_INLINE_VISIBILITY
299    void swap(hash_set& __u) {__table_.swap(__u.__table_);}
300
301    _LIBCPP_INLINE_VISIBILITY
302    hasher hash_funct() const {return __table_.hash_function();}
303    _LIBCPP_INLINE_VISIBILITY
304    key_equal key_eq() const {return __table_.key_eq();}
305
306    _LIBCPP_INLINE_VISIBILITY
307    iterator       find(const key_type& __k)       {return __table_.find(__k);}
308    _LIBCPP_INLINE_VISIBILITY
309    const_iterator find(const key_type& __k) const {return __table_.find(__k);}
310    _LIBCPP_INLINE_VISIBILITY
311    size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
312    _LIBCPP_INLINE_VISIBILITY
313    pair<iterator, iterator>             equal_range(const key_type& __k)
314        {return __table_.__equal_range_unique(__k);}
315    _LIBCPP_INLINE_VISIBILITY
316    pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
317        {return __table_.__equal_range_unique(__k);}
318
319    _LIBCPP_INLINE_VISIBILITY
320    size_type bucket_count() const {return __table_.bucket_count();}
321    _LIBCPP_INLINE_VISIBILITY
322    size_type max_bucket_count() const {return __table_.max_bucket_count();}
323
324    _LIBCPP_INLINE_VISIBILITY
325    size_type elems_in_bucket(size_type __n) const {return __table_.bucket_size(__n);}
326
327    _LIBCPP_INLINE_VISIBILITY
328    void resize(size_type __n) {__table_.rehash(__n);}
329};
330
331template <class _Value, class _Hash, class _Pred, class _Alloc>
332hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(size_type __n,
333        const hasher& __hf, const key_equal& __eql)
334    : __table_(__hf, __eql)
335{
336    __table_.rehash(__n);
337}
338
339template <class _Value, class _Hash, class _Pred, class _Alloc>
340hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(size_type __n,
341        const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
342    : __table_(__hf, __eql, __a)
343{
344    __table_.rehash(__n);
345}
346
347template <class _Value, class _Hash, class _Pred, class _Alloc>
348template <class _InputIterator>
349hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(
350        _InputIterator __first, _InputIterator __last)
351{
352    __table_.rehash(193);
353    insert(__first, __last);
354}
355
356template <class _Value, class _Hash, class _Pred, class _Alloc>
357template <class _InputIterator>
358hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(
359        _InputIterator __first, _InputIterator __last, size_type __n,
360        const hasher& __hf, const key_equal& __eql)
361    : __table_(__hf, __eql)
362{
363    __table_.rehash(__n);
364    insert(__first, __last);
365}
366
367template <class _Value, class _Hash, class _Pred, class _Alloc>
368template <class _InputIterator>
369hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(
370        _InputIterator __first, _InputIterator __last, size_type __n,
371        const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
372    : __table_(__hf, __eql, __a)
373{
374    __table_.rehash(__n);
375    insert(__first, __last);
376}
377
378template <class _Value, class _Hash, class _Pred, class _Alloc>
379hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(
380        const hash_set& __u)
381    : __table_(__u.__table_)
382{
383    __table_.rehash(__u.bucket_count());
384    insert(__u.begin(), __u.end());
385}
386
387template <class _Value, class _Hash, class _Pred, class _Alloc>
388template <class _InputIterator>
389inline
390void
391hash_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
392                                                    _InputIterator __last)
393{
394    for (; __first != __last; ++__first)
395        __table_.__insert_unique(*__first);
396}
397
398template <class _Value, class _Hash, class _Pred, class _Alloc>
399inline _LIBCPP_INLINE_VISIBILITY
400void
401swap(hash_set<_Value, _Hash, _Pred, _Alloc>& __x,
402     hash_set<_Value, _Hash, _Pred, _Alloc>& __y)
403{
404    __x.swap(__y);
405}
406
407template <class _Value, class _Hash, class _Pred, class _Alloc>
408bool
409operator==(const hash_set<_Value, _Hash, _Pred, _Alloc>& __x,
410           const hash_set<_Value, _Hash, _Pred, _Alloc>& __y)
411{
412    if (__x.size() != __y.size())
413        return false;
414    typedef typename hash_set<_Value, _Hash, _Pred, _Alloc>::const_iterator
415                                                                 const_iterator;
416    for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();
417            __i != __ex; ++__i)
418    {
419        const_iterator __j = __y.find(*__i);
420        if (__j == __ey || !(*__i == *__j))
421            return false;
422    }
423    return true;
424}
425
426template <class _Value, class _Hash, class _Pred, class _Alloc>
427inline _LIBCPP_INLINE_VISIBILITY
428bool
429operator!=(const hash_set<_Value, _Hash, _Pred, _Alloc>& __x,
430           const hash_set<_Value, _Hash, _Pred, _Alloc>& __y)
431{
432    return !(__x == __y);
433}
434
435template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>,
436          class _Alloc = allocator<_Value> >
437class _LIBCPP_TEMPLATE_VIS hash_multiset
438{
439public:
440    // types
441    typedef _Value                                                     key_type;
442    typedef key_type                                                   value_type;
443    typedef _Hash                                                      hasher;
444    typedef _Pred                                                      key_equal;
445    typedef _Alloc                                                     allocator_type;
446    typedef value_type&                                                reference;
447    typedef const value_type&                                          const_reference;
448
449private:
450    typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
451
452    __table __table_;
453
454public:
455    typedef typename __table::pointer         pointer;
456    typedef typename __table::const_pointer   const_pointer;
457    typedef typename __table::size_type       size_type;
458    typedef typename __table::difference_type difference_type;
459
460    typedef typename __table::const_iterator       iterator;
461    typedef typename __table::const_iterator       const_iterator;
462
463    _LIBCPP_INLINE_VISIBILITY
464    hash_multiset() {__table_.rehash(193);}
465    explicit hash_multiset(size_type __n, const hasher& __hf = hasher(),
466                                const key_equal& __eql = key_equal());
467    hash_multiset(size_type __n, const hasher& __hf,
468                       const key_equal& __eql, const allocator_type& __a);
469    template <class _InputIterator>
470        hash_multiset(_InputIterator __first, _InputIterator __last);
471    template <class _InputIterator>
472        hash_multiset(_InputIterator __first, _InputIterator __last,
473                      size_type __n, const hasher& __hf = hasher(),
474                      const key_equal& __eql = key_equal());
475    template <class _InputIterator>
476        hash_multiset(_InputIterator __first, _InputIterator __last,
477                      size_type __n , const hasher& __hf,
478                      const key_equal& __eql, const allocator_type& __a);
479    hash_multiset(const hash_multiset& __u);
480
481    _LIBCPP_INLINE_VISIBILITY
482    allocator_type get_allocator() const
483        {return allocator_type(__table_.__node_alloc());}
484
485    _LIBCPP_INLINE_VISIBILITY
486    bool      empty() const {return __table_.size() == 0;}
487    _LIBCPP_INLINE_VISIBILITY
488    size_type size() const  {return __table_.size();}
489    _LIBCPP_INLINE_VISIBILITY
490    size_type max_size() const {return __table_.max_size();}
491
492    _LIBCPP_INLINE_VISIBILITY
493    iterator       begin()        {return __table_.begin();}
494    _LIBCPP_INLINE_VISIBILITY
495    iterator       end()          {return __table_.end();}
496    _LIBCPP_INLINE_VISIBILITY
497    const_iterator begin()  const {return __table_.begin();}
498    _LIBCPP_INLINE_VISIBILITY
499    const_iterator end()    const {return __table_.end();}
500
501    _LIBCPP_INLINE_VISIBILITY
502    iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
503    _LIBCPP_INLINE_VISIBILITY
504    iterator insert(const_iterator, const value_type& __x) {return insert(__x);}
505    template <class _InputIterator>
506        _LIBCPP_INLINE_VISIBILITY
507        void insert(_InputIterator __first, _InputIterator __last);
508
509    _LIBCPP_INLINE_VISIBILITY
510    void erase(const_iterator __p) {__table_.erase(__p);}
511    _LIBCPP_INLINE_VISIBILITY
512    size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
513    _LIBCPP_INLINE_VISIBILITY
514    void erase(const_iterator __first, const_iterator __last)
515        {__table_.erase(__first, __last);}
516    _LIBCPP_INLINE_VISIBILITY
517    void clear() {__table_.clear();}
518
519    _LIBCPP_INLINE_VISIBILITY
520    void swap(hash_multiset& __u) {__table_.swap(__u.__table_);}
521
522    _LIBCPP_INLINE_VISIBILITY
523    hasher hash_funct() const {return __table_.hash_function();}
524    _LIBCPP_INLINE_VISIBILITY
525    key_equal key_eq() const {return __table_.key_eq();}
526
527    _LIBCPP_INLINE_VISIBILITY
528    iterator       find(const key_type& __k)       {return __table_.find(__k);}
529    _LIBCPP_INLINE_VISIBILITY
530    const_iterator find(const key_type& __k) const {return __table_.find(__k);}
531    _LIBCPP_INLINE_VISIBILITY
532    size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
533    _LIBCPP_INLINE_VISIBILITY
534    pair<iterator, iterator>             equal_range(const key_type& __k)
535        {return __table_.__equal_range_multi(__k);}
536    _LIBCPP_INLINE_VISIBILITY
537    pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
538        {return __table_.__equal_range_multi(__k);}
539
540    _LIBCPP_INLINE_VISIBILITY
541    size_type bucket_count() const {return __table_.bucket_count();}
542    _LIBCPP_INLINE_VISIBILITY
543    size_type max_bucket_count() const {return __table_.max_bucket_count();}
544
545    _LIBCPP_INLINE_VISIBILITY
546    size_type elems_in_bucket(size_type __n) const {return __table_.bucket_size(__n);}
547
548    _LIBCPP_INLINE_VISIBILITY
549    void resize(size_type __n) {__table_.rehash(__n);}
550};
551
552template <class _Value, class _Hash, class _Pred, class _Alloc>
553hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
554        size_type __n, const hasher& __hf, const key_equal& __eql)
555    : __table_(__hf, __eql)
556{
557    __table_.rehash(__n);
558}
559
560template <class _Value, class _Hash, class _Pred, class _Alloc>
561hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
562        size_type __n, const hasher& __hf, const key_equal& __eql,
563        const allocator_type& __a)
564    : __table_(__hf, __eql, __a)
565{
566    __table_.rehash(__n);
567}
568
569template <class _Value, class _Hash, class _Pred, class _Alloc>
570template <class _InputIterator>
571hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
572        _InputIterator __first, _InputIterator __last)
573{
574    __table_.rehash(193);
575    insert(__first, __last);
576}
577
578template <class _Value, class _Hash, class _Pred, class _Alloc>
579template <class _InputIterator>
580hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
581        _InputIterator __first, _InputIterator __last, size_type __n,
582        const hasher& __hf, const key_equal& __eql)
583    : __table_(__hf, __eql)
584{
585    __table_.rehash(__n);
586    insert(__first, __last);
587}
588
589template <class _Value, class _Hash, class _Pred, class _Alloc>
590template <class _InputIterator>
591hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
592        _InputIterator __first, _InputIterator __last, size_type __n,
593        const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
594    : __table_(__hf, __eql, __a)
595{
596    __table_.rehash(__n);
597    insert(__first, __last);
598}
599
600template <class _Value, class _Hash, class _Pred, class _Alloc>
601hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
602        const hash_multiset& __u)
603    : __table_(__u.__table_)
604{
605    __table_.rehash(__u.bucket_count());
606    insert(__u.begin(), __u.end());
607}
608
609template <class _Value, class _Hash, class _Pred, class _Alloc>
610template <class _InputIterator>
611inline
612void
613hash_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
614                                                         _InputIterator __last)
615{
616    for (; __first != __last; ++__first)
617        __table_.__insert_multi(*__first);
618}
619
620template <class _Value, class _Hash, class _Pred, class _Alloc>
621inline _LIBCPP_INLINE_VISIBILITY
622void
623swap(hash_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
624     hash_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
625{
626    __x.swap(__y);
627}
628
629template <class _Value, class _Hash, class _Pred, class _Alloc>
630bool
631operator==(const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
632           const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
633{
634    if (__x.size() != __y.size())
635        return false;
636    typedef typename hash_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator
637                                                                 const_iterator;
638    typedef pair<const_iterator, const_iterator> _EqRng;
639    for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;)
640    {
641        _EqRng __xeq = __x.equal_range(*__i);
642        _EqRng __yeq = __y.equal_range(*__i);
643        if (_VSTD::distance(__xeq.first, __xeq.second) !=
644            _VSTD::distance(__yeq.first, __yeq.second) ||
645                  !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first))
646            return false;
647        __i = __xeq.second;
648    }
649    return true;
650}
651
652template <class _Value, class _Hash, class _Pred, class _Alloc>
653inline _LIBCPP_INLINE_VISIBILITY
654bool
655operator!=(const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
656           const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
657{
658    return !(__x == __y);
659}
660
661} // __gnu_cxx
662
663#endif  // _LIBCPP_HASH_SET
664