1// -*- C++ -*-
2//===----------------------------------------------------------------------===//
3//
4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5// See https://llvm.org/LICENSE.txt for license information.
6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7//
8//===----------------------------------------------------------------------===//
9
10#ifndef _LIBCPP_UNORDERED_SET
11#define _LIBCPP_UNORDERED_SET
12
13// clang-format off
14
15/*
16
17 unordered_set synopsis
18
19#include <initializer_list>
20
21namespace std
22{
23
24template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,
25 class Alloc = allocator<Value>>
26class unordered_set
27{
28public:
29 // types
30 typedef Value key_type;
31 typedef key_type value_type;
32 typedef Hash hasher;
33 typedef Pred key_equal;
34 typedef Alloc allocator_type;
35 typedef value_type& reference;
36 typedef const value_type& const_reference;
37 typedef typename allocator_traits<allocator_type>::pointer pointer;
38 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
39 typedef typename allocator_traits<allocator_type>::size_type size_type;
40 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
41
42 typedef /unspecified/ iterator;
43 typedef /unspecified/ const_iterator;
44 typedef /unspecified/ local_iterator;
45 typedef /unspecified/ const_local_iterator;
46
47 typedef unspecified node_type unspecified; // C++17
48 typedef INSERT_RETURN_TYPE<iterator, node_type> insert_return_type; // C++17
49
50 unordered_set()
51 noexcept(
52 is_nothrow_default_constructible<hasher>::value &&
53 is_nothrow_default_constructible<key_equal>::value &&
54 is_nothrow_default_constructible<allocator_type>::value);
55 explicit unordered_set(size_type n, const hasher& hf = hasher(),
56 const key_equal& eql = key_equal(),
57 const allocator_type& a = allocator_type());
58 template <class InputIterator>
59 unordered_set(InputIterator f, InputIterator l,
60 size_type n = 0, const hasher& hf = hasher(),
61 const key_equal& eql = key_equal(),
62 const allocator_type& a = allocator_type());
63 template<container-compatible-range<value_type> R>
64 unordered_set(from_range_t, R&& rg, size_type n = see below,
65 const hasher& hf = hasher(), const key_equal& eql = key_equal(),
66 const allocator_type& a = allocator_type()); // C++23
67 explicit unordered_set(const allocator_type&);
68 unordered_set(const unordered_set&);
69 unordered_set(const unordered_set&, const Allocator&);
70 unordered_set(unordered_set&&)
71 noexcept(
72 is_nothrow_move_constructible<hasher>::value &&
73 is_nothrow_move_constructible<key_equal>::value &&
74 is_nothrow_move_constructible<allocator_type>::value);
75 unordered_set(unordered_set&&, const Allocator&);
76 unordered_set(initializer_list<value_type>, size_type n = 0,
77 const hasher& hf = hasher(), const key_equal& eql = key_equal(),
78 const allocator_type& a = allocator_type());
79 unordered_set(size_type n, const allocator_type& a); // C++14
80 unordered_set(size_type n, const hasher& hf, const allocator_type& a); // C++14
81 template <class InputIterator>
82 unordered_set(InputIterator f, InputIterator l, size_type n, const allocator_type& a); // C++14
83 template <class InputIterator>
84 unordered_set(InputIterator f, InputIterator l, size_type n,
85 const hasher& hf, const allocator_type& a); // C++14
86 template<container-compatible-range<value_type> R>
87 unordered_set(from_range_t, R&& rg, size_type n, const allocator_type& a)
88 : unordered_set(from_range, std::forward<R>(rg), n, hasher(), key_equal(), a) { } // C++23
89 template<container-compatible-range<value_type> R>
90 unordered_set(from_range_t, R&& rg, size_type n, const hasher& hf, const allocator_type& a)
91 : unordered_set(from_range, std::forward<R>(rg), n, hf, key_equal(), a) { } // C++23
92 unordered_set(initializer_list<value_type> il, size_type n, const allocator_type& a); // C++14
93 unordered_set(initializer_list<value_type> il, size_type n,
94 const hasher& hf, const allocator_type& a); // C++14
95 ~unordered_set();
96 unordered_set& operator=(const unordered_set&);
97 unordered_set& operator=(unordered_set&&)
98 noexcept(
99 allocator_type::propagate_on_container_move_assignment::value &&
100 is_nothrow_move_assignable<allocator_type>::value &&
101 is_nothrow_move_assignable<hasher>::value &&
102 is_nothrow_move_assignable<key_equal>::value);
103 unordered_set& operator=(initializer_list<value_type>);
104
105 allocator_type get_allocator() const noexcept;
106
107 bool empty() const noexcept;
108 size_type size() const noexcept;
109 size_type max_size() const noexcept;
110
111 iterator begin() noexcept;
112 iterator end() noexcept;
113 const_iterator begin() const noexcept;
114 const_iterator end() const noexcept;
115 const_iterator cbegin() const noexcept;
116 const_iterator cend() const noexcept;
117
118 template <class... Args>
119 pair<iterator, bool> emplace(Args&&... args);
120 template <class... Args>
121 iterator emplace_hint(const_iterator position, Args&&... args);
122 pair<iterator, bool> insert(const value_type& obj);
123 pair<iterator, bool> insert(value_type&& obj);
124 iterator insert(const_iterator hint, const value_type& obj);
125 iterator insert(const_iterator hint, value_type&& obj);
126 template <class InputIterator>
127 void insert(InputIterator first, InputIterator last);
128 template<container-compatible-range<value_type> R>
129 void insert_range(R&& rg); // C++23
130 void insert(initializer_list<value_type>);
131
132 node_type extract(const_iterator position); // C++17
133 node_type extract(const key_type& x); // C++17
134 insert_return_type insert(node_type&& nh); // C++17
135 iterator insert(const_iterator hint, node_type&& nh); // C++17
136
137 iterator erase(const_iterator position);
138 iterator erase(iterator position); // C++14
139 size_type erase(const key_type& k);
140 iterator erase(const_iterator first, const_iterator last);
141 void clear() noexcept;
142
143 template<class H2, class P2>
144 void merge(unordered_set<Key, H2, P2, Allocator>& source); // C++17
145 template<class H2, class P2>
146 void merge(unordered_set<Key, H2, P2, Allocator>&& source); // C++17
147 template<class H2, class P2>
148 void merge(unordered_multiset<Key, H2, P2, Allocator>& source); // C++17
149 template<class H2, class P2>
150 void merge(unordered_multiset<Key, H2, P2, Allocator>&& source); // C++17
151
152 void swap(unordered_set&)
153 noexcept(allocator_traits<Allocator>::is_always_equal::value &&
154 noexcept(swap(declval<hasher&>(), declval<hasher&>())) &&
155 noexcept(swap(declval<key_equal&>(), declval<key_equal&>()))); // C++17
156
157 hasher hash_function() const;
158 key_equal key_eq() const;
159
160 iterator find(const key_type& k);
161 const_iterator find(const key_type& k) const;
162 template<typename K>
163 iterator find(const K& x); // C++20
164 template<typename K>
165 const_iterator find(const K& x) const; // C++20
166 size_type count(const key_type& k) const;
167 template<typename K>
168 size_type count(const K& k) const; // C++20
169 bool contains(const key_type& k) const; // C++20
170 template<typename K>
171 bool contains(const K& k) const; // C++20
172 pair<iterator, iterator> equal_range(const key_type& k);
173 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
174 template<typename K>
175 pair<iterator, iterator> equal_range(const K& k); // C++20
176 template<typename K>
177 pair<const_iterator, const_iterator> equal_range(const K& k) const; // C++20
178
179 size_type bucket_count() const noexcept;
180 size_type max_bucket_count() const noexcept;
181
182 size_type bucket_size(size_type n) const;
183 size_type bucket(const key_type& k) const;
184
185 local_iterator begin(size_type n);
186 local_iterator end(size_type n);
187 const_local_iterator begin(size_type n) const;
188 const_local_iterator end(size_type n) const;
189 const_local_iterator cbegin(size_type n) const;
190 const_local_iterator cend(size_type n) const;
191
192 float load_factor() const noexcept;
193 float max_load_factor() const noexcept;
194 void max_load_factor(float z);
195 void rehash(size_type n);
196 void reserve(size_type n);
197};
198
199template<class InputIterator,
200 class Hash = hash<typename iterator_traits<InputIterator>::value_type>,
201 class Pred = equal_to<typename iterator_traits<InputIterator>::value_type>,
202 class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
203unordered_set(InputIterator, InputIterator, typename see below::size_type = see below,
204 Hash = Hash(), Pred = Pred(), Allocator = Allocator())
205 -> unordered_set<typename iterator_traits<InputIterator>::value_type,
206 Hash, Pred, Allocator>; // C++17
207
208template<ranges::input_range R,
209 class Hash = hash<ranges::range_value_t<R>>,
210 class Pred = equal_to<ranges::range_value_t<R>>,
211 class Allocator = allocator<ranges::range_value_t<R>>>
212 unordered_set(from_range_t, R&&, typename see below::size_type = see below, Hash = Hash(), Pred = Pred(), Allocator = Allocator())
213 -> unordered_set<ranges::range_value_t<R>, Hash, Pred, Allocator>; // C++23
214
215template<class T, class Hash = hash<T>,
216 class Pred = equal_to<T>, class Allocator = allocator<T>>
217unordered_set(initializer_list<T>, typename see below::size_type = see below,
218 Hash = Hash(), Pred = Pred(), Allocator = Allocator())
219 -> unordered_set<T, Hash, Pred, Allocator>; // C++17
220
221template<class InputIterator, class Allocator>
222unordered_set(InputIterator, InputIterator, typename see below::size_type, Allocator)
223 -> unordered_set<typename iterator_traits<InputIterator>::value_type,
224 hash<typename iterator_traits<InputIterator>::value_type>,
225 equal_to<typename iterator_traits<InputIterator>::value_type>,
226 Allocator>; // C++17
227
228template<class InputIterator, class Hash, class Allocator>
229unordered_set(InputIterator, InputIterator, typename see below::size_type,
230 Hash, Allocator)
231 -> unordered_set<typename iterator_traits<InputIterator>::value_type, Hash,
232 equal_to<typename iterator_traits<InputIterator>::value_type>,
233 Allocator>; // C++17
234
235template<ranges::input_range R, class Allocator>
236 unordered_set(from_range_t, R&&, typename see below::size_type, Allocator)
237 -> unordered_set<ranges::range_value_t<R>, hash<ranges::range_value_t<R>>,
238 equal_to<ranges::range_value_t<R>>, Allocator>; // C++23
239
240template<ranges::input_range R, class Allocator>
241 unordered_set(from_range_t, R&&, Allocator)
242 -> unordered_set<ranges::range_value_t<R>, hash<ranges::range_value_t<R>>,
243 equal_to<ranges::range_value_t<R>>, Allocator>; // C++23
244
245template<ranges::input_range R, class Hash, class Allocator>
246 unordered_set(from_range_t, R&&, typename see below::size_type, Hash, Allocator)
247 -> unordered_set<ranges::range_value_t<R>, Hash,
248 equal_to<ranges::range_value_t<R>>, Allocator>; // C++23
249
250template<class T, class Allocator>
251unordered_set(initializer_list<T>, typename see below::size_type, Allocator)
252 -> unordered_set<T, hash<T>, equal_to<T>, Allocator>; // C++17
253
254template<class T, class Hash, class Allocator>
255unordered_set(initializer_list<T>, typename see below::size_type, Hash, Allocator)
256 -> unordered_set<T, Hash, equal_to<T>, Allocator>; // C++17
257
258template <class Value, class Hash, class Pred, class Alloc>
259 void swap(unordered_set<Value, Hash, Pred, Alloc>& x,
260 unordered_set<Value, Hash, Pred, Alloc>& y)
261 noexcept(noexcept(x.swap(y)));
262
263template <class Value, class Hash, class Pred, class Alloc>
264 bool
265 operator==(const unordered_set<Value, Hash, Pred, Alloc>& x,
266 const unordered_set<Value, Hash, Pred, Alloc>& y);
267
268template <class Value, class Hash, class Pred, class Alloc>
269 bool
270 operator!=(const unordered_set<Value, Hash, Pred, Alloc>& x,
271 const unordered_set<Value, Hash, Pred, Alloc>& y); // removed in C++20
272
273template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,
274 class Alloc = allocator<Value>>
275class unordered_multiset
276{
277public:
278 // types
279 typedef Value key_type;
280 typedef key_type value_type;
281 typedef Hash hasher;
282 typedef Pred key_equal;
283 typedef Alloc allocator_type;
284 typedef value_type& reference;
285 typedef const value_type& const_reference;
286 typedef typename allocator_traits<allocator_type>::pointer pointer;
287 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
288 typedef typename allocator_traits<allocator_type>::size_type size_type;
289 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
290
291 typedef /unspecified/ iterator;
292 typedef /unspecified/ const_iterator;
293 typedef /unspecified/ local_iterator;
294 typedef /unspecified/ const_local_iterator;
295
296 typedef unspecified node_type unspecified; // C++17
297
298 unordered_multiset()
299 noexcept(
300 is_nothrow_default_constructible<hasher>::value &&
301 is_nothrow_default_constructible<key_equal>::value &&
302 is_nothrow_default_constructible<allocator_type>::value);
303 explicit unordered_multiset(size_type n, const hasher& hf = hasher(),
304 const key_equal& eql = key_equal(),
305 const allocator_type& a = allocator_type());
306 template <class InputIterator>
307 unordered_multiset(InputIterator f, InputIterator l,
308 size_type n = 0, const hasher& hf = hasher(),
309 const key_equal& eql = key_equal(),
310 const allocator_type& a = allocator_type());
311 template<container-compatible-range<value_type> R>
312 unordered_multiset(from_range_t, R&& rg, size_type n = see below,
313 const hasher& hf = hasher(), const key_equal& eql = key_equal(),
314 const allocator_type& a = allocator_type()); // C++23
315 explicit unordered_multiset(const allocator_type&);
316 unordered_multiset(const unordered_multiset&);
317 unordered_multiset(const unordered_multiset&, const Allocator&);
318 unordered_multiset(unordered_multiset&&)
319 noexcept(
320 is_nothrow_move_constructible<hasher>::value &&
321 is_nothrow_move_constructible<key_equal>::value &&
322 is_nothrow_move_constructible<allocator_type>::value);
323 unordered_multiset(unordered_multiset&&, const Allocator&);
324 unordered_multiset(initializer_list<value_type>, size_type n = /see below/,
325 const hasher& hf = hasher(), const key_equal& eql = key_equal(),
326 const allocator_type& a = allocator_type());
327 unordered_multiset(size_type n, const allocator_type& a); // C++14
328 unordered_multiset(size_type n, const hasher& hf, const allocator_type& a); // C++14
329 template <class InputIterator>
330 unordered_multiset(InputIterator f, InputIterator l, size_type n, const allocator_type& a); // C++14
331 template <class InputIterator>
332 unordered_multiset(InputIterator f, InputIterator l, size_type n,
333 const hasher& hf, const allocator_type& a); // C++14
334 template<container-compatible-range<value_type> R>
335 unordered_multiset(from_range_t, R&& rg, size_type n, const allocator_type& a)
336 : unordered_multiset(from_range, std::forward<R>(rg), n, hasher(), key_equal(), a) { } // C++23
337 template<container-compatible-range<value_type> R>
338 unordered_multiset(from_range_t, R&& rg, size_type n, const hasher& hf, const allocator_type& a)
339 : unordered_multiset(from_range, std::forward<R>(rg), n, hf, key_equal(), a) { } // C++23
340 unordered_multiset(initializer_list<value_type> il, size_type n, const allocator_type& a); // C++14
341 unordered_multiset(initializer_list<value_type> il, size_type n,
342 const hasher& hf, const allocator_type& a); // C++14
343 ~unordered_multiset();
344 unordered_multiset& operator=(const unordered_multiset&);
345 unordered_multiset& operator=(unordered_multiset&&)
346 noexcept(
347 allocator_type::propagate_on_container_move_assignment::value &&
348 is_nothrow_move_assignable<allocator_type>::value &&
349 is_nothrow_move_assignable<hasher>::value &&
350 is_nothrow_move_assignable<key_equal>::value);
351 unordered_multiset& operator=(initializer_list<value_type>);
352
353 allocator_type get_allocator() const noexcept;
354
355 bool empty() const noexcept;
356 size_type size() const noexcept;
357 size_type max_size() const noexcept;
358
359 iterator begin() noexcept;
360 iterator end() noexcept;
361 const_iterator begin() const noexcept;
362 const_iterator end() const noexcept;
363 const_iterator cbegin() const noexcept;
364 const_iterator cend() const noexcept;
365
366 template <class... Args>
367 iterator emplace(Args&&... args);
368 template <class... Args>
369 iterator emplace_hint(const_iterator position, Args&&... args);
370 iterator insert(const value_type& obj);
371 iterator insert(value_type&& obj);
372 iterator insert(const_iterator hint, const value_type& obj);
373 iterator insert(const_iterator hint, value_type&& obj);
374 template <class InputIterator>
375 void insert(InputIterator first, InputIterator last);
376 template<container-compatible-range<value_type> R>
377 void insert_range(R&& rg); // C++23
378 void insert(initializer_list<value_type>);
379
380 node_type extract(const_iterator position); // C++17
381 node_type extract(const key_type& x); // C++17
382 iterator insert(node_type&& nh); // C++17
383 iterator insert(const_iterator hint, node_type&& nh); // C++17
384
385 iterator erase(const_iterator position);
386 iterator erase(iterator position); // C++14
387 size_type erase(const key_type& k);
388 iterator erase(const_iterator first, const_iterator last);
389 void clear() noexcept;
390
391 template<class H2, class P2>
392 void merge(unordered_multiset<Key, H2, P2, Allocator>& source); // C++17
393 template<class H2, class P2>
394 void merge(unordered_multiset<Key, H2, P2, Allocator>&& source); // C++17
395 template<class H2, class P2>
396 void merge(unordered_set<Key, H2, P2, Allocator>& source); // C++17
397 template<class H2, class P2>
398 void merge(unordered_set<Key, H2, P2, Allocator>&& source); // C++17
399
400 void swap(unordered_multiset&)
401 noexcept(allocator_traits<Allocator>::is_always_equal::value &&
402 noexcept(swap(declval<hasher&>(), declval<hasher&>())) &&
403 noexcept(swap(declval<key_equal&>(), declval<key_equal&>()))); // C++17
404
405 hasher hash_function() const;
406 key_equal key_eq() const;
407
408 iterator find(const key_type& k);
409 const_iterator find(const key_type& k) const;
410 template<typename K>
411 iterator find(const K& x); // C++20
412 template<typename K>
413 const_iterator find(const K& x) const; // C++20
414 size_type count(const key_type& k) const;
415 template<typename K>
416 size_type count(const K& k) const; // C++20
417 bool contains(const key_type& k) const; // C++20
418 template<typename K>
419 bool contains(const K& k) const; // C++20
420 pair<iterator, iterator> equal_range(const key_type& k);
421 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
422 template<typename K>
423 pair<iterator, iterator> equal_range(const K& k); // C++20
424 template<typename K>
425 pair<const_iterator, const_iterator> equal_range(const K& k) const; // C++20
426
427 size_type bucket_count() const noexcept;
428 size_type max_bucket_count() const noexcept;
429
430 size_type bucket_size(size_type n) const;
431 size_type bucket(const key_type& k) const;
432
433 local_iterator begin(size_type n);
434 local_iterator end(size_type n);
435 const_local_iterator begin(size_type n) const;
436 const_local_iterator end(size_type n) const;
437 const_local_iterator cbegin(size_type n) const;
438 const_local_iterator cend(size_type n) const;
439
440 float load_factor() const noexcept;
441 float max_load_factor() const noexcept;
442 void max_load_factor(float z);
443 void rehash(size_type n);
444 void reserve(size_type n);
445};
446
447template<class InputIterator,
448 class Hash = hash<typename iterator_traits<InputIterator>::value_type>,
449 class Pred = equal_to<typename iterator_traits<InputIterator>::value_type>,
450 class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
451unordered_multiset(InputIterator, InputIterator, see below::size_type = see below,
452 Hash = Hash(), Pred = Pred(), Allocator = Allocator())
453 -> unordered_multiset<typename iterator_traits<InputIterator>::value_type,
454 Hash, Pred, Allocator>; // C++17
455
456template<ranges::input_range R,
457 class Hash = hash<ranges::range_value_t<R>>,
458 class Pred = equal_to<ranges::range_value_t<R>>,
459 class Allocator = allocator<ranges::range_value_t<R>>>
460 unordered_multiset(from_range_t, R&&, typename see below::size_type = see below, Hash = Hash(), Pred = Pred(), Allocator = Allocator())
461 -> unordered_multiset<ranges::range_value_t<R>, Hash, Pred, Allocator>; // C++23
462
463template<class T, class Hash = hash<T>,
464 class Pred = equal_to<T>, class Allocator = allocator<T>>
465unordered_multiset(initializer_list<T>, typename see below::size_type = see below,
466 Hash = Hash(), Pred = Pred(), Allocator = Allocator())
467 -> unordered_multiset<T, Hash, Pred, Allocator>; // C++17
468
469template<class InputIterator, class Allocator>
470unordered_multiset(InputIterator, InputIterator, typename see below::size_type, Allocator)
471 -> unordered_multiset<typename iterator_traits<InputIterator>::value_type,
472 hash<typename iterator_traits<InputIterator>::value_type>,
473 equal_to<typename iterator_traits<InputIterator>::value_type>,
474 Allocator>; // C++17
475
476template<class InputIterator, class Hash, class Allocator>
477unordered_multiset(InputIterator, InputIterator, typename see below::size_type,
478 Hash, Allocator)
479 -> unordered_multiset<typename iterator_traits<InputIterator>::value_type, Hash,
480 equal_to<typename iterator_traits<InputIterator>::value_type>, Allocator>; // C++17
481
482template<ranges::input_range R, class Allocator>
483 unordered_multiset(from_range_t, R&&, typename see below::size_type, Allocator)
484 -> unordered_multiset<ranges::range_value_t<R>, hash<ranges::range_value_t<R>>,
485 equal_to<ranges::range_value_t<R>>, Allocator>; // C++23
486
487template<ranges::input_range R, class Allocator>
488 unordered_multiset(from_range_t, R&&, Allocator)
489 -> unordered_multiset<ranges::range_value_t<R>, hash<ranges::range_value_t<R>>,
490 equal_to<ranges::range_value_t<R>>, Allocator>; // C++23
491
492template<ranges::input_range R, class Hash, class Allocator>
493 unordered_multiset(from_range_t, R&&, typename see below::size_type, Hash, Allocator)
494 -> unordered_multiset<ranges::range_value_t<R>, Hash,
495 equal_to<ranges::range_value_t<R>>, Allocator>; // C++23
496
497template<class T, class Allocator>
498unordered_multiset(initializer_list<T>, typename see below::size_type, Allocator)
499 -> unordered_multiset<T, hash<T>, equal_to<T>, Allocator>; // C++17
500
501template<class T, class Hash, class Allocator>
502unordered_multiset(initializer_list<T>, typename see below::size_type, Hash, Allocator)
503 -> unordered_multiset<T, Hash, equal_to<T>, Allocator>; // C++17
504
505template <class Value, class Hash, class Pred, class Alloc>
506 void swap(unordered_multiset<Value, Hash, Pred, Alloc>& x,
507 unordered_multiset<Value, Hash, Pred, Alloc>& y)
508 noexcept(noexcept(x.swap(y)));
509
510template <class K, class T, class H, class P, class A, class Predicate>
511 typename unordered_set<K, T, H, P, A>::size_type
512 erase_if(unordered_set<K, T, H, P, A>& c, Predicate pred); // C++20
513
514template <class K, class T, class H, class P, class A, class Predicate>
515 typename unordered_multiset<K, T, H, P, A>::size_type
516 erase_if(unordered_multiset<K, T, H, P, A>& c, Predicate pred); // C++20
517
518
519template <class Value, class Hash, class Pred, class Alloc>
520 bool
521 operator==(const unordered_multiset<Value, Hash, Pred, Alloc>& x,
522 const unordered_multiset<Value, Hash, Pred, Alloc>& y);
523
524template <class Value, class Hash, class Pred, class Alloc>
525 bool
526 operator!=(const unordered_multiset<Value, Hash, Pred, Alloc>& x,
527 const unordered_multiset<Value, Hash, Pred, Alloc>& y); // removed in C++20
528} // std
529
530*/
531
532// clang-format on
533
534#include <__algorithm/is_permutation.h>
535#include <__assert>
536#include <__config>
537#include <__functional/is_transparent.h>
538#include <__functional/operations.h>
539#include <__hash_table>
540#include <__iterator/distance.h>
541#include <__iterator/erase_if_container.h>
542#include <__iterator/iterator_traits.h>
543#include <__iterator/ranges_iterator_traits.h>
544#include <__memory/addressof.h>
545#include <__memory/allocator.h>
546#include <__memory_resource/polymorphic_allocator.h>
547#include <__node_handle>
548#include <__ranges/concepts.h>
549#include <__ranges/container_compatible_range.h>
550#include <__ranges/from_range.h>
551#include <__type_traits/is_allocator.h>
552#include <__utility/forward.h>
553#include <version>
554
555// standard-mandated includes
556
557// [iterator.range]
558#include <__iterator/access.h>
559#include <__iterator/data.h>
560#include <__iterator/empty.h>
561#include <__iterator/reverse_access.h>
562#include <__iterator/size.h>
563
564// [unord.set.syn]
565#include <compare>
566#include <initializer_list>
567
568#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
569# pragma GCC system_header
570#endif
571
572_LIBCPP_PUSH_MACROS
573#include <__undef_macros>
574
575_LIBCPP_BEGIN_NAMESPACE_STD
576
577template <class _Value, class _Hash, class _Pred, class _Alloc>
578class unordered_multiset;
579
580template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, class _Alloc = allocator<_Value> >
581class _LIBCPP_TEMPLATE_VIS unordered_set {
582public:
583 // types
584 typedef _Value key_type;
585 typedef key_type value_type;
586 typedef __type_identity_t<_Hash> hasher;
587 typedef __type_identity_t<_Pred> key_equal;
588 typedef __type_identity_t<_Alloc> allocator_type;
589 typedef value_type& reference;
590 typedef const value_type& const_reference;
591 static_assert(__check_valid_allocator<allocator_type>::value, "");
592 static_assert(is_same<value_type, typename allocator_type::value_type>::value,
593 "Allocator::value_type must be same type as value_type");
594
595private:
596 typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
597
598 __table __table_;
599
600public:
601 typedef typename __table::pointer pointer;
602 typedef typename __table::const_pointer const_pointer;
603 typedef typename __table::size_type size_type;
604 typedef typename __table::difference_type difference_type;
605
606 typedef typename __table::const_iterator iterator;
607 typedef typename __table::const_iterator const_iterator;
608 typedef typename __table::const_local_iterator local_iterator;
609 typedef typename __table::const_local_iterator const_local_iterator;
610
611#if _LIBCPP_STD_VER >= 17
612 typedef __set_node_handle<typename __table::__node, allocator_type> node_type;
613 typedef __insert_return_type<iterator, node_type> insert_return_type;
614#endif
615
616 template <class _Value2, class _Hash2, class _Pred2, class _Alloc2>
617 friend class _LIBCPP_TEMPLATE_VIS unordered_set;
618 template <class _Value2, class _Hash2, class _Pred2, class _Alloc2>
619 friend class _LIBCPP_TEMPLATE_VIS unordered_multiset;
620
621 _LIBCPP_HIDE_FROM_ABI unordered_set() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) {}
622 explicit _LIBCPP_HIDE_FROM_ABI
623 unordered_set(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
624#if _LIBCPP_STD_VER >= 14
625 inline _LIBCPP_HIDE_FROM_ABI unordered_set(size_type __n, const allocator_type& __a)
626 : unordered_set(__n, hasher(), key_equal(), __a) {}
627 inline _LIBCPP_HIDE_FROM_ABI unordered_set(size_type __n, const hasher& __hf, const allocator_type& __a)
628 : unordered_set(__n, __hf, key_equal(), __a) {}
629#endif
630 _LIBCPP_HIDE_FROM_ABI
631 unordered_set(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a);
632 template <class _InputIterator>
633 _LIBCPP_HIDE_FROM_ABI unordered_set(_InputIterator __first, _InputIterator __last);
634 template <class _InputIterator>
635 _LIBCPP_HIDE_FROM_ABI
636 unordered_set(_InputIterator __first,
637 _InputIterator __last,
638 size_type __n,
639 const hasher& __hf = hasher(),
640 const key_equal& __eql = key_equal());
641 template <class _InputIterator>
642 _LIBCPP_HIDE_FROM_ABI unordered_set(
643 _InputIterator __first,
644 _InputIterator __last,
645 size_type __n,
646 const hasher& __hf,
647 const key_equal& __eql,
648 const allocator_type& __a);
649
650#if _LIBCPP_STD_VER >= 23
651 template <_ContainerCompatibleRange<value_type> _Range>
652 _LIBCPP_HIDE_FROM_ABI unordered_set(
653 from_range_t,
654 _Range&& __range,
655 size_type __n = /*implementation-defined*/ 0,
656 const hasher& __hf = hasher(),
657 const key_equal& __eql = key_equal(),
658 const allocator_type& __a = allocator_type())
659 : __table_(__hf, __eql, __a) {
660 if (__n > 0) {
661 __table_.__rehash_unique(__n);
662 }
663 insert_range(std::forward<_Range>(__range));
664 }
665#endif
666
667#if _LIBCPP_STD_VER >= 14
668 template <class _InputIterator>
669 inline _LIBCPP_HIDE_FROM_ABI
670 unordered_set(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a)
671 : unordered_set(__first, __last, __n, hasher(), key_equal(), __a) {}
672 template <class _InputIterator>
673 _LIBCPP_HIDE_FROM_ABI unordered_set(
674 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const allocator_type& __a)
675 : unordered_set(__first, __last, __n, __hf, key_equal(), __a) {}
676#endif
677
678#if _LIBCPP_STD_VER >= 23
679 template <_ContainerCompatibleRange<value_type> _Range>
680 _LIBCPP_HIDE_FROM_ABI unordered_set(from_range_t, _Range&& __range, size_type __n, const allocator_type& __a)
681 : unordered_set(from_range, std::forward<_Range>(__range), __n, hasher(), key_equal(), __a) {}
682
683 template <_ContainerCompatibleRange<value_type> _Range>
684 _LIBCPP_HIDE_FROM_ABI
685 unordered_set(from_range_t, _Range&& __range, size_type __n, const hasher& __hf, const allocator_type& __a)
686 : unordered_set(from_range, std::forward<_Range>(__range), __n, __hf, key_equal(), __a) {}
687#endif
688
689 _LIBCPP_HIDE_FROM_ABI explicit unordered_set(const allocator_type& __a);
690 _LIBCPP_HIDE_FROM_ABI unordered_set(const unordered_set& __u);
691 _LIBCPP_HIDE_FROM_ABI unordered_set(const unordered_set& __u, const allocator_type& __a);
692#ifndef _LIBCPP_CXX03_LANG
693 _LIBCPP_HIDE_FROM_ABI unordered_set(unordered_set&& __u) _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
694 _LIBCPP_HIDE_FROM_ABI unordered_set(unordered_set&& __u, const allocator_type& __a);
695 _LIBCPP_HIDE_FROM_ABI unordered_set(initializer_list<value_type> __il);
696 _LIBCPP_HIDE_FROM_ABI
697 unordered_set(initializer_list<value_type> __il,
698 size_type __n,
699 const hasher& __hf = hasher(),
700 const key_equal& __eql = key_equal());
701 _LIBCPP_HIDE_FROM_ABI unordered_set(
702 initializer_list<value_type> __il,
703 size_type __n,
704 const hasher& __hf,
705 const key_equal& __eql,
706 const allocator_type& __a);
707# if _LIBCPP_STD_VER >= 14
708 inline _LIBCPP_HIDE_FROM_ABI
709 unordered_set(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)
710 : unordered_set(__il, __n, hasher(), key_equal(), __a) {}
711 inline _LIBCPP_HIDE_FROM_ABI
712 unordered_set(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a)
713 : unordered_set(__il, __n, __hf, key_equal(), __a) {}
714# endif
715#endif // _LIBCPP_CXX03_LANG
716 _LIBCPP_HIDE_FROM_ABI ~unordered_set() {
717 static_assert(sizeof(std::__diagnose_unordered_container_requirements<_Value, _Hash, _Pred>(0)), "");
718 }
719
720 _LIBCPP_HIDE_FROM_ABI unordered_set& operator=(const unordered_set& __u) {
721 __table_ = __u.__table_;
722 return *this;
723 }
724#ifndef _LIBCPP_CXX03_LANG
725 _LIBCPP_HIDE_FROM_ABI unordered_set& operator=(unordered_set&& __u)
726 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
727 _LIBCPP_HIDE_FROM_ABI unordered_set& operator=(initializer_list<value_type> __il);
728#endif // _LIBCPP_CXX03_LANG
729
730 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT {
731 return allocator_type(__table_.__node_alloc());
732 }
733
734 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __table_.size() == 0; }
735 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __table_.size(); }
736 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __table_.max_size(); }
737
738 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __table_.begin(); }
739 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __table_.end(); }
740 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __table_.begin(); }
741 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __table_.end(); }
742 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return __table_.begin(); }
743 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return __table_.end(); }
744
745#ifndef _LIBCPP_CXX03_LANG
746 template <class... _Args>
747 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> emplace(_Args&&... __args) {
748 return __table_.__emplace_unique(std::forward<_Args>(__args)...);
749 }
750 template <class... _Args>
751 _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator, _Args&&... __args) {
752 return __table_.__emplace_unique(std::forward<_Args>(__args)...).first;
753 }
754
755 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(value_type&& __x) {
756 return __table_.__insert_unique(std::move(__x));
757 }
758 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, value_type&& __x) { return insert(std::move(__x)).first; }
759
760 _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); }
761#endif // _LIBCPP_CXX03_LANG
762 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(const value_type& __x) { return __table_.__insert_unique(__x); }
763
764 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, const value_type& __x) { return insert(__x).first; }
765 template <class _InputIterator>
766 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last);
767
768#if _LIBCPP_STD_VER >= 23
769 template <_ContainerCompatibleRange<value_type> _Range>
770 _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) {
771 for (auto&& __element : __range) {
772 __table_.__insert_unique(std::forward<decltype(__element)>(__element));
773 }
774 }
775#endif
776
777 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __table_.erase(__p); }
778 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_unique(__k); }
779 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last) {
780 return __table_.erase(__first, __last);
781 }
782 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __table_.clear(); }
783
784#if _LIBCPP_STD_VER >= 17
785 _LIBCPP_HIDE_FROM_ABI insert_return_type insert(node_type&& __nh) {
786 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
787 "node_type with incompatible allocator passed to unordered_set::insert()");
788 return __table_.template __node_handle_insert_unique< node_type, insert_return_type>(std::move(__nh));
789 }
790 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __h, node_type&& __nh) {
791 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
792 "node_type with incompatible allocator passed to unordered_set::insert()");
793 return __table_.template __node_handle_insert_unique<node_type>(__h, std::move(__nh));
794 }
795 _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) {
796 return __table_.template __node_handle_extract<node_type>(__key);
797 }
798 _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __it) {
799 return __table_.template __node_handle_extract<node_type>(__it);
800 }
801
802 template <class _H2, class _P2>
803 _LIBCPP_HIDE_FROM_ABI void merge(unordered_set<key_type, _H2, _P2, allocator_type>& __source) {
804 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
805 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
806 __table_.__node_handle_merge_unique(__source.__table_);
807 }
808 template <class _H2, class _P2>
809 _LIBCPP_HIDE_FROM_ABI void merge(unordered_set<key_type, _H2, _P2, allocator_type>&& __source) {
810 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
811 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
812 __table_.__node_handle_merge_unique(__source.__table_);
813 }
814 template <class _H2, class _P2>
815 _LIBCPP_HIDE_FROM_ABI void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>& __source) {
816 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
817 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
818 __table_.__node_handle_merge_unique(__source.__table_);
819 }
820 template <class _H2, class _P2>
821 _LIBCPP_HIDE_FROM_ABI void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>&& __source) {
822 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
823 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
824 __table_.__node_handle_merge_unique(__source.__table_);
825 }
826#endif
827
828 _LIBCPP_HIDE_FROM_ABI void swap(unordered_set& __u) _NOEXCEPT_(__is_nothrow_swappable_v<__table>) {
829 __table_.swap(__u.__table_);
830 }
831
832 _LIBCPP_HIDE_FROM_ABI hasher hash_function() const { return __table_.hash_function(); }
833 _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq(); }
834
835 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); }
836 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); }
837#if _LIBCPP_STD_VER >= 20
838 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
839 _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) {
840 return __table_.find(__k);
841 }
842 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
843 _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const {
844 return __table_.find(__k);
845 }
846#endif // _LIBCPP_STD_VER >= 20
847
848 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_unique(__k); }
849#if _LIBCPP_STD_VER >= 20
850 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
851 _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const {
852 return __table_.__count_unique(__k);
853 }
854#endif // _LIBCPP_STD_VER >= 20
855
856#if _LIBCPP_STD_VER >= 20
857 _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); }
858
859 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
860 _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const {
861 return find(__k) != end();
862 }
863#endif // _LIBCPP_STD_VER >= 20
864
865 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {
866 return __table_.__equal_range_unique(__k);
867 }
868 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
869 return __table_.__equal_range_unique(__k);
870 }
871#if _LIBCPP_STD_VER >= 20
872 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
873 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) {
874 return __table_.__equal_range_unique(__k);
875 }
876 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
877 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const {
878 return __table_.__equal_range_unique(__k);
879 }
880#endif // _LIBCPP_STD_VER >= 20
881
882 _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const _NOEXCEPT { return __table_.bucket_count(); }
883 _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const _NOEXCEPT { return __table_.max_bucket_count(); }
884
885 _LIBCPP_HIDE_FROM_ABI size_type bucket_size(size_type __n) const { return __table_.bucket_size(__n); }
886 _LIBCPP_HIDE_FROM_ABI size_type bucket(const key_type& __k) const { return __table_.bucket(__k); }
887
888 _LIBCPP_HIDE_FROM_ABI local_iterator begin(size_type __n) { return __table_.begin(__n); }
889 _LIBCPP_HIDE_FROM_ABI local_iterator end(size_type __n) { return __table_.end(__n); }
890 _LIBCPP_HIDE_FROM_ABI const_local_iterator begin(size_type __n) const { return __table_.cbegin(__n); }
891 _LIBCPP_HIDE_FROM_ABI const_local_iterator end(size_type __n) const { return __table_.cend(__n); }
892 _LIBCPP_HIDE_FROM_ABI const_local_iterator cbegin(size_type __n) const { return __table_.cbegin(__n); }
893 _LIBCPP_HIDE_FROM_ABI const_local_iterator cend(size_type __n) const { return __table_.cend(__n); }
894
895 _LIBCPP_HIDE_FROM_ABI float load_factor() const _NOEXCEPT { return __table_.load_factor(); }
896 _LIBCPP_HIDE_FROM_ABI float max_load_factor() const _NOEXCEPT { return __table_.max_load_factor(); }
897 _LIBCPP_HIDE_FROM_ABI void max_load_factor(float __mlf) { __table_.max_load_factor(__mlf); }
898 _LIBCPP_HIDE_FROM_ABI void rehash(size_type __n) { __table_.__rehash_unique(__n); }
899 _LIBCPP_HIDE_FROM_ABI void reserve(size_type __n) { __table_.__reserve_unique(__n); }
900};
901
902#if _LIBCPP_STD_VER >= 17
903template <class _InputIterator,
904 class _Hash = hash<__iter_value_type<_InputIterator>>,
905 class _Pred = equal_to<__iter_value_type<_InputIterator>>,
906 class _Allocator = allocator<__iter_value_type<_InputIterator>>,
907 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
908 class = enable_if_t<!__is_allocator<_Hash>::value>,
909 class = enable_if_t<!is_integral<_Hash>::value>,
910 class = enable_if_t<!__is_allocator<_Pred>::value>,
911 class = enable_if_t<__is_allocator<_Allocator>::value>>
912unordered_set(_InputIterator,
913 _InputIterator,
914 typename allocator_traits<_Allocator>::size_type = 0,
915 _Hash = _Hash(),
916 _Pred = _Pred(),
917 _Allocator = _Allocator()) -> unordered_set<__iter_value_type<_InputIterator>, _Hash, _Pred, _Allocator>;
918
919# if _LIBCPP_STD_VER >= 23
920template <ranges::input_range _Range,
921 class _Hash = hash<ranges::range_value_t<_Range>>,
922 class _Pred = equal_to<ranges::range_value_t<_Range>>,
923 class _Allocator = allocator<ranges::range_value_t<_Range>>,
924 class = enable_if_t<!__is_allocator<_Hash>::value>,
925 class = enable_if_t<!is_integral<_Hash>::value>,
926 class = enable_if_t<!__is_allocator<_Pred>::value>,
927 class = enable_if_t<__is_allocator<_Allocator>::value>>
928unordered_set(
929 from_range_t,
930 _Range&&,
931 typename allocator_traits<_Allocator>::size_type = 0,
932 _Hash = _Hash(),
933 _Pred = _Pred(),
934 _Allocator = _Allocator()) -> unordered_set<ranges::range_value_t<_Range>, _Hash, _Pred, _Allocator>; // C++23
935# endif
936
937template <class _Tp,
938 class _Hash = hash<_Tp>,
939 class _Pred = equal_to<_Tp>,
940 class _Allocator = allocator<_Tp>,
941 class = enable_if_t<!__is_allocator<_Hash>::value>,
942 class = enable_if_t<!is_integral<_Hash>::value>,
943 class = enable_if_t<!__is_allocator<_Pred>::value>,
944 class = enable_if_t<__is_allocator<_Allocator>::value>>
945unordered_set(initializer_list<_Tp>,
946 typename allocator_traits<_Allocator>::size_type = 0,
947 _Hash = _Hash(),
948 _Pred = _Pred(),
949 _Allocator = _Allocator()) -> unordered_set<_Tp, _Hash, _Pred, _Allocator>;
950
951template <class _InputIterator,
952 class _Allocator,
953 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
954 class = enable_if_t<__is_allocator<_Allocator>::value>>
955unordered_set(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Allocator)
956 -> unordered_set<__iter_value_type<_InputIterator>,
957 hash<__iter_value_type<_InputIterator>>,
958 equal_to<__iter_value_type<_InputIterator>>,
959 _Allocator>;
960
961template <class _InputIterator,
962 class _Hash,
963 class _Allocator,
964 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
965 class = enable_if_t<!__is_allocator<_Hash>::value>,
966 class = enable_if_t<!is_integral<_Hash>::value>,
967 class = enable_if_t<__is_allocator<_Allocator>::value>>
968unordered_set(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
969 -> unordered_set<__iter_value_type<_InputIterator>, _Hash, equal_to<__iter_value_type<_InputIterator>>, _Allocator>;
970
971# if _LIBCPP_STD_VER >= 23
972
973template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
974unordered_set(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Allocator)
975 -> unordered_set<ranges::range_value_t<_Range>,
976 hash<ranges::range_value_t<_Range>>,
977 equal_to<ranges::range_value_t<_Range>>,
978 _Allocator>;
979
980template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
981unordered_set(from_range_t, _Range&&, _Allocator)
982 -> unordered_set<ranges::range_value_t<_Range>,
983 hash<ranges::range_value_t<_Range>>,
984 equal_to<ranges::range_value_t<_Range>>,
985 _Allocator>;
986
987template <ranges::input_range _Range,
988 class _Hash,
989 class _Allocator,
990 class = enable_if_t<!__is_allocator<_Hash>::value>,
991 class = enable_if_t<!is_integral<_Hash>::value>,
992 class = enable_if_t<__is_allocator<_Allocator>::value>>
993unordered_set(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
994 -> unordered_set<ranges::range_value_t<_Range>, _Hash, equal_to<ranges::range_value_t<_Range>>, _Allocator>;
995
996# endif
997
998template <class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
999unordered_set(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Allocator)
1000 -> unordered_set<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
1001
1002template <class _Tp,
1003 class _Hash,
1004 class _Allocator,
1005 class = enable_if_t<!__is_allocator<_Hash>::value>,
1006 class = enable_if_t<!is_integral<_Hash>::value>,
1007 class = enable_if_t<__is_allocator<_Allocator>::value>>
1008unordered_set(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
1009 -> unordered_set<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
1010#endif
1011
1012template <class _Value, class _Hash, class _Pred, class _Alloc>
1013unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n, const hasher& __hf, const key_equal& __eql)
1014 : __table_(__hf, __eql) {
1015 __table_.__rehash_unique(__n);
1016}
1017
1018template <class _Value, class _Hash, class _Pred, class _Alloc>
1019unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
1020 size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1021 : __table_(__hf, __eql, __a) {
1022 __table_.__rehash_unique(__n);
1023}
1024
1025template <class _Value, class _Hash, class _Pred, class _Alloc>
1026template <class _InputIterator>
1027unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(_InputIterator __first, _InputIterator __last) {
1028 insert(__first, __last);
1029}
1030
1031template <class _Value, class _Hash, class _Pred, class _Alloc>
1032template <class _InputIterator>
1033unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
1034 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql)
1035 : __table_(__hf, __eql) {
1036 __table_.__rehash_unique(__n);
1037 insert(__first, __last);
1038}
1039
1040template <class _Value, class _Hash, class _Pred, class _Alloc>
1041template <class _InputIterator>
1042unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
1043 _InputIterator __first,
1044 _InputIterator __last,
1045 size_type __n,
1046 const hasher& __hf,
1047 const key_equal& __eql,
1048 const allocator_type& __a)
1049 : __table_(__hf, __eql, __a) {
1050 __table_.__rehash_unique(__n);
1051 insert(__first, __last);
1052}
1053
1054template <class _Value, class _Hash, class _Pred, class _Alloc>
1055inline unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(const allocator_type& __a) : __table_(__a) {}
1056
1057template <class _Value, class _Hash, class _Pred, class _Alloc>
1058unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(const unordered_set& __u) : __table_(__u.__table_) {
1059 __table_.__rehash_unique(__u.bucket_count());
1060 insert(__u.begin(), __u.end());
1061}
1062
1063template <class _Value, class _Hash, class _Pred, class _Alloc>
1064unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(const unordered_set& __u, const allocator_type& __a)
1065 : __table_(__u.__table_, __a) {
1066 __table_.__rehash_unique(__u.bucket_count());
1067 insert(__u.begin(), __u.end());
1068}
1069
1070#ifndef _LIBCPP_CXX03_LANG
1071
1072template <class _Value, class _Hash, class _Pred, class _Alloc>
1073inline unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(unordered_set&& __u)
1074 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
1075 : __table_(std::move(__u.__table_)) {}
1076
1077template <class _Value, class _Hash, class _Pred, class _Alloc>
1078unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(unordered_set&& __u, const allocator_type& __a)
1079 : __table_(std::move(__u.__table_), __a) {
1080 if (__a != __u.get_allocator()) {
1081 iterator __i = __u.begin();
1082 while (__u.size() != 0)
1083 __table_.__insert_unique(std::move(__u.__table_.remove(__i++)->__get_value()));
1084 }
1085}
1086
1087template <class _Value, class _Hash, class _Pred, class _Alloc>
1088unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(initializer_list<value_type> __il) {
1089 insert(__il.begin(), __il.end());
1090}
1091
1092template <class _Value, class _Hash, class _Pred, class _Alloc>
1093unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
1094 initializer_list<value_type> __il, size_type __n, const hasher& __hf, const key_equal& __eql)
1095 : __table_(__hf, __eql) {
1096 __table_.__rehash_unique(__n);
1097 insert(__il.begin(), __il.end());
1098}
1099
1100template <class _Value, class _Hash, class _Pred, class _Alloc>
1101unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
1102 initializer_list<value_type> __il,
1103 size_type __n,
1104 const hasher& __hf,
1105 const key_equal& __eql,
1106 const allocator_type& __a)
1107 : __table_(__hf, __eql, __a) {
1108 __table_.__rehash_unique(__n);
1109 insert(__il.begin(), __il.end());
1110}
1111
1112template <class _Value, class _Hash, class _Pred, class _Alloc>
1113inline unordered_set<_Value, _Hash, _Pred, _Alloc>&
1114unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(unordered_set&& __u)
1115 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) {
1116 __table_ = std::move(__u.__table_);
1117 return *this;
1118}
1119
1120template <class _Value, class _Hash, class _Pred, class _Alloc>
1121inline unordered_set<_Value, _Hash, _Pred, _Alloc>&
1122unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(initializer_list<value_type> __il) {
1123 __table_.__assign_unique(__il.begin(), __il.end());
1124 return *this;
1125}
1126
1127#endif // _LIBCPP_CXX03_LANG
1128
1129template <class _Value, class _Hash, class _Pred, class _Alloc>
1130template <class _InputIterator>
1131inline void unordered_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) {
1132 for (; __first != __last; ++__first)
1133 __table_.__insert_unique(*__first);
1134}
1135
1136template <class _Value, class _Hash, class _Pred, class _Alloc>
1137inline _LIBCPP_HIDE_FROM_ABI void
1138swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
1139 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
1140 __x.swap(__y);
1141}
1142
1143#if _LIBCPP_STD_VER >= 20
1144template <class _Value, class _Hash, class _Pred, class _Alloc, class _Predicate>
1145inline _LIBCPP_HIDE_FROM_ABI typename unordered_set<_Value, _Hash, _Pred, _Alloc>::size_type
1146erase_if(unordered_set<_Value, _Hash, _Pred, _Alloc>& __c, _Predicate __pred) {
1147 return std::__libcpp_erase_if_container(__c, __pred);
1148}
1149#endif
1150
1151template <class _Value, class _Hash, class _Pred, class _Alloc>
1152_LIBCPP_HIDE_FROM_ABI bool operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
1153 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) {
1154 if (__x.size() != __y.size())
1155 return false;
1156 typedef typename unordered_set<_Value, _Hash, _Pred, _Alloc>::const_iterator const_iterator;
1157 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); __i != __ex; ++__i) {
1158 const_iterator __j = __y.find(*__i);
1159 if (__j == __ey || !(*__i == *__j))
1160 return false;
1161 }
1162 return true;
1163}
1164
1165#if _LIBCPP_STD_VER <= 17
1166
1167template <class _Value, class _Hash, class _Pred, class _Alloc>
1168inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
1169 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) {
1170 return !(__x == __y);
1171}
1172
1173#endif
1174
1175template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, class _Alloc = allocator<_Value> >
1176class _LIBCPP_TEMPLATE_VIS unordered_multiset {
1177public:
1178 // types
1179 typedef _Value key_type;
1180 typedef key_type value_type;
1181 typedef __type_identity_t<_Hash> hasher;
1182 typedef __type_identity_t<_Pred> key_equal;
1183 typedef __type_identity_t<_Alloc> allocator_type;
1184 typedef value_type& reference;
1185 typedef const value_type& const_reference;
1186 static_assert(is_same<value_type, typename allocator_type::value_type>::value,
1187 "Allocator::value_type must be same type as value_type");
1188
1189private:
1190 typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
1191
1192 __table __table_;
1193
1194public:
1195 typedef typename __table::pointer pointer;
1196 typedef typename __table::const_pointer const_pointer;
1197 typedef typename __table::size_type size_type;
1198 typedef typename __table::difference_type difference_type;
1199
1200 typedef typename __table::const_iterator iterator;
1201 typedef typename __table::const_iterator const_iterator;
1202 typedef typename __table::const_local_iterator local_iterator;
1203 typedef typename __table::const_local_iterator const_local_iterator;
1204
1205#if _LIBCPP_STD_VER >= 17
1206 typedef __set_node_handle<typename __table::__node, allocator_type> node_type;
1207#endif
1208
1209 template <class _Value2, class _Hash2, class _Pred2, class _Alloc2>
1210 friend class _LIBCPP_TEMPLATE_VIS unordered_set;
1211 template <class _Value2, class _Hash2, class _Pred2, class _Alloc2>
1212 friend class _LIBCPP_TEMPLATE_VIS unordered_multiset;
1213
1214 _LIBCPP_HIDE_FROM_ABI unordered_multiset() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) {}
1215 explicit _LIBCPP_HIDE_FROM_ABI
1216 unordered_multiset(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
1217 _LIBCPP_HIDE_FROM_ABI
1218 unordered_multiset(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a);
1219#if _LIBCPP_STD_VER >= 14
1220 inline _LIBCPP_HIDE_FROM_ABI unordered_multiset(size_type __n, const allocator_type& __a)
1221 : unordered_multiset(__n, hasher(), key_equal(), __a) {}
1222 inline _LIBCPP_HIDE_FROM_ABI unordered_multiset(size_type __n, const hasher& __hf, const allocator_type& __a)
1223 : unordered_multiset(__n, __hf, key_equal(), __a) {}
1224#endif
1225 template <class _InputIterator>
1226 _LIBCPP_HIDE_FROM_ABI unordered_multiset(_InputIterator __first, _InputIterator __last);
1227 template <class _InputIterator>
1228 _LIBCPP_HIDE_FROM_ABI unordered_multiset(
1229 _InputIterator __first,
1230 _InputIterator __last,
1231 size_type __n,
1232 const hasher& __hf = hasher(),
1233 const key_equal& __eql = key_equal());
1234 template <class _InputIterator>
1235 _LIBCPP_HIDE_FROM_ABI unordered_multiset(
1236 _InputIterator __first,
1237 _InputIterator __last,
1238 size_type __n,
1239 const hasher& __hf,
1240 const key_equal& __eql,
1241 const allocator_type& __a);
1242
1243#if _LIBCPP_STD_VER >= 23
1244 template <_ContainerCompatibleRange<value_type> _Range>
1245 _LIBCPP_HIDE_FROM_ABI unordered_multiset(
1246 from_range_t,
1247 _Range&& __range,
1248 size_type __n = /*implementation-defined*/ 0,
1249 const hasher& __hf = hasher(),
1250 const key_equal& __eql = key_equal(),
1251 const allocator_type& __a = allocator_type())
1252 : __table_(__hf, __eql, __a) {
1253 if (__n > 0) {
1254 __table_.__rehash_multi(__n);
1255 }
1256 insert_range(std::forward<_Range>(__range));
1257 }
1258#endif
1259
1260#if _LIBCPP_STD_VER >= 14
1261 template <class _InputIterator>
1262 inline _LIBCPP_HIDE_FROM_ABI
1263 unordered_multiset(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a)
1264 : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a) {}
1265 template <class _InputIterator>
1266 inline _LIBCPP_HIDE_FROM_ABI unordered_multiset(
1267 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const allocator_type& __a)
1268 : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a) {}
1269#endif
1270
1271#if _LIBCPP_STD_VER >= 23
1272 template <_ContainerCompatibleRange<value_type> _Range>
1273 _LIBCPP_HIDE_FROM_ABI unordered_multiset(from_range_t, _Range&& __range, size_type __n, const allocator_type& __a)
1274 : unordered_multiset(from_range, std::forward<_Range>(__range), __n, hasher(), key_equal(), __a) {}
1275
1276 template <_ContainerCompatibleRange<value_type> _Range>
1277 _LIBCPP_HIDE_FROM_ABI
1278 unordered_multiset(from_range_t, _Range&& __range, size_type __n, const hasher& __hf, const allocator_type& __a)
1279 : unordered_multiset(from_range, std::forward<_Range>(__range), __n, __hf, key_equal(), __a) {}
1280#endif
1281
1282 _LIBCPP_HIDE_FROM_ABI explicit unordered_multiset(const allocator_type& __a);
1283 _LIBCPP_HIDE_FROM_ABI unordered_multiset(const unordered_multiset& __u);
1284 _LIBCPP_HIDE_FROM_ABI unordered_multiset(const unordered_multiset& __u, const allocator_type& __a);
1285#ifndef _LIBCPP_CXX03_LANG
1286 _LIBCPP_HIDE_FROM_ABI unordered_multiset(unordered_multiset&& __u)
1287 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
1288 _LIBCPP_HIDE_FROM_ABI unordered_multiset(unordered_multiset&& __u, const allocator_type& __a);
1289 _LIBCPP_HIDE_FROM_ABI unordered_multiset(initializer_list<value_type> __il);
1290 _LIBCPP_HIDE_FROM_ABI unordered_multiset(
1291 initializer_list<value_type> __il,
1292 size_type __n,
1293 const hasher& __hf = hasher(),
1294 const key_equal& __eql = key_equal());
1295 _LIBCPP_HIDE_FROM_ABI unordered_multiset(
1296 initializer_list<value_type> __il,
1297 size_type __n,
1298 const hasher& __hf,
1299 const key_equal& __eql,
1300 const allocator_type& __a);
1301# if _LIBCPP_STD_VER >= 14
1302 inline _LIBCPP_HIDE_FROM_ABI
1303 unordered_multiset(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)
1304 : unordered_multiset(__il, __n, hasher(), key_equal(), __a) {}
1305 inline _LIBCPP_HIDE_FROM_ABI
1306 unordered_multiset(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a)
1307 : unordered_multiset(__il, __n, __hf, key_equal(), __a) {}
1308# endif
1309#endif // _LIBCPP_CXX03_LANG
1310 _LIBCPP_HIDE_FROM_ABI ~unordered_multiset() {
1311 static_assert(sizeof(std::__diagnose_unordered_container_requirements<_Value, _Hash, _Pred>(0)), "");
1312 }
1313
1314 _LIBCPP_HIDE_FROM_ABI unordered_multiset& operator=(const unordered_multiset& __u) {
1315 __table_ = __u.__table_;
1316 return *this;
1317 }
1318#ifndef _LIBCPP_CXX03_LANG
1319 _LIBCPP_HIDE_FROM_ABI unordered_multiset& operator=(unordered_multiset&& __u)
1320 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
1321 _LIBCPP_HIDE_FROM_ABI unordered_multiset& operator=(initializer_list<value_type> __il);
1322#endif // _LIBCPP_CXX03_LANG
1323
1324 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT {
1325 return allocator_type(__table_.__node_alloc());
1326 }
1327
1328 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __table_.size() == 0; }
1329 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __table_.size(); }
1330 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __table_.max_size(); }
1331
1332 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __table_.begin(); }
1333 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __table_.end(); }
1334 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __table_.begin(); }
1335 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __table_.end(); }
1336 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return __table_.begin(); }
1337 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return __table_.end(); }
1338
1339#ifndef _LIBCPP_CXX03_LANG
1340 template <class... _Args>
1341 _LIBCPP_HIDE_FROM_ABI iterator emplace(_Args&&... __args) {
1342 return __table_.__emplace_multi(std::forward<_Args>(__args)...);
1343 }
1344 template <class... _Args>
1345 _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __p, _Args&&... __args) {
1346 return __table_.__emplace_hint_multi(__p, std::forward<_Args>(__args)...);
1347 }
1348
1349 _LIBCPP_HIDE_FROM_ABI iterator insert(value_type&& __x) { return __table_.__insert_multi(std::move(__x)); }
1350 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __x) {
1351 return __table_.__insert_multi(__p, std::move(__x));
1352 }
1353 _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); }
1354#endif // _LIBCPP_CXX03_LANG
1355
1356 _LIBCPP_HIDE_FROM_ABI iterator insert(const value_type& __x) { return __table_.__insert_multi(__x); }
1357
1358 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __x) {
1359 return __table_.__insert_multi(__p, __x);
1360 }
1361
1362 template <class _InputIterator>
1363 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last);
1364
1365#if _LIBCPP_STD_VER >= 23
1366 template <_ContainerCompatibleRange<value_type> _Range>
1367 _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) {
1368 for (auto&& __element : __range) {
1369 __table_.__insert_multi(std::forward<decltype(__element)>(__element));
1370 }
1371 }
1372#endif
1373
1374#if _LIBCPP_STD_VER >= 17
1375 _LIBCPP_HIDE_FROM_ABI iterator insert(node_type&& __nh) {
1376 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
1377 "node_type with incompatible allocator passed to unordered_multiset::insert()");
1378 return __table_.template __node_handle_insert_multi<node_type>(std::move(__nh));
1379 }
1380 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, node_type&& __nh) {
1381 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
1382 "node_type with incompatible allocator passed to unordered_multiset::insert()");
1383 return __table_.template __node_handle_insert_multi<node_type>(__hint, std::move(__nh));
1384 }
1385 _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __position) {
1386 return __table_.template __node_handle_extract<node_type>(__position);
1387 }
1388 _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) {
1389 return __table_.template __node_handle_extract<node_type>(__key);
1390 }
1391
1392 template <class _H2, class _P2>
1393 _LIBCPP_HIDE_FROM_ABI void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>& __source) {
1394 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1395 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1396 return __table_.__node_handle_merge_multi(__source.__table_);
1397 }
1398 template <class _H2, class _P2>
1399 _LIBCPP_HIDE_FROM_ABI void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>&& __source) {
1400 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1401 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1402 return __table_.__node_handle_merge_multi(__source.__table_);
1403 }
1404 template <class _H2, class _P2>
1405 _LIBCPP_HIDE_FROM_ABI void merge(unordered_set<key_type, _H2, _P2, allocator_type>& __source) {
1406 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1407 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1408 return __table_.__node_handle_merge_multi(__source.__table_);
1409 }
1410 template <class _H2, class _P2>
1411 _LIBCPP_HIDE_FROM_ABI void merge(unordered_set<key_type, _H2, _P2, allocator_type>&& __source) {
1412 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1413 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1414 return __table_.__node_handle_merge_multi(__source.__table_);
1415 }
1416#endif
1417
1418 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __table_.erase(__p); }
1419 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_multi(__k); }
1420 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last) {
1421 return __table_.erase(__first, __last);
1422 }
1423 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __table_.clear(); }
1424
1425 _LIBCPP_HIDE_FROM_ABI void swap(unordered_multiset& __u) _NOEXCEPT_(__is_nothrow_swappable_v<__table>) {
1426 __table_.swap(__u.__table_);
1427 }
1428
1429 _LIBCPP_HIDE_FROM_ABI hasher hash_function() const { return __table_.hash_function(); }
1430 _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq(); }
1431
1432 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); }
1433 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); }
1434#if _LIBCPP_STD_VER >= 20
1435 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
1436 _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) {
1437 return __table_.find(__k);
1438 }
1439 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
1440 _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const {
1441 return __table_.find(__k);
1442 }
1443#endif // _LIBCPP_STD_VER >= 20
1444
1445 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_multi(__k); }
1446#if _LIBCPP_STD_VER >= 20
1447 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
1448 _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const {
1449 return __table_.__count_multi(__k);
1450 }
1451#endif // _LIBCPP_STD_VER >= 20
1452
1453#if _LIBCPP_STD_VER >= 20
1454 _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); }
1455
1456 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
1457 _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const {
1458 return find(__k) != end();
1459 }
1460#endif // _LIBCPP_STD_VER >= 20
1461
1462 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {
1463 return __table_.__equal_range_multi(__k);
1464 }
1465 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
1466 return __table_.__equal_range_multi(__k);
1467 }
1468#if _LIBCPP_STD_VER >= 20
1469 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
1470 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) {
1471 return __table_.__equal_range_multi(__k);
1472 }
1473 template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>
1474 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const {
1475 return __table_.__equal_range_multi(__k);
1476 }
1477#endif // _LIBCPP_STD_VER >= 20
1478
1479 _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const _NOEXCEPT { return __table_.bucket_count(); }
1480 _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const _NOEXCEPT { return __table_.max_bucket_count(); }
1481
1482 _LIBCPP_HIDE_FROM_ABI size_type bucket_size(size_type __n) const { return __table_.bucket_size(__n); }
1483 _LIBCPP_HIDE_FROM_ABI size_type bucket(const key_type& __k) const { return __table_.bucket(__k); }
1484
1485 _LIBCPP_HIDE_FROM_ABI local_iterator begin(size_type __n) { return __table_.begin(__n); }
1486 _LIBCPP_HIDE_FROM_ABI local_iterator end(size_type __n) { return __table_.end(__n); }
1487 _LIBCPP_HIDE_FROM_ABI const_local_iterator begin(size_type __n) const { return __table_.cbegin(__n); }
1488 _LIBCPP_HIDE_FROM_ABI const_local_iterator end(size_type __n) const { return __table_.cend(__n); }
1489 _LIBCPP_HIDE_FROM_ABI const_local_iterator cbegin(size_type __n) const { return __table_.cbegin(__n); }
1490 _LIBCPP_HIDE_FROM_ABI const_local_iterator cend(size_type __n) const { return __table_.cend(__n); }
1491
1492 _LIBCPP_HIDE_FROM_ABI float load_factor() const _NOEXCEPT { return __table_.load_factor(); }
1493 _LIBCPP_HIDE_FROM_ABI float max_load_factor() const _NOEXCEPT { return __table_.max_load_factor(); }
1494 _LIBCPP_HIDE_FROM_ABI void max_load_factor(float __mlf) { __table_.max_load_factor(__mlf); }
1495 _LIBCPP_HIDE_FROM_ABI void rehash(size_type __n) { __table_.__rehash_multi(__n); }
1496 _LIBCPP_HIDE_FROM_ABI void reserve(size_type __n) { __table_.__reserve_multi(__n); }
1497};
1498
1499#if _LIBCPP_STD_VER >= 17
1500template <class _InputIterator,
1501 class _Hash = hash<__iter_value_type<_InputIterator>>,
1502 class _Pred = equal_to<__iter_value_type<_InputIterator>>,
1503 class _Allocator = allocator<__iter_value_type<_InputIterator>>,
1504 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
1505 class = enable_if_t<!__is_allocator<_Hash>::value>,
1506 class = enable_if_t<!is_integral<_Hash>::value>,
1507 class = enable_if_t<!__is_allocator<_Pred>::value>,
1508 class = enable_if_t<__is_allocator<_Allocator>::value>>
1509unordered_multiset(
1510 _InputIterator,
1511 _InputIterator,
1512 typename allocator_traits<_Allocator>::size_type = 0,
1513 _Hash = _Hash(),
1514 _Pred = _Pred(),
1515 _Allocator = _Allocator()) -> unordered_multiset<__iter_value_type<_InputIterator>, _Hash, _Pred, _Allocator>;
1516
1517# if _LIBCPP_STD_VER >= 23
1518template <ranges::input_range _Range,
1519 class _Hash = hash<ranges::range_value_t<_Range>>,
1520 class _Pred = equal_to<ranges::range_value_t<_Range>>,
1521 class _Allocator = allocator<ranges::range_value_t<_Range>>,
1522 class = enable_if_t<!__is_allocator<_Hash>::value>,
1523 class = enable_if_t<!is_integral<_Hash>::value>,
1524 class = enable_if_t<!__is_allocator<_Pred>::value>,
1525 class = enable_if_t<__is_allocator<_Allocator>::value>>
1526unordered_multiset(
1527 from_range_t,
1528 _Range&&,
1529 typename allocator_traits<_Allocator>::size_type = 0,
1530 _Hash = _Hash(),
1531 _Pred = _Pred(),
1532 _Allocator = _Allocator()) -> unordered_multiset<ranges::range_value_t<_Range>, _Hash, _Pred, _Allocator>; // C++23
1533# endif
1534
1535template <class _Tp,
1536 class _Hash = hash<_Tp>,
1537 class _Pred = equal_to<_Tp>,
1538 class _Allocator = allocator<_Tp>,
1539 class = enable_if_t<!__is_allocator<_Hash>::value>,
1540 class = enable_if_t<!is_integral<_Hash>::value>,
1541 class = enable_if_t<!__is_allocator<_Pred>::value>,
1542 class = enable_if_t<__is_allocator<_Allocator>::value>>
1543unordered_multiset(initializer_list<_Tp>,
1544 typename allocator_traits<_Allocator>::size_type = 0,
1545 _Hash = _Hash(),
1546 _Pred = _Pred(),
1547 _Allocator = _Allocator()) -> unordered_multiset<_Tp, _Hash, _Pred, _Allocator>;
1548
1549template <class _InputIterator,
1550 class _Allocator,
1551 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
1552 class = enable_if_t<__is_allocator<_Allocator>::value>>
1553unordered_multiset(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Allocator)
1554 -> unordered_multiset<__iter_value_type<_InputIterator>,
1555 hash<__iter_value_type<_InputIterator>>,
1556 equal_to<__iter_value_type<_InputIterator>>,
1557 _Allocator>;
1558
1559template <class _InputIterator,
1560 class _Hash,
1561 class _Allocator,
1562 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
1563 class = enable_if_t<!__is_allocator<_Hash>::value>,
1564 class = enable_if_t<!is_integral<_Hash>::value>,
1565 class = enable_if_t<__is_allocator<_Allocator>::value>>
1566unordered_multiset(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
1567 -> unordered_multiset<__iter_value_type<_InputIterator>,
1568 _Hash,
1569 equal_to<__iter_value_type<_InputIterator>>,
1570 _Allocator>;
1571
1572# if _LIBCPP_STD_VER >= 23
1573
1574template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
1575unordered_multiset(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Allocator)
1576 -> unordered_multiset<ranges::range_value_t<_Range>,
1577 hash<ranges::range_value_t<_Range>>,
1578 equal_to<ranges::range_value_t<_Range>>,
1579 _Allocator>;
1580
1581template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
1582unordered_multiset(from_range_t, _Range&&, _Allocator)
1583 -> unordered_multiset<ranges::range_value_t<_Range>,
1584 hash<ranges::range_value_t<_Range>>,
1585 equal_to<ranges::range_value_t<_Range>>,
1586 _Allocator>;
1587
1588template <ranges::input_range _Range,
1589 class _Hash,
1590 class _Allocator,
1591 class = enable_if_t<!__is_allocator<_Hash>::value>,
1592 class = enable_if_t<!is_integral<_Hash>::value>,
1593 class = enable_if_t<__is_allocator<_Allocator>::value>>
1594unordered_multiset(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
1595 -> unordered_multiset<ranges::range_value_t<_Range>, _Hash, equal_to<ranges::range_value_t<_Range>>, _Allocator>;
1596
1597# endif
1598
1599template <class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
1600unordered_multiset(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Allocator)
1601 -> unordered_multiset<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
1602
1603template <class _Tp,
1604 class _Hash,
1605 class _Allocator,
1606 class = enable_if_t<!__is_allocator<_Hash>::value>,
1607 class = enable_if_t<!is_integral<_Hash>::value>,
1608 class = enable_if_t<__is_allocator<_Allocator>::value>>
1609unordered_multiset(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
1610 -> unordered_multiset<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
1611#endif
1612
1613template <class _Value, class _Hash, class _Pred, class _Alloc>
1614unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1615 size_type __n, const hasher& __hf, const key_equal& __eql)
1616 : __table_(__hf, __eql) {
1617 __table_.__rehash_multi(__n);
1618}
1619
1620template <class _Value, class _Hash, class _Pred, class _Alloc>
1621unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1622 size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1623 : __table_(__hf, __eql, __a) {
1624 __table_.__rehash_multi(__n);
1625}
1626
1627template <class _Value, class _Hash, class _Pred, class _Alloc>
1628template <class _InputIterator>
1629unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(_InputIterator __first, _InputIterator __last) {
1630 insert(__first, __last);
1631}
1632
1633template <class _Value, class _Hash, class _Pred, class _Alloc>
1634template <class _InputIterator>
1635unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1636 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql)
1637 : __table_(__hf, __eql) {
1638 __table_.__rehash_multi(__n);
1639 insert(__first, __last);
1640}
1641
1642template <class _Value, class _Hash, class _Pred, class _Alloc>
1643template <class _InputIterator>
1644unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1645 _InputIterator __first,
1646 _InputIterator __last,
1647 size_type __n,
1648 const hasher& __hf,
1649 const key_equal& __eql,
1650 const allocator_type& __a)
1651 : __table_(__hf, __eql, __a) {
1652 __table_.__rehash_multi(__n);
1653 insert(__first, __last);
1654}
1655
1656template <class _Value, class _Hash, class _Pred, class _Alloc>
1657inline unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(const allocator_type& __a)
1658 : __table_(__a) {}
1659
1660template <class _Value, class _Hash, class _Pred, class _Alloc>
1661unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(const unordered_multiset& __u)
1662 : __table_(__u.__table_) {
1663 __table_.__rehash_multi(__u.bucket_count());
1664 insert(__u.begin(), __u.end());
1665}
1666
1667template <class _Value, class _Hash, class _Pred, class _Alloc>
1668unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1669 const unordered_multiset& __u, const allocator_type& __a)
1670 : __table_(__u.__table_, __a) {
1671 __table_.__rehash_multi(__u.bucket_count());
1672 insert(__u.begin(), __u.end());
1673}
1674
1675#ifndef _LIBCPP_CXX03_LANG
1676
1677template <class _Value, class _Hash, class _Pred, class _Alloc>
1678inline unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(unordered_multiset&& __u)
1679 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
1680 : __table_(std::move(__u.__table_)) {}
1681
1682template <class _Value, class _Hash, class _Pred, class _Alloc>
1683unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1684 unordered_multiset&& __u, const allocator_type& __a)
1685 : __table_(std::move(__u.__table_), __a) {
1686 if (__a != __u.get_allocator()) {
1687 iterator __i = __u.begin();
1688 while (__u.size() != 0)
1689 __table_.__insert_multi(std::move(__u.__table_.remove(__i++)->__get_value()));
1690 }
1691}
1692
1693template <class _Value, class _Hash, class _Pred, class _Alloc>
1694unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(initializer_list<value_type> __il) {
1695 insert(__il.begin(), __il.end());
1696}
1697
1698template <class _Value, class _Hash, class _Pred, class _Alloc>
1699unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1700 initializer_list<value_type> __il, size_type __n, const hasher& __hf, const key_equal& __eql)
1701 : __table_(__hf, __eql) {
1702 __table_.__rehash_multi(__n);
1703 insert(__il.begin(), __il.end());
1704}
1705
1706template <class _Value, class _Hash, class _Pred, class _Alloc>
1707unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1708 initializer_list<value_type> __il,
1709 size_type __n,
1710 const hasher& __hf,
1711 const key_equal& __eql,
1712 const allocator_type& __a)
1713 : __table_(__hf, __eql, __a) {
1714 __table_.__rehash_multi(__n);
1715 insert(__il.begin(), __il.end());
1716}
1717
1718template <class _Value, class _Hash, class _Pred, class _Alloc>
1719inline unordered_multiset<_Value, _Hash, _Pred, _Alloc>&
1720unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(unordered_multiset&& __u)
1721 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) {
1722 __table_ = std::move(__u.__table_);
1723 return *this;
1724}
1725
1726template <class _Value, class _Hash, class _Pred, class _Alloc>
1727inline unordered_multiset<_Value, _Hash, _Pred, _Alloc>&
1728unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(initializer_list<value_type> __il) {
1729 __table_.__assign_multi(__il.begin(), __il.end());
1730 return *this;
1731}
1732
1733#endif // _LIBCPP_CXX03_LANG
1734
1735template <class _Value, class _Hash, class _Pred, class _Alloc>
1736template <class _InputIterator>
1737inline void unordered_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) {
1738 for (; __first != __last; ++__first)
1739 __table_.__insert_multi(*__first);
1740}
1741
1742template <class _Value, class _Hash, class _Pred, class _Alloc>
1743inline _LIBCPP_HIDE_FROM_ABI void
1744swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1745 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
1746 __x.swap(__y);
1747}
1748
1749#if _LIBCPP_STD_VER >= 20
1750template <class _Value, class _Hash, class _Pred, class _Alloc, class _Predicate>
1751inline _LIBCPP_HIDE_FROM_ABI typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::size_type
1752erase_if(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __c, _Predicate __pred) {
1753 return std::__libcpp_erase_if_container(__c, __pred);
1754}
1755#endif
1756
1757template <class _Value, class _Hash, class _Pred, class _Alloc>
1758_LIBCPP_HIDE_FROM_ABI bool operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1759 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) {
1760 if (__x.size() != __y.size())
1761 return false;
1762 typedef typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator const_iterator;
1763 typedef pair<const_iterator, const_iterator> _EqRng;
1764 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) {
1765 _EqRng __xeq = __x.equal_range(*__i);
1766 _EqRng __yeq = __y.equal_range(*__i);
1767 if (std::distance(__xeq.first, __xeq.second) != std::distance(__yeq.first, __yeq.second) ||
1768 !std::is_permutation(__xeq.first, __xeq.second, __yeq.first))
1769 return false;
1770 __i = __xeq.second;
1771 }
1772 return true;
1773}
1774
1775#if _LIBCPP_STD_VER <= 17
1776
1777template <class _Value, class _Hash, class _Pred, class _Alloc>
1778inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1779 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) {
1780 return !(__x == __y);
1781}
1782
1783#endif
1784
1785_LIBCPP_END_NAMESPACE_STD
1786
1787#if _LIBCPP_STD_VER >= 17
1788_LIBCPP_BEGIN_NAMESPACE_STD
1789namespace pmr {
1790template <class _KeyT, class _HashT = std::hash<_KeyT>, class _PredT = std::equal_to<_KeyT>>
1791using unordered_set _LIBCPP_AVAILABILITY_PMR = std::unordered_set<_KeyT, _HashT, _PredT, polymorphic_allocator<_KeyT>>;
1792
1793template <class _KeyT, class _HashT = std::hash<_KeyT>, class _PredT = std::equal_to<_KeyT>>
1794using unordered_multiset _LIBCPP_AVAILABILITY_PMR =
1795 std::unordered_multiset<_KeyT, _HashT, _PredT, polymorphic_allocator<_KeyT>>;
1796} // namespace pmr
1797_LIBCPP_END_NAMESPACE_STD
1798#endif
1799
1800_LIBCPP_POP_MACROS
1801
1802#if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
1803# include <concepts>
1804# include <cstdlib>
1805# include <functional>
1806# include <iterator>
1807# include <stdexcept>
1808# include <type_traits>
1809#endif
1810
1811#endif // _LIBCPP_UNORDERED_SET
1812