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