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