unordered_map revision 241900 
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#ifndef _LIBCPP_HAS_NO_VARIADICS
790
791    template <class... _Args>
792        pair<iterator, bool> emplace(_Args&&... __args);
793
794    template <class... _Args>
795        _LIBCPP_INLINE_VISIBILITY
796        iterator emplace_hint(const_iterator, _Args&&... __args)
797            {return emplace(_VSTD::forward<_Args>(__args)...).first;}
798#endif  // _LIBCPP_HAS_NO_VARIADICS
799#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
800    _LIBCPP_INLINE_VISIBILITY
801    pair<iterator, bool> insert(const value_type& __x)
802        {return __table_.__insert_unique(__x);}
803#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
804    template <class _Pp,
805              class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
806        _LIBCPP_INLINE_VISIBILITY
807        pair<iterator, bool> insert(_Pp&& __x)
808            {return __table_.__insert_unique(_VSTD::forward<_Pp>(__x));}
809#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
810    _LIBCPP_INLINE_VISIBILITY
811    iterator insert(const_iterator, const value_type& __x)
812        {return insert(__x).first;}
813#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
814    template <class _Pp,
815              class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
816        _LIBCPP_INLINE_VISIBILITY
817        iterator insert(const_iterator, _Pp&& __x)
818            {return insert(_VSTD::forward<_Pp>(__x)).first;}
819#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
820    template <class _InputIterator>
821        void insert(_InputIterator __first, _InputIterator __last);
822#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
823    _LIBCPP_INLINE_VISIBILITY
824    void insert(initializer_list<value_type> __il)
825        {insert(__il.begin(), __il.end());}
826#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
827
828    _LIBCPP_INLINE_VISIBILITY
829    iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);}
830    _LIBCPP_INLINE_VISIBILITY
831    size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
832    _LIBCPP_INLINE_VISIBILITY
833    iterator erase(const_iterator __first, const_iterator __last)
834        {return __table_.erase(__first.__i_, __last.__i_);}
835    _LIBCPP_INLINE_VISIBILITY
836    void clear() _NOEXCEPT {__table_.clear();}
837
838    _LIBCPP_INLINE_VISIBILITY
839    void swap(unordered_map& __u)
840        _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
841        {__table_.swap(__u.__table_);}
842
843    _LIBCPP_INLINE_VISIBILITY
844    hasher hash_function() const
845        {return __table_.hash_function().hash_function();}
846    _LIBCPP_INLINE_VISIBILITY
847    key_equal key_eq() const
848        {return __table_.key_eq().key_eq();}
849
850    _LIBCPP_INLINE_VISIBILITY
851    iterator       find(const key_type& __k)       {return __table_.find(__k);}
852    _LIBCPP_INLINE_VISIBILITY
853    const_iterator find(const key_type& __k) const {return __table_.find(__k);}
854    _LIBCPP_INLINE_VISIBILITY
855    size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
856    _LIBCPP_INLINE_VISIBILITY
857    pair<iterator, iterator>             equal_range(const key_type& __k)
858        {return __table_.__equal_range_unique(__k);}
859    _LIBCPP_INLINE_VISIBILITY
860    pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
861        {return __table_.__equal_range_unique(__k);}
862
863    mapped_type& operator[](const key_type& __k);
864#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
865    mapped_type& operator[](key_type&& __k);
866#endif
867
868    mapped_type&       at(const key_type& __k);
869    const mapped_type& at(const key_type& __k) const;
870
871    _LIBCPP_INLINE_VISIBILITY
872    size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
873    _LIBCPP_INLINE_VISIBILITY
874    size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
875
876    _LIBCPP_INLINE_VISIBILITY
877    size_type bucket_size(size_type __n) const
878        {return __table_.bucket_size(__n);}
879    _LIBCPP_INLINE_VISIBILITY
880    size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
881
882    _LIBCPP_INLINE_VISIBILITY
883    local_iterator       begin(size_type __n)        {return __table_.begin(__n);}
884    _LIBCPP_INLINE_VISIBILITY
885    local_iterator       end(size_type __n)          {return __table_.end(__n);}
886    _LIBCPP_INLINE_VISIBILITY
887    const_local_iterator begin(size_type __n) const  {return __table_.cbegin(__n);}
888    _LIBCPP_INLINE_VISIBILITY
889    const_local_iterator end(size_type __n) const    {return __table_.cend(__n);}
890    _LIBCPP_INLINE_VISIBILITY
891    const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
892    _LIBCPP_INLINE_VISIBILITY
893    const_local_iterator cend(size_type __n) const   {return __table_.cend(__n);}
894
895    _LIBCPP_INLINE_VISIBILITY
896    float load_factor() const _NOEXCEPT {return __table_.load_factor();}
897    _LIBCPP_INLINE_VISIBILITY
898    float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
899    _LIBCPP_INLINE_VISIBILITY
900    void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
901    _LIBCPP_INLINE_VISIBILITY
902    void rehash(size_type __n) {__table_.rehash(__n);}
903    _LIBCPP_INLINE_VISIBILITY
904    void reserve(size_type __n) {__table_.reserve(__n);}
905
906private:
907#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
908    __node_holder __construct_node();
909    template <class _A0>
910        typename enable_if
911        <
912            is_constructible<value_type, _A0>::value,
913            __node_holder
914        >::type
915         __construct_node(_A0&& __a0);
916    template <class _A0>
917        typename enable_if
918        <
919            is_constructible<key_type, _A0>::value,
920            __node_holder
921        >::type
922         __construct_node(_A0&& __a0);
923#ifndef _LIBCPP_HAS_NO_VARIADICS
924    template <class _A0, class _A1, class ..._Args>
925        __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args);
926#endif  // _LIBCPP_HAS_NO_VARIADICS
927#else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
928    __node_holder __construct_node(const key_type& __k);
929#endif
930};
931
932template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
933unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
934        size_type __n, const hasher& __hf, const key_equal& __eql)
935    : __table_(__hf, __eql)
936{
937    __table_.rehash(__n);
938}
939
940template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
941unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
942        size_type __n, const hasher& __hf, const key_equal& __eql,
943        const allocator_type& __a)
944    : __table_(__hf, __eql, __a)
945{
946    __table_.rehash(__n);
947}
948
949template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
950inline _LIBCPP_INLINE_VISIBILITY
951unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
952        const allocator_type& __a)
953    : __table_(__a)
954{
955}
956
957template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
958template <class _InputIterator>
959unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
960        _InputIterator __first, _InputIterator __last)
961{
962    insert(__first, __last);
963}
964
965template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
966template <class _InputIterator>
967unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
968        _InputIterator __first, _InputIterator __last, size_type __n,
969        const hasher& __hf, const key_equal& __eql)
970    : __table_(__hf, __eql)
971{
972    __table_.rehash(__n);
973    insert(__first, __last);
974}
975
976template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
977template <class _InputIterator>
978unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
979        _InputIterator __first, _InputIterator __last, size_type __n,
980        const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
981    : __table_(__hf, __eql, __a)
982{
983    __table_.rehash(__n);
984    insert(__first, __last);
985}
986
987template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
988unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
989        const unordered_map& __u)
990    : __table_(__u.__table_)
991{
992    __table_.rehash(__u.bucket_count());
993    insert(__u.begin(), __u.end());
994}
995
996template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
997unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
998        const unordered_map& __u, const allocator_type& __a)
999    : __table_(__u.__table_, __a)
1000{
1001    __table_.rehash(__u.bucket_count());
1002    insert(__u.begin(), __u.end());
1003}
1004
1005#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1006
1007template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1008inline _LIBCPP_INLINE_VISIBILITY
1009unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1010        unordered_map&& __u)
1011    _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
1012    : __table_(_VSTD::move(__u.__table_))
1013{
1014}
1015
1016template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1017unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1018        unordered_map&& __u, const allocator_type& __a)
1019    : __table_(_VSTD::move(__u.__table_), __a)
1020{
1021    if (__a != __u.get_allocator())
1022    {
1023        iterator __i = __u.begin();
1024        while (__u.size() != 0)
1025            __table_.__insert_unique(
1026                _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_)
1027                                    );
1028    }
1029}
1030
1031#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1032
1033#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1034
1035template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1036unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1037        initializer_list<value_type> __il)
1038{
1039    insert(__il.begin(), __il.end());
1040}
1041
1042template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1043unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1044        initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1045        const key_equal& __eql)
1046    : __table_(__hf, __eql)
1047{
1048    __table_.rehash(__n);
1049    insert(__il.begin(), __il.end());
1050}
1051
1052template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1053unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1054        initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1055        const key_equal& __eql, const allocator_type& __a)
1056    : __table_(__hf, __eql, __a)
1057{
1058    __table_.rehash(__n);
1059    insert(__il.begin(), __il.end());
1060}
1061
1062#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1063
1064#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1065
1066template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1067inline _LIBCPP_INLINE_VISIBILITY
1068unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
1069unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_map&& __u)
1070    _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
1071{
1072    __table_ = _VSTD::move(__u.__table_);
1073    return *this;
1074}
1075
1076#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1077
1078#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1079
1080template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1081inline _LIBCPP_INLINE_VISIBILITY
1082unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
1083unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(
1084        initializer_list<value_type> __il)
1085{
1086    __table_.__assign_unique(__il.begin(), __il.end());
1087    return *this;
1088}
1089
1090#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1091
1092#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1093
1094template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1095typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1096unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node()
1097{
1098    __node_allocator& __na = __table_.__node_alloc();
1099    __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1100    __node_traits::construct(__na, _VSTD::addressof(__h->__value_));
1101    __h.get_deleter().__first_constructed = true;
1102    __h.get_deleter().__second_constructed = true;
1103    return __h;
1104}
1105
1106template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1107template <class _A0>
1108typename enable_if
1109<
1110    is_constructible<pair<const _Key, _Tp>, _A0>::value,
1111    typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1112>::type
1113unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
1114{
1115    __node_allocator& __na = __table_.__node_alloc();
1116    __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1117    __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1118                             _VSTD::forward<_A0>(__a0));
1119    __h.get_deleter().__first_constructed = true;
1120    __h.get_deleter().__second_constructed = true;
1121    return __h;
1122}
1123
1124template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1125template <class _A0>
1126typename enable_if
1127<
1128    is_constructible<_Key, _A0>::value,
1129    typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1130>::type
1131unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
1132{
1133    __node_allocator& __na = __table_.__node_alloc();
1134    __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1135    __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first),
1136                             _VSTD::forward<_A0>(__a0));
1137    __h.get_deleter().__first_constructed = true;
1138    __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second));
1139    __h.get_deleter().__second_constructed = true;
1140    return __h;
1141}
1142
1143#ifndef _LIBCPP_HAS_NO_VARIADICS
1144
1145template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1146template <class _A0, class _A1, class ..._Args>
1147typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1148unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0,
1149                                                                 _A1&& __a1,
1150                                                                 _Args&&... __args)
1151{
1152    __node_allocator& __na = __table_.__node_alloc();
1153    __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1154    __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1155                             _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1),
1156                             _VSTD::forward<_Args>(__args)...);
1157    __h.get_deleter().__first_constructed = true;
1158    __h.get_deleter().__second_constructed = true;
1159    return __h;
1160}
1161
1162template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1163template <class... _Args>
1164pair<typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator, bool>
1165unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_Args&&... __args)
1166{
1167    __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1168    pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1169    if (__r.second)
1170        __h.release();
1171    return __r;
1172}
1173
1174#endif  // _LIBCPP_HAS_NO_VARIADICS
1175#else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1176
1177template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1178typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1179unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(const key_type& __k)
1180{
1181    __node_allocator& __na = __table_.__node_alloc();
1182    __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1183    __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first), __k);
1184    __h.get_deleter().__first_constructed = true;
1185    __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second));
1186    __h.get_deleter().__second_constructed = true;
1187    return _VSTD::move(__h);
1188}
1189
1190#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1191
1192template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1193template <class _InputIterator>
1194inline _LIBCPP_INLINE_VISIBILITY
1195void
1196unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
1197                                                       _InputIterator __last)
1198{
1199    for (; __first != __last; ++__first)
1200        __table_.__insert_unique(*__first);
1201}
1202
1203template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1204_Tp&
1205unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k)
1206{
1207    iterator __i = find(__k);
1208    if (__i != end())
1209        return __i->second;
1210    __node_holder __h = __construct_node(__k);
1211    pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1212    __h.release();
1213    return __r.first->second;
1214}
1215
1216#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1217
1218template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1219_Tp&
1220unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&& __k)
1221{
1222    iterator __i = find(__k);
1223    if (__i != end())
1224        return __i->second;
1225    __node_holder __h = __construct_node(_VSTD::move(__k));
1226    pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1227    __h.release();
1228    return __r.first->second;
1229}
1230
1231#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1232
1233template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1234_Tp&
1235unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k)
1236{
1237    iterator __i = find(__k);
1238#ifndef _LIBCPP_NO_EXCEPTIONS
1239    if (__i == end())
1240        throw out_of_range("unordered_map::at: key not found");
1241#endif  // _LIBCPP_NO_EXCEPTIONS
1242    return __i->second;
1243}
1244
1245template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1246const _Tp&
1247unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) const
1248{
1249    const_iterator __i = find(__k);
1250#ifndef _LIBCPP_NO_EXCEPTIONS
1251    if (__i == end())
1252        throw out_of_range("unordered_map::at: key not found");
1253#endif  // _LIBCPP_NO_EXCEPTIONS
1254    return __i->second;
1255}
1256
1257template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1258inline _LIBCPP_INLINE_VISIBILITY
1259void
1260swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1261     unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1262    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1263{
1264    __x.swap(__y);
1265}
1266
1267template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1268bool
1269operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1270           const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1271{
1272    if (__x.size() != __y.size())
1273        return false;
1274    typedef typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
1275                                                                 const_iterator;
1276    for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();
1277            __i != __ex; ++__i)
1278    {
1279        const_iterator __j = __y.find(__i->first);
1280        if (__j == __ey || !(*__i == *__j))
1281            return false;
1282    }
1283    return true;
1284}
1285
1286template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1287inline _LIBCPP_INLINE_VISIBILITY
1288bool
1289operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1290           const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1291{
1292    return !(__x == __y);
1293}
1294
1295template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
1296          class _Alloc = allocator<pair<const _Key, _Tp> > >
1297class _LIBCPP_VISIBLE unordered_multimap
1298{
1299public:
1300    // types
1301    typedef _Key                                           key_type;
1302    typedef _Tp                                            mapped_type;
1303    typedef _Hash                                          hasher;
1304    typedef _Pred                                          key_equal;
1305    typedef _Alloc                                         allocator_type;
1306    typedef pair<const key_type, mapped_type>              value_type;
1307    typedef value_type&                                    reference;
1308    typedef const value_type&                              const_reference;
1309
1310private:
1311    typedef pair<key_type, mapped_type>                    __value_type;
1312    typedef __unordered_map_hasher<key_type, mapped_type, hasher>   __hasher;
1313    typedef __unordered_map_equal<key_type, mapped_type, key_equal> __key_equal;
1314    typedef typename allocator_traits<allocator_type>::template
1315#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
1316            rebind_alloc<__value_type>
1317#else
1318            rebind_alloc<__value_type>::other
1319#endif
1320                                                           __allocator_type;
1321
1322    typedef __hash_table<__value_type, __hasher,
1323                         __key_equal,  __allocator_type>   __table;
1324
1325    __table __table_;
1326
1327    typedef typename __table::__node_traits                __node_traits;
1328    typedef typename __table::__node_allocator             __node_allocator;
1329    typedef typename __table::__node                       __node;
1330    typedef __hash_map_node_destructor<__node_allocator>   _Dp;
1331    typedef unique_ptr<__node, _Dp>                         __node_holder;
1332    typedef allocator_traits<allocator_type>               __alloc_traits;
1333public:
1334    typedef typename __alloc_traits::pointer         pointer;
1335    typedef typename __alloc_traits::const_pointer   const_pointer;
1336    typedef typename __alloc_traits::size_type       size_type;
1337    typedef typename __alloc_traits::difference_type difference_type;
1338
1339    typedef __hash_map_iterator<typename __table::iterator>       iterator;
1340    typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
1341    typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
1342    typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
1343
1344    _LIBCPP_INLINE_VISIBILITY
1345    unordered_multimap()
1346        _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
1347        {} // = default;
1348    explicit unordered_multimap(size_type __n, const hasher& __hf = hasher(),
1349                                const key_equal& __eql = key_equal());
1350    unordered_multimap(size_type __n, const hasher& __hf,
1351                                const key_equal& __eql,
1352                                const allocator_type& __a);
1353    template <class _InputIterator>
1354        unordered_multimap(_InputIterator __first, _InputIterator __last);
1355    template <class _InputIterator>
1356        unordered_multimap(_InputIterator __first, _InputIterator __last,
1357                      size_type __n, const hasher& __hf = hasher(),
1358                      const key_equal& __eql = key_equal());
1359    template <class _InputIterator>
1360        unordered_multimap(_InputIterator __first, _InputIterator __last,
1361                      size_type __n, const hasher& __hf,
1362                      const key_equal& __eql,
1363                      const allocator_type& __a);
1364    explicit unordered_multimap(const allocator_type& __a);
1365    unordered_multimap(const unordered_multimap& __u);
1366    unordered_multimap(const unordered_multimap& __u, const allocator_type& __a);
1367#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1368    unordered_multimap(unordered_multimap&& __u)
1369        _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
1370    unordered_multimap(unordered_multimap&& __u, const allocator_type& __a);
1371#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1372#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1373    unordered_multimap(initializer_list<value_type> __il);
1374    unordered_multimap(initializer_list<value_type> __il, size_type __n,
1375                       const hasher& __hf = hasher(),
1376                       const key_equal& __eql = key_equal());
1377    unordered_multimap(initializer_list<value_type> __il, size_type __n,
1378                       const hasher& __hf, const key_equal& __eql,
1379                       const allocator_type& __a);
1380#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1381    // ~unordered_multimap() = default;
1382    _LIBCPP_INLINE_VISIBILITY
1383    unordered_multimap& operator=(const unordered_multimap& __u)
1384    {
1385        __table_ = __u.__table_;
1386        return *this;
1387    }
1388#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1389    unordered_multimap& operator=(unordered_multimap&& __u)
1390        _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
1391#endif
1392#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1393    unordered_multimap& operator=(initializer_list<value_type> __il);
1394#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1395
1396    _LIBCPP_INLINE_VISIBILITY
1397    allocator_type get_allocator() const _NOEXCEPT
1398        {return allocator_type(__table_.__node_alloc());}
1399
1400    _LIBCPP_INLINE_VISIBILITY
1401    bool      empty() const _NOEXCEPT {return __table_.size() == 0;}
1402    _LIBCPP_INLINE_VISIBILITY
1403    size_type size() const _NOEXCEPT  {return __table_.size();}
1404    _LIBCPP_INLINE_VISIBILITY
1405    size_type max_size() const _NOEXCEPT {return __table_.max_size();}
1406
1407    _LIBCPP_INLINE_VISIBILITY
1408    iterator       begin() _NOEXCEPT        {return __table_.begin();}
1409    _LIBCPP_INLINE_VISIBILITY
1410    iterator       end() _NOEXCEPT          {return __table_.end();}
1411    _LIBCPP_INLINE_VISIBILITY
1412    const_iterator begin()  const _NOEXCEPT {return __table_.begin();}
1413    _LIBCPP_INLINE_VISIBILITY
1414    const_iterator end()    const _NOEXCEPT {return __table_.end();}
1415    _LIBCPP_INLINE_VISIBILITY
1416    const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
1417    _LIBCPP_INLINE_VISIBILITY
1418    const_iterator cend()   const _NOEXCEPT {return __table_.end();}
1419
1420#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1421#ifndef _LIBCPP_HAS_NO_VARIADICS
1422
1423    template <class... _Args>
1424        iterator emplace(_Args&&... __args);
1425
1426    template <class... _Args>
1427        iterator emplace_hint(const_iterator __p, _Args&&... __args);
1428#endif  // _LIBCPP_HAS_NO_VARIADICS
1429#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1430    _LIBCPP_INLINE_VISIBILITY
1431    iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
1432#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1433    template <class _Pp,
1434              class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1435        _LIBCPP_INLINE_VISIBILITY
1436        iterator insert(_Pp&& __x)
1437            {return __table_.__insert_multi(_VSTD::forward<_Pp>(__x));}
1438#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1439    _LIBCPP_INLINE_VISIBILITY
1440    iterator insert(const_iterator __p, const value_type& __x)
1441        {return __table_.__insert_multi(__p.__i_, __x);}
1442#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1443    template <class _Pp,
1444              class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1445        _LIBCPP_INLINE_VISIBILITY
1446        iterator insert(const_iterator __p, _Pp&& __x)
1447            {return __table_.__insert_multi(__p.__i_, _VSTD::forward<_Pp>(__x));}
1448#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1449    template <class _InputIterator>
1450        void insert(_InputIterator __first, _InputIterator __last);
1451#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1452    _LIBCPP_INLINE_VISIBILITY
1453    void insert(initializer_list<value_type> __il)
1454        {insert(__il.begin(), __il.end());}
1455#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1456
1457    _LIBCPP_INLINE_VISIBILITY
1458    iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);}
1459    _LIBCPP_INLINE_VISIBILITY
1460    size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
1461    _LIBCPP_INLINE_VISIBILITY
1462    iterator erase(const_iterator __first, const_iterator __last)
1463        {return __table_.erase(__first.__i_, __last.__i_);}
1464    _LIBCPP_INLINE_VISIBILITY
1465    void clear() _NOEXCEPT {__table_.clear();}
1466
1467    _LIBCPP_INLINE_VISIBILITY
1468    void swap(unordered_multimap& __u)
1469        _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
1470        {__table_.swap(__u.__table_);}
1471
1472    _LIBCPP_INLINE_VISIBILITY
1473    hasher hash_function() const
1474        {return __table_.hash_function().hash_function();}
1475    _LIBCPP_INLINE_VISIBILITY
1476    key_equal key_eq() const
1477        {return __table_.key_eq().key_eq();}
1478
1479    _LIBCPP_INLINE_VISIBILITY
1480    iterator       find(const key_type& __k)       {return __table_.find(__k);}
1481    _LIBCPP_INLINE_VISIBILITY
1482    const_iterator find(const key_type& __k) const {return __table_.find(__k);}
1483    _LIBCPP_INLINE_VISIBILITY
1484    size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
1485    _LIBCPP_INLINE_VISIBILITY
1486    pair<iterator, iterator>             equal_range(const key_type& __k)
1487        {return __table_.__equal_range_multi(__k);}
1488    _LIBCPP_INLINE_VISIBILITY
1489    pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
1490        {return __table_.__equal_range_multi(__k);}
1491
1492    _LIBCPP_INLINE_VISIBILITY
1493    size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
1494    _LIBCPP_INLINE_VISIBILITY
1495    size_type max_bucket_count() const _NOEXCEPT
1496        {return __table_.max_bucket_count();}
1497
1498    _LIBCPP_INLINE_VISIBILITY
1499    size_type bucket_size(size_type __n) const
1500        {return __table_.bucket_size(__n);}
1501    _LIBCPP_INLINE_VISIBILITY
1502    size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
1503
1504    _LIBCPP_INLINE_VISIBILITY
1505    local_iterator       begin(size_type __n)        {return __table_.begin(__n);}
1506    _LIBCPP_INLINE_VISIBILITY
1507    local_iterator       end(size_type __n)          {return __table_.end(__n);}
1508    _LIBCPP_INLINE_VISIBILITY
1509    const_local_iterator begin(size_type __n) const  {return __table_.cbegin(__n);}
1510    _LIBCPP_INLINE_VISIBILITY
1511    const_local_iterator end(size_type __n) const    {return __table_.cend(__n);}
1512    _LIBCPP_INLINE_VISIBILITY
1513    const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
1514    _LIBCPP_INLINE_VISIBILITY
1515    const_local_iterator cend(size_type __n) const   {return __table_.cend(__n);}
1516
1517    _LIBCPP_INLINE_VISIBILITY
1518    float load_factor() const _NOEXCEPT {return __table_.load_factor();}
1519    _LIBCPP_INLINE_VISIBILITY
1520    float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
1521    _LIBCPP_INLINE_VISIBILITY
1522    void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
1523    _LIBCPP_INLINE_VISIBILITY
1524    void rehash(size_type __n) {__table_.rehash(__n);}
1525    _LIBCPP_INLINE_VISIBILITY
1526    void reserve(size_type __n) {__table_.reserve(__n);}
1527
1528private:
1529#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1530    __node_holder __construct_node();
1531    template <class _A0>
1532        typename enable_if
1533        <
1534            is_constructible<value_type, _A0>::value,
1535            __node_holder
1536        >::type
1537         __construct_node(_A0&& __a0);
1538    template <class _A0>
1539        typename enable_if
1540        <
1541            is_constructible<key_type, _A0>::value,
1542            __node_holder
1543        >::type
1544         __construct_node(_A0&& __a0);
1545#ifndef _LIBCPP_HAS_NO_VARIADICS
1546    template <class _A0, class _A1, class ..._Args>
1547        __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args);
1548#endif  // _LIBCPP_HAS_NO_VARIADICS
1549#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1550};
1551
1552template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1553unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1554        size_type __n, const hasher& __hf, const key_equal& __eql)
1555    : __table_(__hf, __eql)
1556{
1557    __table_.rehash(__n);
1558}
1559
1560template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1561unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1562        size_type __n, const hasher& __hf, const key_equal& __eql,
1563        const allocator_type& __a)
1564    : __table_(__hf, __eql, __a)
1565{
1566    __table_.rehash(__n);
1567}
1568
1569template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1570template <class _InputIterator>
1571unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1572        _InputIterator __first, _InputIterator __last)
1573{
1574    insert(__first, __last);
1575}
1576
1577template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1578template <class _InputIterator>
1579unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1580        _InputIterator __first, _InputIterator __last, size_type __n,
1581        const hasher& __hf, const key_equal& __eql)
1582    : __table_(__hf, __eql)
1583{
1584    __table_.rehash(__n);
1585    insert(__first, __last);
1586}
1587
1588template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1589template <class _InputIterator>
1590unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1591        _InputIterator __first, _InputIterator __last, size_type __n,
1592        const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1593    : __table_(__hf, __eql, __a)
1594{
1595    __table_.rehash(__n);
1596    insert(__first, __last);
1597}
1598
1599template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1600inline _LIBCPP_INLINE_VISIBILITY
1601unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1602        const allocator_type& __a)
1603    : __table_(__a)
1604{
1605}
1606
1607template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1608unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1609        const unordered_multimap& __u)
1610    : __table_(__u.__table_)
1611{
1612    __table_.rehash(__u.bucket_count());
1613    insert(__u.begin(), __u.end());
1614}
1615
1616template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1617unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1618        const unordered_multimap& __u, const allocator_type& __a)
1619    : __table_(__u.__table_, __a)
1620{
1621    __table_.rehash(__u.bucket_count());
1622    insert(__u.begin(), __u.end());
1623}
1624
1625#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1626
1627template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1628inline _LIBCPP_INLINE_VISIBILITY
1629unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1630        unordered_multimap&& __u)
1631    _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
1632    : __table_(_VSTD::move(__u.__table_))
1633{
1634}
1635
1636template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1637unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1638        unordered_multimap&& __u, const allocator_type& __a)
1639    : __table_(_VSTD::move(__u.__table_), __a)
1640{
1641    if (__a != __u.get_allocator())
1642    {
1643        iterator __i = __u.begin();
1644        while (__u.size() != 0)
1645{
1646            __table_.__insert_multi(
1647                _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_)
1648                                   );
1649}
1650    }
1651}
1652
1653#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1654
1655#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1656
1657template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1658unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1659        initializer_list<value_type> __il)
1660{
1661    insert(__il.begin(), __il.end());
1662}
1663
1664template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1665unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1666        initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1667        const key_equal& __eql)
1668    : __table_(__hf, __eql)
1669{
1670    __table_.rehash(__n);
1671    insert(__il.begin(), __il.end());
1672}
1673
1674template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1675unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1676        initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1677        const key_equal& __eql, const allocator_type& __a)
1678    : __table_(__hf, __eql, __a)
1679{
1680    __table_.rehash(__n);
1681    insert(__il.begin(), __il.end());
1682}
1683
1684#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1685
1686#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1687
1688template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1689inline _LIBCPP_INLINE_VISIBILITY
1690unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
1691unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_multimap&& __u)
1692    _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
1693{
1694    __table_ = _VSTD::move(__u.__table_);
1695    return *this;
1696}
1697
1698#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1699
1700#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1701
1702template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1703inline _LIBCPP_INLINE_VISIBILITY
1704unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
1705unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(
1706        initializer_list<value_type> __il)
1707{
1708    __table_.__assign_multi(__il.begin(), __il.end());
1709    return *this;
1710}
1711
1712#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1713
1714#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1715
1716template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1717typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1718unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node()
1719{
1720    __node_allocator& __na = __table_.__node_alloc();
1721    __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1722    __node_traits::construct(__na, _VSTD::addressof(__h->__value_));
1723    __h.get_deleter().__first_constructed = true;
1724    __h.get_deleter().__second_constructed = true;
1725    return __h;
1726}
1727
1728template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1729template <class _A0>
1730typename enable_if
1731<
1732    is_constructible<pair<const _Key, _Tp>, _A0>::value,
1733    typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1734>::type
1735unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
1736{
1737    __node_allocator& __na = __table_.__node_alloc();
1738    __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1739    __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1740                             _VSTD::forward<_A0>(__a0));
1741    __h.get_deleter().__first_constructed = true;
1742    __h.get_deleter().__second_constructed = true;
1743    return __h;
1744}
1745
1746template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1747template <class _A0>
1748typename enable_if
1749<
1750    is_constructible<_Key, _A0>::value,
1751    typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1752>::type
1753unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
1754{
1755    __node_allocator& __na = __table_.__node_alloc();
1756    __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1757    __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first),
1758                             _VSTD::forward<_A0>(__a0));
1759    __h.get_deleter().__first_constructed = true;
1760    __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second));
1761    __h.get_deleter().__second_constructed = true;
1762    return __h;
1763}
1764
1765#ifndef _LIBCPP_HAS_NO_VARIADICS
1766
1767template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1768template <class _A0, class _A1, class ..._Args>
1769typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1770unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(
1771        _A0&& __a0, _A1&& __a1, _Args&&... __args)
1772{
1773    __node_allocator& __na = __table_.__node_alloc();
1774    __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1775    __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1776                             _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1),
1777                             _VSTD::forward<_Args>(__args)...);
1778    __h.get_deleter().__first_constructed = true;
1779    __h.get_deleter().__second_constructed = true;
1780    return __h;
1781}
1782
1783template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1784template <class... _Args>
1785typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator
1786unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_Args&&... __args)
1787{
1788    __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1789    iterator __r = __table_.__node_insert_multi(__h.get());
1790    __h.release();
1791    return __r;
1792}
1793
1794template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1795template <class... _Args>
1796typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator
1797unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace_hint(
1798        const_iterator __p, _Args&&... __args)
1799{
1800    __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1801    iterator __r = __table_.__node_insert_multi(__p.__i_, __h.get());
1802    __h.release();
1803    return __r;
1804}
1805
1806#endif  // _LIBCPP_HAS_NO_VARIADICS
1807#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1808
1809template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1810template <class _InputIterator>
1811inline _LIBCPP_INLINE_VISIBILITY
1812void
1813unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
1814                                                            _InputIterator __last)
1815{
1816    for (; __first != __last; ++__first)
1817        __table_.__insert_multi(*__first);
1818}
1819
1820template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1821inline _LIBCPP_INLINE_VISIBILITY
1822void
1823swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1824     unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1825    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1826{
1827    __x.swap(__y);
1828}
1829
1830template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1831bool
1832operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1833           const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1834{
1835    if (__x.size() != __y.size())
1836        return false;
1837    typedef typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
1838                                                                 const_iterator;
1839    typedef pair<const_iterator, const_iterator> _EqRng;
1840    for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;)
1841    {
1842        _EqRng __xeq = __x.equal_range(__i->first);
1843        _EqRng __yeq = __y.equal_range(__i->first);
1844        if (_VSTD::distance(__xeq.first, __xeq.second) !=
1845            _VSTD::distance(__yeq.first, __yeq.second) ||
1846                  !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first))
1847            return false;
1848        __i = __xeq.second;
1849    }
1850    return true;
1851}
1852
1853template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1854inline _LIBCPP_INLINE_VISIBILITY
1855bool
1856operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1857           const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1858{
1859    return !(__x == __y);
1860}
1861
1862_LIBCPP_END_NAMESPACE_STD
1863
1864#endif  // _LIBCPP_UNORDERED_MAP
1865