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 #include "backward_warning.h"
61 #include <bits/c++config.h>
62 #include <backward/hashtable.h>
63 #include <bits/concept_check.h>
64 
65 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)
66 
67  using std::equal_to;
68  using std::allocator;
69  using std::pair;
70  using std::_Identity;
71 
72  /**
73  * This is an SGI extension.
74  * @ingroup SGIextensions
75  * @doctodo
76  */
77  template<class _Value, class _HashFcn = hash<_Value>,
78  class _EqualKey = equal_to<_Value>,
79  class _Alloc = allocator<_Value> >
80  class hash_set
81  {
82  // concept requirements
83  __glibcxx_class_requires(_Value, _SGIAssignableConcept)
84  __glibcxx_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept)
85  __glibcxx_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept)
86 
87  private:
88  typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>,
89  _EqualKey, _Alloc> _Ht;
90  _Ht _M_ht;
91 
92  public:
93  typedef typename _Ht::key_type key_type;
94  typedef typename _Ht::value_type value_type;
95  typedef typename _Ht::hasher hasher;
96  typedef typename _Ht::key_equal key_equal;
97 
98  typedef typename _Ht::size_type size_type;
99  typedef typename _Ht::difference_type difference_type;
100  typedef typename _Alloc::pointer pointer;
101  typedef typename _Alloc::const_pointer const_pointer;
102  typedef typename _Alloc::reference reference;
103  typedef typename _Alloc::const_reference const_reference;
104 
105  typedef typename _Ht::const_iterator iterator;
106  typedef typename _Ht::const_iterator const_iterator;
107 
108  typedef typename _Ht::allocator_type allocator_type;
109 
110  hasher
111  hash_funct() const
112  { return _M_ht.hash_funct(); }
113 
114  key_equal
115  key_eq() const
116  { return _M_ht.key_eq(); }
117 
118  allocator_type
119  get_allocator() const
120  { return _M_ht.get_allocator(); }
121 
122  hash_set()
123  : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
124 
125  explicit
126  hash_set(size_type __n)
127  : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
128 
129  hash_set(size_type __n, const hasher& __hf)
130  : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
131 
132  hash_set(size_type __n, const hasher& __hf, const key_equal& __eql,
133  const allocator_type& __a = allocator_type())
134  : _M_ht(__n, __hf, __eql, __a) {}
135 
136  template<class _InputIterator>
137  hash_set(_InputIterator __f, _InputIterator __l)
138  : _M_ht(100, hasher(), key_equal(), allocator_type())
139  { _M_ht.insert_unique(__f, __l); }
140 
141  template<class _InputIterator>
142  hash_set(_InputIterator __f, _InputIterator __l, size_type __n)
143  : _M_ht(__n, 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  const hasher& __hf)
149  : _M_ht(__n, __hf, 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, const key_equal& __eql,
155  const allocator_type& __a = allocator_type())
156  : _M_ht(__n, __hf, __eql, __a)
157  { _M_ht.insert_unique(__f, __l); }
158 
159  size_type
160  size() const
161  { return _M_ht.size(); }
162 
163  size_type
164  max_size() const
165  { return _M_ht.max_size(); }
166 
167  bool
168  empty() const
169  { return _M_ht.empty(); }
170 
171  void
172  swap(hash_set& __hs)
173  { _M_ht.swap(__hs._M_ht); }
174 
175  template<class _Val, class _HF, class _EqK, class _Al>
176  friend bool
177  operator==(const hash_set<_Val, _HF, _EqK, _Al>&,
179 
180  iterator
181  begin() const
182  { return _M_ht.begin(); }
183 
184  iterator
185  end() const
186  { return _M_ht.end(); }
187 
189  insert(const value_type& __obj)
190  {
191  pair<typename _Ht::iterator, bool> __p = _M_ht.insert_unique(__obj);
192  return pair<iterator,bool>(__p.first, __p.second);
193  }
194 
195  template<class _InputIterator>
196  void
197  insert(_InputIterator __f, _InputIterator __l)
198  { _M_ht.insert_unique(__f, __l); }
199 
201  insert_noresize(const value_type& __obj)
202  {
204  = _M_ht.insert_unique_noresize(__obj);
205  return pair<iterator, bool>(__p.first, __p.second);
206  }
207 
208  iterator
209  find(const key_type& __key) const
210  { return _M_ht.find(__key); }
211 
212  size_type
213  count(const key_type& __key) const
214  { return _M_ht.count(__key); }
215 
217  equal_range(const key_type& __key) const
218  { return _M_ht.equal_range(__key); }
219 
220  size_type
221  erase(const key_type& __key)
222  {return _M_ht.erase(__key); }
223 
224  void
225  erase(iterator __it)
226  { _M_ht.erase(__it); }
227 
228  void
229  erase(iterator __f, iterator __l)
230  { _M_ht.erase(__f, __l); }
231 
232  void
233  clear()
234  { _M_ht.clear(); }
235 
236  void
237  resize(size_type __hint)
238  { _M_ht.resize(__hint); }
239 
240  size_type
241  bucket_count() const
242  { return _M_ht.bucket_count(); }
243 
244  size_type
245  max_bucket_count() const
246  { return _M_ht.max_bucket_count(); }
247 
248  size_type
249  elems_in_bucket(size_type __n) const
250  { return _M_ht.elems_in_bucket(__n); }
251  };
252 
253  template<class _Value, class _HashFcn, class _EqualKey, class _Alloc>
254  inline bool
255  operator==(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs1,
257  { return __hs1._M_ht == __hs2._M_ht; }
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 == __hs2); }
264 
265  template<class _Val, class _HashFcn, class _EqualKey, class _Alloc>
266  inline void
267  swap(hash_set<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
268  hash_set<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
269  { __hs1.swap(__hs2); }
270 
271 
272  /**
273  * This is an SGI extension.
274  * @ingroup SGIextensions
275  * @doctodo
276  */
277  template<class _Value,
278  class _HashFcn = hash<_Value>,
279  class _EqualKey = equal_to<_Value>,
280  class _Alloc = allocator<_Value> >
282  {
283  // concept requirements
284  __glibcxx_class_requires(_Value, _SGIAssignableConcept)
285  __glibcxx_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept)
286  __glibcxx_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept)
287 
288  private:
289  typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>,
290  _EqualKey, _Alloc> _Ht;
291  _Ht _M_ht;
292 
293  public:
294  typedef typename _Ht::key_type key_type;
295  typedef typename _Ht::value_type value_type;
296  typedef typename _Ht::hasher hasher;
297  typedef typename _Ht::key_equal key_equal;
298 
299  typedef typename _Ht::size_type size_type;
300  typedef typename _Ht::difference_type difference_type;
301  typedef typename _Alloc::pointer pointer;
302  typedef typename _Alloc::const_pointer const_pointer;
303  typedef typename _Alloc::reference reference;
304  typedef typename _Alloc::const_reference const_reference;
305 
306  typedef typename _Ht::const_iterator iterator;
307  typedef typename _Ht::const_iterator const_iterator;
308 
309  typedef typename _Ht::allocator_type allocator_type;
310 
311  hasher
312  hash_funct() const
313  { return _M_ht.hash_funct(); }
314 
315  key_equal
316  key_eq() const
317  { return _M_ht.key_eq(); }
318 
319  allocator_type
320  get_allocator() const
321  { return _M_ht.get_allocator(); }
322 
323  hash_multiset()
324  : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
325 
326  explicit
327  hash_multiset(size_type __n)
328  : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
329 
330  hash_multiset(size_type __n, const hasher& __hf)
331  : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
332 
333  hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql,
334  const allocator_type& __a = allocator_type())
335  : _M_ht(__n, __hf, __eql, __a) {}
336 
337  template<class _InputIterator>
338  hash_multiset(_InputIterator __f, _InputIterator __l)
339  : _M_ht(100, hasher(), key_equal(), allocator_type())
340  { _M_ht.insert_equal(__f, __l); }
341 
342  template<class _InputIterator>
343  hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n)
344  : _M_ht(__n, 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  const hasher& __hf)
350  : _M_ht(__n, __hf, 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, const key_equal& __eql,
356  const allocator_type& __a = allocator_type())
357  : _M_ht(__n, __hf, __eql, __a)
358  { _M_ht.insert_equal(__f, __l); }
359 
360  size_type
361  size() const
362  { return _M_ht.size(); }
363 
364  size_type
365  max_size() const
366  { return _M_ht.max_size(); }
367 
368  bool
369  empty() const
370  { return _M_ht.empty(); }
371 
372  void
373  swap(hash_multiset& hs)
374  { _M_ht.swap(hs._M_ht); }
375 
376  template<class _Val, class _HF, class _EqK, class _Al>
377  friend bool
378  operator==(const hash_multiset<_Val, _HF, _EqK, _Al>&,
380 
381  iterator
382  begin() const
383  { return _M_ht.begin(); }
384 
385  iterator
386  end() const
387  { return _M_ht.end(); }
388 
389  iterator
390  insert(const value_type& __obj)
391  { return _M_ht.insert_equal(__obj); }
392 
393  template<class _InputIterator>
394  void
395  insert(_InputIterator __f, _InputIterator __l)
396  { _M_ht.insert_equal(__f,__l); }
397 
398  iterator
399  insert_noresize(const value_type& __obj)
400  { return _M_ht.insert_equal_noresize(__obj); }
401 
402  iterator
403  find(const key_type& __key) const
404  { return _M_ht.find(__key); }
405 
406  size_type
407  count(const key_type& __key) const
408  { return _M_ht.count(__key); }
409 
411  equal_range(const key_type& __key) const
412  { return _M_ht.equal_range(__key); }
413 
414  size_type
415  erase(const key_type& __key)
416  { return _M_ht.erase(__key); }
417 
418  void
419  erase(iterator __it)
420  { _M_ht.erase(__it); }
421 
422  void
423  erase(iterator __f, iterator __l)
424  { _M_ht.erase(__f, __l); }
425 
426  void
427  clear()
428  { _M_ht.clear(); }
429 
430  void
431  resize(size_type __hint)
432  { _M_ht.resize(__hint); }
433 
434  size_type
435  bucket_count() const
436  { return _M_ht.bucket_count(); }
437 
438  size_type
439  max_bucket_count() const
440  { return _M_ht.max_bucket_count(); }
441 
442  size_type
443  elems_in_bucket(size_type __n) const
444  { return _M_ht.elems_in_bucket(__n); }
445  };
446 
447  template<class _Val, class _HashFcn, class _EqualKey, class _Alloc>
448  inline bool
449  operator==(const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
451  { return __hs1._M_ht == __hs2._M_ht; }
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 == __hs2); }
458 
459  template<class _Val, class _HashFcn, class _EqualKey, class _Alloc>
460  inline void
461  swap(hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
462  hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
463  { __hs1.swap(__hs2); }
464 
465 _GLIBCXX_END_NAMESPACE
466 
467 _GLIBCXX_BEGIN_NAMESPACE(std)
468 
469  // Specialization of insert_iterator so that it will work for hash_set
470  // and hash_multiset.
471  template<class _Value, class _HashFcn, class _EqualKey, class _Alloc>
472  class insert_iterator<__gnu_cxx::hash_set<_Value, _HashFcn,
473  _EqualKey, _Alloc> >
474  {
475  protected:
477  _Container;
478  _Container* container;
479 
480  public:
481  typedef _Container container_type;
482  typedef output_iterator_tag iterator_category;
483  typedef void value_type;
484  typedef void difference_type;
485  typedef void pointer;
486  typedef void reference;
487 
488  insert_iterator(_Container& __x)
489  : container(&__x) {}
490 
491  insert_iterator(_Container& __x, typename _Container::iterator)
492  : container(&__x) {}
493 
494  insert_iterator<_Container>&
495  operator=(const typename _Container::value_type& __value)
496  {
497  container->insert(__value);
498  return *this;
499  }
500 
501  insert_iterator<_Container>&
502  operator*()
503  { return *this; }
504 
505  insert_iterator<_Container>&
506  operator++()
507  { return *this; }
508 
509  insert_iterator<_Container>&
510  operator++(int)
511  { return *this; }
512  };
513 
514  template<class _Value, class _HashFcn, class _EqualKey, class _Alloc>
515  class insert_iterator<__gnu_cxx::hash_multiset<_Value, _HashFcn,
516  _EqualKey, _Alloc> >
517  {
518  protected:
520  _Container;
521  _Container* container;
522  typename _Container::iterator iter;
523 
524  public:
525  typedef _Container container_type;
526  typedef output_iterator_tag iterator_category;
527  typedef void value_type;
528  typedef void difference_type;
529  typedef void pointer;
530  typedef void reference;
531 
532  insert_iterator(_Container& __x)
533  : container(&__x) {}
534 
535  insert_iterator(_Container& __x, typename _Container::iterator)
536  : container(&__x) {}
537 
538  insert_iterator<_Container>&
539  operator=(const typename _Container::value_type& __value)
540  {
541  container->insert(__value);
542  return *this;
543  }
544 
545  insert_iterator<_Container>&
546  operator*()
547  { return *this; }
548 
549  insert_iterator<_Container>&
550  operator++()
551  { return *this; }
552 
553  insert_iterator<_Container>&
554  operator++(int) { return *this; }
555  };
556 
557 _GLIBCXX_END_NAMESPACE
558 
559 #endif