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#include <tuple>
373
374#include <__debug>
375
376#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
377#pragma GCC system_header
378#endif
379
380_LIBCPP_BEGIN_NAMESPACE_STD
381
382template <class _Key, class _Cp, class _Hash, bool _IsEmpty>
383class __unordered_map_hasher
384    : private _Hash
385{
386public:
387    _LIBCPP_INLINE_VISIBILITY
388    __unordered_map_hasher()
389        _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value)
390        : _Hash() {}
391    _LIBCPP_INLINE_VISIBILITY
392    __unordered_map_hasher(const _Hash& __h)
393        _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value)
394        : _Hash(__h) {}
395    _LIBCPP_INLINE_VISIBILITY
396    const _Hash& hash_function() const _NOEXCEPT {return *this;}
397    _LIBCPP_INLINE_VISIBILITY
398    size_t operator()(const _Cp& __x) const
399        {return static_cast<const _Hash&>(*this)(__x.__get_value().first);}
400    _LIBCPP_INLINE_VISIBILITY
401    size_t operator()(const _Key& __x) const
402        {return static_cast<const _Hash&>(*this)(__x);}
403    void swap(__unordered_map_hasher&__y)
404        _NOEXCEPT_(__is_nothrow_swappable<_Hash>::value)
405    {
406        using _VSTD::swap;
407        swap(static_cast<_Hash&>(*this), static_cast<_Hash&>(__y));
408    }
409};
410
411template <class _Key, class _Cp, class _Hash>
412class __unordered_map_hasher<_Key, _Cp, _Hash, false>
413{
414    _Hash __hash_;
415public:
416    _LIBCPP_INLINE_VISIBILITY
417    __unordered_map_hasher()
418        _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value)
419        : __hash_() {}
420    _LIBCPP_INLINE_VISIBILITY
421    __unordered_map_hasher(const _Hash& __h)
422        _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value)
423        : __hash_(__h) {}
424    _LIBCPP_INLINE_VISIBILITY
425    const _Hash& hash_function() const _NOEXCEPT {return __hash_;}
426    _LIBCPP_INLINE_VISIBILITY
427    size_t operator()(const _Cp& __x) const
428        {return __hash_(__x.__get_value().first);}
429    _LIBCPP_INLINE_VISIBILITY
430    size_t operator()(const _Key& __x) const
431        {return __hash_(__x);}
432    void swap(__unordered_map_hasher&__y)
433        _NOEXCEPT_(__is_nothrow_swappable<_Hash>::value)
434    {
435        using _VSTD::swap;
436        swap(__hash_, __y.__hash_);
437    }
438};
439
440template <class _Key, class _Cp, class _Hash, bool __b>
441inline _LIBCPP_INLINE_VISIBILITY
442void
443swap(__unordered_map_hasher<_Key, _Cp, _Hash, __b>& __x,
444     __unordered_map_hasher<_Key, _Cp, _Hash, __b>& __y)
445    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
446{
447    __x.swap(__y);
448}
449
450template <class _Key, class _Cp, class _Pred, bool _IsEmpty>
451class __unordered_map_equal
452    : private _Pred
453{
454public:
455    _LIBCPP_INLINE_VISIBILITY
456    __unordered_map_equal()
457        _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value)
458        : _Pred() {}
459    _LIBCPP_INLINE_VISIBILITY
460    __unordered_map_equal(const _Pred& __p)
461        _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value)
462        : _Pred(__p) {}
463    _LIBCPP_INLINE_VISIBILITY
464    const _Pred& key_eq() const _NOEXCEPT {return *this;}
465    _LIBCPP_INLINE_VISIBILITY
466    bool operator()(const _Cp& __x, const _Cp& __y) const
467        {return static_cast<const _Pred&>(*this)(__x.__get_value().first, __y.__get_value().first);}
468    _LIBCPP_INLINE_VISIBILITY
469    bool operator()(const _Cp& __x, const _Key& __y) const
470        {return static_cast<const _Pred&>(*this)(__x.__get_value().first, __y);}
471    _LIBCPP_INLINE_VISIBILITY
472    bool operator()(const _Key& __x, const _Cp& __y) const
473        {return static_cast<const _Pred&>(*this)(__x, __y.__get_value().first);}
474    void swap(__unordered_map_equal&__y)
475        _NOEXCEPT_(__is_nothrow_swappable<_Pred>::value)
476    {
477        using _VSTD::swap;
478        swap(static_cast<_Pred&>(*this), static_cast<_Pred&>(__y));
479    }
480};
481
482template <class _Key, class _Cp, class _Pred>
483class __unordered_map_equal<_Key, _Cp, _Pred, false>
484{
485    _Pred __pred_;
486public:
487    _LIBCPP_INLINE_VISIBILITY
488    __unordered_map_equal()
489        _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value)
490        : __pred_() {}
491    _LIBCPP_INLINE_VISIBILITY
492    __unordered_map_equal(const _Pred& __p)
493        _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value)
494        : __pred_(__p) {}
495    _LIBCPP_INLINE_VISIBILITY
496    const _Pred& key_eq() const _NOEXCEPT {return __pred_;}
497    _LIBCPP_INLINE_VISIBILITY
498    bool operator()(const _Cp& __x, const _Cp& __y) const
499        {return __pred_(__x.__get_value().first, __y.__get_value().first);}
500    _LIBCPP_INLINE_VISIBILITY
501    bool operator()(const _Cp& __x, const _Key& __y) const
502        {return __pred_(__x.__get_value().first, __y);}
503    _LIBCPP_INLINE_VISIBILITY
504    bool operator()(const _Key& __x, const _Cp& __y) const
505        {return __pred_(__x, __y.__get_value().first);}
506    void swap(__unordered_map_equal&__y)
507        _NOEXCEPT_(__is_nothrow_swappable<_Pred>::value)
508    {
509        using _VSTD::swap;
510        swap(__pred_, __y.__pred_);
511    }
512};
513
514template <class _Key, class _Cp, class _Pred, bool __b>
515inline _LIBCPP_INLINE_VISIBILITY
516void
517swap(__unordered_map_equal<_Key, _Cp, _Pred, __b>& __x,
518     __unordered_map_equal<_Key, _Cp, _Pred, __b>& __y)
519    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
520{
521    __x.swap(__y);
522}
523
524template <class _Alloc>
525class __hash_map_node_destructor
526{
527    typedef _Alloc                              allocator_type;
528    typedef allocator_traits<allocator_type>    __alloc_traits;
529
530public:
531
532    typedef typename __alloc_traits::pointer       pointer;
533private:
534
535    allocator_type& __na_;
536
537    __hash_map_node_destructor& operator=(const __hash_map_node_destructor&);
538
539public:
540    bool __first_constructed;
541    bool __second_constructed;
542
543    _LIBCPP_INLINE_VISIBILITY
544    explicit __hash_map_node_destructor(allocator_type& __na) _NOEXCEPT
545        : __na_(__na),
546          __first_constructed(false),
547          __second_constructed(false)
548        {}
549
550#ifndef _LIBCPP_CXX03_LANG
551    _LIBCPP_INLINE_VISIBILITY
552    __hash_map_node_destructor(__hash_node_destructor<allocator_type>&& __x)
553        _NOEXCEPT
554        : __na_(__x.__na_),
555          __first_constructed(__x.__value_constructed),
556          __second_constructed(__x.__value_constructed)
557        {
558            __x.__value_constructed = false;
559        }
560#else  // _LIBCPP_CXX03_LANG
561    _LIBCPP_INLINE_VISIBILITY
562    __hash_map_node_destructor(const __hash_node_destructor<allocator_type>& __x)
563        : __na_(__x.__na_),
564          __first_constructed(__x.__value_constructed),
565          __second_constructed(__x.__value_constructed)
566        {
567            const_cast<bool&>(__x.__value_constructed) = false;
568        }
569#endif  // _LIBCPP_CXX03_LANG
570
571    _LIBCPP_INLINE_VISIBILITY
572    void operator()(pointer __p) _NOEXCEPT
573    {
574        if (__second_constructed)
575            __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__get_value().second));
576        if (__first_constructed)
577            __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__get_value().first));
578        if (__p)
579            __alloc_traits::deallocate(__na_, __p, 1);
580    }
581};
582
583#ifndef _LIBCPP_CXX03_LANG
584template <class _Key, class _Tp>
585struct __hash_value_type
586{
587    typedef _Key                                     key_type;
588    typedef _Tp                                      mapped_type;
589    typedef pair<const key_type, mapped_type>        value_type;
590    typedef pair<key_type&, mapped_type&>            __nc_ref_pair_type;
591    typedef pair<key_type&&, mapped_type&&>          __nc_rref_pair_type;
592
593private:
594    value_type __cc;
595
596public:
597    _LIBCPP_INLINE_VISIBILITY
598    value_type& __get_value()
599    {
600#if _LIBCPP_STD_VER > 14
601        return *_VSTD::launder(_VSTD::addressof(__cc));
602#else
603        return __cc;
604#endif
605    }
606
607    _LIBCPP_INLINE_VISIBILITY
608    const value_type& __get_value() const
609    {
610#if _LIBCPP_STD_VER > 14
611        return *_VSTD::launder(_VSTD::addressof(__cc));
612#else
613        return __cc;
614#endif
615    }
616
617    _LIBCPP_INLINE_VISIBILITY
618    __nc_ref_pair_type __ref()
619    {
620        value_type& __v = __get_value();
621        return __nc_ref_pair_type(const_cast<key_type&>(__v.first), __v.second);
622    }
623
624    _LIBCPP_INLINE_VISIBILITY
625    __nc_rref_pair_type __move()
626    {
627        value_type& __v = __get_value();
628        return __nc_rref_pair_type(
629            _VSTD::move(const_cast<key_type&>(__v.first)),
630            _VSTD::move(__v.second));
631    }
632
633    _LIBCPP_INLINE_VISIBILITY
634    __hash_value_type& operator=(const __hash_value_type& __v)
635    {
636        __ref() = __v.__get_value();
637        return *this;
638    }
639
640    _LIBCPP_INLINE_VISIBILITY
641    __hash_value_type& operator=(__hash_value_type&& __v)
642    {
643        __ref() = __v.__move();
644        return *this;
645    }
646
647    template <class _ValueTp,
648              class = typename enable_if<
649                    __is_same_uncvref<_ValueTp, value_type>::value
650                 >::type
651             >
652    _LIBCPP_INLINE_VISIBILITY
653    __hash_value_type& operator=(_ValueTp&& __v)
654    {
655        __ref() = _VSTD::forward<_ValueTp>(__v);
656        return *this;
657    }
658
659private:
660    __hash_value_type(const __hash_value_type& __v) = delete;
661    __hash_value_type(__hash_value_type&& __v) = delete;
662    template <class ..._Args>
663    explicit __hash_value_type(_Args&& ...__args) = delete;
664
665    ~__hash_value_type() = delete;
666};
667
668#else
669
670template <class _Key, class _Tp>
671struct __hash_value_type
672{
673    typedef _Key                                     key_type;
674    typedef _Tp                                      mapped_type;
675    typedef pair<const key_type, mapped_type>        value_type;
676
677private:
678    value_type __cc;
679
680public:
681    _LIBCPP_INLINE_VISIBILITY
682    value_type& __get_value() { return __cc; }
683    _LIBCPP_INLINE_VISIBILITY
684    const value_type& __get_value() const { return __cc; }
685
686private:
687   ~__hash_value_type();
688};
689
690#endif
691
692template <class _HashIterator>
693class _LIBCPP_TEMPLATE_VIS __hash_map_iterator
694{
695    _HashIterator __i_;
696
697    typedef  __hash_node_types_from_iterator<_HashIterator> _NodeTypes;
698
699public:
700    typedef forward_iterator_tag                                 iterator_category;
701    typedef typename _NodeTypes::__map_value_type                value_type;
702    typedef typename _NodeTypes::difference_type                 difference_type;
703    typedef value_type&                                          reference;
704    typedef typename _NodeTypes::__map_value_type_pointer       pointer;
705
706    _LIBCPP_INLINE_VISIBILITY
707    __hash_map_iterator() _NOEXCEPT {}
708
709    _LIBCPP_INLINE_VISIBILITY
710    __hash_map_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
711
712    _LIBCPP_INLINE_VISIBILITY
713    reference operator*() const {return __i_->__get_value();}
714    _LIBCPP_INLINE_VISIBILITY
715    pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__get_value());}
716
717    _LIBCPP_INLINE_VISIBILITY
718    __hash_map_iterator& operator++() {++__i_; return *this;}
719    _LIBCPP_INLINE_VISIBILITY
720    __hash_map_iterator operator++(int)
721    {
722        __hash_map_iterator __t(*this);
723        ++(*this);
724        return __t;
725    }
726
727    friend _LIBCPP_INLINE_VISIBILITY
728        bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y)
729        {return __x.__i_ == __y.__i_;}
730    friend _LIBCPP_INLINE_VISIBILITY
731        bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y)
732        {return __x.__i_ != __y.__i_;}
733
734    template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_map;
735    template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
736    template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator;
737    template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator;
738    template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator;
739};
740
741template <class _HashIterator>
742class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator
743{
744    _HashIterator __i_;
745
746    typedef  __hash_node_types_from_iterator<_HashIterator> _NodeTypes;
747
748public:
749    typedef forward_iterator_tag                                 iterator_category;
750    typedef typename _NodeTypes::__map_value_type                value_type;
751    typedef typename _NodeTypes::difference_type                 difference_type;
752    typedef const value_type&                                    reference;
753    typedef typename _NodeTypes::__const_map_value_type_pointer  pointer;
754
755    _LIBCPP_INLINE_VISIBILITY
756    __hash_map_const_iterator() _NOEXCEPT {}
757
758    _LIBCPP_INLINE_VISIBILITY
759    __hash_map_const_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
760    _LIBCPP_INLINE_VISIBILITY
761    __hash_map_const_iterator(
762            __hash_map_iterator<typename _HashIterator::__non_const_iterator> __i)
763                 _NOEXCEPT
764                : __i_(__i.__i_) {}
765
766    _LIBCPP_INLINE_VISIBILITY
767    reference operator*() const {return __i_->__get_value();}
768    _LIBCPP_INLINE_VISIBILITY
769    pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__get_value());}
770
771    _LIBCPP_INLINE_VISIBILITY
772    __hash_map_const_iterator& operator++() {++__i_; return *this;}
773    _LIBCPP_INLINE_VISIBILITY
774    __hash_map_const_iterator operator++(int)
775    {
776        __hash_map_const_iterator __t(*this);
777        ++(*this);
778        return __t;
779    }
780
781    friend _LIBCPP_INLINE_VISIBILITY
782        bool operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)
783        {return __x.__i_ == __y.__i_;}
784    friend _LIBCPP_INLINE_VISIBILITY
785        bool operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)
786        {return __x.__i_ != __y.__i_;}
787
788    template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_map;
789    template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
790    template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator;
791    template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator;
792};
793
794template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
795          class _Alloc = allocator<pair<const _Key, _Tp> > >
796class _LIBCPP_TEMPLATE_VIS unordered_map
797{
798public:
799    // types
800    typedef _Key                                           key_type;
801    typedef _Tp                                            mapped_type;
802    typedef _Hash                                          hasher;
803    typedef _Pred                                          key_equal;
804    typedef _Alloc                                         allocator_type;
805    typedef pair<const key_type, mapped_type>              value_type;
806    typedef value_type&                                    reference;
807    typedef const value_type&                              const_reference;
808    static_assert((is_same<value_type, typename allocator_type::value_type>::value),
809                  "Invalid allocator::value_type");
810
811private:
812    typedef __hash_value_type<key_type, mapped_type>                 __value_type;
813    typedef __unordered_map_hasher<key_type, __value_type, hasher>   __hasher;
814    typedef __unordered_map_equal<key_type, __value_type, key_equal> __key_equal;
815    typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>,
816                                                 __value_type>::type __allocator_type;
817
818    typedef __hash_table<__value_type, __hasher,
819                         __key_equal,  __allocator_type>   __table;
820
821    __table __table_;
822
823    typedef typename __table::_NodeTypes                   _NodeTypes;
824    typedef typename __table::__node_pointer               __node_pointer;
825    typedef typename __table::__node_const_pointer         __node_const_pointer;
826    typedef typename __table::__node_traits                __node_traits;
827    typedef typename __table::__node_allocator             __node_allocator;
828    typedef typename __table::__node                       __node;
829    typedef __hash_map_node_destructor<__node_allocator>   _Dp;
830    typedef unique_ptr<__node, _Dp>                         __node_holder;
831    typedef allocator_traits<allocator_type>               __alloc_traits;
832
833    static_assert((is_same<typename __table::__container_value_type, value_type>::value), "");
834    static_assert((is_same<typename __table::__node_value_type, __value_type>::value), "");
835public:
836    typedef typename __alloc_traits::pointer         pointer;
837    typedef typename __alloc_traits::const_pointer   const_pointer;
838    typedef typename __table::size_type              size_type;
839    typedef typename __table::difference_type        difference_type;
840
841    typedef __hash_map_iterator<typename __table::iterator>       iterator;
842    typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
843    typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
844    typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
845
846    _LIBCPP_INLINE_VISIBILITY
847    unordered_map()
848        _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
849        {
850#if _LIBCPP_DEBUG_LEVEL >= 2
851            __get_db()->__insert_c(this);
852#endif
853        }
854    explicit unordered_map(size_type __n, const hasher& __hf = hasher(),
855                           const key_equal& __eql = key_equal());
856    unordered_map(size_type __n, const hasher& __hf,
857                  const key_equal& __eql,
858                  const allocator_type& __a);
859    template <class _InputIterator>
860        unordered_map(_InputIterator __first, _InputIterator __last);
861    template <class _InputIterator>
862        unordered_map(_InputIterator __first, _InputIterator __last,
863                      size_type __n, const hasher& __hf = hasher(),
864                      const key_equal& __eql = key_equal());
865    template <class _InputIterator>
866        unordered_map(_InputIterator __first, _InputIterator __last,
867                      size_type __n, const hasher& __hf,
868                      const key_equal& __eql,
869                      const allocator_type& __a);
870    _LIBCPP_INLINE_VISIBILITY
871    explicit unordered_map(const allocator_type& __a);
872    unordered_map(const unordered_map& __u);
873    unordered_map(const unordered_map& __u, const allocator_type& __a);
874#ifndef _LIBCPP_CXX03_LANG
875    _LIBCPP_INLINE_VISIBILITY
876    unordered_map(unordered_map&& __u)
877        _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
878    unordered_map(unordered_map&& __u, const allocator_type& __a);
879    unordered_map(initializer_list<value_type> __il);
880    unordered_map(initializer_list<value_type> __il, size_type __n,
881                  const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
882    unordered_map(initializer_list<value_type> __il, size_type __n,
883                  const hasher& __hf, const key_equal& __eql,
884                  const allocator_type& __a);
885#endif  // _LIBCPP_CXX03_LANG
886#if _LIBCPP_STD_VER > 11
887    _LIBCPP_INLINE_VISIBILITY
888    unordered_map(size_type __n, const allocator_type& __a)
889      : unordered_map(__n, hasher(), key_equal(), __a) {}
890    _LIBCPP_INLINE_VISIBILITY
891    unordered_map(size_type __n, const hasher& __hf, const allocator_type& __a)
892      : unordered_map(__n, __hf, key_equal(), __a) {}
893    template <class _InputIterator>
894    _LIBCPP_INLINE_VISIBILITY
895      unordered_map(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a)
896      : unordered_map(__first, __last, __n, hasher(), key_equal(), __a) {}
897    template <class _InputIterator>
898    _LIBCPP_INLINE_VISIBILITY
899      unordered_map(_InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf,
900        const allocator_type& __a)
901      : unordered_map(__first, __last, __n, __hf, key_equal(), __a) {}
902    _LIBCPP_INLINE_VISIBILITY
903    unordered_map(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)
904      : unordered_map(__il, __n, hasher(), key_equal(), __a) {}
905    _LIBCPP_INLINE_VISIBILITY
906    unordered_map(initializer_list<value_type> __il, size_type __n, const hasher& __hf,
907      const allocator_type& __a)
908      : unordered_map(__il, __n, __hf, key_equal(), __a) {}
909#endif
910    // ~unordered_map() = default;
911    _LIBCPP_INLINE_VISIBILITY
912    unordered_map& operator=(const unordered_map& __u)
913    {
914#ifndef _LIBCPP_CXX03_LANG
915        __table_ = __u.__table_;
916#else
917        if (this != &__u) {
918            __table_.clear();
919            __table_.hash_function() = __u.__table_.hash_function();
920            __table_.key_eq() = __u.__table_.key_eq();
921            __table_.max_load_factor() = __u.__table_.max_load_factor();
922            __table_.__copy_assign_alloc(__u.__table_);
923            insert(__u.begin(), __u.end());
924        }
925#endif
926        return *this;
927    }
928#ifndef _LIBCPP_CXX03_LANG
929    _LIBCPP_INLINE_VISIBILITY
930    unordered_map& operator=(unordered_map&& __u)
931        _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
932    _LIBCPP_INLINE_VISIBILITY
933    unordered_map& operator=(initializer_list<value_type> __il);
934#endif  // _LIBCPP_CXX03_LANG
935
936    _LIBCPP_INLINE_VISIBILITY
937    allocator_type get_allocator() const _NOEXCEPT
938        {return allocator_type(__table_.__node_alloc());}
939
940    _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
941    bool      empty() const _NOEXCEPT {return __table_.size() == 0;}
942    _LIBCPP_INLINE_VISIBILITY
943    size_type size() const _NOEXCEPT  {return __table_.size();}
944    _LIBCPP_INLINE_VISIBILITY
945    size_type max_size() const _NOEXCEPT {return __table_.max_size();}
946
947    _LIBCPP_INLINE_VISIBILITY
948    iterator       begin() _NOEXCEPT        {return __table_.begin();}
949    _LIBCPP_INLINE_VISIBILITY
950    iterator       end() _NOEXCEPT          {return __table_.end();}
951    _LIBCPP_INLINE_VISIBILITY
952    const_iterator begin()  const _NOEXCEPT {return __table_.begin();}
953    _LIBCPP_INLINE_VISIBILITY
954    const_iterator end()    const _NOEXCEPT {return __table_.end();}
955    _LIBCPP_INLINE_VISIBILITY
956    const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
957    _LIBCPP_INLINE_VISIBILITY
958    const_iterator cend()   const _NOEXCEPT {return __table_.end();}
959
960    _LIBCPP_INLINE_VISIBILITY
961    pair<iterator, bool> insert(const value_type& __x)
962        {return __table_.__insert_unique(__x);}
963
964    iterator insert(const_iterator __p, const value_type& __x) {
965#if _LIBCPP_DEBUG_LEVEL >= 2
966        _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
967            "unordered_map::insert(const_iterator, const value_type&) called with an iterator not"
968            " referring to this unordered_map");
969#else
970        ((void)__p);
971#endif
972        return insert(__x).first;
973    }
974
975    template <class _InputIterator>
976        _LIBCPP_INLINE_VISIBILITY
977        void insert(_InputIterator __first, _InputIterator __last);
978
979#ifndef _LIBCPP_CXX03_LANG
980    _LIBCPP_INLINE_VISIBILITY
981    void insert(initializer_list<value_type> __il)
982        {insert(__il.begin(), __il.end());}
983
984    _LIBCPP_INLINE_VISIBILITY
985    pair<iterator, bool> insert(value_type&& __x)
986        {return __table_.__insert_unique(_VSTD::move(__x));}
987
988    iterator insert(const_iterator __p, value_type&& __x) {
989#if _LIBCPP_DEBUG_LEVEL >= 2
990        _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
991            "unordered_map::insert(const_iterator, const value_type&) called with an iterator not"
992            " referring to this unordered_map");
993#else
994        ((void)__p);
995#endif
996        return __table_.__insert_unique(_VSTD::move(__x)).first;
997    }
998
999    template <class _Pp,
1000              class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1001        _LIBCPP_INLINE_VISIBILITY
1002        pair<iterator, bool> insert(_Pp&& __x)
1003            {return __table_.__insert_unique(_VSTD::forward<_Pp>(__x));}
1004
1005    template <class _Pp,
1006              class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1007        _LIBCPP_INLINE_VISIBILITY
1008        iterator insert(const_iterator __p, _Pp&& __x)
1009        {
1010#if _LIBCPP_DEBUG_LEVEL >= 2
1011            _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1012                "unordered_map::insert(const_iterator, value_type&&) called with an iterator not"
1013                " referring to this unordered_map");
1014#else
1015          ((void)__p);
1016#endif
1017            return insert(_VSTD::forward<_Pp>(__x)).first;
1018        }
1019
1020    template <class... _Args>
1021    _LIBCPP_INLINE_VISIBILITY
1022    pair<iterator, bool> emplace(_Args&&... __args) {
1023        return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...);
1024    }
1025
1026    template <class... _Args>
1027    _LIBCPP_INLINE_VISIBILITY
1028    iterator emplace_hint(const_iterator __p, _Args&&... __args) {
1029#if _LIBCPP_DEBUG_LEVEL >= 2
1030        _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1031            "unordered_map::emplace_hint(const_iterator, args...) called with an iterator not"
1032            " referring to this unordered_map");
1033#else
1034          ((void)__p);
1035#endif
1036        return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first;
1037    }
1038
1039#endif  // _LIBCPP_CXX03_LANG
1040
1041#if _LIBCPP_STD_VER > 14
1042    template <class... _Args>
1043        _LIBCPP_INLINE_VISIBILITY
1044        pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args)
1045    {
1046        return __table_.__emplace_unique_key_args(__k, _VSTD::piecewise_construct,
1047            _VSTD::forward_as_tuple(__k),
1048            _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
1049    }
1050
1051    template <class... _Args>
1052        _LIBCPP_INLINE_VISIBILITY
1053        pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args)
1054    {
1055        return __table_.__emplace_unique_key_args(__k, _VSTD::piecewise_construct,
1056            _VSTD::forward_as_tuple(_VSTD::move(__k)),
1057            _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
1058    }
1059
1060    template <class... _Args>
1061        _LIBCPP_INLINE_VISIBILITY
1062        iterator try_emplace(const_iterator __h, const key_type& __k, _Args&&... __args)
1063    {
1064#if _LIBCPP_DEBUG_LEVEL >= 2
1065        _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__h) == this,
1066            "unordered_map::try_emplace(const_iterator, key, args...) called with an iterator not"
1067            " referring to this unordered_map");
1068#else
1069        ((void)__h);
1070#endif
1071        return try_emplace(__k, _VSTD::forward<_Args>(__args)...).first;
1072    }
1073
1074    template <class... _Args>
1075        _LIBCPP_INLINE_VISIBILITY
1076        iterator try_emplace(const_iterator __h, key_type&& __k, _Args&&... __args)
1077    {
1078#if _LIBCPP_DEBUG_LEVEL >= 2
1079        _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__h) == this,
1080            "unordered_map::try_emplace(const_iterator, key, args...) called with an iterator not"
1081            " referring to this unordered_map");
1082#else
1083        ((void)__h);
1084#endif
1085        return try_emplace(_VSTD::move(__k), _VSTD::forward<_Args>(__args)...).first;
1086    }
1087
1088    template <class _Vp>
1089        _LIBCPP_INLINE_VISIBILITY
1090        pair<iterator, bool> insert_or_assign(const key_type& __k, _Vp&& __v)
1091    {
1092        pair<iterator, bool> __res = __table_.__emplace_unique_key_args(__k,
1093            __k, _VSTD::forward<_Vp>(__v));
1094        if (!__res.second) {
1095            __res.first->second = _VSTD::forward<_Vp>(__v);
1096        }
1097        return __res;
1098    }
1099
1100    template <class _Vp>
1101        _LIBCPP_INLINE_VISIBILITY
1102        pair<iterator, bool> insert_or_assign(key_type&& __k, _Vp&& __v)
1103    {
1104        pair<iterator, bool> __res = __table_.__emplace_unique_key_args(__k,
1105            _VSTD::move(__k), _VSTD::forward<_Vp>(__v));
1106        if (!__res.second) {
1107            __res.first->second = _VSTD::forward<_Vp>(__v);
1108        }
1109        return __res;
1110    }
1111
1112    template <class _Vp>
1113        _LIBCPP_INLINE_VISIBILITY
1114        iterator insert_or_assign(const_iterator, const key_type& __k, _Vp&& __v)
1115     {
1116          // FIXME: Add debug mode checking for the iterator input
1117          return insert_or_assign(__k, _VSTD::forward<_Vp>(__v)).first;
1118     }
1119
1120    template <class _Vp>
1121        _LIBCPP_INLINE_VISIBILITY
1122        iterator insert_or_assign(const_iterator, key_type&& __k, _Vp&& __v)
1123     {
1124        // FIXME: Add debug mode checking for the iterator input
1125        return insert_or_assign(_VSTD::move(__k), _VSTD::forward<_Vp>(__v)).first;
1126     }
1127#endif // _LIBCPP_STD_VER > 14
1128
1129    _LIBCPP_INLINE_VISIBILITY
1130    iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);}
1131    _LIBCPP_INLINE_VISIBILITY
1132    iterator erase(iterator __p)       {return __table_.erase(__p.__i_);}
1133    _LIBCPP_INLINE_VISIBILITY
1134    size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
1135    _LIBCPP_INLINE_VISIBILITY
1136    iterator erase(const_iterator __first, const_iterator __last)
1137        {return __table_.erase(__first.__i_, __last.__i_);}
1138    _LIBCPP_INLINE_VISIBILITY
1139    void clear() _NOEXCEPT {__table_.clear();}
1140
1141    _LIBCPP_INLINE_VISIBILITY
1142    void swap(unordered_map& __u)
1143        _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
1144        { __table_.swap(__u.__table_);}
1145
1146    _LIBCPP_INLINE_VISIBILITY
1147    hasher hash_function() const
1148        {return __table_.hash_function().hash_function();}
1149    _LIBCPP_INLINE_VISIBILITY
1150    key_equal key_eq() const
1151        {return __table_.key_eq().key_eq();}
1152
1153    _LIBCPP_INLINE_VISIBILITY
1154    iterator       find(const key_type& __k)       {return __table_.find(__k);}
1155    _LIBCPP_INLINE_VISIBILITY
1156    const_iterator find(const key_type& __k) const {return __table_.find(__k);}
1157    _LIBCPP_INLINE_VISIBILITY
1158    size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
1159    _LIBCPP_INLINE_VISIBILITY
1160    pair<iterator, iterator>             equal_range(const key_type& __k)
1161        {return __table_.__equal_range_unique(__k);}
1162    _LIBCPP_INLINE_VISIBILITY
1163    pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
1164        {return __table_.__equal_range_unique(__k);}
1165
1166    mapped_type& operator[](const key_type& __k);
1167#ifndef _LIBCPP_CXX03_LANG
1168    mapped_type& operator[](key_type&& __k);
1169#endif
1170
1171    mapped_type&       at(const key_type& __k);
1172    const mapped_type& at(const key_type& __k) const;
1173
1174    _LIBCPP_INLINE_VISIBILITY
1175    size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
1176    _LIBCPP_INLINE_VISIBILITY
1177    size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
1178
1179    _LIBCPP_INLINE_VISIBILITY
1180    size_type bucket_size(size_type __n) const
1181        {return __table_.bucket_size(__n);}
1182    _LIBCPP_INLINE_VISIBILITY
1183    size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
1184
1185    _LIBCPP_INLINE_VISIBILITY
1186    local_iterator       begin(size_type __n)        {return __table_.begin(__n);}
1187    _LIBCPP_INLINE_VISIBILITY
1188    local_iterator       end(size_type __n)          {return __table_.end(__n);}
1189    _LIBCPP_INLINE_VISIBILITY
1190    const_local_iterator begin(size_type __n) const  {return __table_.cbegin(__n);}
1191    _LIBCPP_INLINE_VISIBILITY
1192    const_local_iterator end(size_type __n) const    {return __table_.cend(__n);}
1193    _LIBCPP_INLINE_VISIBILITY
1194    const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
1195    _LIBCPP_INLINE_VISIBILITY
1196    const_local_iterator cend(size_type __n) const   {return __table_.cend(__n);}
1197
1198    _LIBCPP_INLINE_VISIBILITY
1199    float load_factor() const _NOEXCEPT {return __table_.load_factor();}
1200    _LIBCPP_INLINE_VISIBILITY
1201    float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
1202    _LIBCPP_INLINE_VISIBILITY
1203    void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
1204    _LIBCPP_INLINE_VISIBILITY
1205    void rehash(size_type __n) {__table_.rehash(__n);}
1206    _LIBCPP_INLINE_VISIBILITY
1207    void reserve(size_type __n) {__table_.reserve(__n);}
1208
1209#if _LIBCPP_DEBUG_LEVEL >= 2
1210
1211    bool __dereferenceable(const const_iterator* __i) const
1212        {return __table_.__dereferenceable(&__i->__i_);}
1213    bool __decrementable(const const_iterator* __i) const
1214        {return __table_.__decrementable(&__i->__i_);}
1215    bool __addable(const const_iterator* __i, ptrdiff_t __n) const
1216        {return __table_.__addable(&__i->__i_, __n);}
1217    bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
1218        {return __table_.__addable(&__i->__i_, __n);}
1219
1220#endif  // _LIBCPP_DEBUG_LEVEL >= 2
1221
1222private:
1223
1224#ifdef _LIBCPP_CXX03_LANG
1225    __node_holder __construct_node_with_key(const key_type& __k);
1226#endif
1227};
1228
1229template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1230unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1231        size_type __n, const hasher& __hf, const key_equal& __eql)
1232    : __table_(__hf, __eql)
1233{
1234#if _LIBCPP_DEBUG_LEVEL >= 2
1235    __get_db()->__insert_c(this);
1236#endif
1237    __table_.rehash(__n);
1238}
1239
1240template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1241unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1242        size_type __n, const hasher& __hf, const key_equal& __eql,
1243        const allocator_type& __a)
1244    : __table_(__hf, __eql, typename __table::allocator_type(__a))
1245{
1246#if _LIBCPP_DEBUG_LEVEL >= 2
1247    __get_db()->__insert_c(this);
1248#endif
1249    __table_.rehash(__n);
1250}
1251
1252template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1253inline
1254unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1255        const allocator_type& __a)
1256    : __table_(typename __table::allocator_type(__a))
1257{
1258#if _LIBCPP_DEBUG_LEVEL >= 2
1259    __get_db()->__insert_c(this);
1260#endif
1261}
1262
1263template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1264template <class _InputIterator>
1265unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1266        _InputIterator __first, _InputIterator __last)
1267{
1268#if _LIBCPP_DEBUG_LEVEL >= 2
1269    __get_db()->__insert_c(this);
1270#endif
1271    insert(__first, __last);
1272}
1273
1274template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1275template <class _InputIterator>
1276unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1277        _InputIterator __first, _InputIterator __last, size_type __n,
1278        const hasher& __hf, const key_equal& __eql)
1279    : __table_(__hf, __eql)
1280{
1281#if _LIBCPP_DEBUG_LEVEL >= 2
1282    __get_db()->__insert_c(this);
1283#endif
1284    __table_.rehash(__n);
1285    insert(__first, __last);
1286}
1287
1288template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1289template <class _InputIterator>
1290unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1291        _InputIterator __first, _InputIterator __last, size_type __n,
1292        const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1293    : __table_(__hf, __eql, typename __table::allocator_type(__a))
1294{
1295#if _LIBCPP_DEBUG_LEVEL >= 2
1296    __get_db()->__insert_c(this);
1297#endif
1298    __table_.rehash(__n);
1299    insert(__first, __last);
1300}
1301
1302template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1303unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1304        const unordered_map& __u)
1305    : __table_(__u.__table_)
1306{
1307#if _LIBCPP_DEBUG_LEVEL >= 2
1308    __get_db()->__insert_c(this);
1309#endif
1310    __table_.rehash(__u.bucket_count());
1311    insert(__u.begin(), __u.end());
1312}
1313
1314template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1315unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1316        const unordered_map& __u, const allocator_type& __a)
1317    : __table_(__u.__table_, typename __table::allocator_type(__a))
1318{
1319#if _LIBCPP_DEBUG_LEVEL >= 2
1320    __get_db()->__insert_c(this);
1321#endif
1322    __table_.rehash(__u.bucket_count());
1323    insert(__u.begin(), __u.end());
1324}
1325
1326#ifndef _LIBCPP_CXX03_LANG
1327
1328template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1329inline
1330unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1331        unordered_map&& __u)
1332    _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
1333    : __table_(_VSTD::move(__u.__table_))
1334{
1335#if _LIBCPP_DEBUG_LEVEL >= 2
1336    __get_db()->__insert_c(this);
1337    __get_db()->swap(this, &__u);
1338#endif
1339}
1340
1341template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1342unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1343        unordered_map&& __u, const allocator_type& __a)
1344    : __table_(_VSTD::move(__u.__table_), typename __table::allocator_type(__a))
1345{
1346#if _LIBCPP_DEBUG_LEVEL >= 2
1347    __get_db()->__insert_c(this);
1348#endif
1349    if (__a != __u.get_allocator())
1350    {
1351        iterator __i = __u.begin();
1352        while (__u.size() != 0) {
1353            __table_.__emplace_unique(
1354                __u.__table_.remove((__i++).__i_)->__value_.__move());
1355        }
1356    }
1357#if _LIBCPP_DEBUG_LEVEL >= 2
1358    else
1359        __get_db()->swap(this, &__u);
1360#endif
1361}
1362
1363template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1364unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1365        initializer_list<value_type> __il)
1366{
1367#if _LIBCPP_DEBUG_LEVEL >= 2
1368    __get_db()->__insert_c(this);
1369#endif
1370    insert(__il.begin(), __il.end());
1371}
1372
1373template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1374unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1375        initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1376        const key_equal& __eql)
1377    : __table_(__hf, __eql)
1378{
1379#if _LIBCPP_DEBUG_LEVEL >= 2
1380    __get_db()->__insert_c(this);
1381#endif
1382    __table_.rehash(__n);
1383    insert(__il.begin(), __il.end());
1384}
1385
1386template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1387unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1388        initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1389        const key_equal& __eql, const allocator_type& __a)
1390    : __table_(__hf, __eql, typename __table::allocator_type(__a))
1391{
1392#if _LIBCPP_DEBUG_LEVEL >= 2
1393    __get_db()->__insert_c(this);
1394#endif
1395    __table_.rehash(__n);
1396    insert(__il.begin(), __il.end());
1397}
1398
1399template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1400inline
1401unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
1402unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_map&& __u)
1403    _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
1404{
1405    __table_ = _VSTD::move(__u.__table_);
1406    return *this;
1407}
1408
1409template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1410inline
1411unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
1412unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(
1413        initializer_list<value_type> __il)
1414{
1415    __table_.__assign_unique(__il.begin(), __il.end());
1416    return *this;
1417}
1418
1419#endif  // _LIBCPP_CXX03_LANG
1420
1421template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1422template <class _InputIterator>
1423inline
1424void
1425unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
1426                                                       _InputIterator __last)
1427{
1428    for (; __first != __last; ++__first)
1429        __table_.__insert_unique(*__first);
1430}
1431
1432#ifndef _LIBCPP_CXX03_LANG
1433
1434template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1435_Tp&
1436unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k)
1437{
1438    return __table_.__emplace_unique_key_args(__k,
1439        std::piecewise_construct, std::forward_as_tuple(__k),
1440                                  std::forward_as_tuple()).first->__get_value().second;
1441}
1442
1443template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1444_Tp&
1445unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&& __k)
1446{
1447    return __table_.__emplace_unique_key_args(__k,
1448        std::piecewise_construct, std::forward_as_tuple(std::move(__k)),
1449                                  std::forward_as_tuple()).first->__get_value().second;
1450}
1451#else // _LIBCPP_CXX03_LANG
1452
1453template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1454typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1455unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(const key_type& __k)
1456{
1457    __node_allocator& __na = __table_.__node_alloc();
1458    __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1459    __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__get_value().first), __k);
1460    __h.get_deleter().__first_constructed = true;
1461    __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__get_value().second));
1462    __h.get_deleter().__second_constructed = true;
1463    return _LIBCPP_EXPLICIT_MOVE(__h);  // explicitly moved for C++03
1464}
1465
1466template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1467_Tp&
1468unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k)
1469{
1470    iterator __i = find(__k);
1471    if (__i != end())
1472        return __i->second;
1473    __node_holder __h = __construct_node_with_key(__k);
1474    pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1475    __h.release();
1476    return __r.first->second;
1477}
1478
1479#endif  // _LIBCPP_CXX03_MODE
1480
1481template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1482_Tp&
1483unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k)
1484{
1485    iterator __i = find(__k);
1486#ifndef _LIBCPP_NO_EXCEPTIONS
1487    if (__i == end())
1488        throw out_of_range("unordered_map::at: key not found");
1489#endif  // _LIBCPP_NO_EXCEPTIONS
1490    return __i->second;
1491}
1492
1493template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1494const _Tp&
1495unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) const
1496{
1497    const_iterator __i = find(__k);
1498#ifndef _LIBCPP_NO_EXCEPTIONS
1499    if (__i == end())
1500        throw out_of_range("unordered_map::at: key not found");
1501#endif  // _LIBCPP_NO_EXCEPTIONS
1502    return __i->second;
1503}
1504
1505template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1506inline _LIBCPP_INLINE_VISIBILITY
1507void
1508swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1509     unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1510    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1511{
1512    __x.swap(__y);
1513}
1514
1515template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1516bool
1517operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1518           const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1519{
1520    if (__x.size() != __y.size())
1521        return false;
1522    typedef typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
1523                                                                 const_iterator;
1524    for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();
1525            __i != __ex; ++__i)
1526    {
1527        const_iterator __j = __y.find(__i->first);
1528        if (__j == __ey || !(*__i == *__j))
1529            return false;
1530    }
1531    return true;
1532}
1533
1534template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1535inline _LIBCPP_INLINE_VISIBILITY
1536bool
1537operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1538           const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1539{
1540    return !(__x == __y);
1541}
1542
1543template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
1544          class _Alloc = allocator<pair<const _Key, _Tp> > >
1545class _LIBCPP_TEMPLATE_VIS unordered_multimap
1546{
1547public:
1548    // types
1549    typedef _Key                                           key_type;
1550    typedef _Tp                                            mapped_type;
1551    typedef _Hash                                          hasher;
1552    typedef _Pred                                          key_equal;
1553    typedef _Alloc                                         allocator_type;
1554    typedef pair<const key_type, mapped_type>              value_type;
1555    typedef value_type&                                    reference;
1556    typedef const value_type&                              const_reference;
1557    static_assert((is_same<value_type, typename allocator_type::value_type>::value),
1558                  "Invalid allocator::value_type");
1559
1560private:
1561    typedef __hash_value_type<key_type, mapped_type>                 __value_type;
1562    typedef __unordered_map_hasher<key_type, __value_type, hasher>   __hasher;
1563    typedef __unordered_map_equal<key_type, __value_type, key_equal> __key_equal;
1564    typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>,
1565                                                 __value_type>::type __allocator_type;
1566
1567    typedef __hash_table<__value_type, __hasher,
1568                         __key_equal,  __allocator_type>   __table;
1569
1570    __table __table_;
1571
1572    typedef typename __table::_NodeTypes                   _NodeTypes;
1573    typedef typename __table::__node_traits                __node_traits;
1574    typedef typename __table::__node_allocator             __node_allocator;
1575    typedef typename __table::__node                       __node;
1576    typedef __hash_map_node_destructor<__node_allocator>   _Dp;
1577    typedef unique_ptr<__node, _Dp>                         __node_holder;
1578    typedef allocator_traits<allocator_type>               __alloc_traits;
1579    static_assert((is_same<typename __node_traits::size_type,
1580                          typename __alloc_traits::size_type>::value),
1581                 "Allocator uses different size_type for different types");
1582public:
1583    typedef typename __alloc_traits::pointer         pointer;
1584    typedef typename __alloc_traits::const_pointer   const_pointer;
1585    typedef typename __table::size_type              size_type;
1586    typedef typename __table::difference_type        difference_type;
1587
1588    typedef __hash_map_iterator<typename __table::iterator>       iterator;
1589    typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
1590    typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
1591    typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
1592
1593    _LIBCPP_INLINE_VISIBILITY
1594    unordered_multimap()
1595        _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
1596        {
1597#if _LIBCPP_DEBUG_LEVEL >= 2
1598            __get_db()->__insert_c(this);
1599#endif
1600        }
1601    explicit unordered_multimap(size_type __n, const hasher& __hf = hasher(),
1602                                const key_equal& __eql = key_equal());
1603    unordered_multimap(size_type __n, const hasher& __hf,
1604                                const key_equal& __eql,
1605                                const allocator_type& __a);
1606    template <class _InputIterator>
1607        unordered_multimap(_InputIterator __first, _InputIterator __last);
1608    template <class _InputIterator>
1609        unordered_multimap(_InputIterator __first, _InputIterator __last,
1610                      size_type __n, const hasher& __hf = hasher(),
1611                      const key_equal& __eql = key_equal());
1612    template <class _InputIterator>
1613        unordered_multimap(_InputIterator __first, _InputIterator __last,
1614                      size_type __n, const hasher& __hf,
1615                      const key_equal& __eql,
1616                      const allocator_type& __a);
1617    _LIBCPP_INLINE_VISIBILITY
1618    explicit unordered_multimap(const allocator_type& __a);
1619    unordered_multimap(const unordered_multimap& __u);
1620    unordered_multimap(const unordered_multimap& __u, const allocator_type& __a);
1621#ifndef _LIBCPP_CXX03_LANG
1622    _LIBCPP_INLINE_VISIBILITY
1623    unordered_multimap(unordered_multimap&& __u)
1624        _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
1625    unordered_multimap(unordered_multimap&& __u, const allocator_type& __a);
1626    unordered_multimap(initializer_list<value_type> __il);
1627    unordered_multimap(initializer_list<value_type> __il, size_type __n,
1628                       const hasher& __hf = hasher(),
1629                       const key_equal& __eql = key_equal());
1630    unordered_multimap(initializer_list<value_type> __il, size_type __n,
1631                       const hasher& __hf, const key_equal& __eql,
1632                       const allocator_type& __a);
1633#endif  // _LIBCPP_CXX03_LANG
1634#if _LIBCPP_STD_VER > 11
1635    _LIBCPP_INLINE_VISIBILITY
1636    unordered_multimap(size_type __n, const allocator_type& __a)
1637      : unordered_multimap(__n, hasher(), key_equal(), __a) {}
1638    _LIBCPP_INLINE_VISIBILITY
1639    unordered_multimap(size_type __n, const hasher& __hf, const allocator_type& __a)
1640      : unordered_multimap(__n, __hf, key_equal(), __a) {}
1641    template <class _InputIterator>
1642    _LIBCPP_INLINE_VISIBILITY
1643      unordered_multimap(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a)
1644      : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a) {}
1645    template <class _InputIterator>
1646    _LIBCPP_INLINE_VISIBILITY
1647      unordered_multimap(_InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf,
1648        const allocator_type& __a)
1649      : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a) {}
1650    _LIBCPP_INLINE_VISIBILITY
1651    unordered_multimap(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)
1652      : unordered_multimap(__il, __n, hasher(), key_equal(), __a) {}
1653    _LIBCPP_INLINE_VISIBILITY
1654    unordered_multimap(initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1655      const allocator_type& __a)
1656      : unordered_multimap(__il, __n, __hf, key_equal(), __a) {}
1657#endif
1658    // ~unordered_multimap() = default;
1659    _LIBCPP_INLINE_VISIBILITY
1660    unordered_multimap& operator=(const unordered_multimap& __u)
1661    {
1662#ifndef _LIBCPP_CXX03_LANG
1663        __table_ = __u.__table_;
1664#else
1665        if (this != &__u) {
1666            __table_.clear();
1667            __table_.hash_function() = __u.__table_.hash_function();
1668            __table_.key_eq() = __u.__table_.key_eq();
1669            __table_.max_load_factor() = __u.__table_.max_load_factor();
1670            __table_.__copy_assign_alloc(__u.__table_);
1671            insert(__u.begin(), __u.end());
1672        }
1673#endif
1674        return *this;
1675    }
1676#ifndef _LIBCPP_CXX03_LANG
1677    _LIBCPP_INLINE_VISIBILITY
1678    unordered_multimap& operator=(unordered_multimap&& __u)
1679        _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
1680    _LIBCPP_INLINE_VISIBILITY
1681    unordered_multimap& operator=(initializer_list<value_type> __il);
1682#endif  // _LIBCPP_CXX03_LANG
1683
1684    _LIBCPP_INLINE_VISIBILITY
1685    allocator_type get_allocator() const _NOEXCEPT
1686        {return allocator_type(__table_.__node_alloc());}
1687
1688    _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
1689    bool      empty() const _NOEXCEPT {return __table_.size() == 0;}
1690    _LIBCPP_INLINE_VISIBILITY
1691    size_type size() const _NOEXCEPT  {return __table_.size();}
1692    _LIBCPP_INLINE_VISIBILITY
1693    size_type max_size() const _NOEXCEPT {return __table_.max_size();}
1694
1695    _LIBCPP_INLINE_VISIBILITY
1696    iterator       begin() _NOEXCEPT        {return __table_.begin();}
1697    _LIBCPP_INLINE_VISIBILITY
1698    iterator       end() _NOEXCEPT          {return __table_.end();}
1699    _LIBCPP_INLINE_VISIBILITY
1700    const_iterator begin()  const _NOEXCEPT {return __table_.begin();}
1701    _LIBCPP_INLINE_VISIBILITY
1702    const_iterator end()    const _NOEXCEPT {return __table_.end();}
1703    _LIBCPP_INLINE_VISIBILITY
1704    const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
1705    _LIBCPP_INLINE_VISIBILITY
1706    const_iterator cend()   const _NOEXCEPT {return __table_.end();}
1707
1708    _LIBCPP_INLINE_VISIBILITY
1709    iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
1710
1711    _LIBCPP_INLINE_VISIBILITY
1712    iterator insert(const_iterator __p, const value_type& __x)
1713        {return __table_.__insert_multi(__p.__i_, __x);}
1714
1715    template <class _InputIterator>
1716    _LIBCPP_INLINE_VISIBILITY
1717    void insert(_InputIterator __first, _InputIterator __last);
1718
1719#ifndef _LIBCPP_CXX03_LANG
1720    _LIBCPP_INLINE_VISIBILITY
1721    void insert(initializer_list<value_type> __il)
1722        {insert(__il.begin(), __il.end());}
1723    _LIBCPP_INLINE_VISIBILITY
1724    iterator insert(value_type&& __x) {return __table_.__insert_multi(_VSTD::move(__x));}
1725
1726    _LIBCPP_INLINE_VISIBILITY
1727    iterator insert(const_iterator __p, value_type&& __x)
1728        {return __table_.__insert_multi(__p.__i_, _VSTD::move(__x));}
1729
1730    template <class _Pp,
1731              class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1732    _LIBCPP_INLINE_VISIBILITY
1733    iterator insert(_Pp&& __x)
1734        {return __table_.__insert_multi(_VSTD::forward<_Pp>(__x));}
1735
1736    template <class _Pp,
1737              class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1738    _LIBCPP_INLINE_VISIBILITY
1739    iterator insert(const_iterator __p, _Pp&& __x)
1740        {return __table_.__insert_multi(__p.__i_, _VSTD::forward<_Pp>(__x));}
1741
1742    template <class... _Args>
1743    iterator emplace(_Args&&... __args) {
1744        return __table_.__emplace_multi(_VSTD::forward<_Args>(__args)...);
1745    }
1746
1747    template <class... _Args>
1748    iterator emplace_hint(const_iterator __p, _Args&&... __args) {
1749        return __table_.__emplace_hint_multi(__p.__i_, _VSTD::forward<_Args>(__args)...);
1750    }
1751#endif  // _LIBCPP_CXX03_LANG
1752
1753
1754    _LIBCPP_INLINE_VISIBILITY
1755    iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);}
1756    _LIBCPP_INLINE_VISIBILITY
1757    iterator erase(iterator __p)       {return __table_.erase(__p.__i_);}
1758    _LIBCPP_INLINE_VISIBILITY
1759    size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
1760    _LIBCPP_INLINE_VISIBILITY
1761    iterator erase(const_iterator __first, const_iterator __last)
1762        {return __table_.erase(__first.__i_, __last.__i_);}
1763    _LIBCPP_INLINE_VISIBILITY
1764    void clear() _NOEXCEPT {__table_.clear();}
1765
1766    _LIBCPP_INLINE_VISIBILITY
1767    void swap(unordered_multimap& __u)
1768        _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
1769        {__table_.swap(__u.__table_);}
1770
1771    _LIBCPP_INLINE_VISIBILITY
1772    hasher hash_function() const
1773        {return __table_.hash_function().hash_function();}
1774    _LIBCPP_INLINE_VISIBILITY
1775    key_equal key_eq() const
1776        {return __table_.key_eq().key_eq();}
1777
1778    _LIBCPP_INLINE_VISIBILITY
1779    iterator       find(const key_type& __k)       {return __table_.find(__k);}
1780    _LIBCPP_INLINE_VISIBILITY
1781    const_iterator find(const key_type& __k) const {return __table_.find(__k);}
1782    _LIBCPP_INLINE_VISIBILITY
1783    size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
1784    _LIBCPP_INLINE_VISIBILITY
1785    pair<iterator, iterator>             equal_range(const key_type& __k)
1786        {return __table_.__equal_range_multi(__k);}
1787    _LIBCPP_INLINE_VISIBILITY
1788    pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
1789        {return __table_.__equal_range_multi(__k);}
1790
1791    _LIBCPP_INLINE_VISIBILITY
1792    size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
1793    _LIBCPP_INLINE_VISIBILITY
1794    size_type max_bucket_count() const _NOEXCEPT
1795        {return __table_.max_bucket_count();}
1796
1797    _LIBCPP_INLINE_VISIBILITY
1798    size_type bucket_size(size_type __n) const
1799        {return __table_.bucket_size(__n);}
1800    _LIBCPP_INLINE_VISIBILITY
1801    size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
1802
1803    _LIBCPP_INLINE_VISIBILITY
1804    local_iterator       begin(size_type __n)        {return __table_.begin(__n);}
1805    _LIBCPP_INLINE_VISIBILITY
1806    local_iterator       end(size_type __n)          {return __table_.end(__n);}
1807    _LIBCPP_INLINE_VISIBILITY
1808    const_local_iterator begin(size_type __n) const  {return __table_.cbegin(__n);}
1809    _LIBCPP_INLINE_VISIBILITY
1810    const_local_iterator end(size_type __n) const    {return __table_.cend(__n);}
1811    _LIBCPP_INLINE_VISIBILITY
1812    const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
1813    _LIBCPP_INLINE_VISIBILITY
1814    const_local_iterator cend(size_type __n) const   {return __table_.cend(__n);}
1815
1816    _LIBCPP_INLINE_VISIBILITY
1817    float load_factor() const _NOEXCEPT {return __table_.load_factor();}
1818    _LIBCPP_INLINE_VISIBILITY
1819    float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
1820    _LIBCPP_INLINE_VISIBILITY
1821    void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
1822    _LIBCPP_INLINE_VISIBILITY
1823    void rehash(size_type __n) {__table_.rehash(__n);}
1824    _LIBCPP_INLINE_VISIBILITY
1825    void reserve(size_type __n) {__table_.reserve(__n);}
1826
1827#if _LIBCPP_DEBUG_LEVEL >= 2
1828
1829    bool __dereferenceable(const const_iterator* __i) const
1830        {return __table_.__dereferenceable(&__i->__i_);}
1831    bool __decrementable(const const_iterator* __i) const
1832        {return __table_.__decrementable(&__i->__i_);}
1833    bool __addable(const const_iterator* __i, ptrdiff_t __n) const
1834        {return __table_.__addable(&__i->__i_, __n);}
1835    bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
1836        {return __table_.__addable(&__i->__i_, __n);}
1837
1838#endif  // _LIBCPP_DEBUG_LEVEL >= 2
1839
1840
1841};
1842
1843template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1844unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1845        size_type __n, const hasher& __hf, const key_equal& __eql)
1846    : __table_(__hf, __eql)
1847{
1848#if _LIBCPP_DEBUG_LEVEL >= 2
1849    __get_db()->__insert_c(this);
1850#endif
1851    __table_.rehash(__n);
1852}
1853
1854template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1855unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1856        size_type __n, const hasher& __hf, const key_equal& __eql,
1857        const allocator_type& __a)
1858    : __table_(__hf, __eql, typename __table::allocator_type(__a))
1859{
1860#if _LIBCPP_DEBUG_LEVEL >= 2
1861    __get_db()->__insert_c(this);
1862#endif
1863    __table_.rehash(__n);
1864}
1865
1866template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1867template <class _InputIterator>
1868unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1869        _InputIterator __first, _InputIterator __last)
1870{
1871#if _LIBCPP_DEBUG_LEVEL >= 2
1872    __get_db()->__insert_c(this);
1873#endif
1874    insert(__first, __last);
1875}
1876
1877template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1878template <class _InputIterator>
1879unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1880        _InputIterator __first, _InputIterator __last, size_type __n,
1881        const hasher& __hf, const key_equal& __eql)
1882    : __table_(__hf, __eql)
1883{
1884#if _LIBCPP_DEBUG_LEVEL >= 2
1885    __get_db()->__insert_c(this);
1886#endif
1887    __table_.rehash(__n);
1888    insert(__first, __last);
1889}
1890
1891template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1892template <class _InputIterator>
1893unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1894        _InputIterator __first, _InputIterator __last, size_type __n,
1895        const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1896    : __table_(__hf, __eql, typename __table::allocator_type(__a))
1897{
1898#if _LIBCPP_DEBUG_LEVEL >= 2
1899    __get_db()->__insert_c(this);
1900#endif
1901    __table_.rehash(__n);
1902    insert(__first, __last);
1903}
1904
1905template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1906inline
1907unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1908        const allocator_type& __a)
1909    : __table_(typename __table::allocator_type(__a))
1910{
1911#if _LIBCPP_DEBUG_LEVEL >= 2
1912    __get_db()->__insert_c(this);
1913#endif
1914}
1915
1916template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1917unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1918        const unordered_multimap& __u)
1919    : __table_(__u.__table_)
1920{
1921#if _LIBCPP_DEBUG_LEVEL >= 2
1922    __get_db()->__insert_c(this);
1923#endif
1924    __table_.rehash(__u.bucket_count());
1925    insert(__u.begin(), __u.end());
1926}
1927
1928template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1929unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1930        const unordered_multimap& __u, const allocator_type& __a)
1931    : __table_(__u.__table_, typename __table::allocator_type(__a))
1932{
1933#if _LIBCPP_DEBUG_LEVEL >= 2
1934    __get_db()->__insert_c(this);
1935#endif
1936    __table_.rehash(__u.bucket_count());
1937    insert(__u.begin(), __u.end());
1938}
1939
1940#ifndef _LIBCPP_CXX03_LANG
1941
1942template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1943inline
1944unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1945        unordered_multimap&& __u)
1946    _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
1947    : __table_(_VSTD::move(__u.__table_))
1948{
1949#if _LIBCPP_DEBUG_LEVEL >= 2
1950    __get_db()->__insert_c(this);
1951    __get_db()->swap(this, &__u);
1952#endif
1953}
1954
1955template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1956unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1957        unordered_multimap&& __u, const allocator_type& __a)
1958    : __table_(_VSTD::move(__u.__table_), typename __table::allocator_type(__a))
1959{
1960#if _LIBCPP_DEBUG_LEVEL >= 2
1961    __get_db()->__insert_c(this);
1962#endif
1963    if (__a != __u.get_allocator())
1964    {
1965        iterator __i = __u.begin();
1966        while (__u.size() != 0)
1967        {
1968            __table_.__insert_multi(
1969                __u.__table_.remove((__i++).__i_)->__value_.__move());
1970        }
1971    }
1972#if _LIBCPP_DEBUG_LEVEL >= 2
1973    else
1974        __get_db()->swap(this, &__u);
1975#endif
1976}
1977
1978template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1979unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1980        initializer_list<value_type> __il)
1981{
1982#if _LIBCPP_DEBUG_LEVEL >= 2
1983    __get_db()->__insert_c(this);
1984#endif
1985    insert(__il.begin(), __il.end());
1986}
1987
1988template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1989unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1990        initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1991        const key_equal& __eql)
1992    : __table_(__hf, __eql)
1993{
1994#if _LIBCPP_DEBUG_LEVEL >= 2
1995    __get_db()->__insert_c(this);
1996#endif
1997    __table_.rehash(__n);
1998    insert(__il.begin(), __il.end());
1999}
2000
2001template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2002unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2003        initializer_list<value_type> __il, size_type __n, const hasher& __hf,
2004        const key_equal& __eql, const allocator_type& __a)
2005    : __table_(__hf, __eql, typename __table::allocator_type(__a))
2006{
2007#if _LIBCPP_DEBUG_LEVEL >= 2
2008    __get_db()->__insert_c(this);
2009#endif
2010    __table_.rehash(__n);
2011    insert(__il.begin(), __il.end());
2012}
2013
2014template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2015inline
2016unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
2017unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_multimap&& __u)
2018    _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
2019{
2020    __table_ = _VSTD::move(__u.__table_);
2021    return *this;
2022}
2023
2024template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2025inline
2026unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
2027unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(
2028        initializer_list<value_type> __il)
2029{
2030    __table_.__assign_multi(__il.begin(), __il.end());
2031    return *this;
2032}
2033
2034#endif  // _LIBCPP_CXX03_LANG
2035
2036
2037
2038template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2039template <class _InputIterator>
2040inline
2041void
2042unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
2043                                                            _InputIterator __last)
2044{
2045    for (; __first != __last; ++__first)
2046        __table_.__insert_multi(*__first);
2047}
2048
2049template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2050inline _LIBCPP_INLINE_VISIBILITY
2051void
2052swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2053     unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2054    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
2055{
2056    __x.swap(__y);
2057}
2058
2059template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2060bool
2061operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2062           const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2063{
2064    if (__x.size() != __y.size())
2065        return false;
2066    typedef typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
2067                                                                 const_iterator;
2068    typedef pair<const_iterator, const_iterator> _EqRng;
2069    for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;)
2070    {
2071        _EqRng __xeq = __x.equal_range(__i->first);
2072        _EqRng __yeq = __y.equal_range(__i->first);
2073        if (_VSTD::distance(__xeq.first, __xeq.second) !=
2074            _VSTD::distance(__yeq.first, __yeq.second) ||
2075                  !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first))
2076            return false;
2077        __i = __xeq.second;
2078    }
2079    return true;
2080}
2081
2082template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2083inline _LIBCPP_INLINE_VISIBILITY
2084bool
2085operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2086           const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2087{
2088    return !(__x == __y);
2089}
2090
2091_LIBCPP_END_NAMESPACE_STD
2092
2093#endif  // _LIBCPP_UNORDERED_MAP
2094