contrib/llvm-project/libcxx/include/unordered_set

   1 // -*- C++ -*-
   2 //===-------------------------- unordered_set -----------------------------===//
   3 //
   4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   5 // See https://llvm.org/LICENSE.txt for license information.
   6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #ifndef _LIBCPP_UNORDERED_SET
  11 #define _LIBCPP_UNORDERED_SET
  12
  13 /*
  14
  15     unordered_set synopsis
  16
  17 #include <initializer_list>
  18
  19 namespace std
  20 {
  21
  22 template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,
  23           class Alloc = allocator<Value>>
  24 class unordered_set
  25 {
  26 public:
  27     // types
  28     typedef Value                                                      key_type;
  29     typedef key_type                                                   value_type;
  30     typedef Hash                                                       hasher;
  31     typedef Pred                                                       key_equal;
  32     typedef Alloc                                                      allocator_type;
  33     typedef value_type&                                                reference;
  34     typedef const value_type&                                          const_reference;
  35     typedef typename allocator_traits<allocator_type>::pointer         pointer;
  36     typedef typename allocator_traits<allocator_type>::const_pointer   const_pointer;
  37     typedef typename allocator_traits<allocator_type>::size_type       size_type;
  38     typedef typename allocator_traits<allocator_type>::difference_type difference_type;
  39
  40     typedef /unspecified/ iterator;
  41     typedef /unspecified/ const_iterator;
  42     typedef /unspecified/ local_iterator;
  43     typedef /unspecified/ const_local_iterator;
  44
  45     typedef unspecified node_type unspecified;                            // C++17
  46     typedef INSERT_RETURN_TYPE<iterator, node_type> insert_return_type;   // C++17
  47
  48     unordered_set()
  49         noexcept(
  50             is_nothrow_default_constructible<hasher>::value &&
  51             is_nothrow_default_constructible<key_equal>::value &&
  52             is_nothrow_default_constructible<allocator_type>::value);
  53     explicit unordered_set(size_type n, const hasher& hf = hasher(),
  54                            const key_equal& eql = key_equal(),
  55                            const allocator_type& a = allocator_type());
  56     template <class InputIterator>
  57         unordered_set(InputIterator f, InputIterator l,
  58                       size_type n = 0, const hasher& hf = hasher(),
  59                       const key_equal& eql = key_equal(),
  60                       const allocator_type& a = allocator_type());
  61     explicit unordered_set(const allocator_type&);
  62     unordered_set(const unordered_set&);
  63     unordered_set(const unordered_set&, const Allocator&);
  64     unordered_set(unordered_set&&)
  65         noexcept(
  66             is_nothrow_move_constructible<hasher>::value &&
  67             is_nothrow_move_constructible<key_equal>::value &&
  68             is_nothrow_move_constructible<allocator_type>::value);
  69     unordered_set(unordered_set&&, const Allocator&);
  70     unordered_set(initializer_list<value_type>, size_type n = 0,
  71                   const hasher& hf = hasher(), const key_equal& eql = key_equal(),
  72                   const allocator_type& a = allocator_type());
  73     unordered_set(size_type n, const allocator_type& a); // C++14
  74     unordered_set(size_type n, const hasher& hf, const allocator_type& a); // C++14
  75     template <class InputIterator>
  76       unordered_set(InputIterator f, InputIterator l, size_type n, const allocator_type& a); // C++14
  77     template <class InputIterator>
  78       unordered_set(InputIterator f, InputIterator l, size_type n,
  79                     const hasher& hf,  const allocator_type& a); // C++14
  80     unordered_set(initializer_list<value_type> il, size_type n, const allocator_type& a); // C++14
  81     unordered_set(initializer_list<value_type> il, size_type n,
  82                   const hasher& hf,  const allocator_type& a); // C++14
  83     ~unordered_set();
  84     unordered_set& operator=(const unordered_set&);
  85     unordered_set& operator=(unordered_set&&)
  86         noexcept(
  87             allocator_type::propagate_on_container_move_assignment::value &&
  88             is_nothrow_move_assignable<allocator_type>::value &&
  89             is_nothrow_move_assignable<hasher>::value &&
  90             is_nothrow_move_assignable<key_equal>::value);
  91     unordered_set& operator=(initializer_list<value_type>);
  92
  93     allocator_type get_allocator() const noexcept;
  94
  95     bool      empty() const noexcept;
  96     size_type size() const noexcept;
  97     size_type max_size() const noexcept;
  98
  99     iterator       begin() noexcept;
 100     iterator       end() noexcept;
 101     const_iterator begin()  const noexcept;
 102     const_iterator end()    const noexcept;
 103     const_iterator cbegin() const noexcept;
 104     const_iterator cend()   const noexcept;
 105
 106     template <class... Args>
 107         pair<iterator, bool> emplace(Args&&... args);
 108     template <class... Args>
 109         iterator emplace_hint(const_iterator position, Args&&... args);
 110     pair<iterator, bool> insert(const value_type& obj);
 111     pair<iterator, bool> insert(value_type&& obj);
 112     iterator insert(const_iterator hint, const value_type& obj);
 113     iterator insert(const_iterator hint, value_type&& obj);
 114     template <class InputIterator>
 115         void insert(InputIterator first, InputIterator last);
 116     void insert(initializer_list<value_type>);
 117
 118     node_type extract(const_iterator position);                       // C++17
 119     node_type extract(const key_type& x);                             // C++17
 120     insert_return_type insert(node_type&& nh);                        // C++17
 121     iterator           insert(const_iterator hint, node_type&& nh);   // C++17
 122
 123     iterator erase(const_iterator position);
 124     iterator erase(iterator position);  // C++14
 125     size_type erase(const key_type& k);
 126     iterator erase(const_iterator first, const_iterator last);
 127     void clear() noexcept;
 128
 129     template<class H2, class P2>
 130       void merge(unordered_set<Key, H2, P2, Allocator>& source);         // C++17
 131     template<class H2, class P2>
 132       void merge(unordered_set<Key, H2, P2, Allocator>&& source);        // C++17
 133     template<class H2, class P2>
 134       void merge(unordered_multiset<Key, H2, P2, Allocator>& source);    // C++17
 135     template<class H2, class P2>
 136       void merge(unordered_multiset<Key, H2, P2, Allocator>&& source);   // C++17
 137
 138     void swap(unordered_set&)
 139        noexcept(allocator_traits<Allocator>::is_always_equal::value &&
 140                  noexcept(swap(declval<hasher&>(), declval<hasher&>())) &&
 141                  noexcept(swap(declval<key_equal&>(), declval<key_equal&>()))); // C++17
 142
 143     hasher hash_function() const;
 144     key_equal key_eq() const;
 145
 146     iterator       find(const key_type& k);
 147     const_iterator find(const key_type& k) const;
 148     size_type count(const key_type& k) const;
 149     bool contains(const key_type& k) const; // C++20
 150     pair<iterator, iterator>             equal_range(const key_type& k);
 151     pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
 152
 153     size_type bucket_count() const noexcept;
 154     size_type max_bucket_count() const noexcept;
 155
 156     size_type bucket_size(size_type n) const;
 157     size_type bucket(const key_type& k) const;
 158
 159     local_iterator       begin(size_type n);
 160     local_iterator       end(size_type n);
 161     const_local_iterator begin(size_type n) const;
 162     const_local_iterator end(size_type n) const;
 163     const_local_iterator cbegin(size_type n) const;
 164     const_local_iterator cend(size_type n) const;
 165
 166     float load_factor() const noexcept;
 167     float max_load_factor() const noexcept;
 168     void max_load_factor(float z);
 169     void rehash(size_type n);
 170     void reserve(size_type n);
 171 };
 172
 173 template <class Value, class Hash, class Pred, class Alloc>
 174     void swap(unordered_set<Value, Hash, Pred, Alloc>& x,
 175               unordered_set<Value, Hash, Pred, Alloc>& y)
 176               noexcept(noexcept(x.swap(y)));
 177
 178 template <class Value, class Hash, class Pred, class Alloc>
 179     bool
 180     operator==(const unordered_set<Value, Hash, Pred, Alloc>& x,
 181                const unordered_set<Value, Hash, Pred, Alloc>& y);
 182
 183 template <class Value, class Hash, class Pred, class Alloc>
 184     bool
 185     operator!=(const unordered_set<Value, Hash, Pred, Alloc>& x,
 186                const unordered_set<Value, Hash, Pred, Alloc>& y);
 187
 188 template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,
 189           class Alloc = allocator<Value>>
 190 class unordered_multiset
 191 {
 192 public:
 193     // types
 194     typedef Value                                                      key_type;
 195     typedef key_type                                                   value_type;
 196     typedef Hash                                                       hasher;
 197     typedef Pred                                                       key_equal;
 198     typedef Alloc                                                      allocator_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     typedef unspecified node_type unspecified;   // C++17
 212
 213     unordered_multiset()
 214         noexcept(
 215             is_nothrow_default_constructible<hasher>::value &&
 216             is_nothrow_default_constructible<key_equal>::value &&
 217             is_nothrow_default_constructible<allocator_type>::value);
 218     explicit unordered_multiset(size_type n, const hasher& hf = hasher(),
 219                            const key_equal& eql = key_equal(),
 220                            const allocator_type& a = allocator_type());
 221     template <class InputIterator>
 222         unordered_multiset(InputIterator f, InputIterator l,
 223                       size_type n = 0, const hasher& hf = hasher(),
 224                       const key_equal& eql = key_equal(),
 225                       const allocator_type& a = allocator_type());
 226     explicit unordered_multiset(const allocator_type&);
 227     unordered_multiset(const unordered_multiset&);
 228     unordered_multiset(const unordered_multiset&, const Allocator&);
 229     unordered_multiset(unordered_multiset&&)
 230         noexcept(
 231             is_nothrow_move_constructible<hasher>::value &&
 232             is_nothrow_move_constructible<key_equal>::value &&
 233             is_nothrow_move_constructible<allocator_type>::value);
 234     unordered_multiset(unordered_multiset&&, const Allocator&);
 235     unordered_multiset(initializer_list<value_type>, size_type n = /see below/,
 236                   const hasher& hf = hasher(), const key_equal& eql = key_equal(),
 237                   const allocator_type& a = allocator_type());
 238     unordered_multiset(size_type n, const allocator_type& a); // C++14
 239     unordered_multiset(size_type n, const hasher& hf, const allocator_type& a); // C++14
 240     template <class InputIterator>
 241       unordered_multiset(InputIterator f, InputIterator l, size_type n, const allocator_type& a); // C++14
 242     template <class InputIterator>
 243       unordered_multiset(InputIterator f, InputIterator l, size_type n,
 244                          const hasher& hf, const allocator_type& a); // C++14
 245     unordered_multiset(initializer_list<value_type> il, size_type n, const allocator_type& a); // C++14
 246     unordered_multiset(initializer_list<value_type> il, size_type n,
 247                        const hasher& hf,  const allocator_type& a); // C++14
 248     ~unordered_multiset();
 249     unordered_multiset& operator=(const unordered_multiset&);
 250     unordered_multiset& operator=(unordered_multiset&&)
 251         noexcept(
 252             allocator_type::propagate_on_container_move_assignment::value &&
 253             is_nothrow_move_assignable<allocator_type>::value &&
 254             is_nothrow_move_assignable<hasher>::value &&
 255             is_nothrow_move_assignable<key_equal>::value);
 256     unordered_multiset& operator=(initializer_list<value_type>);
 257
 258     allocator_type get_allocator() const noexcept;
 259
 260     bool      empty() const noexcept;
 261     size_type size() const noexcept;
 262     size_type max_size() const noexcept;
 263
 264     iterator       begin() noexcept;
 265     iterator       end() noexcept;
 266     const_iterator begin()  const noexcept;
 267     const_iterator end()    const noexcept;
 268     const_iterator cbegin() const noexcept;
 269     const_iterator cend()   const noexcept;
 270
 271     template <class... Args>
 272         iterator emplace(Args&&... args);
 273     template <class... Args>
 274         iterator emplace_hint(const_iterator position, Args&&... args);
 275     iterator insert(const value_type& obj);
 276     iterator insert(value_type&& obj);
 277     iterator insert(const_iterator hint, const value_type& obj);
 278     iterator insert(const_iterator hint, value_type&& obj);
 279     template <class InputIterator>
 280         void insert(InputIterator first, InputIterator last);
 281     void insert(initializer_list<value_type>);
 282
 283     node_type extract(const_iterator position);             // C++17
 284     node_type extract(const key_type& x);                   // C++17
 285     iterator insert(node_type&& nh);                        // C++17
 286     iterator insert(const_iterator hint, node_type&& nh);   // C++17
 287
 288     iterator erase(const_iterator position);
 289     iterator erase(iterator position);  // C++14
 290     size_type erase(const key_type& k);
 291     iterator erase(const_iterator first, const_iterator last);
 292     void clear() noexcept;
 293
 294     template<class H2, class P2>
 295       void merge(unordered_multiset<Key, H2, P2, Allocator>& source);    // C++17
 296     template<class H2, class P2>
 297       void merge(unordered_multiset<Key, H2, P2, Allocator>&& source);   // C++17
 298     template<class H2, class P2>
 299       void merge(unordered_set<Key, H2, P2, Allocator>& source);         // C++17
 300     template<class H2, class P2>
 301       void merge(unordered_set<Key, H2, P2, Allocator>&& source);        // C++17
 302
 303     void swap(unordered_multiset&)
 304        noexcept(allocator_traits<Allocator>::is_always_equal::value &&
 305                  noexcept(swap(declval<hasher&>(), declval<hasher&>())) &&
 306                  noexcept(swap(declval<key_equal&>(), declval<key_equal&>()))); // C++17
 307
 308     hasher hash_function() const;
 309     key_equal key_eq() const;
 310
 311     iterator       find(const key_type& k);
 312     const_iterator find(const key_type& k) const;
 313     size_type count(const key_type& k) const;
 314     bool contains(const key_type& k) const; // C++20
 315     pair<iterator, iterator>             equal_range(const key_type& k);
 316     pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
 317
 318     size_type bucket_count() const noexcept;
 319     size_type max_bucket_count() const noexcept;
 320
 321     size_type bucket_size(size_type n) const;
 322     size_type bucket(const key_type& k) const;
 323
 324     local_iterator       begin(size_type n);
 325     local_iterator       end(size_type n);
 326     const_local_iterator begin(size_type n) const;
 327     const_local_iterator end(size_type n) const;
 328     const_local_iterator cbegin(size_type n) const;
 329     const_local_iterator cend(size_type n) const;
 330
 331     float load_factor() const noexcept;
 332     float max_load_factor() const noexcept;
 333     void max_load_factor(float z);
 334     void rehash(size_type n);
 335     void reserve(size_type n);
 336 };
 337
 338 template <class Value, class Hash, class Pred, class Alloc>
 339     void swap(unordered_multiset<Value, Hash, Pred, Alloc>& x,
 340               unordered_multiset<Value, Hash, Pred, Alloc>& y)
 341               noexcept(noexcept(x.swap(y)));
 342
 343 template <class K, class T, class H, class P, class A, class Predicate>
 344     void erase_if(unordered_set<K, T, H, P, A>& c, Predicate pred);       // C++20
 345
 346 template <class K, class T, class H, class P, class A, class Predicate>
 347     void erase_if(unordered_multiset<K, T, H, P, A>& c, Predicate pred);  // C++20
 348
 349
 350 template <class Value, class Hash, class Pred, class Alloc>
 351     bool
 352     operator==(const unordered_multiset<Value, Hash, Pred, Alloc>& x,
 353                const unordered_multiset<Value, Hash, Pred, Alloc>& y);
 354
 355 template <class Value, class Hash, class Pred, class Alloc>
 356     bool
 357     operator!=(const unordered_multiset<Value, Hash, Pred, Alloc>& x,
 358                const unordered_multiset<Value, Hash, Pred, Alloc>& y);
 359 }  // std
 360
 361 */
 362
 363 #include <__config>
 364 #include <__hash_table>
 365 #include <__node_handle>
 366 #include <functional>
 367 #include <version>
 368
 369 #include <__debug>
 370
 371 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 372 #pragma GCC system_header
 373 #endif
 374
 375 _LIBCPP_BEGIN_NAMESPACE_STD
 376
 377 template <class _Value, class _Hash, class _Pred, class _Alloc>
 378 class unordered_multiset;
 379
 380 template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>,
 381           class _Alloc = allocator<_Value> >
 382 class _LIBCPP_TEMPLATE_VIS unordered_set
 383 {
 384 public:
 385     // types
 386     typedef _Value                                                     key_type;
 387     typedef key_type                                                   value_type;
 388     typedef typename __identity<_Hash>::type                           hasher;
 389     typedef typename __identity<_Pred>::type                           key_equal;
 390     typedef typename __identity<_Alloc>::type                          allocator_type;
 391     typedef value_type&                                                reference;
 392     typedef const value_type&                                          const_reference;
 393     static_assert((is_same<value_type, typename allocator_type::value_type>::value),
 394                   "Invalid allocator::value_type");
 395
 396 private:
 397     typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
 398
 399     __table __table_;
 400
 401 public:
 402     typedef typename __table::pointer         pointer;
 403     typedef typename __table::const_pointer   const_pointer;
 404     typedef typename __table::size_type       size_type;
 405     typedef typename __table::difference_type difference_type;
 406
 407     typedef typename __table::const_iterator       iterator;
 408     typedef typename __table::const_iterator       const_iterator;
 409     typedef typename __table::const_local_iterator local_iterator;
 410     typedef typename __table::const_local_iterator const_local_iterator;
 411
 412 #if _LIBCPP_STD_VER > 14
 413     typedef __set_node_handle<typename __table::__node, allocator_type> node_type;
 414     typedef __insert_return_type<iterator, node_type> insert_return_type;
 415 #endif
 416
 417     template <class _Value2, class _Hash2, class _Pred2, class _Alloc2>
 418         friend class _LIBCPP_TEMPLATE_VIS unordered_set;
 419     template <class _Value2, class _Hash2, class _Pred2, class _Alloc2>
 420         friend class _LIBCPP_TEMPLATE_VIS unordered_multiset;
 421
 422     _LIBCPP_INLINE_VISIBILITY
 423     unordered_set()
 424         _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
 425         {
 426 #if _LIBCPP_DEBUG_LEVEL >= 2
 427             __get_db()->__insert_c(this);
 428 #endif
 429         }
 430     explicit unordered_set(size_type __n, const hasher& __hf = hasher(),
 431                            const key_equal& __eql = key_equal());
 432 #if _LIBCPP_STD_VER > 11
 433     inline _LIBCPP_INLINE_VISIBILITY
 434     unordered_set(size_type __n, const allocator_type& __a)
 435         : unordered_set(__n, hasher(), key_equal(), __a) {}
 436     inline _LIBCPP_INLINE_VISIBILITY
 437     unordered_set(size_type __n, const hasher& __hf, const allocator_type& __a)
 438         : unordered_set(__n, __hf, key_equal(), __a) {}
 439 #endif
 440     unordered_set(size_type __n, const hasher& __hf, const key_equal& __eql,
 441                   const allocator_type& __a);
 442     template <class _InputIterator>
 443         unordered_set(_InputIterator __first, _InputIterator __last);
 444     template <class _InputIterator>
 445         unordered_set(_InputIterator __first, _InputIterator __last,
 446                       size_type __n, const hasher& __hf = hasher(),
 447                       const key_equal& __eql = key_equal());
 448     template <class _InputIterator>
 449         unordered_set(_InputIterator __first, _InputIterator __last,
 450                       size_type __n, const hasher& __hf, const key_equal& __eql,
 451                       const allocator_type& __a);
 452 #if _LIBCPP_STD_VER > 11
 453     template <class _InputIterator>
 454     inline _LIBCPP_INLINE_VISIBILITY
 455         unordered_set(_InputIterator __first, _InputIterator __last,
 456                     size_type __n, const allocator_type& __a)
 457             : unordered_set(__first, __last, __n, hasher(), key_equal(), __a) {}
 458     template <class _InputIterator>
 459         unordered_set(_InputIterator __first, _InputIterator __last,
 460                       size_type __n, const hasher& __hf, const allocator_type& __a)
 461             : unordered_set(__first, __last, __n, __hf, key_equal(), __a) {}
 462 #endif
 463     _LIBCPP_INLINE_VISIBILITY
 464     explicit unordered_set(const allocator_type& __a);
 465     unordered_set(const unordered_set& __u);
 466     unordered_set(const unordered_set& __u, const allocator_type& __a);
 467 #ifndef _LIBCPP_CXX03_LANG
 468     _LIBCPP_INLINE_VISIBILITY
 469     unordered_set(unordered_set&& __u)
 470         _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
 471     unordered_set(unordered_set&& __u, const allocator_type& __a);
 472     unordered_set(initializer_list<value_type> __il);
 473     unordered_set(initializer_list<value_type> __il, size_type __n,
 474                   const hasher& __hf = hasher(),
 475                   const key_equal& __eql = key_equal());
 476     unordered_set(initializer_list<value_type> __il, size_type __n,
 477                   const hasher& __hf, const key_equal& __eql,
 478                   const allocator_type& __a);
 479 #if _LIBCPP_STD_VER > 11
 480     inline _LIBCPP_INLINE_VISIBILITY
 481     unordered_set(initializer_list<value_type> __il, size_type __n,
 482                                                       const allocator_type& __a)
 483         : unordered_set(__il, __n, hasher(), key_equal(), __a) {}
 484     inline _LIBCPP_INLINE_VISIBILITY
 485     unordered_set(initializer_list<value_type> __il, size_type __n,
 486                                   const hasher& __hf, const allocator_type& __a)
 487         : unordered_set(__il, __n, __hf, key_equal(), __a) {}
 488 #endif
 489 #endif  // _LIBCPP_CXX03_LANG
 490     _LIBCPP_INLINE_VISIBILITY
 491     ~unordered_set() {
 492         static_assert(sizeof(__diagnose_unordered_container_requirements<_Value, _Hash, _Pred>(0)), "");
 493     }
 494
 495     _LIBCPP_INLINE_VISIBILITY
 496     unordered_set& operator=(const unordered_set& __u)
 497     {
 498         __table_ = __u.__table_;
 499         return *this;
 500     }
 501 #ifndef _LIBCPP_CXX03_LANG
 502     _LIBCPP_INLINE_VISIBILITY
 503     unordered_set& operator=(unordered_set&& __u)
 504         _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
 505     _LIBCPP_INLINE_VISIBILITY
 506     unordered_set& operator=(initializer_list<value_type> __il);
 507 #endif  // _LIBCPP_CXX03_LANG
 508
 509     _LIBCPP_INLINE_VISIBILITY
 510     allocator_type get_allocator() const _NOEXCEPT
 511         {return allocator_type(__table_.__node_alloc());}
 512
 513     _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
 514     bool      empty() const _NOEXCEPT {return __table_.size() == 0;}
 515     _LIBCPP_INLINE_VISIBILITY
 516     size_type size() const _NOEXCEPT  {return __table_.size();}
 517     _LIBCPP_INLINE_VISIBILITY
 518     size_type max_size() const _NOEXCEPT {return __table_.max_size();}
 519
 520     _LIBCPP_INLINE_VISIBILITY
 521     iterator       begin() _NOEXCEPT        {return __table_.begin();}
 522     _LIBCPP_INLINE_VISIBILITY
 523     iterator       end() _NOEXCEPT          {return __table_.end();}
 524     _LIBCPP_INLINE_VISIBILITY
 525     const_iterator begin()  const _NOEXCEPT {return __table_.begin();}
 526     _LIBCPP_INLINE_VISIBILITY
 527     const_iterator end()    const _NOEXCEPT {return __table_.end();}
 528     _LIBCPP_INLINE_VISIBILITY
 529     const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
 530     _LIBCPP_INLINE_VISIBILITY
 531     const_iterator cend()   const _NOEXCEPT {return __table_.end();}
 532
 533 #ifndef _LIBCPP_CXX03_LANG
 534     template <class... _Args>
 535         _LIBCPP_INLINE_VISIBILITY
 536         pair<iterator, bool> emplace(_Args&&... __args)
 537             {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...);}
 538     template <class... _Args>
 539         _LIBCPP_INLINE_VISIBILITY
 540 #if _LIBCPP_DEBUG_LEVEL >= 2
 541         iterator emplace_hint(const_iterator __p, _Args&&... __args)
 542         {
 543             _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
 544                 "unordered_set::emplace_hint(const_iterator, args...) called with an iterator not"
 545                 " referring to this unordered_set");
 546             return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first;
 547         }
 548 #else
 549         iterator emplace_hint(const_iterator, _Args&&... __args)
 550             {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first;}
 551 #endif
 552
 553     _LIBCPP_INLINE_VISIBILITY
 554     pair<iterator, bool> insert(value_type&& __x)
 555         {return __table_.__insert_unique(_VSTD::move(__x));}
 556     _LIBCPP_INLINE_VISIBILITY
 557 #if _LIBCPP_DEBUG_LEVEL >= 2
 558     iterator insert(const_iterator __p, value_type&& __x)
 559         {
 560             _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
 561                 "unordered_set::insert(const_iterator, value_type&&) called with an iterator not"
 562                 " referring to this unordered_set");
 563             return insert(_VSTD::move(__x)).first;
 564         }
 565 #else
 566     iterator insert(const_iterator, value_type&& __x)
 567         {return insert(_VSTD::move(__x)).first;}
 568 #endif
 569     _LIBCPP_INLINE_VISIBILITY
 570     void insert(initializer_list<value_type> __il)
 571         {insert(__il.begin(), __il.end());}
 572 #endif  // _LIBCPP_CXX03_LANG
 573     _LIBCPP_INLINE_VISIBILITY
 574     pair<iterator, bool> insert(const value_type& __x)
 575         {return __table_.__insert_unique(__x);}
 576
 577     _LIBCPP_INLINE_VISIBILITY
 578 #if _LIBCPP_DEBUG_LEVEL >= 2
 579     iterator insert(const_iterator __p, const value_type& __x)
 580         {
 581             _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
 582                 "unordered_set::insert(const_iterator, const value_type&) called with an iterator not"
 583                 " referring to this unordered_set");
 584             return insert(__x).first;
 585         }
 586 #else
 587     iterator insert(const_iterator, const value_type& __x)
 588         {return insert(__x).first;}
 589 #endif
 590     template <class _InputIterator>
 591         _LIBCPP_INLINE_VISIBILITY
 592         void insert(_InputIterator __first, _InputIterator __last);
 593
 594     _LIBCPP_INLINE_VISIBILITY
 595     iterator erase(const_iterator __p) {return __table_.erase(__p);}
 596     _LIBCPP_INLINE_VISIBILITY
 597     size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
 598     _LIBCPP_INLINE_VISIBILITY
 599     iterator erase(const_iterator __first, const_iterator __last)
 600         {return __table_.erase(__first, __last);}
 601     _LIBCPP_INLINE_VISIBILITY
 602     void clear() _NOEXCEPT {__table_.clear();}
 603
 604 #if _LIBCPP_STD_VER > 14
 605     _LIBCPP_INLINE_VISIBILITY
 606     insert_return_type insert(node_type&& __nh)
 607     {
 608         _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
 609             "node_type with incompatible allocator passed to unordered_set::insert()");
 610         return __table_.template __node_handle_insert_unique<
 611             node_type, insert_return_type>(_VSTD::move(__nh));
 612     }
 613     _LIBCPP_INLINE_VISIBILITY
 614     iterator insert(const_iterator __h, node_type&& __nh)
 615     {
 616         _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
 617             "node_type with incompatible allocator passed to unordered_set::insert()");
 618         return __table_.template __node_handle_insert_unique<node_type>(
 619             __h, _VSTD::move(__nh));
 620     }
 621     _LIBCPP_INLINE_VISIBILITY
 622     node_type extract(key_type const& __key)
 623     {
 624         return __table_.template __node_handle_extract<node_type>(__key);
 625     }
 626     _LIBCPP_INLINE_VISIBILITY
 627     node_type extract(const_iterator __it)
 628     {
 629         return __table_.template __node_handle_extract<node_type>(__it);
 630     }
 631
 632     template<class _H2, class _P2>
 633     _LIBCPP_INLINE_VISIBILITY
 634     void merge(unordered_set<key_type, _H2, _P2, allocator_type>& __source)
 635     {
 636         _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
 637                        "merging container with incompatible allocator");
 638         __table_.__node_handle_merge_unique(__source.__table_);
 639     }
 640     template<class _H2, class _P2>
 641     _LIBCPP_INLINE_VISIBILITY
 642     void merge(unordered_set<key_type, _H2, _P2, allocator_type>&& __source)
 643     {
 644         _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
 645                        "merging container with incompatible allocator");
 646         __table_.__node_handle_merge_unique(__source.__table_);
 647     }
 648     template<class _H2, class _P2>
 649     _LIBCPP_INLINE_VISIBILITY
 650     void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>& __source)
 651     {
 652         _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
 653                        "merging container with incompatible allocator");
 654         __table_.__node_handle_merge_unique(__source.__table_);
 655     }
 656     template<class _H2, class _P2>
 657     _LIBCPP_INLINE_VISIBILITY
 658     void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>&& __source)
 659     {
 660         _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
 661                        "merging container with incompatible allocator");
 662         __table_.__node_handle_merge_unique(__source.__table_);
 663     }
 664 #endif
 665
 666     _LIBCPP_INLINE_VISIBILITY
 667     void swap(unordered_set& __u)
 668         _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
 669         {__table_.swap(__u.__table_);}
 670
 671     _LIBCPP_INLINE_VISIBILITY
 672     hasher hash_function() const {return __table_.hash_function();}
 673     _LIBCPP_INLINE_VISIBILITY
 674     key_equal key_eq() const {return __table_.key_eq();}
 675
 676     _LIBCPP_INLINE_VISIBILITY
 677     iterator       find(const key_type& __k)       {return __table_.find(__k);}
 678     _LIBCPP_INLINE_VISIBILITY
 679     const_iterator find(const key_type& __k) const {return __table_.find(__k);}
 680     _LIBCPP_INLINE_VISIBILITY
 681     size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
 682     #if _LIBCPP_STD_VER > 17
 683         _LIBCPP_INLINE_VISIBILITY
 684         bool contains(const key_type& __k) const {return find(__k) != end();}
 685     #endif // _LIBCPP_STD_VER > 17
 686     _LIBCPP_INLINE_VISIBILITY
 687     pair<iterator, iterator>             equal_range(const key_type& __k)
 688         {return __table_.__equal_range_unique(__k);}
 689     _LIBCPP_INLINE_VISIBILITY
 690     pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
 691         {return __table_.__equal_range_unique(__k);}
 692
 693     _LIBCPP_INLINE_VISIBILITY
 694     size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
 695     _LIBCPP_INLINE_VISIBILITY
 696     size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
 697
 698     _LIBCPP_INLINE_VISIBILITY
 699     size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);}
 700     _LIBCPP_INLINE_VISIBILITY
 701     size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
 702
 703     _LIBCPP_INLINE_VISIBILITY
 704     local_iterator       begin(size_type __n)        {return __table_.begin(__n);}
 705     _LIBCPP_INLINE_VISIBILITY
 706     local_iterator       end(size_type __n)          {return __table_.end(__n);}
 707     _LIBCPP_INLINE_VISIBILITY
 708     const_local_iterator begin(size_type __n) const  {return __table_.cbegin(__n);}
 709     _LIBCPP_INLINE_VISIBILITY
 710     const_local_iterator end(size_type __n) const    {return __table_.cend(__n);}
 711     _LIBCPP_INLINE_VISIBILITY
 712     const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
 713     _LIBCPP_INLINE_VISIBILITY
 714     const_local_iterator cend(size_type __n) const   {return __table_.cend(__n);}
 715
 716     _LIBCPP_INLINE_VISIBILITY
 717     float load_factor() const _NOEXCEPT {return __table_.load_factor();}
 718     _LIBCPP_INLINE_VISIBILITY
 719     float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
 720     _LIBCPP_INLINE_VISIBILITY
 721     void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
 722     _LIBCPP_INLINE_VISIBILITY
 723     void rehash(size_type __n) {__table_.rehash(__n);}
 724     _LIBCPP_INLINE_VISIBILITY
 725     void reserve(size_type __n) {__table_.reserve(__n);}
 726
 727 #if _LIBCPP_DEBUG_LEVEL >= 2
 728
 729     bool __dereferenceable(const const_iterator* __i) const
 730         {return __table_.__dereferenceable(__i);}
 731     bool __decrementable(const const_iterator* __i) const
 732         {return __table_.__decrementable(__i);}
 733     bool __addable(const const_iterator* __i, ptrdiff_t __n) const
 734         {return __table_.__addable(__i, __n);}
 735     bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
 736         {return __table_.__addable(__i, __n);}
 737
 738 #endif  // _LIBCPP_DEBUG_LEVEL >= 2
 739
 740 };
 741
 742 #ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES
 743 template<class _InputIterator,
 744          class _Hash = hash<__iter_value_type<_InputIterator>>,
 745          class _Pred = equal_to<__iter_value_type<_InputIterator>>,
 746          class _Allocator = allocator<__iter_value_type<_InputIterator>>,
 747          class = _EnableIf<!__is_allocator<_Hash>::value>,
 748          class = _EnableIf<!is_integral<_Hash>::value>,
 749          class = _EnableIf<!__is_allocator<_Pred>::value>,
 750          class = _EnableIf<__is_allocator<_Allocator>::value>>
 751 unordered_set(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type = 0,
 752               _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
 753   -> unordered_set<__iter_value_type<_InputIterator>, _Hash, _Pred, _Allocator>;
 754
 755 template<class _Tp, class _Hash = hash<_Tp>,
 756          class _Pred = equal_to<_Tp>,
 757          class _Allocator = allocator<_Tp>,
 758          class = _EnableIf<!__is_allocator<_Hash>::value>,
 759          class = _EnableIf<!is_integral<_Hash>::value>,
 760          class = _EnableIf<!__is_allocator<_Pred>::value>,
 761          class = _EnableIf<__is_allocator<_Allocator>::value>>
 762 unordered_set(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type = 0,
 763               _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
 764   -> unordered_set<_Tp, _Hash, _Pred, _Allocator>;
 765
 766 template<class _InputIterator, class _Allocator,
 767          class = _EnableIf<__is_allocator<_Allocator>::value>>
 768 unordered_set(_InputIterator, _InputIterator,
 769               typename allocator_traits<_Allocator>::size_type, _Allocator)
 770   -> unordered_set<__iter_value_type<_InputIterator>,
 771                    hash<__iter_value_type<_InputIterator>>,
 772                    equal_to<__iter_value_type<_InputIterator>>,
 773                    _Allocator>;
 774
 775 template<class _InputIterator, class _Hash, class _Allocator,
 776          class = _EnableIf<!__is_allocator<_Hash>::value>,
 777          class = _EnableIf<!is_integral<_Hash>::value>,
 778          class = _EnableIf<__is_allocator<_Allocator>::value>>
 779 unordered_set(_InputIterator, _InputIterator,
 780               typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
 781   -> unordered_set<__iter_value_type<_InputIterator>, _Hash,
 782                    equal_to<__iter_value_type<_InputIterator>>,
 783                    _Allocator>;
 784
 785 template<class _Tp, class _Allocator,
 786          class = _EnableIf<__is_allocator<_Allocator>::value>>
 787 unordered_set(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Allocator)
 788   -> unordered_set<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
 789
 790 template<class _Tp, class _Hash, class _Allocator,
 791          class = _EnableIf<!__is_allocator<_Hash>::value>,
 792          class = _EnableIf<!is_integral<_Hash>::value>,
 793          class = _EnableIf<__is_allocator<_Allocator>::value>>
 794 unordered_set(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
 795   -> unordered_set<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
 796 #endif
 797
 798 template <class _Value, class _Hash, class _Pred, class _Alloc>
 799 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n,
 800         const hasher& __hf, const key_equal& __eql)
 801     : __table_(__hf, __eql)
 802 {
 803 #if _LIBCPP_DEBUG_LEVEL >= 2
 804     __get_db()->__insert_c(this);
 805 #endif
 806     __table_.rehash(__n);
 807 }
 808
 809 template <class _Value, class _Hash, class _Pred, class _Alloc>
 810 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n,
 811         const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
 812     : __table_(__hf, __eql, __a)
 813 {
 814 #if _LIBCPP_DEBUG_LEVEL >= 2
 815     __get_db()->__insert_c(this);
 816 #endif
 817     __table_.rehash(__n);
 818 }
 819
 820 template <class _Value, class _Hash, class _Pred, class _Alloc>
 821 template <class _InputIterator>
 822 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
 823         _InputIterator __first, _InputIterator __last)
 824 {
 825 #if _LIBCPP_DEBUG_LEVEL >= 2
 826     __get_db()->__insert_c(this);
 827 #endif
 828     insert(__first, __last);
 829 }
 830
 831 template <class _Value, class _Hash, class _Pred, class _Alloc>
 832 template <class _InputIterator>
 833 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
 834         _InputIterator __first, _InputIterator __last, size_type __n,
 835         const hasher& __hf, const key_equal& __eql)
 836     : __table_(__hf, __eql)
 837 {
 838 #if _LIBCPP_DEBUG_LEVEL >= 2
 839     __get_db()->__insert_c(this);
 840 #endif
 841     __table_.rehash(__n);
 842     insert(__first, __last);
 843 }
 844
 845 template <class _Value, class _Hash, class _Pred, class _Alloc>
 846 template <class _InputIterator>
 847 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
 848         _InputIterator __first, _InputIterator __last, size_type __n,
 849         const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
 850     : __table_(__hf, __eql, __a)
 851 {
 852 #if _LIBCPP_DEBUG_LEVEL >= 2
 853     __get_db()->__insert_c(this);
 854 #endif
 855     __table_.rehash(__n);
 856     insert(__first, __last);
 857 }
 858
 859 template <class _Value, class _Hash, class _Pred, class _Alloc>
 860 inline
 861 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
 862         const allocator_type& __a)
 863     : __table_(__a)
 864 {
 865 #if _LIBCPP_DEBUG_LEVEL >= 2
 866     __get_db()->__insert_c(this);
 867 #endif
 868 }
 869
 870 template <class _Value, class _Hash, class _Pred, class _Alloc>
 871 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
 872         const unordered_set& __u)
 873     : __table_(__u.__table_)
 874 {
 875 #if _LIBCPP_DEBUG_LEVEL >= 2
 876     __get_db()->__insert_c(this);
 877 #endif
 878     __table_.rehash(__u.bucket_count());
 879     insert(__u.begin(), __u.end());
 880 }
 881
 882 template <class _Value, class _Hash, class _Pred, class _Alloc>
 883 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
 884         const unordered_set& __u, const allocator_type& __a)
 885     : __table_(__u.__table_, __a)
 886 {
 887 #if _LIBCPP_DEBUG_LEVEL >= 2
 888     __get_db()->__insert_c(this);
 889 #endif
 890     __table_.rehash(__u.bucket_count());
 891     insert(__u.begin(), __u.end());
 892 }
 893
 894 #ifndef _LIBCPP_CXX03_LANG
 895
 896 template <class _Value, class _Hash, class _Pred, class _Alloc>
 897 inline
 898 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
 899         unordered_set&& __u)
 900     _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
 901     : __table_(_VSTD::move(__u.__table_))
 902 {
 903 #if _LIBCPP_DEBUG_LEVEL >= 2
 904     __get_db()->__insert_c(this);
 905     __get_db()->swap(this, &__u);
 906 #endif
 907 }
 908
 909 template <class _Value, class _Hash, class _Pred, class _Alloc>
 910 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
 911         unordered_set&& __u, const allocator_type& __a)
 912     : __table_(_VSTD::move(__u.__table_), __a)
 913 {
 914 #if _LIBCPP_DEBUG_LEVEL >= 2
 915     __get_db()->__insert_c(this);
 916 #endif
 917     if (__a != __u.get_allocator())
 918     {
 919         iterator __i = __u.begin();
 920         while (__u.size() != 0)
 921             __table_.__insert_unique(_VSTD::move(__u.__table_.remove(__i++)->__value_));
 922     }
 923 #if _LIBCPP_DEBUG_LEVEL >= 2
 924     else
 925         __get_db()->swap(this, &__u);
 926 #endif
 927 }
 928
 929 template <class _Value, class _Hash, class _Pred, class _Alloc>
 930 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
 931         initializer_list<value_type> __il)
 932 {
 933 #if _LIBCPP_DEBUG_LEVEL >= 2
 934     __get_db()->__insert_c(this);
 935 #endif
 936     insert(__il.begin(), __il.end());
 937 }
 938
 939 template <class _Value, class _Hash, class _Pred, class _Alloc>
 940 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
 941         initializer_list<value_type> __il, size_type __n, const hasher& __hf,
 942         const key_equal& __eql)
 943     : __table_(__hf, __eql)
 944 {
 945 #if _LIBCPP_DEBUG_LEVEL >= 2
 946     __get_db()->__insert_c(this);
 947 #endif
 948     __table_.rehash(__n);
 949     insert(__il.begin(), __il.end());
 950 }
 951
 952 template <class _Value, class _Hash, class _Pred, class _Alloc>
 953 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
 954         initializer_list<value_type> __il, size_type __n, const hasher& __hf,
 955         const key_equal& __eql, const allocator_type& __a)
 956     : __table_(__hf, __eql, __a)
 957 {
 958 #if _LIBCPP_DEBUG_LEVEL >= 2
 959     __get_db()->__insert_c(this);
 960 #endif
 961     __table_.rehash(__n);
 962     insert(__il.begin(), __il.end());
 963 }
 964
 965 template <class _Value, class _Hash, class _Pred, class _Alloc>
 966 inline
 967 unordered_set<_Value, _Hash, _Pred, _Alloc>&
 968 unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(unordered_set&& __u)
 969     _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
 970 {
 971     __table_ = _VSTD::move(__u.__table_);
 972     return *this;
 973 }
 974
 975 template <class _Value, class _Hash, class _Pred, class _Alloc>
 976 inline
 977 unordered_set<_Value, _Hash, _Pred, _Alloc>&
 978 unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(
 979         initializer_list<value_type> __il)
 980 {
 981     __table_.__assign_unique(__il.begin(), __il.end());
 982     return *this;
 983 }
 984
 985 #endif  // _LIBCPP_CXX03_LANG
 986
 987 template <class _Value, class _Hash, class _Pred, class _Alloc>
 988 template <class _InputIterator>
 989 inline
 990 void
 991 unordered_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
 992                                                     _InputIterator __last)
 993 {
 994     for (; __first != __last; ++__first)
 995         __table_.__insert_unique(*__first);
 996 }
 997
 998 template <class _Value, class _Hash, class _Pred, class _Alloc>
 999 inline _LIBCPP_INLINE_VISIBILITY
1000 void
1001 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
1002      unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
1003     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1004 {
1005     __x.swap(__y);
1006 }
1007
1008 #if _LIBCPP_STD_VER > 17
1009 template <class _Value, class _Hash, class _Pred, class _Alloc, class _Predicate>
1010 inline _LIBCPP_INLINE_VISIBILITY
1011 void erase_if(unordered_set<_Value, _Hash, _Pred, _Alloc>& __c, _Predicate __pred)
1012 { __libcpp_erase_if_container(__c, __pred); }
1013 #endif
1014
1015 template <class _Value, class _Hash, class _Pred, class _Alloc>
1016 bool
1017 operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
1018            const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
1019 {
1020     if (__x.size() != __y.size())
1021         return false;
1022     typedef typename unordered_set<_Value, _Hash, _Pred, _Alloc>::const_iterator
1023                                                                  const_iterator;
1024     for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();
1025             __i != __ex; ++__i)
1026     {
1027         const_iterator __j = __y.find(*__i);
1028         if (__j == __ey || !(*__i == *__j))
1029             return false;
1030     }
1031     return true;
1032 }
1033
1034 template <class _Value, class _Hash, class _Pred, class _Alloc>
1035 inline _LIBCPP_INLINE_VISIBILITY
1036 bool
1037 operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
1038            const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
1039 {
1040     return !(__x == __y);
1041 }
1042
1043 template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>,
1044           class _Alloc = allocator<_Value> >
1045 class _LIBCPP_TEMPLATE_VIS unordered_multiset
1046 {
1047 public:
1048     // types
1049     typedef _Value                                                     key_type;
1050     typedef key_type                                                   value_type;
1051     typedef typename __identity<_Hash>::type                           hasher;
1052     typedef typename __identity<_Pred>::type                           key_equal;
1053     typedef typename __identity<_Alloc>::type                          allocator_type;
1054     typedef value_type&                                                reference;
1055     typedef const value_type&                                          const_reference;
1056     static_assert((is_same<value_type, typename allocator_type::value_type>::value),
1057                   "Invalid allocator::value_type");
1058
1059 private:
1060     typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
1061
1062     __table __table_;
1063
1064 public:
1065     typedef typename __table::pointer         pointer;
1066     typedef typename __table::const_pointer   const_pointer;
1067     typedef typename __table::size_type       size_type;
1068     typedef typename __table::difference_type difference_type;
1069
1070     typedef typename __table::const_iterator       iterator;
1071     typedef typename __table::const_iterator       const_iterator;
1072     typedef typename __table::const_local_iterator local_iterator;
1073     typedef typename __table::const_local_iterator const_local_iterator;
1074
1075 #if _LIBCPP_STD_VER > 14
1076     typedef __set_node_handle<typename __table::__node, allocator_type> node_type;
1077 #endif
1078
1079     template <class _Value2, class _Hash2, class _Pred2, class _Alloc2>
1080         friend class _LIBCPP_TEMPLATE_VIS unordered_set;
1081     template <class _Value2, class _Hash2, class _Pred2, class _Alloc2>
1082         friend class _LIBCPP_TEMPLATE_VIS unordered_multiset;
1083
1084     _LIBCPP_INLINE_VISIBILITY
1085     unordered_multiset()
1086         _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
1087         {
1088 #if _LIBCPP_DEBUG_LEVEL >= 2
1089             __get_db()->__insert_c(this);
1090 #endif
1091         }
1092     explicit unordered_multiset(size_type __n, const hasher& __hf = hasher(),
1093                                 const key_equal& __eql = key_equal());
1094     unordered_multiset(size_type __n, const hasher& __hf,
1095                        const key_equal& __eql, const allocator_type& __a);
1096 #if _LIBCPP_STD_VER > 11
1097     inline _LIBCPP_INLINE_VISIBILITY
1098     unordered_multiset(size_type __n, const allocator_type& __a)
1099         : unordered_multiset(__n, hasher(), key_equal(), __a) {}
1100     inline _LIBCPP_INLINE_VISIBILITY
1101     unordered_multiset(size_type __n, const hasher& __hf, const allocator_type& __a)
1102         : unordered_multiset(__n, __hf, key_equal(), __a) {}
1103 #endif
1104     template <class _InputIterator>
1105         unordered_multiset(_InputIterator __first, _InputIterator __last);
1106     template <class _InputIterator>
1107         unordered_multiset(_InputIterator __first, _InputIterator __last,
1108                       size_type __n, const hasher& __hf = hasher(),
1109                       const key_equal& __eql = key_equal());
1110     template <class _InputIterator>
1111         unordered_multiset(_InputIterator __first, _InputIterator __last,
1112                       size_type __n , const hasher& __hf,
1113                       const key_equal& __eql, const allocator_type& __a);
1114 #if _LIBCPP_STD_VER > 11
1115     template <class _InputIterator>
1116     inline _LIBCPP_INLINE_VISIBILITY
1117     unordered_multiset(_InputIterator __first, _InputIterator __last,
1118                        size_type __n, const allocator_type& __a)
1119         : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a) {}
1120     template <class _InputIterator>
1121     inline _LIBCPP_INLINE_VISIBILITY
1122     unordered_multiset(_InputIterator __first, _InputIterator __last,
1123                        size_type __n, const hasher& __hf, const allocator_type& __a)
1124         : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a) {}
1125 #endif
1126     _LIBCPP_INLINE_VISIBILITY
1127     explicit unordered_multiset(const allocator_type& __a);
1128     unordered_multiset(const unordered_multiset& __u);
1129     unordered_multiset(const unordered_multiset& __u, const allocator_type& __a);
1130 #ifndef _LIBCPP_CXX03_LANG
1131     _LIBCPP_INLINE_VISIBILITY
1132     unordered_multiset(unordered_multiset&& __u)
1133         _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
1134     unordered_multiset(unordered_multiset&& __u, const allocator_type& __a);
1135     unordered_multiset(initializer_list<value_type> __il);
1136     unordered_multiset(initializer_list<value_type> __il, size_type __n,
1137                        const hasher& __hf = hasher(),
1138                        const key_equal& __eql = key_equal());
1139     unordered_multiset(initializer_list<value_type> __il, size_type __n,
1140                        const hasher& __hf, const key_equal& __eql,
1141                        const allocator_type& __a);
1142 #if _LIBCPP_STD_VER > 11
1143     inline _LIBCPP_INLINE_VISIBILITY
1144     unordered_multiset(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)
1145       : unordered_multiset(__il, __n, hasher(), key_equal(), __a) {}
1146     inline _LIBCPP_INLINE_VISIBILITY
1147     unordered_multiset(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a)
1148       : unordered_multiset(__il, __n, __hf, key_equal(), __a) {}
1149 #endif
1150 #endif  // _LIBCPP_CXX03_LANG
1151     _LIBCPP_INLINE_VISIBILITY
1152     ~unordered_multiset() {
1153         static_assert(sizeof(__diagnose_unordered_container_requirements<_Value, _Hash, _Pred>(0)), "");
1154     }
1155
1156     _LIBCPP_INLINE_VISIBILITY
1157     unordered_multiset& operator=(const unordered_multiset& __u)
1158     {
1159         __table_ = __u.__table_;
1160         return *this;
1161     }
1162 #ifndef _LIBCPP_CXX03_LANG
1163     _LIBCPP_INLINE_VISIBILITY
1164     unordered_multiset& operator=(unordered_multiset&& __u)
1165         _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
1166     unordered_multiset& operator=(initializer_list<value_type> __il);
1167 #endif  // _LIBCPP_CXX03_LANG
1168
1169     _LIBCPP_INLINE_VISIBILITY
1170     allocator_type get_allocator() const _NOEXCEPT
1171         {return allocator_type(__table_.__node_alloc());}
1172
1173     _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
1174     bool      empty() const _NOEXCEPT {return __table_.size() == 0;}
1175     _LIBCPP_INLINE_VISIBILITY
1176     size_type size() const _NOEXCEPT  {return __table_.size();}
1177     _LIBCPP_INLINE_VISIBILITY
1178     size_type max_size() const _NOEXCEPT {return __table_.max_size();}
1179
1180     _LIBCPP_INLINE_VISIBILITY
1181     iterator       begin() _NOEXCEPT        {return __table_.begin();}
1182     _LIBCPP_INLINE_VISIBILITY
1183     iterator       end() _NOEXCEPT          {return __table_.end();}
1184     _LIBCPP_INLINE_VISIBILITY
1185     const_iterator begin()  const _NOEXCEPT {return __table_.begin();}
1186     _LIBCPP_INLINE_VISIBILITY
1187     const_iterator end()    const _NOEXCEPT {return __table_.end();}
1188     _LIBCPP_INLINE_VISIBILITY
1189     const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
1190     _LIBCPP_INLINE_VISIBILITY
1191     const_iterator cend()   const _NOEXCEPT {return __table_.end();}
1192
1193 #ifndef _LIBCPP_CXX03_LANG
1194     template <class... _Args>
1195         _LIBCPP_INLINE_VISIBILITY
1196         iterator emplace(_Args&&... __args)
1197             {return __table_.__emplace_multi(_VSTD::forward<_Args>(__args)...);}
1198     template <class... _Args>
1199         _LIBCPP_INLINE_VISIBILITY
1200         iterator emplace_hint(const_iterator __p, _Args&&... __args)
1201             {return __table_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);}
1202
1203     _LIBCPP_INLINE_VISIBILITY
1204     iterator insert(value_type&& __x) {return __table_.__insert_multi(_VSTD::move(__x));}
1205     _LIBCPP_INLINE_VISIBILITY
1206     iterator insert(const_iterator __p, value_type&& __x)
1207         {return __table_.__insert_multi(__p, _VSTD::move(__x));}
1208     _LIBCPP_INLINE_VISIBILITY
1209     void insert(initializer_list<value_type> __il)
1210         {insert(__il.begin(), __il.end());}
1211 #endif  // _LIBCPP_CXX03_LANG
1212
1213     _LIBCPP_INLINE_VISIBILITY
1214     iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
1215
1216     _LIBCPP_INLINE_VISIBILITY
1217     iterator insert(const_iterator __p, const value_type& __x)
1218         {return __table_.__insert_multi(__p, __x);}
1219
1220     template <class _InputIterator>
1221         _LIBCPP_INLINE_VISIBILITY
1222         void insert(_InputIterator __first, _InputIterator __last);
1223
1224 #if _LIBCPP_STD_VER > 14
1225     _LIBCPP_INLINE_VISIBILITY
1226     iterator insert(node_type&& __nh)
1227     {
1228         _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
1229             "node_type with incompatible allocator passed to unordered_multiset::insert()");
1230         return __table_.template __node_handle_insert_multi<node_type>(
1231             _VSTD::move(__nh));
1232     }
1233     _LIBCPP_INLINE_VISIBILITY
1234     iterator insert(const_iterator __hint, node_type&& __nh)
1235     {
1236         _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
1237             "node_type with incompatible allocator passed to unordered_multiset::insert()");
1238         return __table_.template __node_handle_insert_multi<node_type>(
1239             __hint, _VSTD::move(__nh));
1240     }
1241     _LIBCPP_INLINE_VISIBILITY
1242     node_type extract(const_iterator __position)
1243     {
1244         return __table_.template __node_handle_extract<node_type>(
1245             __position);
1246     }
1247     _LIBCPP_INLINE_VISIBILITY
1248     node_type extract(key_type const& __key)
1249     {
1250         return __table_.template __node_handle_extract<node_type>(__key);
1251     }
1252
1253     template <class _H2, class _P2>
1254     _LIBCPP_INLINE_VISIBILITY
1255     void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>& __source)
1256     {
1257         _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1258                        "merging container with incompatible allocator");
1259         return __table_.__node_handle_merge_multi(__source.__table_);
1260     }
1261     template <class _H2, class _P2>
1262     _LIBCPP_INLINE_VISIBILITY
1263     void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>&& __source)
1264     {
1265         _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1266                        "merging container with incompatible allocator");
1267         return __table_.__node_handle_merge_multi(__source.__table_);
1268     }
1269     template <class _H2, class _P2>
1270     _LIBCPP_INLINE_VISIBILITY
1271     void merge(unordered_set<key_type, _H2, _P2, allocator_type>& __source)
1272     {
1273         _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1274                        "merging container with incompatible allocator");
1275         return __table_.__node_handle_merge_multi(__source.__table_);
1276     }
1277     template <class _H2, class _P2>
1278     _LIBCPP_INLINE_VISIBILITY
1279     void merge(unordered_set<key_type, _H2, _P2, allocator_type>&& __source)
1280     {
1281         _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1282                        "merging container with incompatible allocator");
1283         return __table_.__node_handle_merge_multi(__source.__table_);
1284     }
1285 #endif
1286
1287     _LIBCPP_INLINE_VISIBILITY
1288     iterator erase(const_iterator __p) {return __table_.erase(__p);}
1289     _LIBCPP_INLINE_VISIBILITY
1290     size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
1291     _LIBCPP_INLINE_VISIBILITY
1292     iterator erase(const_iterator __first, const_iterator __last)
1293         {return __table_.erase(__first, __last);}
1294     _LIBCPP_INLINE_VISIBILITY
1295     void clear() _NOEXCEPT {__table_.clear();}
1296
1297     _LIBCPP_INLINE_VISIBILITY
1298     void swap(unordered_multiset& __u)
1299         _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
1300         {__table_.swap(__u.__table_);}
1301
1302     _LIBCPP_INLINE_VISIBILITY
1303     hasher hash_function() const {return __table_.hash_function();}
1304     _LIBCPP_INLINE_VISIBILITY
1305     key_equal key_eq() const {return __table_.key_eq();}
1306
1307     _LIBCPP_INLINE_VISIBILITY
1308     iterator       find(const key_type& __k)       {return __table_.find(__k);}
1309     _LIBCPP_INLINE_VISIBILITY
1310     const_iterator find(const key_type& __k) const {return __table_.find(__k);}
1311     _LIBCPP_INLINE_VISIBILITY
1312     size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
1313     #if _LIBCPP_STD_VER > 17
1314         _LIBCPP_INLINE_VISIBILITY
1315         bool contains(const key_type& __k) const {return find(__k) != end();}
1316     #endif // _LIBCPP_STD_VER > 17
1317     _LIBCPP_INLINE_VISIBILITY
1318     pair<iterator, iterator>             equal_range(const key_type& __k)
1319         {return __table_.__equal_range_multi(__k);}
1320     _LIBCPP_INLINE_VISIBILITY
1321     pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
1322         {return __table_.__equal_range_multi(__k);}
1323
1324     _LIBCPP_INLINE_VISIBILITY
1325     size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
1326     _LIBCPP_INLINE_VISIBILITY
1327     size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
1328
1329     _LIBCPP_INLINE_VISIBILITY
1330     size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);}
1331     _LIBCPP_INLINE_VISIBILITY
1332     size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
1333
1334     _LIBCPP_INLINE_VISIBILITY
1335     local_iterator       begin(size_type __n)        {return __table_.begin(__n);}
1336     _LIBCPP_INLINE_VISIBILITY
1337     local_iterator       end(size_type __n)          {return __table_.end(__n);}
1338     _LIBCPP_INLINE_VISIBILITY
1339     const_local_iterator begin(size_type __n) const  {return __table_.cbegin(__n);}
1340     _LIBCPP_INLINE_VISIBILITY
1341     const_local_iterator end(size_type __n) const    {return __table_.cend(__n);}
1342     _LIBCPP_INLINE_VISIBILITY
1343     const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
1344     _LIBCPP_INLINE_VISIBILITY
1345     const_local_iterator cend(size_type __n) const   {return __table_.cend(__n);}
1346
1347     _LIBCPP_INLINE_VISIBILITY
1348     float load_factor() const _NOEXCEPT {return __table_.load_factor();}
1349     _LIBCPP_INLINE_VISIBILITY
1350     float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
1351     _LIBCPP_INLINE_VISIBILITY
1352     void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
1353     _LIBCPP_INLINE_VISIBILITY
1354     void rehash(size_type __n) {__table_.rehash(__n);}
1355     _LIBCPP_INLINE_VISIBILITY
1356     void reserve(size_type __n) {__table_.reserve(__n);}
1357
1358 #if _LIBCPP_DEBUG_LEVEL >= 2
1359
1360     bool __dereferenceable(const const_iterator* __i) const
1361         {return __table_.__dereferenceable(__i);}
1362     bool __decrementable(const const_iterator* __i) const
1363         {return __table_.__decrementable(__i);}
1364     bool __addable(const const_iterator* __i, ptrdiff_t __n) const
1365         {return __table_.__addable(__i, __n);}
1366     bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
1367         {return __table_.__addable(__i, __n);}
1368
1369 #endif  // _LIBCPP_DEBUG_LEVEL >= 2
1370
1371 };
1372
1373 #ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES
1374 template<class _InputIterator,
1375          class _Hash = hash<__iter_value_type<_InputIterator>>,
1376          class _Pred = equal_to<__iter_value_type<_InputIterator>>,
1377          class _Allocator = allocator<__iter_value_type<_InputIterator>>,
1378          class = _EnableIf<!__is_allocator<_Hash>::value>,
1379          class = _EnableIf<!is_integral<_Hash>::value>,
1380          class = _EnableIf<!__is_allocator<_Pred>::value>,
1381          class = _EnableIf<__is_allocator<_Allocator>::value>>
1382 unordered_multiset(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type = 0,
1383               _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
1384   -> unordered_multiset<__iter_value_type<_InputIterator>, _Hash, _Pred, _Allocator>;
1385
1386 template<class _Tp, class _Hash = hash<_Tp>,
1387          class _Pred = equal_to<_Tp>, class _Allocator = allocator<_Tp>,
1388          class = _EnableIf<!__is_allocator<_Hash>::value>,
1389          class = _EnableIf<!is_integral<_Hash>::value>,
1390          class = _EnableIf<!__is_allocator<_Pred>::value>,
1391          class = _EnableIf<__is_allocator<_Allocator>::value>>
1392 unordered_multiset(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type = 0,
1393               _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
1394   -> unordered_multiset<_Tp, _Hash, _Pred, _Allocator>;
1395
1396 template<class _InputIterator, class _Allocator,
1397          class = _EnableIf<__is_allocator<_Allocator>::value>>
1398 unordered_multiset(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Allocator)
1399   -> unordered_multiset<__iter_value_type<_InputIterator>,
1400                    hash<__iter_value_type<_InputIterator>>,
1401                    equal_to<__iter_value_type<_InputIterator>>,
1402                    _Allocator>;
1403
1404 template<class _InputIterator, class _Hash, class _Allocator,
1405          class = _EnableIf<!__is_allocator<_Hash>::value>,
1406          class = _EnableIf<!is_integral<_Hash>::value>,
1407          class = _EnableIf<__is_allocator<_Allocator>::value>>
1408 unordered_multiset(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type,
1409               _Hash, _Allocator)
1410   -> unordered_multiset<__iter_value_type<_InputIterator>, _Hash,
1411                    equal_to<__iter_value_type<_InputIterator>>,
1412                    _Allocator>;
1413
1414 template<class _Tp, class _Allocator,
1415          class = _EnableIf<__is_allocator<_Allocator>::value>>
1416 unordered_multiset(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Allocator)
1417   -> unordered_multiset<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
1418
1419 template<class _Tp, class _Hash, class _Allocator,
1420          class = _EnableIf<!__is_allocator<_Hash>::value>,
1421          class = _EnableIf<!is_integral<_Hash>::value>,
1422          class = _EnableIf<__is_allocator<_Allocator>::value>>
1423 unordered_multiset(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
1424   -> unordered_multiset<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
1425 #endif
1426
1427 template <class _Value, class _Hash, class _Pred, class _Alloc>
1428 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1429         size_type __n, const hasher& __hf, const key_equal& __eql)
1430     : __table_(__hf, __eql)
1431 {
1432 #if _LIBCPP_DEBUG_LEVEL >= 2
1433     __get_db()->__insert_c(this);
1434 #endif
1435     __table_.rehash(__n);
1436 }
1437
1438 template <class _Value, class _Hash, class _Pred, class _Alloc>
1439 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1440         size_type __n, const hasher& __hf, const key_equal& __eql,
1441         const allocator_type& __a)
1442     : __table_(__hf, __eql, __a)
1443 {
1444 #if _LIBCPP_DEBUG_LEVEL >= 2
1445     __get_db()->__insert_c(this);
1446 #endif
1447     __table_.rehash(__n);
1448 }
1449
1450 template <class _Value, class _Hash, class _Pred, class _Alloc>
1451 template <class _InputIterator>
1452 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1453         _InputIterator __first, _InputIterator __last)
1454 {
1455 #if _LIBCPP_DEBUG_LEVEL >= 2
1456     __get_db()->__insert_c(this);
1457 #endif
1458     insert(__first, __last);
1459 }
1460
1461 template <class _Value, class _Hash, class _Pred, class _Alloc>
1462 template <class _InputIterator>
1463 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1464         _InputIterator __first, _InputIterator __last, size_type __n,
1465         const hasher& __hf, const key_equal& __eql)
1466     : __table_(__hf, __eql)
1467 {
1468 #if _LIBCPP_DEBUG_LEVEL >= 2
1469     __get_db()->__insert_c(this);
1470 #endif
1471     __table_.rehash(__n);
1472     insert(__first, __last);
1473 }
1474
1475 template <class _Value, class _Hash, class _Pred, class _Alloc>
1476 template <class _InputIterator>
1477 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1478         _InputIterator __first, _InputIterator __last, size_type __n,
1479         const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1480     : __table_(__hf, __eql, __a)
1481 {
1482 #if _LIBCPP_DEBUG_LEVEL >= 2
1483     __get_db()->__insert_c(this);
1484 #endif
1485     __table_.rehash(__n);
1486     insert(__first, __last);
1487 }
1488
1489 template <class _Value, class _Hash, class _Pred, class _Alloc>
1490 inline
1491 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1492         const allocator_type& __a)
1493     : __table_(__a)
1494 {
1495 #if _LIBCPP_DEBUG_LEVEL >= 2
1496     __get_db()->__insert_c(this);
1497 #endif
1498 }
1499
1500 template <class _Value, class _Hash, class _Pred, class _Alloc>
1501 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1502         const unordered_multiset& __u)
1503     : __table_(__u.__table_)
1504 {
1505 #if _LIBCPP_DEBUG_LEVEL >= 2
1506     __get_db()->__insert_c(this);
1507 #endif
1508     __table_.rehash(__u.bucket_count());
1509     insert(__u.begin(), __u.end());
1510 }
1511
1512 template <class _Value, class _Hash, class _Pred, class _Alloc>
1513 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1514         const unordered_multiset& __u, const allocator_type& __a)
1515     : __table_(__u.__table_, __a)
1516 {
1517 #if _LIBCPP_DEBUG_LEVEL >= 2
1518     __get_db()->__insert_c(this);
1519 #endif
1520     __table_.rehash(__u.bucket_count());
1521     insert(__u.begin(), __u.end());
1522 }
1523
1524 #ifndef _LIBCPP_CXX03_LANG
1525
1526 template <class _Value, class _Hash, class _Pred, class _Alloc>
1527 inline
1528 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1529         unordered_multiset&& __u)
1530     _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
1531     : __table_(_VSTD::move(__u.__table_))
1532 {
1533 #if _LIBCPP_DEBUG_LEVEL >= 2
1534     __get_db()->__insert_c(this);
1535     __get_db()->swap(this, &__u);
1536 #endif
1537 }
1538
1539 template <class _Value, class _Hash, class _Pred, class _Alloc>
1540 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1541         unordered_multiset&& __u, const allocator_type& __a)
1542     : __table_(_VSTD::move(__u.__table_), __a)
1543 {
1544 #if _LIBCPP_DEBUG_LEVEL >= 2
1545     __get_db()->__insert_c(this);
1546 #endif
1547     if (__a != __u.get_allocator())
1548     {
1549         iterator __i = __u.begin();
1550         while (__u.size() != 0)
1551             __table_.__insert_multi(_VSTD::move(__u.__table_.remove(__i++)->__value_));
1552     }
1553 #if _LIBCPP_DEBUG_LEVEL >= 2
1554     else
1555         __get_db()->swap(this, &__u);
1556 #endif
1557 }
1558
1559 template <class _Value, class _Hash, class _Pred, class _Alloc>
1560 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1561         initializer_list<value_type> __il)
1562 {
1563 #if _LIBCPP_DEBUG_LEVEL >= 2
1564     __get_db()->__insert_c(this);
1565 #endif
1566     insert(__il.begin(), __il.end());
1567 }
1568
1569 template <class _Value, class _Hash, class _Pred, class _Alloc>
1570 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1571         initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1572         const key_equal& __eql)
1573     : __table_(__hf, __eql)
1574 {
1575 #if _LIBCPP_DEBUG_LEVEL >= 2
1576     __get_db()->__insert_c(this);
1577 #endif
1578     __table_.rehash(__n);
1579     insert(__il.begin(), __il.end());
1580 }
1581
1582 template <class _Value, class _Hash, class _Pred, class _Alloc>
1583 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1584         initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1585         const key_equal& __eql, const allocator_type& __a)
1586     : __table_(__hf, __eql, __a)
1587 {
1588 #if _LIBCPP_DEBUG_LEVEL >= 2
1589     __get_db()->__insert_c(this);
1590 #endif
1591     __table_.rehash(__n);
1592     insert(__il.begin(), __il.end());
1593 }
1594
1595 template <class _Value, class _Hash, class _Pred, class _Alloc>
1596 inline
1597 unordered_multiset<_Value, _Hash, _Pred, _Alloc>&
1598 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(
1599         unordered_multiset&& __u)
1600     _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
1601 {
1602     __table_ = _VSTD::move(__u.__table_);
1603     return *this;
1604 }
1605
1606 template <class _Value, class _Hash, class _Pred, class _Alloc>
1607 inline
1608 unordered_multiset<_Value, _Hash, _Pred, _Alloc>&
1609 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(
1610         initializer_list<value_type> __il)
1611 {
1612     __table_.__assign_multi(__il.begin(), __il.end());
1613     return *this;
1614 }
1615
1616 #endif  // _LIBCPP_CXX03_LANG
1617
1618 template <class _Value, class _Hash, class _Pred, class _Alloc>
1619 template <class _InputIterator>
1620 inline
1621 void
1622 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
1623                                                          _InputIterator __last)
1624 {
1625     for (; __first != __last; ++__first)
1626         __table_.__insert_multi(*__first);
1627 }
1628
1629 template <class _Value, class _Hash, class _Pred, class _Alloc>
1630 inline _LIBCPP_INLINE_VISIBILITY
1631 void
1632 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1633      unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1634     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1635 {
1636     __x.swap(__y);
1637 }
1638
1639 #if _LIBCPP_STD_VER > 17
1640 template <class _Value, class _Hash, class _Pred, class _Alloc, class _Predicate>
1641 inline _LIBCPP_INLINE_VISIBILITY
1642 void erase_if(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __c, _Predicate __pred)
1643 { __libcpp_erase_if_container(__c, __pred); }
1644 #endif
1645
1646 template <class _Value, class _Hash, class _Pred, class _Alloc>
1647 bool
1648 operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1649            const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1650 {
1651     if (__x.size() != __y.size())
1652         return false;
1653     typedef typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator
1654                                                                  const_iterator;
1655     typedef pair<const_iterator, const_iterator> _EqRng;
1656     for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;)
1657     {
1658         _EqRng __xeq = __x.equal_range(*__i);
1659         _EqRng __yeq = __y.equal_range(*__i);
1660         if (_VSTD::distance(__xeq.first, __xeq.second) !=
1661             _VSTD::distance(__yeq.first, __yeq.second) ||
1662                   !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first))
1663             return false;
1664         __i = __xeq.second;
1665     }
1666     return true;
1667 }
1668
1669 template <class _Value, class _Hash, class _Pred, class _Alloc>
1670 inline _LIBCPP_INLINE_VISIBILITY
1671 bool
1672 operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1673            const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1674 {
1675     return !(__x == __y);
1676 }
1677
1678 _LIBCPP_END_NAMESPACE_STD
1679
1680 #endif  // _LIBCPP_UNORDERED_SET