← 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_map

  • 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_map
 
1
// -*- C++ -*-
 
2
//===-------------------------- hash_map ----------------------------------===//
 
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_MAP
 
12
#define _LIBCPP_HASH_MAP
 
13
 
 
14
/*
 
15
 
 
16
    hash_map synopsis
 
17
 
 
18
namespace __gnu_cxx
 
19
{
 
20
 
 
21
template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
 
22
          class Alloc = allocator<pair<const Key, T>>>
 
23
class hash_map
 
24
{
 
25
public:
 
26
    // types
 
27
    typedef Key                                                        key_type;
 
28
    typedef T                                                          mapped_type;
 
29
    typedef Hash                                                       hasher;
 
30
    typedef Pred                                                       key_equal;
 
31
    typedef Alloc                                                      allocator_type;
 
32
    typedef pair<const key_type, mapped_type>                          value_type;
 
33
    typedef value_type&                                                reference;
 
34
    typedef const value_type&                                          const_reference;
 
35
    typedef typename allocator_traits<allocator_type>::pointer         pointer;
 
36
    typedef typename allocator_traits<allocator_type>::const_pointer   const_pointer;
 
37
    typedef typename allocator_traits<allocator_type>::size_type       size_type;
 
38
    typedef typename allocator_traits<allocator_type>::difference_type difference_type;
 
39
 
 
40
    typedef /unspecified/ iterator;
 
41
    typedef /unspecified/ const_iterator;
 
42
 
 
43
    explicit hash_map(size_type n = 193, const hasher& hf = hasher(),
 
44
                           const key_equal& eql = key_equal(),
 
45
                           const allocator_type& a = allocator_type());
 
46
    template <class InputIterator>
 
47
        hash_map(InputIterator f, InputIterator l,
 
48
                      size_type n = 193, const hasher& hf = hasher(),
 
49
                      const key_equal& eql = key_equal(),
 
50
                      const allocator_type& a = allocator_type());
 
51
    hash_map(const hash_map&);
 
52
    ~hash_map();
 
53
    hash_map& operator=(const hash_map&);
 
54
 
 
55
    allocator_type get_allocator() const;
 
56
 
 
57
    bool      empty() const;
 
58
    size_type size() const;
 
59
    size_type max_size() const;
 
60
 
 
61
    iterator       begin();
 
62
    iterator       end();
 
63
    const_iterator begin()  const;
 
64
    const_iterator end()    const;
 
65
 
 
66
    pair<iterator, bool> insert(const value_type& obj);
 
67
    template <class InputIterator>
 
68
        void insert(InputIterator first, InputIterator last);
 
69
 
 
70
    void erase(const_iterator position);
 
71
    size_type erase(const key_type& k);
 
72
    void erase(const_iterator first, const_iterator last);
 
73
    void clear();
 
74
 
 
75
    void swap(hash_map&);
 
76
 
 
77
    hasher hash_funct() const;
 
78
    key_equal key_eq() const;
 
79
 
 
80
    iterator       find(const key_type& k);
 
81
    const_iterator find(const key_type& k) const;
 
82
    size_type count(const key_type& k) const;
 
83
    pair<iterator, iterator>             equal_range(const key_type& k);
 
84
    pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
 
85
 
 
86
    mapped_type& operator[](const key_type& k);
 
87
 
 
88
    size_type bucket_count() const;
 
89
    size_type max_bucket_count() const;
 
90
 
 
91
    size_type elems_in_bucket(size_type n) const;
 
92
 
 
93
    void resize(size_type n);
 
94
};
 
95
 
 
96
template <class Key, class T, class Hash, class Pred, class Alloc>
 
97
    void swap(hash_map<Key, T, Hash, Pred, Alloc>& x,
 
98
              hash_map<Key, T, Hash, Pred, Alloc>& y);
 
99
 
 
100
template <class Key, class T, class Hash, class Pred, class Alloc>
 
101
    bool
 
102
    operator==(const hash_map<Key, T, Hash, Pred, Alloc>& x,
 
103
               const hash_map<Key, T, Hash, Pred, Alloc>& y);
 
104
 
 
105
template <class Key, class T, class Hash, class Pred, class Alloc>
 
106
    bool
 
107
    operator!=(const hash_map<Key, T, Hash, Pred, Alloc>& x,
 
108
               const hash_map<Key, T, Hash, Pred, Alloc>& y);
 
109
 
 
110
template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
 
111
          class Alloc = allocator<pair<const Key, T>>>
 
112
class hash_multimap
 
113
{
 
114
public:
 
115
    // types
 
116
    typedef Key                                                        key_type;
 
117
    typedef T                                                          mapped_type;
 
118
    typedef Hash                                                       hasher;
 
119
    typedef Pred                                                       key_equal;
 
120
    typedef Alloc                                                      allocator_type;
 
121
    typedef pair<const key_type, mapped_type>                          value_type;
 
122
    typedef value_type&                                                reference;
 
123
    typedef const value_type&                                          const_reference;
 
124
    typedef typename allocator_traits<allocator_type>::pointer         pointer;
 
125
    typedef typename allocator_traits<allocator_type>::const_pointer   const_pointer;
 
126
    typedef typename allocator_traits<allocator_type>::size_type       size_type;
 
127
    typedef typename allocator_traits<allocator_type>::difference_type difference_type;
 
128
 
 
129
    typedef /unspecified/ iterator;
 
130
    typedef /unspecified/ const_iterator;
 
131
 
 
132
    explicit hash_multimap(size_type n = 193, const hasher& hf = hasher(),
 
133
                           const key_equal& eql = key_equal(),
 
134
                           const allocator_type& a = allocator_type());
 
135
    template <class InputIterator>
 
136
        hash_multimap(InputIterator f, InputIterator l,
 
137
                      size_type n = 193, const hasher& hf = hasher(),
 
138
                      const key_equal& eql = key_equal(),
 
139
                      const allocator_type& a = allocator_type());
 
140
    explicit hash_multimap(const allocator_type&);
 
141
    hash_multimap(const hash_multimap&);
 
142
    ~hash_multimap();
 
143
    hash_multimap& operator=(const hash_multimap&);
 
144
 
 
145
    allocator_type get_allocator() const;
 
146
 
 
147
    bool      empty() const;
 
148
    size_type size() const;
 
149
    size_type max_size() const;
 
150
 
 
151
    iterator       begin();
 
152
    iterator       end();
 
153
    const_iterator begin()  const;
 
154
    const_iterator end()    const;
 
155
 
 
156
    iterator insert(const value_type& obj);
 
157
    template <class InputIterator>
 
158
        void insert(InputIterator first, InputIterator last);
 
159
 
 
160
    void erase(const_iterator position);
 
161
    size_type erase(const key_type& k);
 
162
    void erase(const_iterator first, const_iterator last);
 
163
    void clear();
 
164
 
 
165
    void swap(hash_multimap&);
 
166
 
 
167
    hasher hash_funct() const;
 
168
    key_equal key_eq() const;
 
169
 
 
170
    iterator       find(const key_type& k);
 
171
    const_iterator find(const key_type& k) const;
 
172
    size_type count(const key_type& k) const;
 
173
    pair<iterator, iterator>             equal_range(const key_type& k);
 
174
    pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
 
175
 
 
176
    size_type bucket_count() const;
 
177
    size_type max_bucket_count() const;
 
178
 
 
179
    size_type elems_in_bucket(size_type n) const;
 
180
 
 
181
    void resize(size_type n);
 
182
};
 
183
 
 
184
template <class Key, class T, class Hash, class Pred, class Alloc>
 
185
    void swap(hash_multimap<Key, T, Hash, Pred, Alloc>& x,
 
186
              hash_multimap<Key, T, Hash, Pred, Alloc>& y);
 
187
 
 
188
template <class Key, class T, class Hash, class Pred, class Alloc>
 
189
    bool
 
190
    operator==(const hash_multimap<Key, T, Hash, Pred, Alloc>& x,
 
191
               const hash_multimap<Key, T, Hash, Pred, Alloc>& y);
 
192
 
 
193
template <class Key, class T, class Hash, class Pred, class Alloc>
 
194
    bool
 
195
    operator!=(const hash_multimap<Key, T, Hash, Pred, Alloc>& x,
 
196
               const hash_multimap<Key, T, Hash, Pred, Alloc>& y);
 
197
 
 
198
}  // __gnu_cxx
 
199
 
 
200
*/
 
201
 
 
202
#include <__config>
 
203
#include <__hash_table>
 
204
#include <functional>
 
205
#include <stdexcept>
 
206
#include <ext/__hash>
 
207
 
 
208
#if __DEPRECATED
 
209
#warning Use of the header <ext/hash_map> is deprecated.  Migrate to <unordered_map>
 
210
#endif
 
211
 
 
212
#pragma GCC system_header
 
213
 
 
214
namespace __gnu_cxx {
 
215
 
 
216
using namespace std;
 
217
 
 
218
template <class _Tp, class _Hash, bool = is_empty<_Hash>::value
 
219
#if __has_feature(is_final)
 
220
                                         && !__is_final(_Hash)
 
221
#endif
 
222
        >
 
223
class __hash_map_hasher
 
224
    : private _Hash
 
225
{
 
226
public:
 
227
    _LIBCPP_INLINE_VISIBILITY __hash_map_hasher() : _Hash() {}
 
228
    _LIBCPP_INLINE_VISIBILITY __hash_map_hasher(const _Hash& __h) : _Hash(__h) {}
 
229
    _LIBCPP_INLINE_VISIBILITY const _Hash& hash_function() const {return *this;}
 
230
    _LIBCPP_INLINE_VISIBILITY
 
231
    size_t operator()(const _Tp& __x) const
 
232
        {return static_cast<const _Hash&>(*this)(__x.first);}
 
233
    _LIBCPP_INLINE_VISIBILITY
 
234
    size_t operator()(const typename _Tp::first_type& __x) const
 
235
        {return static_cast<const _Hash&>(*this)(__x);}
 
236
};
 
237
 
 
238
template <class _Tp, class _Hash>
 
239
class __hash_map_hasher<_Tp, _Hash, false>
 
240
{
 
241
    _Hash __hash_;
 
242
public:
 
243
    _LIBCPP_INLINE_VISIBILITY __hash_map_hasher() : __hash_() {}
 
244
    _LIBCPP_INLINE_VISIBILITY __hash_map_hasher(const _Hash& __h) : __hash_(__h) {}
 
245
    _LIBCPP_INLINE_VISIBILITY const _Hash& hash_function() const {return __hash_;}
 
246
    _LIBCPP_INLINE_VISIBILITY
 
247
    size_t operator()(const _Tp& __x) const
 
248
        {return __hash_(__x.first);}
 
249
    _LIBCPP_INLINE_VISIBILITY
 
250
    size_t operator()(const typename _Tp::first_type& __x) const
 
251
        {return __hash_(__x);}
 
252
};
 
253
 
 
254
template <class _Tp, class _Pred, bool = is_empty<_Pred>::value
 
255
#if __has_feature(is_final)
 
256
                                         && !__is_final(_Pred)
 
257
#endif
 
258
         >
 
259
class __hash_map_equal
 
260
    : private _Pred
 
261
{
 
262
public:
 
263
    _LIBCPP_INLINE_VISIBILITY __hash_map_equal() : _Pred() {}
 
264
    _LIBCPP_INLINE_VISIBILITY __hash_map_equal(const _Pred& __p) : _Pred(__p) {}
 
265
    _LIBCPP_INLINE_VISIBILITY const _Pred& key_eq() const {return *this;}
 
266
    _LIBCPP_INLINE_VISIBILITY
 
267
    bool operator()(const _Tp& __x, const _Tp& __y) const
 
268
        {return static_cast<const _Pred&>(*this)(__x.first, __y.first);}
 
269
    _LIBCPP_INLINE_VISIBILITY
 
270
    bool operator()(const typename _Tp::first_type& __x, const _Tp& __y) const
 
271
        {return static_cast<const _Pred&>(*this)(__x, __y.first);}
 
272
    _LIBCPP_INLINE_VISIBILITY
 
273
    bool operator()(const _Tp& __x, const typename _Tp::first_type& __y) const
 
274
        {return static_cast<const _Pred&>(*this)(__x.first, __y);}
 
275
    _LIBCPP_INLINE_VISIBILITY
 
276
    bool operator()(const typename _Tp::first_type& __x,
 
277
                    const typename _Tp::first_type& __y) const
 
278
        {return static_cast<const _Pred&>(*this)(__x, __y);}
 
279
};
 
280
 
 
281
template <class _Tp, class _Pred>
 
282
class __hash_map_equal<_Tp, _Pred, false>
 
283
{
 
284
    _Pred __pred_;
 
285
public:
 
286
    _LIBCPP_INLINE_VISIBILITY __hash_map_equal() : __pred_() {}
 
287
    _LIBCPP_INLINE_VISIBILITY __hash_map_equal(const _Pred& __p) : __pred_(__p) {}
 
288
    _LIBCPP_INLINE_VISIBILITY const _Pred& key_eq() const {return __pred_;}
 
289
    _LIBCPP_INLINE_VISIBILITY
 
290
    bool operator()(const _Tp& __x, const _Tp& __y) const
 
291
        {return __pred_(__x.first, __y.first);}
 
292
    _LIBCPP_INLINE_VISIBILITY
 
293
    bool operator()(const typename _Tp::first_type& __x, const _Tp& __y) const
 
294
        {return __pred_(__x, __y.first);}
 
295
    _LIBCPP_INLINE_VISIBILITY
 
296
    bool operator()(const _Tp& __x, const typename _Tp::first_type& __y) const
 
297
        {return __pred_(__x.first, __y);}
 
298
    _LIBCPP_INLINE_VISIBILITY
 
299
    bool operator()(const typename _Tp::first_type& __x,
 
300
                    const typename _Tp::first_type& __y) const
 
301
        {return __pred_(__x, __y);}
 
302
};
 
303
 
 
304
template <class _Alloc>
 
305
class __hash_map_node_destructor
 
306
{
 
307
    typedef _Alloc                              allocator_type;
 
308
    typedef allocator_traits<allocator_type>    __alloc_traits;
 
309
    typedef typename __alloc_traits::value_type::value_type value_type;
 
310
public:
 
311
    typedef typename __alloc_traits::pointer    pointer;
 
312
private:
 
313
    typedef typename value_type::first_type     first_type;
 
314
    typedef typename value_type::second_type    second_type;
 
315
 
 
316
    allocator_type& __na_;
 
317
 
 
318
    __hash_map_node_destructor& operator=(const __hash_map_node_destructor&);
 
319
 
 
320
public:
 
321
    bool __first_constructed;
 
322
    bool __second_constructed;
 
323
 
 
324
    _LIBCPP_INLINE_VISIBILITY
 
325
    explicit __hash_map_node_destructor(allocator_type& __na)
 
326
        : __na_(__na),
 
327
          __first_constructed(false),
 
328
          __second_constructed(false)
 
329
        {}
 
330
 
 
331
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
332
    _LIBCPP_INLINE_VISIBILITY
 
333
    __hash_map_node_destructor(__hash_node_destructor<allocator_type>&& __x)
 
334
        : __na_(__x.__na_),
 
335
          __first_constructed(__x.__value_constructed),
 
336
          __second_constructed(__x.__value_constructed)
 
337
        {
 
338
            __x.__value_constructed = false;
 
339
        }
 
340
#else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
341
    _LIBCPP_INLINE_VISIBILITY
 
342
    __hash_map_node_destructor(const __hash_node_destructor<allocator_type>& __x)
 
343
        : __na_(__x.__na_),
 
344
          __first_constructed(__x.__value_constructed),
 
345
          __second_constructed(__x.__value_constructed)
 
346
        {
 
347
            const_cast<bool&>(__x.__value_constructed) = false;
 
348
        }
 
349
#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
350
 
 
351
    _LIBCPP_INLINE_VISIBILITY
 
352
    void operator()(pointer __p)
 
353
    {
 
354
        if (__second_constructed)
 
355
            __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.second));
 
356
        if (__first_constructed)
 
357
            __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.first));
 
358
        if (__p)
 
359
            __alloc_traits::deallocate(__na_, __p, 1);
 
360
    }
 
361
};
 
362
 
 
363
template <class _HashIterator>
 
364
class _LIBCPP_TYPE_VIS __hash_map_iterator
 
365
{
 
366
    _HashIterator __i_;
 
367
 
 
368
    typedef pointer_traits<typename _HashIterator::pointer>      __pointer_traits;
 
369
    typedef const typename _HashIterator::value_type::first_type key_type;
 
370
    typedef typename _HashIterator::value_type::second_type      mapped_type;
 
371
public:
 
372
    typedef forward_iterator_tag                                 iterator_category;
 
373
    typedef pair<key_type, mapped_type>                          value_type;
 
374
    typedef typename _HashIterator::difference_type              difference_type;
 
375
    typedef value_type&                                          reference;
 
376
    typedef typename __pointer_traits::template
 
377
#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
 
378
            rebind<value_type>
 
379
#else
 
380
            rebind<value_type>::other
 
381
#endif
 
382
                                                                 pointer;
 
383
 
 
384
    _LIBCPP_INLINE_VISIBILITY __hash_map_iterator() {}
 
385
 
 
386
    _LIBCPP_INLINE_VISIBILITY __hash_map_iterator(_HashIterator __i) : __i_(__i) {}
 
387
 
 
388
    _LIBCPP_INLINE_VISIBILITY reference operator*() const {return *operator->();}
 
389
    _LIBCPP_INLINE_VISIBILITY pointer operator->() const {return (pointer)__i_.operator->();}
 
390
 
 
391
    _LIBCPP_INLINE_VISIBILITY __hash_map_iterator& operator++() {++__i_; return *this;}
 
392
    _LIBCPP_INLINE_VISIBILITY
 
393
    __hash_map_iterator operator++(int)
 
394
    {
 
395
        __hash_map_iterator __t(*this);
 
396
        ++(*this);
 
397
        return __t;
 
398
    }
 
399
 
 
400
    friend _LIBCPP_INLINE_VISIBILITY 
 
401
    bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y)
 
402
        {return __x.__i_ == __y.__i_;}
 
403
    friend _LIBCPP_INLINE_VISIBILITY 
 
404
    bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y)
 
405
        {return __x.__i_ != __y.__i_;}
 
406
 
 
407
    template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS hash_map;
 
408
    template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS hash_multimap;
 
409
    template <class> friend class _LIBCPP_TYPE_VIS __hash_const_iterator;
 
410
    template <class> friend class _LIBCPP_TYPE_VIS __hash_const_local_iterator;
 
411
    template <class> friend class _LIBCPP_TYPE_VIS __hash_map_const_iterator;
 
412
};
 
413
 
 
414
template <class _HashIterator>
 
415
class _LIBCPP_TYPE_VIS __hash_map_const_iterator
 
416
{
 
417
    _HashIterator __i_;
 
418
 
 
419
    typedef pointer_traits<typename _HashIterator::pointer>      __pointer_traits;
 
420
    typedef const typename _HashIterator::value_type::first_type key_type;
 
421
    typedef typename _HashIterator::value_type::second_type      mapped_type;
 
422
public:
 
423
    typedef forward_iterator_tag                                 iterator_category;
 
424
    typedef pair<key_type, mapped_type>                          value_type;
 
425
    typedef typename _HashIterator::difference_type              difference_type;
 
426
    typedef const value_type&                                    reference;
 
427
    typedef typename __pointer_traits::template
 
428
#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
 
429
            rebind<value_type>
 
430
#else
 
431
            rebind<value_type>::other
 
432
#endif
 
433
                                                                 pointer;
 
434
 
 
435
    _LIBCPP_INLINE_VISIBILITY __hash_map_const_iterator() {}
 
436
 
 
437
    _LIBCPP_INLINE_VISIBILITY
 
438
    __hash_map_const_iterator(_HashIterator __i) : __i_(__i) {}
 
439
    _LIBCPP_INLINE_VISIBILITY
 
440
    __hash_map_const_iterator(
 
441
            __hash_map_iterator<typename _HashIterator::__non_const_iterator> __i)
 
442
                : __i_(__i.__i_) {}
 
443
 
 
444
    _LIBCPP_INLINE_VISIBILITY
 
445
    reference operator*() const {return *operator->();}
 
446
    _LIBCPP_INLINE_VISIBILITY
 
447
    pointer operator->() const {return (pointer)__i_.operator->();}
 
448
 
 
449
    _LIBCPP_INLINE_VISIBILITY
 
450
    __hash_map_const_iterator& operator++() {++__i_; return *this;}
 
451
    _LIBCPP_INLINE_VISIBILITY
 
452
    __hash_map_const_iterator operator++(int)
 
453
    {
 
454
        __hash_map_const_iterator __t(*this);
 
455
        ++(*this);
 
456
        return __t;
 
457
    }
 
458
 
 
459
    friend _LIBCPP_INLINE_VISIBILITY
 
460
    bool operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)
 
461
        {return __x.__i_ == __y.__i_;}
 
462
    friend _LIBCPP_INLINE_VISIBILITY
 
463
    bool operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)
 
464
        {return __x.__i_ != __y.__i_;}
 
465
 
 
466
    template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS hash_map;
 
467
    template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS hash_multimap;
 
468
    template <class> friend class _LIBCPP_TYPE_VIS __hash_const_iterator;
 
469
    template <class> friend class _LIBCPP_TYPE_VIS __hash_const_local_iterator;
 
470
};
 
471
 
 
472
template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
 
473
          class _Alloc = allocator<pair<const _Key, _Tp> > >
 
474
class _LIBCPP_TYPE_VIS hash_map
 
475
{
 
476
public:
 
477
    // types
 
478
    typedef _Key                                           key_type;
 
479
    typedef _Tp                                            mapped_type;
 
480
    typedef _Tp                                            data_type;
 
481
    typedef _Hash                                          hasher;
 
482
    typedef _Pred                                          key_equal;
 
483
    typedef _Alloc                                         allocator_type;
 
484
    typedef pair<const key_type, mapped_type>              value_type;
 
485
    typedef value_type&                                    reference;
 
486
    typedef const value_type&                              const_reference;
 
487
 
 
488
private:
 
489
    typedef pair<key_type, mapped_type>                    __value_type;
 
490
    typedef __hash_map_hasher<__value_type, hasher>   __hasher;
 
491
    typedef __hash_map_equal<__value_type, key_equal> __key_equal;
 
492
    typedef typename allocator_traits<allocator_type>::template
 
493
#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
 
494
            rebind_alloc<__value_type>
 
495
#else
 
496
            rebind_alloc<__value_type>::other
 
497
#endif
 
498
                                                           __allocator_type;
 
499
 
 
500
    typedef __hash_table<__value_type, __hasher,
 
501
                         __key_equal,  __allocator_type>   __table;
 
502
 
 
503
    __table __table_;
 
504
 
 
505
    typedef typename __table::__node_pointer               __node_pointer;
 
506
    typedef typename __table::__node_const_pointer         __node_const_pointer;
 
507
    typedef typename __table::__node_traits                __node_traits;
 
508
    typedef typename __table::__node_allocator             __node_allocator;
 
509
    typedef typename __table::__node                       __node;
 
510
    typedef __hash_map_node_destructor<__node_allocator>   _Dp;
 
511
    typedef unique_ptr<__node, _Dp>                         __node_holder;
 
512
    typedef allocator_traits<allocator_type>               __alloc_traits;
 
513
public:
 
514
    typedef typename __alloc_traits::pointer         pointer;
 
515
    typedef typename __alloc_traits::const_pointer   const_pointer;
 
516
    typedef typename __alloc_traits::size_type       size_type;
 
517
    typedef typename __alloc_traits::difference_type difference_type;
 
518
 
 
519
    typedef __hash_map_iterator<typename __table::iterator>       iterator;
 
520
    typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
 
521
 
 
522
    _LIBCPP_INLINE_VISIBILITY hash_map() {__table_.rehash(193);}
 
523
    explicit hash_map(size_type __n, const hasher& __hf = hasher(),
 
524
                           const key_equal& __eql = key_equal());
 
525
    hash_map(size_type __n, const hasher& __hf,
 
526
                  const key_equal& __eql,
 
527
                  const allocator_type& __a);
 
528
    template <class _InputIterator>
 
529
        hash_map(_InputIterator __first, _InputIterator __last);
 
530
    template <class _InputIterator>
 
531
        hash_map(_InputIterator __first, _InputIterator __last,
 
532
                      size_type __n, const hasher& __hf = hasher(),
 
533
                      const key_equal& __eql = key_equal());
 
534
    template <class _InputIterator>
 
535
        hash_map(_InputIterator __first, _InputIterator __last,
 
536
                      size_type __n, const hasher& __hf,
 
537
                      const key_equal& __eql,
 
538
                      const allocator_type& __a);
 
539
    hash_map(const hash_map& __u);
 
540
 
 
541
    _LIBCPP_INLINE_VISIBILITY
 
542
    allocator_type get_allocator() const
 
543
        {return allocator_type(__table_.__node_alloc());}
 
544
 
 
545
    _LIBCPP_INLINE_VISIBILITY
 
546
    bool      empty() const {return __table_.size() == 0;}
 
547
    _LIBCPP_INLINE_VISIBILITY
 
548
    size_type size() const  {return __table_.size();}
 
549
    _LIBCPP_INLINE_VISIBILITY
 
550
    size_type max_size() const {return __table_.max_size();}
 
551
 
 
552
    _LIBCPP_INLINE_VISIBILITY
 
553
    iterator       begin()        {return __table_.begin();}
 
554
    _LIBCPP_INLINE_VISIBILITY
 
555
    iterator       end()          {return __table_.end();}
 
556
    _LIBCPP_INLINE_VISIBILITY
 
557
    const_iterator begin()  const {return __table_.begin();}
 
558
    _LIBCPP_INLINE_VISIBILITY
 
559
    const_iterator end()    const {return __table_.end();}
 
560
 
 
561
    _LIBCPP_INLINE_VISIBILITY
 
562
    pair<iterator, bool> insert(const value_type& __x)
 
563
        {return __table_.__insert_unique(__x);}
 
564
    _LIBCPP_INLINE_VISIBILITY
 
565
    iterator insert(const_iterator, const value_type& __x) {return insert(__x).first;}
 
566
    template <class _InputIterator>
 
567
        void insert(_InputIterator __first, _InputIterator __last);
 
568
 
 
569
    _LIBCPP_INLINE_VISIBILITY
 
570
    void erase(const_iterator __p) {__table_.erase(__p.__i_);}
 
571
    _LIBCPP_INLINE_VISIBILITY
 
572
    size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
 
573
    _LIBCPP_INLINE_VISIBILITY
 
574
    void erase(const_iterator __first, const_iterator __last)
 
575
        {__table_.erase(__first.__i_, __last.__i_);}
 
576
    _LIBCPP_INLINE_VISIBILITY
 
577
    void clear() {__table_.clear();}
 
578
 
 
579
    _LIBCPP_INLINE_VISIBILITY
 
580
    void swap(hash_map& __u) {__table_.swap(__u.__table_);}
 
581
 
 
582
    _LIBCPP_INLINE_VISIBILITY
 
583
    hasher hash_funct() const
 
584
        {return __table_.hash_function().hash_function();}
 
585
    _LIBCPP_INLINE_VISIBILITY
 
586
    key_equal key_eq() const
 
587
        {return __table_.key_eq().key_eq();}
 
588
 
 
589
    _LIBCPP_INLINE_VISIBILITY
 
590
    iterator       find(const key_type& __k)       {return __table_.find(__k);}
 
591
    _LIBCPP_INLINE_VISIBILITY
 
592
    const_iterator find(const key_type& __k) const {return __table_.find(__k);}
 
593
    _LIBCPP_INLINE_VISIBILITY
 
594
    size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
 
595
    _LIBCPP_INLINE_VISIBILITY
 
596
    pair<iterator, iterator>             equal_range(const key_type& __k)
 
597
        {return __table_.__equal_range_unique(__k);}
 
598
    _LIBCPP_INLINE_VISIBILITY
 
599
    pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
 
600
        {return __table_.__equal_range_unique(__k);}
 
601
 
 
602
    mapped_type& operator[](const key_type& __k);
 
603
 
 
604
    _LIBCPP_INLINE_VISIBILITY
 
605
    size_type bucket_count() const {return __table_.bucket_count();}
 
606
    _LIBCPP_INLINE_VISIBILITY
 
607
    size_type max_bucket_count() const {return __table_.max_bucket_count();}
 
608
 
 
609
    _LIBCPP_INLINE_VISIBILITY
 
610
    size_type elems_in_bucket(size_type __n) const
 
611
        {return __table_.bucket_size(__n);}
 
612
 
 
613
    _LIBCPP_INLINE_VISIBILITY
 
614
    void resize(size_type __n) {__table_.rehash(__n);}
 
615
 
 
616
private:
 
617
    __node_holder __construct_node(const key_type& __k);
 
618
};
 
619
 
 
620
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
621
hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(
 
622
        size_type __n, const hasher& __hf, const key_equal& __eql)
 
623
    : __table_(__hf, __eql)
 
624
{
 
625
    __table_.rehash(__n);
 
626
}
 
627
 
 
628
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
629
hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(
 
630
        size_type __n, const hasher& __hf, const key_equal& __eql,
 
631
        const allocator_type& __a)
 
632
    : __table_(__hf, __eql, __a)
 
633
{
 
634
    __table_.rehash(__n);
 
635
}
 
636
 
 
637
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
638
template <class _InputIterator>
 
639
hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(
 
640
        _InputIterator __first, _InputIterator __last)
 
641
{
 
642
    __table_.rehash(193);
 
643
    insert(__first, __last);
 
644
}
 
645
 
 
646
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
647
template <class _InputIterator>
 
648
hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(
 
649
        _InputIterator __first, _InputIterator __last, size_type __n,
 
650
        const hasher& __hf, const key_equal& __eql)
 
651
    : __table_(__hf, __eql)
 
652
{
 
653
    __table_.rehash(__n);
 
654
    insert(__first, __last);
 
655
}
 
656
 
 
657
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
658
template <class _InputIterator>
 
659
hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(
 
660
        _InputIterator __first, _InputIterator __last, size_type __n,
 
661
        const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
 
662
    : __table_(__hf, __eql, __a)
 
663
{
 
664
    __table_.rehash(__n);
 
665
    insert(__first, __last);
 
666
}
 
667
 
 
668
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
669
hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(
 
670
        const hash_map& __u)
 
671
    : __table_(__u.__table_)
 
672
{
 
673
    __table_.rehash(__u.bucket_count());
 
674
    insert(__u.begin(), __u.end());
 
675
}
 
676
 
 
677
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
678
typename hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
 
679
hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(const key_type& __k)
 
680
{
 
681
    __node_allocator& __na = __table_.__node_alloc();
 
682
    __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
 
683
    __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first), __k);
 
684
    __h.get_deleter().__first_constructed = true;
 
685
    __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second));
 
686
    __h.get_deleter().__second_constructed = true;
 
687
    return _VSTD::move(__h);
 
688
}
 
689
 
 
690
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
691
template <class _InputIterator>
 
692
inline _LIBCPP_INLINE_VISIBILITY
 
693
void
 
694
hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
 
695
                                                       _InputIterator __last)
 
696
{
 
697
    for (; __first != __last; ++__first)
 
698
        __table_.__insert_unique(*__first);
 
699
}
 
700
 
 
701
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
702
_Tp&
 
703
hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k)
 
704
{
 
705
    iterator __i = find(__k);
 
706
    if (__i != end())
 
707
        return __i->second;
 
708
    __node_holder __h = __construct_node(__k);
 
709
    pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
 
710
    __h.release();
 
711
    return __r.first->second;
 
712
}
 
713
 
 
714
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
715
inline _LIBCPP_INLINE_VISIBILITY
 
716
void
 
717
swap(hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 
718
     hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 
719
{
 
720
    __x.swap(__y);
 
721
}
 
722
 
 
723
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
724
bool
 
725
operator==(const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 
726
           const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 
727
{
 
728
    if (__x.size() != __y.size())
 
729
        return false;
 
730
    typedef typename hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
 
731
                                                                 const_iterator;
 
732
    for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();
 
733
            __i != __ex; ++__i)
 
734
    {
 
735
        const_iterator __j = __y.find(__i->first);
 
736
        if (__j == __ey || !(*__i == *__j))
 
737
            return false;
 
738
    }
 
739
    return true;
 
740
}
 
741
 
 
742
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
743
inline _LIBCPP_INLINE_VISIBILITY
 
744
bool
 
745
operator!=(const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 
746
           const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 
747
{
 
748
    return !(__x == __y);
 
749
}
 
750
 
 
751
template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
 
752
          class _Alloc = allocator<pair<const _Key, _Tp> > >
 
753
class _LIBCPP_TYPE_VIS hash_multimap
 
754
{
 
755
public:
 
756
    // types
 
757
    typedef _Key                                           key_type;
 
758
    typedef _Tp                                            mapped_type;
 
759
    typedef _Tp                                            data_type;
 
760
    typedef _Hash                                          hasher;
 
761
    typedef _Pred                                          key_equal;
 
762
    typedef _Alloc                                         allocator_type;
 
763
    typedef pair<const key_type, mapped_type>              value_type;
 
764
    typedef value_type&                                    reference;
 
765
    typedef const value_type&                              const_reference;
 
766
 
 
767
private:
 
768
    typedef pair<key_type, mapped_type>                    __value_type;
 
769
    typedef __hash_map_hasher<__value_type, hasher>   __hasher;
 
770
    typedef __hash_map_equal<__value_type, key_equal> __key_equal;
 
771
    typedef typename allocator_traits<allocator_type>::template
 
772
#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
 
773
            rebind_alloc<__value_type>
 
774
#else
 
775
            rebind_alloc<__value_type>::other
 
776
#endif
 
777
                                                           __allocator_type;
 
778
 
 
779
    typedef __hash_table<__value_type, __hasher,
 
780
                         __key_equal,  __allocator_type>   __table;
 
781
 
 
782
    __table __table_;
 
783
 
 
784
    typedef typename __table::__node_traits                __node_traits;
 
785
    typedef typename __table::__node_allocator             __node_allocator;
 
786
    typedef typename __table::__node                       __node;
 
787
    typedef __hash_map_node_destructor<__node_allocator>   _Dp;
 
788
    typedef unique_ptr<__node, _Dp>                         __node_holder;
 
789
    typedef allocator_traits<allocator_type>               __alloc_traits;
 
790
public:
 
791
    typedef typename __alloc_traits::pointer         pointer;
 
792
    typedef typename __alloc_traits::const_pointer   const_pointer;
 
793
    typedef typename __alloc_traits::size_type       size_type;
 
794
    typedef typename __alloc_traits::difference_type difference_type;
 
795
 
 
796
    typedef __hash_map_iterator<typename __table::iterator>       iterator;
 
797
    typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
 
798
 
 
799
    _LIBCPP_INLINE_VISIBILITY
 
800
    hash_multimap() {__table_.rehash(193);}
 
801
    explicit hash_multimap(size_type __n, const hasher& __hf = hasher(),
 
802
                                const key_equal& __eql = key_equal());
 
803
    hash_multimap(size_type __n, const hasher& __hf,
 
804
                                const key_equal& __eql,
 
805
                                const allocator_type& __a);
 
806
    template <class _InputIterator>
 
807
        hash_multimap(_InputIterator __first, _InputIterator __last);
 
808
    template <class _InputIterator>
 
809
        hash_multimap(_InputIterator __first, _InputIterator __last,
 
810
                      size_type __n, const hasher& __hf = hasher(),
 
811
                      const key_equal& __eql = key_equal());
 
812
    template <class _InputIterator>
 
813
        hash_multimap(_InputIterator __first, _InputIterator __last,
 
814
                      size_type __n, const hasher& __hf,
 
815
                      const key_equal& __eql,
 
816
                      const allocator_type& __a);
 
817
    hash_multimap(const hash_multimap& __u);
 
818
 
 
819
    _LIBCPP_INLINE_VISIBILITY
 
820
    allocator_type get_allocator() const
 
821
        {return allocator_type(__table_.__node_alloc());}
 
822
 
 
823
    _LIBCPP_INLINE_VISIBILITY
 
824
    bool      empty() const {return __table_.size() == 0;}
 
825
    _LIBCPP_INLINE_VISIBILITY
 
826
    size_type size() const  {return __table_.size();}
 
827
    _LIBCPP_INLINE_VISIBILITY
 
828
    size_type max_size() const {return __table_.max_size();}
 
829
 
 
830
    _LIBCPP_INLINE_VISIBILITY
 
831
    iterator       begin()        {return __table_.begin();}
 
832
    _LIBCPP_INLINE_VISIBILITY
 
833
    iterator       end()          {return __table_.end();}
 
834
    _LIBCPP_INLINE_VISIBILITY
 
835
    const_iterator begin()  const {return __table_.begin();}
 
836
    _LIBCPP_INLINE_VISIBILITY
 
837
    const_iterator end()    const {return __table_.end();}
 
838
 
 
839
    _LIBCPP_INLINE_VISIBILITY
 
840
    iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
 
841
    _LIBCPP_INLINE_VISIBILITY
 
842
    iterator insert(const_iterator, const value_type& __x) {return insert(__x);}
 
843
    template <class _InputIterator>
 
844
        void insert(_InputIterator __first, _InputIterator __last);
 
845
 
 
846
    _LIBCPP_INLINE_VISIBILITY
 
847
    void erase(const_iterator __p) {__table_.erase(__p.__i_);}
 
848
    _LIBCPP_INLINE_VISIBILITY
 
849
    size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
 
850
    _LIBCPP_INLINE_VISIBILITY
 
851
    void erase(const_iterator __first, const_iterator __last)
 
852
        {__table_.erase(__first.__i_, __last.__i_);}
 
853
    _LIBCPP_INLINE_VISIBILITY
 
854
    void clear() {__table_.clear();}
 
855
 
 
856
    _LIBCPP_INLINE_VISIBILITY
 
857
    void swap(hash_multimap& __u) {__table_.swap(__u.__table_);}
 
858
 
 
859
    _LIBCPP_INLINE_VISIBILITY
 
860
    hasher hash_funct() const
 
861
        {return __table_.hash_function().hash_function();}
 
862
    _LIBCPP_INLINE_VISIBILITY
 
863
    key_equal key_eq() const
 
864
        {return __table_.key_eq().key_eq();}
 
865
 
 
866
    _LIBCPP_INLINE_VISIBILITY
 
867
    iterator       find(const key_type& __k)       {return __table_.find(__k);}
 
868
    _LIBCPP_INLINE_VISIBILITY
 
869
    const_iterator find(const key_type& __k) const {return __table_.find(__k);}
 
870
    _LIBCPP_INLINE_VISIBILITY
 
871
    size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
 
872
    _LIBCPP_INLINE_VISIBILITY
 
873
    pair<iterator, iterator>             equal_range(const key_type& __k)
 
874
        {return __table_.__equal_range_multi(__k);}
 
875
    _LIBCPP_INLINE_VISIBILITY
 
876
    pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
 
877
        {return __table_.__equal_range_multi(__k);}
 
878
 
 
879
    _LIBCPP_INLINE_VISIBILITY
 
880
    size_type bucket_count() const {return __table_.bucket_count();}
 
881
    _LIBCPP_INLINE_VISIBILITY
 
882
    size_type max_bucket_count() const {return __table_.max_bucket_count();}
 
883
 
 
884
    _LIBCPP_INLINE_VISIBILITY
 
885
    size_type elems_in_bucket(size_type __n) const
 
886
        {return __table_.bucket_size(__n);}
 
887
 
 
888
    _LIBCPP_INLINE_VISIBILITY
 
889
    void resize(size_type __n) {__table_.rehash(__n);}
 
890
};
 
891
 
 
892
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
893
hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(
 
894
        size_type __n, const hasher& __hf, const key_equal& __eql)
 
895
    : __table_(__hf, __eql)
 
896
{
 
897
    __table_.rehash(__n);
 
898
}
 
899
 
 
900
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
901
hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(
 
902
        size_type __n, const hasher& __hf, const key_equal& __eql,
 
903
        const allocator_type& __a)
 
904
    : __table_(__hf, __eql, __a)
 
905
{
 
906
    __table_.rehash(__n);
 
907
}
 
908
 
 
909
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
910
template <class _InputIterator>
 
911
hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(
 
912
        _InputIterator __first, _InputIterator __last)
 
913
{
 
914
    __table_.rehash(193);
 
915
    insert(__first, __last);
 
916
}
 
917
 
 
918
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
919
template <class _InputIterator>
 
920
hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(
 
921
        _InputIterator __first, _InputIterator __last, size_type __n,
 
922
        const hasher& __hf, const key_equal& __eql)
 
923
    : __table_(__hf, __eql)
 
924
{
 
925
    __table_.rehash(__n);
 
926
    insert(__first, __last);
 
927
}
 
928
 
 
929
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
930
template <class _InputIterator>
 
931
hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(
 
932
        _InputIterator __first, _InputIterator __last, size_type __n,
 
933
        const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
 
934
    : __table_(__hf, __eql, __a)
 
935
{
 
936
    __table_.rehash(__n);
 
937
    insert(__first, __last);
 
938
}
 
939
 
 
940
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
941
hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(
 
942
        const hash_multimap& __u)
 
943
    : __table_(__u.__table_)
 
944
{
 
945
    __table_.rehash(__u.bucket_count());
 
946
    insert(__u.begin(), __u.end());
 
947
}
 
948
 
 
949
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
950
template <class _InputIterator>
 
951
inline _LIBCPP_INLINE_VISIBILITY
 
952
void
 
953
hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
 
954
                                                            _InputIterator __last)
 
955
{
 
956
    for (; __first != __last; ++__first)
 
957
        __table_.__insert_multi(*__first);
 
958
}
 
959
 
 
960
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
961
inline _LIBCPP_INLINE_VISIBILITY
 
962
void
 
963
swap(hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 
964
     hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 
965
{
 
966
    __x.swap(__y);
 
967
}
 
968
 
 
969
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
970
bool
 
971
operator==(const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 
972
           const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 
973
{
 
974
    if (__x.size() != __y.size())
 
975
        return false;
 
976
    typedef typename hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
 
977
                                                                 const_iterator;
 
978
    typedef pair<const_iterator, const_iterator> _EqRng;
 
979
    for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;)
 
980
    {
 
981
        _EqRng __xeq = __x.equal_range(__i->first);
 
982
        _EqRng __yeq = __y.equal_range(__i->first);
 
983
        if (_VSTD::distance(__xeq.first, __xeq.second) !=
 
984
            _VSTD::distance(__yeq.first, __yeq.second) ||
 
985
                  !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first))
 
986
            return false;
 
987
        __i = __xeq.second;
 
988
    }
 
989
    return true;
 
990
}
 
991
 
 
992
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
993
inline _LIBCPP_INLINE_VISIBILITY
 
994
bool
 
995
operator!=(const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 
996
           const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 
997
{
 
998
    return !(__x == __y);
 
999
}
 
1000
 
 
1001
} // __gnu_cxx
 
1002
 
 
1003
#endif  // _LIBCPP_HASH_MAP