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