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