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