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