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