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.__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_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_.__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_CXX03_LANG
 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     unordered_map(initializer_list<value_type> __il);
 828     unordered_map(initializer_list<value_type> __il, size_type __n,
 829                   const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
 830     unordered_map(initializer_list<value_type> __il, size_type __n,
 831                   const hasher& __hf, const key_equal& __eql,
 832                   const allocator_type& __a);
 833 #endif  // _LIBCPP_CXX03_LANG
 834 #if _LIBCPP_STD_VER > 11
 835     _LIBCPP_INLINE_VISIBILITY
 836     unordered_map(size_type __n, const allocator_type& __a)
 837       : unordered_map(__n, hasher(), key_equal(), __a) {}
 838     _LIBCPP_INLINE_VISIBILITY
 839     unordered_map(size_type __n, const hasher& __hf, const allocator_type& __a)
 840       : unordered_map(__n, __hf, key_equal(), __a) {}
 841     template <class _InputIterator>
 842     _LIBCPP_INLINE_VISIBILITY
 843       unordered_map(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a)
 844       : unordered_map(__first, __last, __n, hasher(), key_equal(), __a) {}
 845     template <class _InputIterator>
 846     _LIBCPP_INLINE_VISIBILITY
 847       unordered_map(_InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf,
 848         const allocator_type& __a)
 849       : unordered_map(__first, __last, __n, __hf, key_equal(), __a) {}
 850     _LIBCPP_INLINE_VISIBILITY
 851     unordered_map(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)
 852       : unordered_map(__il, __n, hasher(), key_equal(), __a) {}
 853     _LIBCPP_INLINE_VISIBILITY
 854     unordered_map(initializer_list<value_type> __il, size_type __n, const hasher& __hf,
 855       const allocator_type& __a)
 856       : unordered_map(__il, __n, __hf, key_equal(), __a) {}
 857 #endif
 858     // ~unordered_map() = default;
 859     _LIBCPP_INLINE_VISIBILITY
 860     unordered_map& operator=(const unordered_map& __u)
 861     {
 862 #ifndef _LIBCPP_CXX03_LANG
 863         __table_ = __u.__table_;
 864 #else
 865         if (this != &__u) {
 866             __table_.clear();
 867             __table_.hash_function() = __u.__table_.hash_function();
 868             __table_.key_eq() = __u.__table_.key_eq();
 869             __table_.max_load_factor() = __u.__table_.max_load_factor();
 870             __table_.__copy_assign_alloc(__u.__table_);
 871             insert(__u.begin(), __u.end());
 872         }
 873 #endif
 874         return *this;
 875     }
 876 #ifndef _LIBCPP_CXX03_LANG
 877     _LIBCPP_INLINE_VISIBILITY
 878     unordered_map& operator=(unordered_map&& __u)
 879         _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
 880     _LIBCPP_INLINE_VISIBILITY
 881     unordered_map& operator=(initializer_list<value_type> __il);
 882 #endif  // _LIBCPP_CXX03_LANG
 883
 884     _LIBCPP_INLINE_VISIBILITY
 885     allocator_type get_allocator() const _NOEXCEPT
 886         {return allocator_type(__table_.__node_alloc());}
 887
 888     _LIBCPP_INLINE_VISIBILITY
 889     bool      empty() const _NOEXCEPT {return __table_.size() == 0;}
 890     _LIBCPP_INLINE_VISIBILITY
 891     size_type size() const _NOEXCEPT  {return __table_.size();}
 892     _LIBCPP_INLINE_VISIBILITY
 893     size_type max_size() const _NOEXCEPT {return __table_.max_size();}
 894
 895     _LIBCPP_INLINE_VISIBILITY
 896     iterator       begin() _NOEXCEPT        {return __table_.begin();}
 897     _LIBCPP_INLINE_VISIBILITY
 898     iterator       end() _NOEXCEPT          {return __table_.end();}
 899     _LIBCPP_INLINE_VISIBILITY
 900     const_iterator begin()  const _NOEXCEPT {return __table_.begin();}
 901     _LIBCPP_INLINE_VISIBILITY
 902     const_iterator end()    const _NOEXCEPT {return __table_.end();}
 903     _LIBCPP_INLINE_VISIBILITY
 904     const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
 905     _LIBCPP_INLINE_VISIBILITY
 906     const_iterator cend()   const _NOEXCEPT {return __table_.end();}
 907
 908     _LIBCPP_INLINE_VISIBILITY
 909     pair<iterator, bool> insert(const value_type& __x)
 910         {return __table_.__insert_unique(__x);}
 911
 912     iterator insert(const_iterator __p, const value_type& __x) {
 913 #if _LIBCPP_DEBUG_LEVEL >= 2
 914         _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
 915             "unordered_map::insert(const_iterator, const value_type&) called with an iterator not"
 916             " referring to this unordered_map");
 917 #else
 918         ((void)__p);
 919 #endif
 920         return insert(__x).first;
 921     }
 922
 923     template <class _InputIterator>
 924         _LIBCPP_INLINE_VISIBILITY
 925         void insert(_InputIterator __first, _InputIterator __last);
 926
 927 #ifndef _LIBCPP_CXX03_LANG
 928     _LIBCPP_INLINE_VISIBILITY
 929     void insert(initializer_list<value_type> __il)
 930         {insert(__il.begin(), __il.end());}
 931
 932     _LIBCPP_INLINE_VISIBILITY
 933     pair<iterator, bool> insert(value_type&& __x)
 934         {return __table_.__insert_unique(_VSTD::move(__x));}
 935
 936     iterator insert(const_iterator __p, value_type&& __x) {
 937 #if _LIBCPP_DEBUG_LEVEL >= 2
 938         _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
 939             "unordered_map::insert(const_iterator, const value_type&) called with an iterator not"
 940             " referring to this unordered_map");
 941 #else
 942         ((void)__p);
 943 #endif
 944         return __table_.__insert_unique(_VSTD::move(__x)).first;
 945     }
 946
 947     template <class _Pp,
 948               class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
 949         _LIBCPP_INLINE_VISIBILITY
 950         pair<iterator, bool> insert(_Pp&& __x)
 951             {return __table_.__insert_unique(_VSTD::forward<_Pp>(__x));}
 952
 953     template <class _Pp,
 954               class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
 955         _LIBCPP_INLINE_VISIBILITY
 956         iterator insert(const_iterator __p, _Pp&& __x)
 957         {
 958 #if _LIBCPP_DEBUG_LEVEL >= 2
 959             _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
 960                 "unordered_map::insert(const_iterator, value_type&&) called with an iterator not"
 961                 " referring to this unordered_map");
 962 #else
 963           ((void)__p);
 964 #endif
 965             return insert(_VSTD::forward<_Pp>(__x)).first;
 966         }
 967
 968     template <class... _Args>
 969     _LIBCPP_INLINE_VISIBILITY
 970     pair<iterator, bool> emplace(_Args&&... __args) {
 971         return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...);
 972     }
 973
 974     template <class... _Args>
 975     _LIBCPP_INLINE_VISIBILITY
 976     iterator emplace_hint(const_iterator __p, _Args&&... __args) {
 977 #if _LIBCPP_DEBUG_LEVEL >= 2
 978         _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
 979             "unordered_map::emplace_hint(const_iterator, args...) called with an iterator not"
 980             " referring to this unordered_map");
 981 #else
 982           ((void)__p);
 983 #endif
 984         return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first;
 985     }
 986
 987 #endif  // _LIBCPP_CXX03_LANG
 988
 989 #if _LIBCPP_STD_VER > 14
 990     template <class... _Args>
 991         _LIBCPP_INLINE_VISIBILITY
 992         pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args)
 993     {
 994         return __table_.__emplace_unique_key_args(__k, _VSTD::piecewise_construct,
 995             _VSTD::forward_as_tuple(__k),
 996             _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
 997     }
 998
 999     template <class... _Args>
1000         _LIBCPP_INLINE_VISIBILITY
1001         pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args)
1002     {
1003         return __table_.__emplace_unique_key_args(__k, _VSTD::piecewise_construct,
1004             _VSTD::forward_as_tuple(_VSTD::move(__k)),
1005             _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
1006     }
1007
1008     template <class... _Args>
1009         _LIBCPP_INLINE_VISIBILITY
1010         iterator try_emplace(const_iterator __h, const key_type& __k, _Args&&... __args)
1011     {
1012 #if _LIBCPP_DEBUG_LEVEL >= 2
1013         _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__h) == this,
1014             "unordered_map::try_emplace(const_iterator, key, args...) called with an iterator not"
1015             " referring to this unordered_map");
1016 #else
1017         ((void)__h);
1018 #endif
1019         return try_emplace(__k, _VSTD::forward<_Args>(__args)...).first;
1020     }
1021
1022     template <class... _Args>
1023         _LIBCPP_INLINE_VISIBILITY
1024         iterator try_emplace(const_iterator __h, key_type&& __k, _Args&&... __args)
1025     {
1026 #if _LIBCPP_DEBUG_LEVEL >= 2
1027         _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__h) == this,
1028             "unordered_map::try_emplace(const_iterator, key, args...) called with an iterator not"
1029             " referring to this unordered_map");
1030 #else
1031         ((void)__h);
1032 #endif
1033         return try_emplace(_VSTD::move(__k), _VSTD::forward<_Args>(__args)...).first;
1034     }
1035
1036     template <class _Vp>
1037         _LIBCPP_INLINE_VISIBILITY
1038         pair<iterator, bool> insert_or_assign(const key_type& __k, _Vp&& __v)
1039     {
1040         pair<iterator, bool> __res = __table_.__emplace_unique_key_args(__k,
1041             __k, _VSTD::forward<_Vp>(__v));
1042         if (!__res.second) {
1043             __res.first->second = _VSTD::forward<_Vp>(__v);
1044         }
1045         return __res;
1046     }
1047
1048     template <class _Vp>
1049         _LIBCPP_INLINE_VISIBILITY
1050         pair<iterator, bool> insert_or_assign(key_type&& __k, _Vp&& __v)
1051     {
1052         pair<iterator, bool> __res = __table_.__emplace_unique_key_args(__k,
1053             _VSTD::move(__k), _VSTD::forward<_Vp>(__v));
1054         if (!__res.second) {
1055             __res.first->second = _VSTD::forward<_Vp>(__v);
1056         }
1057         return __res;
1058     }
1059
1060     template <class _Vp>
1061         _LIBCPP_INLINE_VISIBILITY
1062         iterator insert_or_assign(const_iterator, const key_type& __k, _Vp&& __v)
1063      {
1064           // FIXME: Add debug mode checking for the iterator input
1065           return insert_or_assign(__k, _VSTD::forward<_Vp>(__v)).first;
1066      }
1067
1068     template <class _Vp>
1069         _LIBCPP_INLINE_VISIBILITY
1070         iterator insert_or_assign(const_iterator, key_type&& __k, _Vp&& __v)
1071      {
1072         // FIXME: Add debug mode checking for the iterator input
1073         return insert_or_assign(_VSTD::move(__k), _VSTD::forward<_Vp>(__v)).first;
1074      }
1075 #endif // _LIBCPP_STD_VER > 14
1076
1077     _LIBCPP_INLINE_VISIBILITY
1078     iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);}
1079     _LIBCPP_INLINE_VISIBILITY
1080     iterator erase(iterator __p)       {return __table_.erase(__p.__i_);}
1081     _LIBCPP_INLINE_VISIBILITY
1082     size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
1083     _LIBCPP_INLINE_VISIBILITY
1084     iterator erase(const_iterator __first, const_iterator __last)
1085         {return __table_.erase(__first.__i_, __last.__i_);}
1086     _LIBCPP_INLINE_VISIBILITY
1087     void clear() _NOEXCEPT {__table_.clear();}
1088
1089     _LIBCPP_INLINE_VISIBILITY
1090     void swap(unordered_map& __u)
1091         _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
1092         { __table_.swap(__u.__table_);}
1093
1094     _LIBCPP_INLINE_VISIBILITY
1095     hasher hash_function() const
1096         {return __table_.hash_function().hash_function();}
1097     _LIBCPP_INLINE_VISIBILITY
1098     key_equal key_eq() const
1099         {return __table_.key_eq().key_eq();}
1100
1101     _LIBCPP_INLINE_VISIBILITY
1102     iterator       find(const key_type& __k)       {return __table_.find(__k);}
1103     _LIBCPP_INLINE_VISIBILITY
1104     const_iterator find(const key_type& __k) const {return __table_.find(__k);}
1105     _LIBCPP_INLINE_VISIBILITY
1106     size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
1107     _LIBCPP_INLINE_VISIBILITY
1108     pair<iterator, iterator>             equal_range(const key_type& __k)
1109         {return __table_.__equal_range_unique(__k);}
1110     _LIBCPP_INLINE_VISIBILITY
1111     pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
1112         {return __table_.__equal_range_unique(__k);}
1113
1114     mapped_type& operator[](const key_type& __k);
1115 #ifndef _LIBCPP_CXX03_LANG
1116     mapped_type& operator[](key_type&& __k);
1117 #endif
1118
1119     mapped_type&       at(const key_type& __k);
1120     const mapped_type& at(const key_type& __k) const;
1121
1122     _LIBCPP_INLINE_VISIBILITY
1123     size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
1124     _LIBCPP_INLINE_VISIBILITY
1125     size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
1126
1127     _LIBCPP_INLINE_VISIBILITY
1128     size_type bucket_size(size_type __n) const
1129         {return __table_.bucket_size(__n);}
1130     _LIBCPP_INLINE_VISIBILITY
1131     size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
1132
1133     _LIBCPP_INLINE_VISIBILITY
1134     local_iterator       begin(size_type __n)        {return __table_.begin(__n);}
1135     _LIBCPP_INLINE_VISIBILITY
1136     local_iterator       end(size_type __n)          {return __table_.end(__n);}
1137     _LIBCPP_INLINE_VISIBILITY
1138     const_local_iterator begin(size_type __n) const  {return __table_.cbegin(__n);}
1139     _LIBCPP_INLINE_VISIBILITY
1140     const_local_iterator end(size_type __n) const    {return __table_.cend(__n);}
1141     _LIBCPP_INLINE_VISIBILITY
1142     const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
1143     _LIBCPP_INLINE_VISIBILITY
1144     const_local_iterator cend(size_type __n) const   {return __table_.cend(__n);}
1145
1146     _LIBCPP_INLINE_VISIBILITY
1147     float load_factor() const _NOEXCEPT {return __table_.load_factor();}
1148     _LIBCPP_INLINE_VISIBILITY
1149     float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
1150     _LIBCPP_INLINE_VISIBILITY
1151     void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
1152     _LIBCPP_INLINE_VISIBILITY
1153     void rehash(size_type __n) {__table_.rehash(__n);}
1154     _LIBCPP_INLINE_VISIBILITY
1155     void reserve(size_type __n) {__table_.reserve(__n);}
1156
1157 #if _LIBCPP_DEBUG_LEVEL >= 2
1158
1159     bool __dereferenceable(const const_iterator* __i) const
1160         {return __table_.__dereferenceable(&__i->__i_);}
1161     bool __decrementable(const const_iterator* __i) const
1162         {return __table_.__decrementable(&__i->__i_);}
1163     bool __addable(const const_iterator* __i, ptrdiff_t __n) const
1164         {return __table_.__addable(&__i->__i_, __n);}
1165     bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
1166         {return __table_.__addable(&__i->__i_, __n);}
1167
1168 #endif  // _LIBCPP_DEBUG_LEVEL >= 2
1169
1170 private:
1171
1172 #ifdef _LIBCPP_CXX03_LANG
1173     __node_holder __construct_node_with_key(const key_type& __k);
1174 #endif
1175 };
1176
1177 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1178 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1179         size_type __n, const hasher& __hf, const key_equal& __eql)
1180     : __table_(__hf, __eql)
1181 {
1182 #if _LIBCPP_DEBUG_LEVEL >= 2
1183     __get_db()->__insert_c(this);
1184 #endif
1185     __table_.rehash(__n);
1186 }
1187
1188 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1189 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1190         size_type __n, const hasher& __hf, const key_equal& __eql,
1191         const allocator_type& __a)
1192     : __table_(__hf, __eql, typename __table::allocator_type(__a))
1193 {
1194 #if _LIBCPP_DEBUG_LEVEL >= 2
1195     __get_db()->__insert_c(this);
1196 #endif
1197     __table_.rehash(__n);
1198 }
1199
1200 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1201 inline
1202 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1203         const allocator_type& __a)
1204     : __table_(typename __table::allocator_type(__a))
1205 {
1206 #if _LIBCPP_DEBUG_LEVEL >= 2
1207     __get_db()->__insert_c(this);
1208 #endif
1209 }
1210
1211 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1212 template <class _InputIterator>
1213 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1214         _InputIterator __first, _InputIterator __last)
1215 {
1216 #if _LIBCPP_DEBUG_LEVEL >= 2
1217     __get_db()->__insert_c(this);
1218 #endif
1219     insert(__first, __last);
1220 }
1221
1222 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1223 template <class _InputIterator>
1224 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1225         _InputIterator __first, _InputIterator __last, size_type __n,
1226         const hasher& __hf, const key_equal& __eql)
1227     : __table_(__hf, __eql)
1228 {
1229 #if _LIBCPP_DEBUG_LEVEL >= 2
1230     __get_db()->__insert_c(this);
1231 #endif
1232     __table_.rehash(__n);
1233     insert(__first, __last);
1234 }
1235
1236 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1237 template <class _InputIterator>
1238 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1239         _InputIterator __first, _InputIterator __last, size_type __n,
1240         const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1241     : __table_(__hf, __eql, typename __table::allocator_type(__a))
1242 {
1243 #if _LIBCPP_DEBUG_LEVEL >= 2
1244     __get_db()->__insert_c(this);
1245 #endif
1246     __table_.rehash(__n);
1247     insert(__first, __last);
1248 }
1249
1250 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1251 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1252         const unordered_map& __u)
1253     : __table_(__u.__table_)
1254 {
1255 #if _LIBCPP_DEBUG_LEVEL >= 2
1256     __get_db()->__insert_c(this);
1257 #endif
1258     __table_.rehash(__u.bucket_count());
1259     insert(__u.begin(), __u.end());
1260 }
1261
1262 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1263 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1264         const unordered_map& __u, const allocator_type& __a)
1265     : __table_(__u.__table_, typename __table::allocator_type(__a))
1266 {
1267 #if _LIBCPP_DEBUG_LEVEL >= 2
1268     __get_db()->__insert_c(this);
1269 #endif
1270     __table_.rehash(__u.bucket_count());
1271     insert(__u.begin(), __u.end());
1272 }
1273
1274 #ifndef _LIBCPP_CXX03_LANG
1275
1276 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1277 inline
1278 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1279         unordered_map&& __u)
1280     _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
1281     : __table_(_VSTD::move(__u.__table_))
1282 {
1283 #if _LIBCPP_DEBUG_LEVEL >= 2
1284     __get_db()->__insert_c(this);
1285     __get_db()->swap(this, &__u);
1286 #endif
1287 }
1288
1289 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1290 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1291         unordered_map&& __u, const allocator_type& __a)
1292     : __table_(_VSTD::move(__u.__table_), typename __table::allocator_type(__a))
1293 {
1294 #if _LIBCPP_DEBUG_LEVEL >= 2
1295     __get_db()->__insert_c(this);
1296 #endif
1297     if (__a != __u.get_allocator())
1298     {
1299         iterator __i = __u.begin();
1300         while (__u.size() != 0) {
1301             __table_.__emplace_unique(_VSTD::move(
1302                 __u.__table_.remove((__i++).__i_)->__value_.__nc));
1303         }
1304     }
1305 #if _LIBCPP_DEBUG_LEVEL >= 2
1306     else
1307         __get_db()->swap(this, &__u);
1308 #endif
1309 }
1310
1311 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1312 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1313         initializer_list<value_type> __il)
1314 {
1315 #if _LIBCPP_DEBUG_LEVEL >= 2
1316     __get_db()->__insert_c(this);
1317 #endif
1318     insert(__il.begin(), __il.end());
1319 }
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, size_type __n, const hasher& __hf,
1324         const key_equal& __eql)
1325     : __table_(__hf, __eql)
1326 {
1327 #if _LIBCPP_DEBUG_LEVEL >= 2
1328     __get_db()->__insert_c(this);
1329 #endif
1330     __table_.rehash(__n);
1331     insert(__il.begin(), __il.end());
1332 }
1333
1334 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1335 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1336         initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1337         const key_equal& __eql, const allocator_type& __a)
1338     : __table_(__hf, __eql, typename __table::allocator_type(__a))
1339 {
1340 #if _LIBCPP_DEBUG_LEVEL >= 2
1341     __get_db()->__insert_c(this);
1342 #endif
1343     __table_.rehash(__n);
1344     insert(__il.begin(), __il.end());
1345 }
1346
1347 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1348 inline
1349 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
1350 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_map&& __u)
1351     _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
1352 {
1353     __table_ = _VSTD::move(__u.__table_);
1354     return *this;
1355 }
1356
1357 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1358 inline
1359 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
1360 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(
1361         initializer_list<value_type> __il)
1362 {
1363     __table_.__assign_unique(__il.begin(), __il.end());
1364     return *this;
1365 }
1366
1367 #endif  // _LIBCPP_CXX03_LANG
1368
1369 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1370 template <class _InputIterator>
1371 inline
1372 void
1373 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
1374                                                        _InputIterator __last)
1375 {
1376     for (; __first != __last; ++__first)
1377         __table_.__insert_unique(*__first);
1378 }
1379
1380 #ifndef _LIBCPP_CXX03_LANG
1381
1382 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1383 _Tp&
1384 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k)
1385 {
1386     return __table_.__emplace_unique_key_args(__k,
1387         std::piecewise_construct, std::forward_as_tuple(__k),
1388                                   std::forward_as_tuple()).first->__cc.second;
1389 }
1390
1391 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1392 _Tp&
1393 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&& __k)
1394 {
1395     return __table_.__emplace_unique_key_args(__k,
1396         std::piecewise_construct, std::forward_as_tuple(std::move(__k)),
1397                                   std::forward_as_tuple()).first->__cc.second;
1398 }
1399 #else // _LIBCPP_CXX03_LANG
1400
1401 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1402 typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1403 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(const key_type& __k)
1404 {
1405     __node_allocator& __na = __table_.__node_alloc();
1406     __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1407     __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), __k);
1408     __h.get_deleter().__first_constructed = true;
1409     __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
1410     __h.get_deleter().__second_constructed = true;
1411     return _LIBCPP_EXPLICIT_MOVE(__h);  // explicitly moved for C++03
1412 }
1413
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
1427 #endif  // _LIBCPP_CXX03_MODE
1428
1429 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1430 _Tp&
1431 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k)
1432 {
1433     iterator __i = find(__k);
1434 #ifndef _LIBCPP_NO_EXCEPTIONS
1435     if (__i == end())
1436         throw out_of_range("unordered_map::at: key not found");
1437 #endif  // _LIBCPP_NO_EXCEPTIONS
1438     return __i->second;
1439 }
1440
1441 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1442 const _Tp&
1443 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) const
1444 {
1445     const_iterator __i = find(__k);
1446 #ifndef _LIBCPP_NO_EXCEPTIONS
1447     if (__i == end())
1448         throw out_of_range("unordered_map::at: key not found");
1449 #endif  // _LIBCPP_NO_EXCEPTIONS
1450     return __i->second;
1451 }
1452
1453 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1454 inline _LIBCPP_INLINE_VISIBILITY
1455 void
1456 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1457      unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1458     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1459 {
1460     __x.swap(__y);
1461 }
1462
1463 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1464 bool
1465 operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1466            const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1467 {
1468     if (__x.size() != __y.size())
1469         return false;
1470     typedef typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
1471                                                                  const_iterator;
1472     for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();
1473             __i != __ex; ++__i)
1474     {
1475         const_iterator __j = __y.find(__i->first);
1476         if (__j == __ey || !(*__i == *__j))
1477             return false;
1478     }
1479     return true;
1480 }
1481
1482 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1483 inline _LIBCPP_INLINE_VISIBILITY
1484 bool
1485 operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1486            const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1487 {
1488     return !(__x == __y);
1489 }
1490
1491 template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
1492           class _Alloc = allocator<pair<const _Key, _Tp> > >
1493 class _LIBCPP_TEMPLATE_VIS unordered_multimap
1494 {
1495 public:
1496     // types
1497     typedef _Key                                           key_type;
1498     typedef _Tp                                            mapped_type;
1499     typedef _Hash                                          hasher;
1500     typedef _Pred                                          key_equal;
1501     typedef _Alloc                                         allocator_type;
1502     typedef pair<const key_type, mapped_type>              value_type;
1503     typedef pair<key_type, mapped_type>                    __nc_value_type;
1504     typedef value_type&                                    reference;
1505     typedef const value_type&                              const_reference;
1506     static_assert((is_same<value_type, typename allocator_type::value_type>::value),
1507                   "Invalid allocator::value_type");
1508
1509 private:
1510     typedef __hash_value_type<key_type, mapped_type>                 __value_type;
1511     typedef __unordered_map_hasher<key_type, __value_type, hasher>   __hasher;
1512     typedef __unordered_map_equal<key_type, __value_type, key_equal> __key_equal;
1513     typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>,
1514                                                  __value_type>::type __allocator_type;
1515
1516     typedef __hash_table<__value_type, __hasher,
1517                          __key_equal,  __allocator_type>   __table;
1518
1519     __table __table_;
1520
1521     typedef typename __table::_NodeTypes                   _NodeTypes;
1522     typedef typename __table::__node_traits                __node_traits;
1523     typedef typename __table::__node_allocator             __node_allocator;
1524     typedef typename __table::__node                       __node;
1525     typedef __hash_map_node_destructor<__node_allocator>   _Dp;
1526     typedef unique_ptr<__node, _Dp>                         __node_holder;
1527     typedef allocator_traits<allocator_type>               __alloc_traits;
1528     static_assert((is_same<typename __node_traits::size_type,
1529                           typename __alloc_traits::size_type>::value),
1530                  "Allocator uses different size_type for different types");
1531 public:
1532     typedef typename __alloc_traits::pointer         pointer;
1533     typedef typename __alloc_traits::const_pointer   const_pointer;
1534     typedef typename __table::size_type              size_type;
1535     typedef typename __table::difference_type        difference_type;
1536
1537     typedef __hash_map_iterator<typename __table::iterator>       iterator;
1538     typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
1539     typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
1540     typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
1541
1542     _LIBCPP_INLINE_VISIBILITY
1543     unordered_multimap()
1544         _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
1545         {
1546 #if _LIBCPP_DEBUG_LEVEL >= 2
1547             __get_db()->__insert_c(this);
1548 #endif
1549         }
1550     explicit unordered_multimap(size_type __n, const hasher& __hf = hasher(),
1551                                 const key_equal& __eql = key_equal());
1552     unordered_multimap(size_type __n, const hasher& __hf,
1553                                 const key_equal& __eql,
1554                                 const allocator_type& __a);
1555     template <class _InputIterator>
1556         unordered_multimap(_InputIterator __first, _InputIterator __last);
1557     template <class _InputIterator>
1558         unordered_multimap(_InputIterator __first, _InputIterator __last,
1559                       size_type __n, const hasher& __hf = hasher(),
1560                       const key_equal& __eql = key_equal());
1561     template <class _InputIterator>
1562         unordered_multimap(_InputIterator __first, _InputIterator __last,
1563                       size_type __n, const hasher& __hf,
1564                       const key_equal& __eql,
1565                       const allocator_type& __a);
1566     _LIBCPP_INLINE_VISIBILITY
1567     explicit unordered_multimap(const allocator_type& __a);
1568     unordered_multimap(const unordered_multimap& __u);
1569     unordered_multimap(const unordered_multimap& __u, const allocator_type& __a);
1570 #ifndef _LIBCPP_CXX03_LANG
1571     _LIBCPP_INLINE_VISIBILITY
1572     unordered_multimap(unordered_multimap&& __u)
1573         _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
1574     unordered_multimap(unordered_multimap&& __u, const allocator_type& __a);
1575     unordered_multimap(initializer_list<value_type> __il);
1576     unordered_multimap(initializer_list<value_type> __il, size_type __n,
1577                        const hasher& __hf = hasher(),
1578                        const key_equal& __eql = key_equal());
1579     unordered_multimap(initializer_list<value_type> __il, size_type __n,
1580                        const hasher& __hf, const key_equal& __eql,
1581                        const allocator_type& __a);
1582 #endif  // _LIBCPP_CXX03_LANG
1583 #if _LIBCPP_STD_VER > 11
1584     _LIBCPP_INLINE_VISIBILITY
1585     unordered_multimap(size_type __n, const allocator_type& __a)
1586       : unordered_multimap(__n, hasher(), key_equal(), __a) {}
1587     _LIBCPP_INLINE_VISIBILITY
1588     unordered_multimap(size_type __n, const hasher& __hf, const allocator_type& __a)
1589       : unordered_multimap(__n, __hf, key_equal(), __a) {}
1590     template <class _InputIterator>
1591     _LIBCPP_INLINE_VISIBILITY
1592       unordered_multimap(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a)
1593       : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a) {}
1594     template <class _InputIterator>
1595     _LIBCPP_INLINE_VISIBILITY
1596       unordered_multimap(_InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf,
1597         const allocator_type& __a)
1598       : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a) {}
1599     _LIBCPP_INLINE_VISIBILITY
1600     unordered_multimap(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)
1601       : unordered_multimap(__il, __n, hasher(), key_equal(), __a) {}
1602     _LIBCPP_INLINE_VISIBILITY
1603     unordered_multimap(initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1604       const allocator_type& __a)
1605       : unordered_multimap(__il, __n, __hf, key_equal(), __a) {}
1606 #endif
1607     // ~unordered_multimap() = default;
1608     _LIBCPP_INLINE_VISIBILITY
1609     unordered_multimap& operator=(const unordered_multimap& __u)
1610     {
1611 #ifndef _LIBCPP_CXX03_LANG
1612         __table_ = __u.__table_;
1613 #else
1614         if (this != &__u) {
1615             __table_.clear();
1616             __table_.hash_function() = __u.__table_.hash_function();
1617             __table_.key_eq() = __u.__table_.key_eq();
1618             __table_.max_load_factor() = __u.__table_.max_load_factor();
1619             __table_.__copy_assign_alloc(__u.__table_);
1620             insert(__u.begin(), __u.end());
1621         }
1622 #endif
1623         return *this;
1624     }
1625 #ifndef _LIBCPP_CXX03_LANG
1626     _LIBCPP_INLINE_VISIBILITY
1627     unordered_multimap& operator=(unordered_multimap&& __u)
1628         _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
1629     _LIBCPP_INLINE_VISIBILITY
1630     unordered_multimap& operator=(initializer_list<value_type> __il);
1631 #endif  // _LIBCPP_CXX03_LANG
1632
1633     _LIBCPP_INLINE_VISIBILITY
1634     allocator_type get_allocator() const _NOEXCEPT
1635         {return allocator_type(__table_.__node_alloc());}
1636
1637     _LIBCPP_INLINE_VISIBILITY
1638     bool      empty() const _NOEXCEPT {return __table_.size() == 0;}
1639     _LIBCPP_INLINE_VISIBILITY
1640     size_type size() const _NOEXCEPT  {return __table_.size();}
1641     _LIBCPP_INLINE_VISIBILITY
1642     size_type max_size() const _NOEXCEPT {return __table_.max_size();}
1643
1644     _LIBCPP_INLINE_VISIBILITY
1645     iterator       begin() _NOEXCEPT        {return __table_.begin();}
1646     _LIBCPP_INLINE_VISIBILITY
1647     iterator       end() _NOEXCEPT          {return __table_.end();}
1648     _LIBCPP_INLINE_VISIBILITY
1649     const_iterator begin()  const _NOEXCEPT {return __table_.begin();}
1650     _LIBCPP_INLINE_VISIBILITY
1651     const_iterator end()    const _NOEXCEPT {return __table_.end();}
1652     _LIBCPP_INLINE_VISIBILITY
1653     const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
1654     _LIBCPP_INLINE_VISIBILITY
1655     const_iterator cend()   const _NOEXCEPT {return __table_.end();}
1656
1657     _LIBCPP_INLINE_VISIBILITY
1658     iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
1659
1660     _LIBCPP_INLINE_VISIBILITY
1661     iterator insert(const_iterator __p, const value_type& __x)
1662         {return __table_.__insert_multi(__p.__i_, __x);}
1663
1664     template <class _InputIterator>
1665     _LIBCPP_INLINE_VISIBILITY
1666     void insert(_InputIterator __first, _InputIterator __last);
1667
1668 #ifndef _LIBCPP_CXX03_LANG
1669     _LIBCPP_INLINE_VISIBILITY
1670     void insert(initializer_list<value_type> __il)
1671         {insert(__il.begin(), __il.end());}
1672     _LIBCPP_INLINE_VISIBILITY
1673     iterator insert(value_type&& __x) {return __table_.__insert_multi(_VSTD::move(__x));}
1674
1675     _LIBCPP_INLINE_VISIBILITY
1676     iterator insert(const_iterator __p, value_type&& __x)
1677         {return __table_.__insert_multi(__p.__i_, _VSTD::move(__x));}
1678
1679     template <class _Pp,
1680               class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1681     _LIBCPP_INLINE_VISIBILITY
1682     iterator insert(_Pp&& __x)
1683         {return __table_.__insert_multi(_VSTD::forward<_Pp>(__x));}
1684
1685     template <class _Pp,
1686               class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1687     _LIBCPP_INLINE_VISIBILITY
1688     iterator insert(const_iterator __p, _Pp&& __x)
1689         {return __table_.__insert_multi(__p.__i_, _VSTD::forward<_Pp>(__x));}
1690
1691     template <class... _Args>
1692     iterator emplace(_Args&&... __args) {
1693         return __table_.__emplace_multi(_VSTD::forward<_Args>(__args)...);
1694     }
1695
1696     template <class... _Args>
1697     iterator emplace_hint(const_iterator __p, _Args&&... __args) {
1698         return __table_.__emplace_hint_multi(__p.__i_, _VSTD::forward<_Args>(__args)...);
1699     }
1700 #endif  // _LIBCPP_CXX03_LANG
1701
1702
1703     _LIBCPP_INLINE_VISIBILITY
1704     iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);}
1705     _LIBCPP_INLINE_VISIBILITY
1706     iterator erase(iterator __p)       {return __table_.erase(__p.__i_);}
1707     _LIBCPP_INLINE_VISIBILITY
1708     size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
1709     _LIBCPP_INLINE_VISIBILITY
1710     iterator erase(const_iterator __first, const_iterator __last)
1711         {return __table_.erase(__first.__i_, __last.__i_);}
1712     _LIBCPP_INLINE_VISIBILITY
1713     void clear() _NOEXCEPT {__table_.clear();}
1714
1715     _LIBCPP_INLINE_VISIBILITY
1716     void swap(unordered_multimap& __u)
1717         _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
1718         {__table_.swap(__u.__table_);}
1719
1720     _LIBCPP_INLINE_VISIBILITY
1721     hasher hash_function() const
1722         {return __table_.hash_function().hash_function();}
1723     _LIBCPP_INLINE_VISIBILITY
1724     key_equal key_eq() const
1725         {return __table_.key_eq().key_eq();}
1726
1727     _LIBCPP_INLINE_VISIBILITY
1728     iterator       find(const key_type& __k)       {return __table_.find(__k);}
1729     _LIBCPP_INLINE_VISIBILITY
1730     const_iterator find(const key_type& __k) const {return __table_.find(__k);}
1731     _LIBCPP_INLINE_VISIBILITY
1732     size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
1733     _LIBCPP_INLINE_VISIBILITY
1734     pair<iterator, iterator>             equal_range(const key_type& __k)
1735         {return __table_.__equal_range_multi(__k);}
1736     _LIBCPP_INLINE_VISIBILITY
1737     pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
1738         {return __table_.__equal_range_multi(__k);}
1739
1740     _LIBCPP_INLINE_VISIBILITY
1741     size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
1742     _LIBCPP_INLINE_VISIBILITY
1743     size_type max_bucket_count() const _NOEXCEPT
1744         {return __table_.max_bucket_count();}
1745
1746     _LIBCPP_INLINE_VISIBILITY
1747     size_type bucket_size(size_type __n) const
1748         {return __table_.bucket_size(__n);}
1749     _LIBCPP_INLINE_VISIBILITY
1750     size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
1751
1752     _LIBCPP_INLINE_VISIBILITY
1753     local_iterator       begin(size_type __n)        {return __table_.begin(__n);}
1754     _LIBCPP_INLINE_VISIBILITY
1755     local_iterator       end(size_type __n)          {return __table_.end(__n);}
1756     _LIBCPP_INLINE_VISIBILITY
1757     const_local_iterator begin(size_type __n) const  {return __table_.cbegin(__n);}
1758     _LIBCPP_INLINE_VISIBILITY
1759     const_local_iterator end(size_type __n) const    {return __table_.cend(__n);}
1760     _LIBCPP_INLINE_VISIBILITY
1761     const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
1762     _LIBCPP_INLINE_VISIBILITY
1763     const_local_iterator cend(size_type __n) const   {return __table_.cend(__n);}
1764
1765     _LIBCPP_INLINE_VISIBILITY
1766     float load_factor() const _NOEXCEPT {return __table_.load_factor();}
1767     _LIBCPP_INLINE_VISIBILITY
1768     float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
1769     _LIBCPP_INLINE_VISIBILITY
1770     void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
1771     _LIBCPP_INLINE_VISIBILITY
1772     void rehash(size_type __n) {__table_.rehash(__n);}
1773     _LIBCPP_INLINE_VISIBILITY
1774     void reserve(size_type __n) {__table_.reserve(__n);}
1775
1776 #if _LIBCPP_DEBUG_LEVEL >= 2
1777
1778     bool __dereferenceable(const const_iterator* __i) const
1779         {return __table_.__dereferenceable(&__i->__i_);}
1780     bool __decrementable(const const_iterator* __i) const
1781         {return __table_.__decrementable(&__i->__i_);}
1782     bool __addable(const const_iterator* __i, ptrdiff_t __n) const
1783         {return __table_.__addable(&__i->__i_, __n);}
1784     bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
1785         {return __table_.__addable(&__i->__i_, __n);}
1786
1787 #endif  // _LIBCPP_DEBUG_LEVEL >= 2
1788
1789
1790 };
1791
1792 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1793 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1794         size_type __n, const hasher& __hf, const key_equal& __eql)
1795     : __table_(__hf, __eql)
1796 {
1797 #if _LIBCPP_DEBUG_LEVEL >= 2
1798     __get_db()->__insert_c(this);
1799 #endif
1800     __table_.rehash(__n);
1801 }
1802
1803 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1804 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1805         size_type __n, const hasher& __hf, const key_equal& __eql,
1806         const allocator_type& __a)
1807     : __table_(__hf, __eql, typename __table::allocator_type(__a))
1808 {
1809 #if _LIBCPP_DEBUG_LEVEL >= 2
1810     __get_db()->__insert_c(this);
1811 #endif
1812     __table_.rehash(__n);
1813 }
1814
1815 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1816 template <class _InputIterator>
1817 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1818         _InputIterator __first, _InputIterator __last)
1819 {
1820 #if _LIBCPP_DEBUG_LEVEL >= 2
1821     __get_db()->__insert_c(this);
1822 #endif
1823     insert(__first, __last);
1824 }
1825
1826 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1827 template <class _InputIterator>
1828 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1829         _InputIterator __first, _InputIterator __last, size_type __n,
1830         const hasher& __hf, const key_equal& __eql)
1831     : __table_(__hf, __eql)
1832 {
1833 #if _LIBCPP_DEBUG_LEVEL >= 2
1834     __get_db()->__insert_c(this);
1835 #endif
1836     __table_.rehash(__n);
1837     insert(__first, __last);
1838 }
1839
1840 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1841 template <class _InputIterator>
1842 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1843         _InputIterator __first, _InputIterator __last, size_type __n,
1844         const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1845     : __table_(__hf, __eql, typename __table::allocator_type(__a))
1846 {
1847 #if _LIBCPP_DEBUG_LEVEL >= 2
1848     __get_db()->__insert_c(this);
1849 #endif
1850     __table_.rehash(__n);
1851     insert(__first, __last);
1852 }
1853
1854 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1855 inline
1856 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1857         const allocator_type& __a)
1858     : __table_(typename __table::allocator_type(__a))
1859 {
1860 #if _LIBCPP_DEBUG_LEVEL >= 2
1861     __get_db()->__insert_c(this);
1862 #endif
1863 }
1864
1865 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1866 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1867         const unordered_multimap& __u)
1868     : __table_(__u.__table_)
1869 {
1870 #if _LIBCPP_DEBUG_LEVEL >= 2
1871     __get_db()->__insert_c(this);
1872 #endif
1873     __table_.rehash(__u.bucket_count());
1874     insert(__u.begin(), __u.end());
1875 }
1876
1877 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1878 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1879         const unordered_multimap& __u, const allocator_type& __a)
1880     : __table_(__u.__table_, typename __table::allocator_type(__a))
1881 {
1882 #if _LIBCPP_DEBUG_LEVEL >= 2
1883     __get_db()->__insert_c(this);
1884 #endif
1885     __table_.rehash(__u.bucket_count());
1886     insert(__u.begin(), __u.end());
1887 }
1888
1889 #ifndef _LIBCPP_CXX03_LANG
1890
1891 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1892 inline
1893 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1894         unordered_multimap&& __u)
1895     _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
1896     : __table_(_VSTD::move(__u.__table_))
1897 {
1898 #if _LIBCPP_DEBUG_LEVEL >= 2
1899     __get_db()->__insert_c(this);
1900     __get_db()->swap(this, &__u);
1901 #endif
1902 }
1903
1904 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1905 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1906         unordered_multimap&& __u, const allocator_type& __a)
1907     : __table_(_VSTD::move(__u.__table_), typename __table::allocator_type(__a))
1908 {
1909 #if _LIBCPP_DEBUG_LEVEL >= 2
1910     __get_db()->__insert_c(this);
1911 #endif
1912     if (__a != __u.get_allocator())
1913     {
1914         iterator __i = __u.begin();
1915         while (__u.size() != 0)
1916         {
1917             __table_.__insert_multi(
1918                       _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_.__nc)
1919                                    );
1920         }
1921     }
1922 #if _LIBCPP_DEBUG_LEVEL >= 2
1923     else
1924         __get_db()->swap(this, &__u);
1925 #endif
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         initializer_list<value_type> __il)
1931 {
1932 #if _LIBCPP_DEBUG_LEVEL >= 2
1933     __get_db()->__insert_c(this);
1934 #endif
1935     insert(__il.begin(), __il.end());
1936 }
1937
1938 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1939 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1940         initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1941         const key_equal& __eql)
1942     : __table_(__hf, __eql)
1943 {
1944 #if _LIBCPP_DEBUG_LEVEL >= 2
1945     __get_db()->__insert_c(this);
1946 #endif
1947     __table_.rehash(__n);
1948     insert(__il.begin(), __il.end());
1949 }
1950
1951 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1952 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1953         initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1954         const key_equal& __eql, const allocator_type& __a)
1955     : __table_(__hf, __eql, typename __table::allocator_type(__a))
1956 {
1957 #if _LIBCPP_DEBUG_LEVEL >= 2
1958     __get_db()->__insert_c(this);
1959 #endif
1960     __table_.rehash(__n);
1961     insert(__il.begin(), __il.end());
1962 }
1963
1964 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1965 inline
1966 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
1967 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_multimap&& __u)
1968     _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
1969 {
1970     __table_ = _VSTD::move(__u.__table_);
1971     return *this;
1972 }
1973
1974 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1975 inline
1976 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
1977 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(
1978         initializer_list<value_type> __il)
1979 {
1980     __table_.__assign_multi(__il.begin(), __il.end());
1981     return *this;
1982 }
1983
1984 #endif  // _LIBCPP_CXX03_LANG
1985
1986
1987
1988 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1989 template <class _InputIterator>
1990 inline
1991 void
1992 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
1993                                                             _InputIterator __last)
1994 {
1995     for (; __first != __last; ++__first)
1996         __table_.__insert_multi(*__first);
1997 }
1998
1999 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2000 inline _LIBCPP_INLINE_VISIBILITY
2001 void
2002 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2003      unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2004     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
2005 {
2006     __x.swap(__y);
2007 }
2008
2009 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2010 bool
2011 operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2012            const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2013 {
2014     if (__x.size() != __y.size())
2015         return false;
2016     typedef typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
2017                                                                  const_iterator;
2018     typedef pair<const_iterator, const_iterator> _EqRng;
2019     for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;)
2020     {
2021         _EqRng __xeq = __x.equal_range(__i->first);
2022         _EqRng __yeq = __y.equal_range(__i->first);
2023         if (_VSTD::distance(__xeq.first, __xeq.second) !=
2024             _VSTD::distance(__yeq.first, __yeq.second) ||
2025                   !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first))
2026             return false;
2027         __i = __xeq.second;
2028     }
2029     return true;
2030 }
2031
2032 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2033 inline _LIBCPP_INLINE_VISIBILITY
2034 bool
2035 operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2036            const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2037 {
2038     return !(__x == __y);
2039 }
2040
2041 _LIBCPP_END_NAMESPACE_STD
2042
2043 #endif  // _LIBCPP_UNORDERED_MAP