← Back to branch summary

~ubuntu-branches/ubuntu/vivid/emscripten/vivid

« back to all changes in this revision

Viewing changes to system/include/libcxx/ext/hash_set

  • Committer: Package Import Robot
  • Author(s): Sylvestre Ledru
  • Date: 2013-05-02 13:11:51 UTC
  • Revision ID: package-import@ubuntu.com-20130502131151-q8dvteqr1ef2x7xz
Tags: upstream-1.4.1~20130504~adb56cb
Import upstream version 1.4.1~20130504~adb56cb

Show diffs side-by-side

added added

removed removed

Lines of Context:
system/include/libcxx/ext/hash_set
 
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
 
 
18
namespace __gnu_cxx
 
19
{
 
20
 
 
21
template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,
 
22
          class Alloc = allocator<Value>>
 
23
class hash_set
 
24
{
 
25
public:
 
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
 
 
93
template <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
 
 
97
template <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
 
 
102
template <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
 
 
107
template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,
 
108
          class Alloc = allocator<Value>>
 
109
class hash_multiset
 
110
{
 
111
public:
 
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
 
 
179
template <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
 
 
183
template <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
 
 
188
template <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
 
 
205
namespace __gnu_cxx {
 
206
 
 
207
using namespace std;
 
208
 
 
209
template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>,
 
210
          class _Alloc = allocator<_Value> >
 
211
class _LIBCPP_TYPE_VIS hash_set
 
212
{
 
213
public:
 
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
 
 
223
private:
 
224
    typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
 
225
 
 
226
    __table __table_;
 
227
 
 
228
public:
 
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
 
 
326
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
327
hash_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
 
 
334
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
335
hash_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
 
 
342
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
343
template <class _InputIterator>
 
344
hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(
 
345
        _InputIterator __first, _InputIterator __last)
 
346
{
 
347
    __table_.rehash(193);
 
348
    insert(__first, __last);
 
349
}
 
350
 
 
351
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
352
template <class _InputIterator>
 
353
hash_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
 
 
362
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
363
template <class _InputIterator>
 
364
hash_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
 
 
373
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
374
hash_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
 
 
382
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
383
template <class _InputIterator>
 
384
inline _LIBCPP_INLINE_VISIBILITY
 
385
void
 
386
hash_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
 
387
                                                    _InputIterator __last)
 
388
{
 
389
    for (; __first != __last; ++__first)
 
390
        __table_.__insert_unique(*__first);
 
391
}
 
392
 
 
393
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
394
inline _LIBCPP_INLINE_VISIBILITY
 
395
void
 
396
swap(hash_set<_Value, _Hash, _Pred, _Alloc>& __x,
 
397
     hash_set<_Value, _Hash, _Pred, _Alloc>& __y)
 
398
{
 
399
    __x.swap(__y);
 
400
}
 
401
 
 
402
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
403
bool
 
404
operator==(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
 
 
421
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
422
inline _LIBCPP_INLINE_VISIBILITY
 
423
bool
 
424
operator!=(const hash_set<_Value, _Hash, _Pred, _Alloc>& __x,
 
425
           const hash_set<_Value, _Hash, _Pred, _Alloc>& __y)
 
426
{
 
427
    return !(__x == __y);
 
428
}
 
429
 
 
430
template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>,
 
431
          class _Alloc = allocator<_Value> >
 
432
class _LIBCPP_TYPE_VIS hash_multiset
 
433
{
 
434
public:
 
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
 
 
444
private:
 
445
    typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
 
446
 
 
447
    __table __table_;
 
448
 
 
449
public:
 
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
 
 
546
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
547
hash_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
 
 
554
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
555
hash_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
 
 
563
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
564
template <class _InputIterator>
 
565
hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
 
566
        _InputIterator __first, _InputIterator __last)
 
567
{
 
568
    __table_.rehash(193);
 
569
    insert(__first, __last);
 
570
}
 
571
 
 
572
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
573
template <class _InputIterator>
 
574
hash_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
 
 
583
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
584
template <class _InputIterator>
 
585
hash_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
 
 
594
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
595
hash_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
 
 
603
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
604
template <class _InputIterator>
 
605
inline _LIBCPP_INLINE_VISIBILITY
 
606
void
 
607
hash_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
 
608
                                                         _InputIterator __last)
 
609
{
 
610
    for (; __first != __last; ++__first)
 
611
        __table_.__insert_multi(*__first);
 
612
}
 
613
 
 
614
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
615
inline _LIBCPP_INLINE_VISIBILITY
 
616
void
 
617
swap(hash_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
 
618
     hash_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
 
619
{
 
620
    __x.swap(__y);
 
621
}
 
622
 
 
623
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
624
bool
 
625
operator==(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
 
 
646
template <class _Value, class _Hash, class _Pred, class _Alloc>
 
647
inline _LIBCPP_INLINE_VISIBILITY
 
648
bool
 
649
operator!=(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