libstdc++
hash_set
Go to the documentation of this file.
1 // Hashing set implementation -*- C++ -*-
2 
3 // Copyright (C) 2001-2020 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 
67 namespace __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 
474 namespace 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