contrib/libc++/include/unordered_map

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