1 // Hashing set implementation -*- C++ -*-
3 // Copyright (C) 2001, 2002, 2004 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
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). You should only
59 * include this header if you are using GCC 3 or later.
65 #include <ext/hashtable.h>
66 #include <bits/concept_check.h>
75 // Forward declaration of equality operator; needed for friend
77 template <class _Value, class _HashFcn = hash<_Value>,
78 class _EqualKey = equal_to<_Value>,
79 class _Alloc = allocator<_Value> >
82 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
84 operator==(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs1,
85 const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs2);
88 * This is an SGI extension.
89 * @ingroup SGIextensions
92 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
95 // concept requirements
96 __glibcxx_class_requires(_Value, _SGIAssignableConcept)
97 __glibcxx_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept)
98 __glibcxx_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept)
101 typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>,
102 _EqualKey, _Alloc> _Ht;
106 typedef typename _Ht::key_type key_type;
107 typedef typename _Ht::value_type value_type;
108 typedef typename _Ht::hasher hasher;
109 typedef typename _Ht::key_equal key_equal;
111 typedef typename _Ht::size_type size_type;
112 typedef typename _Ht::difference_type difference_type;
113 typedef typename _Alloc::pointer pointer;
114 typedef typename _Alloc::const_pointer const_pointer;
115 typedef typename _Alloc::reference reference;
116 typedef typename _Alloc::const_reference const_reference;
118 typedef typename _Ht::const_iterator iterator;
119 typedef typename _Ht::const_iterator const_iterator;
121 typedef typename _Ht::allocator_type allocator_type;
125 { return _M_ht.hash_funct(); }
129 { return _M_ht.key_eq(); }
132 get_allocator() const
133 { return _M_ht.get_allocator(); }
137 : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
140 hash_set(size_type __n)
141 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
143 hash_set(size_type __n, const hasher& __hf)
144 : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
146 hash_set(size_type __n, const hasher& __hf, const key_equal& __eql,
147 const allocator_type& __a = allocator_type())
148 : _M_ht(__n, __hf, __eql, __a) {}
150 template <class _InputIterator>
151 hash_set(_InputIterator __f, _InputIterator __l)
152 : _M_ht(100, hasher(), key_equal(), allocator_type())
153 { _M_ht.insert_unique(__f, __l); }
155 template <class _InputIterator>
156 hash_set(_InputIterator __f, _InputIterator __l, size_type __n)
157 : _M_ht(__n, hasher(), key_equal(), allocator_type())
158 { _M_ht.insert_unique(__f, __l); }
160 template <class _InputIterator>
161 hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
163 : _M_ht(__n, __hf, key_equal(), allocator_type())
164 { _M_ht.insert_unique(__f, __l); }
166 template <class _InputIterator>
167 hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
168 const hasher& __hf, const key_equal& __eql,
169 const allocator_type& __a = allocator_type())
170 : _M_ht(__n, __hf, __eql, __a)
171 { _M_ht.insert_unique(__f, __l); }
176 { return _M_ht.size(); }
180 { return _M_ht.max_size(); }
184 { return _M_ht.empty(); }
188 { _M_ht.swap(__hs._M_ht); }
190 template <class _Val, class _HF, class _EqK, class _Al>
192 operator==(const hash_set<_Val, _HF, _EqK, _Al>&,
193 const hash_set<_Val, _HF, _EqK, _Al>&);
197 { return _M_ht.begin(); }
201 { return _M_ht.end(); }
205 insert(const value_type& __obj)
207 pair<typename _Ht::iterator, bool> __p = _M_ht.insert_unique(__obj);
208 return pair<iterator,bool>(__p.first, __p.second);
211 template <class _InputIterator>
213 insert(_InputIterator __f, _InputIterator __l)
214 { _M_ht.insert_unique(__f, __l); }
217 insert_noresize(const value_type& __obj)
219 pair<typename _Ht::iterator, bool> __p
220 = _M_ht.insert_unique_noresize(__obj);
221 return pair<iterator, bool>(__p.first, __p.second);
225 find(const key_type& __key) const
226 { return _M_ht.find(__key); }
229 count(const key_type& __key) const
230 { return _M_ht.count(__key); }
232 pair<iterator, iterator>
233 equal_range(const key_type& __key) const
234 { return _M_ht.equal_range(__key); }
237 erase(const key_type& __key)
238 {return _M_ht.erase(__key); }
242 { _M_ht.erase(__it); }
245 erase(iterator __f, iterator __l)
246 { _M_ht.erase(__f, __l); }
254 resize(size_type __hint)
255 { _M_ht.resize(__hint); }
259 { return _M_ht.bucket_count(); }
262 max_bucket_count() const
263 { return _M_ht.max_bucket_count(); }
266 elems_in_bucket(size_type __n) const
267 { return _M_ht.elems_in_bucket(__n); }
270 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
272 operator==(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs1,
273 const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs2)
274 { return __hs1._M_ht == __hs2._M_ht; }
276 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
278 operator!=(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs1,
279 const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs2)
280 { return !(__hs1 == __hs2); }
282 template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>
284 swap(hash_set<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
285 hash_set<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
286 { __hs1.swap(__hs2); }
288 template <class _Value,
289 class _HashFcn = hash<_Value>,
290 class _EqualKey = equal_to<_Value>,
291 class _Alloc = allocator<_Value> >
294 template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>
296 operator==(const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
297 const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2);
301 * This is an SGI extension.
302 * @ingroup SGIextensions
305 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
308 // concept requirements
309 __glibcxx_class_requires(_Value, _SGIAssignableConcept)
310 __glibcxx_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept)
311 __glibcxx_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept)
314 typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>,
315 _EqualKey, _Alloc> _Ht;
319 typedef typename _Ht::key_type key_type;
320 typedef typename _Ht::value_type value_type;
321 typedef typename _Ht::hasher hasher;
322 typedef typename _Ht::key_equal key_equal;
324 typedef typename _Ht::size_type size_type;
325 typedef typename _Ht::difference_type difference_type;
326 typedef typename _Alloc::pointer pointer;
327 typedef typename _Alloc::const_pointer const_pointer;
328 typedef typename _Alloc::reference reference;
329 typedef typename _Alloc::const_reference const_reference;
331 typedef typename _Ht::const_iterator iterator;
332 typedef typename _Ht::const_iterator const_iterator;
334 typedef typename _Ht::allocator_type allocator_type;
338 { return _M_ht.hash_funct(); }
342 { return _M_ht.key_eq(); }
345 get_allocator() const
346 { return _M_ht.get_allocator(); }
350 : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
353 hash_multiset(size_type __n)
354 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
356 hash_multiset(size_type __n, const hasher& __hf)
357 : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
359 hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql,
360 const allocator_type& __a = allocator_type())
361 : _M_ht(__n, __hf, __eql, __a) {}
363 template <class _InputIterator>
364 hash_multiset(_InputIterator __f, _InputIterator __l)
365 : _M_ht(100, hasher(), key_equal(), allocator_type())
366 { _M_ht.insert_equal(__f, __l); }
368 template <class _InputIterator>
369 hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n)
370 : _M_ht(__n, hasher(), key_equal(), allocator_type())
371 { _M_ht.insert_equal(__f, __l); }
373 template <class _InputIterator>
374 hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
376 : _M_ht(__n, __hf, key_equal(), allocator_type())
377 { _M_ht.insert_equal(__f, __l); }
379 template <class _InputIterator>
380 hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
381 const hasher& __hf, const key_equal& __eql,
382 const allocator_type& __a = allocator_type())
383 : _M_ht(__n, __hf, __eql, __a)
384 { _M_ht.insert_equal(__f, __l); }
389 { return _M_ht.size(); }
393 { return _M_ht.max_size(); }
397 { return _M_ht.empty(); }
400 swap(hash_multiset& hs)
401 { _M_ht.swap(hs._M_ht); }
403 template <class _Val, class _HF, class _EqK, class _Al>
405 operator==(const hash_multiset<_Val, _HF, _EqK, _Al>&,
406 const hash_multiset<_Val, _HF, _EqK, _Al>&);
410 { return _M_ht.begin(); }
414 { return _M_ht.end(); }
418 insert(const value_type& __obj)
419 { return _M_ht.insert_equal(__obj); }
421 template <class _InputIterator>
423 insert(_InputIterator __f, _InputIterator __l)
424 { _M_ht.insert_equal(__f,__l); }
427 insert_noresize(const value_type& __obj)
428 { return _M_ht.insert_equal_noresize(__obj); }
431 find(const key_type& __key) const
432 { return _M_ht.find(__key); }
435 count(const key_type& __key) const
436 { return _M_ht.count(__key); }
438 pair<iterator, iterator>
439 equal_range(const key_type& __key) const
440 { return _M_ht.equal_range(__key); }
443 erase(const key_type& __key)
444 { return _M_ht.erase(__key); }
448 { _M_ht.erase(__it); }
451 erase(iterator __f, iterator __l)
452 { _M_ht.erase(__f, __l); }
460 resize(size_type __hint)
461 { _M_ht.resize(__hint); }
465 { return _M_ht.bucket_count(); }
468 max_bucket_count() const
469 { return _M_ht.max_bucket_count(); }
472 elems_in_bucket(size_type __n) const
473 { return _M_ht.elems_in_bucket(__n); }
476 template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>
478 operator==(const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
479 const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
480 { return __hs1._M_ht == __hs2._M_ht; }
482 template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>
484 operator!=(const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
485 const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
486 { return !(__hs1 == __hs2); }
488 template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>
490 swap(hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
491 hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
492 { __hs1.swap(__hs2); }
494 } // namespace __gnu_cxx
498 // Specialization of insert_iterator so that it will work for hash_set
499 // and hash_multiset.
501 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
502 class insert_iterator<__gnu_cxx::hash_set<_Value, _HashFcn,
506 typedef __gnu_cxx::hash_set<_Value, _HashFcn, _EqualKey, _Alloc>
508 _Container* container;
511 typedef _Container container_type;
512 typedef output_iterator_tag iterator_category;
513 typedef void value_type;
514 typedef void difference_type;
515 typedef void pointer;
516 typedef void reference;
518 insert_iterator(_Container& __x)
521 insert_iterator(_Container& __x, typename _Container::iterator)
524 insert_iterator<_Container>&
525 operator=(const typename _Container::value_type& __value)
527 container->insert(__value);
531 insert_iterator<_Container>&
535 insert_iterator<_Container>&
539 insert_iterator<_Container>&
544 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
545 class insert_iterator<__gnu_cxx::hash_multiset<_Value, _HashFcn,
549 typedef __gnu_cxx::hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc>
551 _Container* container;
552 typename _Container::iterator iter;
555 typedef _Container container_type;
556 typedef output_iterator_tag iterator_category;
557 typedef void value_type;
558 typedef void difference_type;
559 typedef void pointer;
560 typedef void reference;
562 insert_iterator(_Container& __x)
565 insert_iterator(_Container& __x, typename _Container::iterator)
568 insert_iterator<_Container>&
569 operator=(const typename _Container::value_type& __value)
571 container->insert(__value);
575 insert_iterator<_Container>&
579 insert_iterator<_Container>&
583 insert_iterator<_Container>&
584 operator++(int) { return *this; }