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