llvm-project

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

19
namespace std
20
{
21

22
template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
23
          class Alloc = allocator<pair<const Key, T>>>
24
class unordered_map
25
{
26
public:
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

232
template<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>>>
235
unordered_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

240
template<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

247
template<class Key, class T, class Hash = hash<Key>,
248
    class Pred = equal_to<Key>, class Allocator = allocator<pair<const Key, T>>>
249
unordered_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

253
template<class InputIterator, class Allocator>
254
unordered_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

258
template<class InputIterator, class Allocator>
259
unordered_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

263
template<class InputIterator, class Hash, class Allocator>
264
unordered_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

268
template<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

273
template<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

278
template<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

283
template<class Key, class T, typename Allocator>
284
unordered_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

287
template<class Key, class T, typename Allocator>
288
unordered_map(initializer_list<pair<const Key, T>>, Allocator)
289
  -> unordered_map<Key, T, hash<Key>, equal_to<Key>, Allocator>; // C++17
290

291
template<class Key, class T, class Hash, class Allocator>
292
unordered_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

295
template <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

300
template <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

305
template <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

310
template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
311
          class Alloc = allocator<pair<const Key, T>>>
312
class unordered_multimap
313
{
314
public:
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

495
template<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>>>
498
unordered_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

503
template<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

510
template<class Key, class T, class Hash = hash<Key>,
511
    class Pred = equal_to<Key>, class Allocator = allocator<pair<const Key, T>>>
512
unordered_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

516
template<class InputIterator, class Allocator>
517
unordered_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

521
template<class InputIterator, class Allocator>
522
unordered_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

526
template<class InputIterator, class Hash, class Allocator>
527
unordered_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

531
template<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

536
template<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

541
template<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

546
template<class Key, class T, typename Allocator>
547
unordered_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

550
template<class Key, class T, typename Allocator>
551
unordered_multimap(initializer_list<pair<const Key, T>>, Allocator)
552
  -> unordered_multimap<Key, T, hash<Key>, equal_to<Key>, Allocator>; // C++17
553

554
template<class Key, class T, class Hash, class Allocator>
555
unordered_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

559
template <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

564
template <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

568
template <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

572
template <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

577
template <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/is_transparent.h>
590
#include <__functional/operations.h>
591
#include <__hash_table>
592
#include <__iterator/distance.h>
593
#include <__iterator/erase_if_container.h>
594
#include <__iterator/iterator_traits.h>
595
#include <__iterator/ranges_iterator_traits.h>
596
#include <__memory/addressof.h>
597
#include <__memory/allocator.h>
598
#include <__memory_resource/polymorphic_allocator.h>
599
#include <__node_handle>
600
#include <__ranges/concepts.h>
601
#include <__ranges/container_compatible_range.h>
602
#include <__ranges/from_range.h>
603
#include <__type_traits/is_allocator.h>
604
#include <__type_traits/type_identity.h>
605
#include <__utility/forward.h>
606
#include <stdexcept>
607
#include <tuple>
608
#include <version>
609

610
// standard-mandated includes
611

612
// [iterator.range]
613
#include <__iterator/access.h>
614
#include <__iterator/data.h>
615
#include <__iterator/empty.h>
616
#include <__iterator/reverse_access.h>
617
#include <__iterator/size.h>
618

619
// [unord.map.syn]
620
#include <compare>
621
#include <initializer_list>
622

623
#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
624
#  pragma GCC system_header
625
#endif
626

627
_LIBCPP_PUSH_MACROS
628
#include <__undef_macros>
629

630
_LIBCPP_BEGIN_NAMESPACE_STD
631

632
template <class _Key,
633
          class _Cp,
634
          class _Hash,
635
          class _Pred,
636
          bool = is_empty<_Hash>::value && !__libcpp_is_final<_Hash>::value>
637
class __unordered_map_hasher : private _Hash {
638
public:
639
  _LIBCPP_HIDE_FROM_ABI __unordered_map_hasher() _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value) : _Hash() {}
640
  _LIBCPP_HIDE_FROM_ABI __unordered_map_hasher(const _Hash& __h) _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value)
641
      : _Hash(__h) {}
642
  _LIBCPP_HIDE_FROM_ABI const _Hash& hash_function() const _NOEXCEPT { return *this; }
643
  _LIBCPP_HIDE_FROM_ABI size_t operator()(const _Cp& __x) const {
644
    return static_cast<const _Hash&>(*this)(__x.__get_value().first);
645
  }
646
  _LIBCPP_HIDE_FROM_ABI size_t operator()(const _Key& __x) const { return static_cast<const _Hash&>(*this)(__x); }
647
#if _LIBCPP_STD_VER >= 20
648
  template <typename _K2>
649
  _LIBCPP_HIDE_FROM_ABI size_t operator()(const _K2& __x) const {
650
    return static_cast<const _Hash&>(*this)(__x);
651
  }
652
#endif
653
  _LIBCPP_HIDE_FROM_ABI void swap(__unordered_map_hasher& __y) _NOEXCEPT_(__is_nothrow_swappable_v<_Hash>) {
654
    using std::swap;
655
    swap(static_cast<_Hash&>(*this), static_cast<_Hash&>(__y));
656
  }
657
};
658

659
template <class _Key, class _Cp, class _Hash, class _Pred>
660
class __unordered_map_hasher<_Key, _Cp, _Hash, _Pred, false> {
661
  _Hash __hash_;
662

663
public:
664
  _LIBCPP_HIDE_FROM_ABI __unordered_map_hasher() _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value)
665
      : __hash_() {}
666
  _LIBCPP_HIDE_FROM_ABI __unordered_map_hasher(const _Hash& __h) _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value)
667
      : __hash_(__h) {}
668
  _LIBCPP_HIDE_FROM_ABI const _Hash& hash_function() const _NOEXCEPT { return __hash_; }
669
  _LIBCPP_HIDE_FROM_ABI size_t operator()(const _Cp& __x) const { return __hash_(__x.__get_value().first); }
670
  _LIBCPP_HIDE_FROM_ABI size_t operator()(const _Key& __x) const { return __hash_(__x); }
671
#if _LIBCPP_STD_VER >= 20
672
  template <typename _K2>
673
  _LIBCPP_HIDE_FROM_ABI size_t operator()(const _K2& __x) const {
674
    return __hash_(__x);
675
  }
676
#endif
677
  _LIBCPP_HIDE_FROM_ABI void swap(__unordered_map_hasher& __y) _NOEXCEPT_(__is_nothrow_swappable_v<_Hash>) {
678
    using std::swap;
679
    swap(__hash_, __y.__hash_);
680
  }
681
};
682

683
template <class _Key, class _Cp, class _Hash, class _Pred, bool __b>
684
inline _LIBCPP_HIDE_FROM_ABI void
685
swap(__unordered_map_hasher<_Key, _Cp, _Hash, _Pred, __b>& __x,
686
     __unordered_map_hasher<_Key, _Cp, _Hash, _Pred, __b>& __y) _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
687
  __x.swap(__y);
688
}
689

690
template <class _Key,
691
          class _Cp,
692
          class _Pred,
693
          class _Hash,
694
          bool = is_empty<_Pred>::value && !__libcpp_is_final<_Pred>::value>
695
class __unordered_map_equal : private _Pred {
696
public:
697
  _LIBCPP_HIDE_FROM_ABI __unordered_map_equal() _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value) : _Pred() {}
698
  _LIBCPP_HIDE_FROM_ABI __unordered_map_equal(const _Pred& __p) _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value)
699
      : _Pred(__p) {}
700
  _LIBCPP_HIDE_FROM_ABI const _Pred& key_eq() const _NOEXCEPT { return *this; }
701
  _LIBCPP_HIDE_FROM_ABI bool operator()(const _Cp& __x, const _Cp& __y) const {
702
    return static_cast<const _Pred&>(*this)(__x.__get_value().first, __y.__get_value().first);
703
  }
704
  _LIBCPP_HIDE_FROM_ABI bool operator()(const _Cp& __x, const _Key& __y) const {
705
    return static_cast<const _Pred&>(*this)(__x.__get_value().first, __y);
706
  }
707
  _LIBCPP_HIDE_FROM_ABI bool operator()(const _Key& __x, const _Cp& __y) const {
708
    return static_cast<const _Pred&>(*this)(__x, __y.__get_value().first);
709
  }
710
#if _LIBCPP_STD_VER >= 20
711
  template <typename _K2>
712
  _LIBCPP_HIDE_FROM_ABI bool operator()(const _Cp& __x, const _K2& __y) const {
713
    return static_cast<const _Pred&>(*this)(__x.__get_value().first, __y);
714
  }
715
  template <typename _K2>
716
  _LIBCPP_HIDE_FROM_ABI bool operator()(const _K2& __x, const _Cp& __y) const {
717
    return static_cast<const _Pred&>(*this)(__x, __y.__get_value().first);
718
  }
719
  template <typename _K2>
720
  _LIBCPP_HIDE_FROM_ABI bool operator()(const _Key& __x, const _K2& __y) const {
721
    return static_cast<const _Pred&>(*this)(__x, __y);
722
  }
723
  template <typename _K2>
724
  _LIBCPP_HIDE_FROM_ABI bool operator()(const _K2& __x, const _Key& __y) const {
725
    return static_cast<const _Pred&>(*this)(__x, __y);
726
  }
727
#endif
728
  _LIBCPP_HIDE_FROM_ABI void swap(__unordered_map_equal& __y) _NOEXCEPT_(__is_nothrow_swappable_v<_Pred>) {
729
    using std::swap;
730
    swap(static_cast<_Pred&>(*this), static_cast<_Pred&>(__y));
731
  }
732
};
733

734
template <class _Key, class _Cp, class _Pred, class _Hash>
735
class __unordered_map_equal<_Key, _Cp, _Pred, _Hash, false> {
736
  _Pred __pred_;
737

738
public:
739
  _LIBCPP_HIDE_FROM_ABI __unordered_map_equal() _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value)
740
      : __pred_() {}
741
  _LIBCPP_HIDE_FROM_ABI __unordered_map_equal(const _Pred& __p) _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value)
742
      : __pred_(__p) {}
743
  _LIBCPP_HIDE_FROM_ABI const _Pred& key_eq() const _NOEXCEPT { return __pred_; }
744
  _LIBCPP_HIDE_FROM_ABI bool operator()(const _Cp& __x, const _Cp& __y) const {
745
    return __pred_(__x.__get_value().first, __y.__get_value().first);
746
  }
747
  _LIBCPP_HIDE_FROM_ABI bool operator()(const _Cp& __x, const _Key& __y) const {
748
    return __pred_(__x.__get_value().first, __y);
749
  }
750
  _LIBCPP_HIDE_FROM_ABI bool operator()(const _Key& __x, const _Cp& __y) const {
751
    return __pred_(__x, __y.__get_value().first);
752
  }
753
#if _LIBCPP_STD_VER >= 20
754
  template <typename _K2>
755
  _LIBCPP_HIDE_FROM_ABI bool operator()(const _Cp& __x, const _K2& __y) const {
756
    return __pred_(__x.__get_value().first, __y);
757
  }
758
  template <typename _K2>
759
  _LIBCPP_HIDE_FROM_ABI bool operator()(const _K2& __x, const _Cp& __y) const {
760
    return __pred_(__x, __y.__get_value().first);
761
  }
762
  template <typename _K2>
763
  _LIBCPP_HIDE_FROM_ABI bool operator()(const _Key& __x, const _K2& __y) const {
764
    return __pred_(__x, __y);
765
  }
766
  template <typename _K2>
767
  _LIBCPP_HIDE_FROM_ABI bool operator()(const _K2& __x, const _Key& __y) const {
768
    return __pred_(__x, __y);
769
  }
770
#endif
771
  _LIBCPP_HIDE_FROM_ABI void swap(__unordered_map_equal& __y) _NOEXCEPT_(__is_nothrow_swappable_v<_Pred>) {
772
    using std::swap;
773
    swap(__pred_, __y.__pred_);
774
  }
775
};
776

777
template <class _Key, class _Cp, class _Pred, class _Hash, bool __b>
778
inline _LIBCPP_HIDE_FROM_ABI void
779
swap(__unordered_map_equal<_Key, _Cp, _Pred, _Hash, __b>& __x, __unordered_map_equal<_Key, _Cp, _Pred, _Hash, __b>& __y)
780
    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
781
  __x.swap(__y);
782
}
783

784
template <class _Alloc>
785
class __hash_map_node_destructor {
786
  typedef _Alloc allocator_type;
787
  typedef allocator_traits<allocator_type> __alloc_traits;
788

789
public:
790
  typedef typename __alloc_traits::pointer pointer;
791

792
private:
793
  allocator_type& __na_;
794

795
public:
796
  bool __first_constructed;
797
  bool __second_constructed;
798

799
  __hash_map_node_destructor& operator=(const __hash_map_node_destructor&) = delete;
800

801
  _LIBCPP_HIDE_FROM_ABI explicit __hash_map_node_destructor(allocator_type& __na) _NOEXCEPT
802
      : __na_(__na),
803
        __first_constructed(false),
804
        __second_constructed(false) {}
805

806
#ifndef _LIBCPP_CXX03_LANG
807
  _LIBCPP_HIDE_FROM_ABI __hash_map_node_destructor(__hash_node_destructor<allocator_type>&& __x) _NOEXCEPT
808
      : __na_(__x.__na_),
809
        __first_constructed(__x.__value_constructed),
810
        __second_constructed(__x.__value_constructed) {
811
    __x.__value_constructed = false;
812
  }
813
#else  // _LIBCPP_CXX03_LANG
814
  _LIBCPP_HIDE_FROM_ABI __hash_map_node_destructor(const __hash_node_destructor<allocator_type>& __x)
815
      : __na_(__x.__na_), __first_constructed(__x.__value_constructed), __second_constructed(__x.__value_constructed) {
816
    const_cast<bool&>(__x.__value_constructed) = false;
817
  }
818
#endif // _LIBCPP_CXX03_LANG
819

820
  _LIBCPP_HIDE_FROM_ABI void operator()(pointer __p) _NOEXCEPT {
821
    if (__second_constructed)
822
      __alloc_traits::destroy(__na_, std::addressof(__p->__get_value().__get_value().second));
823
    if (__first_constructed)
824
      __alloc_traits::destroy(__na_, std::addressof(__p->__get_value().__get_value().first));
825
    if (__p)
826
      __alloc_traits::deallocate(__na_, __p, 1);
827
  }
828
};
829

830
#ifndef _LIBCPP_CXX03_LANG
831
template <class _Key, class _Tp>
832
struct _LIBCPP_STANDALONE_DEBUG __hash_value_type {
833
  typedef _Key key_type;
834
  typedef _Tp mapped_type;
835
  typedef pair<const key_type, mapped_type> value_type;
836
  typedef pair<key_type&, mapped_type&> __nc_ref_pair_type;
837
  typedef pair<key_type&&, mapped_type&&> __nc_rref_pair_type;
838

839
private:
840
  value_type __cc_;
841

842
public:
843
  _LIBCPP_HIDE_FROM_ABI value_type& __get_value() {
844
#  if _LIBCPP_STD_VER >= 17
845
    return *std::launder(std::addressof(__cc_));
846
#  else
847
    return __cc_;
848
#  endif
849
  }
850

851
  _LIBCPP_HIDE_FROM_ABI const value_type& __get_value() const {
852
#  if _LIBCPP_STD_VER >= 17
853
    return *std::launder(std::addressof(__cc_));
854
#  else
855
    return __cc_;
856
#  endif
857
  }
858

859
  _LIBCPP_HIDE_FROM_ABI __nc_ref_pair_type __ref() {
860
    value_type& __v = __get_value();
861
    return __nc_ref_pair_type(const_cast<key_type&>(__v.first), __v.second);
862
  }
863

864
  _LIBCPP_HIDE_FROM_ABI __nc_rref_pair_type __move() {
865
    value_type& __v = __get_value();
866
    return __nc_rref_pair_type(std::move(const_cast<key_type&>(__v.first)), std::move(__v.second));
867
  }
868

869
  _LIBCPP_HIDE_FROM_ABI __hash_value_type& operator=(const __hash_value_type& __v) {
870
    __ref() = __v.__get_value();
871
    return *this;
872
  }
873

874
  _LIBCPP_HIDE_FROM_ABI __hash_value_type& operator=(__hash_value_type&& __v) {
875
    __ref() = __v.__move();
876
    return *this;
877
  }
878

879
  template <class _ValueTp, __enable_if_t<__is_same_uncvref<_ValueTp, value_type>::value, int> = 0>
880
  _LIBCPP_HIDE_FROM_ABI __hash_value_type& operator=(_ValueTp&& __v) {
881
    __ref() = std::forward<_ValueTp>(__v);
882
    return *this;
883
  }
884

885
  __hash_value_type(const __hash_value_type& __v) = delete;
886
  __hash_value_type(__hash_value_type&& __v)      = delete;
887
  template <class... _Args>
888
  explicit __hash_value_type(_Args&&... __args) = delete;
889

890
  ~__hash_value_type() = delete;
891
};
892

893
#else
894

895
template <class _Key, class _Tp>
896
struct __hash_value_type {
897
  typedef _Key key_type;
898
  typedef _Tp mapped_type;
899
  typedef pair<const key_type, mapped_type> value_type;
900

901
private:
902
  value_type __cc_;
903

904
public:
905
  _LIBCPP_HIDE_FROM_ABI value_type& __get_value() { return __cc_; }
906
  _LIBCPP_HIDE_FROM_ABI const value_type& __get_value() const { return __cc_; }
907

908
  ~__hash_value_type() = delete;
909
};
910

911
#endif
912

913
template <class _HashIterator>
914
class _LIBCPP_TEMPLATE_VIS __hash_map_iterator {
915
  _HashIterator __i_;
916

917
  typedef __hash_node_types_from_iterator<_HashIterator> _NodeTypes;
918

919
public:
920
  typedef forward_iterator_tag iterator_category;
921
  typedef typename _NodeTypes::__map_value_type value_type;
922
  typedef typename _NodeTypes::difference_type difference_type;
923
  typedef value_type& reference;
924
  typedef typename _NodeTypes::__map_value_type_pointer pointer;
925

926
  _LIBCPP_HIDE_FROM_ABI __hash_map_iterator() _NOEXCEPT {}
927

928
  _LIBCPP_HIDE_FROM_ABI __hash_map_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
929

930
  _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __i_->__get_value(); }
931
  _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return pointer_traits<pointer>::pointer_to(__i_->__get_value()); }
932

933
  _LIBCPP_HIDE_FROM_ABI __hash_map_iterator& operator++() {
934
    ++__i_;
935
    return *this;
936
  }
937
  _LIBCPP_HIDE_FROM_ABI __hash_map_iterator operator++(int) {
938
    __hash_map_iterator __t(*this);
939
    ++(*this);
940
    return __t;
941
  }
942

943
  friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y) {
944
    return __x.__i_ == __y.__i_;
945
  }
946
#if _LIBCPP_STD_VER <= 17
947
  friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y) {
948
    return __x.__i_ != __y.__i_;
949
  }
950
#endif
951

952
  template <class, class, class, class, class>
953
  friend class _LIBCPP_TEMPLATE_VIS unordered_map;
954
  template <class, class, class, class, class>
955
  friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
956
  template <class>
957
  friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator;
958
  template <class>
959
  friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator;
960
  template <class>
961
  friend class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator;
962
};
963

964
template <class _HashIterator>
965
class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator {
966
  _HashIterator __i_;
967

968
  typedef __hash_node_types_from_iterator<_HashIterator> _NodeTypes;
969

970
public:
971
  typedef forward_iterator_tag iterator_category;
972
  typedef typename _NodeTypes::__map_value_type value_type;
973
  typedef typename _NodeTypes::difference_type difference_type;
974
  typedef const value_type& reference;
975
  typedef typename _NodeTypes::__const_map_value_type_pointer pointer;
976

977
  _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator() _NOEXCEPT {}
978

979
  _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
980
  _LIBCPP_HIDE_FROM_ABI
981
  __hash_map_const_iterator(__hash_map_iterator<typename _HashIterator::__non_const_iterator> __i) _NOEXCEPT
982
      : __i_(__i.__i_) {}
983

984
  _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __i_->__get_value(); }
985
  _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return pointer_traits<pointer>::pointer_to(__i_->__get_value()); }
986

987
  _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator& operator++() {
988
    ++__i_;
989
    return *this;
990
  }
991
  _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator operator++(int) {
992
    __hash_map_const_iterator __t(*this);
993
    ++(*this);
994
    return __t;
995
  }
996

997
  friend _LIBCPP_HIDE_FROM_ABI bool
998
  operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) {
999
    return __x.__i_ == __y.__i_;
1000
  }
1001
#if _LIBCPP_STD_VER <= 17
1002
  friend _LIBCPP_HIDE_FROM_ABI bool
1003
  operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) {
1004
    return __x.__i_ != __y.__i_;
1005
  }
1006
#endif
1007

1008
  template <class, class, class, class, class>
1009
  friend class _LIBCPP_TEMPLATE_VIS unordered_map;
1010
  template <class, class, class, class, class>
1011
  friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
1012
  template <class>
1013
  friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator;
1014
  template <class>
1015
  friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator;
1016
};
1017

1018
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1019
class unordered_multimap;
1020

1021
template <class _Key,
1022
          class _Tp,
1023
          class _Hash  = hash<_Key>,
1024
          class _Pred  = equal_to<_Key>,
1025
          class _Alloc = allocator<pair<const _Key, _Tp> > >
1026
class _LIBCPP_TEMPLATE_VIS unordered_map {
1027
public:
1028
  // types
1029
  typedef _Key key_type;
1030
  typedef _Tp mapped_type;
1031
  typedef __type_identity_t<_Hash> hasher;
1032
  typedef __type_identity_t<_Pred> key_equal;
1033
  typedef __type_identity_t<_Alloc> allocator_type;
1034
  typedef pair<const key_type, mapped_type> value_type;
1035
  typedef value_type& reference;
1036
  typedef const value_type& const_reference;
1037
  static_assert(is_same<value_type, typename allocator_type::value_type>::value,
1038
                "Allocator::value_type must be same type as value_type");
1039

1040
private:
1041
  typedef __hash_value_type<key_type, mapped_type> __value_type;
1042
  typedef __unordered_map_hasher<key_type, __value_type, hasher, key_equal> __hasher;
1043
  typedef __unordered_map_equal<key_type, __value_type, key_equal, hasher> __key_equal;
1044
  typedef __rebind_alloc<allocator_traits<allocator_type>, __value_type> __allocator_type;
1045

1046
  typedef __hash_table<__value_type, __hasher, __key_equal, __allocator_type> __table;
1047

1048
  __table __table_;
1049

1050
  typedef typename __table::_NodeTypes _NodeTypes;
1051
  typedef typename __table::__node_pointer __node_pointer;
1052
  typedef typename __table::__node_const_pointer __node_const_pointer;
1053
  typedef typename __table::__node_traits __node_traits;
1054
  typedef typename __table::__node_allocator __node_allocator;
1055
  typedef typename __table::__node __node;
1056
  typedef __hash_map_node_destructor<__node_allocator> _Dp;
1057
  typedef unique_ptr<__node, _Dp> __node_holder;
1058
  typedef allocator_traits<allocator_type> __alloc_traits;
1059

1060
  static_assert(__check_valid_allocator<allocator_type>::value, "");
1061

1062
  static_assert(is_same<typename __table::__container_value_type, value_type>::value, "");
1063
  static_assert(is_same<typename __table::__node_value_type, __value_type>::value, "");
1064

1065
public:
1066
  typedef typename __alloc_traits::pointer pointer;
1067
  typedef typename __alloc_traits::const_pointer const_pointer;
1068
  typedef typename __table::size_type size_type;
1069
  typedef typename __table::difference_type difference_type;
1070

1071
  typedef __hash_map_iterator<typename __table::iterator> iterator;
1072
  typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
1073
  typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
1074
  typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
1075

1076
#if _LIBCPP_STD_VER >= 17
1077
  typedef __map_node_handle<__node, allocator_type> node_type;
1078
  typedef __insert_return_type<iterator, node_type> insert_return_type;
1079
#endif
1080

1081
  template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2>
1082
  friend class _LIBCPP_TEMPLATE_VIS unordered_map;
1083
  template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2>
1084
  friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
1085

1086
  _LIBCPP_HIDE_FROM_ABI unordered_map() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) {}
1087
  explicit _LIBCPP_HIDE_FROM_ABI
1088
  unordered_map(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
1089
  _LIBCPP_HIDE_FROM_ABI
1090
  unordered_map(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a);
1091
  template <class _InputIterator>
1092
  _LIBCPP_HIDE_FROM_ABI unordered_map(_InputIterator __first, _InputIterator __last);
1093
  template <class _InputIterator>
1094
  _LIBCPP_HIDE_FROM_ABI
1095
  unordered_map(_InputIterator __first,
1096
                _InputIterator __last,
1097
                size_type __n,
1098
                const hasher& __hf     = hasher(),
1099
                const key_equal& __eql = key_equal());
1100
  template <class _InputIterator>
1101
  _LIBCPP_HIDE_FROM_ABI unordered_map(
1102
      _InputIterator __first,
1103
      _InputIterator __last,
1104
      size_type __n,
1105
      const hasher& __hf,
1106
      const key_equal& __eql,
1107
      const allocator_type& __a);
1108

1109
#if _LIBCPP_STD_VER >= 23
1110
  template <_ContainerCompatibleRange<value_type> _Range>
1111
  _LIBCPP_HIDE_FROM_ABI unordered_map(
1112
      from_range_t,
1113
      _Range&& __range,
1114
      size_type __n             = /*implementation-defined*/ 0,
1115
      const hasher& __hf        = hasher(),
1116
      const key_equal& __eql    = key_equal(),
1117
      const allocator_type& __a = allocator_type())
1118
      : __table_(__hf, __eql, typename __table::allocator_type(__a)) {
1119
    if (__n > 0) {
1120
      __table_.__rehash_unique(__n);
1121
    }
1122
    insert_range(std::forward<_Range>(__range));
1123
  }
1124
#endif
1125

1126
  _LIBCPP_HIDE_FROM_ABI explicit unordered_map(const allocator_type& __a);
1127
  _LIBCPP_HIDE_FROM_ABI unordered_map(const unordered_map& __u);
1128
  _LIBCPP_HIDE_FROM_ABI unordered_map(const unordered_map& __u, const allocator_type& __a);
1129
#ifndef _LIBCPP_CXX03_LANG
1130
  _LIBCPP_HIDE_FROM_ABI unordered_map(unordered_map&& __u) _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
1131
  _LIBCPP_HIDE_FROM_ABI unordered_map(unordered_map&& __u, const allocator_type& __a);
1132
  _LIBCPP_HIDE_FROM_ABI unordered_map(initializer_list<value_type> __il);
1133
  _LIBCPP_HIDE_FROM_ABI
1134
  unordered_map(initializer_list<value_type> __il,
1135
                size_type __n,
1136
                const hasher& __hf     = hasher(),
1137
                const key_equal& __eql = key_equal());
1138
  _LIBCPP_HIDE_FROM_ABI unordered_map(
1139
      initializer_list<value_type> __il,
1140
      size_type __n,
1141
      const hasher& __hf,
1142
      const key_equal& __eql,
1143
      const allocator_type& __a);
1144
#endif // _LIBCPP_CXX03_LANG
1145
#if _LIBCPP_STD_VER >= 14
1146
  _LIBCPP_HIDE_FROM_ABI unordered_map(size_type __n, const allocator_type& __a)
1147
      : unordered_map(__n, hasher(), key_equal(), __a) {}
1148
  _LIBCPP_HIDE_FROM_ABI unordered_map(size_type __n, const hasher& __hf, const allocator_type& __a)
1149
      : unordered_map(__n, __hf, key_equal(), __a) {}
1150
  template <class _InputIterator>
1151
  _LIBCPP_HIDE_FROM_ABI
1152
  unordered_map(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a)
1153
      : unordered_map(__first, __last, __n, hasher(), key_equal(), __a) {}
1154
  template <class _InputIterator>
1155
  _LIBCPP_HIDE_FROM_ABI unordered_map(
1156
      _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const allocator_type& __a)
1157
      : unordered_map(__first, __last, __n, __hf, key_equal(), __a) {}
1158

1159
#  if _LIBCPP_STD_VER >= 23
1160
  template <_ContainerCompatibleRange<value_type> _Range>
1161
  _LIBCPP_HIDE_FROM_ABI unordered_map(from_range_t, _Range&& __range, size_type __n, const allocator_type& __a)
1162
      : unordered_map(from_range, std::forward<_Range>(__range), __n, hasher(), key_equal(), __a) {}
1163

1164
  template <_ContainerCompatibleRange<value_type> _Range>
1165
  _LIBCPP_HIDE_FROM_ABI
1166
  unordered_map(from_range_t, _Range&& __range, size_type __n, const hasher& __hf, const allocator_type& __a)
1167
      : unordered_map(from_range, std::forward<_Range>(__range), __n, __hf, key_equal(), __a) {}
1168
#  endif
1169

1170
  _LIBCPP_HIDE_FROM_ABI unordered_map(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)
1171
      : unordered_map(__il, __n, hasher(), key_equal(), __a) {}
1172
  _LIBCPP_HIDE_FROM_ABI
1173
  unordered_map(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a)
1174
      : unordered_map(__il, __n, __hf, key_equal(), __a) {}
1175
#endif
1176
  _LIBCPP_HIDE_FROM_ABI ~unordered_map() {
1177
    static_assert(sizeof(std::__diagnose_unordered_container_requirements<_Key, _Hash, _Pred>(0)), "");
1178
  }
1179

1180
  _LIBCPP_HIDE_FROM_ABI unordered_map& operator=(const unordered_map& __u) {
1181
#ifndef _LIBCPP_CXX03_LANG
1182
    __table_ = __u.__table_;
1183
#else
1184
    if (this != std::addressof(__u)) {
1185
      __table_.clear();
1186
      __table_.hash_function()   = __u.__table_.hash_function();
1187
      __table_.key_eq()          = __u.__table_.key_eq();
1188
      __table_.max_load_factor() = __u.__table_.max_load_factor();
1189
      __table_.__copy_assign_alloc(__u.__table_);
1190
      insert(__u.begin(), __u.end());
1191
    }
1192
#endif
1193
    return *this;
1194
  }
1195
#ifndef _LIBCPP_CXX03_LANG
1196
  _LIBCPP_HIDE_FROM_ABI unordered_map& operator=(unordered_map&& __u)
1197
      _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
1198
  _LIBCPP_HIDE_FROM_ABI unordered_map& operator=(initializer_list<value_type> __il);
1199
#endif // _LIBCPP_CXX03_LANG
1200

1201
  _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT {
1202
    return allocator_type(__table_.__node_alloc());
1203
  }
1204

1205
  _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __table_.size() == 0; }
1206
  _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __table_.size(); }
1207
  _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __table_.max_size(); }
1208

1209
  _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __table_.begin(); }
1210
  _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __table_.end(); }
1211
  _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __table_.begin(); }
1212
  _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __table_.end(); }
1213
  _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return __table_.begin(); }
1214
  _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return __table_.end(); }
1215

1216
  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(const value_type& __x) { return __table_.__insert_unique(__x); }
1217

1218
  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, const value_type& __x) { return insert(__x).first; }
1219

1220
  template <class _InputIterator>
1221
  _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last);
1222

1223
#if _LIBCPP_STD_VER >= 23
1224
  template <_ContainerCompatibleRange<value_type> _Range>
1225
  _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) {
1226
    for (auto&& __element : __range) {
1227
      __table_.__insert_unique(std::forward<decltype(__element)>(__element));
1228
    }
1229
  }
1230
#endif
1231

1232
#ifndef _LIBCPP_CXX03_LANG
1233
  _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); }
1234

1235
  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(value_type&& __x) {
1236
    return __table_.__insert_unique(std::move(__x));
1237
  }
1238

1239
  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, value_type&& __x) {
1240
    return __table_.__insert_unique(std::move(__x)).first;
1241
  }
1242

1243
  template <class _Pp, __enable_if_t<is_constructible<value_type, _Pp>::value, int> = 0>
1244
  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(_Pp&& __x) {
1245
    return __table_.__insert_unique(std::forward<_Pp>(__x));
1246
  }
1247

1248
  template <class _Pp, __enable_if_t<is_constructible<value_type, _Pp>::value, int> = 0>
1249
  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, _Pp&& __x) {
1250
    return insert(std::forward<_Pp>(__x)).first;
1251
  }
1252

1253
  template <class... _Args>
1254
  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> emplace(_Args&&... __args) {
1255
    return __table_.__emplace_unique(std::forward<_Args>(__args)...);
1256
  }
1257

1258
  template <class... _Args>
1259
  _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator, _Args&&... __args) {
1260
    return __table_.__emplace_unique(std::forward<_Args>(__args)...).first;
1261
  }
1262

1263
#endif // _LIBCPP_CXX03_LANG
1264

1265
#if _LIBCPP_STD_VER >= 17
1266
  template <class... _Args>
1267
  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args) {
1268
    return __table_.__emplace_unique_key_args(
1269
        __k, piecewise_construct, std::forward_as_tuple(__k), std::forward_as_tuple(std::forward<_Args>(__args)...));
1270
  }
1271

1272
  template <class... _Args>
1273
  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args) {
1274
    return __table_.__emplace_unique_key_args(
1275
        __k,
1276
        piecewise_construct,
1277
        std::forward_as_tuple(std::move(__k)),
1278
        std::forward_as_tuple(std::forward<_Args>(__args)...));
1279
  }
1280

1281
  template <class... _Args>
1282
  _LIBCPP_HIDE_FROM_ABI iterator try_emplace(const_iterator, const key_type& __k, _Args&&... __args) {
1283
    return try_emplace(__k, std::forward<_Args>(__args)...).first;
1284
  }
1285

1286
  template <class... _Args>
1287
  _LIBCPP_HIDE_FROM_ABI iterator try_emplace(const_iterator, key_type&& __k, _Args&&... __args) {
1288
    return try_emplace(std::move(__k), std::forward<_Args>(__args)...).first;
1289
  }
1290

1291
  template <class _Vp>
1292
  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert_or_assign(const key_type& __k, _Vp&& __v) {
1293
    pair<iterator, bool> __res = __table_.__emplace_unique_key_args(__k, __k, std::forward<_Vp>(__v));
1294
    if (!__res.second) {
1295
      __res.first->second = std::forward<_Vp>(__v);
1296
    }
1297
    return __res;
1298
  }
1299

1300
  template <class _Vp>
1301
  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert_or_assign(key_type&& __k, _Vp&& __v) {
1302
    pair<iterator, bool> __res = __table_.__emplace_unique_key_args(__k, std::move(__k), std::forward<_Vp>(__v));
1303
    if (!__res.second) {
1304
      __res.first->second = std::forward<_Vp>(__v);
1305
    }
1306
    return __res;
1307
  }
1308

1309
  template <class _Vp>
1310
  _LIBCPP_HIDE_FROM_ABI iterator insert_or_assign(const_iterator, const key_type& __k, _Vp&& __v) {
1311
    return insert_or_assign(__k, std::forward<_Vp>(__v)).first;
1312
  }
1313

1314
  template <class _Vp>
1315
  _LIBCPP_HIDE_FROM_ABI iterator insert_or_assign(const_iterator, key_type&& __k, _Vp&& __v) {
1316
    return insert_or_assign(std::move(__k), std::forward<_Vp>(__v)).first;
1317
  }
1318
#endif // _LIBCPP_STD_VER >= 17
1319

1320
  _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __table_.erase(__p.__i_); }
1321
  _LIBCPP_HIDE_FROM_ABI iterator erase(iterator __p) { return __table_.erase(__p.__i_); }
1322
  _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_unique(__k); }
1323
  _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last) {
1324
    return __table_.erase(__first.__i_, __last.__i_);
1325
  }
1326
  _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __table_.clear(); }
1327

1328
#if _LIBCPP_STD_VER >= 17
1329
  _LIBCPP_HIDE_FROM_ABI insert_return_type insert(node_type&& __nh) {
1330
    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
1331
                                        "node_type with incompatible allocator passed to unordered_map::insert()");
1332
    return __table_.template __node_handle_insert_unique< node_type, insert_return_type>(std::move(__nh));
1333
  }
1334
  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, node_type&& __nh) {
1335
    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
1336
                                        "node_type with incompatible allocator passed to unordered_map::insert()");
1337
    return __table_.template __node_handle_insert_unique<node_type>(__hint.__i_, std::move(__nh));
1338
  }
1339
  _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) {
1340
    return __table_.template __node_handle_extract<node_type>(__key);
1341
  }
1342
  _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __it) {
1343
    return __table_.template __node_handle_extract<node_type>(__it.__i_);
1344
  }
1345

1346
  template <class _H2, class _P2>
1347
  _LIBCPP_HIDE_FROM_ABI void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>& __source) {
1348
    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1349
        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1350
    return __table_.__node_handle_merge_unique(__source.__table_);
1351
  }
1352
  template <class _H2, class _P2>
1353
  _LIBCPP_HIDE_FROM_ABI void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>&& __source) {
1354
    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1355
        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1356
    return __table_.__node_handle_merge_unique(__source.__table_);
1357
  }
1358
  template <class _H2, class _P2>
1359
  _LIBCPP_HIDE_FROM_ABI void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>& __source) {
1360
    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1361
        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1362
    return __table_.__node_handle_merge_unique(__source.__table_);
1363
  }
1364
  template <class _H2, class _P2>
1365
  _LIBCPP_HIDE_FROM_ABI void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>&& __source) {
1366
    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1367
        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1368
    return __table_.__node_handle_merge_unique(__source.__table_);
1369
  }
1370
#endif
1371

1372
  _LIBCPP_HIDE_FROM_ABI void swap(unordered_map& __u) _NOEXCEPT_(__is_nothrow_swappable_v<__table>) {
1373
    __table_.swap(__u.__table_);
1374
  }
1375

1376
  _LIBCPP_HIDE_FROM_ABI hasher hash_function() const { return __table_.hash_function().hash_function(); }
1377
  _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq().key_eq(); }
1378

1379
  _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); }
1380
  _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); }
1381
#if _LIBCPP_STD_VER >= 20
1382
  template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
1383
  _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) {
1384
    return __table_.find(__k);
1385
  }
1386
  template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
1387
  _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const {
1388
    return __table_.find(__k);
1389
  }
1390
#endif // _LIBCPP_STD_VER >= 20
1391

1392
  _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_unique(__k); }
1393
#if _LIBCPP_STD_VER >= 20
1394
  template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
1395
  _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const {
1396
    return __table_.__count_unique(__k);
1397
  }
1398
#endif // _LIBCPP_STD_VER >= 20
1399

1400
#if _LIBCPP_STD_VER >= 20
1401
  _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); }
1402

1403
  template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
1404
  _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const {
1405
    return find(__k) != end();
1406
  }
1407
#endif // _LIBCPP_STD_VER >= 20
1408

1409
  _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {
1410
    return __table_.__equal_range_unique(__k);
1411
  }
1412
  _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
1413
    return __table_.__equal_range_unique(__k);
1414
  }
1415
#if _LIBCPP_STD_VER >= 20
1416
  template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
1417
  _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) {
1418
    return __table_.__equal_range_unique(__k);
1419
  }
1420
  template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
1421
  _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const {
1422
    return __table_.__equal_range_unique(__k);
1423
  }
1424
#endif // _LIBCPP_STD_VER >= 20
1425

1426
  _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](const key_type& __k);
1427
#ifndef _LIBCPP_CXX03_LANG
1428
  _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](key_type&& __k);
1429
#endif
1430

1431
  _LIBCPP_HIDE_FROM_ABI mapped_type& at(const key_type& __k);
1432
  _LIBCPP_HIDE_FROM_ABI const mapped_type& at(const key_type& __k) const;
1433

1434
  _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const _NOEXCEPT { return __table_.bucket_count(); }
1435
  _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const _NOEXCEPT { return __table_.max_bucket_count(); }
1436

1437
  _LIBCPP_HIDE_FROM_ABI size_type bucket_size(size_type __n) const { return __table_.bucket_size(__n); }
1438
  _LIBCPP_HIDE_FROM_ABI size_type bucket(const key_type& __k) const { return __table_.bucket(__k); }
1439

1440
  _LIBCPP_HIDE_FROM_ABI local_iterator begin(size_type __n) { return __table_.begin(__n); }
1441
  _LIBCPP_HIDE_FROM_ABI local_iterator end(size_type __n) { return __table_.end(__n); }
1442
  _LIBCPP_HIDE_FROM_ABI const_local_iterator begin(size_type __n) const { return __table_.cbegin(__n); }
1443
  _LIBCPP_HIDE_FROM_ABI const_local_iterator end(size_type __n) const { return __table_.cend(__n); }
1444
  _LIBCPP_HIDE_FROM_ABI const_local_iterator cbegin(size_type __n) const { return __table_.cbegin(__n); }
1445
  _LIBCPP_HIDE_FROM_ABI const_local_iterator cend(size_type __n) const { return __table_.cend(__n); }
1446

1447
  _LIBCPP_HIDE_FROM_ABI float load_factor() const _NOEXCEPT { return __table_.load_factor(); }
1448
  _LIBCPP_HIDE_FROM_ABI float max_load_factor() const _NOEXCEPT { return __table_.max_load_factor(); }
1449
  _LIBCPP_HIDE_FROM_ABI void max_load_factor(float __mlf) { __table_.max_load_factor(__mlf); }
1450
  _LIBCPP_HIDE_FROM_ABI void rehash(size_type __n) { __table_.__rehash_unique(__n); }
1451
  _LIBCPP_HIDE_FROM_ABI void reserve(size_type __n) { __table_.__reserve_unique(__n); }
1452

1453
private:
1454
#ifdef _LIBCPP_CXX03_LANG
1455
  _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node_with_key(const key_type& __k);
1456
#endif
1457
};
1458

1459
#if _LIBCPP_STD_VER >= 17
1460
template <class _InputIterator,
1461
          class _Hash      = hash<__iter_key_type<_InputIterator>>,
1462
          class _Pred      = equal_to<__iter_key_type<_InputIterator>>,
1463
          class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>,
1464
          class            = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
1465
          class            = enable_if_t<!__is_allocator<_Hash>::value>,
1466
          class            = enable_if_t<!is_integral<_Hash>::value>,
1467
          class            = enable_if_t<!__is_allocator<_Pred>::value>,
1468
          class            = enable_if_t<__is_allocator<_Allocator>::value>>
1469
unordered_map(_InputIterator,
1470
              _InputIterator,
1471
              typename allocator_traits<_Allocator>::size_type = 0,
1472
              _Hash                                            = _Hash(),
1473
              _Pred                                            = _Pred(),
1474
              _Allocator                                       = _Allocator())
1475
    -> unordered_map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Hash, _Pred, _Allocator>;
1476

1477
#  if _LIBCPP_STD_VER >= 23
1478
template <ranges::input_range _Range,
1479
          class _Hash      = hash<__range_key_type<_Range>>,
1480
          class _Pred      = equal_to<__range_key_type<_Range>>,
1481
          class _Allocator = allocator<__range_to_alloc_type<_Range>>,
1482
          class            = enable_if_t<!__is_allocator<_Hash>::value>,
1483
          class            = enable_if_t<!is_integral<_Hash>::value>,
1484
          class            = enable_if_t<!__is_allocator<_Pred>::value>,
1485
          class            = enable_if_t<__is_allocator<_Allocator>::value>>
1486
unordered_map(from_range_t,
1487
              _Range&&,
1488
              typename allocator_traits<_Allocator>::size_type = 0,
1489
              _Hash                                            = _Hash(),
1490
              _Pred                                            = _Pred(),
1491
              _Allocator                                       = _Allocator())
1492
    -> unordered_map<__range_key_type<_Range>, __range_mapped_type<_Range>, _Hash, _Pred, _Allocator>; // C++23
1493
#  endif
1494

1495
template <class _Key,
1496
          class _Tp,
1497
          class _Hash      = hash<remove_const_t<_Key>>,
1498
          class _Pred      = equal_to<remove_const_t<_Key>>,
1499
          class _Allocator = allocator<pair<const _Key, _Tp>>,
1500
          class            = enable_if_t<!__is_allocator<_Hash>::value>,
1501
          class            = enable_if_t<!is_integral<_Hash>::value>,
1502
          class            = enable_if_t<!__is_allocator<_Pred>::value>,
1503
          class            = enable_if_t<__is_allocator<_Allocator>::value>>
1504
unordered_map(initializer_list<pair<_Key, _Tp>>,
1505
              typename allocator_traits<_Allocator>::size_type = 0,
1506
              _Hash                                            = _Hash(),
1507
              _Pred                                            = _Pred(),
1508
              _Allocator = _Allocator()) -> unordered_map<remove_const_t<_Key>, _Tp, _Hash, _Pred, _Allocator>;
1509

1510
template <class _InputIterator,
1511
          class _Allocator,
1512
          class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
1513
          class = enable_if_t<__is_allocator<_Allocator>::value>>
1514
unordered_map(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Allocator)
1515
    -> unordered_map<__iter_key_type<_InputIterator>,
1516
                     __iter_mapped_type<_InputIterator>,
1517
                     hash<__iter_key_type<_InputIterator>>,
1518
                     equal_to<__iter_key_type<_InputIterator>>,
1519
                     _Allocator>;
1520

1521
template <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>>
1525
unordered_map(_InputIterator, _InputIterator, _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

1532
template <class _InputIterator,
1533
          class _Hash,
1534
          class _Allocator,
1535
          class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
1536
          class = enable_if_t<!__is_allocator<_Hash>::value>,
1537
          class = enable_if_t<!is_integral<_Hash>::value>,
1538
          class = enable_if_t<__is_allocator<_Allocator>::value>>
1539
unordered_map(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
1540
    -> unordered_map<__iter_key_type<_InputIterator>,
1541
                     __iter_mapped_type<_InputIterator>,
1542
                     _Hash,
1543
                     equal_to<__iter_key_type<_InputIterator>>,
1544
                     _Allocator>;
1545

1546
#  if _LIBCPP_STD_VER >= 23
1547

1548
template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
1549
unordered_map(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Allocator)
1550
    -> unordered_map<__range_key_type<_Range>,
1551
                     __range_mapped_type<_Range>,
1552
                     hash<__range_key_type<_Range>>,
1553
                     equal_to<__range_key_type<_Range>>,
1554
                     _Allocator>;
1555

1556
template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
1557
unordered_map(from_range_t, _Range&&, _Allocator)
1558
    -> unordered_map<__range_key_type<_Range>,
1559
                     __range_mapped_type<_Range>,
1560
                     hash<__range_key_type<_Range>>,
1561
                     equal_to<__range_key_type<_Range>>,
1562
                     _Allocator>;
1563

1564
template <ranges::input_range _Range,
1565
          class _Hash,
1566
          class _Allocator,
1567
          class = enable_if_t<!__is_allocator<_Hash>::value>,
1568
          class = enable_if_t<!is_integral<_Hash>::value>,
1569
          class = enable_if_t<__is_allocator<_Allocator>::value>>
1570
unordered_map(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
1571
    -> unordered_map<__range_key_type<_Range>,
1572
                     __range_mapped_type<_Range>,
1573
                     _Hash,
1574
                     equal_to<__range_key_type<_Range>>,
1575
                     _Allocator>;
1576

1577
#  endif
1578

1579
template <class _Key, class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
1580
unordered_map(initializer_list<pair<_Key, _Tp>>, typename allocator_traits<_Allocator>::size_type, _Allocator)
1581
    -> unordered_map<remove_const_t<_Key>, _Tp, hash<remove_const_t<_Key>>, equal_to<remove_const_t<_Key>>, _Allocator>;
1582

1583
template <class _Key, class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
1584
unordered_map(initializer_list<pair<_Key, _Tp>>, _Allocator)
1585
    -> unordered_map<remove_const_t<_Key>, _Tp, hash<remove_const_t<_Key>>, equal_to<remove_const_t<_Key>>, _Allocator>;
1586

1587
template <class _Key,
1588
          class _Tp,
1589
          class _Hash,
1590
          class _Allocator,
1591
          class = enable_if_t<!__is_allocator<_Hash>::value>,
1592
          class = enable_if_t<!is_integral<_Hash>::value>,
1593
          class = enable_if_t<__is_allocator<_Allocator>::value>>
1594
unordered_map(initializer_list<pair<_Key, _Tp>>, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
1595
    -> unordered_map<remove_const_t<_Key>, _Tp, _Hash, equal_to<remove_const_t<_Key>>, _Allocator>;
1596
#endif
1597

1598
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1599
unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(size_type __n, const hasher& __hf, const key_equal& __eql)
1600
    : __table_(__hf, __eql) {
1601
  __table_.__rehash_unique(__n);
1602
}
1603

1604
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1605
unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1606
    size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1607
    : __table_(__hf, __eql, typename __table::allocator_type(__a)) {
1608
  __table_.__rehash_unique(__n);
1609
}
1610

1611
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1612
inline unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(const allocator_type& __a)
1613
    : __table_(typename __table::allocator_type(__a)) {}
1614

1615
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1616
template <class _InputIterator>
1617
unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(_InputIterator __first, _InputIterator __last) {
1618
  insert(__first, __last);
1619
}
1620

1621
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1622
template <class _InputIterator>
1623
unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1624
    _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql)
1625
    : __table_(__hf, __eql) {
1626
  __table_.__rehash_unique(__n);
1627
  insert(__first, __last);
1628
}
1629

1630
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1631
template <class _InputIterator>
1632
unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1633
    _InputIterator __first,
1634
    _InputIterator __last,
1635
    size_type __n,
1636
    const hasher& __hf,
1637
    const key_equal& __eql,
1638
    const allocator_type& __a)
1639
    : __table_(__hf, __eql, typename __table::allocator_type(__a)) {
1640
  __table_.__rehash_unique(__n);
1641
  insert(__first, __last);
1642
}
1643

1644
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1645
unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(const unordered_map& __u) : __table_(__u.__table_) {
1646
  __table_.__rehash_unique(__u.bucket_count());
1647
  insert(__u.begin(), __u.end());
1648
}
1649

1650
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1651
unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(const unordered_map& __u, const allocator_type& __a)
1652
    : __table_(__u.__table_, typename __table::allocator_type(__a)) {
1653
  __table_.__rehash_unique(__u.bucket_count());
1654
  insert(__u.begin(), __u.end());
1655
}
1656

1657
#ifndef _LIBCPP_CXX03_LANG
1658

1659
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1660
inline unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(unordered_map&& __u)
1661
    _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
1662
    : __table_(std::move(__u.__table_)) {}
1663

1664
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1665
unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(unordered_map&& __u, const allocator_type& __a)
1666
    : __table_(std::move(__u.__table_), typename __table::allocator_type(__a)) {
1667
  if (__a != __u.get_allocator()) {
1668
    iterator __i = __u.begin();
1669
    while (__u.size() != 0) {
1670
      __table_.__emplace_unique(__u.__table_.remove((__i++).__i_)->__get_value().__move());
1671
    }
1672
  }
1673
}
1674

1675
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1676
unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(initializer_list<value_type> __il) {
1677
  insert(__il.begin(), __il.end());
1678
}
1679

1680
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1681
unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1682
    initializer_list<value_type> __il, size_type __n, const hasher& __hf, const key_equal& __eql)
1683
    : __table_(__hf, __eql) {
1684
  __table_.__rehash_unique(__n);
1685
  insert(__il.begin(), __il.end());
1686
}
1687

1688
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1689
unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1690
    initializer_list<value_type> __il,
1691
    size_type __n,
1692
    const hasher& __hf,
1693
    const key_equal& __eql,
1694
    const allocator_type& __a)
1695
    : __table_(__hf, __eql, typename __table::allocator_type(__a)) {
1696
  __table_.__rehash_unique(__n);
1697
  insert(__il.begin(), __il.end());
1698
}
1699

1700
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1701
inline unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
1702
unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_map&& __u)
1703
    _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) {
1704
  __table_ = std::move(__u.__table_);
1705
  return *this;
1706
}
1707

1708
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1709
inline unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
1710
unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(initializer_list<value_type> __il) {
1711
  __table_.__assign_unique(__il.begin(), __il.end());
1712
  return *this;
1713
}
1714

1715
#endif // _LIBCPP_CXX03_LANG
1716

1717
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1718
template <class _InputIterator>
1719
inline void unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) {
1720
  for (; __first != __last; ++__first)
1721
    __table_.__insert_unique(*__first);
1722
}
1723

1724
#ifndef _LIBCPP_CXX03_LANG
1725

1726
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1727
_Tp& unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k) {
1728
  return __table_
1729
      .__emplace_unique_key_args(__k, piecewise_construct, std::forward_as_tuple(__k), std::forward_as_tuple())
1730
      .first->__get_value()
1731
      .second;
1732
}
1733

1734
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1735
_Tp& unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&& __k) {
1736
  return __table_
1737
      .__emplace_unique_key_args(
1738
          __k, piecewise_construct, std::forward_as_tuple(std::move(__k)), std::forward_as_tuple())
1739
      .first->__get_value()
1740
      .second;
1741
}
1742
#else // _LIBCPP_CXX03_LANG
1743

1744
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1745
typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1746
unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(const key_type& __k) {
1747
  __node_allocator& __na = __table_.__node_alloc();
1748
  __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1749
  __node_traits::construct(__na, std::addressof(__h->__get_value().__get_value().first), __k);
1750
  __h.get_deleter().__first_constructed = true;
1751
  __node_traits::construct(__na, std::addressof(__h->__get_value().__get_value().second));
1752
  __h.get_deleter().__second_constructed = true;
1753
  return __h;
1754
}
1755

1756
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1757
_Tp& unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k) {
1758
  iterator __i = find(__k);
1759
  if (__i != end())
1760
    return __i->second;
1761
  __node_holder __h        = __construct_node_with_key(__k);
1762
  pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1763
  __h.release();
1764
  return __r.first->second;
1765
}
1766

1767
#endif // _LIBCPP_CXX03_LANG
1768

1769
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1770
_Tp& unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) {
1771
  iterator __i = find(__k);
1772
  if (__i == end())
1773
    __throw_out_of_range("unordered_map::at: key not found");
1774
  return __i->second;
1775
}
1776

1777
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1778
const _Tp& unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) const {
1779
  const_iterator __i = find(__k);
1780
  if (__i == end())
1781
    __throw_out_of_range("unordered_map::at: key not found");
1782
  return __i->second;
1783
}
1784

1785
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1786
inline _LIBCPP_HIDE_FROM_ABI void
1787
swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1788
    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
1789
  __x.swap(__y);
1790
}
1791

1792
#if _LIBCPP_STD_VER >= 20
1793
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc, class _Predicate>
1794
inline _LIBCPP_HIDE_FROM_ABI typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::size_type
1795
erase_if(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __c, _Predicate __pred) {
1796
  return std::__libcpp_erase_if_container(__c, __pred);
1797
}
1798
#endif
1799

1800
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1801
_LIBCPP_HIDE_FROM_ABI bool operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1802
                                      const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) {
1803
  if (__x.size() != __y.size())
1804
    return false;
1805
  typedef typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator const_iterator;
1806
  for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); __i != __ex; ++__i) {
1807
    const_iterator __j = __y.find(__i->first);
1808
    if (__j == __ey || !(*__i == *__j))
1809
      return false;
1810
  }
1811
  return true;
1812
}
1813

1814
#if _LIBCPP_STD_VER <= 17
1815

1816
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1817
inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1818
                                             const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) {
1819
  return !(__x == __y);
1820
}
1821

1822
#endif
1823

1824
template <class _Key,
1825
          class _Tp,
1826
          class _Hash  = hash<_Key>,
1827
          class _Pred  = equal_to<_Key>,
1828
          class _Alloc = allocator<pair<const _Key, _Tp> > >
1829
class _LIBCPP_TEMPLATE_VIS unordered_multimap {
1830
public:
1831
  // types
1832
  typedef _Key key_type;
1833
  typedef _Tp mapped_type;
1834
  typedef __type_identity_t<_Hash> hasher;
1835
  typedef __type_identity_t<_Pred> key_equal;
1836
  typedef __type_identity_t<_Alloc> allocator_type;
1837
  typedef pair<const key_type, mapped_type> value_type;
1838
  typedef value_type& reference;
1839
  typedef const value_type& const_reference;
1840
  static_assert(__check_valid_allocator<allocator_type>::value, "");
1841
  static_assert(is_same<value_type, typename allocator_type::value_type>::value,
1842
                "Allocator::value_type must be same type as value_type");
1843

1844
private:
1845
  typedef __hash_value_type<key_type, mapped_type> __value_type;
1846
  typedef __unordered_map_hasher<key_type, __value_type, hasher, key_equal> __hasher;
1847
  typedef __unordered_map_equal<key_type, __value_type, key_equal, hasher> __key_equal;
1848
  typedef __rebind_alloc<allocator_traits<allocator_type>, __value_type> __allocator_type;
1849

1850
  typedef __hash_table<__value_type, __hasher, __key_equal, __allocator_type> __table;
1851

1852
  __table __table_;
1853

1854
  typedef typename __table::_NodeTypes _NodeTypes;
1855
  typedef typename __table::__node_traits __node_traits;
1856
  typedef typename __table::__node_allocator __node_allocator;
1857
  typedef typename __table::__node __node;
1858
  typedef __hash_map_node_destructor<__node_allocator> _Dp;
1859
  typedef unique_ptr<__node, _Dp> __node_holder;
1860
  typedef allocator_traits<allocator_type> __alloc_traits;
1861
  static_assert(is_same<typename __node_traits::size_type, typename __alloc_traits::size_type>::value,
1862
                "Allocator uses different size_type for different types");
1863

1864
public:
1865
  typedef typename __alloc_traits::pointer pointer;
1866
  typedef typename __alloc_traits::const_pointer const_pointer;
1867
  typedef typename __table::size_type size_type;
1868
  typedef typename __table::difference_type difference_type;
1869

1870
  typedef __hash_map_iterator<typename __table::iterator> iterator;
1871
  typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
1872
  typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
1873
  typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
1874

1875
#if _LIBCPP_STD_VER >= 17
1876
  typedef __map_node_handle<__node, allocator_type> node_type;
1877
#endif
1878

1879
  template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2>
1880
  friend class _LIBCPP_TEMPLATE_VIS unordered_map;
1881
  template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2>
1882
  friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
1883

1884
  _LIBCPP_HIDE_FROM_ABI unordered_multimap() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) {}
1885
  explicit _LIBCPP_HIDE_FROM_ABI
1886
  unordered_multimap(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
1887
  _LIBCPP_HIDE_FROM_ABI
1888
  unordered_multimap(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a);
1889
  template <class _InputIterator>
1890
  _LIBCPP_HIDE_FROM_ABI unordered_multimap(_InputIterator __first, _InputIterator __last);
1891
  template <class _InputIterator>
1892
  _LIBCPP_HIDE_FROM_ABI unordered_multimap(
1893
      _InputIterator __first,
1894
      _InputIterator __last,
1895
      size_type __n,
1896
      const hasher& __hf     = hasher(),
1897
      const key_equal& __eql = key_equal());
1898
  template <class _InputIterator>
1899
  _LIBCPP_HIDE_FROM_ABI unordered_multimap(
1900
      _InputIterator __first,
1901
      _InputIterator __last,
1902
      size_type __n,
1903
      const hasher& __hf,
1904
      const key_equal& __eql,
1905
      const allocator_type& __a);
1906

1907
#if _LIBCPP_STD_VER >= 23
1908
  template <_ContainerCompatibleRange<value_type> _Range>
1909
  _LIBCPP_HIDE_FROM_ABI unordered_multimap(
1910
      from_range_t,
1911
      _Range&& __range,
1912
      size_type __n             = /*implementation-defined*/ 0,
1913
      const hasher& __hf        = hasher(),
1914
      const key_equal& __eql    = key_equal(),
1915
      const allocator_type& __a = allocator_type())
1916
      : __table_(__hf, __eql, typename __table::allocator_type(__a)) {
1917
    if (__n > 0) {
1918
      __table_.__rehash_multi(__n);
1919
    }
1920
    insert_range(std::forward<_Range>(__range));
1921
  }
1922
#endif
1923

1924
  _LIBCPP_HIDE_FROM_ABI explicit unordered_multimap(const allocator_type& __a);
1925
  _LIBCPP_HIDE_FROM_ABI unordered_multimap(const unordered_multimap& __u);
1926
  _LIBCPP_HIDE_FROM_ABI unordered_multimap(const unordered_multimap& __u, const allocator_type& __a);
1927
#ifndef _LIBCPP_CXX03_LANG
1928
  _LIBCPP_HIDE_FROM_ABI unordered_multimap(unordered_multimap&& __u)
1929
      _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
1930
  _LIBCPP_HIDE_FROM_ABI unordered_multimap(unordered_multimap&& __u, const allocator_type& __a);
1931
  _LIBCPP_HIDE_FROM_ABI unordered_multimap(initializer_list<value_type> __il);
1932
  _LIBCPP_HIDE_FROM_ABI unordered_multimap(
1933
      initializer_list<value_type> __il,
1934
      size_type __n,
1935
      const hasher& __hf     = hasher(),
1936
      const key_equal& __eql = key_equal());
1937
  _LIBCPP_HIDE_FROM_ABI unordered_multimap(
1938
      initializer_list<value_type> __il,
1939
      size_type __n,
1940
      const hasher& __hf,
1941
      const key_equal& __eql,
1942
      const allocator_type& __a);
1943
#endif // _LIBCPP_CXX03_LANG
1944
#if _LIBCPP_STD_VER >= 14
1945
  _LIBCPP_HIDE_FROM_ABI unordered_multimap(size_type __n, const allocator_type& __a)
1946
      : unordered_multimap(__n, hasher(), key_equal(), __a) {}
1947
  _LIBCPP_HIDE_FROM_ABI unordered_multimap(size_type __n, const hasher& __hf, const allocator_type& __a)
1948
      : unordered_multimap(__n, __hf, key_equal(), __a) {}
1949
  template <class _InputIterator>
1950
  _LIBCPP_HIDE_FROM_ABI
1951
  unordered_multimap(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a)
1952
      : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a) {}
1953
  template <class _InputIterator>
1954
  _LIBCPP_HIDE_FROM_ABI unordered_multimap(
1955
      _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const allocator_type& __a)
1956
      : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a) {}
1957

1958
#  if _LIBCPP_STD_VER >= 23
1959
  template <_ContainerCompatibleRange<value_type> _Range>
1960
  _LIBCPP_HIDE_FROM_ABI unordered_multimap(from_range_t, _Range&& __range, size_type __n, const allocator_type& __a)
1961
      : unordered_multimap(from_range, std::forward<_Range>(__range), __n, hasher(), key_equal(), __a) {}
1962

1963
  template <_ContainerCompatibleRange<value_type> _Range>
1964
  _LIBCPP_HIDE_FROM_ABI
1965
  unordered_multimap(from_range_t, _Range&& __range, size_type __n, const hasher& __hf, const allocator_type& __a)
1966
      : unordered_multimap(from_range, std::forward<_Range>(__range), __n, __hf, key_equal(), __a) {}
1967
#  endif
1968

1969
  _LIBCPP_HIDE_FROM_ABI unordered_multimap(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)
1970
      : unordered_multimap(__il, __n, hasher(), key_equal(), __a) {}
1971
  _LIBCPP_HIDE_FROM_ABI
1972
  unordered_multimap(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a)
1973
      : unordered_multimap(__il, __n, __hf, key_equal(), __a) {}
1974
#endif
1975
  _LIBCPP_HIDE_FROM_ABI ~unordered_multimap() {
1976
    static_assert(sizeof(std::__diagnose_unordered_container_requirements<_Key, _Hash, _Pred>(0)), "");
1977
  }
1978

1979
  _LIBCPP_HIDE_FROM_ABI unordered_multimap& operator=(const unordered_multimap& __u) {
1980
#ifndef _LIBCPP_CXX03_LANG
1981
    __table_ = __u.__table_;
1982
#else
1983
    if (this != std::addressof(__u)) {
1984
      __table_.clear();
1985
      __table_.hash_function()   = __u.__table_.hash_function();
1986
      __table_.key_eq()          = __u.__table_.key_eq();
1987
      __table_.max_load_factor() = __u.__table_.max_load_factor();
1988
      __table_.__copy_assign_alloc(__u.__table_);
1989
      insert(__u.begin(), __u.end());
1990
    }
1991
#endif
1992
    return *this;
1993
  }
1994
#ifndef _LIBCPP_CXX03_LANG
1995
  _LIBCPP_HIDE_FROM_ABI unordered_multimap& operator=(unordered_multimap&& __u)
1996
      _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
1997
  _LIBCPP_HIDE_FROM_ABI unordered_multimap& operator=(initializer_list<value_type> __il);
1998
#endif // _LIBCPP_CXX03_LANG
1999

2000
  _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT {
2001
    return allocator_type(__table_.__node_alloc());
2002
  }
2003

2004
  _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __table_.size() == 0; }
2005
  _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __table_.size(); }
2006
  _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __table_.max_size(); }
2007

2008
  _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __table_.begin(); }
2009
  _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __table_.end(); }
2010
  _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __table_.begin(); }
2011
  _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __table_.end(); }
2012
  _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return __table_.begin(); }
2013
  _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return __table_.end(); }
2014

2015
  _LIBCPP_HIDE_FROM_ABI iterator insert(const value_type& __x) { return __table_.__insert_multi(__x); }
2016

2017
  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __x) {
2018
    return __table_.__insert_multi(__p.__i_, __x);
2019
  }
2020

2021
  template <class _InputIterator>
2022
  _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last);
2023

2024
#if _LIBCPP_STD_VER >= 23
2025
  template <_ContainerCompatibleRange<value_type> _Range>
2026
  _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) {
2027
    for (auto&& __element : __range) {
2028
      __table_.__insert_multi(std::forward<decltype(__element)>(__element));
2029
    }
2030
  }
2031
#endif
2032

2033
#ifndef _LIBCPP_CXX03_LANG
2034
  _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); }
2035
  _LIBCPP_HIDE_FROM_ABI iterator insert(value_type&& __x) { return __table_.__insert_multi(std::move(__x)); }
2036

2037
  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __x) {
2038
    return __table_.__insert_multi(__p.__i_, std::move(__x));
2039
  }
2040

2041
  template <class _Pp, __enable_if_t<is_constructible<value_type, _Pp>::value, int> = 0>
2042
  _LIBCPP_HIDE_FROM_ABI iterator insert(_Pp&& __x) {
2043
    return __table_.__insert_multi(std::forward<_Pp>(__x));
2044
  }
2045

2046
  template <class _Pp, __enable_if_t<is_constructible<value_type, _Pp>::value, int> = 0>
2047
  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, _Pp&& __x) {
2048
    return __table_.__insert_multi(__p.__i_, std::forward<_Pp>(__x));
2049
  }
2050

2051
  template <class... _Args>
2052
  _LIBCPP_HIDE_FROM_ABI iterator emplace(_Args&&... __args) {
2053
    return __table_.__emplace_multi(std::forward<_Args>(__args)...);
2054
  }
2055

2056
  template <class... _Args>
2057
  _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __p, _Args&&... __args) {
2058
    return __table_.__emplace_hint_multi(__p.__i_, std::forward<_Args>(__args)...);
2059
  }
2060
#endif // _LIBCPP_CXX03_LANG
2061

2062
  _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __table_.erase(__p.__i_); }
2063
  _LIBCPP_HIDE_FROM_ABI iterator erase(iterator __p) { return __table_.erase(__p.__i_); }
2064
  _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_multi(__k); }
2065
  _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last) {
2066
    return __table_.erase(__first.__i_, __last.__i_);
2067
  }
2068
  _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __table_.clear(); }
2069

2070
#if _LIBCPP_STD_VER >= 17
2071
  _LIBCPP_HIDE_FROM_ABI iterator insert(node_type&& __nh) {
2072
    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
2073
                                        "node_type with incompatible allocator passed to unordered_multimap::insert()");
2074
    return __table_.template __node_handle_insert_multi<node_type>(std::move(__nh));
2075
  }
2076
  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, node_type&& __nh) {
2077
    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
2078
                                        "node_type with incompatible allocator passed to unordered_multimap::insert()");
2079
    return __table_.template __node_handle_insert_multi<node_type>(__hint.__i_, std::move(__nh));
2080
  }
2081
  _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) {
2082
    return __table_.template __node_handle_extract<node_type>(__key);
2083
  }
2084
  _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __it) {
2085
    return __table_.template __node_handle_extract<node_type>(__it.__i_);
2086
  }
2087

2088
  template <class _H2, class _P2>
2089
  _LIBCPP_HIDE_FROM_ABI void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>& __source) {
2090
    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
2091
        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
2092
    return __table_.__node_handle_merge_multi(__source.__table_);
2093
  }
2094
  template <class _H2, class _P2>
2095
  _LIBCPP_HIDE_FROM_ABI void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>&& __source) {
2096
    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
2097
        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
2098
    return __table_.__node_handle_merge_multi(__source.__table_);
2099
  }
2100
  template <class _H2, class _P2>
2101
  _LIBCPP_HIDE_FROM_ABI void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>& __source) {
2102
    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
2103
        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
2104
    return __table_.__node_handle_merge_multi(__source.__table_);
2105
  }
2106
  template <class _H2, class _P2>
2107
  _LIBCPP_HIDE_FROM_ABI void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>&& __source) {
2108
    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
2109
        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
2110
    return __table_.__node_handle_merge_multi(__source.__table_);
2111
  }
2112
#endif
2113

2114
  _LIBCPP_HIDE_FROM_ABI void swap(unordered_multimap& __u) _NOEXCEPT_(__is_nothrow_swappable_v<__table>) {
2115
    __table_.swap(__u.__table_);
2116
  }
2117

2118
  _LIBCPP_HIDE_FROM_ABI hasher hash_function() const { return __table_.hash_function().hash_function(); }
2119
  _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq().key_eq(); }
2120

2121
  _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); }
2122
  _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); }
2123
#if _LIBCPP_STD_VER >= 20
2124
  template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
2125
  _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) {
2126
    return __table_.find(__k);
2127
  }
2128
  template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
2129
  _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const {
2130
    return __table_.find(__k);
2131
  }
2132
#endif // _LIBCPP_STD_VER >= 20
2133

2134
  _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_multi(__k); }
2135
#if _LIBCPP_STD_VER >= 20
2136
  template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
2137
  _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const {
2138
    return __table_.__count_multi(__k);
2139
  }
2140
#endif // _LIBCPP_STD_VER >= 20
2141

2142
#if _LIBCPP_STD_VER >= 20
2143
  _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); }
2144

2145
  template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
2146
  _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const {
2147
    return find(__k) != end();
2148
  }
2149
#endif // _LIBCPP_STD_VER >= 20
2150

2151
  _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {
2152
    return __table_.__equal_range_multi(__k);
2153
  }
2154
  _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
2155
    return __table_.__equal_range_multi(__k);
2156
  }
2157
#if _LIBCPP_STD_VER >= 20
2158
  template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
2159
  _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) {
2160
    return __table_.__equal_range_multi(__k);
2161
  }
2162
  template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
2163
  _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const {
2164
    return __table_.__equal_range_multi(__k);
2165
  }
2166
#endif // _LIBCPP_STD_VER >= 20
2167

2168
  _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const _NOEXCEPT { return __table_.bucket_count(); }
2169
  _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const _NOEXCEPT { return __table_.max_bucket_count(); }
2170

2171
  _LIBCPP_HIDE_FROM_ABI size_type bucket_size(size_type __n) const { return __table_.bucket_size(__n); }
2172
  _LIBCPP_HIDE_FROM_ABI size_type bucket(const key_type& __k) const { return __table_.bucket(__k); }
2173

2174
  _LIBCPP_HIDE_FROM_ABI local_iterator begin(size_type __n) { return __table_.begin(__n); }
2175
  _LIBCPP_HIDE_FROM_ABI local_iterator end(size_type __n) { return __table_.end(__n); }
2176
  _LIBCPP_HIDE_FROM_ABI const_local_iterator begin(size_type __n) const { return __table_.cbegin(__n); }
2177
  _LIBCPP_HIDE_FROM_ABI const_local_iterator end(size_type __n) const { return __table_.cend(__n); }
2178
  _LIBCPP_HIDE_FROM_ABI const_local_iterator cbegin(size_type __n) const { return __table_.cbegin(__n); }
2179
  _LIBCPP_HIDE_FROM_ABI const_local_iterator cend(size_type __n) const { return __table_.cend(__n); }
2180

2181
  _LIBCPP_HIDE_FROM_ABI float load_factor() const _NOEXCEPT { return __table_.load_factor(); }
2182
  _LIBCPP_HIDE_FROM_ABI float max_load_factor() const _NOEXCEPT { return __table_.max_load_factor(); }
2183
  _LIBCPP_HIDE_FROM_ABI void max_load_factor(float __mlf) { __table_.max_load_factor(__mlf); }
2184
  _LIBCPP_HIDE_FROM_ABI void rehash(size_type __n) { __table_.__rehash_multi(__n); }
2185
  _LIBCPP_HIDE_FROM_ABI void reserve(size_type __n) { __table_.__reserve_multi(__n); }
2186
};
2187

2188
#if _LIBCPP_STD_VER >= 17
2189
template <class _InputIterator,
2190
          class _Hash      = hash<__iter_key_type<_InputIterator>>,
2191
          class _Pred      = equal_to<__iter_key_type<_InputIterator>>,
2192
          class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>,
2193
          class            = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
2194
          class            = enable_if_t<!__is_allocator<_Hash>::value>,
2195
          class            = enable_if_t<!is_integral<_Hash>::value>,
2196
          class            = enable_if_t<!__is_allocator<_Pred>::value>,
2197
          class            = enable_if_t<__is_allocator<_Allocator>::value>>
2198
unordered_multimap(_InputIterator,
2199
                   _InputIterator,
2200
                   typename allocator_traits<_Allocator>::size_type = 0,
2201
                   _Hash                                            = _Hash(),
2202
                   _Pred                                            = _Pred(),
2203
                   _Allocator                                       = _Allocator())
2204
    -> unordered_multimap<__iter_key_type<_InputIterator>,
2205
                          __iter_mapped_type<_InputIterator>,
2206
                          _Hash,
2207
                          _Pred,
2208
                          _Allocator>;
2209

2210
#  if _LIBCPP_STD_VER >= 23
2211
template <ranges::input_range _Range,
2212
          class _Hash      = hash<__range_key_type<_Range>>,
2213
          class _Pred      = equal_to<__range_key_type<_Range>>,
2214
          class _Allocator = allocator<__range_to_alloc_type<_Range>>,
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>>
2219
unordered_multimap(from_range_t,
2220
                   _Range&&,
2221
                   typename allocator_traits<_Allocator>::size_type = 0,
2222
                   _Hash                                            = _Hash(),
2223
                   _Pred                                            = _Pred(),
2224
                   _Allocator                                       = _Allocator())
2225
    -> unordered_multimap<__range_key_type<_Range>, __range_mapped_type<_Range>, _Hash, _Pred, _Allocator>;
2226
#  endif
2227

2228
template <class _Key,
2229
          class _Tp,
2230
          class _Hash      = hash<remove_const_t<_Key>>,
2231
          class _Pred      = equal_to<remove_const_t<_Key>>,
2232
          class _Allocator = allocator<pair<const _Key, _Tp>>,
2233
          class            = enable_if_t<!__is_allocator<_Hash>::value>,
2234
          class            = enable_if_t<!is_integral<_Hash>::value>,
2235
          class            = enable_if_t<!__is_allocator<_Pred>::value>,
2236
          class            = enable_if_t<__is_allocator<_Allocator>::value>>
2237
unordered_multimap(
2238
    initializer_list<pair<_Key, _Tp>>,
2239
    typename allocator_traits<_Allocator>::size_type = 0,
2240
    _Hash                                            = _Hash(),
2241
    _Pred                                            = _Pred(),
2242
    _Allocator = _Allocator()) -> unordered_multimap<remove_const_t<_Key>, _Tp, _Hash, _Pred, _Allocator>;
2243

2244
template <class _InputIterator,
2245
          class _Allocator,
2246
          class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
2247
          class = enable_if_t<__is_allocator<_Allocator>::value>>
2248
unordered_multimap(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Allocator)
2249
    -> unordered_multimap<__iter_key_type<_InputIterator>,
2250
                          __iter_mapped_type<_InputIterator>,
2251
                          hash<__iter_key_type<_InputIterator>>,
2252
                          equal_to<__iter_key_type<_InputIterator>>,
2253
                          _Allocator>;
2254

2255
template <class _InputIterator,
2256
          class _Allocator,
2257
          class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
2258
          class = enable_if_t<__is_allocator<_Allocator>::value>>
2259
unordered_multimap(_InputIterator, _InputIterator, _Allocator)
2260
    -> unordered_multimap<__iter_key_type<_InputIterator>,
2261
                          __iter_mapped_type<_InputIterator>,
2262
                          hash<__iter_key_type<_InputIterator>>,
2263
                          equal_to<__iter_key_type<_InputIterator>>,
2264
                          _Allocator>;
2265

2266
template <class _InputIterator,
2267
          class _Hash,
2268
          class _Allocator,
2269
          class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
2270
          class = enable_if_t<!__is_allocator<_Hash>::value>,
2271
          class = enable_if_t<!is_integral<_Hash>::value>,
2272
          class = enable_if_t<__is_allocator<_Allocator>::value>>
2273
unordered_multimap(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
2274
    -> unordered_multimap<__iter_key_type<_InputIterator>,
2275
                          __iter_mapped_type<_InputIterator>,
2276
                          _Hash,
2277
                          equal_to<__iter_key_type<_InputIterator>>,
2278
                          _Allocator>;
2279

2280
#  if _LIBCPP_STD_VER >= 23
2281

2282
template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
2283
unordered_multimap(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Allocator)
2284
    -> unordered_multimap<__range_key_type<_Range>,
2285
                          __range_mapped_type<_Range>,
2286
                          hash<__range_key_type<_Range>>,
2287
                          equal_to<__range_key_type<_Range>>,
2288
                          _Allocator>;
2289

2290
template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
2291
unordered_multimap(from_range_t, _Range&&, _Allocator)
2292
    -> unordered_multimap<__range_key_type<_Range>,
2293
                          __range_mapped_type<_Range>,
2294
                          hash<__range_key_type<_Range>>,
2295
                          equal_to<__range_key_type<_Range>>,
2296
                          _Allocator>;
2297

2298
template <ranges::input_range _Range,
2299
          class _Hash,
2300
          class _Allocator,
2301
          class = enable_if_t<!__is_allocator<_Hash>::value>,
2302
          class = enable_if_t<!is_integral<_Hash>::value>,
2303
          class = enable_if_t<__is_allocator<_Allocator>::value>>
2304
unordered_multimap(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
2305
    -> unordered_multimap<__range_key_type<_Range>,
2306
                          __range_mapped_type<_Range>,
2307
                          _Hash,
2308
                          equal_to<__range_key_type<_Range>>,
2309
                          _Allocator>;
2310

2311
#  endif
2312

2313
template <class _Key, class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
2314
unordered_multimap(initializer_list<pair<_Key, _Tp>>, typename allocator_traits<_Allocator>::size_type, _Allocator)
2315
    -> unordered_multimap<remove_const_t<_Key>,
2316
                          _Tp,
2317
                          hash<remove_const_t<_Key>>,
2318
                          equal_to<remove_const_t<_Key>>,
2319
                          _Allocator>;
2320

2321
template <class _Key, class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
2322
unordered_multimap(initializer_list<pair<_Key, _Tp>>, _Allocator)
2323
    -> unordered_multimap<remove_const_t<_Key>,
2324
                          _Tp,
2325
                          hash<remove_const_t<_Key>>,
2326
                          equal_to<remove_const_t<_Key>>,
2327
                          _Allocator>;
2328

2329
template <class _Key,
2330
          class _Tp,
2331
          class _Hash,
2332
          class _Allocator,
2333
          class = enable_if_t<!__is_allocator<_Hash>::value>,
2334
          class = enable_if_t<!is_integral<_Hash>::value>,
2335
          class = enable_if_t<__is_allocator<_Allocator>::value>>
2336
unordered_multimap(
2337
    initializer_list<pair<_Key, _Tp>>, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
2338
    -> unordered_multimap<remove_const_t<_Key>, _Tp, _Hash, equal_to<remove_const_t<_Key>>, _Allocator>;
2339
#endif
2340

2341
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2342
unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2343
    size_type __n, const hasher& __hf, const key_equal& __eql)
2344
    : __table_(__hf, __eql) {
2345
  __table_.__rehash_multi(__n);
2346
}
2347

2348
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2349
unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2350
    size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
2351
    : __table_(__hf, __eql, typename __table::allocator_type(__a)) {
2352
  __table_.__rehash_multi(__n);
2353
}
2354

2355
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2356
template <class _InputIterator>
2357
unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(_InputIterator __first, _InputIterator __last) {
2358
  insert(__first, __last);
2359
}
2360

2361
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2362
template <class _InputIterator>
2363
unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2364
    _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql)
2365
    : __table_(__hf, __eql) {
2366
  __table_.__rehash_multi(__n);
2367
  insert(__first, __last);
2368
}
2369

2370
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2371
template <class _InputIterator>
2372
unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2373
    _InputIterator __first,
2374
    _InputIterator __last,
2375
    size_type __n,
2376
    const hasher& __hf,
2377
    const key_equal& __eql,
2378
    const allocator_type& __a)
2379
    : __table_(__hf, __eql, typename __table::allocator_type(__a)) {
2380
  __table_.__rehash_multi(__n);
2381
  insert(__first, __last);
2382
}
2383

2384
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2385
inline unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(const allocator_type& __a)
2386
    : __table_(typename __table::allocator_type(__a)) {}
2387

2388
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2389
unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(const unordered_multimap& __u)
2390
    : __table_(__u.__table_) {
2391
  __table_.__rehash_multi(__u.bucket_count());
2392
  insert(__u.begin(), __u.end());
2393
}
2394

2395
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2396
unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2397
    const unordered_multimap& __u, const allocator_type& __a)
2398
    : __table_(__u.__table_, typename __table::allocator_type(__a)) {
2399
  __table_.__rehash_multi(__u.bucket_count());
2400
  insert(__u.begin(), __u.end());
2401
}
2402

2403
#ifndef _LIBCPP_CXX03_LANG
2404

2405
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2406
inline unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(unordered_multimap&& __u)
2407
    _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
2408
    : __table_(std::move(__u.__table_)) {}
2409

2410
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2411
unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2412
    unordered_multimap&& __u, const allocator_type& __a)
2413
    : __table_(std::move(__u.__table_), typename __table::allocator_type(__a)) {
2414
  if (__a != __u.get_allocator()) {
2415
    iterator __i = __u.begin();
2416
    while (__u.size() != 0) {
2417
      __table_.__insert_multi(__u.__table_.remove((__i++).__i_)->__get_value().__move());
2418
    }
2419
  }
2420
}
2421

2422
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2423
unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(initializer_list<value_type> __il) {
2424
  insert(__il.begin(), __il.end());
2425
}
2426

2427
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2428
unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2429
    initializer_list<value_type> __il, size_type __n, const hasher& __hf, const key_equal& __eql)
2430
    : __table_(__hf, __eql) {
2431
  __table_.__rehash_multi(__n);
2432
  insert(__il.begin(), __il.end());
2433
}
2434

2435
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2436
unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2437
    initializer_list<value_type> __il,
2438
    size_type __n,
2439
    const hasher& __hf,
2440
    const key_equal& __eql,
2441
    const allocator_type& __a)
2442
    : __table_(__hf, __eql, typename __table::allocator_type(__a)) {
2443
  __table_.__rehash_multi(__n);
2444
  insert(__il.begin(), __il.end());
2445
}
2446

2447
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2448
inline unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
2449
unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_multimap&& __u)
2450
    _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) {
2451
  __table_ = std::move(__u.__table_);
2452
  return *this;
2453
}
2454

2455
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2456
inline unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
2457
unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(initializer_list<value_type> __il) {
2458
  __table_.__assign_multi(__il.begin(), __il.end());
2459
  return *this;
2460
}
2461

2462
#endif // _LIBCPP_CXX03_LANG
2463

2464
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2465
template <class _InputIterator>
2466
inline void unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) {
2467
  for (; __first != __last; ++__first)
2468
    __table_.__insert_multi(*__first);
2469
}
2470

2471
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2472
inline _LIBCPP_HIDE_FROM_ABI void
2473
swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2474
    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
2475
  __x.swap(__y);
2476
}
2477

2478
#if _LIBCPP_STD_VER >= 20
2479
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc, class _Predicate>
2480
inline _LIBCPP_HIDE_FROM_ABI typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::size_type
2481
erase_if(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __c, _Predicate __pred) {
2482
  return std::__libcpp_erase_if_container(__c, __pred);
2483
}
2484
#endif
2485

2486
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2487
_LIBCPP_HIDE_FROM_ABI bool operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2488
                                      const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) {
2489
  if (__x.size() != __y.size())
2490
    return false;
2491
  typedef typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator const_iterator;
2492
  typedef pair<const_iterator, const_iterator> _EqRng;
2493
  for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) {
2494
    _EqRng __xeq = __x.equal_range(__i->first);
2495
    _EqRng __yeq = __y.equal_range(__i->first);
2496
    if (std::distance(__xeq.first, __xeq.second) != std::distance(__yeq.first, __yeq.second) ||
2497
        !std::is_permutation(__xeq.first, __xeq.second, __yeq.first))
2498
      return false;
2499
    __i = __xeq.second;
2500
  }
2501
  return true;
2502
}
2503

2504
#if _LIBCPP_STD_VER <= 17
2505

2506
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2507
inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2508
                                             const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) {
2509
  return !(__x == __y);
2510
}
2511

2512
#endif
2513

2514
_LIBCPP_END_NAMESPACE_STD
2515

2516
#if _LIBCPP_STD_VER >= 17
2517
_LIBCPP_BEGIN_NAMESPACE_STD
2518
namespace pmr {
2519
template <class _KeyT, class _ValueT, class _HashT = std::hash<_KeyT>, class _PredT = std::equal_to<_KeyT>>
2520
using unordered_map _LIBCPP_AVAILABILITY_PMR =
2521
    std::unordered_map<_KeyT, _ValueT, _HashT, _PredT, polymorphic_allocator<std::pair<const _KeyT, _ValueT>>>;
2522

2523
template <class _KeyT, class _ValueT, class _HashT = std::hash<_KeyT>, class _PredT = std::equal_to<_KeyT>>
2524
using unordered_multimap _LIBCPP_AVAILABILITY_PMR =
2525
    std::unordered_multimap<_KeyT, _ValueT, _HashT, _PredT, polymorphic_allocator<std::pair<const _KeyT, _ValueT>>>;
2526
} // namespace pmr
2527
_LIBCPP_END_NAMESPACE_STD
2528
#endif
2529

2530
_LIBCPP_POP_MACROS
2531

2532
#if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
2533
#  include <algorithm>
2534
#  include <bit>
2535
#  include <concepts>
2536
#  include <cstdlib>
2537
#  include <iterator>
2538
#  include <type_traits>
2539
#endif
2540

2541
#endif // _LIBCPP_UNORDERED_MAP
2542