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