2 //===------------------------- hash_set ------------------------------------===//
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
8 //===----------------------------------------------------------------------===//
10 #ifndef _LIBCPP_HASH_SET
11 #define _LIBCPP_HASH_SET
20 template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,
21 class Alloc = allocator<Value>>
26 typedef Value key_type;
27 typedef key_type value_type;
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;
38 typedef /unspecified/ iterator;
39 typedef /unspecified/ const_iterator;
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&);
51 hash_set& operator=(const hash_set&);
53 allocator_type get_allocator() const;
56 size_type size() const;
57 size_type max_size() const;
61 const_iterator begin() const;
62 const_iterator end() const;
64 pair<iterator, bool> insert(const value_type& obj);
65 template <class InputIterator>
66 void insert(InputIterator first, InputIterator last);
68 void erase(const_iterator position);
69 size_type erase(const key_type& k);
70 void erase(const_iterator first, const_iterator last);
75 hasher hash_funct() const;
76 key_equal key_eq() const;
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;
84 size_type bucket_count() const;
85 size_type max_bucket_count() const;
87 size_type elems_in_bucket(size_type n) const;
89 void resize(size_type n);
92 template <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);
96 template <class Value, class Hash, class Pred, class Alloc>
98 operator==(const hash_set<Value, Hash, Pred, Alloc>& x,
99 const hash_set<Value, Hash, Pred, Alloc>& y);
101 template <class Value, class Hash, class Pred, class Alloc>
103 operator!=(const hash_set<Value, Hash, Pred, Alloc>& x,
104 const hash_set<Value, Hash, Pred, Alloc>& y);
106 template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,
107 class Alloc = allocator<Value>>
112 typedef Value key_type;
113 typedef key_type value_type;
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;
124 typedef /unspecified/ iterator;
125 typedef /unspecified/ const_iterator;
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&);
137 hash_multiset& operator=(const hash_multiset&);
139 allocator_type get_allocator() const;
142 size_type size() const;
143 size_type max_size() const;
147 const_iterator begin() const;
148 const_iterator end() const;
150 iterator insert(const value_type& obj);
151 template <class InputIterator>
152 void insert(InputIterator first, InputIterator last);
154 void erase(const_iterator position);
155 size_type erase(const key_type& k);
156 void erase(const_iterator first, const_iterator last);
159 void swap(hash_multiset&);
161 hasher hash_funct() const;
162 key_equal key_eq() const;
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;
170 size_type bucket_count() const;
171 size_type max_bucket_count() const;
173 size_type elems_in_bucket(size_type n) const;
175 void resize(size_type n);
178 template <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);
182 template <class Value, class Hash, class Pred, class Alloc>
184 operator==(const hash_multiset<Value, Hash, Pred, Alloc>& x,
185 const hash_multiset<Value, Hash, Pred, Alloc>& y);
187 template <class Value, class Hash, class Pred, class Alloc>
189 operator!=(const hash_multiset<Value, Hash, Pred, Alloc>& x,
190 const hash_multiset<Value, Hash, Pred, Alloc>& y);
196 #include <__hash_table>
197 #include <functional>
198 #include <ext/__hash>
201 #if defined(_LIBCPP_WARNING)
202 _LIBCPP_WARNING("Use of the header <ext/hash_set> is deprecated. Migrate to <unordered_set>")
204 # warning Use of the header <ext/hash_set> is deprecated. Migrate to <unordered_set>
208 namespace __gnu_cxx {
211 template <class _Value, class _Hash = hash<_Value>, class _Pred = std::equal_to<_Value>,
212 class _Alloc = std::allocator<_Value> >
213 class _LIBCPP_TEMPLATE_VIS hash_set
217 typedef _Value key_type;
218 typedef key_type value_type;
219 typedef _Hash hasher;
220 typedef _Pred key_equal;
221 typedef _Alloc allocator_type;
222 typedef value_type& reference;
223 typedef const value_type& const_reference;
226 typedef std::__hash_table<value_type, hasher, key_equal, allocator_type> __table;
231 typedef typename __table::pointer pointer;
232 typedef typename __table::const_pointer const_pointer;
233 typedef typename __table::size_type size_type;
234 typedef typename __table::difference_type difference_type;
236 typedef typename __table::const_iterator iterator;
237 typedef typename __table::const_iterator const_iterator;
239 _LIBCPP_INLINE_VISIBILITY
240 hash_set() {__table_.rehash(193);}
241 explicit hash_set(size_type __n, const hasher& __hf = hasher(),
242 const key_equal& __eql = key_equal());
243 hash_set(size_type __n, const hasher& __hf, const key_equal& __eql,
244 const allocator_type& __a);
245 template <class _InputIterator>
246 hash_set(_InputIterator __first, _InputIterator __last);
247 template <class _InputIterator>
248 hash_set(_InputIterator __first, _InputIterator __last,
249 size_type __n, const hasher& __hf = hasher(),
250 const key_equal& __eql = key_equal());
251 template <class _InputIterator>
252 hash_set(_InputIterator __first, _InputIterator __last,
253 size_type __n, const hasher& __hf, const key_equal& __eql,
254 const allocator_type& __a);
255 hash_set(const hash_set& __u);
257 _LIBCPP_INLINE_VISIBILITY
258 allocator_type get_allocator() const
259 {return allocator_type(__table_.__node_alloc());}
261 _LIBCPP_INLINE_VISIBILITY
262 bool empty() const {return __table_.size() == 0;}
263 _LIBCPP_INLINE_VISIBILITY
264 size_type size() const {return __table_.size();}
265 _LIBCPP_INLINE_VISIBILITY
266 size_type max_size() const {return __table_.max_size();}
268 _LIBCPP_INLINE_VISIBILITY
269 iterator begin() {return __table_.begin();}
270 _LIBCPP_INLINE_VISIBILITY
271 iterator end() {return __table_.end();}
272 _LIBCPP_INLINE_VISIBILITY
273 const_iterator begin() const {return __table_.begin();}
274 _LIBCPP_INLINE_VISIBILITY
275 const_iterator end() const {return __table_.end();}
277 _LIBCPP_INLINE_VISIBILITY
278 std::pair<iterator, bool> insert(const value_type& __x)
279 {return __table_.__insert_unique(__x);}
280 _LIBCPP_INLINE_VISIBILITY
281 iterator insert(const_iterator, const value_type& __x) {return insert(__x).first;}
282 template <class _InputIterator>
283 _LIBCPP_INLINE_VISIBILITY
284 void insert(_InputIterator __first, _InputIterator __last);
286 _LIBCPP_INLINE_VISIBILITY
287 void erase(const_iterator __p) {__table_.erase(__p);}
288 _LIBCPP_INLINE_VISIBILITY
289 size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
290 _LIBCPP_INLINE_VISIBILITY
291 void erase(const_iterator __first, const_iterator __last)
292 {__table_.erase(__first, __last);}
293 _LIBCPP_INLINE_VISIBILITY
294 void clear() {__table_.clear();}
296 _LIBCPP_INLINE_VISIBILITY
297 void swap(hash_set& __u) {__table_.swap(__u.__table_);}
299 _LIBCPP_INLINE_VISIBILITY
300 hasher hash_funct() const {return __table_.hash_function();}
301 _LIBCPP_INLINE_VISIBILITY
302 key_equal key_eq() const {return __table_.key_eq();}
304 _LIBCPP_INLINE_VISIBILITY
305 iterator find(const key_type& __k) {return __table_.find(__k);}
306 _LIBCPP_INLINE_VISIBILITY
307 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
308 _LIBCPP_INLINE_VISIBILITY
309 size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
310 _LIBCPP_INLINE_VISIBILITY
311 std::pair<iterator, iterator> equal_range(const key_type& __k)
312 {return __table_.__equal_range_unique(__k);}
313 _LIBCPP_INLINE_VISIBILITY
314 std::pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
315 {return __table_.__equal_range_unique(__k);}
317 _LIBCPP_INLINE_VISIBILITY
318 size_type bucket_count() const {return __table_.bucket_count();}
319 _LIBCPP_INLINE_VISIBILITY
320 size_type max_bucket_count() const {return __table_.max_bucket_count();}
322 _LIBCPP_INLINE_VISIBILITY
323 size_type elems_in_bucket(size_type __n) const {return __table_.bucket_size(__n);}
325 _LIBCPP_INLINE_VISIBILITY
326 void resize(size_type __n) {__table_.rehash(__n);}
329 template <class _Value, class _Hash, class _Pred, class _Alloc>
330 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(size_type __n,
331 const hasher& __hf, const key_equal& __eql)
332 : __table_(__hf, __eql)
334 __table_.rehash(__n);
337 template <class _Value, class _Hash, class _Pred, class _Alloc>
338 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(size_type __n,
339 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
340 : __table_(__hf, __eql, __a)
342 __table_.rehash(__n);
345 template <class _Value, class _Hash, class _Pred, class _Alloc>
346 template <class _InputIterator>
347 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(
348 _InputIterator __first, _InputIterator __last)
350 __table_.rehash(193);
351 insert(__first, __last);
354 template <class _Value, class _Hash, class _Pred, class _Alloc>
355 template <class _InputIterator>
356 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(
357 _InputIterator __first, _InputIterator __last, size_type __n,
358 const hasher& __hf, const key_equal& __eql)
359 : __table_(__hf, __eql)
361 __table_.rehash(__n);
362 insert(__first, __last);
365 template <class _Value, class _Hash, class _Pred, class _Alloc>
366 template <class _InputIterator>
367 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(
368 _InputIterator __first, _InputIterator __last, size_type __n,
369 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
370 : __table_(__hf, __eql, __a)
372 __table_.rehash(__n);
373 insert(__first, __last);
376 template <class _Value, class _Hash, class _Pred, class _Alloc>
377 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(
379 : __table_(__u.__table_)
381 __table_.rehash(__u.bucket_count());
382 insert(__u.begin(), __u.end());
385 template <class _Value, class _Hash, class _Pred, class _Alloc>
386 template <class _InputIterator>
389 hash_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
390 _InputIterator __last)
392 for (; __first != __last; ++__first)
393 __table_.__insert_unique(*__first);
396 template <class _Value, class _Hash, class _Pred, class _Alloc>
397 inline _LIBCPP_INLINE_VISIBILITY
399 swap(hash_set<_Value, _Hash, _Pred, _Alloc>& __x,
400 hash_set<_Value, _Hash, _Pred, _Alloc>& __y)
405 template <class _Value, class _Hash, class _Pred, class _Alloc>
407 operator==(const hash_set<_Value, _Hash, _Pred, _Alloc>& __x,
408 const hash_set<_Value, _Hash, _Pred, _Alloc>& __y)
410 if (__x.size() != __y.size())
412 typedef typename hash_set<_Value, _Hash, _Pred, _Alloc>::const_iterator
414 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();
417 const_iterator __j = __y.find(*__i);
418 if (__j == __ey || !(*__i == *__j))
424 template <class _Value, class _Hash, class _Pred, class _Alloc>
425 inline _LIBCPP_INLINE_VISIBILITY
427 operator!=(const hash_set<_Value, _Hash, _Pred, _Alloc>& __x,
428 const hash_set<_Value, _Hash, _Pred, _Alloc>& __y)
430 return !(__x == __y);
433 template <class _Value, class _Hash = hash<_Value>, class _Pred = std::equal_to<_Value>,
434 class _Alloc = std::allocator<_Value> >
435 class _LIBCPP_TEMPLATE_VIS hash_multiset
439 typedef _Value key_type;
440 typedef key_type value_type;
441 typedef _Hash hasher;
442 typedef _Pred key_equal;
443 typedef _Alloc allocator_type;
444 typedef value_type& reference;
445 typedef const value_type& const_reference;
448 typedef std::__hash_table<value_type, hasher, key_equal, allocator_type> __table;
453 typedef typename __table::pointer pointer;
454 typedef typename __table::const_pointer const_pointer;
455 typedef typename __table::size_type size_type;
456 typedef typename __table::difference_type difference_type;
458 typedef typename __table::const_iterator iterator;
459 typedef typename __table::const_iterator const_iterator;
461 _LIBCPP_INLINE_VISIBILITY
462 hash_multiset() {__table_.rehash(193);}
463 explicit hash_multiset(size_type __n, const hasher& __hf = hasher(),
464 const key_equal& __eql = key_equal());
465 hash_multiset(size_type __n, const hasher& __hf,
466 const key_equal& __eql, const allocator_type& __a);
467 template <class _InputIterator>
468 hash_multiset(_InputIterator __first, _InputIterator __last);
469 template <class _InputIterator>
470 hash_multiset(_InputIterator __first, _InputIterator __last,
471 size_type __n, const hasher& __hf = hasher(),
472 const key_equal& __eql = key_equal());
473 template <class _InputIterator>
474 hash_multiset(_InputIterator __first, _InputIterator __last,
475 size_type __n , const hasher& __hf,
476 const key_equal& __eql, const allocator_type& __a);
477 hash_multiset(const hash_multiset& __u);
479 _LIBCPP_INLINE_VISIBILITY
480 allocator_type get_allocator() const
481 {return allocator_type(__table_.__node_alloc());}
483 _LIBCPP_INLINE_VISIBILITY
484 bool empty() const {return __table_.size() == 0;}
485 _LIBCPP_INLINE_VISIBILITY
486 size_type size() const {return __table_.size();}
487 _LIBCPP_INLINE_VISIBILITY
488 size_type max_size() const {return __table_.max_size();}
490 _LIBCPP_INLINE_VISIBILITY
491 iterator begin() {return __table_.begin();}
492 _LIBCPP_INLINE_VISIBILITY
493 iterator end() {return __table_.end();}
494 _LIBCPP_INLINE_VISIBILITY
495 const_iterator begin() const {return __table_.begin();}
496 _LIBCPP_INLINE_VISIBILITY
497 const_iterator end() const {return __table_.end();}
499 _LIBCPP_INLINE_VISIBILITY
500 iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
501 _LIBCPP_INLINE_VISIBILITY
502 iterator insert(const_iterator, const value_type& __x) {return insert(__x);}
503 template <class _InputIterator>
504 _LIBCPP_INLINE_VISIBILITY
505 void insert(_InputIterator __first, _InputIterator __last);
507 _LIBCPP_INLINE_VISIBILITY
508 void erase(const_iterator __p) {__table_.erase(__p);}
509 _LIBCPP_INLINE_VISIBILITY
510 size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
511 _LIBCPP_INLINE_VISIBILITY
512 void erase(const_iterator __first, const_iterator __last)
513 {__table_.erase(__first, __last);}
514 _LIBCPP_INLINE_VISIBILITY
515 void clear() {__table_.clear();}
517 _LIBCPP_INLINE_VISIBILITY
518 void swap(hash_multiset& __u) {__table_.swap(__u.__table_);}
520 _LIBCPP_INLINE_VISIBILITY
521 hasher hash_funct() const {return __table_.hash_function();}
522 _LIBCPP_INLINE_VISIBILITY
523 key_equal key_eq() const {return __table_.key_eq();}
525 _LIBCPP_INLINE_VISIBILITY
526 iterator find(const key_type& __k) {return __table_.find(__k);}
527 _LIBCPP_INLINE_VISIBILITY
528 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
529 _LIBCPP_INLINE_VISIBILITY
530 size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
531 _LIBCPP_INLINE_VISIBILITY
532 std::pair<iterator, iterator> equal_range(const key_type& __k)
533 {return __table_.__equal_range_multi(__k);}
534 _LIBCPP_INLINE_VISIBILITY
535 std::pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
536 {return __table_.__equal_range_multi(__k);}
538 _LIBCPP_INLINE_VISIBILITY
539 size_type bucket_count() const {return __table_.bucket_count();}
540 _LIBCPP_INLINE_VISIBILITY
541 size_type max_bucket_count() const {return __table_.max_bucket_count();}
543 _LIBCPP_INLINE_VISIBILITY
544 size_type elems_in_bucket(size_type __n) const {return __table_.bucket_size(__n);}
546 _LIBCPP_INLINE_VISIBILITY
547 void resize(size_type __n) {__table_.rehash(__n);}
550 template <class _Value, class _Hash, class _Pred, class _Alloc>
551 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
552 size_type __n, const hasher& __hf, const key_equal& __eql)
553 : __table_(__hf, __eql)
555 __table_.rehash(__n);
558 template <class _Value, class _Hash, class _Pred, class _Alloc>
559 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
560 size_type __n, const hasher& __hf, const key_equal& __eql,
561 const allocator_type& __a)
562 : __table_(__hf, __eql, __a)
564 __table_.rehash(__n);
567 template <class _Value, class _Hash, class _Pred, class _Alloc>
568 template <class _InputIterator>
569 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
570 _InputIterator __first, _InputIterator __last)
572 __table_.rehash(193);
573 insert(__first, __last);
576 template <class _Value, class _Hash, class _Pred, class _Alloc>
577 template <class _InputIterator>
578 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
579 _InputIterator __first, _InputIterator __last, size_type __n,
580 const hasher& __hf, const key_equal& __eql)
581 : __table_(__hf, __eql)
583 __table_.rehash(__n);
584 insert(__first, __last);
587 template <class _Value, class _Hash, class _Pred, class _Alloc>
588 template <class _InputIterator>
589 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
590 _InputIterator __first, _InputIterator __last, size_type __n,
591 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
592 : __table_(__hf, __eql, __a)
594 __table_.rehash(__n);
595 insert(__first, __last);
598 template <class _Value, class _Hash, class _Pred, class _Alloc>
599 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
600 const hash_multiset& __u)
601 : __table_(__u.__table_)
603 __table_.rehash(__u.bucket_count());
604 insert(__u.begin(), __u.end());
607 template <class _Value, class _Hash, class _Pred, class _Alloc>
608 template <class _InputIterator>
611 hash_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
612 _InputIterator __last)
614 for (; __first != __last; ++__first)
615 __table_.__insert_multi(*__first);
618 template <class _Value, class _Hash, class _Pred, class _Alloc>
619 inline _LIBCPP_INLINE_VISIBILITY
621 swap(hash_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
622 hash_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
627 template <class _Value, class _Hash, class _Pred, class _Alloc>
629 operator==(const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
630 const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
632 if (__x.size() != __y.size())
634 typedef typename hash_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator
636 typedef std::pair<const_iterator, const_iterator> _EqRng;
637 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;)
639 _EqRng __xeq = __x.equal_range(*__i);
640 _EqRng __yeq = __y.equal_range(*__i);
641 if (_VSTD::distance(__xeq.first, __xeq.second) !=
642 _VSTD::distance(__yeq.first, __yeq.second) ||
643 !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first))
650 template <class _Value, class _Hash, class _Pred, class _Alloc>
651 inline _LIBCPP_INLINE_VISIBILITY
653 operator!=(const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
654 const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
656 return !(__x == __y);
661 #endif // _LIBCPP_HASH_SET