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     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.__get_value().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.__get_value().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.__get_value().first, __y.__get_value().first);}
 468     _LIBCPP_INLINE_VISIBILITY
 469     bool operator()(const _Cp& __x, const _Key& __y) const
 470         {return static_cast<const _Pred&>(*this)(__x.__get_value().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.__get_value().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.__get_value().first, __y.__get_value().first);}
 500     _LIBCPP_INLINE_VISIBILITY
 501     bool operator()(const _Cp& __x, const _Key& __y) const
 502         {return __pred_(__x.__get_value().first, __y);}
 503     _LIBCPP_INLINE_VISIBILITY
 504     bool operator()(const _Key& __x, const _Cp& __y) const
 505         {return __pred_(__x, __y.__get_value().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_CXX03_LANG
 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_CXX03_LANG
 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_CXX03_LANG
 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_.__get_value().second));
 576         if (__first_constructed)
 577             __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__get_value().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 struct __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_ref_pair_type;
 591     typedef pair<key_type&&, mapped_type&&>          __nc_rref_pair_type;
 592
 593 private:
 594     value_type __cc;
 595
 596 public:
 597     _LIBCPP_INLINE_VISIBILITY
 598     value_type& __get_value()
 599     {
 600 #if _LIBCPP_STD_VER > 14
 601         return *_VSTD::launder(_VSTD::addressof(__cc));
 602 #else
 603         return __cc;
 604 #endif
 605     }
 606
 607     _LIBCPP_INLINE_VISIBILITY
 608     const value_type& __get_value() const
 609     {
 610 #if _LIBCPP_STD_VER > 14
 611         return *_VSTD::launder(_VSTD::addressof(__cc));
 612 #else
 613         return __cc;
 614 #endif
 615     }
 616
 617     _LIBCPP_INLINE_VISIBILITY
 618     __nc_ref_pair_type __ref()
 619     {
 620         value_type& __v = __get_value();
 621         return __nc_ref_pair_type(const_cast<key_type&>(__v.first), __v.second);
 622     }
 623
 624     _LIBCPP_INLINE_VISIBILITY
 625     __nc_rref_pair_type __move()
 626     {
 627         value_type& __v = __get_value();
 628         return __nc_rref_pair_type(
 629             _VSTD::move(const_cast<key_type&>(__v.first)),
 630             _VSTD::move(__v.second));
 631     }
 632
 633     _LIBCPP_INLINE_VISIBILITY
 634     __hash_value_type& operator=(const __hash_value_type& __v)
 635     {
 636         __ref() = __v.__get_value();
 637         return *this;
 638     }
 639
 640     _LIBCPP_INLINE_VISIBILITY
 641     __hash_value_type& operator=(__hash_value_type&& __v)
 642     {
 643         __ref() = __v.__move();
 644         return *this;
 645     }
 646
 647     template <class _ValueTp,
 648               class = typename enable_if<
 649                     __is_same_uncvref<_ValueTp, value_type>::value
 650                  >::type
 651              >
 652     _LIBCPP_INLINE_VISIBILITY
 653     __hash_value_type& operator=(_ValueTp&& __v)
 654     {
 655         __ref() = _VSTD::forward<_ValueTp>(__v);
 656         return *this;
 657     }
 658
 659 private:
 660     __hash_value_type(const __hash_value_type& __v) = delete;
 661     __hash_value_type(__hash_value_type&& __v) = delete;
 662     template <class ..._Args>
 663     explicit __hash_value_type(_Args&& ...__args) = delete;
 664
 665     ~__hash_value_type() = delete;
 666 };
 667
 668 #else
 669
 670 template <class _Key, class _Tp>
 671 struct __hash_value_type
 672 {
 673     typedef _Key                                     key_type;
 674     typedef _Tp                                      mapped_type;
 675     typedef pair<const key_type, mapped_type>        value_type;
 676
 677 private:
 678     value_type __cc;
 679
 680 public:
 681     _LIBCPP_INLINE_VISIBILITY
 682     value_type& __get_value() { return __cc; }
 683     _LIBCPP_INLINE_VISIBILITY
 684     const value_type& __get_value() const { return __cc; }
 685
 686 private:
 687    ~__hash_value_type();
 688 };
 689
 690 #endif
 691
 692 template <class _HashIterator>
 693 class _LIBCPP_TEMPLATE_VIS __hash_map_iterator
 694 {
 695     _HashIterator __i_;
 696
 697     typedef  __hash_node_types_from_iterator<_HashIterator> _NodeTypes;
 698
 699 public:
 700     typedef forward_iterator_tag                                 iterator_category;
 701     typedef typename _NodeTypes::__map_value_type                value_type;
 702     typedef typename _NodeTypes::difference_type                 difference_type;
 703     typedef value_type&                                          reference;
 704     typedef typename _NodeTypes::__map_value_type_pointer       pointer;
 705
 706     _LIBCPP_INLINE_VISIBILITY
 707     __hash_map_iterator() _NOEXCEPT {}
 708
 709     _LIBCPP_INLINE_VISIBILITY
 710     __hash_map_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
 711
 712     _LIBCPP_INLINE_VISIBILITY
 713     reference operator*() const {return __i_->__get_value();}
 714     _LIBCPP_INLINE_VISIBILITY
 715     pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__get_value());}
 716
 717     _LIBCPP_INLINE_VISIBILITY
 718     __hash_map_iterator& operator++() {++__i_; return *this;}
 719     _LIBCPP_INLINE_VISIBILITY
 720     __hash_map_iterator operator++(int)
 721     {
 722         __hash_map_iterator __t(*this);
 723         ++(*this);
 724         return __t;
 725     }
 726
 727     friend _LIBCPP_INLINE_VISIBILITY
 728         bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y)
 729         {return __x.__i_ == __y.__i_;}
 730     friend _LIBCPP_INLINE_VISIBILITY
 731         bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y)
 732         {return __x.__i_ != __y.__i_;}
 733
 734     template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_map;
 735     template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
 736     template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator;
 737     template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator;
 738     template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator;
 739 };
 740
 741 template <class _HashIterator>
 742 class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator
 743 {
 744     _HashIterator __i_;
 745
 746     typedef  __hash_node_types_from_iterator<_HashIterator> _NodeTypes;
 747
 748 public:
 749     typedef forward_iterator_tag                                 iterator_category;
 750     typedef typename _NodeTypes::__map_value_type                value_type;
 751     typedef typename _NodeTypes::difference_type                 difference_type;
 752     typedef const value_type&                                    reference;
 753     typedef typename _NodeTypes::__const_map_value_type_pointer  pointer;
 754
 755     _LIBCPP_INLINE_VISIBILITY
 756     __hash_map_const_iterator() _NOEXCEPT {}
 757
 758     _LIBCPP_INLINE_VISIBILITY
 759     __hash_map_const_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
 760     _LIBCPP_INLINE_VISIBILITY
 761     __hash_map_const_iterator(
 762             __hash_map_iterator<typename _HashIterator::__non_const_iterator> __i)
 763                  _NOEXCEPT
 764                 : __i_(__i.__i_) {}
 765
 766     _LIBCPP_INLINE_VISIBILITY
 767     reference operator*() const {return __i_->__get_value();}
 768     _LIBCPP_INLINE_VISIBILITY
 769     pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__get_value());}
 770
 771     _LIBCPP_INLINE_VISIBILITY
 772     __hash_map_const_iterator& operator++() {++__i_; return *this;}
 773     _LIBCPP_INLINE_VISIBILITY
 774     __hash_map_const_iterator operator++(int)
 775     {
 776         __hash_map_const_iterator __t(*this);
 777         ++(*this);
 778         return __t;
 779     }
 780
 781     friend _LIBCPP_INLINE_VISIBILITY
 782         bool operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)
 783         {return __x.__i_ == __y.__i_;}
 784     friend _LIBCPP_INLINE_VISIBILITY
 785         bool operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)
 786         {return __x.__i_ != __y.__i_;}
 787
 788     template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_map;
 789     template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
 790     template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator;
 791     template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator;
 792 };
 793
 794 template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
 795           class _Alloc = allocator<pair<const _Key, _Tp> > >
 796 class _LIBCPP_TEMPLATE_VIS unordered_map
 797 {
 798 public:
 799     // types
 800     typedef _Key                                           key_type;
 801     typedef _Tp                                            mapped_type;
 802     typedef _Hash                                          hasher;
 803     typedef _Pred                                          key_equal;
 804     typedef _Alloc                                         allocator_type;
 805     typedef pair<const key_type, mapped_type>              value_type;
 806     typedef value_type&                                    reference;
 807     typedef const value_type&                              const_reference;
 808     static_assert((is_same<value_type, typename allocator_type::value_type>::value),
 809                   "Invalid allocator::value_type");
 810
 811 private:
 812     typedef __hash_value_type<key_type, mapped_type>                 __value_type;
 813     typedef __unordered_map_hasher<key_type, __value_type, hasher>   __hasher;
 814     typedef __unordered_map_equal<key_type, __value_type, key_equal> __key_equal;
 815     typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>,
 816                                                  __value_type>::type __allocator_type;
 817
 818     typedef __hash_table<__value_type, __hasher,
 819                          __key_equal,  __allocator_type>   __table;
 820
 821     __table __table_;
 822
 823     typedef typename __table::_NodeTypes                   _NodeTypes;
 824     typedef typename __table::__node_pointer               __node_pointer;
 825     typedef typename __table::__node_const_pointer         __node_const_pointer;
 826     typedef typename __table::__node_traits                __node_traits;
 827     typedef typename __table::__node_allocator             __node_allocator;
 828     typedef typename __table::__node                       __node;
 829     typedef __hash_map_node_destructor<__node_allocator>   _Dp;
 830     typedef unique_ptr<__node, _Dp>                         __node_holder;
 831     typedef allocator_traits<allocator_type>               __alloc_traits;
 832
 833     static_assert((is_same<typename __table::__container_value_type, value_type>::value), "");
 834     static_assert((is_same<typename __table::__node_value_type, __value_type>::value), "");
 835 public:
 836     typedef typename __alloc_traits::pointer         pointer;
 837     typedef typename __alloc_traits::const_pointer   const_pointer;
 838     typedef typename __table::size_type              size_type;
 839     typedef typename __table::difference_type        difference_type;
 840
 841     typedef __hash_map_iterator<typename __table::iterator>       iterator;
 842     typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
 843     typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
 844     typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
 845
 846     _LIBCPP_INLINE_VISIBILITY
 847     unordered_map()
 848         _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
 849         {
 850 #if _LIBCPP_DEBUG_LEVEL >= 2
 851             __get_db()->__insert_c(this);
 852 #endif
 853         }
 854     explicit unordered_map(size_type __n, const hasher& __hf = hasher(),
 855                            const key_equal& __eql = key_equal());
 856     unordered_map(size_type __n, const hasher& __hf,
 857                   const key_equal& __eql,
 858                   const allocator_type& __a);
 859     template <class _InputIterator>
 860         unordered_map(_InputIterator __first, _InputIterator __last);
 861     template <class _InputIterator>
 862         unordered_map(_InputIterator __first, _InputIterator __last,
 863                       size_type __n, const hasher& __hf = hasher(),
 864                       const key_equal& __eql = key_equal());
 865     template <class _InputIterator>
 866         unordered_map(_InputIterator __first, _InputIterator __last,
 867                       size_type __n, const hasher& __hf,
 868                       const key_equal& __eql,
 869                       const allocator_type& __a);
 870     _LIBCPP_INLINE_VISIBILITY
 871     explicit unordered_map(const allocator_type& __a);
 872     unordered_map(const unordered_map& __u);
 873     unordered_map(const unordered_map& __u, const allocator_type& __a);
 874 #ifndef _LIBCPP_CXX03_LANG
 875     _LIBCPP_INLINE_VISIBILITY
 876     unordered_map(unordered_map&& __u)
 877         _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
 878     unordered_map(unordered_map&& __u, const allocator_type& __a);
 879     unordered_map(initializer_list<value_type> __il);
 880     unordered_map(initializer_list<value_type> __il, size_type __n,
 881                   const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
 882     unordered_map(initializer_list<value_type> __il, size_type __n,
 883                   const hasher& __hf, const key_equal& __eql,
 884                   const allocator_type& __a);
 885 #endif  // _LIBCPP_CXX03_LANG
 886 #if _LIBCPP_STD_VER > 11
 887     _LIBCPP_INLINE_VISIBILITY
 888     unordered_map(size_type __n, const allocator_type& __a)
 889       : unordered_map(__n, hasher(), key_equal(), __a) {}
 890     _LIBCPP_INLINE_VISIBILITY
 891     unordered_map(size_type __n, const hasher& __hf, const allocator_type& __a)
 892       : unordered_map(__n, __hf, key_equal(), __a) {}
 893     template <class _InputIterator>
 894     _LIBCPP_INLINE_VISIBILITY
 895       unordered_map(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a)
 896       : unordered_map(__first, __last, __n, hasher(), key_equal(), __a) {}
 897     template <class _InputIterator>
 898     _LIBCPP_INLINE_VISIBILITY
 899       unordered_map(_InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf,
 900         const allocator_type& __a)
 901       : unordered_map(__first, __last, __n, __hf, key_equal(), __a) {}
 902     _LIBCPP_INLINE_VISIBILITY
 903     unordered_map(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)
 904       : unordered_map(__il, __n, hasher(), key_equal(), __a) {}
 905     _LIBCPP_INLINE_VISIBILITY
 906     unordered_map(initializer_list<value_type> __il, size_type __n, const hasher& __hf,
 907       const allocator_type& __a)
 908       : unordered_map(__il, __n, __hf, key_equal(), __a) {}
 909 #endif
 910     // ~unordered_map() = default;
 911     _LIBCPP_INLINE_VISIBILITY
 912     unordered_map& operator=(const unordered_map& __u)
 913     {
 914 #ifndef _LIBCPP_CXX03_LANG
 915         __table_ = __u.__table_;
 916 #else
 917         if (this != &__u) {
 918             __table_.clear();
 919             __table_.hash_function() = __u.__table_.hash_function();
 920             __table_.key_eq() = __u.__table_.key_eq();
 921             __table_.max_load_factor() = __u.__table_.max_load_factor();
 922             __table_.__copy_assign_alloc(__u.__table_);
 923             insert(__u.begin(), __u.end());
 924         }
 925 #endif
 926         return *this;
 927     }
 928 #ifndef _LIBCPP_CXX03_LANG
 929     _LIBCPP_INLINE_VISIBILITY
 930     unordered_map& operator=(unordered_map&& __u)
 931         _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
 932     _LIBCPP_INLINE_VISIBILITY
 933     unordered_map& operator=(initializer_list<value_type> __il);
 934 #endif  // _LIBCPP_CXX03_LANG
 935
 936     _LIBCPP_INLINE_VISIBILITY
 937     allocator_type get_allocator() const _NOEXCEPT
 938         {return allocator_type(__table_.__node_alloc());}
 939
 940     _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
 941     bool      empty() const _NOEXCEPT {return __table_.size() == 0;}
 942     _LIBCPP_INLINE_VISIBILITY
 943     size_type size() const _NOEXCEPT  {return __table_.size();}
 944     _LIBCPP_INLINE_VISIBILITY
 945     size_type max_size() const _NOEXCEPT {return __table_.max_size();}
 946
 947     _LIBCPP_INLINE_VISIBILITY
 948     iterator       begin() _NOEXCEPT        {return __table_.begin();}
 949     _LIBCPP_INLINE_VISIBILITY
 950     iterator       end() _NOEXCEPT          {return __table_.end();}
 951     _LIBCPP_INLINE_VISIBILITY
 952     const_iterator begin()  const _NOEXCEPT {return __table_.begin();}
 953     _LIBCPP_INLINE_VISIBILITY
 954     const_iterator end()    const _NOEXCEPT {return __table_.end();}
 955     _LIBCPP_INLINE_VISIBILITY
 956     const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
 957     _LIBCPP_INLINE_VISIBILITY
 958     const_iterator cend()   const _NOEXCEPT {return __table_.end();}
 959
 960     _LIBCPP_INLINE_VISIBILITY
 961     pair<iterator, bool> insert(const value_type& __x)
 962         {return __table_.__insert_unique(__x);}
 963
 964     iterator insert(const_iterator __p, const value_type& __x) {
 965 #if _LIBCPP_DEBUG_LEVEL >= 2
 966         _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
 967             "unordered_map::insert(const_iterator, const value_type&) called with an iterator not"
 968             " referring to this unordered_map");
 969 #else
 970         ((void)__p);
 971 #endif
 972         return insert(__x).first;
 973     }
 974
 975     template <class _InputIterator>
 976         _LIBCPP_INLINE_VISIBILITY
 977         void insert(_InputIterator __first, _InputIterator __last);
 978
 979 #ifndef _LIBCPP_CXX03_LANG
 980     _LIBCPP_INLINE_VISIBILITY
 981     void insert(initializer_list<value_type> __il)
 982         {insert(__il.begin(), __il.end());}
 983
 984     _LIBCPP_INLINE_VISIBILITY
 985     pair<iterator, bool> insert(value_type&& __x)
 986         {return __table_.__insert_unique(_VSTD::move(__x));}
 987
 988     iterator insert(const_iterator __p, value_type&& __x) {
 989 #if _LIBCPP_DEBUG_LEVEL >= 2
 990         _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
 991             "unordered_map::insert(const_iterator, const value_type&) called with an iterator not"
 992             " referring to this unordered_map");
 993 #else
 994         ((void)__p);
 995 #endif
 996         return __table_.__insert_unique(_VSTD::move(__x)).first;
 997     }
 998
 999     template <class _Pp,
1000               class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1001         _LIBCPP_INLINE_VISIBILITY
1002         pair<iterator, bool> insert(_Pp&& __x)
1003             {return __table_.__insert_unique(_VSTD::forward<_Pp>(__x));}
1004
1005     template <class _Pp,
1006               class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1007         _LIBCPP_INLINE_VISIBILITY
1008         iterator insert(const_iterator __p, _Pp&& __x)
1009         {
1010 #if _LIBCPP_DEBUG_LEVEL >= 2
1011             _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1012                 "unordered_map::insert(const_iterator, value_type&&) called with an iterator not"
1013                 " referring to this unordered_map");
1014 #else
1015           ((void)__p);
1016 #endif
1017             return insert(_VSTD::forward<_Pp>(__x)).first;
1018         }
1019
1020     template <class... _Args>
1021     _LIBCPP_INLINE_VISIBILITY
1022     pair<iterator, bool> emplace(_Args&&... __args) {
1023         return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...);
1024     }
1025
1026     template <class... _Args>
1027     _LIBCPP_INLINE_VISIBILITY
1028     iterator emplace_hint(const_iterator __p, _Args&&... __args) {
1029 #if _LIBCPP_DEBUG_LEVEL >= 2
1030         _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1031             "unordered_map::emplace_hint(const_iterator, args...) called with an iterator not"
1032             " referring to this unordered_map");
1033 #else
1034           ((void)__p);
1035 #endif
1036         return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first;
1037     }
1038
1039 #endif  // _LIBCPP_CXX03_LANG
1040
1041 #if _LIBCPP_STD_VER > 14
1042     template <class... _Args>
1043         _LIBCPP_INLINE_VISIBILITY
1044         pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args)
1045     {
1046         return __table_.__emplace_unique_key_args(__k, _VSTD::piecewise_construct,
1047             _VSTD::forward_as_tuple(__k),
1048             _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
1049     }
1050
1051     template <class... _Args>
1052         _LIBCPP_INLINE_VISIBILITY
1053         pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args)
1054     {
1055         return __table_.__emplace_unique_key_args(__k, _VSTD::piecewise_construct,
1056             _VSTD::forward_as_tuple(_VSTD::move(__k)),
1057             _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
1058     }
1059
1060     template <class... _Args>
1061         _LIBCPP_INLINE_VISIBILITY
1062         iterator try_emplace(const_iterator __h, const key_type& __k, _Args&&... __args)
1063     {
1064 #if _LIBCPP_DEBUG_LEVEL >= 2
1065         _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__h) == this,
1066             "unordered_map::try_emplace(const_iterator, key, args...) called with an iterator not"
1067             " referring to this unordered_map");
1068 #else
1069         ((void)__h);
1070 #endif
1071         return try_emplace(__k, _VSTD::forward<_Args>(__args)...).first;
1072     }
1073
1074     template <class... _Args>
1075         _LIBCPP_INLINE_VISIBILITY
1076         iterator try_emplace(const_iterator __h, key_type&& __k, _Args&&... __args)
1077     {
1078 #if _LIBCPP_DEBUG_LEVEL >= 2
1079         _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__h) == this,
1080             "unordered_map::try_emplace(const_iterator, key, args...) called with an iterator not"
1081             " referring to this unordered_map");
1082 #else
1083         ((void)__h);
1084 #endif
1085         return try_emplace(_VSTD::move(__k), _VSTD::forward<_Args>(__args)...).first;
1086     }
1087
1088     template <class _Vp>
1089         _LIBCPP_INLINE_VISIBILITY
1090         pair<iterator, bool> insert_or_assign(const key_type& __k, _Vp&& __v)
1091     {
1092         pair<iterator, bool> __res = __table_.__emplace_unique_key_args(__k,
1093             __k, _VSTD::forward<_Vp>(__v));
1094         if (!__res.second) {
1095             __res.first->second = _VSTD::forward<_Vp>(__v);
1096         }
1097         return __res;
1098     }
1099
1100     template <class _Vp>
1101         _LIBCPP_INLINE_VISIBILITY
1102         pair<iterator, bool> insert_or_assign(key_type&& __k, _Vp&& __v)
1103     {
1104         pair<iterator, bool> __res = __table_.__emplace_unique_key_args(__k,
1105             _VSTD::move(__k), _VSTD::forward<_Vp>(__v));
1106         if (!__res.second) {
1107             __res.first->second = _VSTD::forward<_Vp>(__v);
1108         }
1109         return __res;
1110     }
1111
1112     template <class _Vp>
1113         _LIBCPP_INLINE_VISIBILITY
1114         iterator insert_or_assign(const_iterator, const key_type& __k, _Vp&& __v)
1115      {
1116           // FIXME: Add debug mode checking for the iterator input
1117           return insert_or_assign(__k, _VSTD::forward<_Vp>(__v)).first;
1118      }
1119
1120     template <class _Vp>
1121         _LIBCPP_INLINE_VISIBILITY
1122         iterator insert_or_assign(const_iterator, key_type&& __k, _Vp&& __v)
1123      {
1124         // FIXME: Add debug mode checking for the iterator input
1125         return insert_or_assign(_VSTD::move(__k), _VSTD::forward<_Vp>(__v)).first;
1126      }
1127 #endif // _LIBCPP_STD_VER > 14
1128
1129     _LIBCPP_INLINE_VISIBILITY
1130     iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);}
1131     _LIBCPP_INLINE_VISIBILITY
1132     iterator erase(iterator __p)       {return __table_.erase(__p.__i_);}
1133     _LIBCPP_INLINE_VISIBILITY
1134     size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
1135     _LIBCPP_INLINE_VISIBILITY
1136     iterator erase(const_iterator __first, const_iterator __last)
1137         {return __table_.erase(__first.__i_, __last.__i_);}
1138     _LIBCPP_INLINE_VISIBILITY
1139     void clear() _NOEXCEPT {__table_.clear();}
1140
1141     _LIBCPP_INLINE_VISIBILITY
1142     void swap(unordered_map& __u)
1143         _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
1144         { __table_.swap(__u.__table_);}
1145
1146     _LIBCPP_INLINE_VISIBILITY
1147     hasher hash_function() const
1148         {return __table_.hash_function().hash_function();}
1149     _LIBCPP_INLINE_VISIBILITY
1150     key_equal key_eq() const
1151         {return __table_.key_eq().key_eq();}
1152
1153     _LIBCPP_INLINE_VISIBILITY
1154     iterator       find(const key_type& __k)       {return __table_.find(__k);}
1155     _LIBCPP_INLINE_VISIBILITY
1156     const_iterator find(const key_type& __k) const {return __table_.find(__k);}
1157     _LIBCPP_INLINE_VISIBILITY
1158     size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
1159     _LIBCPP_INLINE_VISIBILITY
1160     pair<iterator, iterator>             equal_range(const key_type& __k)
1161         {return __table_.__equal_range_unique(__k);}
1162     _LIBCPP_INLINE_VISIBILITY
1163     pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
1164         {return __table_.__equal_range_unique(__k);}
1165
1166     mapped_type& operator[](const key_type& __k);
1167 #ifndef _LIBCPP_CXX03_LANG
1168     mapped_type& operator[](key_type&& __k);
1169 #endif
1170
1171     mapped_type&       at(const key_type& __k);
1172     const mapped_type& at(const key_type& __k) const;
1173
1174     _LIBCPP_INLINE_VISIBILITY
1175     size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
1176     _LIBCPP_INLINE_VISIBILITY
1177     size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
1178
1179     _LIBCPP_INLINE_VISIBILITY
1180     size_type bucket_size(size_type __n) const
1181         {return __table_.bucket_size(__n);}
1182     _LIBCPP_INLINE_VISIBILITY
1183     size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
1184
1185     _LIBCPP_INLINE_VISIBILITY
1186     local_iterator       begin(size_type __n)        {return __table_.begin(__n);}
1187     _LIBCPP_INLINE_VISIBILITY
1188     local_iterator       end(size_type __n)          {return __table_.end(__n);}
1189     _LIBCPP_INLINE_VISIBILITY
1190     const_local_iterator begin(size_type __n) const  {return __table_.cbegin(__n);}
1191     _LIBCPP_INLINE_VISIBILITY
1192     const_local_iterator end(size_type __n) const    {return __table_.cend(__n);}
1193     _LIBCPP_INLINE_VISIBILITY
1194     const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
1195     _LIBCPP_INLINE_VISIBILITY
1196     const_local_iterator cend(size_type __n) const   {return __table_.cend(__n);}
1197
1198     _LIBCPP_INLINE_VISIBILITY
1199     float load_factor() const _NOEXCEPT {return __table_.load_factor();}
1200     _LIBCPP_INLINE_VISIBILITY
1201     float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
1202     _LIBCPP_INLINE_VISIBILITY
1203     void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
1204     _LIBCPP_INLINE_VISIBILITY
1205     void rehash(size_type __n) {__table_.rehash(__n);}
1206     _LIBCPP_INLINE_VISIBILITY
1207     void reserve(size_type __n) {__table_.reserve(__n);}
1208
1209 #if _LIBCPP_DEBUG_LEVEL >= 2
1210
1211     bool __dereferenceable(const const_iterator* __i) const
1212         {return __table_.__dereferenceable(&__i->__i_);}
1213     bool __decrementable(const const_iterator* __i) const
1214         {return __table_.__decrementable(&__i->__i_);}
1215     bool __addable(const const_iterator* __i, ptrdiff_t __n) const
1216         {return __table_.__addable(&__i->__i_, __n);}
1217     bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
1218         {return __table_.__addable(&__i->__i_, __n);}
1219
1220 #endif  // _LIBCPP_DEBUG_LEVEL >= 2
1221
1222 private:
1223
1224 #ifdef _LIBCPP_CXX03_LANG
1225     __node_holder __construct_node_with_key(const key_type& __k);
1226 #endif
1227 };
1228
1229 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1230 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1231         size_type __n, const hasher& __hf, const key_equal& __eql)
1232     : __table_(__hf, __eql)
1233 {
1234 #if _LIBCPP_DEBUG_LEVEL >= 2
1235     __get_db()->__insert_c(this);
1236 #endif
1237     __table_.rehash(__n);
1238 }
1239
1240 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1241 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1242         size_type __n, const hasher& __hf, const key_equal& __eql,
1243         const allocator_type& __a)
1244     : __table_(__hf, __eql, typename __table::allocator_type(__a))
1245 {
1246 #if _LIBCPP_DEBUG_LEVEL >= 2
1247     __get_db()->__insert_c(this);
1248 #endif
1249     __table_.rehash(__n);
1250 }
1251
1252 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1253 inline
1254 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1255         const allocator_type& __a)
1256     : __table_(typename __table::allocator_type(__a))
1257 {
1258 #if _LIBCPP_DEBUG_LEVEL >= 2
1259     __get_db()->__insert_c(this);
1260 #endif
1261 }
1262
1263 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1264 template <class _InputIterator>
1265 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1266         _InputIterator __first, _InputIterator __last)
1267 {
1268 #if _LIBCPP_DEBUG_LEVEL >= 2
1269     __get_db()->__insert_c(this);
1270 #endif
1271     insert(__first, __last);
1272 }
1273
1274 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1275 template <class _InputIterator>
1276 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1277         _InputIterator __first, _InputIterator __last, size_type __n,
1278         const hasher& __hf, const key_equal& __eql)
1279     : __table_(__hf, __eql)
1280 {
1281 #if _LIBCPP_DEBUG_LEVEL >= 2
1282     __get_db()->__insert_c(this);
1283 #endif
1284     __table_.rehash(__n);
1285     insert(__first, __last);
1286 }
1287
1288 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1289 template <class _InputIterator>
1290 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1291         _InputIterator __first, _InputIterator __last, size_type __n,
1292         const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1293     : __table_(__hf, __eql, typename __table::allocator_type(__a))
1294 {
1295 #if _LIBCPP_DEBUG_LEVEL >= 2
1296     __get_db()->__insert_c(this);
1297 #endif
1298     __table_.rehash(__n);
1299     insert(__first, __last);
1300 }
1301
1302 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1303 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1304         const unordered_map& __u)
1305     : __table_(__u.__table_)
1306 {
1307 #if _LIBCPP_DEBUG_LEVEL >= 2
1308     __get_db()->__insert_c(this);
1309 #endif
1310     __table_.rehash(__u.bucket_count());
1311     insert(__u.begin(), __u.end());
1312 }
1313
1314 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1315 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1316         const unordered_map& __u, const allocator_type& __a)
1317     : __table_(__u.__table_, typename __table::allocator_type(__a))
1318 {
1319 #if _LIBCPP_DEBUG_LEVEL >= 2
1320     __get_db()->__insert_c(this);
1321 #endif
1322     __table_.rehash(__u.bucket_count());
1323     insert(__u.begin(), __u.end());
1324 }
1325
1326 #ifndef _LIBCPP_CXX03_LANG
1327
1328 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1329 inline
1330 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1331         unordered_map&& __u)
1332     _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
1333     : __table_(_VSTD::move(__u.__table_))
1334 {
1335 #if _LIBCPP_DEBUG_LEVEL >= 2
1336     __get_db()->__insert_c(this);
1337     __get_db()->swap(this, &__u);
1338 #endif
1339 }
1340
1341 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1342 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1343         unordered_map&& __u, const allocator_type& __a)
1344     : __table_(_VSTD::move(__u.__table_), typename __table::allocator_type(__a))
1345 {
1346 #if _LIBCPP_DEBUG_LEVEL >= 2
1347     __get_db()->__insert_c(this);
1348 #endif
1349     if (__a != __u.get_allocator())
1350     {
1351         iterator __i = __u.begin();
1352         while (__u.size() != 0) {
1353             __table_.__emplace_unique(
1354                 __u.__table_.remove((__i++).__i_)->__value_.__move());
1355         }
1356     }
1357 #if _LIBCPP_DEBUG_LEVEL >= 2
1358     else
1359         __get_db()->swap(this, &__u);
1360 #endif
1361 }
1362
1363 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1364 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1365         initializer_list<value_type> __il)
1366 {
1367 #if _LIBCPP_DEBUG_LEVEL >= 2
1368     __get_db()->__insert_c(this);
1369 #endif
1370     insert(__il.begin(), __il.end());
1371 }
1372
1373 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1374 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1375         initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1376         const key_equal& __eql)
1377     : __table_(__hf, __eql)
1378 {
1379 #if _LIBCPP_DEBUG_LEVEL >= 2
1380     __get_db()->__insert_c(this);
1381 #endif
1382     __table_.rehash(__n);
1383     insert(__il.begin(), __il.end());
1384 }
1385
1386 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1387 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1388         initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1389         const key_equal& __eql, const allocator_type& __a)
1390     : __table_(__hf, __eql, typename __table::allocator_type(__a))
1391 {
1392 #if _LIBCPP_DEBUG_LEVEL >= 2
1393     __get_db()->__insert_c(this);
1394 #endif
1395     __table_.rehash(__n);
1396     insert(__il.begin(), __il.end());
1397 }
1398
1399 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1400 inline
1401 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
1402 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_map&& __u)
1403     _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
1404 {
1405     __table_ = _VSTD::move(__u.__table_);
1406     return *this;
1407 }
1408
1409 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1410 inline
1411 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
1412 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(
1413         initializer_list<value_type> __il)
1414 {
1415     __table_.__assign_unique(__il.begin(), __il.end());
1416     return *this;
1417 }
1418
1419 #endif  // _LIBCPP_CXX03_LANG
1420
1421 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1422 template <class _InputIterator>
1423 inline
1424 void
1425 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
1426                                                        _InputIterator __last)
1427 {
1428     for (; __first != __last; ++__first)
1429         __table_.__insert_unique(*__first);
1430 }
1431
1432 #ifndef _LIBCPP_CXX03_LANG
1433
1434 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1435 _Tp&
1436 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k)
1437 {
1438     return __table_.__emplace_unique_key_args(__k,
1439         std::piecewise_construct, std::forward_as_tuple(__k),
1440                                   std::forward_as_tuple()).first->__get_value().second;
1441 }
1442
1443 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1444 _Tp&
1445 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&& __k)
1446 {
1447     return __table_.__emplace_unique_key_args(__k,
1448         std::piecewise_construct, std::forward_as_tuple(std::move(__k)),
1449                                   std::forward_as_tuple()).first->__get_value().second;
1450 }
1451 #else // _LIBCPP_CXX03_LANG
1452
1453 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1454 typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1455 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(const key_type& __k)
1456 {
1457     __node_allocator& __na = __table_.__node_alloc();
1458     __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1459     __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__get_value().first), __k);
1460     __h.get_deleter().__first_constructed = true;
1461     __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__get_value().second));
1462     __h.get_deleter().__second_constructed = true;
1463     return _LIBCPP_EXPLICIT_MOVE(__h);  // explicitly moved for C++03
1464 }
1465
1466 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1467 _Tp&
1468 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k)
1469 {
1470     iterator __i = find(__k);
1471     if (__i != end())
1472         return __i->second;
1473     __node_holder __h = __construct_node_with_key(__k);
1474     pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1475     __h.release();
1476     return __r.first->second;
1477 }
1478
1479 #endif  // _LIBCPP_CXX03_MODE
1480
1481 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1482 _Tp&
1483 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k)
1484 {
1485     iterator __i = find(__k);
1486 #ifndef _LIBCPP_NO_EXCEPTIONS
1487     if (__i == end())
1488         throw out_of_range("unordered_map::at: key not found");
1489 #endif  // _LIBCPP_NO_EXCEPTIONS
1490     return __i->second;
1491 }
1492
1493 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1494 const _Tp&
1495 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) const
1496 {
1497     const_iterator __i = find(__k);
1498 #ifndef _LIBCPP_NO_EXCEPTIONS
1499     if (__i == end())
1500         throw out_of_range("unordered_map::at: key not found");
1501 #endif  // _LIBCPP_NO_EXCEPTIONS
1502     return __i->second;
1503 }
1504
1505 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1506 inline _LIBCPP_INLINE_VISIBILITY
1507 void
1508 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1509      unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1510     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1511 {
1512     __x.swap(__y);
1513 }
1514
1515 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1516 bool
1517 operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1518            const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1519 {
1520     if (__x.size() != __y.size())
1521         return false;
1522     typedef typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
1523                                                                  const_iterator;
1524     for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();
1525             __i != __ex; ++__i)
1526     {
1527         const_iterator __j = __y.find(__i->first);
1528         if (__j == __ey || !(*__i == *__j))
1529             return false;
1530     }
1531     return true;
1532 }
1533
1534 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1535 inline _LIBCPP_INLINE_VISIBILITY
1536 bool
1537 operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1538            const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1539 {
1540     return !(__x == __y);
1541 }
1542
1543 template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
1544           class _Alloc = allocator<pair<const _Key, _Tp> > >
1545 class _LIBCPP_TEMPLATE_VIS unordered_multimap
1546 {
1547 public:
1548     // types
1549     typedef _Key                                           key_type;
1550     typedef _Tp                                            mapped_type;
1551     typedef _Hash                                          hasher;
1552     typedef _Pred                                          key_equal;
1553     typedef _Alloc                                         allocator_type;
1554     typedef pair<const key_type, mapped_type>              value_type;
1555     typedef value_type&                                    reference;
1556     typedef const value_type&                              const_reference;
1557     static_assert((is_same<value_type, typename allocator_type::value_type>::value),
1558                   "Invalid allocator::value_type");
1559
1560 private:
1561     typedef __hash_value_type<key_type, mapped_type>                 __value_type;
1562     typedef __unordered_map_hasher<key_type, __value_type, hasher>   __hasher;
1563     typedef __unordered_map_equal<key_type, __value_type, key_equal> __key_equal;
1564     typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>,
1565                                                  __value_type>::type __allocator_type;
1566
1567     typedef __hash_table<__value_type, __hasher,
1568                          __key_equal,  __allocator_type>   __table;
1569
1570     __table __table_;
1571
1572     typedef typename __table::_NodeTypes                   _NodeTypes;
1573     typedef typename __table::__node_traits                __node_traits;
1574     typedef typename __table::__node_allocator             __node_allocator;
1575     typedef typename __table::__node                       __node;
1576     typedef __hash_map_node_destructor<__node_allocator>   _Dp;
1577     typedef unique_ptr<__node, _Dp>                         __node_holder;
1578     typedef allocator_traits<allocator_type>               __alloc_traits;
1579     static_assert((is_same<typename __node_traits::size_type,
1580                           typename __alloc_traits::size_type>::value),
1581                  "Allocator uses different size_type for different types");
1582 public:
1583     typedef typename __alloc_traits::pointer         pointer;
1584     typedef typename __alloc_traits::const_pointer   const_pointer;
1585     typedef typename __table::size_type              size_type;
1586     typedef typename __table::difference_type        difference_type;
1587
1588     typedef __hash_map_iterator<typename __table::iterator>       iterator;
1589     typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
1590     typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
1591     typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
1592
1593     _LIBCPP_INLINE_VISIBILITY
1594     unordered_multimap()
1595         _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
1596         {
1597 #if _LIBCPP_DEBUG_LEVEL >= 2
1598             __get_db()->__insert_c(this);
1599 #endif
1600         }
1601     explicit unordered_multimap(size_type __n, const hasher& __hf = hasher(),
1602                                 const key_equal& __eql = key_equal());
1603     unordered_multimap(size_type __n, const hasher& __hf,
1604                                 const key_equal& __eql,
1605                                 const allocator_type& __a);
1606     template <class _InputIterator>
1607         unordered_multimap(_InputIterator __first, _InputIterator __last);
1608     template <class _InputIterator>
1609         unordered_multimap(_InputIterator __first, _InputIterator __last,
1610                       size_type __n, const hasher& __hf = hasher(),
1611                       const key_equal& __eql = key_equal());
1612     template <class _InputIterator>
1613         unordered_multimap(_InputIterator __first, _InputIterator __last,
1614                       size_type __n, const hasher& __hf,
1615                       const key_equal& __eql,
1616                       const allocator_type& __a);
1617     _LIBCPP_INLINE_VISIBILITY
1618     explicit unordered_multimap(const allocator_type& __a);
1619     unordered_multimap(const unordered_multimap& __u);
1620     unordered_multimap(const unordered_multimap& __u, const allocator_type& __a);
1621 #ifndef _LIBCPP_CXX03_LANG
1622     _LIBCPP_INLINE_VISIBILITY
1623     unordered_multimap(unordered_multimap&& __u)
1624         _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
1625     unordered_multimap(unordered_multimap&& __u, const allocator_type& __a);
1626     unordered_multimap(initializer_list<value_type> __il);
1627     unordered_multimap(initializer_list<value_type> __il, size_type __n,
1628                        const hasher& __hf = hasher(),
1629                        const key_equal& __eql = key_equal());
1630     unordered_multimap(initializer_list<value_type> __il, size_type __n,
1631                        const hasher& __hf, const key_equal& __eql,
1632                        const allocator_type& __a);
1633 #endif  // _LIBCPP_CXX03_LANG
1634 #if _LIBCPP_STD_VER > 11
1635     _LIBCPP_INLINE_VISIBILITY
1636     unordered_multimap(size_type __n, const allocator_type& __a)
1637       : unordered_multimap(__n, hasher(), key_equal(), __a) {}
1638     _LIBCPP_INLINE_VISIBILITY
1639     unordered_multimap(size_type __n, const hasher& __hf, const allocator_type& __a)
1640       : unordered_multimap(__n, __hf, key_equal(), __a) {}
1641     template <class _InputIterator>
1642     _LIBCPP_INLINE_VISIBILITY
1643       unordered_multimap(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a)
1644       : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a) {}
1645     template <class _InputIterator>
1646     _LIBCPP_INLINE_VISIBILITY
1647       unordered_multimap(_InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf,
1648         const allocator_type& __a)
1649       : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a) {}
1650     _LIBCPP_INLINE_VISIBILITY
1651     unordered_multimap(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)
1652       : unordered_multimap(__il, __n, hasher(), key_equal(), __a) {}
1653     _LIBCPP_INLINE_VISIBILITY
1654     unordered_multimap(initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1655       const allocator_type& __a)
1656       : unordered_multimap(__il, __n, __hf, key_equal(), __a) {}
1657 #endif
1658     // ~unordered_multimap() = default;
1659     _LIBCPP_INLINE_VISIBILITY
1660     unordered_multimap& operator=(const unordered_multimap& __u)
1661     {
1662 #ifndef _LIBCPP_CXX03_LANG
1663         __table_ = __u.__table_;
1664 #else
1665         if (this != &__u) {
1666             __table_.clear();
1667             __table_.hash_function() = __u.__table_.hash_function();
1668             __table_.key_eq() = __u.__table_.key_eq();
1669             __table_.max_load_factor() = __u.__table_.max_load_factor();
1670             __table_.__copy_assign_alloc(__u.__table_);
1671             insert(__u.begin(), __u.end());
1672         }
1673 #endif
1674         return *this;
1675     }
1676 #ifndef _LIBCPP_CXX03_LANG
1677     _LIBCPP_INLINE_VISIBILITY
1678     unordered_multimap& operator=(unordered_multimap&& __u)
1679         _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
1680     _LIBCPP_INLINE_VISIBILITY
1681     unordered_multimap& operator=(initializer_list<value_type> __il);
1682 #endif  // _LIBCPP_CXX03_LANG
1683
1684     _LIBCPP_INLINE_VISIBILITY
1685     allocator_type get_allocator() const _NOEXCEPT
1686         {return allocator_type(__table_.__node_alloc());}
1687
1688     _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
1689     bool      empty() const _NOEXCEPT {return __table_.size() == 0;}
1690     _LIBCPP_INLINE_VISIBILITY
1691     size_type size() const _NOEXCEPT  {return __table_.size();}
1692     _LIBCPP_INLINE_VISIBILITY
1693     size_type max_size() const _NOEXCEPT {return __table_.max_size();}
1694
1695     _LIBCPP_INLINE_VISIBILITY
1696     iterator       begin() _NOEXCEPT        {return __table_.begin();}
1697     _LIBCPP_INLINE_VISIBILITY
1698     iterator       end() _NOEXCEPT          {return __table_.end();}
1699     _LIBCPP_INLINE_VISIBILITY
1700     const_iterator begin()  const _NOEXCEPT {return __table_.begin();}
1701     _LIBCPP_INLINE_VISIBILITY
1702     const_iterator end()    const _NOEXCEPT {return __table_.end();}
1703     _LIBCPP_INLINE_VISIBILITY
1704     const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
1705     _LIBCPP_INLINE_VISIBILITY
1706     const_iterator cend()   const _NOEXCEPT {return __table_.end();}
1707
1708     _LIBCPP_INLINE_VISIBILITY
1709     iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
1710
1711     _LIBCPP_INLINE_VISIBILITY
1712     iterator insert(const_iterator __p, const value_type& __x)
1713         {return __table_.__insert_multi(__p.__i_, __x);}
1714
1715     template <class _InputIterator>
1716     _LIBCPP_INLINE_VISIBILITY
1717     void insert(_InputIterator __first, _InputIterator __last);
1718
1719 #ifndef _LIBCPP_CXX03_LANG
1720     _LIBCPP_INLINE_VISIBILITY
1721     void insert(initializer_list<value_type> __il)
1722         {insert(__il.begin(), __il.end());}
1723     _LIBCPP_INLINE_VISIBILITY
1724     iterator insert(value_type&& __x) {return __table_.__insert_multi(_VSTD::move(__x));}
1725
1726     _LIBCPP_INLINE_VISIBILITY
1727     iterator insert(const_iterator __p, value_type&& __x)
1728         {return __table_.__insert_multi(__p.__i_, _VSTD::move(__x));}
1729
1730     template <class _Pp,
1731               class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1732     _LIBCPP_INLINE_VISIBILITY
1733     iterator insert(_Pp&& __x)
1734         {return __table_.__insert_multi(_VSTD::forward<_Pp>(__x));}
1735
1736     template <class _Pp,
1737               class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1738     _LIBCPP_INLINE_VISIBILITY
1739     iterator insert(const_iterator __p, _Pp&& __x)
1740         {return __table_.__insert_multi(__p.__i_, _VSTD::forward<_Pp>(__x));}
1741
1742     template <class... _Args>
1743     iterator emplace(_Args&&... __args) {
1744         return __table_.__emplace_multi(_VSTD::forward<_Args>(__args)...);
1745     }
1746
1747     template <class... _Args>
1748     iterator emplace_hint(const_iterator __p, _Args&&... __args) {
1749         return __table_.__emplace_hint_multi(__p.__i_, _VSTD::forward<_Args>(__args)...);
1750     }
1751 #endif  // _LIBCPP_CXX03_LANG
1752
1753
1754     _LIBCPP_INLINE_VISIBILITY
1755     iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);}
1756     _LIBCPP_INLINE_VISIBILITY
1757     iterator erase(iterator __p)       {return __table_.erase(__p.__i_);}
1758     _LIBCPP_INLINE_VISIBILITY
1759     size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
1760     _LIBCPP_INLINE_VISIBILITY
1761     iterator erase(const_iterator __first, const_iterator __last)
1762         {return __table_.erase(__first.__i_, __last.__i_);}
1763     _LIBCPP_INLINE_VISIBILITY
1764     void clear() _NOEXCEPT {__table_.clear();}
1765
1766     _LIBCPP_INLINE_VISIBILITY
1767     void swap(unordered_multimap& __u)
1768         _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
1769         {__table_.swap(__u.__table_);}
1770
1771     _LIBCPP_INLINE_VISIBILITY
1772     hasher hash_function() const
1773         {return __table_.hash_function().hash_function();}
1774     _LIBCPP_INLINE_VISIBILITY
1775     key_equal key_eq() const
1776         {return __table_.key_eq().key_eq();}
1777
1778     _LIBCPP_INLINE_VISIBILITY
1779     iterator       find(const key_type& __k)       {return __table_.find(__k);}
1780     _LIBCPP_INLINE_VISIBILITY
1781     const_iterator find(const key_type& __k) const {return __table_.find(__k);}
1782     _LIBCPP_INLINE_VISIBILITY
1783     size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
1784     _LIBCPP_INLINE_VISIBILITY
1785     pair<iterator, iterator>             equal_range(const key_type& __k)
1786         {return __table_.__equal_range_multi(__k);}
1787     _LIBCPP_INLINE_VISIBILITY
1788     pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
1789         {return __table_.__equal_range_multi(__k);}
1790
1791     _LIBCPP_INLINE_VISIBILITY
1792     size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
1793     _LIBCPP_INLINE_VISIBILITY
1794     size_type max_bucket_count() const _NOEXCEPT
1795         {return __table_.max_bucket_count();}
1796
1797     _LIBCPP_INLINE_VISIBILITY
1798     size_type bucket_size(size_type __n) const
1799         {return __table_.bucket_size(__n);}
1800     _LIBCPP_INLINE_VISIBILITY
1801     size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
1802
1803     _LIBCPP_INLINE_VISIBILITY
1804     local_iterator       begin(size_type __n)        {return __table_.begin(__n);}
1805     _LIBCPP_INLINE_VISIBILITY
1806     local_iterator       end(size_type __n)          {return __table_.end(__n);}
1807     _LIBCPP_INLINE_VISIBILITY
1808     const_local_iterator begin(size_type __n) const  {return __table_.cbegin(__n);}
1809     _LIBCPP_INLINE_VISIBILITY
1810     const_local_iterator end(size_type __n) const    {return __table_.cend(__n);}
1811     _LIBCPP_INLINE_VISIBILITY
1812     const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
1813     _LIBCPP_INLINE_VISIBILITY
1814     const_local_iterator cend(size_type __n) const   {return __table_.cend(__n);}
1815
1816     _LIBCPP_INLINE_VISIBILITY
1817     float load_factor() const _NOEXCEPT {return __table_.load_factor();}
1818     _LIBCPP_INLINE_VISIBILITY
1819     float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
1820     _LIBCPP_INLINE_VISIBILITY
1821     void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
1822     _LIBCPP_INLINE_VISIBILITY
1823     void rehash(size_type __n) {__table_.rehash(__n);}
1824     _LIBCPP_INLINE_VISIBILITY
1825     void reserve(size_type __n) {__table_.reserve(__n);}
1826
1827 #if _LIBCPP_DEBUG_LEVEL >= 2
1828
1829     bool __dereferenceable(const const_iterator* __i) const
1830         {return __table_.__dereferenceable(&__i->__i_);}
1831     bool __decrementable(const const_iterator* __i) const
1832         {return __table_.__decrementable(&__i->__i_);}
1833     bool __addable(const const_iterator* __i, ptrdiff_t __n) const
1834         {return __table_.__addable(&__i->__i_, __n);}
1835     bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
1836         {return __table_.__addable(&__i->__i_, __n);}
1837
1838 #endif  // _LIBCPP_DEBUG_LEVEL >= 2
1839
1840
1841 };
1842
1843 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1844 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1845         size_type __n, const hasher& __hf, const key_equal& __eql)
1846     : __table_(__hf, __eql)
1847 {
1848 #if _LIBCPP_DEBUG_LEVEL >= 2
1849     __get_db()->__insert_c(this);
1850 #endif
1851     __table_.rehash(__n);
1852 }
1853
1854 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1855 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1856         size_type __n, const hasher& __hf, const key_equal& __eql,
1857         const allocator_type& __a)
1858     : __table_(__hf, __eql, typename __table::allocator_type(__a))
1859 {
1860 #if _LIBCPP_DEBUG_LEVEL >= 2
1861     __get_db()->__insert_c(this);
1862 #endif
1863     __table_.rehash(__n);
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)
1870 {
1871 #if _LIBCPP_DEBUG_LEVEL >= 2
1872     __get_db()->__insert_c(this);
1873 #endif
1874     insert(__first, __last);
1875 }
1876
1877 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1878 template <class _InputIterator>
1879 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1880         _InputIterator __first, _InputIterator __last, size_type __n,
1881         const hasher& __hf, const key_equal& __eql)
1882     : __table_(__hf, __eql)
1883 {
1884 #if _LIBCPP_DEBUG_LEVEL >= 2
1885     __get_db()->__insert_c(this);
1886 #endif
1887     __table_.rehash(__n);
1888     insert(__first, __last);
1889 }
1890
1891 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1892 template <class _InputIterator>
1893 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1894         _InputIterator __first, _InputIterator __last, size_type __n,
1895         const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1896     : __table_(__hf, __eql, typename __table::allocator_type(__a))
1897 {
1898 #if _LIBCPP_DEBUG_LEVEL >= 2
1899     __get_db()->__insert_c(this);
1900 #endif
1901     __table_.rehash(__n);
1902     insert(__first, __last);
1903 }
1904
1905 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1906 inline
1907 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1908         const allocator_type& __a)
1909     : __table_(typename __table::allocator_type(__a))
1910 {
1911 #if _LIBCPP_DEBUG_LEVEL >= 2
1912     __get_db()->__insert_c(this);
1913 #endif
1914 }
1915
1916 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1917 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1918         const unordered_multimap& __u)
1919     : __table_(__u.__table_)
1920 {
1921 #if _LIBCPP_DEBUG_LEVEL >= 2
1922     __get_db()->__insert_c(this);
1923 #endif
1924     __table_.rehash(__u.bucket_count());
1925     insert(__u.begin(), __u.end());
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         const unordered_multimap& __u, const allocator_type& __a)
1931     : __table_(__u.__table_, typename __table::allocator_type(__a))
1932 {
1933 #if _LIBCPP_DEBUG_LEVEL >= 2
1934     __get_db()->__insert_c(this);
1935 #endif
1936     __table_.rehash(__u.bucket_count());
1937     insert(__u.begin(), __u.end());
1938 }
1939
1940 #ifndef _LIBCPP_CXX03_LANG
1941
1942 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1943 inline
1944 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1945         unordered_multimap&& __u)
1946     _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
1947     : __table_(_VSTD::move(__u.__table_))
1948 {
1949 #if _LIBCPP_DEBUG_LEVEL >= 2
1950     __get_db()->__insert_c(this);
1951     __get_db()->swap(this, &__u);
1952 #endif
1953 }
1954
1955 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1956 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1957         unordered_multimap&& __u, const allocator_type& __a)
1958     : __table_(_VSTD::move(__u.__table_), typename __table::allocator_type(__a))
1959 {
1960 #if _LIBCPP_DEBUG_LEVEL >= 2
1961     __get_db()->__insert_c(this);
1962 #endif
1963     if (__a != __u.get_allocator())
1964     {
1965         iterator __i = __u.begin();
1966         while (__u.size() != 0)
1967         {
1968             __table_.__insert_multi(
1969                 __u.__table_.remove((__i++).__i_)->__value_.__move());
1970         }
1971     }
1972 #if _LIBCPP_DEBUG_LEVEL >= 2
1973     else
1974         __get_db()->swap(this, &__u);
1975 #endif
1976 }
1977
1978 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1979 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1980         initializer_list<value_type> __il)
1981 {
1982 #if _LIBCPP_DEBUG_LEVEL >= 2
1983     __get_db()->__insert_c(this);
1984 #endif
1985     insert(__il.begin(), __il.end());
1986 }
1987
1988 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1989 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1990         initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1991         const key_equal& __eql)
1992     : __table_(__hf, __eql)
1993 {
1994 #if _LIBCPP_DEBUG_LEVEL >= 2
1995     __get_db()->__insert_c(this);
1996 #endif
1997     __table_.rehash(__n);
1998     insert(__il.begin(), __il.end());
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         initializer_list<value_type> __il, size_type __n, const hasher& __hf,
2004         const key_equal& __eql, const allocator_type& __a)
2005     : __table_(__hf, __eql, typename __table::allocator_type(__a))
2006 {
2007 #if _LIBCPP_DEBUG_LEVEL >= 2
2008     __get_db()->__insert_c(this);
2009 #endif
2010     __table_.rehash(__n);
2011     insert(__il.begin(), __il.end());
2012 }
2013
2014 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2015 inline
2016 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
2017 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_multimap&& __u)
2018     _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
2019 {
2020     __table_ = _VSTD::move(__u.__table_);
2021     return *this;
2022 }
2023
2024 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2025 inline
2026 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
2027 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(
2028         initializer_list<value_type> __il)
2029 {
2030     __table_.__assign_multi(__il.begin(), __il.end());
2031     return *this;
2032 }
2033
2034 #endif  // _LIBCPP_CXX03_LANG
2035
2036
2037
2038 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2039 template <class _InputIterator>
2040 inline
2041 void
2042 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
2043                                                             _InputIterator __last)
2044 {
2045     for (; __first != __last; ++__first)
2046         __table_.__insert_multi(*__first);
2047 }
2048
2049 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2050 inline _LIBCPP_INLINE_VISIBILITY
2051 void
2052 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2053      unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2054     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
2055 {
2056     __x.swap(__y);
2057 }
2058
2059 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2060 bool
2061 operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2062            const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2063 {
2064     if (__x.size() != __y.size())
2065         return false;
2066     typedef typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
2067                                                                  const_iterator;
2068     typedef pair<const_iterator, const_iterator> _EqRng;
2069     for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;)
2070     {
2071         _EqRng __xeq = __x.equal_range(__i->first);
2072         _EqRng __yeq = __y.equal_range(__i->first);
2073         if (_VSTD::distance(__xeq.first, __xeq.second) !=
2074             _VSTD::distance(__yeq.first, __yeq.second) ||
2075                   !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first))
2076             return false;
2077         __i = __xeq.second;
2078     }
2079     return true;
2080 }
2081
2082 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2083 inline _LIBCPP_INLINE_VISIBILITY
2084 bool
2085 operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2086            const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2087 {
2088     return !(__x == __y);
2089 }
2090
2091 _LIBCPP_END_NAMESPACE_STD
2092
2093 #endif  // _LIBCPP_UNORDERED_MAP