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