libstdc++
hash_set
Go to the documentation of this file.
1// Hashing set implementation -*- C++ -*-
2
3// Copyright (C) 2001-2021 Free Software Foundation, Inc.
4//
5// This file is part of the GNU ISO C++ Library. This library is free
6// software; you can redistribute it and/or modify it under the
7// terms of the GNU General Public License as published by the
8// Free Software Foundation; either version 3, or (at your option)
9// any later version.
10
11// This library is distributed in the hope that it will be useful,
12// but WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14// GNU General Public License for more details.
15
16// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.
19
20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23// <http://www.gnu.org/licenses/>.
24
25/*
26 * Copyright (c) 1996
27 * Silicon Graphics Computer Systems, Inc.
28 *
29 * Permission to use, copy, modify, distribute and sell this software
30 * and its documentation for any purpose is hereby granted without fee,
31 * provided that the above copyright notice appear in all copies and
32 * that both that copyright notice and this permission notice appear
33 * in supporting documentation. Silicon Graphics makes no
34 * representations about the suitability of this software for any
35 * purpose. It is provided "as is" without express or implied warranty.
36 *
37 *
38 * Copyright (c) 1994
39 * Hewlett-Packard Company
40 *
41 * Permission to use, copy, modify, distribute and sell this software
42 * and its documentation for any purpose is hereby granted without fee,
43 * provided that the above copyright notice appear in all copies and
44 * that both that copyright notice and this permission notice appear
45 * in supporting documentation. Hewlett-Packard Company makes no
46 * representations about the suitability of this software for any
47 * purpose. It is provided "as is" without express or implied warranty.
48 *
49 */
50
51/** @file backward/hash_set
52 * This file is a GNU extension to the Standard C++ Library (possibly
53 * containing extensions from the HP/SGI STL subset).
54 */
55
56#ifndef _BACKWARD_HASH_SET
57#define _BACKWARD_HASH_SET 1
58
59#ifndef _GLIBCXX_PERMIT_BACKWARD_HASH
60#include <backward/backward_warning.h>
61#endif
62
63#include <bits/c++config.h>
64#include <backward/hashtable.h>
65#include <bits/concept_check.h>
66
67namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
68{
69_GLIBCXX_BEGIN_NAMESPACE_VERSION
70
71 using std::equal_to;
72 using std::allocator;
73 using std::pair;
74 using std::_Identity;
75
76 /**
77 * This is an SGI extension.
78 * @ingroup SGIextensions
79 * @doctodo
80 */
81 template<class _Value, class _HashFcn = hash<_Value>,
82 class _EqualKey = equal_to<_Value>,
83 class _Alloc = allocator<_Value> >
84 class hash_set
85 {
86 // concept requirements
87 __glibcxx_class_requires(_Value, _SGIAssignableConcept)
88 __glibcxx_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept)
89 __glibcxx_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept)
90
91 typedef __alloc_traits<_Alloc> _Alloc_traits;
92
93 private:
94 typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>,
95 _EqualKey, _Alloc> _Ht;
96 _Ht _M_ht;
97
98 public:
99 typedef typename _Ht::key_type key_type;
100 typedef typename _Ht::value_type value_type;
101 typedef typename _Ht::hasher hasher;
102 typedef typename _Ht::key_equal key_equal;
103
104 typedef typename _Ht::size_type size_type;
105 typedef typename _Ht::difference_type difference_type;
106 typedef typename _Alloc_traits::pointer pointer;
107 typedef typename _Alloc_traits::const_pointer const_pointer;
108 typedef typename _Alloc_traits::reference reference;
109 typedef typename _Alloc_traits::const_reference const_reference;
110
111 typedef typename _Ht::const_iterator iterator;
112 typedef typename _Ht::const_iterator const_iterator;
113
114 typedef typename _Ht::allocator_type allocator_type;
115
116 hasher
117 hash_funct() const
118 { return _M_ht.hash_funct(); }
119
120 key_equal
121 key_eq() const
122 { return _M_ht.key_eq(); }
123
124 allocator_type
125 get_allocator() const
126 { return _M_ht.get_allocator(); }
127
128 hash_set()
129 : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
130
131 explicit
132 hash_set(size_type __n)
133 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
134
135 hash_set(size_type __n, const hasher& __hf)
136 : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
137
138 hash_set(size_type __n, const hasher& __hf, const key_equal& __eql,
139 const allocator_type& __a = allocator_type())
140 : _M_ht(__n, __hf, __eql, __a) {}
141
142 template<class _InputIterator>
143 hash_set(_InputIterator __f, _InputIterator __l)
144 : _M_ht(100, hasher(), key_equal(), allocator_type())
145 { _M_ht.insert_unique(__f, __l); }
146
147 template<class _InputIterator>
148 hash_set(_InputIterator __f, _InputIterator __l, size_type __n)
149 : _M_ht(__n, hasher(), key_equal(), allocator_type())
150 { _M_ht.insert_unique(__f, __l); }
151
152 template<class _InputIterator>
153 hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
154 const hasher& __hf)
155 : _M_ht(__n, __hf, key_equal(), allocator_type())
156 { _M_ht.insert_unique(__f, __l); }
157
158 template<class _InputIterator>
159 hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
160 const hasher& __hf, const key_equal& __eql,
161 const allocator_type& __a = allocator_type())
162 : _M_ht(__n, __hf, __eql, __a)
163 { _M_ht.insert_unique(__f, __l); }
164
165 size_type
166 size() const
167 { return _M_ht.size(); }
168
169 size_type
170 max_size() const
171 { return _M_ht.max_size(); }
172
173 _GLIBCXX_NODISCARD bool
174 empty() const
175 { return _M_ht.empty(); }
176
177 void
178 swap(hash_set& __hs)
179 { _M_ht.swap(__hs._M_ht); }
180
181 template<class _Val, class _HF, class _EqK, class _Al>
182 friend bool
183 operator==(const hash_set<_Val, _HF, _EqK, _Al>&,
184 const hash_set<_Val, _HF, _EqK, _Al>&);
185
186 iterator
187 begin() const
188 { return _M_ht.begin(); }
189
190 iterator
191 end() const
192 { return _M_ht.end(); }
193
194 pair<iterator, bool>
195 insert(const value_type& __obj)
196 {
197 pair<typename _Ht::iterator, bool> __p = _M_ht.insert_unique(__obj);
198 return pair<iterator,bool>(__p.first, __p.second);
199 }
200
201 template<class _InputIterator>
202 void
203 insert(_InputIterator __f, _InputIterator __l)
204 { _M_ht.insert_unique(__f, __l); }
205
206 pair<iterator, bool>
207 insert_noresize(const value_type& __obj)
208 {
209 pair<typename _Ht::iterator, bool> __p
210 = _M_ht.insert_unique_noresize(__obj);
211 return pair<iterator, bool>(__p.first, __p.second);
212 }
213
214 iterator
215 find(const key_type& __key) const
216 { return _M_ht.find(__key); }
217
218 size_type
219 count(const key_type& __key) const
220 { return _M_ht.count(__key); }
221
222 pair<iterator, iterator>
223 equal_range(const key_type& __key) const
224 { return _M_ht.equal_range(__key); }
225
226 size_type
227 erase(const key_type& __key)
228 {return _M_ht.erase(__key); }
229
230 void
231 erase(iterator __it)
232 { _M_ht.erase(__it); }
233
234 void
235 erase(iterator __f, iterator __l)
236 { _M_ht.erase(__f, __l); }
237
238 void
239 clear()
240 { _M_ht.clear(); }
241
242 void
243 resize(size_type __hint)
244 { _M_ht.resize(__hint); }
245
246 size_type
247 bucket_count() const
248 { return _M_ht.bucket_count(); }
249
250 size_type
251 max_bucket_count() const
252 { return _M_ht.max_bucket_count(); }
253
254 size_type
255 elems_in_bucket(size_type __n) const
256 { return _M_ht.elems_in_bucket(__n); }
257 };
258
259 template<class _Value, class _HashFcn, class _EqualKey, class _Alloc>
260 inline bool
261 operator==(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs1,
262 const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs2)
263 { return __hs1._M_ht == __hs2._M_ht; }
264
265 template<class _Value, class _HashFcn, class _EqualKey, class _Alloc>
266 inline bool
267 operator!=(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs1,
268 const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs2)
269 { return !(__hs1 == __hs2); }
270
271 template<class _Val, class _HashFcn, class _EqualKey, class _Alloc>
272 inline void
273 swap(hash_set<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
274 hash_set<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
275 { __hs1.swap(__hs2); }
276
277
278 /**
279 * This is an SGI extension.
280 * @ingroup SGIextensions
281 * @doctodo
282 */
283 template<class _Value,
284 class _HashFcn = hash<_Value>,
285 class _EqualKey = equal_to<_Value>,
286 class _Alloc = allocator<_Value> >
287 class hash_multiset
288 {
289 // concept requirements
290 __glibcxx_class_requires(_Value, _SGIAssignableConcept)
291 __glibcxx_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept)
292 __glibcxx_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept)
293
294 private:
295 typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>,
296 _EqualKey, _Alloc> _Ht;
297 _Ht _M_ht;
298
299 public:
300 typedef typename _Ht::key_type key_type;
301 typedef typename _Ht::value_type value_type;
302 typedef typename _Ht::hasher hasher;
303 typedef typename _Ht::key_equal key_equal;
304
305 typedef typename _Ht::size_type size_type;
306 typedef typename _Ht::difference_type difference_type;
307 typedef typename _Alloc::pointer pointer;
308 typedef typename _Alloc::const_pointer const_pointer;
309 typedef typename _Alloc::reference reference;
310 typedef typename _Alloc::const_reference const_reference;
311
312 typedef typename _Ht::const_iterator iterator;
313 typedef typename _Ht::const_iterator const_iterator;
314
315 typedef typename _Ht::allocator_type allocator_type;
316
317 hasher
318 hash_funct() const
319 { return _M_ht.hash_funct(); }
320
321 key_equal
322 key_eq() const
323 { return _M_ht.key_eq(); }
324
325 allocator_type
326 get_allocator() const
327 { return _M_ht.get_allocator(); }
328
329 hash_multiset()
330 : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
331
332 explicit
333 hash_multiset(size_type __n)
334 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
335
336 hash_multiset(size_type __n, const hasher& __hf)
337 : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
338
339 hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql,
340 const allocator_type& __a = allocator_type())
341 : _M_ht(__n, __hf, __eql, __a) {}
342
343 template<class _InputIterator>
344 hash_multiset(_InputIterator __f, _InputIterator __l)
345 : _M_ht(100, hasher(), key_equal(), allocator_type())
346 { _M_ht.insert_equal(__f, __l); }
347
348 template<class _InputIterator>
349 hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n)
350 : _M_ht(__n, hasher(), key_equal(), allocator_type())
351 { _M_ht.insert_equal(__f, __l); }
352
353 template<class _InputIterator>
354 hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
355 const hasher& __hf)
356 : _M_ht(__n, __hf, key_equal(), allocator_type())
357 { _M_ht.insert_equal(__f, __l); }
358
359 template<class _InputIterator>
360 hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
361 const hasher& __hf, const key_equal& __eql,
362 const allocator_type& __a = allocator_type())
363 : _M_ht(__n, __hf, __eql, __a)
364 { _M_ht.insert_equal(__f, __l); }
365
366 size_type
367 size() const
368 { return _M_ht.size(); }
369
370 size_type
371 max_size() const
372 { return _M_ht.max_size(); }
373
374 _GLIBCXX_NODISCARD bool
375 empty() const
376 { return _M_ht.empty(); }
377
378 void
379 swap(hash_multiset& hs)
380 { _M_ht.swap(hs._M_ht); }
381
382 template<class _Val, class _HF, class _EqK, class _Al>
383 friend bool
384 operator==(const hash_multiset<_Val, _HF, _EqK, _Al>&,
385 const hash_multiset<_Val, _HF, _EqK, _Al>&);
386
387 iterator
388 begin() const
389 { return _M_ht.begin(); }
390
391 iterator
392 end() const
393 { return _M_ht.end(); }
394
395 iterator
396 insert(const value_type& __obj)
397 { return _M_ht.insert_equal(__obj); }
398
399 template<class _InputIterator>
400 void
401 insert(_InputIterator __f, _InputIterator __l)
402 { _M_ht.insert_equal(__f,__l); }
403
404 iterator
405 insert_noresize(const value_type& __obj)
406 { return _M_ht.insert_equal_noresize(__obj); }
407
408 iterator
409 find(const key_type& __key) const
410 { return _M_ht.find(__key); }
411
412 size_type
413 count(const key_type& __key) const
414 { return _M_ht.count(__key); }
415
416 pair<iterator, iterator>
417 equal_range(const key_type& __key) const
418 { return _M_ht.equal_range(__key); }
419
420 size_type
421 erase(const key_type& __key)
422 { return _M_ht.erase(__key); }
423
424 void
425 erase(iterator __it)
426 { _M_ht.erase(__it); }
427
428 void
429 erase(iterator __f, iterator __l)
430 { _M_ht.erase(__f, __l); }
431
432 void
433 clear()
434 { _M_ht.clear(); }
435
436 void
437 resize(size_type __hint)
438 { _M_ht.resize(__hint); }
439
440 size_type
441 bucket_count() const
442 { return _M_ht.bucket_count(); }
443
444 size_type
445 max_bucket_count() const
446 { return _M_ht.max_bucket_count(); }
447
448 size_type
449 elems_in_bucket(size_type __n) const
450 { return _M_ht.elems_in_bucket(__n); }
451 };
452
453 template<class _Val, class _HashFcn, class _EqualKey, class _Alloc>
454 inline bool
455 operator==(const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
456 const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
457 { return __hs1._M_ht == __hs2._M_ht; }
458
459 template<class _Val, class _HashFcn, class _EqualKey, class _Alloc>
460 inline bool
461 operator!=(const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
462 const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
463 { return !(__hs1 == __hs2); }
464
465 template<class _Val, class _HashFcn, class _EqualKey, class _Alloc>
466 inline void
467 swap(hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
468 hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
469 { __hs1.swap(__hs2); }
470
471_GLIBCXX_END_NAMESPACE_VERSION
472} // namespace
473
474namespace std _GLIBCXX_VISIBILITY(default)
475{
476_GLIBCXX_BEGIN_NAMESPACE_VERSION
477
478 // Specialization of insert_iterator so that it will work for hash_set
479 // and hash_multiset.
480 template<class _Value, class _HashFcn, class _EqualKey, class _Alloc>
481 class insert_iterator<__gnu_cxx::hash_set<_Value, _HashFcn,
482 _EqualKey, _Alloc> >
483 {
484 protected:
485 typedef __gnu_cxx::hash_set<_Value, _HashFcn, _EqualKey, _Alloc>
486 _Container;
487 _Container* container;
488
489 public:
490 typedef _Container container_type;
491 typedef output_iterator_tag iterator_category;
492 typedef void value_type;
493 typedef void difference_type;
494 typedef void pointer;
495 typedef void reference;
496
497 insert_iterator(_Container& __x)
498 : container(&__x) {}
499
500 insert_iterator(_Container& __x, typename _Container::iterator)
501 : container(&__x) {}
502
503 insert_iterator<_Container>&
504 operator=(const typename _Container::value_type& __value)
505 {
506 container->insert(__value);
507 return *this;
508 }
509
510 insert_iterator<_Container>&
511 operator*()
512 { return *this; }
513
514 insert_iterator<_Container>&
515 operator++()
516 { return *this; }
517
518 insert_iterator<_Container>&
519 operator++(int)
520 { return *this; }
521 };
522
523 template<class _Value, class _HashFcn, class _EqualKey, class _Alloc>
524 class insert_iterator<__gnu_cxx::hash_multiset<_Value, _HashFcn,
525 _EqualKey, _Alloc> >
526 {
527 protected:
528 typedef __gnu_cxx::hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc>
529 _Container;
530 _Container* container;
531 typename _Container::iterator iter;
532
533 public:
534 typedef _Container container_type;
535 typedef output_iterator_tag iterator_category;
536 typedef void value_type;
537 typedef void difference_type;
538 typedef void pointer;
539 typedef void reference;
540
541 insert_iterator(_Container& __x)
542 : container(&__x) {}
543
544 insert_iterator(_Container& __x, typename _Container::iterator)
545 : container(&__x) {}
546
547 insert_iterator<_Container>&
548 operator=(const typename _Container::value_type& __value)
549 {
550 container->insert(__value);
551 return *this;
552 }
553
554 insert_iterator<_Container>&
555 operator*()
556 { return *this; }
557
558 insert_iterator<_Container>&
559 operator++()
560 { return *this; }
561
562 insert_iterator<_Container>&
563 operator++(int) { return *this; }
564 };
565
566_GLIBCXX_END_NAMESPACE_VERSION
567} // namespace
568
569#endif