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