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