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