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