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