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