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