← Back to branch summary

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

« back to all changes in this revision

Viewing changes to system/include/libcxx/unordered_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/unordered_map
 
1
// -*- C++ -*-
 
2
//===-------------------------- unordered_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_UNORDERED_MAP
 
12
#define _LIBCPP_UNORDERED_MAP
 
13
 
 
14
/*
 
15
 
 
16
    unordered_map synopsis
 
17
 
 
18
#include <initializer_list>
 
19
 
 
20
namespace std
 
21
{
 
22
 
 
23
template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
 
24
          class Alloc = allocator<pair<const Key, T>>>
 
25
class unordered_map
 
26
{
 
27
public:
 
28
    // types
 
29
    typedef Key                                                        key_type;
 
30
    typedef T                                                          mapped_type;
 
31
    typedef Hash                                                       hasher;
 
32
    typedef Pred                                                       key_equal;
 
33
    typedef Alloc                                                      allocator_type;
 
34
    typedef pair<const key_type, mapped_type>                          value_type;
 
35
    typedef value_type&                                                reference;
 
36
    typedef const value_type&                                          const_reference;
 
37
    typedef typename allocator_traits<allocator_type>::pointer         pointer;
 
38
    typedef typename allocator_traits<allocator_type>::const_pointer   const_pointer;
 
39
    typedef typename allocator_traits<allocator_type>::size_type       size_type;
 
40
    typedef typename allocator_traits<allocator_type>::difference_type difference_type;
 
41
 
 
42
    typedef /unspecified/ iterator;
 
43
    typedef /unspecified/ const_iterator;
 
44
    typedef /unspecified/ local_iterator;
 
45
    typedef /unspecified/ const_local_iterator;
 
46
 
 
47
    unordered_map()
 
48
        noexcept(
 
49
            is_nothrow_default_constructible<hasher>::value &&
 
50
            is_nothrow_default_constructible<key_equal>::value &&
 
51
            is_nothrow_default_constructible<allocator_type>::value);
 
52
    explicit unordered_map(size_type n, const hasher& hf = hasher(),
 
53
                           const key_equal& eql = key_equal(),
 
54
                           const allocator_type& a = allocator_type());
 
55
    template <class InputIterator>
 
56
        unordered_map(InputIterator f, InputIterator l,
 
57
                      size_type n = 0, const hasher& hf = hasher(),
 
58
                      const key_equal& eql = key_equal(),
 
59
                      const allocator_type& a = allocator_type());
 
60
    explicit unordered_map(const allocator_type&);
 
61
    unordered_map(const unordered_map&);
 
62
    unordered_map(const unordered_map&, const Allocator&);
 
63
    unordered_map(unordered_map&&)
 
64
        noexcept(
 
65
            is_nothrow_move_constructible<hasher>::value &&
 
66
            is_nothrow_move_constructible<key_equal>::value &&
 
67
            is_nothrow_move_constructible<allocator_type>::value);
 
68
    unordered_map(unordered_map&&, const Allocator&);
 
69
    unordered_map(initializer_list<value_type>, size_type n = 0,
 
70
                  const hasher& hf = hasher(), const key_equal& eql = key_equal(),
 
71
                  const allocator_type& a = allocator_type());
 
72
    ~unordered_map();
 
73
    unordered_map& operator=(const unordered_map&);
 
74
    unordered_map& operator=(unordered_map&&)
 
75
        noexcept(
 
76
            allocator_type::propagate_on_container_move_assignment::value &&
 
77
            is_nothrow_move_assignable<allocator_type>::value &&
 
78
            is_nothrow_move_assignable<hasher>::value &&
 
79
            is_nothrow_move_assignable<key_equal>::value);
 
80
    unordered_map& operator=(initializer_list<value_type>);
 
81
 
 
82
    allocator_type get_allocator() const noexcept;
 
83
 
 
84
    bool      empty() const noexcept;
 
85
    size_type size() const noexcept;
 
86
    size_type max_size() const noexcept;
 
87
 
 
88
    iterator       begin() noexcept;
 
89
    iterator       end() noexcept;
 
90
    const_iterator begin()  const noexcept;
 
91
    const_iterator end()    const noexcept;
 
92
    const_iterator cbegin() const noexcept;
 
93
    const_iterator cend()   const noexcept;
 
94
 
 
95
    template <class... Args>
 
96
        pair<iterator, bool> emplace(Args&&... args);
 
97
    template <class... Args>
 
98
        iterator emplace_hint(const_iterator position, Args&&... args);
 
99
    pair<iterator, bool> insert(const value_type& obj);
 
100
    template <class P>
 
101
        pair<iterator, bool> insert(P&& obj);
 
102
    iterator insert(const_iterator hint, const value_type& obj);
 
103
    template <class P>
 
104
        iterator insert(const_iterator hint, P&& obj);
 
105
    template <class InputIterator>
 
106
        void insert(InputIterator first, InputIterator last);
 
107
    void insert(initializer_list<value_type>);
 
108
 
 
109
    iterator erase(const_iterator position);
 
110
    size_type erase(const key_type& k);
 
111
    iterator erase(const_iterator first, const_iterator last);
 
112
    void clear() noexcept;
 
113
 
 
114
    void swap(unordered_map&)
 
115
        noexcept(
 
116
            (!allocator_type::propagate_on_container_swap::value ||
 
117
             __is_nothrow_swappable<allocator_type>::value) &&
 
118
            __is_nothrow_swappable<hasher>::value &&
 
119
            __is_nothrow_swappable<key_equal>::value);
 
120
 
 
121
    hasher hash_function() const;
 
122
    key_equal key_eq() const;
 
123
 
 
124
    iterator       find(const key_type& k);
 
125
    const_iterator find(const key_type& k) const;
 
126
    size_type count(const key_type& k) const;
 
127
    pair<iterator, iterator>             equal_range(const key_type& k);
 
128
    pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
 
129
 
 
130
    mapped_type& operator[](const key_type& k);
 
131
    mapped_type& operator[](key_type&& k);
 
132
 
 
133
    mapped_type&       at(const key_type& k);
 
134
    const mapped_type& at(const key_type& k) const;
 
135
 
 
136
    size_type bucket_count() const noexcept;
 
137
    size_type max_bucket_count() const noexcept;
 
138
 
 
139
    size_type bucket_size(size_type n) const;
 
140
    size_type bucket(const key_type& k) const;
 
141
 
 
142
    local_iterator       begin(size_type n);
 
143
    local_iterator       end(size_type n);
 
144
    const_local_iterator begin(size_type n) const;
 
145
    const_local_iterator end(size_type n) const;
 
146
    const_local_iterator cbegin(size_type n) const;
 
147
    const_local_iterator cend(size_type n) const;
 
148
 
 
149
    float load_factor() const noexcept;
 
150
    float max_load_factor() const noexcept;
 
151
    void max_load_factor(float z);
 
152
    void rehash(size_type n);
 
153
    void reserve(size_type n);
 
154
};
 
155
 
 
156
template <class Key, class T, class Hash, class Pred, class Alloc>
 
157
    void swap(unordered_map<Key, T, Hash, Pred, Alloc>& x,
 
158
              unordered_map<Key, T, Hash, Pred, Alloc>& y)
 
159
              noexcept(noexcept(x.swap(y)));
 
160
 
 
161
template <class Key, class T, class Hash, class Pred, class Alloc>
 
162
    bool
 
163
    operator==(const unordered_map<Key, T, Hash, Pred, Alloc>& x,
 
164
               const unordered_map<Key, T, Hash, Pred, Alloc>& y);
 
165
 
 
166
template <class Key, class T, class Hash, class Pred, class Alloc>
 
167
    bool
 
168
    operator!=(const unordered_map<Key, T, Hash, Pred, Alloc>& x,
 
169
               const unordered_map<Key, T, Hash, Pred, Alloc>& y);
 
170
 
 
171
template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
 
172
          class Alloc = allocator<pair<const Key, T>>>
 
173
class unordered_multimap
 
174
{
 
175
public:
 
176
    // types
 
177
    typedef Key                                                        key_type;
 
178
    typedef T                                                          mapped_type;
 
179
    typedef Hash                                                       hasher;
 
180
    typedef Pred                                                       key_equal;
 
181
    typedef Alloc                                                      allocator_type;
 
182
    typedef pair<const key_type, mapped_type>                          value_type;
 
183
    typedef value_type&                                                reference;
 
184
    typedef const value_type&                                          const_reference;
 
185
    typedef typename allocator_traits<allocator_type>::pointer         pointer;
 
186
    typedef typename allocator_traits<allocator_type>::const_pointer   const_pointer;
 
187
    typedef typename allocator_traits<allocator_type>::size_type       size_type;
 
188
    typedef typename allocator_traits<allocator_type>::difference_type difference_type;
 
189
 
 
190
    typedef /unspecified/ iterator;
 
191
    typedef /unspecified/ const_iterator;
 
192
    typedef /unspecified/ local_iterator;
 
193
    typedef /unspecified/ const_local_iterator;
 
194
 
 
195
    unordered_multimap()
 
196
        noexcept(
 
197
            is_nothrow_default_constructible<hasher>::value &&
 
198
            is_nothrow_default_constructible<key_equal>::value &&
 
199
            is_nothrow_default_constructible<allocator_type>::value);
 
200
    explicit unordered_multimap(size_type n, const hasher& hf = hasher(),
 
201
                           const key_equal& eql = key_equal(),
 
202
                           const allocator_type& a = allocator_type());
 
203
    template <class InputIterator>
 
204
        unordered_multimap(InputIterator f, InputIterator l,
 
205
                      size_type n = 0, const hasher& hf = hasher(),
 
206
                      const key_equal& eql = key_equal(),
 
207
                      const allocator_type& a = allocator_type());
 
208
    explicit unordered_multimap(const allocator_type&);
 
209
    unordered_multimap(const unordered_multimap&);
 
210
    unordered_multimap(const unordered_multimap&, const Allocator&);
 
211
    unordered_multimap(unordered_multimap&&)
 
212
        noexcept(
 
213
            is_nothrow_move_constructible<hasher>::value &&
 
214
            is_nothrow_move_constructible<key_equal>::value &&
 
215
            is_nothrow_move_constructible<allocator_type>::value);
 
216
    unordered_multimap(unordered_multimap&&, const Allocator&);
 
217
    unordered_multimap(initializer_list<value_type>, size_type n = 0,
 
218
                  const hasher& hf = hasher(), const key_equal& eql = key_equal(),
 
219
                  const allocator_type& a = allocator_type());
 
220
    ~unordered_multimap();
 
221
    unordered_multimap& operator=(const unordered_multimap&);
 
222
    unordered_multimap& operator=(unordered_multimap&&)
 
223
        noexcept(
 
224
            allocator_type::propagate_on_container_move_assignment::value &&
 
225
            is_nothrow_move_assignable<allocator_type>::value &&
 
226
            is_nothrow_move_assignable<hasher>::value &&
 
227
            is_nothrow_move_assignable<key_equal>::value);
 
228
    unordered_multimap& operator=(initializer_list<value_type>);
 
229
 
 
230
    allocator_type get_allocator() const noexcept;
 
231
 
 
232
    bool      empty() const noexcept;
 
233
    size_type size() const noexcept;
 
234
    size_type max_size() const noexcept;
 
235
 
 
236
    iterator       begin() noexcept;
 
237
    iterator       end() noexcept;
 
238
    const_iterator begin()  const noexcept;
 
239
    const_iterator end()    const noexcept;
 
240
    const_iterator cbegin() const noexcept;
 
241
    const_iterator cend()   const noexcept;
 
242
 
 
243
    template <class... Args>
 
244
        iterator emplace(Args&&... args);
 
245
    template <class... Args>
 
246
        iterator emplace_hint(const_iterator position, Args&&... args);
 
247
    iterator insert(const value_type& obj);
 
248
    template <class P>
 
249
        iterator insert(P&& obj);
 
250
    iterator insert(const_iterator hint, const value_type& obj);
 
251
    template <class P>
 
252
        iterator insert(const_iterator hint, P&& obj);
 
253
    template <class InputIterator>
 
254
        void insert(InputIterator first, InputIterator last);
 
255
    void insert(initializer_list<value_type>);
 
256
 
 
257
    iterator erase(const_iterator position);
 
258
    size_type erase(const key_type& k);
 
259
    iterator erase(const_iterator first, const_iterator last);
 
260
    void clear() noexcept;
 
261
 
 
262
    void swap(unordered_multimap&)
 
263
        noexcept(
 
264
            (!allocator_type::propagate_on_container_swap::value ||
 
265
             __is_nothrow_swappable<allocator_type>::value) &&
 
266
            __is_nothrow_swappable<hasher>::value &&
 
267
            __is_nothrow_swappable<key_equal>::value);
 
268
 
 
269
    hasher hash_function() const;
 
270
    key_equal key_eq() const;
 
271
 
 
272
    iterator       find(const key_type& k);
 
273
    const_iterator find(const key_type& k) const;
 
274
    size_type count(const key_type& k) const;
 
275
    pair<iterator, iterator>             equal_range(const key_type& k);
 
276
    pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
 
277
 
 
278
    size_type bucket_count() const noexcept;
 
279
    size_type max_bucket_count() const noexcept;
 
280
 
 
281
    size_type bucket_size(size_type n) const;
 
282
    size_type bucket(const key_type& k) const;
 
283
 
 
284
    local_iterator       begin(size_type n);
 
285
    local_iterator       end(size_type n);
 
286
    const_local_iterator begin(size_type n) const;
 
287
    const_local_iterator end(size_type n) const;
 
288
    const_local_iterator cbegin(size_type n) const;
 
289
    const_local_iterator cend(size_type n) const;
 
290
 
 
291
    float load_factor() const noexcept;
 
292
    float max_load_factor() const noexcept;
 
293
    void max_load_factor(float z);
 
294
    void rehash(size_type n);
 
295
    void reserve(size_type n);
 
296
};
 
297
 
 
298
template <class Key, class T, class Hash, class Pred, class Alloc>
 
299
    void swap(unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
 
300
              unordered_multimap<Key, T, Hash, Pred, Alloc>& y)
 
301
              noexcept(noexcept(x.swap(y)));
 
302
 
 
303
template <class Key, class T, class Hash, class Pred, class Alloc>
 
304
    bool
 
305
    operator==(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
 
306
               const unordered_multimap<Key, T, Hash, Pred, Alloc>& y);
 
307
 
 
308
template <class Key, class T, class Hash, class Pred, class Alloc>
 
309
    bool
 
310
    operator!=(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
 
311
               const unordered_multimap<Key, T, Hash, Pred, Alloc>& y);
 
312
 
 
313
}  // std
 
314
 
 
315
*/
 
316
 
 
317
#include <__config>
 
318
#include <__hash_table>
 
319
#include <functional>
 
320
#include <stdexcept>
 
321
 
 
322
#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 
323
#pragma GCC system_header
 
324
#endif
 
325
 
 
326
_LIBCPP_BEGIN_NAMESPACE_STD
 
327
 
 
328
template <class _Key, class _Tp, class _Hash, bool = is_empty<_Hash>::value
 
329
#if __has_feature(is_final)
 
330
                                         && !__is_final(_Hash)
 
331
#endif
 
332
         >
 
333
class __unordered_map_hasher
 
334
    : private _Hash
 
335
{
 
336
    typedef pair<typename remove_const<_Key>::type, _Tp> _Pp;
 
337
    typedef pair<const _Key, _Tp> _Cp;
 
338
public:
 
339
    _LIBCPP_INLINE_VISIBILITY
 
340
    __unordered_map_hasher()
 
341
        _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value)
 
342
        : _Hash() {}
 
343
    _LIBCPP_INLINE_VISIBILITY
 
344
    __unordered_map_hasher(const _Hash& __h)
 
345
        _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value)
 
346
        : _Hash(__h) {}
 
347
    _LIBCPP_INLINE_VISIBILITY
 
348
    const _Hash& hash_function() const _NOEXCEPT {return *this;}
 
349
    _LIBCPP_INLINE_VISIBILITY
 
350
    size_t operator()(const _Pp& __x) const
 
351
        {return static_cast<const _Hash&>(*this)(__x.first);}
 
352
    _LIBCPP_INLINE_VISIBILITY
 
353
    size_t operator()(const _Cp& __x) const
 
354
        {return static_cast<const _Hash&>(*this)(__x.first);}
 
355
    _LIBCPP_INLINE_VISIBILITY
 
356
    size_t operator()(const _Key& __x) const
 
357
        {return static_cast<const _Hash&>(*this)(__x);}
 
358
};
 
359
 
 
360
template <class _Key, class _Tp, class _Hash>
 
361
class __unordered_map_hasher<_Key, _Tp, _Hash, false>
 
362
{
 
363
    _Hash __hash_;
 
364
 
 
365
    typedef pair<typename remove_const<_Key>::type, _Tp> _Pp;
 
366
    typedef pair<const _Key, _Tp> _Cp;
 
367
public:
 
368
    _LIBCPP_INLINE_VISIBILITY
 
369
    __unordered_map_hasher()
 
370
        _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value)
 
371
        : __hash_() {}
 
372
    _LIBCPP_INLINE_VISIBILITY
 
373
    __unordered_map_hasher(const _Hash& __h)
 
374
        _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value)
 
375
        : __hash_(__h) {}
 
376
    _LIBCPP_INLINE_VISIBILITY
 
377
    const _Hash& hash_function() const _NOEXCEPT {return __hash_;}
 
378
    _LIBCPP_INLINE_VISIBILITY
 
379
    size_t operator()(const _Pp& __x) const
 
380
        {return __hash_(__x.first);}
 
381
    _LIBCPP_INLINE_VISIBILITY
 
382
    size_t operator()(const _Cp& __x) const
 
383
        {return __hash_(__x.first);}
 
384
    _LIBCPP_INLINE_VISIBILITY
 
385
    size_t operator()(const _Key& __x) const
 
386
        {return __hash_(__x);}
 
387
};
 
388
 
 
389
template <class _Key, class _Tp, class _Pred, bool = is_empty<_Pred>::value
 
390
#if __has_feature(is_final)
 
391
                                         && !__is_final(_Pred)
 
392
#endif
 
393
         >
 
394
class __unordered_map_equal
 
395
    : private _Pred
 
396
{
 
397
    typedef pair<typename remove_const<_Key>::type, _Tp> _Pp;
 
398
    typedef pair<const _Key, _Tp> _Cp;
 
399
public:
 
400
    _LIBCPP_INLINE_VISIBILITY
 
401
    __unordered_map_equal()
 
402
        _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value)
 
403
        : _Pred() {}
 
404
    _LIBCPP_INLINE_VISIBILITY
 
405
    __unordered_map_equal(const _Pred& __p)
 
406
        _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value)
 
407
        : _Pred(__p) {}
 
408
    _LIBCPP_INLINE_VISIBILITY
 
409
    const _Pred& key_eq() const _NOEXCEPT {return *this;}
 
410
    _LIBCPP_INLINE_VISIBILITY
 
411
    bool operator()(const _Pp& __x, const _Pp& __y) const
 
412
        {return static_cast<const _Pred&>(*this)(__x.first, __y.first);}
 
413
    _LIBCPP_INLINE_VISIBILITY
 
414
    bool operator()(const _Pp& __x, const _Cp& __y) const
 
415
        {return static_cast<const _Pred&>(*this)(__x.first, __y.first);}
 
416
    _LIBCPP_INLINE_VISIBILITY
 
417
    bool operator()(const _Pp& __x, const _Key& __y) const
 
418
        {return static_cast<const _Pred&>(*this)(__x.first, __y);}
 
419
    _LIBCPP_INLINE_VISIBILITY
 
420
    bool operator()(const _Cp& __x, const _Pp& __y) const
 
421
        {return static_cast<const _Pred&>(*this)(__x.first, __y.first);}
 
422
    _LIBCPP_INLINE_VISIBILITY
 
423
    bool operator()(const _Cp& __x, const _Cp& __y) const
 
424
        {return static_cast<const _Pred&>(*this)(__x.first, __y.first);}
 
425
    _LIBCPP_INLINE_VISIBILITY
 
426
    bool operator()(const _Cp& __x, const _Key& __y) const
 
427
        {return static_cast<const _Pred&>(*this)(__x.first, __y);}
 
428
    _LIBCPP_INLINE_VISIBILITY
 
429
    bool operator()(const _Key& __x, const _Pp& __y) const
 
430
        {return static_cast<const _Pred&>(*this)(__x, __y.first);}
 
431
    _LIBCPP_INLINE_VISIBILITY
 
432
    bool operator()(const _Key& __x, const _Cp& __y) const
 
433
        {return static_cast<const _Pred&>(*this)(__x, __y.first);}
 
434
    _LIBCPP_INLINE_VISIBILITY
 
435
    bool operator()(const _Key& __x, const _Key& __y) const
 
436
        {return static_cast<const _Pred&>(*this)(__x, __y);}
 
437
};
 
438
 
 
439
template <class _Key, class _Tp, class _Pred>
 
440
class __unordered_map_equal<_Key, _Tp, _Pred, false>
 
441
{
 
442
    _Pred __pred_;
 
443
 
 
444
    typedef pair<typename remove_const<_Key>::type, _Tp> _Pp;
 
445
    typedef pair<const _Key, _Tp> _Cp;
 
446
public:
 
447
    _LIBCPP_INLINE_VISIBILITY
 
448
    __unordered_map_equal()
 
449
        _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value)
 
450
        : __pred_() {}
 
451
    _LIBCPP_INLINE_VISIBILITY
 
452
    __unordered_map_equal(const _Pred& __p)
 
453
        _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value)
 
454
        : __pred_(__p) {}
 
455
    _LIBCPP_INLINE_VISIBILITY
 
456
    const _Pred& key_eq() const _NOEXCEPT {return __pred_;}
 
457
    _LIBCPP_INLINE_VISIBILITY
 
458
    bool operator()(const _Pp& __x, const _Pp& __y) const
 
459
        {return __pred_(__x.first, __y.first);}
 
460
    _LIBCPP_INLINE_VISIBILITY
 
461
    bool operator()(const _Pp& __x, const _Cp& __y) const
 
462
        {return __pred_(__x.first, __y.first);}
 
463
    _LIBCPP_INLINE_VISIBILITY
 
464
    bool operator()(const _Pp& __x, const _Key& __y) const
 
465
        {return __pred_(__x.first, __y);}
 
466
    _LIBCPP_INLINE_VISIBILITY
 
467
    bool operator()(const _Cp& __x, const _Pp& __y) const
 
468
        {return __pred_(__x.first, __y.first);}
 
469
    _LIBCPP_INLINE_VISIBILITY
 
470
    bool operator()(const _Cp& __x, const _Cp& __y) const
 
471
        {return __pred_(__x.first, __y.first);}
 
472
    _LIBCPP_INLINE_VISIBILITY
 
473
    bool operator()(const _Cp& __x, const _Key& __y) const
 
474
        {return __pred_(__x.first, __y);}
 
475
    _LIBCPP_INLINE_VISIBILITY
 
476
    bool operator()(const _Key& __x, const _Pp& __y) const
 
477
        {return __pred_(__x, __y.first);}
 
478
    _LIBCPP_INLINE_VISIBILITY
 
479
    bool operator()(const _Key& __x, const _Cp& __y) const
 
480
        {return __pred_(__x, __y.first);}
 
481
    _LIBCPP_INLINE_VISIBILITY
 
482
    bool operator()(const _Key& __x, const _Key& __y) const
 
483
        {return __pred_(__x, __y);}
 
484
};
 
485
 
 
486
template <class _Alloc>
 
487
class __hash_map_node_destructor
 
488
{
 
489
    typedef _Alloc                              allocator_type;
 
490
    typedef allocator_traits<allocator_type>    __alloc_traits;
 
491
    typedef typename __alloc_traits::value_type::value_type value_type;
 
492
public:
 
493
    typedef typename __alloc_traits::pointer    pointer;
 
494
private:
 
495
    typedef typename value_type::first_type     first_type;
 
496
    typedef typename value_type::second_type    second_type;
 
497
 
 
498
    allocator_type& __na_;
 
499
 
 
500
    __hash_map_node_destructor& operator=(const __hash_map_node_destructor&);
 
501
 
 
502
public:
 
503
    bool __first_constructed;
 
504
    bool __second_constructed;
 
505
 
 
506
    _LIBCPP_INLINE_VISIBILITY
 
507
    explicit __hash_map_node_destructor(allocator_type& __na) _NOEXCEPT
 
508
        : __na_(__na),
 
509
          __first_constructed(false),
 
510
          __second_constructed(false)
 
511
        {}
 
512
 
 
513
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
514
    _LIBCPP_INLINE_VISIBILITY
 
515
    __hash_map_node_destructor(__hash_node_destructor<allocator_type>&& __x)
 
516
        _NOEXCEPT
 
517
        : __na_(__x.__na_),
 
518
          __first_constructed(__x.__value_constructed),
 
519
          __second_constructed(__x.__value_constructed)
 
520
        {
 
521
            __x.__value_constructed = false;
 
522
        }
 
523
#else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
524
    _LIBCPP_INLINE_VISIBILITY
 
525
    __hash_map_node_destructor(const __hash_node_destructor<allocator_type>& __x)
 
526
        : __na_(__x.__na_),
 
527
          __first_constructed(__x.__value_constructed),
 
528
          __second_constructed(__x.__value_constructed)
 
529
        {
 
530
            const_cast<bool&>(__x.__value_constructed) = false;
 
531
        }
 
532
#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
533
 
 
534
    _LIBCPP_INLINE_VISIBILITY
 
535
    void operator()(pointer __p) _NOEXCEPT
 
536
    {
 
537
        if (__second_constructed)
 
538
            __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.second));
 
539
        if (__first_constructed)
 
540
            __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.first));
 
541
        if (__p)
 
542
            __alloc_traits::deallocate(__na_, __p, 1);
 
543
    }
 
544
};
 
545
 
 
546
template <class _HashIterator>
 
547
class _LIBCPP_TYPE_VIS __hash_map_iterator
 
548
{
 
549
    _HashIterator __i_;
 
550
 
 
551
    typedef pointer_traits<typename _HashIterator::pointer>      __pointer_traits;
 
552
    typedef const typename _HashIterator::value_type::first_type key_type;
 
553
    typedef typename _HashIterator::value_type::second_type      mapped_type;
 
554
public:
 
555
    typedef forward_iterator_tag                                 iterator_category;
 
556
    typedef pair<key_type, mapped_type>                          value_type;
 
557
    typedef typename _HashIterator::difference_type              difference_type;
 
558
    typedef value_type&                                          reference;
 
559
    typedef typename __pointer_traits::template
 
560
#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
 
561
            rebind<value_type>
 
562
#else
 
563
            rebind<value_type>::other
 
564
#endif
 
565
                                                                 pointer;
 
566
 
 
567
    _LIBCPP_INLINE_VISIBILITY
 
568
    __hash_map_iterator() _NOEXCEPT {}
 
569
 
 
570
    _LIBCPP_INLINE_VISIBILITY
 
571
    __hash_map_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
 
572
 
 
573
    _LIBCPP_INLINE_VISIBILITY
 
574
    reference operator*() const {return *operator->();}
 
575
    _LIBCPP_INLINE_VISIBILITY
 
576
    pointer operator->() const {return (pointer)__i_.operator->();}
 
577
 
 
578
    _LIBCPP_INLINE_VISIBILITY
 
579
    __hash_map_iterator& operator++() {++__i_; return *this;}
 
580
    _LIBCPP_INLINE_VISIBILITY
 
581
    __hash_map_iterator operator++(int)
 
582
    {
 
583
        __hash_map_iterator __t(*this);
 
584
        ++(*this);
 
585
        return __t;
 
586
    }
 
587
 
 
588
    friend _LIBCPP_INLINE_VISIBILITY
 
589
        bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y)
 
590
        {return __x.__i_ == __y.__i_;}
 
591
    friend _LIBCPP_INLINE_VISIBILITY
 
592
        bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y)
 
593
        {return __x.__i_ != __y.__i_;}
 
594
 
 
595
    template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_map;
 
596
    template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_multimap;
 
597
    template <class> friend class _LIBCPP_TYPE_VIS __hash_const_iterator;
 
598
    template <class> friend class _LIBCPP_TYPE_VIS __hash_const_local_iterator;
 
599
    template <class> friend class _LIBCPP_TYPE_VIS __hash_map_const_iterator;
 
600
};
 
601
 
 
602
template <class _HashIterator>
 
603
class _LIBCPP_TYPE_VIS __hash_map_const_iterator
 
604
{
 
605
    _HashIterator __i_;
 
606
 
 
607
    typedef pointer_traits<typename _HashIterator::pointer>      __pointer_traits;
 
608
    typedef const typename _HashIterator::value_type::first_type key_type;
 
609
    typedef typename _HashIterator::value_type::second_type      mapped_type;
 
610
public:
 
611
    typedef forward_iterator_tag                                 iterator_category;
 
612
    typedef pair<key_type, mapped_type>                          value_type;
 
613
    typedef typename _HashIterator::difference_type              difference_type;
 
614
    typedef const value_type&                                    reference;
 
615
    typedef typename __pointer_traits::template
 
616
#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
 
617
            rebind<const value_type>
 
618
#else
 
619
            rebind<const value_type>::other
 
620
#endif
 
621
                                                                 pointer;
 
622
 
 
623
    _LIBCPP_INLINE_VISIBILITY
 
624
    __hash_map_const_iterator() _NOEXCEPT {}
 
625
 
 
626
    _LIBCPP_INLINE_VISIBILITY
 
627
    __hash_map_const_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
 
628
    _LIBCPP_INLINE_VISIBILITY
 
629
    __hash_map_const_iterator(
 
630
            __hash_map_iterator<typename _HashIterator::__non_const_iterator> __i)
 
631
                 _NOEXCEPT
 
632
                : __i_(__i.__i_) {}
 
633
 
 
634
    _LIBCPP_INLINE_VISIBILITY
 
635
    reference operator*() const {return *operator->();}
 
636
    _LIBCPP_INLINE_VISIBILITY
 
637
    pointer operator->() const {return (pointer)__i_.operator->();}
 
638
 
 
639
    _LIBCPP_INLINE_VISIBILITY
 
640
    __hash_map_const_iterator& operator++() {++__i_; return *this;}
 
641
    _LIBCPP_INLINE_VISIBILITY
 
642
    __hash_map_const_iterator operator++(int)
 
643
    {
 
644
        __hash_map_const_iterator __t(*this);
 
645
        ++(*this);
 
646
        return __t;
 
647
    }
 
648
 
 
649
    friend _LIBCPP_INLINE_VISIBILITY
 
650
        bool operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)
 
651
        {return __x.__i_ == __y.__i_;}
 
652
    friend _LIBCPP_INLINE_VISIBILITY
 
653
        bool operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)
 
654
        {return __x.__i_ != __y.__i_;}
 
655
 
 
656
    template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_map;
 
657
    template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_multimap;
 
658
    template <class> friend class _LIBCPP_TYPE_VIS __hash_const_iterator;
 
659
    template <class> friend class _LIBCPP_TYPE_VIS __hash_const_local_iterator;
 
660
};
 
661
 
 
662
template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
 
663
          class _Alloc = allocator<pair<const _Key, _Tp> > >
 
664
class _LIBCPP_TYPE_VIS unordered_map
 
665
{
 
666
public:
 
667
    // types
 
668
    typedef _Key                                           key_type;
 
669
    typedef _Tp                                            mapped_type;
 
670
    typedef _Hash                                          hasher;
 
671
    typedef _Pred                                          key_equal;
 
672
    typedef _Alloc                                         allocator_type;
 
673
    typedef pair<const key_type, mapped_type>              value_type;
 
674
    typedef value_type&                                    reference;
 
675
    typedef const value_type&                              const_reference;
 
676
 
 
677
private:
 
678
    typedef pair<key_type, mapped_type>                    __value_type;
 
679
    typedef __unordered_map_hasher<key_type, mapped_type, hasher>   __hasher;
 
680
    typedef __unordered_map_equal<key_type, mapped_type, key_equal> __key_equal;
 
681
    typedef typename allocator_traits<allocator_type>::template
 
682
#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
 
683
            rebind_alloc<__value_type>
 
684
#else
 
685
            rebind_alloc<__value_type>::other
 
686
#endif
 
687
                                                           __allocator_type;
 
688
 
 
689
    typedef __hash_table<__value_type, __hasher,
 
690
                         __key_equal,  __allocator_type>   __table;
 
691
 
 
692
    __table __table_;
 
693
 
 
694
    typedef typename __table::__node_pointer               __node_pointer;
 
695
    typedef typename __table::__node_const_pointer         __node_const_pointer;
 
696
    typedef typename __table::__node_traits                __node_traits;
 
697
    typedef typename __table::__node_allocator             __node_allocator;
 
698
    typedef typename __table::__node                       __node;
 
699
    typedef __hash_map_node_destructor<__node_allocator>   _Dp;
 
700
    typedef unique_ptr<__node, _Dp>                         __node_holder;
 
701
    typedef allocator_traits<allocator_type>               __alloc_traits;
 
702
public:
 
703
    typedef typename __alloc_traits::pointer         pointer;
 
704
    typedef typename __alloc_traits::const_pointer   const_pointer;
 
705
    typedef typename __alloc_traits::size_type       size_type;
 
706
    typedef typename __alloc_traits::difference_type difference_type;
 
707
 
 
708
    typedef __hash_map_iterator<typename __table::iterator>       iterator;
 
709
    typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
 
710
    typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
 
711
    typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
 
712
 
 
713
    _LIBCPP_INLINE_VISIBILITY
 
714
    unordered_map()
 
715
        _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
 
716
        {} // = default;
 
717
    explicit unordered_map(size_type __n, const hasher& __hf = hasher(),
 
718
                           const key_equal& __eql = key_equal());
 
719
    unordered_map(size_type __n, const hasher& __hf,
 
720
                  const key_equal& __eql,
 
721
                  const allocator_type& __a);
 
722
    template <class _InputIterator>
 
723
        unordered_map(_InputIterator __first, _InputIterator __last);
 
724
    template <class _InputIterator>
 
725
        unordered_map(_InputIterator __first, _InputIterator __last,
 
726
                      size_type __n, const hasher& __hf = hasher(),
 
727
                      const key_equal& __eql = key_equal());
 
728
    template <class _InputIterator>
 
729
        unordered_map(_InputIterator __first, _InputIterator __last,
 
730
                      size_type __n, const hasher& __hf,
 
731
                      const key_equal& __eql,
 
732
                      const allocator_type& __a);
 
733
    explicit unordered_map(const allocator_type& __a);
 
734
    unordered_map(const unordered_map& __u);
 
735
    unordered_map(const unordered_map& __u, const allocator_type& __a);
 
736
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
737
    unordered_map(unordered_map&& __u)
 
738
        _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
 
739
    unordered_map(unordered_map&& __u, const allocator_type& __a);
 
740
#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
741
#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 
742
    unordered_map(initializer_list<value_type> __il);
 
743
    unordered_map(initializer_list<value_type> __il, size_type __n,
 
744
                  const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
 
745
    unordered_map(initializer_list<value_type> __il, size_type __n,
 
746
                  const hasher& __hf, const key_equal& __eql,
 
747
                  const allocator_type& __a);
 
748
#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 
749
    // ~unordered_map() = default;
 
750
    _LIBCPP_INLINE_VISIBILITY
 
751
    unordered_map& operator=(const unordered_map& __u)
 
752
    {
 
753
        __table_ = __u.__table_;
 
754
        return *this;
 
755
    }
 
756
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
757
    unordered_map& operator=(unordered_map&& __u)
 
758
        _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
 
759
#endif
 
760
#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 
761
    unordered_map& operator=(initializer_list<value_type> __il);
 
762
#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 
763
 
 
764
    _LIBCPP_INLINE_VISIBILITY
 
765
    allocator_type get_allocator() const _NOEXCEPT
 
766
        {return allocator_type(__table_.__node_alloc());}
 
767
 
 
768
    _LIBCPP_INLINE_VISIBILITY
 
769
    bool      empty() const _NOEXCEPT {return __table_.size() == 0;}
 
770
    _LIBCPP_INLINE_VISIBILITY
 
771
    size_type size() const _NOEXCEPT  {return __table_.size();}
 
772
    _LIBCPP_INLINE_VISIBILITY
 
773
    size_type max_size() const _NOEXCEPT {return __table_.max_size();}
 
774
 
 
775
    _LIBCPP_INLINE_VISIBILITY
 
776
    iterator       begin() _NOEXCEPT        {return __table_.begin();}
 
777
    _LIBCPP_INLINE_VISIBILITY
 
778
    iterator       end() _NOEXCEPT          {return __table_.end();}
 
779
    _LIBCPP_INLINE_VISIBILITY
 
780
    const_iterator begin()  const _NOEXCEPT {return __table_.begin();}
 
781
    _LIBCPP_INLINE_VISIBILITY
 
782
    const_iterator end()    const _NOEXCEPT {return __table_.end();}
 
783
    _LIBCPP_INLINE_VISIBILITY
 
784
    const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
 
785
    _LIBCPP_INLINE_VISIBILITY
 
786
    const_iterator cend()   const _NOEXCEPT {return __table_.end();}
 
787
 
 
788
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
789
#ifndef _LIBCPP_HAS_NO_VARIADICS
 
790
 
 
791
    template <class... _Args>
 
792
        pair<iterator, bool> emplace(_Args&&... __args);
 
793
 
 
794
    template <class... _Args>
 
795
        _LIBCPP_INLINE_VISIBILITY
 
796
        iterator emplace_hint(const_iterator, _Args&&... __args)
 
797
            {return emplace(_VSTD::forward<_Args>(__args)...).first;}
 
798
#endif  // _LIBCPP_HAS_NO_VARIADICS
 
799
#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
800
    _LIBCPP_INLINE_VISIBILITY
 
801
    pair<iterator, bool> insert(const value_type& __x)
 
802
        {return __table_.__insert_unique(__x);}
 
803
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
804
    template <class _Pp,
 
805
              class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
 
806
        _LIBCPP_INLINE_VISIBILITY
 
807
        pair<iterator, bool> insert(_Pp&& __x)
 
808
            {return __table_.__insert_unique(_VSTD::forward<_Pp>(__x));}
 
809
#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
810
    _LIBCPP_INLINE_VISIBILITY
 
811
    iterator insert(const_iterator, const value_type& __x)
 
812
        {return insert(__x).first;}
 
813
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
814
    template <class _Pp,
 
815
              class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
 
816
        _LIBCPP_INLINE_VISIBILITY
 
817
        iterator insert(const_iterator, _Pp&& __x)
 
818
            {return insert(_VSTD::forward<_Pp>(__x)).first;}
 
819
#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
820
    template <class _InputIterator>
 
821
        void insert(_InputIterator __first, _InputIterator __last);
 
822
#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 
823
    _LIBCPP_INLINE_VISIBILITY
 
824
    void insert(initializer_list<value_type> __il)
 
825
        {insert(__il.begin(), __il.end());}
 
826
#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 
827
 
 
828
    _LIBCPP_INLINE_VISIBILITY
 
829
    iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);}
 
830
    _LIBCPP_INLINE_VISIBILITY
 
831
    size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
 
832
    _LIBCPP_INLINE_VISIBILITY
 
833
    iterator erase(const_iterator __first, const_iterator __last)
 
834
        {return __table_.erase(__first.__i_, __last.__i_);}
 
835
    _LIBCPP_INLINE_VISIBILITY
 
836
    void clear() _NOEXCEPT {__table_.clear();}
 
837
 
 
838
    _LIBCPP_INLINE_VISIBILITY
 
839
    void swap(unordered_map& __u)
 
840
        _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
 
841
        {__table_.swap(__u.__table_);}
 
842
 
 
843
    _LIBCPP_INLINE_VISIBILITY
 
844
    hasher hash_function() const
 
845
        {return __table_.hash_function().hash_function();}
 
846
    _LIBCPP_INLINE_VISIBILITY
 
847
    key_equal key_eq() const
 
848
        {return __table_.key_eq().key_eq();}
 
849
 
 
850
    _LIBCPP_INLINE_VISIBILITY
 
851
    iterator       find(const key_type& __k)       {return __table_.find(__k);}
 
852
    _LIBCPP_INLINE_VISIBILITY
 
853
    const_iterator find(const key_type& __k) const {return __table_.find(__k);}
 
854
    _LIBCPP_INLINE_VISIBILITY
 
855
    size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
 
856
    _LIBCPP_INLINE_VISIBILITY
 
857
    pair<iterator, iterator>             equal_range(const key_type& __k)
 
858
        {return __table_.__equal_range_unique(__k);}
 
859
    _LIBCPP_INLINE_VISIBILITY
 
860
    pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
 
861
        {return __table_.__equal_range_unique(__k);}
 
862
 
 
863
    mapped_type& operator[](const key_type& __k);
 
864
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
865
    mapped_type& operator[](key_type&& __k);
 
866
#endif
 
867
 
 
868
    mapped_type&       at(const key_type& __k);
 
869
    const mapped_type& at(const key_type& __k) const;
 
870
 
 
871
    _LIBCPP_INLINE_VISIBILITY
 
872
    size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
 
873
    _LIBCPP_INLINE_VISIBILITY
 
874
    size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
 
875
 
 
876
    _LIBCPP_INLINE_VISIBILITY
 
877
    size_type bucket_size(size_type __n) const
 
878
        {return __table_.bucket_size(__n);}
 
879
    _LIBCPP_INLINE_VISIBILITY
 
880
    size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
 
881
 
 
882
    _LIBCPP_INLINE_VISIBILITY
 
883
    local_iterator       begin(size_type __n)        {return __table_.begin(__n);}
 
884
    _LIBCPP_INLINE_VISIBILITY
 
885
    local_iterator       end(size_type __n)          {return __table_.end(__n);}
 
886
    _LIBCPP_INLINE_VISIBILITY
 
887
    const_local_iterator begin(size_type __n) const  {return __table_.cbegin(__n);}
 
888
    _LIBCPP_INLINE_VISIBILITY
 
889
    const_local_iterator end(size_type __n) const    {return __table_.cend(__n);}
 
890
    _LIBCPP_INLINE_VISIBILITY
 
891
    const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
 
892
    _LIBCPP_INLINE_VISIBILITY
 
893
    const_local_iterator cend(size_type __n) const   {return __table_.cend(__n);}
 
894
 
 
895
    _LIBCPP_INLINE_VISIBILITY
 
896
    float load_factor() const _NOEXCEPT {return __table_.load_factor();}
 
897
    _LIBCPP_INLINE_VISIBILITY
 
898
    float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
 
899
    _LIBCPP_INLINE_VISIBILITY
 
900
    void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
 
901
    _LIBCPP_INLINE_VISIBILITY
 
902
    void rehash(size_type __n) {__table_.rehash(__n);}
 
903
    _LIBCPP_INLINE_VISIBILITY
 
904
    void reserve(size_type __n) {__table_.reserve(__n);}
 
905
 
 
906
private:
 
907
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
908
    __node_holder __construct_node();
 
909
    template <class _A0>
 
910
        typename enable_if
 
911
        <
 
912
            is_constructible<value_type, _A0>::value,
 
913
            __node_holder
 
914
        >::type
 
915
         __construct_node(_A0&& __a0);
 
916
    template <class _A0>
 
917
        typename enable_if
 
918
        <
 
919
            is_constructible<key_type, _A0>::value,
 
920
            __node_holder
 
921
        >::type
 
922
         __construct_node(_A0&& __a0);
 
923
#ifndef _LIBCPP_HAS_NO_VARIADICS
 
924
    template <class _A0, class _A1, class ..._Args>
 
925
        __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args);
 
926
#endif  // _LIBCPP_HAS_NO_VARIADICS
 
927
#else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
928
    __node_holder __construct_node(const key_type& __k);
 
929
#endif
 
930
};
 
931
 
 
932
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
933
unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
 
934
        size_type __n, const hasher& __hf, const key_equal& __eql)
 
935
    : __table_(__hf, __eql)
 
936
{
 
937
    __table_.rehash(__n);
 
938
}
 
939
 
 
940
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
941
unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
 
942
        size_type __n, const hasher& __hf, const key_equal& __eql,
 
943
        const allocator_type& __a)
 
944
    : __table_(__hf, __eql, __a)
 
945
{
 
946
    __table_.rehash(__n);
 
947
}
 
948
 
 
949
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
950
inline _LIBCPP_INLINE_VISIBILITY
 
951
unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
 
952
        const allocator_type& __a)
 
953
    : __table_(__a)
 
954
{
 
955
}
 
956
 
 
957
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
958
template <class _InputIterator>
 
959
unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
 
960
        _InputIterator __first, _InputIterator __last)
 
961
{
 
962
    insert(__first, __last);
 
963
}
 
964
 
 
965
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
966
template <class _InputIterator>
 
967
unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
 
968
        _InputIterator __first, _InputIterator __last, size_type __n,
 
969
        const hasher& __hf, const key_equal& __eql)
 
970
    : __table_(__hf, __eql)
 
971
{
 
972
    __table_.rehash(__n);
 
973
    insert(__first, __last);
 
974
}
 
975
 
 
976
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
977
template <class _InputIterator>
 
978
unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
 
979
        _InputIterator __first, _InputIterator __last, size_type __n,
 
980
        const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
 
981
    : __table_(__hf, __eql, __a)
 
982
{
 
983
    __table_.rehash(__n);
 
984
    insert(__first, __last);
 
985
}
 
986
 
 
987
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
988
unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
 
989
        const unordered_map& __u)
 
990
    : __table_(__u.__table_)
 
991
{
 
992
    __table_.rehash(__u.bucket_count());
 
993
    insert(__u.begin(), __u.end());
 
994
}
 
995
 
 
996
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
997
unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
 
998
        const unordered_map& __u, const allocator_type& __a)
 
999
    : __table_(__u.__table_, __a)
 
1000
{
 
1001
    __table_.rehash(__u.bucket_count());
 
1002
    insert(__u.begin(), __u.end());
 
1003
}
 
1004
 
 
1005
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
1006
 
 
1007
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
1008
inline _LIBCPP_INLINE_VISIBILITY
 
1009
unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
 
1010
        unordered_map&& __u)
 
1011
    _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
 
1012
    : __table_(_VSTD::move(__u.__table_))
 
1013
{
 
1014
}
 
1015
 
 
1016
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
1017
unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
 
1018
        unordered_map&& __u, const allocator_type& __a)
 
1019
    : __table_(_VSTD::move(__u.__table_), __a)
 
1020
{
 
1021
    if (__a != __u.get_allocator())
 
1022
    {
 
1023
        iterator __i = __u.begin();
 
1024
        while (__u.size() != 0)
 
1025
            __table_.__insert_unique(
 
1026
                _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_)
 
1027
                                    );
 
1028
    }
 
1029
}
 
1030
 
 
1031
#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
1032
 
 
1033
#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 
1034
 
 
1035
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
1036
unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
 
1037
        initializer_list<value_type> __il)
 
1038
{
 
1039
    insert(__il.begin(), __il.end());
 
1040
}
 
1041
 
 
1042
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
1043
unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
 
1044
        initializer_list<value_type> __il, size_type __n, const hasher& __hf,
 
1045
        const key_equal& __eql)
 
1046
    : __table_(__hf, __eql)
 
1047
{
 
1048
    __table_.rehash(__n);
 
1049
    insert(__il.begin(), __il.end());
 
1050
}
 
1051
 
 
1052
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
1053
unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
 
1054
        initializer_list<value_type> __il, size_type __n, const hasher& __hf,
 
1055
        const key_equal& __eql, const allocator_type& __a)
 
1056
    : __table_(__hf, __eql, __a)
 
1057
{
 
1058
    __table_.rehash(__n);
 
1059
    insert(__il.begin(), __il.end());
 
1060
}
 
1061
 
 
1062
#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 
1063
 
 
1064
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
1065
 
 
1066
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
1067
inline _LIBCPP_INLINE_VISIBILITY
 
1068
unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
 
1069
unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_map&& __u)
 
1070
    _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
 
1071
{
 
1072
    __table_ = _VSTD::move(__u.__table_);
 
1073
    return *this;
 
1074
}
 
1075
 
 
1076
#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
1077
 
 
1078
#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 
1079
 
 
1080
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
1081
inline _LIBCPP_INLINE_VISIBILITY
 
1082
unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
 
1083
unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(
 
1084
        initializer_list<value_type> __il)
 
1085
{
 
1086
    __table_.__assign_unique(__il.begin(), __il.end());
 
1087
    return *this;
 
1088
}
 
1089
 
 
1090
#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 
1091
 
 
1092
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
1093
 
 
1094
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
1095
typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
 
1096
unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node()
 
1097
{
 
1098
    __node_allocator& __na = __table_.__node_alloc();
 
1099
    __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
 
1100
    __node_traits::construct(__na, _VSTD::addressof(__h->__value_));
 
1101
    __h.get_deleter().__first_constructed = true;
 
1102
    __h.get_deleter().__second_constructed = true;
 
1103
    return __h;
 
1104
}
 
1105
 
 
1106
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
1107
template <class _A0>
 
1108
typename enable_if
 
1109
<
 
1110
    is_constructible<pair<const _Key, _Tp>, _A0>::value,
 
1111
    typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
 
1112
>::type
 
1113
unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
 
1114
{
 
1115
    __node_allocator& __na = __table_.__node_alloc();
 
1116
    __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
 
1117
    __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
 
1118
                             _VSTD::forward<_A0>(__a0));
 
1119
    __h.get_deleter().__first_constructed = true;
 
1120
    __h.get_deleter().__second_constructed = true;
 
1121
    return __h;
 
1122
}
 
1123
 
 
1124
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
1125
template <class _A0>
 
1126
typename enable_if
 
1127
<
 
1128
    is_constructible<_Key, _A0>::value,
 
1129
    typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
 
1130
>::type
 
1131
unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
 
1132
{
 
1133
    __node_allocator& __na = __table_.__node_alloc();
 
1134
    __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
 
1135
    __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first),
 
1136
                             _VSTD::forward<_A0>(__a0));
 
1137
    __h.get_deleter().__first_constructed = true;
 
1138
    __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second));
 
1139
    __h.get_deleter().__second_constructed = true;
 
1140
    return __h;
 
1141
}
 
1142
 
 
1143
#ifndef _LIBCPP_HAS_NO_VARIADICS
 
1144
 
 
1145
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
1146
template <class _A0, class _A1, class ..._Args>
 
1147
typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
 
1148
unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0,
 
1149
                                                                 _A1&& __a1,
 
1150
                                                                 _Args&&... __args)
 
1151
{
 
1152
    __node_allocator& __na = __table_.__node_alloc();
 
1153
    __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
 
1154
    __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
 
1155
                             _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1),
 
1156
                             _VSTD::forward<_Args>(__args)...);
 
1157
    __h.get_deleter().__first_constructed = true;
 
1158
    __h.get_deleter().__second_constructed = true;
 
1159
    return __h;
 
1160
}
 
1161
 
 
1162
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
1163
template <class... _Args>
 
1164
pair<typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator, bool>
 
1165
unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_Args&&... __args)
 
1166
{
 
1167
    __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
 
1168
    pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
 
1169
    if (__r.second)
 
1170
        __h.release();
 
1171
    return __r;
 
1172
}
 
1173
 
 
1174
#endif  // _LIBCPP_HAS_NO_VARIADICS
 
1175
#else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
1176
 
 
1177
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
1178
typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
 
1179
unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(const key_type& __k)
 
1180
{
 
1181
    __node_allocator& __na = __table_.__node_alloc();
 
1182
    __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
 
1183
    __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first), __k);
 
1184
    __h.get_deleter().__first_constructed = true;
 
1185
    __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second));
 
1186
    __h.get_deleter().__second_constructed = true;
 
1187
    return _VSTD::move(__h);
 
1188
}
 
1189
 
 
1190
#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
1191
 
 
1192
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
1193
template <class _InputIterator>
 
1194
inline _LIBCPP_INLINE_VISIBILITY
 
1195
void
 
1196
unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
 
1197
                                                       _InputIterator __last)
 
1198
{
 
1199
    for (; __first != __last; ++__first)
 
1200
        __table_.__insert_unique(*__first);
 
1201
}
 
1202
 
 
1203
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
1204
_Tp&
 
1205
unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k)
 
1206
{
 
1207
    iterator __i = find(__k);
 
1208
    if (__i != end())
 
1209
        return __i->second;
 
1210
    __node_holder __h = __construct_node(__k);
 
1211
    pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
 
1212
    __h.release();
 
1213
    return __r.first->second;
 
1214
}
 
1215
 
 
1216
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
1217
 
 
1218
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
1219
_Tp&
 
1220
unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&& __k)
 
1221
{
 
1222
    iterator __i = find(__k);
 
1223
    if (__i != end())
 
1224
        return __i->second;
 
1225
    __node_holder __h = __construct_node(_VSTD::move(__k));
 
1226
    pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
 
1227
    __h.release();
 
1228
    return __r.first->second;
 
1229
}
 
1230
 
 
1231
#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
1232
 
 
1233
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
1234
_Tp&
 
1235
unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k)
 
1236
{
 
1237
    iterator __i = find(__k);
 
1238
#ifndef _LIBCPP_NO_EXCEPTIONS
 
1239
    if (__i == end())
 
1240
        throw out_of_range("unordered_map::at: key not found");
 
1241
#endif  // _LIBCPP_NO_EXCEPTIONS
 
1242
    return __i->second;
 
1243
}
 
1244
 
 
1245
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
1246
const _Tp&
 
1247
unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) const
 
1248
{
 
1249
    const_iterator __i = find(__k);
 
1250
#ifndef _LIBCPP_NO_EXCEPTIONS
 
1251
    if (__i == end())
 
1252
        throw out_of_range("unordered_map::at: key not found");
 
1253
#endif  // _LIBCPP_NO_EXCEPTIONS
 
1254
    return __i->second;
 
1255
}
 
1256
 
 
1257
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
1258
inline _LIBCPP_INLINE_VISIBILITY
 
1259
void
 
1260
swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 
1261
     unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 
1262
    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
 
1263
{
 
1264
    __x.swap(__y);
 
1265
}
 
1266
 
 
1267
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
1268
bool
 
1269
operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 
1270
           const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 
1271
{
 
1272
    if (__x.size() != __y.size())
 
1273
        return false;
 
1274
    typedef typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
 
1275
                                                                 const_iterator;
 
1276
    for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();
 
1277
            __i != __ex; ++__i)
 
1278
    {
 
1279
        const_iterator __j = __y.find(__i->first);
 
1280
        if (__j == __ey || !(*__i == *__j))
 
1281
            return false;
 
1282
    }
 
1283
    return true;
 
1284
}
 
1285
 
 
1286
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
1287
inline _LIBCPP_INLINE_VISIBILITY
 
1288
bool
 
1289
operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 
1290
           const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 
1291
{
 
1292
    return !(__x == __y);
 
1293
}
 
1294
 
 
1295
template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
 
1296
          class _Alloc = allocator<pair<const _Key, _Tp> > >
 
1297
class _LIBCPP_TYPE_VIS unordered_multimap
 
1298
{
 
1299
public:
 
1300
    // types
 
1301
    typedef _Key                                           key_type;
 
1302
    typedef _Tp                                            mapped_type;
 
1303
    typedef _Hash                                          hasher;
 
1304
    typedef _Pred                                          key_equal;
 
1305
    typedef _Alloc                                         allocator_type;
 
1306
    typedef pair<const key_type, mapped_type>              value_type;
 
1307
    typedef value_type&                                    reference;
 
1308
    typedef const value_type&                              const_reference;
 
1309
 
 
1310
private:
 
1311
    typedef pair<key_type, mapped_type>                    __value_type;
 
1312
    typedef __unordered_map_hasher<key_type, mapped_type, hasher>   __hasher;
 
1313
    typedef __unordered_map_equal<key_type, mapped_type, key_equal> __key_equal;
 
1314
    typedef typename allocator_traits<allocator_type>::template
 
1315
#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
 
1316
            rebind_alloc<__value_type>
 
1317
#else
 
1318
            rebind_alloc<__value_type>::other
 
1319
#endif
 
1320
                                                           __allocator_type;
 
1321
 
 
1322
    typedef __hash_table<__value_type, __hasher,
 
1323
                         __key_equal,  __allocator_type>   __table;
 
1324
 
 
1325
    __table __table_;
 
1326
 
 
1327
    typedef typename __table::__node_traits                __node_traits;
 
1328
    typedef typename __table::__node_allocator             __node_allocator;
 
1329
    typedef typename __table::__node                       __node;
 
1330
    typedef __hash_map_node_destructor<__node_allocator>   _Dp;
 
1331
    typedef unique_ptr<__node, _Dp>                         __node_holder;
 
1332
    typedef allocator_traits<allocator_type>               __alloc_traits;
 
1333
public:
 
1334
    typedef typename __alloc_traits::pointer         pointer;
 
1335
    typedef typename __alloc_traits::const_pointer   const_pointer;
 
1336
    typedef typename __alloc_traits::size_type       size_type;
 
1337
    typedef typename __alloc_traits::difference_type difference_type;
 
1338
 
 
1339
    typedef __hash_map_iterator<typename __table::iterator>       iterator;
 
1340
    typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
 
1341
    typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
 
1342
    typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
 
1343
 
 
1344
    _LIBCPP_INLINE_VISIBILITY
 
1345
    unordered_multimap()
 
1346
        _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
 
1347
        {} // = default;
 
1348
    explicit unordered_multimap(size_type __n, const hasher& __hf = hasher(),
 
1349
                                const key_equal& __eql = key_equal());
 
1350
    unordered_multimap(size_type __n, const hasher& __hf,
 
1351
                                const key_equal& __eql,
 
1352
                                const allocator_type& __a);
 
1353
    template <class _InputIterator>
 
1354
        unordered_multimap(_InputIterator __first, _InputIterator __last);
 
1355
    template <class _InputIterator>
 
1356
        unordered_multimap(_InputIterator __first, _InputIterator __last,
 
1357
                      size_type __n, const hasher& __hf = hasher(),
 
1358
                      const key_equal& __eql = key_equal());
 
1359
    template <class _InputIterator>
 
1360
        unordered_multimap(_InputIterator __first, _InputIterator __last,
 
1361
                      size_type __n, const hasher& __hf,
 
1362
                      const key_equal& __eql,
 
1363
                      const allocator_type& __a);
 
1364
    explicit unordered_multimap(const allocator_type& __a);
 
1365
    unordered_multimap(const unordered_multimap& __u);
 
1366
    unordered_multimap(const unordered_multimap& __u, const allocator_type& __a);
 
1367
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
1368
    unordered_multimap(unordered_multimap&& __u)
 
1369
        _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
 
1370
    unordered_multimap(unordered_multimap&& __u, const allocator_type& __a);
 
1371
#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
1372
#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 
1373
    unordered_multimap(initializer_list<value_type> __il);
 
1374
    unordered_multimap(initializer_list<value_type> __il, size_type __n,
 
1375
                       const hasher& __hf = hasher(),
 
1376
                       const key_equal& __eql = key_equal());
 
1377
    unordered_multimap(initializer_list<value_type> __il, size_type __n,
 
1378
                       const hasher& __hf, const key_equal& __eql,
 
1379
                       const allocator_type& __a);
 
1380
#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 
1381
    // ~unordered_multimap() = default;
 
1382
    _LIBCPP_INLINE_VISIBILITY
 
1383
    unordered_multimap& operator=(const unordered_multimap& __u)
 
1384
    {
 
1385
        __table_ = __u.__table_;
 
1386
        return *this;
 
1387
    }
 
1388
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
1389
    unordered_multimap& operator=(unordered_multimap&& __u)
 
1390
        _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
 
1391
#endif
 
1392
#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 
1393
    unordered_multimap& operator=(initializer_list<value_type> __il);
 
1394
#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 
1395
 
 
1396
    _LIBCPP_INLINE_VISIBILITY
 
1397
    allocator_type get_allocator() const _NOEXCEPT
 
1398
        {return allocator_type(__table_.__node_alloc());}
 
1399
 
 
1400
    _LIBCPP_INLINE_VISIBILITY
 
1401
    bool      empty() const _NOEXCEPT {return __table_.size() == 0;}
 
1402
    _LIBCPP_INLINE_VISIBILITY
 
1403
    size_type size() const _NOEXCEPT  {return __table_.size();}
 
1404
    _LIBCPP_INLINE_VISIBILITY
 
1405
    size_type max_size() const _NOEXCEPT {return __table_.max_size();}
 
1406
 
 
1407
    _LIBCPP_INLINE_VISIBILITY
 
1408
    iterator       begin() _NOEXCEPT        {return __table_.begin();}
 
1409
    _LIBCPP_INLINE_VISIBILITY
 
1410
    iterator       end() _NOEXCEPT          {return __table_.end();}
 
1411
    _LIBCPP_INLINE_VISIBILITY
 
1412
    const_iterator begin()  const _NOEXCEPT {return __table_.begin();}
 
1413
    _LIBCPP_INLINE_VISIBILITY
 
1414
    const_iterator end()    const _NOEXCEPT {return __table_.end();}
 
1415
    _LIBCPP_INLINE_VISIBILITY
 
1416
    const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
 
1417
    _LIBCPP_INLINE_VISIBILITY
 
1418
    const_iterator cend()   const _NOEXCEPT {return __table_.end();}
 
1419
 
 
1420
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
1421
#ifndef _LIBCPP_HAS_NO_VARIADICS
 
1422
 
 
1423
    template <class... _Args>
 
1424
        iterator emplace(_Args&&... __args);
 
1425
 
 
1426
    template <class... _Args>
 
1427
        iterator emplace_hint(const_iterator __p, _Args&&... __args);
 
1428
#endif  // _LIBCPP_HAS_NO_VARIADICS
 
1429
#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
1430
    _LIBCPP_INLINE_VISIBILITY
 
1431
    iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
 
1432
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
1433
    template <class _Pp,
 
1434
              class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
 
1435
        _LIBCPP_INLINE_VISIBILITY
 
1436
        iterator insert(_Pp&& __x)
 
1437
            {return __table_.__insert_multi(_VSTD::forward<_Pp>(__x));}
 
1438
#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
1439
    _LIBCPP_INLINE_VISIBILITY
 
1440
    iterator insert(const_iterator __p, const value_type& __x)
 
1441
        {return __table_.__insert_multi(__p.__i_, __x);}
 
1442
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
1443
    template <class _Pp,
 
1444
              class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
 
1445
        _LIBCPP_INLINE_VISIBILITY
 
1446
        iterator insert(const_iterator __p, _Pp&& __x)
 
1447
            {return __table_.__insert_multi(__p.__i_, _VSTD::forward<_Pp>(__x));}
 
1448
#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
1449
    template <class _InputIterator>
 
1450
        void insert(_InputIterator __first, _InputIterator __last);
 
1451
#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 
1452
    _LIBCPP_INLINE_VISIBILITY
 
1453
    void insert(initializer_list<value_type> __il)
 
1454
        {insert(__il.begin(), __il.end());}
 
1455
#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 
1456
 
 
1457
    _LIBCPP_INLINE_VISIBILITY
 
1458
    iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);}
 
1459
    _LIBCPP_INLINE_VISIBILITY
 
1460
    size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
 
1461
    _LIBCPP_INLINE_VISIBILITY
 
1462
    iterator erase(const_iterator __first, const_iterator __last)
 
1463
        {return __table_.erase(__first.__i_, __last.__i_);}
 
1464
    _LIBCPP_INLINE_VISIBILITY
 
1465
    void clear() _NOEXCEPT {__table_.clear();}
 
1466
 
 
1467
    _LIBCPP_INLINE_VISIBILITY
 
1468
    void swap(unordered_multimap& __u)
 
1469
        _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
 
1470
        {__table_.swap(__u.__table_);}
 
1471
 
 
1472
    _LIBCPP_INLINE_VISIBILITY
 
1473
    hasher hash_function() const
 
1474
        {return __table_.hash_function().hash_function();}
 
1475
    _LIBCPP_INLINE_VISIBILITY
 
1476
    key_equal key_eq() const
 
1477
        {return __table_.key_eq().key_eq();}
 
1478
 
 
1479
    _LIBCPP_INLINE_VISIBILITY
 
1480
    iterator       find(const key_type& __k)       {return __table_.find(__k);}
 
1481
    _LIBCPP_INLINE_VISIBILITY
 
1482
    const_iterator find(const key_type& __k) const {return __table_.find(__k);}
 
1483
    _LIBCPP_INLINE_VISIBILITY
 
1484
    size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
 
1485
    _LIBCPP_INLINE_VISIBILITY
 
1486
    pair<iterator, iterator>             equal_range(const key_type& __k)
 
1487
        {return __table_.__equal_range_multi(__k);}
 
1488
    _LIBCPP_INLINE_VISIBILITY
 
1489
    pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
 
1490
        {return __table_.__equal_range_multi(__k);}
 
1491
 
 
1492
    _LIBCPP_INLINE_VISIBILITY
 
1493
    size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
 
1494
    _LIBCPP_INLINE_VISIBILITY
 
1495
    size_type max_bucket_count() const _NOEXCEPT
 
1496
        {return __table_.max_bucket_count();}
 
1497
 
 
1498
    _LIBCPP_INLINE_VISIBILITY
 
1499
    size_type bucket_size(size_type __n) const
 
1500
        {return __table_.bucket_size(__n);}
 
1501
    _LIBCPP_INLINE_VISIBILITY
 
1502
    size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
 
1503
 
 
1504
    _LIBCPP_INLINE_VISIBILITY
 
1505
    local_iterator       begin(size_type __n)        {return __table_.begin(__n);}
 
1506
    _LIBCPP_INLINE_VISIBILITY
 
1507
    local_iterator       end(size_type __n)          {return __table_.end(__n);}
 
1508
    _LIBCPP_INLINE_VISIBILITY
 
1509
    const_local_iterator begin(size_type __n) const  {return __table_.cbegin(__n);}
 
1510
    _LIBCPP_INLINE_VISIBILITY
 
1511
    const_local_iterator end(size_type __n) const    {return __table_.cend(__n);}
 
1512
    _LIBCPP_INLINE_VISIBILITY
 
1513
    const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
 
1514
    _LIBCPP_INLINE_VISIBILITY
 
1515
    const_local_iterator cend(size_type __n) const   {return __table_.cend(__n);}
 
1516
 
 
1517
    _LIBCPP_INLINE_VISIBILITY
 
1518
    float load_factor() const _NOEXCEPT {return __table_.load_factor();}
 
1519
    _LIBCPP_INLINE_VISIBILITY
 
1520
    float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
 
1521
    _LIBCPP_INLINE_VISIBILITY
 
1522
    void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
 
1523
    _LIBCPP_INLINE_VISIBILITY
 
1524
    void rehash(size_type __n) {__table_.rehash(__n);}
 
1525
    _LIBCPP_INLINE_VISIBILITY
 
1526
    void reserve(size_type __n) {__table_.reserve(__n);}
 
1527
 
 
1528
private:
 
1529
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
1530
    __node_holder __construct_node();
 
1531
    template <class _A0>
 
1532
        typename enable_if
 
1533
        <
 
1534
            is_constructible<value_type, _A0>::value,
 
1535
            __node_holder
 
1536
        >::type
 
1537
         __construct_node(_A0&& __a0);
 
1538
    template <class _A0>
 
1539
        typename enable_if
 
1540
        <
 
1541
            is_constructible<key_type, _A0>::value,
 
1542
            __node_holder
 
1543
        >::type
 
1544
         __construct_node(_A0&& __a0);
 
1545
#ifndef _LIBCPP_HAS_NO_VARIADICS
 
1546
    template <class _A0, class _A1, class ..._Args>
 
1547
        __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args);
 
1548
#endif  // _LIBCPP_HAS_NO_VARIADICS
 
1549
#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
1550
};
 
1551
 
 
1552
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
1553
unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
 
1554
        size_type __n, const hasher& __hf, const key_equal& __eql)
 
1555
    : __table_(__hf, __eql)
 
1556
{
 
1557
    __table_.rehash(__n);
 
1558
}
 
1559
 
 
1560
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
1561
unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
 
1562
        size_type __n, const hasher& __hf, const key_equal& __eql,
 
1563
        const allocator_type& __a)
 
1564
    : __table_(__hf, __eql, __a)
 
1565
{
 
1566
    __table_.rehash(__n);
 
1567
}
 
1568
 
 
1569
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
1570
template <class _InputIterator>
 
1571
unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
 
1572
        _InputIterator __first, _InputIterator __last)
 
1573
{
 
1574
    insert(__first, __last);
 
1575
}
 
1576
 
 
1577
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
1578
template <class _InputIterator>
 
1579
unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
 
1580
        _InputIterator __first, _InputIterator __last, size_type __n,
 
1581
        const hasher& __hf, const key_equal& __eql)
 
1582
    : __table_(__hf, __eql)
 
1583
{
 
1584
    __table_.rehash(__n);
 
1585
    insert(__first, __last);
 
1586
}
 
1587
 
 
1588
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
1589
template <class _InputIterator>
 
1590
unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
 
1591
        _InputIterator __first, _InputIterator __last, size_type __n,
 
1592
        const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
 
1593
    : __table_(__hf, __eql, __a)
 
1594
{
 
1595
    __table_.rehash(__n);
 
1596
    insert(__first, __last);
 
1597
}
 
1598
 
 
1599
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
1600
inline _LIBCPP_INLINE_VISIBILITY
 
1601
unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
 
1602
        const allocator_type& __a)
 
1603
    : __table_(__a)
 
1604
{
 
1605
}
 
1606
 
 
1607
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
1608
unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
 
1609
        const unordered_multimap& __u)
 
1610
    : __table_(__u.__table_)
 
1611
{
 
1612
    __table_.rehash(__u.bucket_count());
 
1613
    insert(__u.begin(), __u.end());
 
1614
}
 
1615
 
 
1616
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
1617
unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
 
1618
        const unordered_multimap& __u, const allocator_type& __a)
 
1619
    : __table_(__u.__table_, __a)
 
1620
{
 
1621
    __table_.rehash(__u.bucket_count());
 
1622
    insert(__u.begin(), __u.end());
 
1623
}
 
1624
 
 
1625
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
1626
 
 
1627
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
1628
inline _LIBCPP_INLINE_VISIBILITY
 
1629
unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
 
1630
        unordered_multimap&& __u)
 
1631
    _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
 
1632
    : __table_(_VSTD::move(__u.__table_))
 
1633
{
 
1634
}
 
1635
 
 
1636
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
1637
unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
 
1638
        unordered_multimap&& __u, const allocator_type& __a)
 
1639
    : __table_(_VSTD::move(__u.__table_), __a)
 
1640
{
 
1641
    if (__a != __u.get_allocator())
 
1642
    {
 
1643
        iterator __i = __u.begin();
 
1644
        while (__u.size() != 0)
 
1645
{
 
1646
            __table_.__insert_multi(
 
1647
                _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_)
 
1648
                                   );
 
1649
}
 
1650
    }
 
1651
}
 
1652
 
 
1653
#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
1654
 
 
1655
#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 
1656
 
 
1657
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
1658
unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
 
1659
        initializer_list<value_type> __il)
 
1660
{
 
1661
    insert(__il.begin(), __il.end());
 
1662
}
 
1663
 
 
1664
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
1665
unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
 
1666
        initializer_list<value_type> __il, size_type __n, const hasher& __hf,
 
1667
        const key_equal& __eql)
 
1668
    : __table_(__hf, __eql)
 
1669
{
 
1670
    __table_.rehash(__n);
 
1671
    insert(__il.begin(), __il.end());
 
1672
}
 
1673
 
 
1674
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
1675
unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
 
1676
        initializer_list<value_type> __il, size_type __n, const hasher& __hf,
 
1677
        const key_equal& __eql, const allocator_type& __a)
 
1678
    : __table_(__hf, __eql, __a)
 
1679
{
 
1680
    __table_.rehash(__n);
 
1681
    insert(__il.begin(), __il.end());
 
1682
}
 
1683
 
 
1684
#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 
1685
 
 
1686
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
1687
 
 
1688
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
1689
inline _LIBCPP_INLINE_VISIBILITY
 
1690
unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
 
1691
unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_multimap&& __u)
 
1692
    _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
 
1693
{
 
1694
    __table_ = _VSTD::move(__u.__table_);
 
1695
    return *this;
 
1696
}
 
1697
 
 
1698
#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
1699
 
 
1700
#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 
1701
 
 
1702
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
1703
inline _LIBCPP_INLINE_VISIBILITY
 
1704
unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
 
1705
unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(
 
1706
        initializer_list<value_type> __il)
 
1707
{
 
1708
    __table_.__assign_multi(__il.begin(), __il.end());
 
1709
    return *this;
 
1710
}
 
1711
 
 
1712
#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 
1713
 
 
1714
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
1715
 
 
1716
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
1717
typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
 
1718
unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node()
 
1719
{
 
1720
    __node_allocator& __na = __table_.__node_alloc();
 
1721
    __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
 
1722
    __node_traits::construct(__na, _VSTD::addressof(__h->__value_));
 
1723
    __h.get_deleter().__first_constructed = true;
 
1724
    __h.get_deleter().__second_constructed = true;
 
1725
    return __h;
 
1726
}
 
1727
 
 
1728
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
1729
template <class _A0>
 
1730
typename enable_if
 
1731
<
 
1732
    is_constructible<pair<const _Key, _Tp>, _A0>::value,
 
1733
    typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
 
1734
>::type
 
1735
unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
 
1736
{
 
1737
    __node_allocator& __na = __table_.__node_alloc();
 
1738
    __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
 
1739
    __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
 
1740
                             _VSTD::forward<_A0>(__a0));
 
1741
    __h.get_deleter().__first_constructed = true;
 
1742
    __h.get_deleter().__second_constructed = true;
 
1743
    return __h;
 
1744
}
 
1745
 
 
1746
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
1747
template <class _A0>
 
1748
typename enable_if
 
1749
<
 
1750
    is_constructible<_Key, _A0>::value,
 
1751
    typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
 
1752
>::type
 
1753
unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
 
1754
{
 
1755
    __node_allocator& __na = __table_.__node_alloc();
 
1756
    __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
 
1757
    __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first),
 
1758
                             _VSTD::forward<_A0>(__a0));
 
1759
    __h.get_deleter().__first_constructed = true;
 
1760
    __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second));
 
1761
    __h.get_deleter().__second_constructed = true;
 
1762
    return __h;
 
1763
}
 
1764
 
 
1765
#ifndef _LIBCPP_HAS_NO_VARIADICS
 
1766
 
 
1767
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
1768
template <class _A0, class _A1, class ..._Args>
 
1769
typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
 
1770
unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(
 
1771
        _A0&& __a0, _A1&& __a1, _Args&&... __args)
 
1772
{
 
1773
    __node_allocator& __na = __table_.__node_alloc();
 
1774
    __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
 
1775
    __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
 
1776
                             _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1),
 
1777
                             _VSTD::forward<_Args>(__args)...);
 
1778
    __h.get_deleter().__first_constructed = true;
 
1779
    __h.get_deleter().__second_constructed = true;
 
1780
    return __h;
 
1781
}
 
1782
 
 
1783
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
1784
template <class... _Args>
 
1785
typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator
 
1786
unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_Args&&... __args)
 
1787
{
 
1788
    __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
 
1789
    iterator __r = __table_.__node_insert_multi(__h.get());
 
1790
    __h.release();
 
1791
    return __r;
 
1792
}
 
1793
 
 
1794
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
1795
template <class... _Args>
 
1796
typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator
 
1797
unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace_hint(
 
1798
        const_iterator __p, _Args&&... __args)
 
1799
{
 
1800
    __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
 
1801
    iterator __r = __table_.__node_insert_multi(__p.__i_, __h.get());
 
1802
    __h.release();
 
1803
    return __r;
 
1804
}
 
1805
 
 
1806
#endif  // _LIBCPP_HAS_NO_VARIADICS
 
1807
#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
1808
 
 
1809
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
1810
template <class _InputIterator>
 
1811
inline _LIBCPP_INLINE_VISIBILITY
 
1812
void
 
1813
unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
 
1814
                                                            _InputIterator __last)
 
1815
{
 
1816
    for (; __first != __last; ++__first)
 
1817
        __table_.__insert_multi(*__first);
 
1818
}
 
1819
 
 
1820
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
1821
inline _LIBCPP_INLINE_VISIBILITY
 
1822
void
 
1823
swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 
1824
     unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 
1825
    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
 
1826
{
 
1827
    __x.swap(__y);
 
1828
}
 
1829
 
 
1830
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
1831
bool
 
1832
operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 
1833
           const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 
1834
{
 
1835
    if (__x.size() != __y.size())
 
1836
        return false;
 
1837
    typedef typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
 
1838
                                                                 const_iterator;
 
1839
    typedef pair<const_iterator, const_iterator> _EqRng;
 
1840
    for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;)
 
1841
    {
 
1842
        _EqRng __xeq = __x.equal_range(__i->first);
 
1843
        _EqRng __yeq = __y.equal_range(__i->first);
 
1844
        if (_VSTD::distance(__xeq.first, __xeq.second) !=
 
1845
            _VSTD::distance(__yeq.first, __yeq.second) ||
 
1846
                  !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first))
 
1847
            return false;
 
1848
        __i = __xeq.second;
 
1849
    }
 
1850
    return true;
 
1851
}
 
1852
 
 
1853
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 
1854
inline _LIBCPP_INLINE_VISIBILITY
 
1855
bool
 
1856
operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 
1857
           const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 
1858
{
 
1859
    return !(__x == __y);
 
1860
}
 
1861
 
 
1862
_LIBCPP_END_NAMESPACE_STD
 
1863
 
 
1864
#endif  // _LIBCPP_UNORDERED_MAP