1 // Hashing set implementation -*- C++ -*-
3 // Copyright (C) 2001, 2002, 2004, 2005, 2006 Free Software Foundation, Inc.
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 2, or (at your option)
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.
16 // You should have received a copy of the GNU General Public License along
17 // with this library; see the file COPYING. If not, write to the Free
18 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
21 // As a special exception, you may use this file as part of a free software
22 // library without restriction. Specifically, if other files instantiate
23 // templates or use macros or inline functions from this file, or you compile
24 // this file and link it with other files to produce an executable, this
25 // file does not by itself cause the resulting executable to be covered by
26 // the GNU General Public License. This exception does not however
27 // invalidate any other reasons why the executable file might be covered by
28 // the GNU General Public License.
32 * Silicon Graphics Computer Systems, Inc.
34 * Permission to use, copy, modify, distribute and sell this software
35 * and its documentation for any purpose is hereby granted without fee,
36 * provided that the above copyright notice appear in all copies and
37 * that both that copyright notice and this permission notice appear
38 * in supporting documentation. Silicon Graphics makes no
39 * representations about the suitability of this software for any
40 * purpose. It is provided "as is" without express or implied warranty.
44 * Hewlett-Packard Company
46 * Permission to use, copy, modify, distribute and sell this software
47 * and its documentation for any purpose is hereby granted without fee,
48 * provided that the above copyright notice appear in all copies and
49 * that both that copyright notice and this permission notice appear
50 * in supporting documentation. Hewlett-Packard Company makes no
51 * representations about the suitability of this software for any
52 * purpose. It is provided "as is" without express or implied warranty.
56 /** @file ext/hash_set
57 * This file is a GNU extension to the Standard C++ Library (possibly
58 * containing extensions from the HP/SGI STL subset).
64 #include <bits/c++config.h>
65 #include <ext/hashtable.h>
66 #include <bits/concept_check.h>
68 _GLIBCXX_BEGIN_NESTED_NAMESPACE(__gnu_cxx, _GLIBCXX_EXT)
76 * This is an SGI extension.
77 * @ingroup SGIextensions
80 template<class _Value, class _HashFcn = hash<_Value>,
81 class _EqualKey = equal_to<_Value>,
82 class _Alloc = allocator<_Value> >
85 // concept requirements
86 __glibcxx_class_requires(_Value, _SGIAssignableConcept)
87 __glibcxx_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept)
88 __glibcxx_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept)
91 typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>,
92 _EqualKey, _Alloc> _Ht;
96 typedef typename _Ht::key_type key_type;
97 typedef typename _Ht::value_type value_type;
98 typedef typename _Ht::hasher hasher;
99 typedef typename _Ht::key_equal key_equal;
101 typedef typename _Ht::size_type size_type;
102 typedef typename _Ht::difference_type difference_type;
103 typedef typename _Alloc::pointer pointer;
104 typedef typename _Alloc::const_pointer const_pointer;
105 typedef typename _Alloc::reference reference;
106 typedef typename _Alloc::const_reference const_reference;
108 typedef typename _Ht::const_iterator iterator;
109 typedef typename _Ht::const_iterator const_iterator;
111 typedef typename _Ht::allocator_type allocator_type;
115 { return _M_ht.hash_funct(); }
119 { return _M_ht.key_eq(); }
122 get_allocator() const
123 { return _M_ht.get_allocator(); }
127 : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
130 hash_set(size_type __n)
131 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
133 hash_set(size_type __n, const hasher& __hf)
134 : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
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) {}
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); }
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); }
150 template<class _InputIterator>
151 hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
153 : _M_ht(__n, __hf, key_equal(), allocator_type())
154 { _M_ht.insert_unique(__f, __l); }
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); }
166 { return _M_ht.size(); }
170 { return _M_ht.max_size(); }
174 { return _M_ht.empty(); }
178 { _M_ht.swap(__hs._M_ht); }
180 template<class _Val, class _HF, class _EqK, class _Al>
182 operator==(const hash_set<_Val, _HF, _EqK, _Al>&,
183 const hash_set<_Val, _HF, _EqK, _Al>&);
187 { return _M_ht.begin(); }
191 { return _M_ht.end(); }
195 insert(const value_type& __obj)
197 pair<typename _Ht::iterator, bool> __p = _M_ht.insert_unique(__obj);
198 return pair<iterator,bool>(__p.first, __p.second);
201 template<class _InputIterator>
203 insert(_InputIterator __f, _InputIterator __l)
204 { _M_ht.insert_unique(__f, __l); }
207 insert_noresize(const value_type& __obj)
209 pair<typename _Ht::iterator, bool> __p
210 = _M_ht.insert_unique_noresize(__obj);
211 return pair<iterator, bool>(__p.first, __p.second);
215 find(const key_type& __key) const
216 { return _M_ht.find(__key); }
219 count(const key_type& __key) const
220 { return _M_ht.count(__key); }
222 pair<iterator, iterator>
223 equal_range(const key_type& __key) const
224 { return _M_ht.equal_range(__key); }
227 erase(const key_type& __key)
228 {return _M_ht.erase(__key); }
232 { _M_ht.erase(__it); }
235 erase(iterator __f, iterator __l)
236 { _M_ht.erase(__f, __l); }
244 resize(size_type __hint)
245 { _M_ht.resize(__hint); }
249 { return _M_ht.bucket_count(); }
252 max_bucket_count() const
253 { return _M_ht.max_bucket_count(); }
256 elems_in_bucket(size_type __n) const
257 { return _M_ht.elems_in_bucket(__n); }
260 template<class _Value, class _HashFcn, class _EqualKey, class _Alloc>
262 operator==(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs1,
263 const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs2)
264 { return __hs1._M_ht == __hs2._M_ht; }
266 template<class _Value, class _HashFcn, class _EqualKey, class _Alloc>
268 operator!=(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs1,
269 const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs2)
270 { return !(__hs1 == __hs2); }
272 template<class _Val, class _HashFcn, class _EqualKey, class _Alloc>
274 swap(hash_set<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
275 hash_set<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
276 { __hs1.swap(__hs2); }
280 * This is an SGI extension.
281 * @ingroup SGIextensions
284 template<class _Value,
285 class _HashFcn = hash<_Value>,
286 class _EqualKey = equal_to<_Value>,
287 class _Alloc = allocator<_Value> >
290 // concept requirements
291 __glibcxx_class_requires(_Value, _SGIAssignableConcept)
292 __glibcxx_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept)
293 __glibcxx_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept)
296 typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>,
297 _EqualKey, _Alloc> _Ht;
301 typedef typename _Ht::key_type key_type;
302 typedef typename _Ht::value_type value_type;
303 typedef typename _Ht::hasher hasher;
304 typedef typename _Ht::key_equal key_equal;
306 typedef typename _Ht::size_type size_type;
307 typedef typename _Ht::difference_type difference_type;
308 typedef typename _Alloc::pointer pointer;
309 typedef typename _Alloc::const_pointer const_pointer;
310 typedef typename _Alloc::reference reference;
311 typedef typename _Alloc::const_reference const_reference;
313 typedef typename _Ht::const_iterator iterator;
314 typedef typename _Ht::const_iterator const_iterator;
316 typedef typename _Ht::allocator_type allocator_type;
320 { return _M_ht.hash_funct(); }
324 { return _M_ht.key_eq(); }
327 get_allocator() const
328 { return _M_ht.get_allocator(); }
332 : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
335 hash_multiset(size_type __n)
336 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
338 hash_multiset(size_type __n, const hasher& __hf)
339 : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
341 hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql,
342 const allocator_type& __a = allocator_type())
343 : _M_ht(__n, __hf, __eql, __a) {}
345 template<class _InputIterator>
346 hash_multiset(_InputIterator __f, _InputIterator __l)
347 : _M_ht(100, hasher(), key_equal(), allocator_type())
348 { _M_ht.insert_equal(__f, __l); }
350 template<class _InputIterator>
351 hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n)
352 : _M_ht(__n, hasher(), key_equal(), allocator_type())
353 { _M_ht.insert_equal(__f, __l); }
355 template<class _InputIterator>
356 hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
358 : _M_ht(__n, __hf, key_equal(), allocator_type())
359 { _M_ht.insert_equal(__f, __l); }
361 template<class _InputIterator>
362 hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
363 const hasher& __hf, const key_equal& __eql,
364 const allocator_type& __a = allocator_type())
365 : _M_ht(__n, __hf, __eql, __a)
366 { _M_ht.insert_equal(__f, __l); }
371 { return _M_ht.size(); }
375 { return _M_ht.max_size(); }
379 { return _M_ht.empty(); }
382 swap(hash_multiset& hs)
383 { _M_ht.swap(hs._M_ht); }
385 template<class _Val, class _HF, class _EqK, class _Al>
387 operator==(const hash_multiset<_Val, _HF, _EqK, _Al>&,
388 const hash_multiset<_Val, _HF, _EqK, _Al>&);
392 { return _M_ht.begin(); }
396 { return _M_ht.end(); }
400 insert(const value_type& __obj)
401 { return _M_ht.insert_equal(__obj); }
403 template<class _InputIterator>
405 insert(_InputIterator __f, _InputIterator __l)
406 { _M_ht.insert_equal(__f,__l); }
409 insert_noresize(const value_type& __obj)
410 { return _M_ht.insert_equal_noresize(__obj); }
413 find(const key_type& __key) const
414 { return _M_ht.find(__key); }
417 count(const key_type& __key) const
418 { return _M_ht.count(__key); }
420 pair<iterator, iterator>
421 equal_range(const key_type& __key) const
422 { return _M_ht.equal_range(__key); }
425 erase(const key_type& __key)
426 { return _M_ht.erase(__key); }
430 { _M_ht.erase(__it); }
433 erase(iterator __f, iterator __l)
434 { _M_ht.erase(__f, __l); }
442 resize(size_type __hint)
443 { _M_ht.resize(__hint); }
447 { return _M_ht.bucket_count(); }
450 max_bucket_count() const
451 { return _M_ht.max_bucket_count(); }
454 elems_in_bucket(size_type __n) const
455 { return _M_ht.elems_in_bucket(__n); }
458 template<class _Val, class _HashFcn, class _EqualKey, class _Alloc>
460 operator==(const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
461 const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
462 { return __hs1._M_ht == __hs2._M_ht; }
464 template<class _Val, class _HashFcn, class _EqualKey, class _Alloc>
466 operator!=(const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
467 const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
468 { return !(__hs1 == __hs2); }
470 template<class _Val, class _HashFcn, class _EqualKey, class _Alloc>
472 swap(hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
473 hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
474 { __hs1.swap(__hs2); }
476 _GLIBCXX_END_NESTED_NAMESPACE
478 #ifdef _GLIBCXX_DEBUG
479 # include <debug/hash_set>
482 _GLIBCXX_BEGIN_NAMESPACE(std)
484 // Specialization of insert_iterator so that it will work for hash_set
485 // and hash_multiset.
486 template<class _Value, class _HashFcn, class _EqualKey, class _Alloc>
487 class insert_iterator<__gnu_cxx::hash_set<_Value, _HashFcn,
491 typedef __gnu_cxx::hash_set<_Value, _HashFcn, _EqualKey, _Alloc>
493 _Container* container;
496 typedef _Container container_type;
497 typedef output_iterator_tag iterator_category;
498 typedef void value_type;
499 typedef void difference_type;
500 typedef void pointer;
501 typedef void reference;
503 insert_iterator(_Container& __x)
506 insert_iterator(_Container& __x, typename _Container::iterator)
509 insert_iterator<_Container>&
510 operator=(const typename _Container::value_type& __value)
512 container->insert(__value);
516 insert_iterator<_Container>&
520 insert_iterator<_Container>&
524 insert_iterator<_Container>&
529 template<class _Value, class _HashFcn, class _EqualKey, class _Alloc>
530 class insert_iterator<__gnu_cxx::hash_multiset<_Value, _HashFcn,
534 typedef __gnu_cxx::hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc>
536 _Container* container;
537 typename _Container::iterator iter;
540 typedef _Container container_type;
541 typedef output_iterator_tag iterator_category;
542 typedef void value_type;
543 typedef void difference_type;
544 typedef void pointer;
545 typedef void reference;
547 insert_iterator(_Container& __x)
550 insert_iterator(_Container& __x, typename _Container::iterator)
553 insert_iterator<_Container>&
554 operator=(const typename _Container::value_type& __value)
556 container->insert(__value);
560 insert_iterator<_Container>&
564 insert_iterator<_Container>&
568 insert_iterator<_Container>&
569 operator++(int) { return *this; }
572 _GLIBCXX_END_NAMESPACE