hash_set

Go to the documentation of this file.
00001 // Hashing set implementation -*- C++ -*- 00002 00003 // Copyright (C) 2001, 2002 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the 00007 // terms of the GNU General Public License as published by the 00008 // Free Software Foundation; either version 2, or (at your option) 00009 // any later version. 00010 00011 // This library is distributed in the hope that it will be useful, 00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 // GNU General Public License for more details. 00015 00016 // You should have received a copy of the GNU General Public License along 00017 // with this library; see the file COPYING. If not, write to the Free 00018 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 00019 // USA. 00020 00021 // As a special exception, you may use this file as part of a free software 00022 // library without restriction. Specifically, if other files instantiate 00023 // templates or use macros or inline functions from this file, or you compile 00024 // this file and link it with other files to produce an executable, this 00025 // file does not by itself cause the resulting executable to be covered by 00026 // the GNU General Public License. This exception does not however 00027 // invalidate any other reasons why the executable file might be covered by 00028 // the GNU General Public License. 00029 00030 /* 00031 * Copyright (c) 1996 00032 * Silicon Graphics Computer Systems, Inc. 00033 * 00034 * Permission to use, copy, modify, distribute and sell this software 00035 * and its documentation for any purpose is hereby granted without fee, 00036 * provided that the above copyright notice appear in all copies and 00037 * that both that copyright notice and this permission notice appear 00038 * in supporting documentation. Silicon Graphics makes no 00039 * representations about the suitability of this software for any 00040 * purpose. It is provided "as is" without express or implied warranty. 00041 * 00042 * 00043 * Copyright (c) 1994 00044 * Hewlett-Packard Company 00045 * 00046 * Permission to use, copy, modify, distribute and sell this software 00047 * and its documentation for any purpose is hereby granted without fee, 00048 * provided that the above copyright notice appear in all copies and 00049 * that both that copyright notice and this permission notice appear 00050 * in supporting documentation. Hewlett-Packard Company makes no 00051 * representations about the suitability of this software for any 00052 * purpose. It is provided "as is" without express or implied warranty. 00053 * 00054 */ 00055 00056 /** @file ext/hash_set 00057 * This file is a GNU extension to the Standard C++ Library (possibly 00058 * containing extensions from the HP/SGI STL subset). You should only 00059 * include this header if you are using GCC 3 or later. 00060 */ 00061 00062 #ifndef _HASH_SET 00063 #define _HASH_SET 1 00064 00065 #include <ext/hashtable.h> 00066 #include <bits/concept_check.h> 00067 00068 namespace __gnu_cxx 00069 { 00070 using std::equal_to; 00071 using std::allocator; 00072 using std::pair; 00073 using std::_Identity; 00074 00075 // Forward declaration of equality operator; needed for friend 00076 // declaration. 00077 template <class _Value, class _HashFcn = hash<_Value>, 00078 class _EqualKey = equal_to<_Value>, 00079 class _Alloc = allocator<_Value> > 00080 class hash_set; 00081 00082 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc> 00083 inline bool 00084 operator==(const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs1, 00085 const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs2); 00086 00087 /** 00088 * This is an SGI extension. 00089 * @ingroup SGIextensions 00090 * @doctodo 00091 */ 00092 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc> 00093 class hash_set 00094 { 00095 // concept requirements 00096 __glibcxx_class_requires(_Value, _SGIAssignableConcept) 00097 __glibcxx_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept) 00098 __glibcxx_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept) 00099 00100 private: 00101 typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>, 00102 _EqualKey, _Alloc> _Ht; 00103 _Ht _M_ht; 00104 00105 public: 00106 typedef typename _Ht::key_type key_type; 00107 typedef typename _Ht::value_type value_type; 00108 typedef typename _Ht::hasher hasher; 00109 typedef typename _Ht::key_equal key_equal; 00110 00111 typedef typename _Ht::size_type size_type; 00112 typedef typename _Ht::difference_type difference_type; 00113 typedef typename _Alloc::pointer pointer; 00114 typedef typename _Alloc::const_pointer const_pointer; 00115 typedef typename _Alloc::reference reference; 00116 typedef typename _Alloc::const_reference const_reference; 00117 00118 typedef typename _Ht::const_iterator iterator; 00119 typedef typename _Ht::const_iterator const_iterator; 00120 00121 typedef typename _Ht::allocator_type allocator_type; 00122 00123 hasher hash_funct() const { return _M_ht.hash_funct(); } 00124 key_equal key_eq() const { return _M_ht.key_eq(); } 00125 allocator_type get_allocator() const { return _M_ht.get_allocator(); } 00126 00127 public: 00128 hash_set() 00129 : _M_ht(100, hasher(), key_equal(), allocator_type()) {} 00130 explicit hash_set(size_type __n) 00131 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {} 00132 hash_set(size_type __n, const hasher& __hf) 00133 : _M_ht(__n, __hf, key_equal(), allocator_type()) {} 00134 hash_set(size_type __n, const hasher& __hf, const key_equal& __eql, 00135 const allocator_type& __a = allocator_type()) 00136 : _M_ht(__n, __hf, __eql, __a) {} 00137 00138 template <class _InputIterator> 00139 hash_set(_InputIterator __f, _InputIterator __l) 00140 : _M_ht(100, hasher(), key_equal(), allocator_type()) 00141 { _M_ht.insert_unique(__f, __l); } 00142 template <class _InputIterator> 00143 hash_set(_InputIterator __f, _InputIterator __l, size_type __n) 00144 : _M_ht(__n, hasher(), key_equal(), allocator_type()) 00145 { _M_ht.insert_unique(__f, __l); } 00146 template <class _InputIterator> 00147 hash_set(_InputIterator __f, _InputIterator __l, size_type __n, 00148 const hasher& __hf) 00149 : _M_ht(__n, __hf, key_equal(), allocator_type()) 00150 { _M_ht.insert_unique(__f, __l); } 00151 template <class _InputIterator> 00152 hash_set(_InputIterator __f, _InputIterator __l, size_type __n, 00153 const hasher& __hf, const key_equal& __eql, 00154 const allocator_type& __a = allocator_type()) 00155 : _M_ht(__n, __hf, __eql, __a) 00156 { _M_ht.insert_unique(__f, __l); } 00157 00158 public: 00159 size_type size() const { return _M_ht.size(); } 00160 size_type max_size() const { return _M_ht.max_size(); } 00161 bool empty() const { return _M_ht.empty(); } 00162 void swap(hash_set& __hs) { _M_ht.swap(__hs._M_ht); } 00163 00164 template <class _Val, class _HF, class _EqK, class _Al> 00165 friend bool operator== (const hash_set<_Val, _HF, _EqK, _Al>&, 00166 const hash_set<_Val, _HF, _EqK, _Al>&); 00167 00168 iterator begin() const { return _M_ht.begin(); } 00169 iterator end() const { return _M_ht.end(); } 00170 00171 public: 00172 pair<iterator, bool> insert(const value_type& __obj) 00173 { 00174 pair<typename _Ht::iterator, bool> __p = _M_ht.insert_unique(__obj); 00175 return pair<iterator,bool>(__p.first, __p.second); 00176 } 00177 template <class _InputIterator> 00178 void insert(_InputIterator __f, _InputIterator __l) 00179 { _M_ht.insert_unique(__f,__l); } 00180 pair<iterator, bool> insert_noresize(const value_type& __obj) 00181 { 00182 pair<typename _Ht::iterator, bool> __p = 00183 _M_ht.insert_unique_noresize(__obj); 00184 return pair<iterator, bool>(__p.first, __p.second); 00185 } 00186 00187 iterator find(const key_type& __key) const { return _M_ht.find(__key); } 00188 00189 size_type count(const key_type& __key) const { return _M_ht.count(__key); } 00190 00191 pair<iterator, iterator> equal_range(const key_type& __key) const 00192 { return _M_ht.equal_range(__key); } 00193 00194 size_type erase(const key_type& __key) {return _M_ht.erase(__key); } 00195 void erase(iterator __it) { _M_ht.erase(__it); } 00196 void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); } 00197 void clear() { _M_ht.clear(); } 00198 00199 public: 00200 void resize(size_type __hint) { _M_ht.resize(__hint); } 00201 size_type bucket_count() const { return _M_ht.bucket_count(); } 00202 size_type max_bucket_count() const { return _M_ht.max_bucket_count(); } 00203 size_type elems_in_bucket(size_type __n) const 00204 { return _M_ht.elems_in_bucket(__n); } 00205 }; 00206 00207 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc> 00208 inline bool 00209 operator==(const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs1, 00210 const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs2) 00211 { 00212 return __hs1._M_ht == __hs2._M_ht; 00213 } 00214 00215 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc> 00216 inline bool 00217 operator!=(const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs1, 00218 const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs2) { 00219 return !(__hs1 == __hs2); 00220 } 00221 00222 template <class _Val, class _HashFcn, class _EqualKey, class _Alloc> 00223 inline void 00224 swap(hash_set<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1, 00225 hash_set<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2) 00226 { 00227 __hs1.swap(__hs2); 00228 } 00229 00230 00231 template <class _Value, 00232 class _HashFcn = hash<_Value>, 00233 class _EqualKey = equal_to<_Value>, 00234 class _Alloc = allocator<_Value> > 00235 class hash_multiset; 00236 00237 template <class _Val, class _HashFcn, class _EqualKey, class _Alloc> 00238 inline bool 00239 operator==(const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1, 00240 const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2); 00241 00242 00243 /** 00244 * This is an SGI extension. 00245 * @ingroup SGIextensions 00246 * @doctodo 00247 */ 00248 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc> 00249 class hash_multiset 00250 { 00251 // concept requirements 00252 __glibcxx_class_requires(_Value, _SGIAssignableConcept) 00253 __glibcxx_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept) 00254 __glibcxx_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept) 00255 00256 private: 00257 typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>, 00258 _EqualKey, _Alloc> _Ht; 00259 _Ht _M_ht; 00260 00261 public: 00262 typedef typename _Ht::key_type key_type; 00263 typedef typename _Ht::value_type value_type; 00264 typedef typename _Ht::hasher hasher; 00265 typedef typename _Ht::key_equal key_equal; 00266 00267 typedef typename _Ht::size_type size_type; 00268 typedef typename _Ht::difference_type difference_type; 00269 typedef typename _Alloc::pointer pointer; 00270 typedef typename _Alloc::const_pointer const_pointer; 00271 typedef typename _Alloc::reference reference; 00272 typedef typename _Alloc::const_reference const_reference; 00273 00274 typedef typename _Ht::const_iterator iterator; 00275 typedef typename _Ht::const_iterator const_iterator; 00276 00277 typedef typename _Ht::allocator_type allocator_type; 00278 00279 hasher hash_funct() const { return _M_ht.hash_funct(); } 00280 key_equal key_eq() const { return _M_ht.key_eq(); } 00281 allocator_type get_allocator() const { return _M_ht.get_allocator(); } 00282 00283 public: 00284 hash_multiset() 00285 : _M_ht(100, hasher(), key_equal(), allocator_type()) {} 00286 explicit hash_multiset(size_type __n) 00287 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {} 00288 hash_multiset(size_type __n, const hasher& __hf) 00289 : _M_ht(__n, __hf, key_equal(), allocator_type()) {} 00290 hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql, 00291 const allocator_type& __a = allocator_type()) 00292 : _M_ht(__n, __hf, __eql, __a) {} 00293 00294 template <class _InputIterator> 00295 hash_multiset(_InputIterator __f, _InputIterator __l) 00296 : _M_ht(100, hasher(), key_equal(), allocator_type()) 00297 { _M_ht.insert_equal(__f, __l); } 00298 template <class _InputIterator> 00299 hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n) 00300 : _M_ht(__n, hasher(), key_equal(), allocator_type()) 00301 { _M_ht.insert_equal(__f, __l); } 00302 template <class _InputIterator> 00303 hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n, 00304 const hasher& __hf) 00305 : _M_ht(__n, __hf, key_equal(), allocator_type()) 00306 { _M_ht.insert_equal(__f, __l); } 00307 template <class _InputIterator> 00308 hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n, 00309 const hasher& __hf, const key_equal& __eql, 00310 const allocator_type& __a = allocator_type()) 00311 : _M_ht(__n, __hf, __eql, __a) 00312 { _M_ht.insert_equal(__f, __l); } 00313 00314 public: 00315 size_type size() const { return _M_ht.size(); } 00316 size_type max_size() const { return _M_ht.max_size(); } 00317 bool empty() const { return _M_ht.empty(); } 00318 void swap(hash_multiset& hs) { _M_ht.swap(hs._M_ht); } 00319 00320 template <class _Val, class _HF, class _EqK, class _Al> 00321 friend bool operator== (const hash_multiset<_Val, _HF, _EqK, _Al>&, 00322 const hash_multiset<_Val, _HF, _EqK, _Al>&); 00323 00324 iterator begin() const { return _M_ht.begin(); } 00325 iterator end() const { return _M_ht.end(); } 00326 00327 public: 00328 iterator insert(const value_type& __obj) 00329 { return _M_ht.insert_equal(__obj); } 00330 template <class _InputIterator> 00331 void insert(_InputIterator __f, _InputIterator __l) 00332 { _M_ht.insert_equal(__f,__l); } 00333 iterator insert_noresize(const value_type& __obj) 00334 { return _M_ht.insert_equal_noresize(__obj); } 00335 00336 iterator find(const key_type& __key) const { return _M_ht.find(__key); } 00337 00338 size_type count(const key_type& __key) const { return _M_ht.count(__key); } 00339 00340 pair<iterator, iterator> equal_range(const key_type& __key) const 00341 { return _M_ht.equal_range(__key); } 00342 00343 size_type erase(const key_type& __key) {return _M_ht.erase(__key); } 00344 void erase(iterator __it) { _M_ht.erase(__it); } 00345 void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); } 00346 void clear() { _M_ht.clear(); } 00347 00348 public: 00349 void resize(size_type __hint) { _M_ht.resize(__hint); } 00350 size_type bucket_count() const { return _M_ht.bucket_count(); } 00351 size_type max_bucket_count() const { return _M_ht.max_bucket_count(); } 00352 size_type elems_in_bucket(size_type __n) const 00353 { return _M_ht.elems_in_bucket(__n); } 00354 }; 00355 00356 template <class _Val, class _HashFcn, class _EqualKey, class _Alloc> 00357 inline bool 00358 operator==(const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1, 00359 const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2) 00360 { 00361 return __hs1._M_ht == __hs2._M_ht; 00362 } 00363 00364 template <class _Val, class _HashFcn, class _EqualKey, class _Alloc> 00365 inline bool 00366 operator!=(const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1, 00367 const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2) { 00368 return !(__hs1 == __hs2); 00369 } 00370 00371 template <class _Val, class _HashFcn, class _EqualKey, class _Alloc> 00372 inline void 00373 swap(hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1, 00374 hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2) { 00375 __hs1.swap(__hs2); 00376 } 00377 00378 } // namespace __gnu_cxx 00379 00380 namespace std 00381 { 00382 // Specialization of insert_iterator so that it will work for hash_set 00383 // and hash_multiset. 00384 00385 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc> 00386 class insert_iterator<__gnu_cxx::hash_set<_Value, _HashFcn, _EqualKey, _Alloc> > { 00387 protected: 00388 typedef __gnu_cxx::hash_set<_Value, _HashFcn, _EqualKey, _Alloc> _Container; 00389 _Container* container; 00390 public: 00391 typedef _Container container_type; 00392 typedef output_iterator_tag iterator_category; 00393 typedef void value_type; 00394 typedef void difference_type; 00395 typedef void pointer; 00396 typedef void reference; 00397 00398 insert_iterator(_Container& __x) : container(&__x) {} 00399 insert_iterator(_Container& __x, typename _Container::iterator) 00400 : container(&__x) {} 00401 insert_iterator<_Container>& 00402 operator=(const typename _Container::value_type& __value) { 00403 container->insert(__value); 00404 return *this; 00405 } 00406 insert_iterator<_Container>& operator*() { return *this; } 00407 insert_iterator<_Container>& operator++() { return *this; } 00408 insert_iterator<_Container>& operator++(int) { return *this; } 00409 }; 00410 00411 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc> 00412 class insert_iterator<__gnu_cxx::hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc> > { 00413 protected: 00414 typedef __gnu_cxx::hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc> _Container; 00415 _Container* container; 00416 typename _Container::iterator iter; 00417 public: 00418 typedef _Container container_type; 00419 typedef output_iterator_tag iterator_category; 00420 typedef void value_type; 00421 typedef void difference_type; 00422 typedef void pointer; 00423 typedef void reference; 00424 00425 insert_iterator(_Container& __x) : container(&__x) {} 00426 insert_iterator(_Container& __x, typename _Container::iterator) 00427 : container(&__x) {} 00428 insert_iterator<_Container>& 00429 operator=(const typename _Container::value_type& __value) { 00430 container->insert(__value); 00431 return *this; 00432 } 00433 insert_iterator<_Container>& operator*() { return *this; } 00434 insert_iterator<_Container>& operator++() { return *this; } 00435 insert_iterator<_Container>& operator++(int) { return *this; } 00436 }; 00437 } // namespace std 00438 00439 #endif

Generated on Wed Jun 9 11:18:35 2004 for libstdc++-v3 Source by doxygen 1.3.7