1 // Hashing set implementation -*- C++ -*-
3 // Copyright (C) 2001, 2002 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.
62 #ifndef __SGI_STL_INTERNAL_HASH_SET_H
63 #define __SGI_STL_INTERNAL_HASH_SET_H
65 #include <ext/stl_hashtable.h>
66 #include <bits/concept_check.h>
75 // Forward declaration of equality operator; needed for friend declaration.
77 template <class _Value,
78 class _HashFcn = hash<_Value>,
79 class _EqualKey = equal_to<_Value>,
80 class _Alloc = allocator<_Value> >
83 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
85 operator==(const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs1,
86 const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs2);
89 * This is an SGI extension.
90 * @ingroup SGIextensions
93 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
96 // concept requirements
97 __glibcpp_class_requires(_Value, _SGIAssignableConcept)
98 __glibcpp_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept);
99 __glibcpp_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept);
102 typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>,
103 _EqualKey, _Alloc> _Ht;
107 typedef typename _Ht::key_type key_type;
108 typedef typename _Ht::value_type value_type;
109 typedef typename _Ht::hasher hasher;
110 typedef typename _Ht::key_equal key_equal;
112 typedef typename _Ht::size_type size_type;
113 typedef typename _Ht::difference_type difference_type;
114 typedef typename _Ht::const_pointer pointer;
115 typedef typename _Ht::const_pointer const_pointer;
116 typedef typename _Ht::const_reference reference;
117 typedef typename _Ht::const_reference const_reference;
119 typedef typename _Ht::const_iterator iterator;
120 typedef typename _Ht::const_iterator const_iterator;
122 typedef typename _Ht::allocator_type allocator_type;
124 hasher hash_funct() const { return _M_ht.hash_funct(); }
125 key_equal key_eq() const { return _M_ht.key_eq(); }
126 allocator_type get_allocator() const { return _M_ht.get_allocator(); }
130 : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
131 explicit hash_set(size_type __n)
132 : _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()) {}
135 hash_set(size_type __n, const hasher& __hf, const key_equal& __eql,
136 const allocator_type& __a = allocator_type())
137 : _M_ht(__n, __hf, __eql, __a) {}
139 template <class _InputIterator>
140 hash_set(_InputIterator __f, _InputIterator __l)
141 : _M_ht(100, hasher(), key_equal(), allocator_type())
142 { _M_ht.insert_unique(__f, __l); }
143 template <class _InputIterator>
144 hash_set(_InputIterator __f, _InputIterator __l, size_type __n)
145 : _M_ht(__n, hasher(), key_equal(), allocator_type())
146 { _M_ht.insert_unique(__f, __l); }
147 template <class _InputIterator>
148 hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
150 : _M_ht(__n, __hf, key_equal(), allocator_type())
151 { _M_ht.insert_unique(__f, __l); }
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); }
160 size_type size() const { return _M_ht.size(); }
161 size_type max_size() const { return _M_ht.max_size(); }
162 bool empty() const { return _M_ht.empty(); }
163 void swap(hash_set& __hs) { _M_ht.swap(__hs._M_ht); }
165 template <class _Val, class _HF, class _EqK, class _Al>
166 friend bool operator== (const hash_set<_Val, _HF, _EqK, _Al>&,
167 const hash_set<_Val, _HF, _EqK, _Al>&);
169 iterator begin() const { return _M_ht.begin(); }
170 iterator end() const { return _M_ht.end(); }
173 pair<iterator, bool> insert(const value_type& __obj)
175 pair<typename _Ht::iterator, bool> __p = _M_ht.insert_unique(__obj);
176 return pair<iterator,bool>(__p.first, __p.second);
178 template <class _InputIterator>
179 void insert(_InputIterator __f, _InputIterator __l)
180 { _M_ht.insert_unique(__f,__l); }
181 pair<iterator, bool> insert_noresize(const value_type& __obj)
183 pair<typename _Ht::iterator, bool> __p =
184 _M_ht.insert_unique_noresize(__obj);
185 return pair<iterator, bool>(__p.first, __p.second);
188 iterator find(const key_type& __key) const { return _M_ht.find(__key); }
190 size_type count(const key_type& __key) const { return _M_ht.count(__key); }
192 pair<iterator, iterator> equal_range(const key_type& __key) const
193 { return _M_ht.equal_range(__key); }
195 size_type erase(const key_type& __key) {return _M_ht.erase(__key); }
196 void erase(iterator __it) { _M_ht.erase(__it); }
197 void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); }
198 void clear() { _M_ht.clear(); }
201 void resize(size_type __hint) { _M_ht.resize(__hint); }
202 size_type bucket_count() const { return _M_ht.bucket_count(); }
203 size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
204 size_type elems_in_bucket(size_type __n) const
205 { return _M_ht.elems_in_bucket(__n); }
208 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
210 operator==(const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs1,
211 const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs2)
213 return __hs1._M_ht == __hs2._M_ht;
216 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
218 operator!=(const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs1,
219 const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs2) {
220 return !(__hs1 == __hs2);
223 template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>
225 swap(hash_set<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1,
226 hash_set<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2)
232 template <class _Value,
233 class _HashFcn = hash<_Value>,
234 class _EqualKey = equal_to<_Value>,
235 class _Alloc = allocator<_Value> >
238 template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>
240 operator==(const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1,
241 const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2);
245 * This is an SGI extension.
246 * @ingroup SGIextensions
249 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
252 // concept requirements
253 __glibcpp_class_requires(_Value, _SGIAssignableConcept)
254 __glibcpp_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept);
255 __glibcpp_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept);
258 typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>,
259 _EqualKey, _Alloc> _Ht;
263 typedef typename _Ht::key_type key_type;
264 typedef typename _Ht::value_type value_type;
265 typedef typename _Ht::hasher hasher;
266 typedef typename _Ht::key_equal key_equal;
268 typedef typename _Ht::size_type size_type;
269 typedef typename _Ht::difference_type difference_type;
270 typedef typename _Ht::const_pointer pointer;
271 typedef typename _Ht::const_pointer const_pointer;
272 typedef typename _Ht::const_reference reference;
273 typedef typename _Ht::const_reference const_reference;
275 typedef typename _Ht::const_iterator iterator;
276 typedef typename _Ht::const_iterator const_iterator;
278 typedef typename _Ht::allocator_type allocator_type;
280 hasher hash_funct() const { return _M_ht.hash_funct(); }
281 key_equal key_eq() const { return _M_ht.key_eq(); }
282 allocator_type get_allocator() const { return _M_ht.get_allocator(); }
286 : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
287 explicit hash_multiset(size_type __n)
288 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
289 hash_multiset(size_type __n, const hasher& __hf)
290 : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
291 hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql,
292 const allocator_type& __a = allocator_type())
293 : _M_ht(__n, __hf, __eql, __a) {}
295 template <class _InputIterator>
296 hash_multiset(_InputIterator __f, _InputIterator __l)
297 : _M_ht(100, hasher(), key_equal(), allocator_type())
298 { _M_ht.insert_equal(__f, __l); }
299 template <class _InputIterator>
300 hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n)
301 : _M_ht(__n, hasher(), key_equal(), allocator_type())
302 { _M_ht.insert_equal(__f, __l); }
303 template <class _InputIterator>
304 hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
306 : _M_ht(__n, __hf, key_equal(), allocator_type())
307 { _M_ht.insert_equal(__f, __l); }
308 template <class _InputIterator>
309 hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
310 const hasher& __hf, const key_equal& __eql,
311 const allocator_type& __a = allocator_type())
312 : _M_ht(__n, __hf, __eql, __a)
313 { _M_ht.insert_equal(__f, __l); }
316 size_type size() const { return _M_ht.size(); }
317 size_type max_size() const { return _M_ht.max_size(); }
318 bool empty() const { return _M_ht.empty(); }
319 void swap(hash_multiset& hs) { _M_ht.swap(hs._M_ht); }
321 template <class _Val, class _HF, class _EqK, class _Al>
322 friend bool operator== (const hash_multiset<_Val, _HF, _EqK, _Al>&,
323 const hash_multiset<_Val, _HF, _EqK, _Al>&);
325 iterator begin() const { return _M_ht.begin(); }
326 iterator end() const { return _M_ht.end(); }
329 iterator insert(const value_type& __obj)
330 { return _M_ht.insert_equal(__obj); }
331 template <class _InputIterator>
332 void insert(_InputIterator __f, _InputIterator __l)
333 { _M_ht.insert_equal(__f,__l); }
334 iterator insert_noresize(const value_type& __obj)
335 { return _M_ht.insert_equal_noresize(__obj); }
337 iterator find(const key_type& __key) const { return _M_ht.find(__key); }
339 size_type count(const key_type& __key) const { return _M_ht.count(__key); }
341 pair<iterator, iterator> equal_range(const key_type& __key) const
342 { return _M_ht.equal_range(__key); }
344 size_type erase(const key_type& __key) {return _M_ht.erase(__key); }
345 void erase(iterator __it) { _M_ht.erase(__it); }
346 void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); }
347 void clear() { _M_ht.clear(); }
350 void resize(size_type __hint) { _M_ht.resize(__hint); }
351 size_type bucket_count() const { return _M_ht.bucket_count(); }
352 size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
353 size_type elems_in_bucket(size_type __n) const
354 { return _M_ht.elems_in_bucket(__n); }
357 template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>
359 operator==(const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1,
360 const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2)
362 return __hs1._M_ht == __hs2._M_ht;
365 template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>
367 operator!=(const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1,
368 const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2) {
369 return !(__hs1 == __hs2);
372 template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>
374 swap(hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1,
375 hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2) {
379 } // namespace __gnu_cxx
383 // Specialization of insert_iterator so that it will work for hash_set
384 // and hash_multiset.
386 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
387 class insert_iterator<__gnu_cxx::hash_set<_Value, _HashFcn, _EqualKey, _Alloc> > {
389 typedef __gnu_cxx::hash_set<_Value, _HashFcn, _EqualKey, _Alloc> _Container;
390 _Container* container;
392 typedef _Container container_type;
393 typedef output_iterator_tag iterator_category;
394 typedef void value_type;
395 typedef void difference_type;
396 typedef void pointer;
397 typedef void reference;
399 insert_iterator(_Container& __x) : container(&__x) {}
400 insert_iterator(_Container& __x, typename _Container::iterator)
402 insert_iterator<_Container>&
403 operator=(const typename _Container::value_type& __value) {
404 container->insert(__value);
407 insert_iterator<_Container>& operator*() { return *this; }
408 insert_iterator<_Container>& operator++() { return *this; }
409 insert_iterator<_Container>& operator++(int) { return *this; }
412 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
413 class insert_iterator<__gnu_cxx::hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc> > {
415 typedef __gnu_cxx::hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc> _Container;
416 _Container* container;
417 typename _Container::iterator iter;
419 typedef _Container container_type;
420 typedef output_iterator_tag iterator_category;
421 typedef void value_type;
422 typedef void difference_type;
423 typedef void pointer;
424 typedef void reference;
426 insert_iterator(_Container& __x) : container(&__x) {}
427 insert_iterator(_Container& __x, typename _Container::iterator)
429 insert_iterator<_Container>&
430 operator=(const typename _Container::value_type& __value) {
431 container->insert(__value);
434 insert_iterator<_Container>& operator*() { return *this; }
435 insert_iterator<_Container>& operator++() { return *this; }
436 insert_iterator<_Container>& operator++(int) { return *this; }
441 #endif /* __SGI_STL_INTERNAL_HASH_SET_H */