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