libcxx/include/unordered_map

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