libstdc++
hash_set
Go to the documentation of this file.
1 // Hashing set implementation -*- C++ -*-
2 
3 // Copyright (C) 2001-2014 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_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  private:
92  typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>,
93  _EqualKey, _Alloc> _Ht;
94  _Ht _M_ht;
95 
96  public:
97  typedef typename _Ht::key_type key_type;
98  typedef typename _Ht::value_type value_type;
99  typedef typename _Ht::hasher hasher;
100  typedef typename _Ht::key_equal key_equal;
101 
102  typedef typename _Ht::size_type size_type;
103  typedef typename _Ht::difference_type difference_type;
104  typedef typename _Alloc::pointer pointer;
105  typedef typename _Alloc::const_pointer const_pointer;
106  typedef typename _Alloc::reference reference;
107  typedef typename _Alloc::const_reference const_reference;
108 
109  typedef typename _Ht::const_iterator iterator;
110  typedef typename _Ht::const_iterator const_iterator;
111 
112  typedef typename _Ht::allocator_type allocator_type;
113 
114  hasher
115  hash_funct() const
116  { return _M_ht.hash_funct(); }
117 
118  key_equal
119  key_eq() const
120  { return _M_ht.key_eq(); }
121 
122  allocator_type
123  get_allocator() const
124  { return _M_ht.get_allocator(); }
125 
126  hash_set()
127  : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
128 
129  explicit
130  hash_set(size_type __n)
131  : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
132 
133  hash_set(size_type __n, const hasher& __hf)
134  : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
135 
136  hash_set(size_type __n, const hasher& __hf, const key_equal& __eql,
137  const allocator_type& __a = allocator_type())
138  : _M_ht(__n, __hf, __eql, __a) {}
139 
140  template<class _InputIterator>
141  hash_set(_InputIterator __f, _InputIterator __l)
142  : _M_ht(100, hasher(), key_equal(), allocator_type())
143  { _M_ht.insert_unique(__f, __l); }
144 
145  template<class _InputIterator>
146  hash_set(_InputIterator __f, _InputIterator __l, size_type __n)
147  : _M_ht(__n, hasher(), key_equal(), allocator_type())
148  { _M_ht.insert_unique(__f, __l); }
149 
150  template<class _InputIterator>
151  hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
152  const hasher& __hf)
153  : _M_ht(__n, __hf, key_equal(), allocator_type())
154  { _M_ht.insert_unique(__f, __l); }
155 
156  template<class _InputIterator>
157  hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
158  const hasher& __hf, const key_equal& __eql,
159  const allocator_type& __a = allocator_type())
160  : _M_ht(__n, __hf, __eql, __a)
161  { _M_ht.insert_unique(__f, __l); }
162 
163  size_type
164  size() const
165  { return _M_ht.size(); }
166 
167  size_type
168  max_size() const
169  { return _M_ht.max_size(); }
170 
171  bool
172  empty() const
173  { return _M_ht.empty(); }
174 
175  void
176  swap(hash_set& __hs)
177  { _M_ht.swap(__hs._M_ht); }
178 
179  template<class _Val, class _HF, class _EqK, class _Al>
180  friend bool
181  operator==(const hash_set<_Val, _HF, _EqK, _Al>&,
182  const hash_set<_Val, _HF, _EqK, _Al>&);
183 
184  iterator
185  begin() const
186  { return _M_ht.begin(); }
187 
188  iterator
189  end() const
190  { return _M_ht.end(); }
191 
192  pair<iterator, bool>
193  insert(const value_type& __obj)
194  {
195  pair<typename _Ht::iterator, bool> __p = _M_ht.insert_unique(__obj);
196  return pair<iterator,bool>(__p.first, __p.second);
197  }
198 
199  template<class _InputIterator>
200  void
201  insert(_InputIterator __f, _InputIterator __l)
202  { _M_ht.insert_unique(__f, __l); }
203 
204  pair<iterator, bool>
205  insert_noresize(const value_type& __obj)
206  {
207  pair<typename _Ht::iterator, bool> __p
208  = _M_ht.insert_unique_noresize(__obj);
209  return pair<iterator, bool>(__p.first, __p.second);
210  }
211 
212  iterator
213  find(const key_type& __key) const
214  { return _M_ht.find(__key); }
215 
216  size_type
217  count(const key_type& __key) const
218  { return _M_ht.count(__key); }
219 
220  pair<iterator, iterator>
221  equal_range(const key_type& __key) const
222  { return _M_ht.equal_range(__key); }
223 
224  size_type
225  erase(const key_type& __key)
226  {return _M_ht.erase(__key); }
227 
228  void
229  erase(iterator __it)
230  { _M_ht.erase(__it); }
231 
232  void
233  erase(iterator __f, iterator __l)
234  { _M_ht.erase(__f, __l); }
235 
236  void
237  clear()
238  { _M_ht.clear(); }
239 
240  void
241  resize(size_type __hint)
242  { _M_ht.resize(__hint); }
243 
244  size_type
245  bucket_count() const
246  { return _M_ht.bucket_count(); }
247 
248  size_type
249  max_bucket_count() const
250  { return _M_ht.max_bucket_count(); }
251 
252  size_type
253  elems_in_bucket(size_type __n) const
254  { return _M_ht.elems_in_bucket(__n); }
255  };
256 
257  template<class _Value, class _HashFcn, class _EqualKey, class _Alloc>
258  inline bool
259  operator==(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs1,
260  const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs2)
261  { return __hs1._M_ht == __hs2._M_ht; }
262 
263  template<class _Value, class _HashFcn, class _EqualKey, class _Alloc>
264  inline bool
265  operator!=(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs1,
266  const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs2)
267  { return !(__hs1 == __hs2); }
268 
269  template<class _Val, class _HashFcn, class _EqualKey, class _Alloc>
270  inline void
271  swap(hash_set<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
272  hash_set<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
273  { __hs1.swap(__hs2); }
274 
275 
276  /**
277  * This is an SGI extension.
278  * @ingroup SGIextensions
279  * @doctodo
280  */
281  template<class _Value,
282  class _HashFcn = hash<_Value>,
283  class _EqualKey = equal_to<_Value>,
284  class _Alloc = allocator<_Value> >
285  class hash_multiset
286  {
287  // concept requirements
288  __glibcxx_class_requires(_Value, _SGIAssignableConcept)
289  __glibcxx_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept)
290  __glibcxx_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept)
291 
292  private:
293  typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>,
294  _EqualKey, _Alloc> _Ht;
295  _Ht _M_ht;
296 
297  public:
298  typedef typename _Ht::key_type key_type;
299  typedef typename _Ht::value_type value_type;
300  typedef typename _Ht::hasher hasher;
301  typedef typename _Ht::key_equal key_equal;
302 
303  typedef typename _Ht::size_type size_type;
304  typedef typename _Ht::difference_type difference_type;
305  typedef typename _Alloc::pointer pointer;
306  typedef typename _Alloc::const_pointer const_pointer;
307  typedef typename _Alloc::reference reference;
308  typedef typename _Alloc::const_reference const_reference;
309 
310  typedef typename _Ht::const_iterator iterator;
311  typedef typename _Ht::const_iterator const_iterator;
312 
313  typedef typename _Ht::allocator_type allocator_type;
314 
315  hasher
316  hash_funct() const
317  { return _M_ht.hash_funct(); }
318 
319  key_equal
320  key_eq() const
321  { return _M_ht.key_eq(); }
322 
323  allocator_type
324  get_allocator() const
325  { return _M_ht.get_allocator(); }
326 
327  hash_multiset()
328  : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
329 
330  explicit
331  hash_multiset(size_type __n)
332  : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
333 
334  hash_multiset(size_type __n, const hasher& __hf)
335  : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
336 
337  hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql,
338  const allocator_type& __a = allocator_type())
339  : _M_ht(__n, __hf, __eql, __a) {}
340 
341  template<class _InputIterator>
342  hash_multiset(_InputIterator __f, _InputIterator __l)
343  : _M_ht(100, hasher(), key_equal(), allocator_type())
344  { _M_ht.insert_equal(__f, __l); }
345 
346  template<class _InputIterator>
347  hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n)
348  : _M_ht(__n, hasher(), key_equal(), allocator_type())
349  { _M_ht.insert_equal(__f, __l); }
350 
351  template<class _InputIterator>
352  hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
353  const hasher& __hf)
354  : _M_ht(__n, __hf, key_equal(), allocator_type())
355  { _M_ht.insert_equal(__f, __l); }
356 
357  template<class _InputIterator>
358  hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
359  const hasher& __hf, const key_equal& __eql,
360  const allocator_type& __a = allocator_type())
361  : _M_ht(__n, __hf, __eql, __a)
362  { _M_ht.insert_equal(__f, __l); }
363 
364  size_type
365  size() const
366  { return _M_ht.size(); }
367 
368  size_type
369  max_size() const
370  { return _M_ht.max_size(); }
371 
372  bool
373  empty() const
374  { return _M_ht.empty(); }
375 
376  void
377  swap(hash_multiset& hs)
378  { _M_ht.swap(hs._M_ht); }
379 
380  template<class _Val, class _HF, class _EqK, class _Al>
381  friend bool
382  operator==(const hash_multiset<_Val, _HF, _EqK, _Al>&,
383  const hash_multiset<_Val, _HF, _EqK, _Al>&);
384 
385  iterator
386  begin() const
387  { return _M_ht.begin(); }
388 
389  iterator
390  end() const
391  { return _M_ht.end(); }
392 
393  iterator
394  insert(const value_type& __obj)
395  { return _M_ht.insert_equal(__obj); }
396 
397  template<class _InputIterator>
398  void
399  insert(_InputIterator __f, _InputIterator __l)
400  { _M_ht.insert_equal(__f,__l); }
401 
402  iterator
403  insert_noresize(const value_type& __obj)
404  { return _M_ht.insert_equal_noresize(__obj); }
405 
406  iterator
407  find(const key_type& __key) const
408  { return _M_ht.find(__key); }
409 
410  size_type
411  count(const key_type& __key) const
412  { return _M_ht.count(__key); }
413 
414  pair<iterator, iterator>
415  equal_range(const key_type& __key) const
416  { return _M_ht.equal_range(__key); }
417 
418  size_type
419  erase(const key_type& __key)
420  { return _M_ht.erase(__key); }
421 
422  void
423  erase(iterator __it)
424  { _M_ht.erase(__it); }
425 
426  void
427  erase(iterator __f, iterator __l)
428  { _M_ht.erase(__f, __l); }
429 
430  void
431  clear()
432  { _M_ht.clear(); }
433 
434  void
435  resize(size_type __hint)
436  { _M_ht.resize(__hint); }
437 
438  size_type
439  bucket_count() const
440  { return _M_ht.bucket_count(); }
441 
442  size_type
443  max_bucket_count() const
444  { return _M_ht.max_bucket_count(); }
445 
446  size_type
447  elems_in_bucket(size_type __n) const
448  { return _M_ht.elems_in_bucket(__n); }
449  };
450 
451  template<class _Val, class _HashFcn, class _EqualKey, class _Alloc>
452  inline bool
453  operator==(const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
454  const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
455  { return __hs1._M_ht == __hs2._M_ht; }
456 
457  template<class _Val, class _HashFcn, class _EqualKey, class _Alloc>
458  inline bool
459  operator!=(const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
460  const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
461  { return !(__hs1 == __hs2); }
462 
463  template<class _Val, class _HashFcn, class _EqualKey, class _Alloc>
464  inline void
465  swap(hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
466  hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
467  { __hs1.swap(__hs2); }
468 
469 _GLIBCXX_END_NAMESPACE_VERSION
470 } // namespace
471 
472 namespace std _GLIBCXX_VISIBILITY(default)
473 {
474 _GLIBCXX_BEGIN_NAMESPACE_VERSION
475 
476  // Specialization of insert_iterator so that it will work for hash_set
477  // and hash_multiset.
478  template<class _Value, class _HashFcn, class _EqualKey, class _Alloc>
479  class insert_iterator<__gnu_cxx::hash_set<_Value, _HashFcn,
480  _EqualKey, _Alloc> >
481  {
482  protected:
483  typedef __gnu_cxx::hash_set<_Value, _HashFcn, _EqualKey, _Alloc>
484  _Container;
485  _Container* container;
486 
487  public:
488  typedef _Container container_type;
489  typedef output_iterator_tag iterator_category;
490  typedef void value_type;
491  typedef void difference_type;
492  typedef void pointer;
493  typedef void reference;
494 
495  insert_iterator(_Container& __x)
496  : container(&__x) {}
497 
498  insert_iterator(_Container& __x, typename _Container::iterator)
499  : container(&__x) {}
500 
501  insert_iterator<_Container>&
502  operator=(const typename _Container::value_type& __value)
503  {
504  container->insert(__value);
505  return *this;
506  }
507 
508  insert_iterator<_Container>&
509  operator*()
510  { return *this; }
511 
512  insert_iterator<_Container>&
513  operator++()
514  { return *this; }
515 
516  insert_iterator<_Container>&
517  operator++(int)
518  { return *this; }
519  };
520 
521  template<class _Value, class _HashFcn, class _EqualKey, class _Alloc>
522  class insert_iterator<__gnu_cxx::hash_multiset<_Value, _HashFcn,
523  _EqualKey, _Alloc> >
524  {
525  protected:
526  typedef __gnu_cxx::hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc>
527  _Container;
528  _Container* container;
529  typename _Container::iterator iter;
530 
531  public:
532  typedef _Container container_type;
533  typedef output_iterator_tag iterator_category;
534  typedef void value_type;
535  typedef void difference_type;
536  typedef void pointer;
537  typedef void reference;
538 
539  insert_iterator(_Container& __x)
540  : container(&__x) {}
541 
542  insert_iterator(_Container& __x, typename _Container::iterator)
543  : container(&__x) {}
544 
545  insert_iterator<_Container>&
546  operator=(const typename _Container::value_type& __value)
547  {
548  container->insert(__value);
549  return *this;
550  }
551 
552  insert_iterator<_Container>&
553  operator*()
554  { return *this; }
555 
556  insert_iterator<_Container>&
557  operator++()
558  { return *this; }
559 
560  insert_iterator<_Container>&
561  operator++(int) { return *this; }
562  };
563 
564 _GLIBCXX_END_NAMESPACE_VERSION
565 } // namespace
566 
567 #endif
std::pair::second
_T2 second
first is a copy of the first object
Definition: stl_pair.h:102
std::pair::first
_T1 first
second_type is the second bound type
Definition: stl_pair.h:101
std::pair
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:96
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:129
std::insert_iterator::operator=
insert_iterator & operator=(const typename _Container::value_type &__value)
Definition: stl_iterator.h:639
std::insert_iterator::container_type
_Container container_type
A nested typedef for the type of whatever container you used.
Definition: stl_iterator.h:597
std::insert_iterator::operator*
insert_iterator & operator*()
Simply returns *this.
Definition: stl_iterator.h:657
std::iterator< output_iterator_tag, void, void, void, void >::value_type
void value_type
The type &quot;pointed to&quot; by the iterator.
Definition: stl_iterator_base_types.h:123
std::insert_iterator::operator++
insert_iterator & operator++()
Simply returns *this. (This iterator does not move.)
Definition: stl_iterator.h:662
std::allocator
The standard allocator, as per [20.4].
Definition: allocator.h:92
std::swap
void swap(function< _Res(_Args...)> &__x, function< _Res(_Args...)> &__y)
Swap the targets of two polymorphic function object wrappers.
Definition: functional:2534
std::equal_to
One of the comparison functors.
Definition: stl_function.h:336
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:127
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:125
std::insert_iterator::insert_iterator
insert_iterator(_Container &__x, typename _Container::iterator __i)
Definition: stl_iterator.h:603