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