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