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