contrib/libc++/include/unordered_map

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