contrib/libc++/include/unordered_set

   1 // -*- C++ -*-
   2 //===-------------------------- unordered_set -----------------------------===//
   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_SET
  12 #define _LIBCPP_UNORDERED_SET
  13
  14 /*
  15
  16     unordered_set synopsis
  17
  18 #include <initializer_list>
  19
  20 namespace std
  21 {
  22
  23 template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,
  24           class Alloc = allocator<Value>>
  25 class unordered_set
  26 {
  27 public:
  28     // types
  29     typedef Value                                                      key_type;
  30     typedef key_type                                                   value_type;
  31     typedef Hash                                                       hasher;
  32     typedef Pred                                                       key_equal;
  33     typedef Alloc                                                      allocator_type;
  34     typedef value_type&                                                reference;
  35     typedef const value_type&                                          const_reference;
  36     typedef typename allocator_traits<allocator_type>::pointer         pointer;
  37     typedef typename allocator_traits<allocator_type>::const_pointer   const_pointer;
  38     typedef typename allocator_traits<allocator_type>::size_type       size_type;
  39     typedef typename allocator_traits<allocator_type>::difference_type difference_type;
  40
  41     typedef /unspecified/ iterator;
  42     typedef /unspecified/ const_iterator;
  43     typedef /unspecified/ local_iterator;
  44     typedef /unspecified/ const_local_iterator;
  45
  46     typedef unspecified node_type unspecified;                            // C++17
  47     typedef INSERT_RETURN_TYPE<iterator, node_type> insert_return_type;   // C++17
  48
  49     unordered_set()
  50         noexcept(
  51             is_nothrow_default_constructible<hasher>::value &&
  52             is_nothrow_default_constructible<key_equal>::value &&
  53             is_nothrow_default_constructible<allocator_type>::value);
  54     explicit unordered_set(size_type n, const hasher& hf = hasher(),
  55                            const key_equal& eql = key_equal(),
  56                            const allocator_type& a = allocator_type());
  57     template <class InputIterator>
  58         unordered_set(InputIterator f, InputIterator l,
  59                       size_type n = 0, const hasher& hf = hasher(),
  60                       const key_equal& eql = key_equal(),
  61                       const allocator_type& a = allocator_type());
  62     explicit unordered_set(const allocator_type&);
  63     unordered_set(const unordered_set&);
  64     unordered_set(const unordered_set&, const Allocator&);
  65     unordered_set(unordered_set&&)
  66         noexcept(
  67             is_nothrow_move_constructible<hasher>::value &&
  68             is_nothrow_move_constructible<key_equal>::value &&
  69             is_nothrow_move_constructible<allocator_type>::value);
  70     unordered_set(unordered_set&&, const Allocator&);
  71     unordered_set(initializer_list<value_type>, size_type n = 0,
  72                   const hasher& hf = hasher(), const key_equal& eql = key_equal(),
  73                   const allocator_type& a = allocator_type());
  74     unordered_set(size_type n, const allocator_type& a); // C++14
  75     unordered_set(size_type n, const hasher& hf, const allocator_type& a); // C++14
  76     template <class InputIterator>
  77       unordered_set(InputIterator f, InputIterator l, size_type n, const allocator_type& a); // C++14
  78     template <class InputIterator>
  79       unordered_set(InputIterator f, InputIterator l, size_type n,
  80                     const hasher& hf,  const allocator_type& a); // C++14
  81     unordered_set(initializer_list<value_type> il, size_type n, const allocator_type& a); // C++14
  82     unordered_set(initializer_list<value_type> il, size_type n,
  83                   const hasher& hf,  const allocator_type& a); // C++14
  84     ~unordered_set();
  85     unordered_set& operator=(const unordered_set&);
  86     unordered_set& operator=(unordered_set&&)
  87         noexcept(
  88             allocator_type::propagate_on_container_move_assignment::value &&
  89             is_nothrow_move_assignable<allocator_type>::value &&
  90             is_nothrow_move_assignable<hasher>::value &&
  91             is_nothrow_move_assignable<key_equal>::value);
  92     unordered_set& operator=(initializer_list<value_type>);
  93
  94     allocator_type get_allocator() const noexcept;
  95
  96     bool      empty() const noexcept;
  97     size_type size() const noexcept;
  98     size_type max_size() const noexcept;
  99
 100     iterator       begin() noexcept;
 101     iterator       end() noexcept;
 102     const_iterator begin()  const noexcept;
 103     const_iterator end()    const noexcept;
 104     const_iterator cbegin() const noexcept;
 105     const_iterator cend()   const noexcept;
 106
 107     template <class... Args>
 108         pair<iterator, bool> emplace(Args&&... args);
 109     template <class... Args>
 110         iterator emplace_hint(const_iterator position, Args&&... args);
 111     pair<iterator, bool> insert(const value_type& obj);
 112     pair<iterator, bool> insert(value_type&& obj);
 113     iterator insert(const_iterator hint, const value_type& obj);
 114     iterator insert(const_iterator hint, value_type&& obj);
 115     template <class InputIterator>
 116         void insert(InputIterator first, InputIterator last);
 117     void insert(initializer_list<value_type>);
 118
 119     node_type extract(const_iterator position);                       // C++17
 120     node_type extract(const key_type& x);                             // C++17
 121     insert_return_type insert(node_type&& nh);                        // C++17
 122     iterator           insert(const_iterator hint, node_type&& nh);   // C++17
 123
 124     iterator erase(const_iterator position);
 125     iterator erase(iterator position);  // C++14
 126     size_type erase(const key_type& k);
 127     iterator erase(const_iterator first, const_iterator last);
 128     void clear() noexcept;
 129
 130     template<class H2, class P2>
 131       void merge(unordered_set<Key, H2, P2, Allocator>& source);         // C++17
 132     template<class H2, class P2>
 133       void merge(unordered_set<Key, H2, P2, Allocator>&& source);        // C++17
 134     template<class H2, class P2>
 135       void merge(unordered_multiset<Key, H2, P2, Allocator>& source);    // C++17
 136     template<class H2, class P2>
 137       void merge(unordered_multiset<Key, H2, P2, Allocator>&& source);   // C++17
 138
 139     void swap(unordered_set&)
 140        noexcept(allocator_traits<Allocator>::is_always_equal::value &&
 141                  noexcept(swap(declval<hasher&>(), declval<hasher&>())) &&
 142                  noexcept(swap(declval<key_equal&>(), declval<key_equal&>()))); // C++17
 143
 144     hasher hash_function() const;
 145     key_equal key_eq() const;
 146
 147     iterator       find(const key_type& k);
 148     const_iterator find(const key_type& k) const;
 149     size_type count(const key_type& k) const;
 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     pair<iterator, iterator>             equal_range(const key_type& k);
 315     pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
 316
 317     size_type bucket_count() const noexcept;
 318     size_type max_bucket_count() const noexcept;
 319
 320     size_type bucket_size(size_type n) const;
 321     size_type bucket(const key_type& k) const;
 322
 323     local_iterator       begin(size_type n);
 324     local_iterator       end(size_type n);
 325     const_local_iterator begin(size_type n) const;
 326     const_local_iterator end(size_type n) const;
 327     const_local_iterator cbegin(size_type n) const;
 328     const_local_iterator cend(size_type n) const;
 329
 330     float load_factor() const noexcept;
 331     float max_load_factor() const noexcept;
 332     void max_load_factor(float z);
 333     void rehash(size_type n);
 334     void reserve(size_type n);
 335 };
 336
 337 template <class Value, class Hash, class Pred, class Alloc>
 338     void swap(unordered_multiset<Value, Hash, Pred, Alloc>& x,
 339               unordered_multiset<Value, Hash, Pred, Alloc>& y)
 340               noexcept(noexcept(x.swap(y)));
 341
 342 template <class K, class T, class H, class P, class A, class Predicate>
 343     void erase_if(unordered_set<K, T, H, P, A>& c, Predicate pred);       // C++20
 344
 345 template <class K, class T, class H, class P, class A, class Predicate>
 346     void erase_if(unordered_multiset<K, T, H, P, A>& c, Predicate pred);  // C++20
 347
 348
 349 template <class Value, class Hash, class Pred, class Alloc>
 350     bool
 351     operator==(const unordered_multiset<Value, Hash, Pred, Alloc>& x,
 352                const unordered_multiset<Value, Hash, Pred, Alloc>& y);
 353
 354 template <class Value, class Hash, class Pred, class Alloc>
 355     bool
 356     operator!=(const unordered_multiset<Value, Hash, Pred, Alloc>& x,
 357                const unordered_multiset<Value, Hash, Pred, Alloc>& y);
 358 }  // std
 359
 360 */
 361
 362 #include <__config>
 363 #include <__hash_table>
 364 #include <__node_handle>
 365 #include <functional>
 366 #include <version>
 367
 368 #include <__debug>
 369
 370 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 371 #pragma GCC system_header
 372 #endif
 373
 374 _LIBCPP_BEGIN_NAMESPACE_STD
 375
 376 template <class _Value, class _Hash, class _Pred, class _Alloc>
 377 class unordered_multiset;
 378
 379 template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>,
 380           class _Alloc = allocator<_Value> >
 381 class _LIBCPP_TEMPLATE_VIS unordered_set
 382 {
 383 public:
 384     // types
 385     typedef _Value                                                     key_type;
 386     typedef key_type                                                   value_type;
 387     typedef _Hash                                                      hasher;
 388     typedef _Pred                                                      key_equal;
 389     typedef _Alloc                                                     allocator_type;
 390     typedef value_type&                                                reference;
 391     typedef const value_type&                                          const_reference;
 392     static_assert((is_same<value_type, typename allocator_type::value_type>::value),
 393                   "Invalid allocator::value_type");
 394     static_assert(sizeof(__diagnose_unordered_container_requirements<_Value, _Hash, _Pred>(0)), "");
 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     // ~unordered_set() = default;
 491     _LIBCPP_INLINE_VISIBILITY
 492     unordered_set& operator=(const unordered_set& __u)
 493     {
 494         __table_ = __u.__table_;
 495         return *this;
 496     }
 497 #ifndef _LIBCPP_CXX03_LANG
 498     _LIBCPP_INLINE_VISIBILITY
 499     unordered_set& operator=(unordered_set&& __u)
 500         _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
 501     _LIBCPP_INLINE_VISIBILITY
 502     unordered_set& operator=(initializer_list<value_type> __il);
 503 #endif  // _LIBCPP_CXX03_LANG
 504
 505     _LIBCPP_INLINE_VISIBILITY
 506     allocator_type get_allocator() const _NOEXCEPT
 507         {return allocator_type(__table_.__node_alloc());}
 508
 509     _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
 510     bool      empty() const _NOEXCEPT {return __table_.size() == 0;}
 511     _LIBCPP_INLINE_VISIBILITY
 512     size_type size() const _NOEXCEPT  {return __table_.size();}
 513     _LIBCPP_INLINE_VISIBILITY
 514     size_type max_size() const _NOEXCEPT {return __table_.max_size();}
 515
 516     _LIBCPP_INLINE_VISIBILITY
 517     iterator       begin() _NOEXCEPT        {return __table_.begin();}
 518     _LIBCPP_INLINE_VISIBILITY
 519     iterator       end() _NOEXCEPT          {return __table_.end();}
 520     _LIBCPP_INLINE_VISIBILITY
 521     const_iterator begin()  const _NOEXCEPT {return __table_.begin();}
 522     _LIBCPP_INLINE_VISIBILITY
 523     const_iterator end()    const _NOEXCEPT {return __table_.end();}
 524     _LIBCPP_INLINE_VISIBILITY
 525     const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
 526     _LIBCPP_INLINE_VISIBILITY
 527     const_iterator cend()   const _NOEXCEPT {return __table_.end();}
 528
 529 #ifndef _LIBCPP_CXX03_LANG
 530     template <class... _Args>
 531         _LIBCPP_INLINE_VISIBILITY
 532         pair<iterator, bool> emplace(_Args&&... __args)
 533             {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...);}
 534     template <class... _Args>
 535         _LIBCPP_INLINE_VISIBILITY
 536 #if _LIBCPP_DEBUG_LEVEL >= 2
 537         iterator emplace_hint(const_iterator __p, _Args&&... __args)
 538         {
 539             _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
 540                 "unordered_set::emplace_hint(const_iterator, args...) called with an iterator not"
 541                 " referring to this unordered_set");
 542             return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first;
 543         }
 544 #else
 545         iterator emplace_hint(const_iterator, _Args&&... __args)
 546             {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first;}
 547 #endif
 548
 549     _LIBCPP_INLINE_VISIBILITY
 550     pair<iterator, bool> insert(value_type&& __x)
 551         {return __table_.__insert_unique(_VSTD::move(__x));}
 552     _LIBCPP_INLINE_VISIBILITY
 553 #if _LIBCPP_DEBUG_LEVEL >= 2
 554     iterator insert(const_iterator __p, value_type&& __x)
 555         {
 556             _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
 557                 "unordered_set::insert(const_iterator, value_type&&) called with an iterator not"
 558                 " referring to this unordered_set");
 559             return insert(_VSTD::move(__x)).first;
 560         }
 561 #else
 562     iterator insert(const_iterator, value_type&& __x)
 563         {return insert(_VSTD::move(__x)).first;}
 564 #endif
 565     _LIBCPP_INLINE_VISIBILITY
 566     void insert(initializer_list<value_type> __il)
 567         {insert(__il.begin(), __il.end());}
 568 #endif  // _LIBCPP_CXX03_LANG
 569     _LIBCPP_INLINE_VISIBILITY
 570     pair<iterator, bool> insert(const value_type& __x)
 571         {return __table_.__insert_unique(__x);}
 572
 573     _LIBCPP_INLINE_VISIBILITY
 574 #if _LIBCPP_DEBUG_LEVEL >= 2
 575     iterator insert(const_iterator __p, const value_type& __x)
 576         {
 577             _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
 578                 "unordered_set::insert(const_iterator, const value_type&) called with an iterator not"
 579                 " referring to this unordered_set");
 580             return insert(__x).first;
 581         }
 582 #else
 583     iterator insert(const_iterator, const value_type& __x)
 584         {return insert(__x).first;}
 585 #endif
 586     template <class _InputIterator>
 587         _LIBCPP_INLINE_VISIBILITY
 588         void insert(_InputIterator __first, _InputIterator __last);
 589
 590     _LIBCPP_INLINE_VISIBILITY
 591     iterator erase(const_iterator __p) {return __table_.erase(__p);}
 592     _LIBCPP_INLINE_VISIBILITY
 593     size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
 594     _LIBCPP_INLINE_VISIBILITY
 595     iterator erase(const_iterator __first, const_iterator __last)
 596         {return __table_.erase(__first, __last);}
 597     _LIBCPP_INLINE_VISIBILITY
 598     void clear() _NOEXCEPT {__table_.clear();}
 599
 600 #if _LIBCPP_STD_VER > 14
 601     _LIBCPP_INLINE_VISIBILITY
 602     insert_return_type insert(node_type&& __nh)
 603     {
 604         _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
 605             "node_type with incompatible allocator passed to unordered_set::insert()");
 606         return __table_.template __node_handle_insert_unique<
 607             node_type, insert_return_type>(_VSTD::move(__nh));
 608     }
 609     _LIBCPP_INLINE_VISIBILITY
 610     iterator insert(const_iterator __h, node_type&& __nh)
 611     {
 612         _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
 613             "node_type with incompatible allocator passed to unordered_set::insert()");
 614         return __table_.template __node_handle_insert_unique<node_type>(
 615             __h, _VSTD::move(__nh));
 616     }
 617     _LIBCPP_INLINE_VISIBILITY
 618     node_type extract(key_type const& __key)
 619     {
 620         return __table_.template __node_handle_extract<node_type>(__key);
 621     }
 622     _LIBCPP_INLINE_VISIBILITY
 623     node_type extract(const_iterator __it)
 624     {
 625         return __table_.template __node_handle_extract<node_type>(__it);
 626     }
 627
 628     template<class _H2, class _P2>
 629     _LIBCPP_INLINE_VISIBILITY
 630     void merge(unordered_set<key_type, _H2, _P2, allocator_type>& __source)
 631     {
 632         _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
 633                        "merging container with incompatible allocator");
 634         __table_.__node_handle_merge_unique(__source.__table_);
 635     }
 636     template<class _H2, class _P2>
 637     _LIBCPP_INLINE_VISIBILITY
 638     void merge(unordered_set<key_type, _H2, _P2, allocator_type>&& __source)
 639     {
 640         _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
 641                        "merging container with incompatible allocator");
 642         __table_.__node_handle_merge_unique(__source.__table_);
 643     }
 644     template<class _H2, class _P2>
 645     _LIBCPP_INLINE_VISIBILITY
 646     void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>& __source)
 647     {
 648         _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
 649                        "merging container with incompatible allocator");
 650         __table_.__node_handle_merge_unique(__source.__table_);
 651     }
 652     template<class _H2, class _P2>
 653     _LIBCPP_INLINE_VISIBILITY
 654     void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>&& __source)
 655     {
 656         _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
 657                        "merging container with incompatible allocator");
 658         __table_.__node_handle_merge_unique(__source.__table_);
 659     }
 660 #endif
 661
 662     _LIBCPP_INLINE_VISIBILITY
 663     void swap(unordered_set& __u)
 664         _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
 665         {__table_.swap(__u.__table_);}
 666
 667     _LIBCPP_INLINE_VISIBILITY
 668     hasher hash_function() const {return __table_.hash_function();}
 669     _LIBCPP_INLINE_VISIBILITY
 670     key_equal key_eq() const {return __table_.key_eq();}
 671
 672     _LIBCPP_INLINE_VISIBILITY
 673     iterator       find(const key_type& __k)       {return __table_.find(__k);}
 674     _LIBCPP_INLINE_VISIBILITY
 675     const_iterator find(const key_type& __k) const {return __table_.find(__k);}
 676     _LIBCPP_INLINE_VISIBILITY
 677     size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
 678     _LIBCPP_INLINE_VISIBILITY
 679     pair<iterator, iterator>             equal_range(const key_type& __k)
 680         {return __table_.__equal_range_unique(__k);}
 681     _LIBCPP_INLINE_VISIBILITY
 682     pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
 683         {return __table_.__equal_range_unique(__k);}
 684
 685     _LIBCPP_INLINE_VISIBILITY
 686     size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
 687     _LIBCPP_INLINE_VISIBILITY
 688     size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
 689
 690     _LIBCPP_INLINE_VISIBILITY
 691     size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);}
 692     _LIBCPP_INLINE_VISIBILITY
 693     size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
 694
 695     _LIBCPP_INLINE_VISIBILITY
 696     local_iterator       begin(size_type __n)        {return __table_.begin(__n);}
 697     _LIBCPP_INLINE_VISIBILITY
 698     local_iterator       end(size_type __n)          {return __table_.end(__n);}
 699     _LIBCPP_INLINE_VISIBILITY
 700     const_local_iterator begin(size_type __n) const  {return __table_.cbegin(__n);}
 701     _LIBCPP_INLINE_VISIBILITY
 702     const_local_iterator end(size_type __n) const    {return __table_.cend(__n);}
 703     _LIBCPP_INLINE_VISIBILITY
 704     const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
 705     _LIBCPP_INLINE_VISIBILITY
 706     const_local_iterator cend(size_type __n) const   {return __table_.cend(__n);}
 707
 708     _LIBCPP_INLINE_VISIBILITY
 709     float load_factor() const _NOEXCEPT {return __table_.load_factor();}
 710     _LIBCPP_INLINE_VISIBILITY
 711     float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
 712     _LIBCPP_INLINE_VISIBILITY
 713     void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
 714     _LIBCPP_INLINE_VISIBILITY
 715     void rehash(size_type __n) {__table_.rehash(__n);}
 716     _LIBCPP_INLINE_VISIBILITY
 717     void reserve(size_type __n) {__table_.reserve(__n);}
 718
 719 #if _LIBCPP_DEBUG_LEVEL >= 2
 720
 721     bool __dereferenceable(const const_iterator* __i) const
 722         {return __table_.__dereferenceable(__i);}
 723     bool __decrementable(const const_iterator* __i) const
 724         {return __table_.__decrementable(__i);}
 725     bool __addable(const const_iterator* __i, ptrdiff_t __n) const
 726         {return __table_.__addable(__i, __n);}
 727     bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
 728         {return __table_.__addable(__i, __n);}
 729
 730 #endif  // _LIBCPP_DEBUG_LEVEL >= 2
 731
 732 };
 733
 734 template <class _Value, class _Hash, class _Pred, class _Alloc>
 735 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n,
 736         const hasher& __hf, const key_equal& __eql)
 737     : __table_(__hf, __eql)
 738 {
 739 #if _LIBCPP_DEBUG_LEVEL >= 2
 740     __get_db()->__insert_c(this);
 741 #endif
 742     __table_.rehash(__n);
 743 }
 744
 745 template <class _Value, class _Hash, class _Pred, class _Alloc>
 746 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n,
 747         const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
 748     : __table_(__hf, __eql, __a)
 749 {
 750 #if _LIBCPP_DEBUG_LEVEL >= 2
 751     __get_db()->__insert_c(this);
 752 #endif
 753     __table_.rehash(__n);
 754 }
 755
 756 template <class _Value, class _Hash, class _Pred, class _Alloc>
 757 template <class _InputIterator>
 758 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
 759         _InputIterator __first, _InputIterator __last)
 760 {
 761 #if _LIBCPP_DEBUG_LEVEL >= 2
 762     __get_db()->__insert_c(this);
 763 #endif
 764     insert(__first, __last);
 765 }
 766
 767 template <class _Value, class _Hash, class _Pred, class _Alloc>
 768 template <class _InputIterator>
 769 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
 770         _InputIterator __first, _InputIterator __last, size_type __n,
 771         const hasher& __hf, const key_equal& __eql)
 772     : __table_(__hf, __eql)
 773 {
 774 #if _LIBCPP_DEBUG_LEVEL >= 2
 775     __get_db()->__insert_c(this);
 776 #endif
 777     __table_.rehash(__n);
 778     insert(__first, __last);
 779 }
 780
 781 template <class _Value, class _Hash, class _Pred, class _Alloc>
 782 template <class _InputIterator>
 783 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
 784         _InputIterator __first, _InputIterator __last, size_type __n,
 785         const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
 786     : __table_(__hf, __eql, __a)
 787 {
 788 #if _LIBCPP_DEBUG_LEVEL >= 2
 789     __get_db()->__insert_c(this);
 790 #endif
 791     __table_.rehash(__n);
 792     insert(__first, __last);
 793 }
 794
 795 template <class _Value, class _Hash, class _Pred, class _Alloc>
 796 inline
 797 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
 798         const allocator_type& __a)
 799     : __table_(__a)
 800 {
 801 #if _LIBCPP_DEBUG_LEVEL >= 2
 802     __get_db()->__insert_c(this);
 803 #endif
 804 }
 805
 806 template <class _Value, class _Hash, class _Pred, class _Alloc>
 807 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
 808         const unordered_set& __u)
 809     : __table_(__u.__table_)
 810 {
 811 #if _LIBCPP_DEBUG_LEVEL >= 2
 812     __get_db()->__insert_c(this);
 813 #endif
 814     __table_.rehash(__u.bucket_count());
 815     insert(__u.begin(), __u.end());
 816 }
 817
 818 template <class _Value, class _Hash, class _Pred, class _Alloc>
 819 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
 820         const unordered_set& __u, const allocator_type& __a)
 821     : __table_(__u.__table_, __a)
 822 {
 823 #if _LIBCPP_DEBUG_LEVEL >= 2
 824     __get_db()->__insert_c(this);
 825 #endif
 826     __table_.rehash(__u.bucket_count());
 827     insert(__u.begin(), __u.end());
 828 }
 829
 830 #ifndef _LIBCPP_CXX03_LANG
 831
 832 template <class _Value, class _Hash, class _Pred, class _Alloc>
 833 inline
 834 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
 835         unordered_set&& __u)
 836     _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
 837     : __table_(_VSTD::move(__u.__table_))
 838 {
 839 #if _LIBCPP_DEBUG_LEVEL >= 2
 840     __get_db()->__insert_c(this);
 841     __get_db()->swap(this, &__u);
 842 #endif
 843 }
 844
 845 template <class _Value, class _Hash, class _Pred, class _Alloc>
 846 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
 847         unordered_set&& __u, const allocator_type& __a)
 848     : __table_(_VSTD::move(__u.__table_), __a)
 849 {
 850 #if _LIBCPP_DEBUG_LEVEL >= 2
 851     __get_db()->__insert_c(this);
 852 #endif
 853     if (__a != __u.get_allocator())
 854     {
 855         iterator __i = __u.begin();
 856         while (__u.size() != 0)
 857             __table_.__insert_unique(_VSTD::move(__u.__table_.remove(__i++)->__value_));
 858     }
 859 #if _LIBCPP_DEBUG_LEVEL >= 2
 860     else
 861         __get_db()->swap(this, &__u);
 862 #endif
 863 }
 864
 865 template <class _Value, class _Hash, class _Pred, class _Alloc>
 866 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
 867         initializer_list<value_type> __il)
 868 {
 869 #if _LIBCPP_DEBUG_LEVEL >= 2
 870     __get_db()->__insert_c(this);
 871 #endif
 872     insert(__il.begin(), __il.end());
 873 }
 874
 875 template <class _Value, class _Hash, class _Pred, class _Alloc>
 876 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
 877         initializer_list<value_type> __il, size_type __n, const hasher& __hf,
 878         const key_equal& __eql)
 879     : __table_(__hf, __eql)
 880 {
 881 #if _LIBCPP_DEBUG_LEVEL >= 2
 882     __get_db()->__insert_c(this);
 883 #endif
 884     __table_.rehash(__n);
 885     insert(__il.begin(), __il.end());
 886 }
 887
 888 template <class _Value, class _Hash, class _Pred, class _Alloc>
 889 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
 890         initializer_list<value_type> __il, size_type __n, const hasher& __hf,
 891         const key_equal& __eql, const allocator_type& __a)
 892     : __table_(__hf, __eql, __a)
 893 {
 894 #if _LIBCPP_DEBUG_LEVEL >= 2
 895     __get_db()->__insert_c(this);
 896 #endif
 897     __table_.rehash(__n);
 898     insert(__il.begin(), __il.end());
 899 }
 900
 901 template <class _Value, class _Hash, class _Pred, class _Alloc>
 902 inline
 903 unordered_set<_Value, _Hash, _Pred, _Alloc>&
 904 unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(unordered_set&& __u)
 905     _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
 906 {
 907     __table_ = _VSTD::move(__u.__table_);
 908     return *this;
 909 }
 910
 911 template <class _Value, class _Hash, class _Pred, class _Alloc>
 912 inline
 913 unordered_set<_Value, _Hash, _Pred, _Alloc>&
 914 unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(
 915         initializer_list<value_type> __il)
 916 {
 917     __table_.__assign_unique(__il.begin(), __il.end());
 918     return *this;
 919 }
 920
 921 #endif  // _LIBCPP_CXX03_LANG
 922
 923 template <class _Value, class _Hash, class _Pred, class _Alloc>
 924 template <class _InputIterator>
 925 inline
 926 void
 927 unordered_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
 928                                                     _InputIterator __last)
 929 {
 930     for (; __first != __last; ++__first)
 931         __table_.__insert_unique(*__first);
 932 }
 933
 934 template <class _Value, class _Hash, class _Pred, class _Alloc>
 935 inline _LIBCPP_INLINE_VISIBILITY
 936 void
 937 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
 938      unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
 939     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
 940 {
 941     __x.swap(__y);
 942 }
 943
 944 #if _LIBCPP_STD_VER > 17
 945 template <class _Value, class _Hash, class _Pred, class _Alloc, class _Predicate>
 946 inline _LIBCPP_INLINE_VISIBILITY
 947 void erase_if(unordered_set<_Value, _Hash, _Pred, _Alloc>& __c, _Predicate __pred)
 948 { __libcpp_erase_if_container(__c, __pred); }
 949 #endif
 950
 951 template <class _Value, class _Hash, class _Pred, class _Alloc>
 952 bool
 953 operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
 954            const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
 955 {
 956     if (__x.size() != __y.size())
 957         return false;
 958     typedef typename unordered_set<_Value, _Hash, _Pred, _Alloc>::const_iterator
 959                                                                  const_iterator;
 960     for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();
 961             __i != __ex; ++__i)
 962     {
 963         const_iterator __j = __y.find(*__i);
 964         if (__j == __ey || !(*__i == *__j))
 965             return false;
 966     }
 967     return true;
 968 }
 969
 970 template <class _Value, class _Hash, class _Pred, class _Alloc>
 971 inline _LIBCPP_INLINE_VISIBILITY
 972 bool
 973 operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
 974            const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
 975 {
 976     return !(__x == __y);
 977 }
 978
 979 template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>,
 980           class _Alloc = allocator<_Value> >
 981 class _LIBCPP_TEMPLATE_VIS unordered_multiset
 982 {
 983 public:
 984     // types
 985     typedef _Value                                                     key_type;
 986     typedef key_type                                                   value_type;
 987     typedef _Hash                                                      hasher;
 988     typedef _Pred                                                      key_equal;
 989     typedef _Alloc                                                     allocator_type;
 990     typedef value_type&                                                reference;
 991     typedef const value_type&                                          const_reference;
 992     static_assert((is_same<value_type, typename allocator_type::value_type>::value),
 993                   "Invalid allocator::value_type");
 994     static_assert(sizeof(__diagnose_unordered_container_requirements<_Value, _Hash, _Pred>(0)), "");
 995
 996 private:
 997     typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
 998
 999     __table __table_;
1000
1001 public:
1002     typedef typename __table::pointer         pointer;
1003     typedef typename __table::const_pointer   const_pointer;
1004     typedef typename __table::size_type       size_type;
1005     typedef typename __table::difference_type difference_type;
1006
1007     typedef typename __table::const_iterator       iterator;
1008     typedef typename __table::const_iterator       const_iterator;
1009     typedef typename __table::const_local_iterator local_iterator;
1010     typedef typename __table::const_local_iterator const_local_iterator;
1011
1012 #if _LIBCPP_STD_VER > 14
1013     typedef __set_node_handle<typename __table::__node, allocator_type> node_type;
1014 #endif
1015
1016     template <class _Value2, class _Hash2, class _Pred2, class _Alloc2>
1017         friend class _LIBCPP_TEMPLATE_VIS unordered_set;
1018     template <class _Value2, class _Hash2, class _Pred2, class _Alloc2>
1019         friend class _LIBCPP_TEMPLATE_VIS unordered_multiset;
1020
1021     _LIBCPP_INLINE_VISIBILITY
1022     unordered_multiset()
1023         _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
1024         {
1025 #if _LIBCPP_DEBUG_LEVEL >= 2
1026             __get_db()->__insert_c(this);
1027 #endif
1028         }
1029     explicit unordered_multiset(size_type __n, const hasher& __hf = hasher(),
1030                                 const key_equal& __eql = key_equal());
1031     unordered_multiset(size_type __n, const hasher& __hf,
1032                        const key_equal& __eql, const allocator_type& __a);
1033 #if _LIBCPP_STD_VER > 11
1034     inline _LIBCPP_INLINE_VISIBILITY
1035     unordered_multiset(size_type __n, const allocator_type& __a)
1036         : unordered_multiset(__n, hasher(), key_equal(), __a) {}
1037     inline _LIBCPP_INLINE_VISIBILITY
1038     unordered_multiset(size_type __n, const hasher& __hf, const allocator_type& __a)
1039         : unordered_multiset(__n, __hf, key_equal(), __a) {}
1040 #endif
1041     template <class _InputIterator>
1042         unordered_multiset(_InputIterator __first, _InputIterator __last);
1043     template <class _InputIterator>
1044         unordered_multiset(_InputIterator __first, _InputIterator __last,
1045                       size_type __n, const hasher& __hf = hasher(),
1046                       const key_equal& __eql = key_equal());
1047     template <class _InputIterator>
1048         unordered_multiset(_InputIterator __first, _InputIterator __last,
1049                       size_type __n , const hasher& __hf,
1050                       const key_equal& __eql, const allocator_type& __a);
1051 #if _LIBCPP_STD_VER > 11
1052     template <class _InputIterator>
1053     inline _LIBCPP_INLINE_VISIBILITY
1054     unordered_multiset(_InputIterator __first, _InputIterator __last,
1055                        size_type __n, const allocator_type& __a)
1056         : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a) {}
1057     template <class _InputIterator>
1058     inline _LIBCPP_INLINE_VISIBILITY
1059     unordered_multiset(_InputIterator __first, _InputIterator __last,
1060                        size_type __n, const hasher& __hf, const allocator_type& __a)
1061         : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a) {}
1062 #endif
1063     _LIBCPP_INLINE_VISIBILITY
1064     explicit unordered_multiset(const allocator_type& __a);
1065     unordered_multiset(const unordered_multiset& __u);
1066     unordered_multiset(const unordered_multiset& __u, const allocator_type& __a);
1067 #ifndef _LIBCPP_CXX03_LANG
1068     _LIBCPP_INLINE_VISIBILITY
1069     unordered_multiset(unordered_multiset&& __u)
1070         _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
1071     unordered_multiset(unordered_multiset&& __u, const allocator_type& __a);
1072     unordered_multiset(initializer_list<value_type> __il);
1073     unordered_multiset(initializer_list<value_type> __il, size_type __n,
1074                        const hasher& __hf = hasher(),
1075                        const key_equal& __eql = key_equal());
1076     unordered_multiset(initializer_list<value_type> __il, size_type __n,
1077                        const hasher& __hf, const key_equal& __eql,
1078                        const allocator_type& __a);
1079 #if _LIBCPP_STD_VER > 11
1080     inline _LIBCPP_INLINE_VISIBILITY
1081     unordered_multiset(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)
1082       : unordered_multiset(__il, __n, hasher(), key_equal(), __a) {}
1083     inline _LIBCPP_INLINE_VISIBILITY
1084     unordered_multiset(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a)
1085       : unordered_multiset(__il, __n, __hf, key_equal(), __a) {}
1086 #endif
1087 #endif  // _LIBCPP_CXX03_LANG
1088     // ~unordered_multiset() = default;
1089     _LIBCPP_INLINE_VISIBILITY
1090     unordered_multiset& operator=(const unordered_multiset& __u)
1091     {
1092         __table_ = __u.__table_;
1093         return *this;
1094     }
1095 #ifndef _LIBCPP_CXX03_LANG
1096     _LIBCPP_INLINE_VISIBILITY
1097     unordered_multiset& operator=(unordered_multiset&& __u)
1098         _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
1099     unordered_multiset& operator=(initializer_list<value_type> __il);
1100 #endif  // _LIBCPP_CXX03_LANG
1101
1102     _LIBCPP_INLINE_VISIBILITY
1103     allocator_type get_allocator() const _NOEXCEPT
1104         {return allocator_type(__table_.__node_alloc());}
1105
1106     _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
1107     bool      empty() const _NOEXCEPT {return __table_.size() == 0;}
1108     _LIBCPP_INLINE_VISIBILITY
1109     size_type size() const _NOEXCEPT  {return __table_.size();}
1110     _LIBCPP_INLINE_VISIBILITY
1111     size_type max_size() const _NOEXCEPT {return __table_.max_size();}
1112
1113     _LIBCPP_INLINE_VISIBILITY
1114     iterator       begin() _NOEXCEPT        {return __table_.begin();}
1115     _LIBCPP_INLINE_VISIBILITY
1116     iterator       end() _NOEXCEPT          {return __table_.end();}
1117     _LIBCPP_INLINE_VISIBILITY
1118     const_iterator begin()  const _NOEXCEPT {return __table_.begin();}
1119     _LIBCPP_INLINE_VISIBILITY
1120     const_iterator end()    const _NOEXCEPT {return __table_.end();}
1121     _LIBCPP_INLINE_VISIBILITY
1122     const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
1123     _LIBCPP_INLINE_VISIBILITY
1124     const_iterator cend()   const _NOEXCEPT {return __table_.end();}
1125
1126 #ifndef _LIBCPP_CXX03_LANG
1127     template <class... _Args>
1128         _LIBCPP_INLINE_VISIBILITY
1129         iterator emplace(_Args&&... __args)
1130             {return __table_.__emplace_multi(_VSTD::forward<_Args>(__args)...);}
1131     template <class... _Args>
1132         _LIBCPP_INLINE_VISIBILITY
1133         iterator emplace_hint(const_iterator __p, _Args&&... __args)
1134             {return __table_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);}
1135
1136     _LIBCPP_INLINE_VISIBILITY
1137     iterator insert(value_type&& __x) {return __table_.__insert_multi(_VSTD::move(__x));}
1138     _LIBCPP_INLINE_VISIBILITY
1139     iterator insert(const_iterator __p, value_type&& __x)
1140         {return __table_.__insert_multi(__p, _VSTD::move(__x));}
1141     _LIBCPP_INLINE_VISIBILITY
1142     void insert(initializer_list<value_type> __il)
1143         {insert(__il.begin(), __il.end());}
1144 #endif  // _LIBCPP_CXX03_LANG
1145
1146     _LIBCPP_INLINE_VISIBILITY
1147     iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
1148
1149     _LIBCPP_INLINE_VISIBILITY
1150     iterator insert(const_iterator __p, const value_type& __x)
1151         {return __table_.__insert_multi(__p, __x);}
1152
1153     template <class _InputIterator>
1154         _LIBCPP_INLINE_VISIBILITY
1155         void insert(_InputIterator __first, _InputIterator __last);
1156
1157 #if _LIBCPP_STD_VER > 14
1158     _LIBCPP_INLINE_VISIBILITY
1159     iterator insert(node_type&& __nh)
1160     {
1161         _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
1162             "node_type with incompatible allocator passed to unordered_multiset::insert()");
1163         return __table_.template __node_handle_insert_multi<node_type>(
1164             _VSTD::move(__nh));
1165     }
1166     _LIBCPP_INLINE_VISIBILITY
1167     iterator insert(const_iterator __hint, node_type&& __nh)
1168     {
1169         _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
1170             "node_type with incompatible allocator passed to unordered_multiset::insert()");
1171         return __table_.template __node_handle_insert_multi<node_type>(
1172             __hint, _VSTD::move(__nh));
1173     }
1174     _LIBCPP_INLINE_VISIBILITY
1175     node_type extract(const_iterator __position)
1176     {
1177         return __table_.template __node_handle_extract<node_type>(
1178             __position);
1179     }
1180     _LIBCPP_INLINE_VISIBILITY
1181     node_type extract(key_type const& __key)
1182     {
1183         return __table_.template __node_handle_extract<node_type>(__key);
1184     }
1185
1186     template <class _H2, class _P2>
1187     _LIBCPP_INLINE_VISIBILITY
1188     void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>& __source)
1189     {
1190         _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1191                        "merging container with incompatible allocator");
1192         return __table_.__node_handle_merge_multi(__source.__table_);
1193     }
1194     template <class _H2, class _P2>
1195     _LIBCPP_INLINE_VISIBILITY
1196     void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>&& __source)
1197     {
1198         _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1199                        "merging container with incompatible allocator");
1200         return __table_.__node_handle_merge_multi(__source.__table_);
1201     }
1202     template <class _H2, class _P2>
1203     _LIBCPP_INLINE_VISIBILITY
1204     void merge(unordered_set<key_type, _H2, _P2, allocator_type>& __source)
1205     {
1206         _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1207                        "merging container with incompatible allocator");
1208         return __table_.__node_handle_merge_multi(__source.__table_);
1209     }
1210     template <class _H2, class _P2>
1211     _LIBCPP_INLINE_VISIBILITY
1212     void merge(unordered_set<key_type, _H2, _P2, allocator_type>&& __source)
1213     {
1214         _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1215                        "merging container with incompatible allocator");
1216         return __table_.__node_handle_merge_multi(__source.__table_);
1217     }
1218 #endif
1219
1220     _LIBCPP_INLINE_VISIBILITY
1221     iterator erase(const_iterator __p) {return __table_.erase(__p);}
1222     _LIBCPP_INLINE_VISIBILITY
1223     size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
1224     _LIBCPP_INLINE_VISIBILITY
1225     iterator erase(const_iterator __first, const_iterator __last)
1226         {return __table_.erase(__first, __last);}
1227     _LIBCPP_INLINE_VISIBILITY
1228     void clear() _NOEXCEPT {__table_.clear();}
1229
1230     _LIBCPP_INLINE_VISIBILITY
1231     void swap(unordered_multiset& __u)
1232         _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
1233         {__table_.swap(__u.__table_);}
1234
1235     _LIBCPP_INLINE_VISIBILITY
1236     hasher hash_function() const {return __table_.hash_function();}
1237     _LIBCPP_INLINE_VISIBILITY
1238     key_equal key_eq() const {return __table_.key_eq();}
1239
1240     _LIBCPP_INLINE_VISIBILITY
1241     iterator       find(const key_type& __k)       {return __table_.find(__k);}
1242     _LIBCPP_INLINE_VISIBILITY
1243     const_iterator find(const key_type& __k) const {return __table_.find(__k);}
1244     _LIBCPP_INLINE_VISIBILITY
1245     size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
1246     _LIBCPP_INLINE_VISIBILITY
1247     pair<iterator, iterator>             equal_range(const key_type& __k)
1248         {return __table_.__equal_range_multi(__k);}
1249     _LIBCPP_INLINE_VISIBILITY
1250     pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
1251         {return __table_.__equal_range_multi(__k);}
1252
1253     _LIBCPP_INLINE_VISIBILITY
1254     size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
1255     _LIBCPP_INLINE_VISIBILITY
1256     size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
1257
1258     _LIBCPP_INLINE_VISIBILITY
1259     size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);}
1260     _LIBCPP_INLINE_VISIBILITY
1261     size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
1262
1263     _LIBCPP_INLINE_VISIBILITY
1264     local_iterator       begin(size_type __n)        {return __table_.begin(__n);}
1265     _LIBCPP_INLINE_VISIBILITY
1266     local_iterator       end(size_type __n)          {return __table_.end(__n);}
1267     _LIBCPP_INLINE_VISIBILITY
1268     const_local_iterator begin(size_type __n) const  {return __table_.cbegin(__n);}
1269     _LIBCPP_INLINE_VISIBILITY
1270     const_local_iterator end(size_type __n) const    {return __table_.cend(__n);}
1271     _LIBCPP_INLINE_VISIBILITY
1272     const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
1273     _LIBCPP_INLINE_VISIBILITY
1274     const_local_iterator cend(size_type __n) const   {return __table_.cend(__n);}
1275
1276     _LIBCPP_INLINE_VISIBILITY
1277     float load_factor() const _NOEXCEPT {return __table_.load_factor();}
1278     _LIBCPP_INLINE_VISIBILITY
1279     float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
1280     _LIBCPP_INLINE_VISIBILITY
1281     void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
1282     _LIBCPP_INLINE_VISIBILITY
1283     void rehash(size_type __n) {__table_.rehash(__n);}
1284     _LIBCPP_INLINE_VISIBILITY
1285     void reserve(size_type __n) {__table_.reserve(__n);}
1286
1287 #if _LIBCPP_DEBUG_LEVEL >= 2
1288
1289     bool __dereferenceable(const const_iterator* __i) const
1290         {return __table_.__dereferenceable(__i);}
1291     bool __decrementable(const const_iterator* __i) const
1292         {return __table_.__decrementable(__i);}
1293     bool __addable(const const_iterator* __i, ptrdiff_t __n) const
1294         {return __table_.__addable(__i, __n);}
1295     bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
1296         {return __table_.__addable(__i, __n);}
1297
1298 #endif  // _LIBCPP_DEBUG_LEVEL >= 2
1299
1300 };
1301
1302 template <class _Value, class _Hash, class _Pred, class _Alloc>
1303 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1304         size_type __n, const hasher& __hf, const key_equal& __eql)
1305     : __table_(__hf, __eql)
1306 {
1307 #if _LIBCPP_DEBUG_LEVEL >= 2
1308     __get_db()->__insert_c(this);
1309 #endif
1310     __table_.rehash(__n);
1311 }
1312
1313 template <class _Value, class _Hash, class _Pred, class _Alloc>
1314 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1315         size_type __n, const hasher& __hf, const key_equal& __eql,
1316         const allocator_type& __a)
1317     : __table_(__hf, __eql, __a)
1318 {
1319 #if _LIBCPP_DEBUG_LEVEL >= 2
1320     __get_db()->__insert_c(this);
1321 #endif
1322     __table_.rehash(__n);
1323 }
1324
1325 template <class _Value, class _Hash, class _Pred, class _Alloc>
1326 template <class _InputIterator>
1327 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1328         _InputIterator __first, _InputIterator __last)
1329 {
1330 #if _LIBCPP_DEBUG_LEVEL >= 2
1331     __get_db()->__insert_c(this);
1332 #endif
1333     insert(__first, __last);
1334 }
1335
1336 template <class _Value, class _Hash, class _Pred, class _Alloc>
1337 template <class _InputIterator>
1338 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1339         _InputIterator __first, _InputIterator __last, size_type __n,
1340         const hasher& __hf, const key_equal& __eql)
1341     : __table_(__hf, __eql)
1342 {
1343 #if _LIBCPP_DEBUG_LEVEL >= 2
1344     __get_db()->__insert_c(this);
1345 #endif
1346     __table_.rehash(__n);
1347     insert(__first, __last);
1348 }
1349
1350 template <class _Value, class _Hash, class _Pred, class _Alloc>
1351 template <class _InputIterator>
1352 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1353         _InputIterator __first, _InputIterator __last, size_type __n,
1354         const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1355     : __table_(__hf, __eql, __a)
1356 {
1357 #if _LIBCPP_DEBUG_LEVEL >= 2
1358     __get_db()->__insert_c(this);
1359 #endif
1360     __table_.rehash(__n);
1361     insert(__first, __last);
1362 }
1363
1364 template <class _Value, class _Hash, class _Pred, class _Alloc>
1365 inline
1366 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1367         const allocator_type& __a)
1368     : __table_(__a)
1369 {
1370 #if _LIBCPP_DEBUG_LEVEL >= 2
1371     __get_db()->__insert_c(this);
1372 #endif
1373 }
1374
1375 template <class _Value, class _Hash, class _Pred, class _Alloc>
1376 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1377         const unordered_multiset& __u)
1378     : __table_(__u.__table_)
1379 {
1380 #if _LIBCPP_DEBUG_LEVEL >= 2
1381     __get_db()->__insert_c(this);
1382 #endif
1383     __table_.rehash(__u.bucket_count());
1384     insert(__u.begin(), __u.end());
1385 }
1386
1387 template <class _Value, class _Hash, class _Pred, class _Alloc>
1388 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1389         const unordered_multiset& __u, const allocator_type& __a)
1390     : __table_(__u.__table_, __a)
1391 {
1392 #if _LIBCPP_DEBUG_LEVEL >= 2
1393     __get_db()->__insert_c(this);
1394 #endif
1395     __table_.rehash(__u.bucket_count());
1396     insert(__u.begin(), __u.end());
1397 }
1398
1399 #ifndef _LIBCPP_CXX03_LANG
1400
1401 template <class _Value, class _Hash, class _Pred, class _Alloc>
1402 inline
1403 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1404         unordered_multiset&& __u)
1405     _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
1406     : __table_(_VSTD::move(__u.__table_))
1407 {
1408 #if _LIBCPP_DEBUG_LEVEL >= 2
1409     __get_db()->__insert_c(this);
1410     __get_db()->swap(this, &__u);
1411 #endif
1412 }
1413
1414 template <class _Value, class _Hash, class _Pred, class _Alloc>
1415 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1416         unordered_multiset&& __u, const allocator_type& __a)
1417     : __table_(_VSTD::move(__u.__table_), __a)
1418 {
1419 #if _LIBCPP_DEBUG_LEVEL >= 2
1420     __get_db()->__insert_c(this);
1421 #endif
1422     if (__a != __u.get_allocator())
1423     {
1424         iterator __i = __u.begin();
1425         while (__u.size() != 0)
1426             __table_.__insert_multi(_VSTD::move(__u.__table_.remove(__i++)->__value_));
1427     }
1428 #if _LIBCPP_DEBUG_LEVEL >= 2
1429     else
1430         __get_db()->swap(this, &__u);
1431 #endif
1432 }
1433
1434 template <class _Value, class _Hash, class _Pred, class _Alloc>
1435 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1436         initializer_list<value_type> __il)
1437 {
1438 #if _LIBCPP_DEBUG_LEVEL >= 2
1439     __get_db()->__insert_c(this);
1440 #endif
1441     insert(__il.begin(), __il.end());
1442 }
1443
1444 template <class _Value, class _Hash, class _Pred, class _Alloc>
1445 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1446         initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1447         const key_equal& __eql)
1448     : __table_(__hf, __eql)
1449 {
1450 #if _LIBCPP_DEBUG_LEVEL >= 2
1451     __get_db()->__insert_c(this);
1452 #endif
1453     __table_.rehash(__n);
1454     insert(__il.begin(), __il.end());
1455 }
1456
1457 template <class _Value, class _Hash, class _Pred, class _Alloc>
1458 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1459         initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1460         const key_equal& __eql, const allocator_type& __a)
1461     : __table_(__hf, __eql, __a)
1462 {
1463 #if _LIBCPP_DEBUG_LEVEL >= 2
1464     __get_db()->__insert_c(this);
1465 #endif
1466     __table_.rehash(__n);
1467     insert(__il.begin(), __il.end());
1468 }
1469
1470 template <class _Value, class _Hash, class _Pred, class _Alloc>
1471 inline
1472 unordered_multiset<_Value, _Hash, _Pred, _Alloc>&
1473 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(
1474         unordered_multiset&& __u)
1475     _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
1476 {
1477     __table_ = _VSTD::move(__u.__table_);
1478     return *this;
1479 }
1480
1481 template <class _Value, class _Hash, class _Pred, class _Alloc>
1482 inline
1483 unordered_multiset<_Value, _Hash, _Pred, _Alloc>&
1484 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(
1485         initializer_list<value_type> __il)
1486 {
1487     __table_.__assign_multi(__il.begin(), __il.end());
1488     return *this;
1489 }
1490
1491 #endif  // _LIBCPP_CXX03_LANG
1492
1493 template <class _Value, class _Hash, class _Pred, class _Alloc>
1494 template <class _InputIterator>
1495 inline
1496 void
1497 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
1498                                                          _InputIterator __last)
1499 {
1500     for (; __first != __last; ++__first)
1501         __table_.__insert_multi(*__first);
1502 }
1503
1504 template <class _Value, class _Hash, class _Pred, class _Alloc>
1505 inline _LIBCPP_INLINE_VISIBILITY
1506 void
1507 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1508      unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1509     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1510 {
1511     __x.swap(__y);
1512 }
1513
1514 #if _LIBCPP_STD_VER > 17
1515 template <class _Value, class _Hash, class _Pred, class _Alloc, class _Predicate>
1516 inline _LIBCPP_INLINE_VISIBILITY
1517 void erase_if(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __c, _Predicate __pred)
1518 { __libcpp_erase_if_container(__c, __pred); }
1519 #endif
1520
1521 template <class _Value, class _Hash, class _Pred, class _Alloc>
1522 bool
1523 operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1524            const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1525 {
1526     if (__x.size() != __y.size())
1527         return false;
1528     typedef typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator
1529                                                                  const_iterator;
1530     typedef pair<const_iterator, const_iterator> _EqRng;
1531     for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;)
1532     {
1533         _EqRng __xeq = __x.equal_range(*__i);
1534         _EqRng __yeq = __y.equal_range(*__i);
1535         if (_VSTD::distance(__xeq.first, __xeq.second) !=
1536             _VSTD::distance(__yeq.first, __yeq.second) ||
1537                   !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first))
1538             return false;
1539         __i = __xeq.second;
1540     }
1541     return true;
1542 }
1543
1544 template <class _Value, class _Hash, class _Pred, class _Alloc>
1545 inline _LIBCPP_INLINE_VISIBILITY
1546 bool
1547 operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1548            const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1549 {
1550     return !(__x == __y);
1551 }
1552
1553 _LIBCPP_END_NAMESPACE_STD
1554
1555 #endif  // _LIBCPP_UNORDERED_SET