contrib/llvm-project/libcxx/include/unordered_map

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