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