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_HASH_SET
11#define _LIBCPP_HASH_SET
12
13/*
14
15 hash_set synopsis
16
17namespace __gnu_cxx
18{
19
20template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,
21 class Alloc = allocator<Value>>
22class hash_set
23{
24public:
25 // types
26 typedef Value key_type;
27 typedef key_type value_type;
28 typedef Hash hasher;
29 typedef Pred key_equal;
30 typedef Alloc allocator_type;
31 typedef value_type& reference;
32 typedef const value_type& const_reference;
33 typedef typename allocator_traits<allocator_type>::pointer pointer;
34 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
35 typedef typename allocator_traits<allocator_type>::size_type size_type;
36 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
37
38 typedef /unspecified/ iterator;
39 typedef /unspecified/ const_iterator;
40
41 explicit hash_set(size_type n = 193, const hasher& hf = hasher(),
42 const key_equal& eql = key_equal(),
43 const allocator_type& a = allocator_type());
44 template <class InputIterator>
45 hash_set(InputIterator f, InputIterator l,
46 size_type n = 193, const hasher& hf = hasher(),
47 const key_equal& eql = key_equal(),
48 const allocator_type& a = allocator_type());
49 hash_set(const hash_set&);
50 ~hash_set();
51 hash_set& operator=(const hash_set&);
52
53 allocator_type get_allocator() const;
54
55 bool empty() const;
56 size_type size() const;
57 size_type max_size() const;
58
59 iterator begin();
60 iterator end();
61 const_iterator begin() const;
62 const_iterator end() const;
63
64 pair<iterator, bool> insert(const value_type& obj);
65 template <class InputIterator>
66 void insert(InputIterator first, InputIterator last);
67
68 void erase(const_iterator position);
69 size_type erase(const key_type& k);
70 void erase(const_iterator first, const_iterator last);
71 void clear();
72
73 void swap(hash_set&);
74
75 hasher hash_funct() const;
76 key_equal key_eq() const;
77
78 iterator find(const key_type& k);
79 const_iterator find(const key_type& k) const;
80 size_type count(const key_type& k) const;
81 pair<iterator, iterator> equal_range(const key_type& k);
82 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
83
84 size_type bucket_count() const;
85 size_type max_bucket_count() const;
86
87 size_type elems_in_bucket(size_type n) const;
88
89 void resize(size_type n);
90};
91
92template <class Value, class Hash, class Pred, class Alloc>
93 void swap(hash_set<Value, Hash, Pred, Alloc>& x,
94 hash_set<Value, Hash, Pred, Alloc>& y);
95
96template <class Value, class Hash, class Pred, class Alloc>
97 bool
98 operator==(const hash_set<Value, Hash, Pred, Alloc>& x,
99 const hash_set<Value, Hash, Pred, Alloc>& y);
100
101template <class Value, class Hash, class Pred, class Alloc>
102 bool
103 operator!=(const hash_set<Value, Hash, Pred, Alloc>& x,
104 const hash_set<Value, Hash, Pred, Alloc>& y);
105
106template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,
107 class Alloc = allocator<Value>>
108class hash_multiset
109{
110public:
111 // types
112 typedef Value key_type;
113 typedef key_type value_type;
114 typedef Hash hasher;
115 typedef Pred key_equal;
116 typedef Alloc allocator_type;
117 typedef value_type& reference;
118 typedef const value_type& const_reference;
119 typedef typename allocator_traits<allocator_type>::pointer pointer;
120 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
121 typedef typename allocator_traits<allocator_type>::size_type size_type;
122 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
123
124 typedef /unspecified/ iterator;
125 typedef /unspecified/ const_iterator;
126
127 explicit hash_multiset(size_type n = 193, const hasher& hf = hasher(),
128 const key_equal& eql = key_equal(),
129 const allocator_type& a = allocator_type());
130 template <class InputIterator>
131 hash_multiset(InputIterator f, InputIterator l,
132 size_type n = 193, const hasher& hf = hasher(),
133 const key_equal& eql = key_equal(),
134 const allocator_type& a = allocator_type());
135 hash_multiset(const hash_multiset&);
136 ~hash_multiset();
137 hash_multiset& operator=(const hash_multiset&);
138
139 allocator_type get_allocator() const;
140
141 bool empty() const;
142 size_type size() const;
143 size_type max_size() const;
144
145 iterator begin();
146 iterator end();
147 const_iterator begin() const;
148 const_iterator end() const;
149
150 iterator insert(const value_type& obj);
151 template <class InputIterator>
152 void insert(InputIterator first, InputIterator last);
153
154 void erase(const_iterator position);
155 size_type erase(const key_type& k);
156 void erase(const_iterator first, const_iterator last);
157 void clear();
158
159 void swap(hash_multiset&);
160
161 hasher hash_funct() const;
162 key_equal key_eq() const;
163
164 iterator find(const key_type& k);
165 const_iterator find(const key_type& k) const;
166 size_type count(const key_type& k) const;
167 pair<iterator, iterator> equal_range(const key_type& k);
168 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
169
170 size_type bucket_count() const;
171 size_type max_bucket_count() const;
172
173 size_type elems_in_bucket(size_type n) const;
174
175 void resize(size_type n);
176};
177
178template <class Value, class Hash, class Pred, class Alloc>
179 void swap(hash_multiset<Value, Hash, Pred, Alloc>& x,
180 hash_multiset<Value, Hash, Pred, Alloc>& y);
181
182template <class Value, class Hash, class Pred, class Alloc>
183 bool
184 operator==(const hash_multiset<Value, Hash, Pred, Alloc>& x,
185 const hash_multiset<Value, Hash, Pred, Alloc>& y);
186
187template <class Value, class Hash, class Pred, class Alloc>
188 bool
189 operator!=(const hash_multiset<Value, Hash, Pred, Alloc>& x,
190 const hash_multiset<Value, Hash, Pred, Alloc>& y);
191} // __gnu_cxx
192
193*/
194
195#if __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS)
196# include <__cxx03/ext/hash_set>
197#else
198# include <__config>
199# include <__hash_table>
200# include <algorithm>
201# include <ext/__hash>
202# include <functional>
203
204# if defined(__DEPRECATED) && __DEPRECATED
205# if defined(_LIBCPP_WARNING)
206_LIBCPP_WARNING("Use of the header <ext/hash_set> is deprecated. Migrate to <unordered_set>")
207# else
208# warning Use of the header <ext/hash_set> is deprecated. Migrate to <unordered_set>
209# endif
210# endif
211
212# if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
213# pragma GCC system_header
214# endif
215
216namespace __gnu_cxx {
217
218template <class _Value,
219 class _Hash = hash<_Value>,
220 class _Pred = std::equal_to<_Value>,
221 class _Alloc = std::allocator<_Value> >
222class hash_set {
223public:
224 // types
225 typedef _Value key_type;
226 typedef key_type value_type;
227 typedef _Hash hasher;
228 typedef _Pred key_equal;
229 typedef _Alloc allocator_type;
230 typedef value_type& reference;
231 typedef const value_type& const_reference;
232
233private:
234 typedef std::__hash_table<value_type, hasher, key_equal, allocator_type> __table;
235
236 __table __table_;
237
238public:
239 typedef typename __table::pointer pointer;
240 typedef typename __table::const_pointer const_pointer;
241 typedef typename __table::size_type size_type;
242 typedef typename __table::difference_type difference_type;
243
244 typedef typename __table::const_iterator iterator;
245 typedef typename __table::const_iterator const_iterator;
246
247 _LIBCPP_HIDE_FROM_ABI hash_set() {}
248 _LIBCPP_HIDE_FROM_ABI explicit hash_set(
249 size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
250 _LIBCPP_HIDE_FROM_ABI hash_set(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a);
251 template <class _InputIterator>
252 _LIBCPP_HIDE_FROM_ABI hash_set(_InputIterator __first, _InputIterator __last);
253 template <class _InputIterator>
254 _LIBCPP_HIDE_FROM_ABI
255 hash_set(_InputIterator __first,
256 _InputIterator __last,
257 size_type __n,
258 const hasher& __hf = hasher(),
259 const key_equal& __eql = key_equal());
260 template <class _InputIterator>
261 _LIBCPP_HIDE_FROM_ABI
262 hash_set(_InputIterator __first,
263 _InputIterator __last,
264 size_type __n,
265 const hasher& __hf,
266 const key_equal& __eql,
267 const allocator_type& __a);
268 _LIBCPP_HIDE_FROM_ABI hash_set(const hash_set& __u);
269
270 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const { return allocator_type(__table_.__node_alloc()); }
271
272 _LIBCPP_HIDE_FROM_ABI bool empty() const { return __table_.size() == 0; }
273 _LIBCPP_HIDE_FROM_ABI size_type size() const { return __table_.size(); }
274 _LIBCPP_HIDE_FROM_ABI size_type max_size() const { return __table_.max_size(); }
275
276 _LIBCPP_HIDE_FROM_ABI iterator begin() { return __table_.begin(); }
277 _LIBCPP_HIDE_FROM_ABI iterator end() { return __table_.end(); }
278 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const { return __table_.begin(); }
279 _LIBCPP_HIDE_FROM_ABI const_iterator end() const { return __table_.end(); }
280
281 _LIBCPP_HIDE_FROM_ABI std::pair<iterator, bool> insert(const value_type& __x) {
282 return __table_.__emplace_unique(__x);
283 }
284 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, const value_type& __x) { return insert(__x).first; }
285 template <class _InputIterator>
286 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last);
287
288 _LIBCPP_HIDE_FROM_ABI void erase(const_iterator __p) { __table_.erase(__p); }
289 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_unique(__k); }
290 _LIBCPP_HIDE_FROM_ABI void erase(const_iterator __first, const_iterator __last) { __table_.erase(__first, __last); }
291 _LIBCPP_HIDE_FROM_ABI void clear() { __table_.clear(); }
292
293 _LIBCPP_HIDE_FROM_ABI void swap(hash_set& __u) { __table_.swap(__u.__table_); }
294
295 _LIBCPP_HIDE_FROM_ABI hasher hash_funct() const { return __table_.hash_function(); }
296 _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq(); }
297
298 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); }
299 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); }
300 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_unique(__k); }
301 _LIBCPP_HIDE_FROM_ABI std::pair<iterator, iterator> equal_range(const key_type& __k) {
302 return __table_.__equal_range_unique(__k);
303 }
304 _LIBCPP_HIDE_FROM_ABI std::pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
305 return __table_.__equal_range_unique(__k);
306 }
307
308 _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const { return __table_.bucket_count(); }
309 _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const { return __table_.max_bucket_count(); }
310
311 _LIBCPP_HIDE_FROM_ABI size_type elems_in_bucket(size_type __n) const { return __table_.bucket_size(__n); }
312
313 _LIBCPP_HIDE_FROM_ABI void resize(size_type __n) { __table_.__rehash_unique(__n); }
314};
315
316template <class _Value, class _Hash, class _Pred, class _Alloc>
317hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(size_type __n, const hasher& __hf, const key_equal& __eql)
318 : __table_(__hf, __eql) {
319 __table_.__rehash_unique(__n);
320}
321
322template <class _Value, class _Hash, class _Pred, class _Alloc>
323hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(
324 size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
325 : __table_(__hf, __eql, __a) {
326 __table_.__rehash_unique(__n);
327}
328
329template <class _Value, class _Hash, class _Pred, class _Alloc>
330template <class _InputIterator>
331hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(_InputIterator __first, _InputIterator __last) {
332 insert(__first, __last);
333}
334
335template <class _Value, class _Hash, class _Pred, class _Alloc>
336template <class _InputIterator>
337hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(
338 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql)
339 : __table_(__hf, __eql) {
340 __table_.__rehash_unique(__n);
341 insert(__first, __last);
342}
343
344template <class _Value, class _Hash, class _Pred, class _Alloc>
345template <class _InputIterator>
346hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(
347 _InputIterator __first,
348 _InputIterator __last,
349 size_type __n,
350 const hasher& __hf,
351 const key_equal& __eql,
352 const allocator_type& __a)
353 : __table_(__hf, __eql, __a) {
354 __table_.__rehash_unique(__n);
355 insert(__first, __last);
356}
357
358template <class _Value, class _Hash, class _Pred, class _Alloc>
359hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(const hash_set& __u) : __table_(__u.__table_) {
360 __table_.__rehash_unique(__u.bucket_count());
361 insert(__u.begin(), __u.end());
362}
363
364template <class _Value, class _Hash, class _Pred, class _Alloc>
365template <class _InputIterator>
366inline void hash_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) {
367 for (; __first != __last; ++__first)
368 __table_.__emplace_unique(*__first);
369}
370
371template <class _Value, class _Hash, class _Pred, class _Alloc>
372inline _LIBCPP_HIDE_FROM_ABI void
373swap(hash_set<_Value, _Hash, _Pred, _Alloc>& __x, hash_set<_Value, _Hash, _Pred, _Alloc>& __y) {
374 __x.swap(__y);
375}
376
377template <class _Value, class _Hash, class _Pred, class _Alloc>
378_LIBCPP_HIDE_FROM_ABI bool
379operator==(const hash_set<_Value, _Hash, _Pred, _Alloc>& __x, const hash_set<_Value, _Hash, _Pred, _Alloc>& __y) {
380 if (__x.size() != __y.size())
381 return false;
382 typedef typename hash_set<_Value, _Hash, _Pred, _Alloc>::const_iterator const_iterator;
383 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); __i != __ex; ++__i) {
384 const_iterator __j = __y.find(*__i);
385 if (__j == __ey || !(*__i == *__j))
386 return false;
387 }
388 return true;
389}
390
391template <class _Value, class _Hash, class _Pred, class _Alloc>
392inline _LIBCPP_HIDE_FROM_ABI bool
393operator!=(const hash_set<_Value, _Hash, _Pred, _Alloc>& __x, const hash_set<_Value, _Hash, _Pred, _Alloc>& __y) {
394 return !(__x == __y);
395}
396
397template <class _Value,
398 class _Hash = hash<_Value>,
399 class _Pred = std::equal_to<_Value>,
400 class _Alloc = std::allocator<_Value> >
401class hash_multiset {
402public:
403 // types
404 typedef _Value key_type;
405 typedef key_type value_type;
406 typedef _Hash hasher;
407 typedef _Pred key_equal;
408 typedef _Alloc allocator_type;
409 typedef value_type& reference;
410 typedef const value_type& const_reference;
411
412private:
413 typedef std::__hash_table<value_type, hasher, key_equal, allocator_type> __table;
414
415 __table __table_;
416
417public:
418 typedef typename __table::pointer pointer;
419 typedef typename __table::const_pointer const_pointer;
420 typedef typename __table::size_type size_type;
421 typedef typename __table::difference_type difference_type;
422
423 typedef typename __table::const_iterator iterator;
424 typedef typename __table::const_iterator const_iterator;
425
426 _LIBCPP_HIDE_FROM_ABI hash_multiset() {}
427 explicit _LIBCPP_HIDE_FROM_ABI
428 hash_multiset(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
429 _LIBCPP_HIDE_FROM_ABI
430 hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a);
431 template <class _InputIterator>
432 _LIBCPP_HIDE_FROM_ABI hash_multiset(_InputIterator __first, _InputIterator __last);
433 template <class _InputIterator>
434 _LIBCPP_HIDE_FROM_ABI
435 hash_multiset(_InputIterator __first,
436 _InputIterator __last,
437 size_type __n,
438 const hasher& __hf = hasher(),
439 const key_equal& __eql = key_equal());
440 template <class _InputIterator>
441 _LIBCPP_HIDE_FROM_ABI hash_multiset(
442 _InputIterator __first,
443 _InputIterator __last,
444 size_type __n,
445 const hasher& __hf,
446 const key_equal& __eql,
447 const allocator_type& __a);
448 _LIBCPP_HIDE_FROM_ABI hash_multiset(const hash_multiset& __u);
449
450 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const { return allocator_type(__table_.__node_alloc()); }
451
452 _LIBCPP_HIDE_FROM_ABI bool empty() const { return __table_.size() == 0; }
453 _LIBCPP_HIDE_FROM_ABI size_type size() const { return __table_.size(); }
454 _LIBCPP_HIDE_FROM_ABI size_type max_size() const { return __table_.max_size(); }
455
456 _LIBCPP_HIDE_FROM_ABI iterator begin() { return __table_.begin(); }
457 _LIBCPP_HIDE_FROM_ABI iterator end() { return __table_.end(); }
458 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const { return __table_.begin(); }
459 _LIBCPP_HIDE_FROM_ABI const_iterator end() const { return __table_.end(); }
460
461 _LIBCPP_HIDE_FROM_ABI iterator insert(const value_type& __x) { return __table_.__emplace_multi(__x); }
462 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, const value_type& __x) { return insert(__x); }
463 template <class _InputIterator>
464 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last);
465
466 _LIBCPP_HIDE_FROM_ABI void erase(const_iterator __p) { __table_.erase(__p); }
467 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_multi(__k); }
468 _LIBCPP_HIDE_FROM_ABI void erase(const_iterator __first, const_iterator __last) { __table_.erase(__first, __last); }
469 _LIBCPP_HIDE_FROM_ABI void clear() { __table_.clear(); }
470
471 _LIBCPP_HIDE_FROM_ABI void swap(hash_multiset& __u) { __table_.swap(__u.__table_); }
472
473 _LIBCPP_HIDE_FROM_ABI hasher hash_funct() const { return __table_.hash_function(); }
474 _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq(); }
475
476 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); }
477 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); }
478 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_multi(__k); }
479 _LIBCPP_HIDE_FROM_ABI std::pair<iterator, iterator> equal_range(const key_type& __k) {
480 return __table_.__equal_range_multi(__k);
481 }
482 _LIBCPP_HIDE_FROM_ABI std::pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
483 return __table_.__equal_range_multi(__k);
484 }
485
486 _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const { return __table_.bucket_count(); }
487 _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const { return __table_.max_bucket_count(); }
488
489 _LIBCPP_HIDE_FROM_ABI size_type elems_in_bucket(size_type __n) const { return __table_.bucket_size(__n); }
490
491 _LIBCPP_HIDE_FROM_ABI void resize(size_type __n) { __table_.__rehash_multi(__n); }
492};
493
494template <class _Value, class _Hash, class _Pred, class _Alloc>
495hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql)
496 : __table_(__hf, __eql) {
497 __table_.__rehash_multi(__n);
498}
499
500template <class _Value, class _Hash, class _Pred, class _Alloc>
501hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
502 size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
503 : __table_(__hf, __eql, __a) {
504 __table_.__rehash_multi(__n);
505}
506
507template <class _Value, class _Hash, class _Pred, class _Alloc>
508template <class _InputIterator>
509hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(_InputIterator __first, _InputIterator __last) {
510 insert(__first, __last);
511}
512
513template <class _Value, class _Hash, class _Pred, class _Alloc>
514template <class _InputIterator>
515hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
516 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql)
517 : __table_(__hf, __eql) {
518 __table_.__rehash_multi(__n);
519 insert(__first, __last);
520}
521
522template <class _Value, class _Hash, class _Pred, class _Alloc>
523template <class _InputIterator>
524hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
525 _InputIterator __first,
526 _InputIterator __last,
527 size_type __n,
528 const hasher& __hf,
529 const key_equal& __eql,
530 const allocator_type& __a)
531 : __table_(__hf, __eql, __a) {
532 __table_.__rehash_multi(__n);
533 insert(__first, __last);
534}
535
536template <class _Value, class _Hash, class _Pred, class _Alloc>
537hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(const hash_multiset& __u) : __table_(__u.__table_) {
538 __table_.__rehash_multi(__u.bucket_count());
539 insert(__u.begin(), __u.end());
540}
541
542template <class _Value, class _Hash, class _Pred, class _Alloc>
543template <class _InputIterator>
544inline void hash_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) {
545 for (; __first != __last; ++__first)
546 __table_.__emplace_multi(*__first);
547}
548
549template <class _Value, class _Hash, class _Pred, class _Alloc>
550inline _LIBCPP_HIDE_FROM_ABI void
551swap(hash_multiset<_Value, _Hash, _Pred, _Alloc>& __x, hash_multiset<_Value, _Hash, _Pred, _Alloc>& __y) {
552 __x.swap(__y);
553}
554
555template <class _Value, class _Hash, class _Pred, class _Alloc>
556_LIBCPP_HIDE_FROM_ABI bool operator==(const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
557 const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __y) {
558 if (__x.size() != __y.size())
559 return false;
560 typedef typename hash_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator const_iterator;
561 typedef std::pair<const_iterator, const_iterator> _EqRng;
562 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) {
563 _EqRng __xeq = __x.equal_range(*__i);
564 _EqRng __yeq = __y.equal_range(*__i);
565 if (std::distance(__xeq.first, __xeq.second) != std::distance(__yeq.first, __yeq.second) ||
566 !std::is_permutation(__xeq.first, __xeq.second, __yeq.first))
567 return false;
568 __i = __xeq.second;
569 }
570 return true;
571}
572
573template <class _Value, class _Hash, class _Pred, class _Alloc>
574inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
575 const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __y) {
576 return !(__x == __y);
577}
578
579} // namespace __gnu_cxx
580
581# if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
582# include <concepts>
583# include <iterator>
584# include <type_traits>
585# endif
586#endif // __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS)
587
588#endif // _LIBCPP_HASH_SET