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 00062 #ifndef __SGI_STL_INTERNAL_HASH_SET_H 00063 #define __SGI_STL_INTERNAL_HASH_SET_H 00064 00065 #include <ext/stl_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 declaration. 00076 00077 template <class _Value, 00078 class _HashFcn = hash<_Value>, 00079 class _EqualKey = equal_to<_Value>, 00080 class _Alloc = allocator<_Value> > 00081 class hash_set; 00082 00083 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc> 00084 inline bool 00085 operator==(const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs1, 00086 const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs2); 00087 00093 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc> 00094 class hash_set 00095 { 00096 // concept requirements 00097 __glibcpp_class_requires(_Value, _SGIAssignableConcept) 00098 __glibcpp_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept); 00099 __glibcpp_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept); 00100 00101 private: 00102 typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>, 00103 _EqualKey, _Alloc> _Ht; 00104 _Ht _M_ht; 00105 00106 public: 00107 typedef typename _Ht::key_type key_type; 00108 typedef typename _Ht::value_type value_type; 00109 typedef typename _Ht::hasher hasher; 00110 typedef typename _Ht::key_equal key_equal; 00111 00112 typedef typename _Ht::size_type size_type; 00113 typedef typename _Ht::difference_type difference_type; 00114 typedef typename _Ht::const_pointer pointer; 00115 typedef typename _Ht::const_pointer const_pointer; 00116 typedef typename _Ht::const_reference reference; 00117 typedef typename _Ht::const_reference const_reference; 00118 00119 typedef typename _Ht::const_iterator iterator; 00120 typedef typename _Ht::const_iterator const_iterator; 00121 00122 typedef typename _Ht::allocator_type allocator_type; 00123 00124 hasher hash_funct() const { return _M_ht.hash_funct(); } 00125 key_equal key_eq() const { return _M_ht.key_eq(); } 00126 allocator_type get_allocator() const { return _M_ht.get_allocator(); } 00127 00128 public: 00129 hash_set() 00130 : _M_ht(100, hasher(), key_equal(), allocator_type()) {} 00131 explicit hash_set(size_type __n) 00132 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {} 00133 hash_set(size_type __n, const hasher& __hf) 00134 : _M_ht(__n, __hf, key_equal(), allocator_type()) {} 00135 hash_set(size_type __n, const hasher& __hf, const key_equal& __eql, 00136 const allocator_type& __a = allocator_type()) 00137 : _M_ht(__n, __hf, __eql, __a) {} 00138 00139 template <class _InputIterator> 00140 hash_set(_InputIterator __f, _InputIterator __l) 00141 : _M_ht(100, hasher(), key_equal(), allocator_type()) 00142 { _M_ht.insert_unique(__f, __l); } 00143 template <class _InputIterator> 00144 hash_set(_InputIterator __f, _InputIterator __l, size_type __n) 00145 : _M_ht(__n, hasher(), key_equal(), allocator_type()) 00146 { _M_ht.insert_unique(__f, __l); } 00147 template <class _InputIterator> 00148 hash_set(_InputIterator __f, _InputIterator __l, size_type __n, 00149 const hasher& __hf) 00150 : _M_ht(__n, __hf, key_equal(), allocator_type()) 00151 { _M_ht.insert_unique(__f, __l); } 00152 template <class _InputIterator> 00153 hash_set(_InputIterator __f, _InputIterator __l, size_type __n, 00154 const hasher& __hf, const key_equal& __eql, 00155 const allocator_type& __a = allocator_type()) 00156 : _M_ht(__n, __hf, __eql, __a) 00157 { _M_ht.insert_unique(__f, __l); } 00158 00159 public: 00160 size_type size() const { return _M_ht.size(); } 00161 size_type max_size() const { return _M_ht.max_size(); } 00162 bool empty() const { return _M_ht.empty(); } 00163 void swap(hash_set& __hs) { _M_ht.swap(__hs._M_ht); } 00164 00165 template <class _Val, class _HF, class _EqK, class _Al> 00166 friend bool operator== (const hash_set<_Val, _HF, _EqK, _Al>&, 00167 const hash_set<_Val, _HF, _EqK, _Al>&); 00168 00169 iterator begin() const { return _M_ht.begin(); } 00170 iterator end() const { return _M_ht.end(); } 00171 00172 public: 00173 pair<iterator, bool> insert(const value_type& __obj) 00174 { 00175 pair<typename _Ht::iterator, bool> __p = _M_ht.insert_unique(__obj); 00176 return pair<iterator,bool>(__p.first, __p.second); 00177 } 00178 template <class _InputIterator> 00179 void insert(_InputIterator __f, _InputIterator __l) 00180 { _M_ht.insert_unique(__f,__l); } 00181 pair<iterator, bool> insert_noresize(const value_type& __obj) 00182 { 00183 pair<typename _Ht::iterator, bool> __p = 00184 _M_ht.insert_unique_noresize(__obj); 00185 return pair<iterator, bool>(__p.first, __p.second); 00186 } 00187 00188 iterator find(const key_type& __key) const { return _M_ht.find(__key); } 00189 00190 size_type count(const key_type& __key) const { return _M_ht.count(__key); } 00191 00192 pair<iterator, iterator> equal_range(const key_type& __key) const 00193 { return _M_ht.equal_range(__key); } 00194 00195 size_type erase(const key_type& __key) {return _M_ht.erase(__key); } 00196 void erase(iterator __it) { _M_ht.erase(__it); } 00197 void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); } 00198 void clear() { _M_ht.clear(); } 00199 00200 public: 00201 void resize(size_type __hint) { _M_ht.resize(__hint); } 00202 size_type bucket_count() const { return _M_ht.bucket_count(); } 00203 size_type max_bucket_count() const { return _M_ht.max_bucket_count(); } 00204 size_type elems_in_bucket(size_type __n) const 00205 { return _M_ht.elems_in_bucket(__n); } 00206 }; 00207 00208 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc> 00209 inline bool 00210 operator==(const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs1, 00211 const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs2) 00212 { 00213 return __hs1._M_ht == __hs2._M_ht; 00214 } 00215 00216 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc> 00217 inline bool 00218 operator!=(const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs1, 00219 const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs2) { 00220 return !(__hs1 == __hs2); 00221 } 00222 00223 template <class _Val, class _HashFcn, class _EqualKey, class _Alloc> 00224 inline void 00225 swap(hash_set<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1, 00226 hash_set<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2) 00227 { 00228 __hs1.swap(__hs2); 00229 } 00230 00231 00232 template <class _Value, 00233 class _HashFcn = hash<_Value>, 00234 class _EqualKey = equal_to<_Value>, 00235 class _Alloc = allocator<_Value> > 00236 class hash_multiset; 00237 00238 template <class _Val, class _HashFcn, class _EqualKey, class _Alloc> 00239 inline bool 00240 operator==(const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1, 00241 const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2); 00242 00243 00249 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc> 00250 class hash_multiset 00251 { 00252 // concept requirements 00253 __glibcpp_class_requires(_Value, _SGIAssignableConcept) 00254 __glibcpp_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept); 00255 __glibcpp_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept); 00256 00257 private: 00258 typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>, 00259 _EqualKey, _Alloc> _Ht; 00260 _Ht _M_ht; 00261 00262 public: 00263 typedef typename _Ht::key_type key_type; 00264 typedef typename _Ht::value_type value_type; 00265 typedef typename _Ht::hasher hasher; 00266 typedef typename _Ht::key_equal key_equal; 00267 00268 typedef typename _Ht::size_type size_type; 00269 typedef typename _Ht::difference_type difference_type; 00270 typedef typename _Ht::const_pointer pointer; 00271 typedef typename _Ht::const_pointer const_pointer; 00272 typedef typename _Ht::const_reference reference; 00273 typedef typename _Ht::const_reference const_reference; 00274 00275 typedef typename _Ht::const_iterator iterator; 00276 typedef typename _Ht::const_iterator const_iterator; 00277 00278 typedef typename _Ht::allocator_type allocator_type; 00279 00280 hasher hash_funct() const { return _M_ht.hash_funct(); } 00281 key_equal key_eq() const { return _M_ht.key_eq(); } 00282 allocator_type get_allocator() const { return _M_ht.get_allocator(); } 00283 00284 public: 00285 hash_multiset() 00286 : _M_ht(100, hasher(), key_equal(), allocator_type()) {} 00287 explicit hash_multiset(size_type __n) 00288 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {} 00289 hash_multiset(size_type __n, const hasher& __hf) 00290 : _M_ht(__n, __hf, key_equal(), allocator_type()) {} 00291 hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql, 00292 const allocator_type& __a = allocator_type()) 00293 : _M_ht(__n, __hf, __eql, __a) {} 00294 00295 template <class _InputIterator> 00296 hash_multiset(_InputIterator __f, _InputIterator __l) 00297 : _M_ht(100, hasher(), key_equal(), allocator_type()) 00298 { _M_ht.insert_equal(__f, __l); } 00299 template <class _InputIterator> 00300 hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n) 00301 : _M_ht(__n, hasher(), key_equal(), allocator_type()) 00302 { _M_ht.insert_equal(__f, __l); } 00303 template <class _InputIterator> 00304 hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n, 00305 const hasher& __hf) 00306 : _M_ht(__n, __hf, key_equal(), allocator_type()) 00307 { _M_ht.insert_equal(__f, __l); } 00308 template <class _InputIterator> 00309 hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n, 00310 const hasher& __hf, const key_equal& __eql, 00311 const allocator_type& __a = allocator_type()) 00312 : _M_ht(__n, __hf, __eql, __a) 00313 { _M_ht.insert_equal(__f, __l); } 00314 00315 public: 00316 size_type size() const { return _M_ht.size(); } 00317 size_type max_size() const { return _M_ht.max_size(); } 00318 bool empty() const { return _M_ht.empty(); } 00319 void swap(hash_multiset& hs) { _M_ht.swap(hs._M_ht); } 00320 00321 template <class _Val, class _HF, class _EqK, class _Al> 00322 friend bool operator== (const hash_multiset<_Val, _HF, _EqK, _Al>&, 00323 const hash_multiset<_Val, _HF, _EqK, _Al>&); 00324 00325 iterator begin() const { return _M_ht.begin(); } 00326 iterator end() const { return _M_ht.end(); } 00327 00328 public: 00329 iterator insert(const value_type& __obj) 00330 { return _M_ht.insert_equal(__obj); } 00331 template <class _InputIterator> 00332 void insert(_InputIterator __f, _InputIterator __l) 00333 { _M_ht.insert_equal(__f,__l); } 00334 iterator insert_noresize(const value_type& __obj) 00335 { return _M_ht.insert_equal_noresize(__obj); } 00336 00337 iterator find(const key_type& __key) const { return _M_ht.find(__key); } 00338 00339 size_type count(const key_type& __key) const { return _M_ht.count(__key); } 00340 00341 pair<iterator, iterator> equal_range(const key_type& __key) const 00342 { return _M_ht.equal_range(__key); } 00343 00344 size_type erase(const key_type& __key) {return _M_ht.erase(__key); } 00345 void erase(iterator __it) { _M_ht.erase(__it); } 00346 void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); } 00347 void clear() { _M_ht.clear(); } 00348 00349 public: 00350 void resize(size_type __hint) { _M_ht.resize(__hint); } 00351 size_type bucket_count() const { return _M_ht.bucket_count(); } 00352 size_type max_bucket_count() const { return _M_ht.max_bucket_count(); } 00353 size_type elems_in_bucket(size_type __n) const 00354 { return _M_ht.elems_in_bucket(__n); } 00355 }; 00356 00357 template <class _Val, class _HashFcn, class _EqualKey, class _Alloc> 00358 inline bool 00359 operator==(const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1, 00360 const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2) 00361 { 00362 return __hs1._M_ht == __hs2._M_ht; 00363 } 00364 00365 template <class _Val, class _HashFcn, class _EqualKey, class _Alloc> 00366 inline bool 00367 operator!=(const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1, 00368 const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2) { 00369 return !(__hs1 == __hs2); 00370 } 00371 00372 template <class _Val, class _HashFcn, class _EqualKey, class _Alloc> 00373 inline void 00374 swap(hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1, 00375 hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2) { 00376 __hs1.swap(__hs2); 00377 } 00378 00379 } // namespace __gnu_cxx 00380 00381 namespace std 00382 { 00383 // Specialization of insert_iterator so that it will work for hash_set 00384 // and hash_multiset. 00385 00386 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc> 00387 class insert_iterator<__gnu_cxx::hash_set<_Value, _HashFcn, _EqualKey, _Alloc> > { 00388 protected: 00389 typedef __gnu_cxx::hash_set<_Value, _HashFcn, _EqualKey, _Alloc> _Container; 00390 _Container* container; 00391 public: 00392 typedef _Container container_type; 00393 typedef output_iterator_tag iterator_category; 00394 typedef void value_type; 00395 typedef void difference_type; 00396 typedef void pointer; 00397 typedef void reference; 00398 00399 insert_iterator(_Container& __x) : container(&__x) {} 00400 insert_iterator(_Container& __x, typename _Container::iterator) 00401 : container(&__x) {} 00402 insert_iterator<_Container>& 00403 operator=(const typename _Container::value_type& __value) { 00404 container->insert(__value); 00405 return *this; 00406 } 00407 insert_iterator<_Container>& operator*() { return *this; } 00408 insert_iterator<_Container>& operator++() { return *this; } 00409 insert_iterator<_Container>& operator++(int) { return *this; } 00410 }; 00411 00412 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc> 00413 class insert_iterator<__gnu_cxx::hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc> > { 00414 protected: 00415 typedef __gnu_cxx::hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc> _Container; 00416 _Container* container; 00417 typename _Container::iterator iter; 00418 public: 00419 typedef _Container container_type; 00420 typedef output_iterator_tag iterator_category; 00421 typedef void value_type; 00422 typedef void difference_type; 00423 typedef void pointer; 00424 typedef void reference; 00425 00426 insert_iterator(_Container& __x) : container(&__x) {} 00427 insert_iterator(_Container& __x, typename _Container::iterator) 00428 : container(&__x) {} 00429 insert_iterator<_Container>& 00430 operator=(const typename _Container::value_type& __value) { 00431 container->insert(__value); 00432 return *this; 00433 } 00434 insert_iterator<_Container>& operator*() { return *this; } 00435 insert_iterator<_Container>& operator++() { return *this; } 00436 insert_iterator<_Container>& operator++(int) { return *this; } 00437 }; 00438 00439 } // namespace std 00440 00441 #endif /* __SGI_STL_INTERNAL_HASH_SET_H */ 00442 00443 // Local Variables: 00444 // mode:C++ 00445 // End:

Generated on Wed Sep 29 13:54:49 2004 for libstdc++-v3 Source by doxygen 1.3.7