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