libcxx/include/unordered_set

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