2 //===------------------------- hash_set ------------------------------------===//
4 // The LLVM Compiler Infrastructure
6 // This file is dual licensed under the MIT and the University of Illinois Open
7 // Source Licenses. See LICENSE.TXT for details.
9 //===----------------------------------------------------------------------===//
11 #ifndef _LIBCPP_HASH_SET
12 #define _LIBCPP_HASH_SET
21 template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,
22 class Alloc = allocator<Value>>
27 typedef Value key_type;
28 typedef key_type value_type;
30 typedef Pred key_equal;
31 typedef Alloc allocator_type;
32 typedef value_type& reference;
33 typedef const value_type& const_reference;
34 typedef typename allocator_traits<allocator_type>::pointer pointer;
35 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
36 typedef typename allocator_traits<allocator_type>::size_type size_type;
37 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
39 typedef /unspecified/ iterator;
40 typedef /unspecified/ const_iterator;
42 explicit hash_set(size_type n = 193, const hasher& hf = hasher(),
43 const key_equal& eql = key_equal(),
44 const allocator_type& a = allocator_type());
45 template <class InputIterator>
46 hash_set(InputIterator f, InputIterator l,
47 size_type n = 193, const hasher& hf = hasher(),
48 const key_equal& eql = key_equal(),
49 const allocator_type& a = allocator_type());
50 hash_set(const hash_set&);
52 hash_set& operator=(const hash_set&);
54 allocator_type get_allocator() const;
57 size_type size() const;
58 size_type max_size() const;
62 const_iterator begin() const;
63 const_iterator end() const;
65 pair<iterator, bool> insert(const value_type& obj);
66 template <class InputIterator>
67 void insert(InputIterator first, InputIterator last);
69 void erase(const_iterator position);
70 size_type erase(const key_type& k);
71 void erase(const_iterator first, const_iterator last);
76 hasher hash_funct() const;
77 key_equal key_eq() const;
79 iterator find(const key_type& k);
80 const_iterator find(const key_type& k) const;
81 size_type count(const key_type& k) const;
82 pair<iterator, iterator> equal_range(const key_type& k);
83 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
85 size_type bucket_count() const;
86 size_type max_bucket_count() const;
88 size_type elems_in_bucket(size_type n) const;
90 void resize(size_type n);
93 template <class Value, class Hash, class Pred, class Alloc>
94 void swap(hash_set<Value, Hash, Pred, Alloc>& x,
95 hash_set<Value, Hash, Pred, Alloc>& y);
97 template <class Value, class Hash, class Pred, class Alloc>
99 operator==(const hash_set<Value, Hash, Pred, Alloc>& x,
100 const hash_set<Value, Hash, Pred, Alloc>& y);
102 template <class Value, class Hash, class Pred, class Alloc>
104 operator!=(const hash_set<Value, Hash, Pred, Alloc>& x,
105 const hash_set<Value, Hash, Pred, Alloc>& y);
107 template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,
108 class Alloc = allocator<Value>>
113 typedef Value key_type;
114 typedef key_type value_type;
116 typedef Pred key_equal;
117 typedef Alloc allocator_type;
118 typedef value_type& reference;
119 typedef const value_type& const_reference;
120 typedef typename allocator_traits<allocator_type>::pointer pointer;
121 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
122 typedef typename allocator_traits<allocator_type>::size_type size_type;
123 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
125 typedef /unspecified/ iterator;
126 typedef /unspecified/ const_iterator;
128 explicit hash_multiset(size_type n = 193, const hasher& hf = hasher(),
129 const key_equal& eql = key_equal(),
130 const allocator_type& a = allocator_type());
131 template <class InputIterator>
132 hash_multiset(InputIterator f, InputIterator l,
133 size_type n = 193, const hasher& hf = hasher(),
134 const key_equal& eql = key_equal(),
135 const allocator_type& a = allocator_type());
136 hash_multiset(const hash_multiset&);
138 hash_multiset& operator=(const hash_multiset&);
140 allocator_type get_allocator() const;
143 size_type size() const;
144 size_type max_size() const;
148 const_iterator begin() const;
149 const_iterator end() const;
151 iterator insert(const value_type& obj);
152 template <class InputIterator>
153 void insert(InputIterator first, InputIterator last);
155 void erase(const_iterator position);
156 size_type erase(const key_type& k);
157 void erase(const_iterator first, const_iterator last);
160 void swap(hash_multiset&);
162 hasher hash_funct() const;
163 key_equal key_eq() const;
165 iterator find(const key_type& k);
166 const_iterator find(const key_type& k) const;
167 size_type count(const key_type& k) const;
168 pair<iterator, iterator> equal_range(const key_type& k);
169 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
171 size_type bucket_count() const;
172 size_type max_bucket_count() const;
174 size_type elems_in_bucket(size_type n) const;
176 void resize(size_type n);
179 template <class Value, class Hash, class Pred, class Alloc>
180 void swap(hash_multiset<Value, Hash, Pred, Alloc>& x,
181 hash_multiset<Value, Hash, Pred, Alloc>& y);
183 template <class Value, class Hash, class Pred, class Alloc>
185 operator==(const hash_multiset<Value, Hash, Pred, Alloc>& x,
186 const hash_multiset<Value, Hash, Pred, Alloc>& y);
188 template <class Value, class Hash, class Pred, class Alloc>
190 operator!=(const hash_multiset<Value, Hash, Pred, Alloc>& x,
191 const hash_multiset<Value, Hash, Pred, Alloc>& y);
197 #include <__hash_table>
198 #include <functional>
199 #include <ext/__hash>
202 #warning Use of the header <ext/hash_set> is deprecated. Migrate to <unordered_set>
205 namespace __gnu_cxx {
209 template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>,
210 class _Alloc = allocator<_Value> >
211 class _LIBCPP_TYPE_VIS hash_set
215 typedef _Value key_type;
216 typedef key_type value_type;
217 typedef _Hash hasher;
218 typedef _Pred key_equal;
219 typedef _Alloc allocator_type;
220 typedef value_type& reference;
221 typedef const value_type& const_reference;
224 typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
229 typedef typename __table::pointer pointer;
230 typedef typename __table::const_pointer const_pointer;
231 typedef typename __table::size_type size_type;
232 typedef typename __table::difference_type difference_type;
234 typedef typename __table::const_iterator iterator;
235 typedef typename __table::const_iterator const_iterator;
237 _LIBCPP_INLINE_VISIBILITY
238 hash_set() {__table_.rehash(193);}
239 explicit hash_set(size_type __n, const hasher& __hf = hasher(),
240 const key_equal& __eql = key_equal());
241 hash_set(size_type __n, const hasher& __hf, const key_equal& __eql,
242 const allocator_type& __a);
243 template <class _InputIterator>
244 hash_set(_InputIterator __first, _InputIterator __last);
245 template <class _InputIterator>
246 hash_set(_InputIterator __first, _InputIterator __last,
247 size_type __n, const hasher& __hf = hasher(),
248 const key_equal& __eql = key_equal());
249 template <class _InputIterator>
250 hash_set(_InputIterator __first, _InputIterator __last,
251 size_type __n, const hasher& __hf, const key_equal& __eql,
252 const allocator_type& __a);
253 hash_set(const hash_set& __u);
255 _LIBCPP_INLINE_VISIBILITY
256 allocator_type get_allocator() const
257 {return allocator_type(__table_.__node_alloc());}
259 _LIBCPP_INLINE_VISIBILITY
260 bool empty() const {return __table_.size() == 0;}
261 _LIBCPP_INLINE_VISIBILITY
262 size_type size() const {return __table_.size();}
263 _LIBCPP_INLINE_VISIBILITY
264 size_type max_size() const {return __table_.max_size();}
266 _LIBCPP_INLINE_VISIBILITY
267 iterator begin() {return __table_.begin();}
268 _LIBCPP_INLINE_VISIBILITY
269 iterator end() {return __table_.end();}
270 _LIBCPP_INLINE_VISIBILITY
271 const_iterator begin() const {return __table_.begin();}
272 _LIBCPP_INLINE_VISIBILITY
273 const_iterator end() const {return __table_.end();}
275 _LIBCPP_INLINE_VISIBILITY
276 pair<iterator, bool> insert(const value_type& __x)
277 {return __table_.__insert_unique(__x);}
278 _LIBCPP_INLINE_VISIBILITY
279 iterator insert(const_iterator, const value_type& __x) {return insert(__x).first;}
280 template <class _InputIterator>
281 void insert(_InputIterator __first, _InputIterator __last);
283 _LIBCPP_INLINE_VISIBILITY
284 void erase(const_iterator __p) {__table_.erase(__p);}
285 _LIBCPP_INLINE_VISIBILITY
286 size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
287 _LIBCPP_INLINE_VISIBILITY
288 void erase(const_iterator __first, const_iterator __last)
289 {__table_.erase(__first, __last);}
290 _LIBCPP_INLINE_VISIBILITY
291 void clear() {__table_.clear();}
293 _LIBCPP_INLINE_VISIBILITY
294 void swap(hash_set& __u) {__table_.swap(__u.__table_);}
296 _LIBCPP_INLINE_VISIBILITY
297 hasher hash_funct() const {return __table_.hash_function();}
298 _LIBCPP_INLINE_VISIBILITY
299 key_equal key_eq() const {return __table_.key_eq();}
301 _LIBCPP_INLINE_VISIBILITY
302 iterator find(const key_type& __k) {return __table_.find(__k);}
303 _LIBCPP_INLINE_VISIBILITY
304 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
305 _LIBCPP_INLINE_VISIBILITY
306 size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
307 _LIBCPP_INLINE_VISIBILITY
308 pair<iterator, iterator> equal_range(const key_type& __k)
309 {return __table_.__equal_range_unique(__k);}
310 _LIBCPP_INLINE_VISIBILITY
311 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
312 {return __table_.__equal_range_unique(__k);}
314 _LIBCPP_INLINE_VISIBILITY
315 size_type bucket_count() const {return __table_.bucket_count();}
316 _LIBCPP_INLINE_VISIBILITY
317 size_type max_bucket_count() const {return __table_.max_bucket_count();}
319 _LIBCPP_INLINE_VISIBILITY
320 size_type elems_in_bucket(size_type __n) const {return __table_.bucket_size(__n);}
322 _LIBCPP_INLINE_VISIBILITY
323 void resize(size_type __n) {__table_.rehash(__n);}
326 template <class _Value, class _Hash, class _Pred, class _Alloc>
327 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(size_type __n,
328 const hasher& __hf, const key_equal& __eql)
329 : __table_(__hf, __eql)
331 __table_.rehash(__n);
334 template <class _Value, class _Hash, class _Pred, class _Alloc>
335 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(size_type __n,
336 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
337 : __table_(__hf, __eql, __a)
339 __table_.rehash(__n);
342 template <class _Value, class _Hash, class _Pred, class _Alloc>
343 template <class _InputIterator>
344 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(
345 _InputIterator __first, _InputIterator __last)
347 __table_.rehash(193);
348 insert(__first, __last);
351 template <class _Value, class _Hash, class _Pred, class _Alloc>
352 template <class _InputIterator>
353 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(
354 _InputIterator __first, _InputIterator __last, size_type __n,
355 const hasher& __hf, const key_equal& __eql)
356 : __table_(__hf, __eql)
358 __table_.rehash(__n);
359 insert(__first, __last);
362 template <class _Value, class _Hash, class _Pred, class _Alloc>
363 template <class _InputIterator>
364 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(
365 _InputIterator __first, _InputIterator __last, size_type __n,
366 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
367 : __table_(__hf, __eql, __a)
369 __table_.rehash(__n);
370 insert(__first, __last);
373 template <class _Value, class _Hash, class _Pred, class _Alloc>
374 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(
376 : __table_(__u.__table_)
378 __table_.rehash(__u.bucket_count());
379 insert(__u.begin(), __u.end());
382 template <class _Value, class _Hash, class _Pred, class _Alloc>
383 template <class _InputIterator>
384 inline _LIBCPP_INLINE_VISIBILITY
386 hash_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
387 _InputIterator __last)
389 for (; __first != __last; ++__first)
390 __table_.__insert_unique(*__first);
393 template <class _Value, class _Hash, class _Pred, class _Alloc>
394 inline _LIBCPP_INLINE_VISIBILITY
396 swap(hash_set<_Value, _Hash, _Pred, _Alloc>& __x,
397 hash_set<_Value, _Hash, _Pred, _Alloc>& __y)
402 template <class _Value, class _Hash, class _Pred, class _Alloc>
404 operator==(const hash_set<_Value, _Hash, _Pred, _Alloc>& __x,
405 const hash_set<_Value, _Hash, _Pred, _Alloc>& __y)
407 if (__x.size() != __y.size())
409 typedef typename hash_set<_Value, _Hash, _Pred, _Alloc>::const_iterator
411 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();
414 const_iterator __j = __y.find(*__i);
415 if (__j == __ey || !(*__i == *__j))
421 template <class _Value, class _Hash, class _Pred, class _Alloc>
422 inline _LIBCPP_INLINE_VISIBILITY
424 operator!=(const hash_set<_Value, _Hash, _Pred, _Alloc>& __x,
425 const hash_set<_Value, _Hash, _Pred, _Alloc>& __y)
427 return !(__x == __y);
430 template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>,
431 class _Alloc = allocator<_Value> >
432 class _LIBCPP_TYPE_VIS hash_multiset
436 typedef _Value key_type;
437 typedef key_type value_type;
438 typedef _Hash hasher;
439 typedef _Pred key_equal;
440 typedef _Alloc allocator_type;
441 typedef value_type& reference;
442 typedef const value_type& const_reference;
445 typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
450 typedef typename __table::pointer pointer;
451 typedef typename __table::const_pointer const_pointer;
452 typedef typename __table::size_type size_type;
453 typedef typename __table::difference_type difference_type;
455 typedef typename __table::const_iterator iterator;
456 typedef typename __table::const_iterator const_iterator;
458 _LIBCPP_INLINE_VISIBILITY
459 hash_multiset() {__table_.rehash(193);}
460 explicit hash_multiset(size_type __n, const hasher& __hf = hasher(),
461 const key_equal& __eql = key_equal());
462 hash_multiset(size_type __n, const hasher& __hf,
463 const key_equal& __eql, const allocator_type& __a);
464 template <class _InputIterator>
465 hash_multiset(_InputIterator __first, _InputIterator __last);
466 template <class _InputIterator>
467 hash_multiset(_InputIterator __first, _InputIterator __last,
468 size_type __n, const hasher& __hf = hasher(),
469 const key_equal& __eql = key_equal());
470 template <class _InputIterator>
471 hash_multiset(_InputIterator __first, _InputIterator __last,
472 size_type __n , const hasher& __hf,
473 const key_equal& __eql, const allocator_type& __a);
474 hash_multiset(const hash_multiset& __u);
476 _LIBCPP_INLINE_VISIBILITY
477 allocator_type get_allocator() const
478 {return allocator_type(__table_.__node_alloc());}
480 _LIBCPP_INLINE_VISIBILITY
481 bool empty() const {return __table_.size() == 0;}
482 _LIBCPP_INLINE_VISIBILITY
483 size_type size() const {return __table_.size();}
484 _LIBCPP_INLINE_VISIBILITY
485 size_type max_size() const {return __table_.max_size();}
487 _LIBCPP_INLINE_VISIBILITY
488 iterator begin() {return __table_.begin();}
489 _LIBCPP_INLINE_VISIBILITY
490 iterator end() {return __table_.end();}
491 _LIBCPP_INLINE_VISIBILITY
492 const_iterator begin() const {return __table_.begin();}
493 _LIBCPP_INLINE_VISIBILITY
494 const_iterator end() const {return __table_.end();}
496 _LIBCPP_INLINE_VISIBILITY
497 iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
498 _LIBCPP_INLINE_VISIBILITY
499 iterator insert(const_iterator, const value_type& __x) {return insert(__x);}
500 template <class _InputIterator>
501 void insert(_InputIterator __first, _InputIterator __last);
503 _LIBCPP_INLINE_VISIBILITY
504 void erase(const_iterator __p) {__table_.erase(__p);}
505 _LIBCPP_INLINE_VISIBILITY
506 size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
507 _LIBCPP_INLINE_VISIBILITY
508 void erase(const_iterator __first, const_iterator __last)
509 {__table_.erase(__first, __last);}
510 _LIBCPP_INLINE_VISIBILITY
511 void clear() {__table_.clear();}
513 _LIBCPP_INLINE_VISIBILITY
514 void swap(hash_multiset& __u) {__table_.swap(__u.__table_);}
516 _LIBCPP_INLINE_VISIBILITY
517 hasher hash_funct() const {return __table_.hash_function();}
518 _LIBCPP_INLINE_VISIBILITY
519 key_equal key_eq() const {return __table_.key_eq();}
521 _LIBCPP_INLINE_VISIBILITY
522 iterator find(const key_type& __k) {return __table_.find(__k);}
523 _LIBCPP_INLINE_VISIBILITY
524 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
525 _LIBCPP_INLINE_VISIBILITY
526 size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
527 _LIBCPP_INLINE_VISIBILITY
528 pair<iterator, iterator> equal_range(const key_type& __k)
529 {return __table_.__equal_range_multi(__k);}
530 _LIBCPP_INLINE_VISIBILITY
531 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
532 {return __table_.__equal_range_multi(__k);}
534 _LIBCPP_INLINE_VISIBILITY
535 size_type bucket_count() const {return __table_.bucket_count();}
536 _LIBCPP_INLINE_VISIBILITY
537 size_type max_bucket_count() const {return __table_.max_bucket_count();}
539 _LIBCPP_INLINE_VISIBILITY
540 size_type elems_in_bucket(size_type __n) const {return __table_.bucket_size(__n);}
542 _LIBCPP_INLINE_VISIBILITY
543 void resize(size_type __n) {__table_.rehash(__n);}
546 template <class _Value, class _Hash, class _Pred, class _Alloc>
547 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
548 size_type __n, const hasher& __hf, const key_equal& __eql)
549 : __table_(__hf, __eql)
551 __table_.rehash(__n);
554 template <class _Value, class _Hash, class _Pred, class _Alloc>
555 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
556 size_type __n, const hasher& __hf, const key_equal& __eql,
557 const allocator_type& __a)
558 : __table_(__hf, __eql, __a)
560 __table_.rehash(__n);
563 template <class _Value, class _Hash, class _Pred, class _Alloc>
564 template <class _InputIterator>
565 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
566 _InputIterator __first, _InputIterator __last)
568 __table_.rehash(193);
569 insert(__first, __last);
572 template <class _Value, class _Hash, class _Pred, class _Alloc>
573 template <class _InputIterator>
574 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
575 _InputIterator __first, _InputIterator __last, size_type __n,
576 const hasher& __hf, const key_equal& __eql)
577 : __table_(__hf, __eql)
579 __table_.rehash(__n);
580 insert(__first, __last);
583 template <class _Value, class _Hash, class _Pred, class _Alloc>
584 template <class _InputIterator>
585 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
586 _InputIterator __first, _InputIterator __last, size_type __n,
587 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
588 : __table_(__hf, __eql, __a)
590 __table_.rehash(__n);
591 insert(__first, __last);
594 template <class _Value, class _Hash, class _Pred, class _Alloc>
595 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
596 const hash_multiset& __u)
597 : __table_(__u.__table_)
599 __table_.rehash(__u.bucket_count());
600 insert(__u.begin(), __u.end());
603 template <class _Value, class _Hash, class _Pred, class _Alloc>
604 template <class _InputIterator>
605 inline _LIBCPP_INLINE_VISIBILITY
607 hash_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
608 _InputIterator __last)
610 for (; __first != __last; ++__first)
611 __table_.__insert_multi(*__first);
614 template <class _Value, class _Hash, class _Pred, class _Alloc>
615 inline _LIBCPP_INLINE_VISIBILITY
617 swap(hash_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
618 hash_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
623 template <class _Value, class _Hash, class _Pred, class _Alloc>
625 operator==(const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
626 const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
628 if (__x.size() != __y.size())
630 typedef typename hash_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator
632 typedef pair<const_iterator, const_iterator> _EqRng;
633 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;)
635 _EqRng __xeq = __x.equal_range(*__i);
636 _EqRng __yeq = __y.equal_range(*__i);
637 if (_VSTD::distance(__xeq.first, __xeq.second) !=
638 _VSTD::distance(__yeq.first, __yeq.second) ||
639 !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first))
646 template <class _Value, class _Hash, class _Pred, class _Alloc>
647 inline _LIBCPP_INLINE_VISIBILITY
649 operator!=(const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
650 const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
652 return !(__x == __y);
657 #endif // _LIBCPP_HASH_SET