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 #include <__algorithm/is_permutation.h>
 535 #include <__assert>
 536 #include <__config>
 537 #include <__functional/hash.h>
 538 #include <__functional/is_transparent.h>
 539 #include <__functional/operations.h>
 540 #include <__hash_table>
 541 #include <__iterator/distance.h>
 542 #include <__iterator/erase_if_container.h>
 543 #include <__iterator/iterator_traits.h>
 544 #include <__iterator/ranges_iterator_traits.h>
 545 #include <__memory/addressof.h>
 546 #include <__memory/allocator.h>
 547 #include <__memory/allocator_traits.h>
 548 #include <__memory_resource/polymorphic_allocator.h>
 549 #include <__node_handle>
 550 #include <__ranges/concepts.h>
 551 #include <__ranges/container_compatible_range.h>
 552 #include <__ranges/from_range.h>
 553 #include <__type_traits/container_traits.h>
 554 #include <__type_traits/enable_if.h>
 555 #include <__type_traits/invoke.h>
 556 #include <__type_traits/is_allocator.h>
 557 #include <__type_traits/is_integral.h>
 558 #include <__type_traits/is_nothrow_assignable.h>
 559 #include <__type_traits/is_nothrow_constructible.h>
 560 #include <__type_traits/is_same.h>
 561 #include <__type_traits/is_swappable.h>
 562 #include <__type_traits/type_identity.h>
 563 #include <__utility/forward.h>
 564 #include <__utility/move.h>
 565 #include <__utility/pair.h>
 566 #include <version>
 567
 568 // standard-mandated includes
 569
 570 // [iterator.range]
 571 #include <__iterator/access.h>
 572 #include <__iterator/data.h>
 573 #include <__iterator/empty.h>
 574 #include <__iterator/reverse_access.h>
 575 #include <__iterator/size.h>
 576
 577 // [unord.set.syn]
 578 #include <compare>
 579 #include <initializer_list>
 580
 581 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 582 #  pragma GCC system_header
 583 #endif
 584
 585 _LIBCPP_PUSH_MACROS
 586 #include <__undef_macros>
 587
 588 _LIBCPP_BEGIN_NAMESPACE_STD
 589
 590 template <class _Value, class _Hash, class _Pred, class _Alloc>
 591 class unordered_multiset;
 592
 593 template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, class _Alloc = allocator<_Value> >
 594 class _LIBCPP_TEMPLATE_VIS unordered_set {
 595 public:
 596   // types
 597   typedef _Value key_type;
 598   typedef key_type value_type;
 599   typedef __type_identity_t<_Hash> hasher;
 600   typedef __type_identity_t<_Pred> key_equal;
 601   typedef __type_identity_t<_Alloc> allocator_type;
 602   typedef value_type& reference;
 603   typedef const value_type& const_reference;
 604   static_assert(__check_valid_allocator<allocator_type>::value, "");
 605   static_assert(is_same<value_type, typename allocator_type::value_type>::value,
 606                 "Allocator::value_type must be same type as value_type");
 607
 608 private:
 609   typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
 610
 611   __table __table_;
 612
 613 public:
 614   typedef typename __table::pointer pointer;
 615   typedef typename __table::const_pointer const_pointer;
 616   typedef typename __table::size_type size_type;
 617   typedef typename __table::difference_type difference_type;
 618
 619   typedef typename __table::const_iterator iterator;
 620   typedef typename __table::const_iterator const_iterator;
 621   typedef typename __table::const_local_iterator local_iterator;
 622   typedef typename __table::const_local_iterator const_local_iterator;
 623
 624 #if _LIBCPP_STD_VER >= 17
 625   typedef __set_node_handle<typename __table::__node, allocator_type> node_type;
 626   typedef __insert_return_type<iterator, node_type> insert_return_type;
 627 #endif
 628
 629   template <class _Value2, class _Hash2, class _Pred2, class _Alloc2>
 630   friend class _LIBCPP_TEMPLATE_VIS unordered_set;
 631   template <class _Value2, class _Hash2, class _Pred2, class _Alloc2>
 632   friend class _LIBCPP_TEMPLATE_VIS unordered_multiset;
 633
 634   _LIBCPP_HIDE_FROM_ABI unordered_set() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) {}
 635   explicit _LIBCPP_HIDE_FROM_ABI
 636   unordered_set(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
 637 #if _LIBCPP_STD_VER >= 14
 638   inline _LIBCPP_HIDE_FROM_ABI unordered_set(size_type __n, const allocator_type& __a)
 639       : unordered_set(__n, hasher(), key_equal(), __a) {}
 640   inline _LIBCPP_HIDE_FROM_ABI unordered_set(size_type __n, const hasher& __hf, const allocator_type& __a)
 641       : unordered_set(__n, __hf, key_equal(), __a) {}
 642 #endif
 643   _LIBCPP_HIDE_FROM_ABI
 644   unordered_set(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a);
 645   template <class _InputIterator>
 646   _LIBCPP_HIDE_FROM_ABI unordered_set(_InputIterator __first, _InputIterator __last);
 647   template <class _InputIterator>
 648   _LIBCPP_HIDE_FROM_ABI
 649   unordered_set(_InputIterator __first,
 650                 _InputIterator __last,
 651                 size_type __n,
 652                 const hasher& __hf     = hasher(),
 653                 const key_equal& __eql = key_equal());
 654   template <class _InputIterator>
 655   _LIBCPP_HIDE_FROM_ABI unordered_set(
 656       _InputIterator __first,
 657       _InputIterator __last,
 658       size_type __n,
 659       const hasher& __hf,
 660       const key_equal& __eql,
 661       const allocator_type& __a);
 662
 663 #if _LIBCPP_STD_VER >= 23
 664   template <_ContainerCompatibleRange<value_type> _Range>
 665   _LIBCPP_HIDE_FROM_ABI unordered_set(
 666       from_range_t,
 667       _Range&& __range,
 668       size_type __n             = /*implementation-defined*/ 0,
 669       const hasher& __hf        = hasher(),
 670       const key_equal& __eql    = key_equal(),
 671       const allocator_type& __a = allocator_type())
 672       : __table_(__hf, __eql, __a) {
 673     if (__n > 0) {
 674       __table_.__rehash_unique(__n);
 675     }
 676     insert_range(std::forward<_Range>(__range));
 677   }
 678 #endif
 679
 680 #if _LIBCPP_STD_VER >= 14
 681   template <class _InputIterator>
 682   inline _LIBCPP_HIDE_FROM_ABI
 683   unordered_set(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a)
 684       : unordered_set(__first, __last, __n, hasher(), key_equal(), __a) {}
 685   template <class _InputIterator>
 686   _LIBCPP_HIDE_FROM_ABI unordered_set(
 687       _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const allocator_type& __a)
 688       : unordered_set(__first, __last, __n, __hf, key_equal(), __a) {}
 689 #endif
 690
 691 #if _LIBCPP_STD_VER >= 23
 692   template <_ContainerCompatibleRange<value_type> _Range>
 693   _LIBCPP_HIDE_FROM_ABI unordered_set(from_range_t, _Range&& __range, size_type __n, const allocator_type& __a)
 694       : unordered_set(from_range, std::forward<_Range>(__range), __n, hasher(), key_equal(), __a) {}
 695
 696   template <_ContainerCompatibleRange<value_type> _Range>
 697   _LIBCPP_HIDE_FROM_ABI
 698   unordered_set(from_range_t, _Range&& __range, size_type __n, const hasher& __hf, const allocator_type& __a)
 699       : unordered_set(from_range, std::forward<_Range>(__range), __n, __hf, key_equal(), __a) {}
 700 #endif
 701
 702   _LIBCPP_HIDE_FROM_ABI explicit unordered_set(const allocator_type& __a);
 703   _LIBCPP_HIDE_FROM_ABI unordered_set(const unordered_set& __u);
 704   _LIBCPP_HIDE_FROM_ABI unordered_set(const unordered_set& __u, const allocator_type& __a);
 705 #ifndef _LIBCPP_CXX03_LANG
 706   _LIBCPP_HIDE_FROM_ABI unordered_set(unordered_set&& __u) _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
 707   _LIBCPP_HIDE_FROM_ABI unordered_set(unordered_set&& __u, const allocator_type& __a);
 708   _LIBCPP_HIDE_FROM_ABI unordered_set(initializer_list<value_type> __il);
 709   _LIBCPP_HIDE_FROM_ABI
 710   unordered_set(initializer_list<value_type> __il,
 711                 size_type __n,
 712                 const hasher& __hf     = hasher(),
 713                 const key_equal& __eql = key_equal());
 714   _LIBCPP_HIDE_FROM_ABI unordered_set(
 715       initializer_list<value_type> __il,
 716       size_type __n,
 717       const hasher& __hf,
 718       const key_equal& __eql,
 719       const allocator_type& __a);
 720 #  if _LIBCPP_STD_VER >= 14
 721   inline _LIBCPP_HIDE_FROM_ABI
 722   unordered_set(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)
 723       : unordered_set(__il, __n, hasher(), key_equal(), __a) {}
 724   inline _LIBCPP_HIDE_FROM_ABI
 725   unordered_set(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a)
 726       : unordered_set(__il, __n, __hf, key_equal(), __a) {}
 727 #  endif
 728 #endif // _LIBCPP_CXX03_LANG
 729   _LIBCPP_HIDE_FROM_ABI ~unordered_set() {
 730     static_assert(sizeof(std::__diagnose_unordered_container_requirements<_Value, _Hash, _Pred>(0)), "");
 731   }
 732
 733   _LIBCPP_HIDE_FROM_ABI unordered_set& operator=(const unordered_set& __u) {
 734     __table_ = __u.__table_;
 735     return *this;
 736   }
 737 #ifndef _LIBCPP_CXX03_LANG
 738   _LIBCPP_HIDE_FROM_ABI unordered_set& operator=(unordered_set&& __u)
 739       _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
 740   _LIBCPP_HIDE_FROM_ABI unordered_set& operator=(initializer_list<value_type> __il);
 741 #endif // _LIBCPP_CXX03_LANG
 742
 743   _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT {
 744     return allocator_type(__table_.__node_alloc());
 745   }
 746
 747   [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __table_.size() == 0; }
 748   _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __table_.size(); }
 749   _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __table_.max_size(); }
 750
 751   _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __table_.begin(); }
 752   _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __table_.end(); }
 753   _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __table_.begin(); }
 754   _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __table_.end(); }
 755   _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return __table_.begin(); }
 756   _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return __table_.end(); }
 757
 758 #ifndef _LIBCPP_CXX03_LANG
 759   template <class... _Args>
 760   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> emplace(_Args&&... __args) {
 761     return __table_.__emplace_unique(std::forward<_Args>(__args)...);
 762   }
 763   template <class... _Args>
 764   _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator, _Args&&... __args) {
 765     return __table_.__emplace_unique(std::forward<_Args>(__args)...).first;
 766   }
 767
 768   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(value_type&& __x) {
 769     return __table_.__insert_unique(std::move(__x));
 770   }
 771   _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, value_type&& __x) { return insert(std::move(__x)).first; }
 772
 773   _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); }
 774 #endif // _LIBCPP_CXX03_LANG
 775   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(const value_type& __x) { return __table_.__insert_unique(__x); }
 776
 777   _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, const value_type& __x) { return insert(__x).first; }
 778   template <class _InputIterator>
 779   _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last);
 780
 781 #if _LIBCPP_STD_VER >= 23
 782   template <_ContainerCompatibleRange<value_type> _Range>
 783   _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) {
 784     for (auto&& __element : __range) {
 785       __table_.__insert_unique(std::forward<decltype(__element)>(__element));
 786     }
 787   }
 788 #endif
 789
 790   _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __table_.erase(__p); }
 791   _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_unique(__k); }
 792   _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last) {
 793     return __table_.erase(__first, __last);
 794   }
 795   _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __table_.clear(); }
 796
 797 #if _LIBCPP_STD_VER >= 17
 798   _LIBCPP_HIDE_FROM_ABI insert_return_type insert(node_type&& __nh) {
 799     _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
 800                                         "node_type with incompatible allocator passed to unordered_set::insert()");
 801     return __table_.template __node_handle_insert_unique< node_type, insert_return_type>(std::move(__nh));
 802   }
 803   _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __h, node_type&& __nh) {
 804     _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
 805                                         "node_type with incompatible allocator passed to unordered_set::insert()");
 806     return __table_.template __node_handle_insert_unique<node_type>(__h, std::move(__nh));
 807   }
 808   _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) {
 809     return __table_.template __node_handle_extract<node_type>(__key);
 810   }
 811   _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __it) {
 812     return __table_.template __node_handle_extract<node_type>(__it);
 813   }
 814
 815   template <class _H2, class _P2>
 816   _LIBCPP_HIDE_FROM_ABI void merge(unordered_set<key_type, _H2, _P2, allocator_type>& __source) {
 817     _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
 818         __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
 819     __table_.__node_handle_merge_unique(__source.__table_);
 820   }
 821   template <class _H2, class _P2>
 822   _LIBCPP_HIDE_FROM_ABI void merge(unordered_set<key_type, _H2, _P2, allocator_type>&& __source) {
 823     _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
 824         __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
 825     __table_.__node_handle_merge_unique(__source.__table_);
 826   }
 827   template <class _H2, class _P2>
 828   _LIBCPP_HIDE_FROM_ABI void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>& __source) {
 829     _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
 830         __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
 831     __table_.__node_handle_merge_unique(__source.__table_);
 832   }
 833   template <class _H2, class _P2>
 834   _LIBCPP_HIDE_FROM_ABI void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>&& __source) {
 835     _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
 836         __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
 837     __table_.__node_handle_merge_unique(__source.__table_);
 838   }
 839 #endif
 840
 841   _LIBCPP_HIDE_FROM_ABI void swap(unordered_set& __u) _NOEXCEPT_(__is_nothrow_swappable_v<__table>) {
 842     __table_.swap(__u.__table_);
 843   }
 844
 845   _LIBCPP_HIDE_FROM_ABI hasher hash_function() const { return __table_.hash_function(); }
 846   _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq(); }
 847
 848   _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); }
 849   _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); }
 850 #if _LIBCPP_STD_VER >= 20
 851   template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
 852   _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) {
 853     return __table_.find(__k);
 854   }
 855   template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
 856   _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const {
 857     return __table_.find(__k);
 858   }
 859 #endif // _LIBCPP_STD_VER >= 20
 860
 861   _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_unique(__k); }
 862 #if _LIBCPP_STD_VER >= 20
 863   template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
 864   _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const {
 865     return __table_.__count_unique(__k);
 866   }
 867 #endif // _LIBCPP_STD_VER >= 20
 868
 869 #if _LIBCPP_STD_VER >= 20
 870   _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); }
 871
 872   template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
 873   _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const {
 874     return find(__k) != end();
 875   }
 876 #endif // _LIBCPP_STD_VER >= 20
 877
 878   _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {
 879     return __table_.__equal_range_unique(__k);
 880   }
 881   _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
 882     return __table_.__equal_range_unique(__k);
 883   }
 884 #if _LIBCPP_STD_VER >= 20
 885   template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
 886   _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) {
 887     return __table_.__equal_range_unique(__k);
 888   }
 889   template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
 890   _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const {
 891     return __table_.__equal_range_unique(__k);
 892   }
 893 #endif // _LIBCPP_STD_VER >= 20
 894
 895   _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const _NOEXCEPT { return __table_.bucket_count(); }
 896   _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const _NOEXCEPT { return __table_.max_bucket_count(); }
 897
 898   _LIBCPP_HIDE_FROM_ABI size_type bucket_size(size_type __n) const { return __table_.bucket_size(__n); }
 899   _LIBCPP_HIDE_FROM_ABI size_type bucket(const key_type& __k) const { return __table_.bucket(__k); }
 900
 901   _LIBCPP_HIDE_FROM_ABI local_iterator begin(size_type __n) { return __table_.begin(__n); }
 902   _LIBCPP_HIDE_FROM_ABI local_iterator end(size_type __n) { return __table_.end(__n); }
 903   _LIBCPP_HIDE_FROM_ABI const_local_iterator begin(size_type __n) const { return __table_.cbegin(__n); }
 904   _LIBCPP_HIDE_FROM_ABI const_local_iterator end(size_type __n) const { return __table_.cend(__n); }
 905   _LIBCPP_HIDE_FROM_ABI const_local_iterator cbegin(size_type __n) const { return __table_.cbegin(__n); }
 906   _LIBCPP_HIDE_FROM_ABI const_local_iterator cend(size_type __n) const { return __table_.cend(__n); }
 907
 908   _LIBCPP_HIDE_FROM_ABI float load_factor() const _NOEXCEPT { return __table_.load_factor(); }
 909   _LIBCPP_HIDE_FROM_ABI float max_load_factor() const _NOEXCEPT { return __table_.max_load_factor(); }
 910   _LIBCPP_HIDE_FROM_ABI void max_load_factor(float __mlf) { __table_.max_load_factor(__mlf); }
 911   _LIBCPP_HIDE_FROM_ABI void rehash(size_type __n) { __table_.__rehash_unique(__n); }
 912   _LIBCPP_HIDE_FROM_ABI void reserve(size_type __n) { __table_.__reserve_unique(__n); }
 913 };
 914
 915 #if _LIBCPP_STD_VER >= 17
 916 template <class _InputIterator,
 917           class _Hash      = hash<__iter_value_type<_InputIterator>>,
 918           class _Pred      = equal_to<__iter_value_type<_InputIterator>>,
 919           class _Allocator = allocator<__iter_value_type<_InputIterator>>,
 920           class            = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
 921           class            = enable_if_t<!__is_allocator<_Hash>::value>,
 922           class            = enable_if_t<!is_integral<_Hash>::value>,
 923           class            = enable_if_t<!__is_allocator<_Pred>::value>,
 924           class            = enable_if_t<__is_allocator<_Allocator>::value>>
 925 unordered_set(_InputIterator,
 926               _InputIterator,
 927               typename allocator_traits<_Allocator>::size_type = 0,
 928               _Hash                                            = _Hash(),
 929               _Pred                                            = _Pred(),
 930               _Allocator = _Allocator()) -> unordered_set<__iter_value_type<_InputIterator>, _Hash, _Pred, _Allocator>;
 931
 932 #  if _LIBCPP_STD_VER >= 23
 933 template <ranges::input_range _Range,
 934           class _Hash      = hash<ranges::range_value_t<_Range>>,
 935           class _Pred      = equal_to<ranges::range_value_t<_Range>>,
 936           class _Allocator = allocator<ranges::range_value_t<_Range>>,
 937           class            = enable_if_t<!__is_allocator<_Hash>::value>,
 938           class            = enable_if_t<!is_integral<_Hash>::value>,
 939           class            = enable_if_t<!__is_allocator<_Pred>::value>,
 940           class            = enable_if_t<__is_allocator<_Allocator>::value>>
 941 unordered_set(
 942     from_range_t,
 943     _Range&&,
 944     typename allocator_traits<_Allocator>::size_type = 0,
 945     _Hash                                            = _Hash(),
 946     _Pred                                            = _Pred(),
 947     _Allocator = _Allocator()) -> unordered_set<ranges::range_value_t<_Range>, _Hash, _Pred, _Allocator>; // C++23
 948 #  endif
 949
 950 template <class _Tp,
 951           class _Hash      = hash<_Tp>,
 952           class _Pred      = equal_to<_Tp>,
 953           class _Allocator = allocator<_Tp>,
 954           class            = enable_if_t<!__is_allocator<_Hash>::value>,
 955           class            = enable_if_t<!is_integral<_Hash>::value>,
 956           class            = enable_if_t<!__is_allocator<_Pred>::value>,
 957           class            = enable_if_t<__is_allocator<_Allocator>::value>>
 958 unordered_set(initializer_list<_Tp>,
 959               typename allocator_traits<_Allocator>::size_type = 0,
 960               _Hash                                            = _Hash(),
 961               _Pred                                            = _Pred(),
 962               _Allocator = _Allocator()) -> unordered_set<_Tp, _Hash, _Pred, _Allocator>;
 963
 964 template <class _InputIterator,
 965           class _Allocator,
 966           class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
 967           class = enable_if_t<__is_allocator<_Allocator>::value>>
 968 unordered_set(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Allocator)
 969     -> unordered_set<__iter_value_type<_InputIterator>,
 970                      hash<__iter_value_type<_InputIterator>>,
 971                      equal_to<__iter_value_type<_InputIterator>>,
 972                      _Allocator>;
 973
 974 template <class _InputIterator,
 975           class _Hash,
 976           class _Allocator,
 977           class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
 978           class = enable_if_t<!__is_allocator<_Hash>::value>,
 979           class = enable_if_t<!is_integral<_Hash>::value>,
 980           class = enable_if_t<__is_allocator<_Allocator>::value>>
 981 unordered_set(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
 982     -> unordered_set<__iter_value_type<_InputIterator>, _Hash, equal_to<__iter_value_type<_InputIterator>>, _Allocator>;
 983
 984 #  if _LIBCPP_STD_VER >= 23
 985
 986 template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
 987 unordered_set(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Allocator)
 988     -> unordered_set<ranges::range_value_t<_Range>,
 989                      hash<ranges::range_value_t<_Range>>,
 990                      equal_to<ranges::range_value_t<_Range>>,
 991                      _Allocator>;
 992
 993 template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
 994 unordered_set(from_range_t, _Range&&, _Allocator)
 995     -> unordered_set<ranges::range_value_t<_Range>,
 996                      hash<ranges::range_value_t<_Range>>,
 997                      equal_to<ranges::range_value_t<_Range>>,
 998                      _Allocator>;
 999
1000 template <ranges::input_range _Range,
1001           class _Hash,
1002           class _Allocator,
1003           class = enable_if_t<!__is_allocator<_Hash>::value>,
1004           class = enable_if_t<!is_integral<_Hash>::value>,
1005           class = enable_if_t<__is_allocator<_Allocator>::value>>
1006 unordered_set(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
1007     -> unordered_set<ranges::range_value_t<_Range>, _Hash, equal_to<ranges::range_value_t<_Range>>, _Allocator>;
1008
1009 #  endif
1010
1011 template <class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
1012 unordered_set(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Allocator)
1013     -> unordered_set<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
1014
1015 template <class _Tp,
1016           class _Hash,
1017           class _Allocator,
1018           class = enable_if_t<!__is_allocator<_Hash>::value>,
1019           class = enable_if_t<!is_integral<_Hash>::value>,
1020           class = enable_if_t<__is_allocator<_Allocator>::value>>
1021 unordered_set(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
1022     -> unordered_set<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
1023 #endif
1024
1025 template <class _Value, class _Hash, class _Pred, class _Alloc>
1026 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n, const hasher& __hf, const key_equal& __eql)
1027     : __table_(__hf, __eql) {
1028   __table_.__rehash_unique(__n);
1029 }
1030
1031 template <class _Value, class _Hash, class _Pred, class _Alloc>
1032 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
1033     size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1034     : __table_(__hf, __eql, __a) {
1035   __table_.__rehash_unique(__n);
1036 }
1037
1038 template <class _Value, class _Hash, class _Pred, class _Alloc>
1039 template <class _InputIterator>
1040 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(_InputIterator __first, _InputIterator __last) {
1041   insert(__first, __last);
1042 }
1043
1044 template <class _Value, class _Hash, class _Pred, class _Alloc>
1045 template <class _InputIterator>
1046 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
1047     _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql)
1048     : __table_(__hf, __eql) {
1049   __table_.__rehash_unique(__n);
1050   insert(__first, __last);
1051 }
1052
1053 template <class _Value, class _Hash, class _Pred, class _Alloc>
1054 template <class _InputIterator>
1055 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
1056     _InputIterator __first,
1057     _InputIterator __last,
1058     size_type __n,
1059     const hasher& __hf,
1060     const key_equal& __eql,
1061     const allocator_type& __a)
1062     : __table_(__hf, __eql, __a) {
1063   __table_.__rehash_unique(__n);
1064   insert(__first, __last);
1065 }
1066
1067 template <class _Value, class _Hash, class _Pred, class _Alloc>
1068 inline unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(const allocator_type& __a) : __table_(__a) {}
1069
1070 template <class _Value, class _Hash, class _Pred, class _Alloc>
1071 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(const unordered_set& __u) : __table_(__u.__table_) {
1072   __table_.__rehash_unique(__u.bucket_count());
1073   insert(__u.begin(), __u.end());
1074 }
1075
1076 template <class _Value, class _Hash, class _Pred, class _Alloc>
1077 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(const unordered_set& __u, const allocator_type& __a)
1078     : __table_(__u.__table_, __a) {
1079   __table_.__rehash_unique(__u.bucket_count());
1080   insert(__u.begin(), __u.end());
1081 }
1082
1083 #ifndef _LIBCPP_CXX03_LANG
1084
1085 template <class _Value, class _Hash, class _Pred, class _Alloc>
1086 inline unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(unordered_set&& __u)
1087     _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
1088     : __table_(std::move(__u.__table_)) {}
1089
1090 template <class _Value, class _Hash, class _Pred, class _Alloc>
1091 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(unordered_set&& __u, const allocator_type& __a)
1092     : __table_(std::move(__u.__table_), __a) {
1093   if (__a != __u.get_allocator()) {
1094     iterator __i = __u.begin();
1095     while (__u.size() != 0)
1096       __table_.__insert_unique(std::move(__u.__table_.remove(__i++)->__get_value()));
1097   }
1098 }
1099
1100 template <class _Value, class _Hash, class _Pred, class _Alloc>
1101 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(initializer_list<value_type> __il) {
1102   insert(__il.begin(), __il.end());
1103 }
1104
1105 template <class _Value, class _Hash, class _Pred, class _Alloc>
1106 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
1107     initializer_list<value_type> __il, size_type __n, const hasher& __hf, const key_equal& __eql)
1108     : __table_(__hf, __eql) {
1109   __table_.__rehash_unique(__n);
1110   insert(__il.begin(), __il.end());
1111 }
1112
1113 template <class _Value, class _Hash, class _Pred, class _Alloc>
1114 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
1115     initializer_list<value_type> __il,
1116     size_type __n,
1117     const hasher& __hf,
1118     const key_equal& __eql,
1119     const allocator_type& __a)
1120     : __table_(__hf, __eql, __a) {
1121   __table_.__rehash_unique(__n);
1122   insert(__il.begin(), __il.end());
1123 }
1124
1125 template <class _Value, class _Hash, class _Pred, class _Alloc>
1126 inline unordered_set<_Value, _Hash, _Pred, _Alloc>&
1127 unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(unordered_set&& __u)
1128     _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) {
1129   __table_ = std::move(__u.__table_);
1130   return *this;
1131 }
1132
1133 template <class _Value, class _Hash, class _Pred, class _Alloc>
1134 inline unordered_set<_Value, _Hash, _Pred, _Alloc>&
1135 unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(initializer_list<value_type> __il) {
1136   __table_.__assign_unique(__il.begin(), __il.end());
1137   return *this;
1138 }
1139
1140 #endif // _LIBCPP_CXX03_LANG
1141
1142 template <class _Value, class _Hash, class _Pred, class _Alloc>
1143 template <class _InputIterator>
1144 inline void unordered_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) {
1145   for (; __first != __last; ++__first)
1146     __table_.__insert_unique(*__first);
1147 }
1148
1149 template <class _Value, class _Hash, class _Pred, class _Alloc>
1150 inline _LIBCPP_HIDE_FROM_ABI void
1151 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
1152     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
1153   __x.swap(__y);
1154 }
1155
1156 #if _LIBCPP_STD_VER >= 20
1157 template <class _Value, class _Hash, class _Pred, class _Alloc, class _Predicate>
1158 inline _LIBCPP_HIDE_FROM_ABI typename unordered_set<_Value, _Hash, _Pred, _Alloc>::size_type
1159 erase_if(unordered_set<_Value, _Hash, _Pred, _Alloc>& __c, _Predicate __pred) {
1160   return std::__libcpp_erase_if_container(__c, __pred);
1161 }
1162 #endif
1163
1164 template <class _Value, class _Hash, class _Pred, class _Alloc>
1165 _LIBCPP_HIDE_FROM_ABI bool operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
1166                                       const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) {
1167   if (__x.size() != __y.size())
1168     return false;
1169   typedef typename unordered_set<_Value, _Hash, _Pred, _Alloc>::const_iterator const_iterator;
1170   for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); __i != __ex; ++__i) {
1171     const_iterator __j = __y.find(*__i);
1172     if (__j == __ey || !(*__i == *__j))
1173       return false;
1174   }
1175   return true;
1176 }
1177
1178 #if _LIBCPP_STD_VER <= 17
1179
1180 template <class _Value, class _Hash, class _Pred, class _Alloc>
1181 inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
1182                                              const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) {
1183   return !(__x == __y);
1184 }
1185
1186 #endif
1187
1188 template <class _Value, class _Hash, class _Pred, class _Alloc>
1189 struct __container_traits<unordered_set<_Value, _Hash, _Pred, _Alloc> > {
1190   // http://eel.is/c++draft/unord.req.except#2
1191   //  For unordered associative containers, if an exception is thrown by any operation
1192   //  other than the container's hash function from within an insert or emplace function
1193   //  inserting a single element, the insertion has no effect.
1194   static _LIBCPP_CONSTEXPR const bool __emplacement_has_strong_exception_safety_guarantee =
1195       __nothrow_invokable<_Hash, const _Value&>::value;
1196 };
1197
1198 template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, class _Alloc = allocator<_Value> >
1199 class _LIBCPP_TEMPLATE_VIS unordered_multiset {
1200 public:
1201   // types
1202   typedef _Value key_type;
1203   typedef key_type value_type;
1204   typedef __type_identity_t<_Hash> hasher;
1205   typedef __type_identity_t<_Pred> key_equal;
1206   typedef __type_identity_t<_Alloc> allocator_type;
1207   typedef value_type& reference;
1208   typedef const value_type& const_reference;
1209   static_assert(is_same<value_type, typename allocator_type::value_type>::value,
1210                 "Allocator::value_type must be same type as value_type");
1211
1212 private:
1213   typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
1214
1215   __table __table_;
1216
1217 public:
1218   typedef typename __table::pointer pointer;
1219   typedef typename __table::const_pointer const_pointer;
1220   typedef typename __table::size_type size_type;
1221   typedef typename __table::difference_type difference_type;
1222
1223   typedef typename __table::const_iterator iterator;
1224   typedef typename __table::const_iterator const_iterator;
1225   typedef typename __table::const_local_iterator local_iterator;
1226   typedef typename __table::const_local_iterator const_local_iterator;
1227
1228 #if _LIBCPP_STD_VER >= 17
1229   typedef __set_node_handle<typename __table::__node, allocator_type> node_type;
1230 #endif
1231
1232   template <class _Value2, class _Hash2, class _Pred2, class _Alloc2>
1233   friend class _LIBCPP_TEMPLATE_VIS unordered_set;
1234   template <class _Value2, class _Hash2, class _Pred2, class _Alloc2>
1235   friend class _LIBCPP_TEMPLATE_VIS unordered_multiset;
1236
1237   _LIBCPP_HIDE_FROM_ABI unordered_multiset() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) {}
1238   explicit _LIBCPP_HIDE_FROM_ABI
1239   unordered_multiset(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
1240   _LIBCPP_HIDE_FROM_ABI
1241   unordered_multiset(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a);
1242 #if _LIBCPP_STD_VER >= 14
1243   inline _LIBCPP_HIDE_FROM_ABI unordered_multiset(size_type __n, const allocator_type& __a)
1244       : unordered_multiset(__n, hasher(), key_equal(), __a) {}
1245   inline _LIBCPP_HIDE_FROM_ABI unordered_multiset(size_type __n, const hasher& __hf, const allocator_type& __a)
1246       : unordered_multiset(__n, __hf, key_equal(), __a) {}
1247 #endif
1248   template <class _InputIterator>
1249   _LIBCPP_HIDE_FROM_ABI unordered_multiset(_InputIterator __first, _InputIterator __last);
1250   template <class _InputIterator>
1251   _LIBCPP_HIDE_FROM_ABI unordered_multiset(
1252       _InputIterator __first,
1253       _InputIterator __last,
1254       size_type __n,
1255       const hasher& __hf     = hasher(),
1256       const key_equal& __eql = key_equal());
1257   template <class _InputIterator>
1258   _LIBCPP_HIDE_FROM_ABI unordered_multiset(
1259       _InputIterator __first,
1260       _InputIterator __last,
1261       size_type __n,
1262       const hasher& __hf,
1263       const key_equal& __eql,
1264       const allocator_type& __a);
1265
1266 #if _LIBCPP_STD_VER >= 23
1267   template <_ContainerCompatibleRange<value_type> _Range>
1268   _LIBCPP_HIDE_FROM_ABI unordered_multiset(
1269       from_range_t,
1270       _Range&& __range,
1271       size_type __n             = /*implementation-defined*/ 0,
1272       const hasher& __hf        = hasher(),
1273       const key_equal& __eql    = key_equal(),
1274       const allocator_type& __a = allocator_type())
1275       : __table_(__hf, __eql, __a) {
1276     if (__n > 0) {
1277       __table_.__rehash_multi(__n);
1278     }
1279     insert_range(std::forward<_Range>(__range));
1280   }
1281 #endif
1282
1283 #if _LIBCPP_STD_VER >= 14
1284   template <class _InputIterator>
1285   inline _LIBCPP_HIDE_FROM_ABI
1286   unordered_multiset(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a)
1287       : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a) {}
1288   template <class _InputIterator>
1289   inline _LIBCPP_HIDE_FROM_ABI unordered_multiset(
1290       _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const allocator_type& __a)
1291       : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a) {}
1292 #endif
1293
1294 #if _LIBCPP_STD_VER >= 23
1295   template <_ContainerCompatibleRange<value_type> _Range>
1296   _LIBCPP_HIDE_FROM_ABI unordered_multiset(from_range_t, _Range&& __range, size_type __n, const allocator_type& __a)
1297       : unordered_multiset(from_range, std::forward<_Range>(__range), __n, hasher(), key_equal(), __a) {}
1298
1299   template <_ContainerCompatibleRange<value_type> _Range>
1300   _LIBCPP_HIDE_FROM_ABI
1301   unordered_multiset(from_range_t, _Range&& __range, size_type __n, const hasher& __hf, const allocator_type& __a)
1302       : unordered_multiset(from_range, std::forward<_Range>(__range), __n, __hf, key_equal(), __a) {}
1303 #endif
1304
1305   _LIBCPP_HIDE_FROM_ABI explicit unordered_multiset(const allocator_type& __a);
1306   _LIBCPP_HIDE_FROM_ABI unordered_multiset(const unordered_multiset& __u);
1307   _LIBCPP_HIDE_FROM_ABI unordered_multiset(const unordered_multiset& __u, const allocator_type& __a);
1308 #ifndef _LIBCPP_CXX03_LANG
1309   _LIBCPP_HIDE_FROM_ABI unordered_multiset(unordered_multiset&& __u)
1310       _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
1311   _LIBCPP_HIDE_FROM_ABI unordered_multiset(unordered_multiset&& __u, const allocator_type& __a);
1312   _LIBCPP_HIDE_FROM_ABI unordered_multiset(initializer_list<value_type> __il);
1313   _LIBCPP_HIDE_FROM_ABI unordered_multiset(
1314       initializer_list<value_type> __il,
1315       size_type __n,
1316       const hasher& __hf     = hasher(),
1317       const key_equal& __eql = key_equal());
1318   _LIBCPP_HIDE_FROM_ABI unordered_multiset(
1319       initializer_list<value_type> __il,
1320       size_type __n,
1321       const hasher& __hf,
1322       const key_equal& __eql,
1323       const allocator_type& __a);
1324 #  if _LIBCPP_STD_VER >= 14
1325   inline _LIBCPP_HIDE_FROM_ABI
1326   unordered_multiset(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)
1327       : unordered_multiset(__il, __n, hasher(), key_equal(), __a) {}
1328   inline _LIBCPP_HIDE_FROM_ABI
1329   unordered_multiset(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a)
1330       : unordered_multiset(__il, __n, __hf, key_equal(), __a) {}
1331 #  endif
1332 #endif // _LIBCPP_CXX03_LANG
1333   _LIBCPP_HIDE_FROM_ABI ~unordered_multiset() {
1334     static_assert(sizeof(std::__diagnose_unordered_container_requirements<_Value, _Hash, _Pred>(0)), "");
1335   }
1336
1337   _LIBCPP_HIDE_FROM_ABI unordered_multiset& operator=(const unordered_multiset& __u) {
1338     __table_ = __u.__table_;
1339     return *this;
1340   }
1341 #ifndef _LIBCPP_CXX03_LANG
1342   _LIBCPP_HIDE_FROM_ABI unordered_multiset& operator=(unordered_multiset&& __u)
1343       _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
1344   _LIBCPP_HIDE_FROM_ABI unordered_multiset& operator=(initializer_list<value_type> __il);
1345 #endif // _LIBCPP_CXX03_LANG
1346
1347   _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT {
1348     return allocator_type(__table_.__node_alloc());
1349   }
1350
1351   [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __table_.size() == 0; }
1352   _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __table_.size(); }
1353   _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __table_.max_size(); }
1354
1355   _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __table_.begin(); }
1356   _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __table_.end(); }
1357   _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __table_.begin(); }
1358   _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __table_.end(); }
1359   _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return __table_.begin(); }
1360   _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return __table_.end(); }
1361
1362 #ifndef _LIBCPP_CXX03_LANG
1363   template <class... _Args>
1364   _LIBCPP_HIDE_FROM_ABI iterator emplace(_Args&&... __args) {
1365     return __table_.__emplace_multi(std::forward<_Args>(__args)...);
1366   }
1367   template <class... _Args>
1368   _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __p, _Args&&... __args) {
1369     return __table_.__emplace_hint_multi(__p, std::forward<_Args>(__args)...);
1370   }
1371
1372   _LIBCPP_HIDE_FROM_ABI iterator insert(value_type&& __x) { return __table_.__insert_multi(std::move(__x)); }
1373   _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __x) {
1374     return __table_.__insert_multi(__p, std::move(__x));
1375   }
1376   _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); }
1377 #endif // _LIBCPP_CXX03_LANG
1378
1379   _LIBCPP_HIDE_FROM_ABI iterator insert(const value_type& __x) { return __table_.__insert_multi(__x); }
1380
1381   _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __x) {
1382     return __table_.__insert_multi(__p, __x);
1383   }
1384
1385   template <class _InputIterator>
1386   _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last);
1387
1388 #if _LIBCPP_STD_VER >= 23
1389   template <_ContainerCompatibleRange<value_type> _Range>
1390   _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) {
1391     for (auto&& __element : __range) {
1392       __table_.__insert_multi(std::forward<decltype(__element)>(__element));
1393     }
1394   }
1395 #endif
1396
1397 #if _LIBCPP_STD_VER >= 17
1398   _LIBCPP_HIDE_FROM_ABI iterator insert(node_type&& __nh) {
1399     _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
1400                                         "node_type with incompatible allocator passed to unordered_multiset::insert()");
1401     return __table_.template __node_handle_insert_multi<node_type>(std::move(__nh));
1402   }
1403   _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, node_type&& __nh) {
1404     _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
1405                                         "node_type with incompatible allocator passed to unordered_multiset::insert()");
1406     return __table_.template __node_handle_insert_multi<node_type>(__hint, std::move(__nh));
1407   }
1408   _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __position) {
1409     return __table_.template __node_handle_extract<node_type>(__position);
1410   }
1411   _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) {
1412     return __table_.template __node_handle_extract<node_type>(__key);
1413   }
1414
1415   template <class _H2, class _P2>
1416   _LIBCPP_HIDE_FROM_ABI void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>& __source) {
1417     _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1418         __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1419     return __table_.__node_handle_merge_multi(__source.__table_);
1420   }
1421   template <class _H2, class _P2>
1422   _LIBCPP_HIDE_FROM_ABI void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>&& __source) {
1423     _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1424         __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1425     return __table_.__node_handle_merge_multi(__source.__table_);
1426   }
1427   template <class _H2, class _P2>
1428   _LIBCPP_HIDE_FROM_ABI void merge(unordered_set<key_type, _H2, _P2, allocator_type>& __source) {
1429     _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1430         __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1431     return __table_.__node_handle_merge_multi(__source.__table_);
1432   }
1433   template <class _H2, class _P2>
1434   _LIBCPP_HIDE_FROM_ABI void merge(unordered_set<key_type, _H2, _P2, allocator_type>&& __source) {
1435     _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1436         __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1437     return __table_.__node_handle_merge_multi(__source.__table_);
1438   }
1439 #endif
1440
1441   _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __table_.erase(__p); }
1442   _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_multi(__k); }
1443   _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last) {
1444     return __table_.erase(__first, __last);
1445   }
1446   _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __table_.clear(); }
1447
1448   _LIBCPP_HIDE_FROM_ABI void swap(unordered_multiset& __u) _NOEXCEPT_(__is_nothrow_swappable_v<__table>) {
1449     __table_.swap(__u.__table_);
1450   }
1451
1452   _LIBCPP_HIDE_FROM_ABI hasher hash_function() const { return __table_.hash_function(); }
1453   _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq(); }
1454
1455   _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); }
1456   _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); }
1457 #if _LIBCPP_STD_VER >= 20
1458   template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
1459   _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) {
1460     return __table_.find(__k);
1461   }
1462   template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
1463   _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const {
1464     return __table_.find(__k);
1465   }
1466 #endif // _LIBCPP_STD_VER >= 20
1467
1468   _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_multi(__k); }
1469 #if _LIBCPP_STD_VER >= 20
1470   template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
1471   _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const {
1472     return __table_.__count_multi(__k);
1473   }
1474 #endif // _LIBCPP_STD_VER >= 20
1475
1476 #if _LIBCPP_STD_VER >= 20
1477   _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); }
1478
1479   template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
1480   _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const {
1481     return find(__k) != end();
1482   }
1483 #endif // _LIBCPP_STD_VER >= 20
1484
1485   _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {
1486     return __table_.__equal_range_multi(__k);
1487   }
1488   _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
1489     return __table_.__equal_range_multi(__k);
1490   }
1491 #if _LIBCPP_STD_VER >= 20
1492   template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
1493   _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) {
1494     return __table_.__equal_range_multi(__k);
1495   }
1496   template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
1497   _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const {
1498     return __table_.__equal_range_multi(__k);
1499   }
1500 #endif // _LIBCPP_STD_VER >= 20
1501
1502   _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const _NOEXCEPT { return __table_.bucket_count(); }
1503   _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const _NOEXCEPT { return __table_.max_bucket_count(); }
1504
1505   _LIBCPP_HIDE_FROM_ABI size_type bucket_size(size_type __n) const { return __table_.bucket_size(__n); }
1506   _LIBCPP_HIDE_FROM_ABI size_type bucket(const key_type& __k) const { return __table_.bucket(__k); }
1507
1508   _LIBCPP_HIDE_FROM_ABI local_iterator begin(size_type __n) { return __table_.begin(__n); }
1509   _LIBCPP_HIDE_FROM_ABI local_iterator end(size_type __n) { return __table_.end(__n); }
1510   _LIBCPP_HIDE_FROM_ABI const_local_iterator begin(size_type __n) const { return __table_.cbegin(__n); }
1511   _LIBCPP_HIDE_FROM_ABI const_local_iterator end(size_type __n) const { return __table_.cend(__n); }
1512   _LIBCPP_HIDE_FROM_ABI const_local_iterator cbegin(size_type __n) const { return __table_.cbegin(__n); }
1513   _LIBCPP_HIDE_FROM_ABI const_local_iterator cend(size_type __n) const { return __table_.cend(__n); }
1514
1515   _LIBCPP_HIDE_FROM_ABI float load_factor() const _NOEXCEPT { return __table_.load_factor(); }
1516   _LIBCPP_HIDE_FROM_ABI float max_load_factor() const _NOEXCEPT { return __table_.max_load_factor(); }
1517   _LIBCPP_HIDE_FROM_ABI void max_load_factor(float __mlf) { __table_.max_load_factor(__mlf); }
1518   _LIBCPP_HIDE_FROM_ABI void rehash(size_type __n) { __table_.__rehash_multi(__n); }
1519   _LIBCPP_HIDE_FROM_ABI void reserve(size_type __n) { __table_.__reserve_multi(__n); }
1520 };
1521
1522 #if _LIBCPP_STD_VER >= 17
1523 template <class _InputIterator,
1524           class _Hash      = hash<__iter_value_type<_InputIterator>>,
1525           class _Pred      = equal_to<__iter_value_type<_InputIterator>>,
1526           class _Allocator = allocator<__iter_value_type<_InputIterator>>,
1527           class            = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
1528           class            = enable_if_t<!__is_allocator<_Hash>::value>,
1529           class            = enable_if_t<!is_integral<_Hash>::value>,
1530           class            = enable_if_t<!__is_allocator<_Pred>::value>,
1531           class            = enable_if_t<__is_allocator<_Allocator>::value>>
1532 unordered_multiset(
1533     _InputIterator,
1534     _InputIterator,
1535     typename allocator_traits<_Allocator>::size_type = 0,
1536     _Hash                                            = _Hash(),
1537     _Pred                                            = _Pred(),
1538     _Allocator = _Allocator()) -> unordered_multiset<__iter_value_type<_InputIterator>, _Hash, _Pred, _Allocator>;
1539
1540 #  if _LIBCPP_STD_VER >= 23
1541 template <ranges::input_range _Range,
1542           class _Hash      = hash<ranges::range_value_t<_Range>>,
1543           class _Pred      = equal_to<ranges::range_value_t<_Range>>,
1544           class _Allocator = allocator<ranges::range_value_t<_Range>>,
1545           class            = enable_if_t<!__is_allocator<_Hash>::value>,
1546           class            = enable_if_t<!is_integral<_Hash>::value>,
1547           class            = enable_if_t<!__is_allocator<_Pred>::value>,
1548           class            = enable_if_t<__is_allocator<_Allocator>::value>>
1549 unordered_multiset(
1550     from_range_t,
1551     _Range&&,
1552     typename allocator_traits<_Allocator>::size_type = 0,
1553     _Hash                                            = _Hash(),
1554     _Pred                                            = _Pred(),
1555     _Allocator = _Allocator()) -> unordered_multiset<ranges::range_value_t<_Range>, _Hash, _Pred, _Allocator>; // C++23
1556 #  endif
1557
1558 template <class _Tp,
1559           class _Hash      = hash<_Tp>,
1560           class _Pred      = equal_to<_Tp>,
1561           class _Allocator = allocator<_Tp>,
1562           class            = enable_if_t<!__is_allocator<_Hash>::value>,
1563           class            = enable_if_t<!is_integral<_Hash>::value>,
1564           class            = enable_if_t<!__is_allocator<_Pred>::value>,
1565           class            = enable_if_t<__is_allocator<_Allocator>::value>>
1566 unordered_multiset(initializer_list<_Tp>,
1567                    typename allocator_traits<_Allocator>::size_type = 0,
1568                    _Hash                                            = _Hash(),
1569                    _Pred                                            = _Pred(),
1570                    _Allocator = _Allocator()) -> unordered_multiset<_Tp, _Hash, _Pred, _Allocator>;
1571
1572 template <class _InputIterator,
1573           class _Allocator,
1574           class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
1575           class = enable_if_t<__is_allocator<_Allocator>::value>>
1576 unordered_multiset(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Allocator)
1577     -> unordered_multiset<__iter_value_type<_InputIterator>,
1578                           hash<__iter_value_type<_InputIterator>>,
1579                           equal_to<__iter_value_type<_InputIterator>>,
1580                           _Allocator>;
1581
1582 template <class _InputIterator,
1583           class _Hash,
1584           class _Allocator,
1585           class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
1586           class = enable_if_t<!__is_allocator<_Hash>::value>,
1587           class = enable_if_t<!is_integral<_Hash>::value>,
1588           class = enable_if_t<__is_allocator<_Allocator>::value>>
1589 unordered_multiset(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
1590     -> unordered_multiset<__iter_value_type<_InputIterator>,
1591                           _Hash,
1592                           equal_to<__iter_value_type<_InputIterator>>,
1593                           _Allocator>;
1594
1595 #  if _LIBCPP_STD_VER >= 23
1596
1597 template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
1598 unordered_multiset(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Allocator)
1599     -> unordered_multiset<ranges::range_value_t<_Range>,
1600                           hash<ranges::range_value_t<_Range>>,
1601                           equal_to<ranges::range_value_t<_Range>>,
1602                           _Allocator>;
1603
1604 template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
1605 unordered_multiset(from_range_t, _Range&&, _Allocator)
1606     -> unordered_multiset<ranges::range_value_t<_Range>,
1607                           hash<ranges::range_value_t<_Range>>,
1608                           equal_to<ranges::range_value_t<_Range>>,
1609                           _Allocator>;
1610
1611 template <ranges::input_range _Range,
1612           class _Hash,
1613           class _Allocator,
1614           class = enable_if_t<!__is_allocator<_Hash>::value>,
1615           class = enable_if_t<!is_integral<_Hash>::value>,
1616           class = enable_if_t<__is_allocator<_Allocator>::value>>
1617 unordered_multiset(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
1618     -> unordered_multiset<ranges::range_value_t<_Range>, _Hash, equal_to<ranges::range_value_t<_Range>>, _Allocator>;
1619
1620 #  endif
1621
1622 template <class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
1623 unordered_multiset(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Allocator)
1624     -> unordered_multiset<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
1625
1626 template <class _Tp,
1627           class _Hash,
1628           class _Allocator,
1629           class = enable_if_t<!__is_allocator<_Hash>::value>,
1630           class = enable_if_t<!is_integral<_Hash>::value>,
1631           class = enable_if_t<__is_allocator<_Allocator>::value>>
1632 unordered_multiset(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
1633     -> unordered_multiset<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
1634 #endif
1635
1636 template <class _Value, class _Hash, class _Pred, class _Alloc>
1637 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1638     size_type __n, const hasher& __hf, const key_equal& __eql)
1639     : __table_(__hf, __eql) {
1640   __table_.__rehash_multi(__n);
1641 }
1642
1643 template <class _Value, class _Hash, class _Pred, class _Alloc>
1644 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1645     size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1646     : __table_(__hf, __eql, __a) {
1647   __table_.__rehash_multi(__n);
1648 }
1649
1650 template <class _Value, class _Hash, class _Pred, class _Alloc>
1651 template <class _InputIterator>
1652 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(_InputIterator __first, _InputIterator __last) {
1653   insert(__first, __last);
1654 }
1655
1656 template <class _Value, class _Hash, class _Pred, class _Alloc>
1657 template <class _InputIterator>
1658 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1659     _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql)
1660     : __table_(__hf, __eql) {
1661   __table_.__rehash_multi(__n);
1662   insert(__first, __last);
1663 }
1664
1665 template <class _Value, class _Hash, class _Pred, class _Alloc>
1666 template <class _InputIterator>
1667 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1668     _InputIterator __first,
1669     _InputIterator __last,
1670     size_type __n,
1671     const hasher& __hf,
1672     const key_equal& __eql,
1673     const allocator_type& __a)
1674     : __table_(__hf, __eql, __a) {
1675   __table_.__rehash_multi(__n);
1676   insert(__first, __last);
1677 }
1678
1679 template <class _Value, class _Hash, class _Pred, class _Alloc>
1680 inline unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(const allocator_type& __a)
1681     : __table_(__a) {}
1682
1683 template <class _Value, class _Hash, class _Pred, class _Alloc>
1684 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(const unordered_multiset& __u)
1685     : __table_(__u.__table_) {
1686   __table_.__rehash_multi(__u.bucket_count());
1687   insert(__u.begin(), __u.end());
1688 }
1689
1690 template <class _Value, class _Hash, class _Pred, class _Alloc>
1691 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1692     const unordered_multiset& __u, const allocator_type& __a)
1693     : __table_(__u.__table_, __a) {
1694   __table_.__rehash_multi(__u.bucket_count());
1695   insert(__u.begin(), __u.end());
1696 }
1697
1698 #ifndef _LIBCPP_CXX03_LANG
1699
1700 template <class _Value, class _Hash, class _Pred, class _Alloc>
1701 inline unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(unordered_multiset&& __u)
1702     _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
1703     : __table_(std::move(__u.__table_)) {}
1704
1705 template <class _Value, class _Hash, class _Pred, class _Alloc>
1706 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1707     unordered_multiset&& __u, const allocator_type& __a)
1708     : __table_(std::move(__u.__table_), __a) {
1709   if (__a != __u.get_allocator()) {
1710     iterator __i = __u.begin();
1711     while (__u.size() != 0)
1712       __table_.__insert_multi(std::move(__u.__table_.remove(__i++)->__get_value()));
1713   }
1714 }
1715
1716 template <class _Value, class _Hash, class _Pred, class _Alloc>
1717 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(initializer_list<value_type> __il) {
1718   insert(__il.begin(), __il.end());
1719 }
1720
1721 template <class _Value, class _Hash, class _Pred, class _Alloc>
1722 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1723     initializer_list<value_type> __il, size_type __n, const hasher& __hf, const key_equal& __eql)
1724     : __table_(__hf, __eql) {
1725   __table_.__rehash_multi(__n);
1726   insert(__il.begin(), __il.end());
1727 }
1728
1729 template <class _Value, class _Hash, class _Pred, class _Alloc>
1730 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1731     initializer_list<value_type> __il,
1732     size_type __n,
1733     const hasher& __hf,
1734     const key_equal& __eql,
1735     const allocator_type& __a)
1736     : __table_(__hf, __eql, __a) {
1737   __table_.__rehash_multi(__n);
1738   insert(__il.begin(), __il.end());
1739 }
1740
1741 template <class _Value, class _Hash, class _Pred, class _Alloc>
1742 inline unordered_multiset<_Value, _Hash, _Pred, _Alloc>&
1743 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(unordered_multiset&& __u)
1744     _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) {
1745   __table_ = std::move(__u.__table_);
1746   return *this;
1747 }
1748
1749 template <class _Value, class _Hash, class _Pred, class _Alloc>
1750 inline unordered_multiset<_Value, _Hash, _Pred, _Alloc>&
1751 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(initializer_list<value_type> __il) {
1752   __table_.__assign_multi(__il.begin(), __il.end());
1753   return *this;
1754 }
1755
1756 #endif // _LIBCPP_CXX03_LANG
1757
1758 template <class _Value, class _Hash, class _Pred, class _Alloc>
1759 template <class _InputIterator>
1760 inline void unordered_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) {
1761   for (; __first != __last; ++__first)
1762     __table_.__insert_multi(*__first);
1763 }
1764
1765 template <class _Value, class _Hash, class _Pred, class _Alloc>
1766 inline _LIBCPP_HIDE_FROM_ABI void
1767 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1768     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
1769   __x.swap(__y);
1770 }
1771
1772 #if _LIBCPP_STD_VER >= 20
1773 template <class _Value, class _Hash, class _Pred, class _Alloc, class _Predicate>
1774 inline _LIBCPP_HIDE_FROM_ABI typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::size_type
1775 erase_if(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __c, _Predicate __pred) {
1776   return std::__libcpp_erase_if_container(__c, __pred);
1777 }
1778 #endif
1779
1780 template <class _Value, class _Hash, class _Pred, class _Alloc>
1781 _LIBCPP_HIDE_FROM_ABI bool operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1782                                       const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) {
1783   if (__x.size() != __y.size())
1784     return false;
1785   typedef typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator const_iterator;
1786   typedef pair<const_iterator, const_iterator> _EqRng;
1787   for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) {
1788     _EqRng __xeq = __x.equal_range(*__i);
1789     _EqRng __yeq = __y.equal_range(*__i);
1790     if (std::distance(__xeq.first, __xeq.second) != std::distance(__yeq.first, __yeq.second) ||
1791         !std::is_permutation(__xeq.first, __xeq.second, __yeq.first))
1792       return false;
1793     __i = __xeq.second;
1794   }
1795   return true;
1796 }
1797
1798 #if _LIBCPP_STD_VER <= 17
1799
1800 template <class _Value, class _Hash, class _Pred, class _Alloc>
1801 inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1802                                              const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) {
1803   return !(__x == __y);
1804 }
1805
1806 #endif
1807
1808 template <class _Value, class _Hash, class _Pred, class _Alloc>
1809 struct __container_traits<unordered_multiset<_Value, _Hash, _Pred, _Alloc> > {
1810   // http://eel.is/c++draft/unord.req.except#2
1811   //  For unordered associative containers, if an exception is thrown by any operation
1812   //  other than the container's hash function from within an insert or emplace function
1813   //  inserting a single element, the insertion has no effect.
1814   static _LIBCPP_CONSTEXPR const bool __emplacement_has_strong_exception_safety_guarantee =
1815       __nothrow_invokable<_Hash, const _Value&>::value;
1816 };
1817
1818 _LIBCPP_END_NAMESPACE_STD
1819
1820 #if _LIBCPP_STD_VER >= 17
1821 _LIBCPP_BEGIN_NAMESPACE_STD
1822 namespace pmr {
1823 template <class _KeyT, class _HashT = std::hash<_KeyT>, class _PredT = std::equal_to<_KeyT>>
1824 using unordered_set _LIBCPP_AVAILABILITY_PMR = std::unordered_set<_KeyT, _HashT, _PredT, polymorphic_allocator<_KeyT>>;
1825
1826 template <class _KeyT, class _HashT = std::hash<_KeyT>, class _PredT = std::equal_to<_KeyT>>
1827 using unordered_multiset _LIBCPP_AVAILABILITY_PMR =
1828     std::unordered_multiset<_KeyT, _HashT, _PredT, polymorphic_allocator<_KeyT>>;
1829 } // namespace pmr
1830 _LIBCPP_END_NAMESPACE_STD
1831 #endif
1832
1833 _LIBCPP_POP_MACROS
1834
1835 #if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
1836 #  include <cmath>
1837 #  include <concepts>
1838 #  include <cstdlib>
1839 #  include <functional>
1840 #  include <iterator>
1841 #  include <stdexcept>
1842 #  include <type_traits>
1843 #endif
1844
1845 #endif // _LIBCPP_UNORDERED_SET