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 #if defined(_LIBCPP_WARNING)
203 _LIBCPP_WARNING("Use of the header <ext/hash_set> is deprecated. Migrate to <unordered_set>")
205 # warning Use of the header <ext/hash_set> is deprecated. Migrate to <unordered_set>
209 namespace __gnu_cxx {
213 template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>,
214 class _Alloc = allocator<_Value> >
215 class _LIBCPP_TEMPLATE_VIS hash_set
219 typedef _Value key_type;
220 typedef key_type value_type;
221 typedef _Hash hasher;
222 typedef _Pred key_equal;
223 typedef _Alloc allocator_type;
224 typedef value_type& reference;
225 typedef const value_type& const_reference;
228 typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
233 typedef typename __table::pointer pointer;
234 typedef typename __table::const_pointer const_pointer;
235 typedef typename __table::size_type size_type;
236 typedef typename __table::difference_type difference_type;
238 typedef typename __table::const_iterator iterator;
239 typedef typename __table::const_iterator const_iterator;
241 _LIBCPP_INLINE_VISIBILITY
242 hash_set() {__table_.rehash(193);}
243 explicit hash_set(size_type __n, const hasher& __hf = hasher(),
244 const key_equal& __eql = key_equal());
245 hash_set(size_type __n, const hasher& __hf, const key_equal& __eql,
246 const allocator_type& __a);
247 template <class _InputIterator>
248 hash_set(_InputIterator __first, _InputIterator __last);
249 template <class _InputIterator>
250 hash_set(_InputIterator __first, _InputIterator __last,
251 size_type __n, const hasher& __hf = hasher(),
252 const key_equal& __eql = key_equal());
253 template <class _InputIterator>
254 hash_set(_InputIterator __first, _InputIterator __last,
255 size_type __n, const hasher& __hf, const key_equal& __eql,
256 const allocator_type& __a);
257 hash_set(const hash_set& __u);
259 _LIBCPP_INLINE_VISIBILITY
260 allocator_type get_allocator() const
261 {return allocator_type(__table_.__node_alloc());}
263 _LIBCPP_INLINE_VISIBILITY
264 bool empty() const {return __table_.size() == 0;}
265 _LIBCPP_INLINE_VISIBILITY
266 size_type size() const {return __table_.size();}
267 _LIBCPP_INLINE_VISIBILITY
268 size_type max_size() const {return __table_.max_size();}
270 _LIBCPP_INLINE_VISIBILITY
271 iterator begin() {return __table_.begin();}
272 _LIBCPP_INLINE_VISIBILITY
273 iterator end() {return __table_.end();}
274 _LIBCPP_INLINE_VISIBILITY
275 const_iterator begin() const {return __table_.begin();}
276 _LIBCPP_INLINE_VISIBILITY
277 const_iterator end() const {return __table_.end();}
279 _LIBCPP_INLINE_VISIBILITY
280 pair<iterator, bool> insert(const value_type& __x)
281 {return __table_.__insert_unique(__x);}
282 _LIBCPP_INLINE_VISIBILITY
283 iterator insert(const_iterator, const value_type& __x) {return insert(__x).first;}
284 template <class _InputIterator>
285 _LIBCPP_INLINE_VISIBILITY
286 void insert(_InputIterator __first, _InputIterator __last);
288 _LIBCPP_INLINE_VISIBILITY
289 void erase(const_iterator __p) {__table_.erase(__p);}
290 _LIBCPP_INLINE_VISIBILITY
291 size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
292 _LIBCPP_INLINE_VISIBILITY
293 void erase(const_iterator __first, const_iterator __last)
294 {__table_.erase(__first, __last);}
295 _LIBCPP_INLINE_VISIBILITY
296 void clear() {__table_.clear();}
298 _LIBCPP_INLINE_VISIBILITY
299 void swap(hash_set& __u) {__table_.swap(__u.__table_);}
301 _LIBCPP_INLINE_VISIBILITY
302 hasher hash_funct() const {return __table_.hash_function();}
303 _LIBCPP_INLINE_VISIBILITY
304 key_equal key_eq() const {return __table_.key_eq();}
306 _LIBCPP_INLINE_VISIBILITY
307 iterator find(const key_type& __k) {return __table_.find(__k);}
308 _LIBCPP_INLINE_VISIBILITY
309 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
310 _LIBCPP_INLINE_VISIBILITY
311 size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
312 _LIBCPP_INLINE_VISIBILITY
313 pair<iterator, iterator> equal_range(const key_type& __k)
314 {return __table_.__equal_range_unique(__k);}
315 _LIBCPP_INLINE_VISIBILITY
316 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
317 {return __table_.__equal_range_unique(__k);}
319 _LIBCPP_INLINE_VISIBILITY
320 size_type bucket_count() const {return __table_.bucket_count();}
321 _LIBCPP_INLINE_VISIBILITY
322 size_type max_bucket_count() const {return __table_.max_bucket_count();}
324 _LIBCPP_INLINE_VISIBILITY
325 size_type elems_in_bucket(size_type __n) const {return __table_.bucket_size(__n);}
327 _LIBCPP_INLINE_VISIBILITY
328 void resize(size_type __n) {__table_.rehash(__n);}
331 template <class _Value, class _Hash, class _Pred, class _Alloc>
332 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(size_type __n,
333 const hasher& __hf, const key_equal& __eql)
334 : __table_(__hf, __eql)
336 __table_.rehash(__n);
339 template <class _Value, class _Hash, class _Pred, class _Alloc>
340 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(size_type __n,
341 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
342 : __table_(__hf, __eql, __a)
344 __table_.rehash(__n);
347 template <class _Value, class _Hash, class _Pred, class _Alloc>
348 template <class _InputIterator>
349 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(
350 _InputIterator __first, _InputIterator __last)
352 __table_.rehash(193);
353 insert(__first, __last);
356 template <class _Value, class _Hash, class _Pred, class _Alloc>
357 template <class _InputIterator>
358 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(
359 _InputIterator __first, _InputIterator __last, size_type __n,
360 const hasher& __hf, const key_equal& __eql)
361 : __table_(__hf, __eql)
363 __table_.rehash(__n);
364 insert(__first, __last);
367 template <class _Value, class _Hash, class _Pred, class _Alloc>
368 template <class _InputIterator>
369 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(
370 _InputIterator __first, _InputIterator __last, size_type __n,
371 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
372 : __table_(__hf, __eql, __a)
374 __table_.rehash(__n);
375 insert(__first, __last);
378 template <class _Value, class _Hash, class _Pred, class _Alloc>
379 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(
381 : __table_(__u.__table_)
383 __table_.rehash(__u.bucket_count());
384 insert(__u.begin(), __u.end());
387 template <class _Value, class _Hash, class _Pred, class _Alloc>
388 template <class _InputIterator>
391 hash_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
392 _InputIterator __last)
394 for (; __first != __last; ++__first)
395 __table_.__insert_unique(*__first);
398 template <class _Value, class _Hash, class _Pred, class _Alloc>
399 inline _LIBCPP_INLINE_VISIBILITY
401 swap(hash_set<_Value, _Hash, _Pred, _Alloc>& __x,
402 hash_set<_Value, _Hash, _Pred, _Alloc>& __y)
407 template <class _Value, class _Hash, class _Pred, class _Alloc>
409 operator==(const hash_set<_Value, _Hash, _Pred, _Alloc>& __x,
410 const hash_set<_Value, _Hash, _Pred, _Alloc>& __y)
412 if (__x.size() != __y.size())
414 typedef typename hash_set<_Value, _Hash, _Pred, _Alloc>::const_iterator
416 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();
419 const_iterator __j = __y.find(*__i);
420 if (__j == __ey || !(*__i == *__j))
426 template <class _Value, class _Hash, class _Pred, class _Alloc>
427 inline _LIBCPP_INLINE_VISIBILITY
429 operator!=(const hash_set<_Value, _Hash, _Pred, _Alloc>& __x,
430 const hash_set<_Value, _Hash, _Pred, _Alloc>& __y)
432 return !(__x == __y);
435 template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>,
436 class _Alloc = allocator<_Value> >
437 class _LIBCPP_TEMPLATE_VIS hash_multiset
441 typedef _Value key_type;
442 typedef key_type value_type;
443 typedef _Hash hasher;
444 typedef _Pred key_equal;
445 typedef _Alloc allocator_type;
446 typedef value_type& reference;
447 typedef const value_type& const_reference;
450 typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
455 typedef typename __table::pointer pointer;
456 typedef typename __table::const_pointer const_pointer;
457 typedef typename __table::size_type size_type;
458 typedef typename __table::difference_type difference_type;
460 typedef typename __table::const_iterator iterator;
461 typedef typename __table::const_iterator const_iterator;
463 _LIBCPP_INLINE_VISIBILITY
464 hash_multiset() {__table_.rehash(193);}
465 explicit hash_multiset(size_type __n, const hasher& __hf = hasher(),
466 const key_equal& __eql = key_equal());
467 hash_multiset(size_type __n, const hasher& __hf,
468 const key_equal& __eql, const allocator_type& __a);
469 template <class _InputIterator>
470 hash_multiset(_InputIterator __first, _InputIterator __last);
471 template <class _InputIterator>
472 hash_multiset(_InputIterator __first, _InputIterator __last,
473 size_type __n, const hasher& __hf = hasher(),
474 const key_equal& __eql = key_equal());
475 template <class _InputIterator>
476 hash_multiset(_InputIterator __first, _InputIterator __last,
477 size_type __n , const hasher& __hf,
478 const key_equal& __eql, const allocator_type& __a);
479 hash_multiset(const hash_multiset& __u);
481 _LIBCPP_INLINE_VISIBILITY
482 allocator_type get_allocator() const
483 {return allocator_type(__table_.__node_alloc());}
485 _LIBCPP_INLINE_VISIBILITY
486 bool empty() const {return __table_.size() == 0;}
487 _LIBCPP_INLINE_VISIBILITY
488 size_type size() const {return __table_.size();}
489 _LIBCPP_INLINE_VISIBILITY
490 size_type max_size() const {return __table_.max_size();}
492 _LIBCPP_INLINE_VISIBILITY
493 iterator begin() {return __table_.begin();}
494 _LIBCPP_INLINE_VISIBILITY
495 iterator end() {return __table_.end();}
496 _LIBCPP_INLINE_VISIBILITY
497 const_iterator begin() const {return __table_.begin();}
498 _LIBCPP_INLINE_VISIBILITY
499 const_iterator end() const {return __table_.end();}
501 _LIBCPP_INLINE_VISIBILITY
502 iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
503 _LIBCPP_INLINE_VISIBILITY
504 iterator insert(const_iterator, const value_type& __x) {return insert(__x);}
505 template <class _InputIterator>
506 _LIBCPP_INLINE_VISIBILITY
507 void insert(_InputIterator __first, _InputIterator __last);
509 _LIBCPP_INLINE_VISIBILITY
510 void erase(const_iterator __p) {__table_.erase(__p);}
511 _LIBCPP_INLINE_VISIBILITY
512 size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
513 _LIBCPP_INLINE_VISIBILITY
514 void erase(const_iterator __first, const_iterator __last)
515 {__table_.erase(__first, __last);}
516 _LIBCPP_INLINE_VISIBILITY
517 void clear() {__table_.clear();}
519 _LIBCPP_INLINE_VISIBILITY
520 void swap(hash_multiset& __u) {__table_.swap(__u.__table_);}
522 _LIBCPP_INLINE_VISIBILITY
523 hasher hash_funct() const {return __table_.hash_function();}
524 _LIBCPP_INLINE_VISIBILITY
525 key_equal key_eq() const {return __table_.key_eq();}
527 _LIBCPP_INLINE_VISIBILITY
528 iterator find(const key_type& __k) {return __table_.find(__k);}
529 _LIBCPP_INLINE_VISIBILITY
530 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
531 _LIBCPP_INLINE_VISIBILITY
532 size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
533 _LIBCPP_INLINE_VISIBILITY
534 pair<iterator, iterator> equal_range(const key_type& __k)
535 {return __table_.__equal_range_multi(__k);}
536 _LIBCPP_INLINE_VISIBILITY
537 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
538 {return __table_.__equal_range_multi(__k);}
540 _LIBCPP_INLINE_VISIBILITY
541 size_type bucket_count() const {return __table_.bucket_count();}
542 _LIBCPP_INLINE_VISIBILITY
543 size_type max_bucket_count() const {return __table_.max_bucket_count();}
545 _LIBCPP_INLINE_VISIBILITY
546 size_type elems_in_bucket(size_type __n) const {return __table_.bucket_size(__n);}
548 _LIBCPP_INLINE_VISIBILITY
549 void resize(size_type __n) {__table_.rehash(__n);}
552 template <class _Value, class _Hash, class _Pred, class _Alloc>
553 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
554 size_type __n, const hasher& __hf, const key_equal& __eql)
555 : __table_(__hf, __eql)
557 __table_.rehash(__n);
560 template <class _Value, class _Hash, class _Pred, class _Alloc>
561 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
562 size_type __n, const hasher& __hf, const key_equal& __eql,
563 const allocator_type& __a)
564 : __table_(__hf, __eql, __a)
566 __table_.rehash(__n);
569 template <class _Value, class _Hash, class _Pred, class _Alloc>
570 template <class _InputIterator>
571 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
572 _InputIterator __first, _InputIterator __last)
574 __table_.rehash(193);
575 insert(__first, __last);
578 template <class _Value, class _Hash, class _Pred, class _Alloc>
579 template <class _InputIterator>
580 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
581 _InputIterator __first, _InputIterator __last, size_type __n,
582 const hasher& __hf, const key_equal& __eql)
583 : __table_(__hf, __eql)
585 __table_.rehash(__n);
586 insert(__first, __last);
589 template <class _Value, class _Hash, class _Pred, class _Alloc>
590 template <class _InputIterator>
591 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
592 _InputIterator __first, _InputIterator __last, size_type __n,
593 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
594 : __table_(__hf, __eql, __a)
596 __table_.rehash(__n);
597 insert(__first, __last);
600 template <class _Value, class _Hash, class _Pred, class _Alloc>
601 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
602 const hash_multiset& __u)
603 : __table_(__u.__table_)
605 __table_.rehash(__u.bucket_count());
606 insert(__u.begin(), __u.end());
609 template <class _Value, class _Hash, class _Pred, class _Alloc>
610 template <class _InputIterator>
613 hash_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
614 _InputIterator __last)
616 for (; __first != __last; ++__first)
617 __table_.__insert_multi(*__first);
620 template <class _Value, class _Hash, class _Pred, class _Alloc>
621 inline _LIBCPP_INLINE_VISIBILITY
623 swap(hash_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
624 hash_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
629 template <class _Value, class _Hash, class _Pred, class _Alloc>
631 operator==(const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
632 const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
634 if (__x.size() != __y.size())
636 typedef typename hash_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator
638 typedef pair<const_iterator, const_iterator> _EqRng;
639 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;)
641 _EqRng __xeq = __x.equal_range(*__i);
642 _EqRng __yeq = __y.equal_range(*__i);
643 if (_VSTD::distance(__xeq.first, __xeq.second) !=
644 _VSTD::distance(__yeq.first, __yeq.second) ||
645 !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first))
652 template <class _Value, class _Hash, class _Pred, class _Alloc>
653 inline _LIBCPP_INLINE_VISIBILITY
655 operator!=(const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
656 const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
658 return !(__x == __y);
663 #endif // _LIBCPP_HASH_SET