contrib/libc++/include/unordered_map

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