libstdc++
|
00001 // Hashing set implementation -*- C++ -*- 00002 00003 // Copyright (C) 2001, 2002, 2004, 2005, 2006, 2009, 2010 00004 // Free Software Foundation, Inc. 00005 // 00006 // This file is part of the GNU ISO C++ Library. This library is free 00007 // software; you can redistribute it and/or modify it under the 00008 // terms of the GNU General Public License as published by the 00009 // Free Software Foundation; either version 3, or (at your option) 00010 // any later version. 00011 00012 // This library is distributed in the hope that it will be useful, 00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00015 // GNU General Public License for more details. 00016 00017 // Under Section 7 of GPL version 3, you are granted additional 00018 // permissions described in the GCC Runtime Library Exception, version 00019 // 3.1, as published by the Free Software Foundation. 00020 00021 // You should have received a copy of the GNU General Public License and 00022 // a copy of the GCC Runtime Library Exception along with this program; 00023 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00024 // <http://www.gnu.org/licenses/>. 00025 00026 /* 00027 * Copyright (c) 1996 00028 * Silicon Graphics Computer Systems, Inc. 00029 * 00030 * Permission to use, copy, modify, distribute and sell this software 00031 * and its documentation for any purpose is hereby granted without fee, 00032 * provided that the above copyright notice appear in all copies and 00033 * that both that copyright notice and this permission notice appear 00034 * in supporting documentation. Silicon Graphics makes no 00035 * representations about the suitability of this software for any 00036 * purpose. It is provided "as is" without express or implied warranty. 00037 * 00038 * 00039 * Copyright (c) 1994 00040 * Hewlett-Packard Company 00041 * 00042 * Permission to use, copy, modify, distribute and sell this software 00043 * and its documentation for any purpose is hereby granted without fee, 00044 * provided that the above copyright notice appear in all copies and 00045 * that both that copyright notice and this permission notice appear 00046 * in supporting documentation. Hewlett-Packard Company makes no 00047 * representations about the suitability of this software for any 00048 * purpose. It is provided "as is" without express or implied warranty. 00049 * 00050 */ 00051 00052 /** @file backward/hash_set 00053 * This file is a GNU extension to the Standard C++ Library (possibly 00054 * containing extensions from the HP/SGI STL subset). 00055 */ 00056 00057 #ifndef _BACKWARD_HASH_SET 00058 #define _BACKWARD_HASH_SET 1 00059 00060 #ifndef _GLIBCXX_PERMIT_BACKWARD_HASH 00061 #include "backward_warning.h" 00062 #endif 00063 00064 #include <bits/c++config.h> 00065 #include <backward/hashtable.h> 00066 #include <bits/concept_check.h> 00067 00068 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default) 00069 { 00070 _GLIBCXX_BEGIN_NAMESPACE_VERSION 00071 00072 using std::equal_to; 00073 using std::allocator; 00074 using std::pair; 00075 using std::_Identity; 00076 00077 /** 00078 * This is an SGI extension. 00079 * @ingroup SGIextensions 00080 * @doctodo 00081 */ 00082 template<class _Value, class _HashFcn = hash<_Value>, 00083 class _EqualKey = equal_to<_Value>, 00084 class _Alloc = allocator<_Value> > 00085 class hash_set 00086 { 00087 // concept requirements 00088 __glibcxx_class_requires(_Value, _SGIAssignableConcept) 00089 __glibcxx_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept) 00090 __glibcxx_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept) 00091 00092 private: 00093 typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>, 00094 _EqualKey, _Alloc> _Ht; 00095 _Ht _M_ht; 00096 00097 public: 00098 typedef typename _Ht::key_type key_type; 00099 typedef typename _Ht::value_type value_type; 00100 typedef typename _Ht::hasher hasher; 00101 typedef typename _Ht::key_equal key_equal; 00102 00103 typedef typename _Ht::size_type size_type; 00104 typedef typename _Ht::difference_type difference_type; 00105 typedef typename _Alloc::pointer pointer; 00106 typedef typename _Alloc::const_pointer const_pointer; 00107 typedef typename _Alloc::reference reference; 00108 typedef typename _Alloc::const_reference const_reference; 00109 00110 typedef typename _Ht::const_iterator iterator; 00111 typedef typename _Ht::const_iterator const_iterator; 00112 00113 typedef typename _Ht::allocator_type allocator_type; 00114 00115 hasher 00116 hash_funct() const 00117 { return _M_ht.hash_funct(); } 00118 00119 key_equal 00120 key_eq() const 00121 { return _M_ht.key_eq(); } 00122 00123 allocator_type 00124 get_allocator() const 00125 { return _M_ht.get_allocator(); } 00126 00127 hash_set() 00128 : _M_ht(100, hasher(), key_equal(), allocator_type()) {} 00129 00130 explicit 00131 hash_set(size_type __n) 00132 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {} 00133 00134 hash_set(size_type __n, const hasher& __hf) 00135 : _M_ht(__n, __hf, key_equal(), allocator_type()) {} 00136 00137 hash_set(size_type __n, const hasher& __hf, const key_equal& __eql, 00138 const allocator_type& __a = allocator_type()) 00139 : _M_ht(__n, __hf, __eql, __a) {} 00140 00141 template<class _InputIterator> 00142 hash_set(_InputIterator __f, _InputIterator __l) 00143 : _M_ht(100, hasher(), key_equal(), allocator_type()) 00144 { _M_ht.insert_unique(__f, __l); } 00145 00146 template<class _InputIterator> 00147 hash_set(_InputIterator __f, _InputIterator __l, size_type __n) 00148 : _M_ht(__n, hasher(), key_equal(), allocator_type()) 00149 { _M_ht.insert_unique(__f, __l); } 00150 00151 template<class _InputIterator> 00152 hash_set(_InputIterator __f, _InputIterator __l, size_type __n, 00153 const hasher& __hf) 00154 : _M_ht(__n, __hf, key_equal(), allocator_type()) 00155 { _M_ht.insert_unique(__f, __l); } 00156 00157 template<class _InputIterator> 00158 hash_set(_InputIterator __f, _InputIterator __l, size_type __n, 00159 const hasher& __hf, const key_equal& __eql, 00160 const allocator_type& __a = allocator_type()) 00161 : _M_ht(__n, __hf, __eql, __a) 00162 { _M_ht.insert_unique(__f, __l); } 00163 00164 size_type 00165 size() const 00166 { return _M_ht.size(); } 00167 00168 size_type 00169 max_size() const 00170 { return _M_ht.max_size(); } 00171 00172 bool 00173 empty() const 00174 { return _M_ht.empty(); } 00175 00176 void 00177 swap(hash_set& __hs) 00178 { _M_ht.swap(__hs._M_ht); } 00179 00180 template<class _Val, class _HF, class _EqK, class _Al> 00181 friend bool 00182 operator==(const hash_set<_Val, _HF, _EqK, _Al>&, 00183 const hash_set<_Val, _HF, _EqK, _Al>&); 00184 00185 iterator 00186 begin() const 00187 { return _M_ht.begin(); } 00188 00189 iterator 00190 end() const 00191 { return _M_ht.end(); } 00192 00193 pair<iterator, bool> 00194 insert(const value_type& __obj) 00195 { 00196 pair<typename _Ht::iterator, bool> __p = _M_ht.insert_unique(__obj); 00197 return pair<iterator,bool>(__p.first, __p.second); 00198 } 00199 00200 template<class _InputIterator> 00201 void 00202 insert(_InputIterator __f, _InputIterator __l) 00203 { _M_ht.insert_unique(__f, __l); } 00204 00205 pair<iterator, bool> 00206 insert_noresize(const value_type& __obj) 00207 { 00208 pair<typename _Ht::iterator, bool> __p 00209 = _M_ht.insert_unique_noresize(__obj); 00210 return pair<iterator, bool>(__p.first, __p.second); 00211 } 00212 00213 iterator 00214 find(const key_type& __key) const 00215 { return _M_ht.find(__key); } 00216 00217 size_type 00218 count(const key_type& __key) const 00219 { return _M_ht.count(__key); } 00220 00221 pair<iterator, iterator> 00222 equal_range(const key_type& __key) const 00223 { return _M_ht.equal_range(__key); } 00224 00225 size_type 00226 erase(const key_type& __key) 00227 {return _M_ht.erase(__key); } 00228 00229 void 00230 erase(iterator __it) 00231 { _M_ht.erase(__it); } 00232 00233 void 00234 erase(iterator __f, iterator __l) 00235 { _M_ht.erase(__f, __l); } 00236 00237 void 00238 clear() 00239 { _M_ht.clear(); } 00240 00241 void 00242 resize(size_type __hint) 00243 { _M_ht.resize(__hint); } 00244 00245 size_type 00246 bucket_count() const 00247 { return _M_ht.bucket_count(); } 00248 00249 size_type 00250 max_bucket_count() const 00251 { return _M_ht.max_bucket_count(); } 00252 00253 size_type 00254 elems_in_bucket(size_type __n) const 00255 { return _M_ht.elems_in_bucket(__n); } 00256 }; 00257 00258 template<class _Value, class _HashFcn, class _EqualKey, class _Alloc> 00259 inline bool 00260 operator==(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs1, 00261 const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs2) 00262 { return __hs1._M_ht == __hs2._M_ht; } 00263 00264 template<class _Value, class _HashFcn, class _EqualKey, class _Alloc> 00265 inline bool 00266 operator!=(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs1, 00267 const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs2) 00268 { return !(__hs1 == __hs2); } 00269 00270 template<class _Val, class _HashFcn, class _EqualKey, class _Alloc> 00271 inline void 00272 swap(hash_set<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1, 00273 hash_set<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2) 00274 { __hs1.swap(__hs2); } 00275 00276 00277 /** 00278 * This is an SGI extension. 00279 * @ingroup SGIextensions 00280 * @doctodo 00281 */ 00282 template<class _Value, 00283 class _HashFcn = hash<_Value>, 00284 class _EqualKey = equal_to<_Value>, 00285 class _Alloc = allocator<_Value> > 00286 class hash_multiset 00287 { 00288 // concept requirements 00289 __glibcxx_class_requires(_Value, _SGIAssignableConcept) 00290 __glibcxx_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept) 00291 __glibcxx_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept) 00292 00293 private: 00294 typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>, 00295 _EqualKey, _Alloc> _Ht; 00296 _Ht _M_ht; 00297 00298 public: 00299 typedef typename _Ht::key_type key_type; 00300 typedef typename _Ht::value_type value_type; 00301 typedef typename _Ht::hasher hasher; 00302 typedef typename _Ht::key_equal key_equal; 00303 00304 typedef typename _Ht::size_type size_type; 00305 typedef typename _Ht::difference_type difference_type; 00306 typedef typename _Alloc::pointer pointer; 00307 typedef typename _Alloc::const_pointer const_pointer; 00308 typedef typename _Alloc::reference reference; 00309 typedef typename _Alloc::const_reference const_reference; 00310 00311 typedef typename _Ht::const_iterator iterator; 00312 typedef typename _Ht::const_iterator const_iterator; 00313 00314 typedef typename _Ht::allocator_type allocator_type; 00315 00316 hasher 00317 hash_funct() const 00318 { return _M_ht.hash_funct(); } 00319 00320 key_equal 00321 key_eq() const 00322 { return _M_ht.key_eq(); } 00323 00324 allocator_type 00325 get_allocator() const 00326 { return _M_ht.get_allocator(); } 00327 00328 hash_multiset() 00329 : _M_ht(100, hasher(), key_equal(), allocator_type()) {} 00330 00331 explicit 00332 hash_multiset(size_type __n) 00333 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {} 00334 00335 hash_multiset(size_type __n, const hasher& __hf) 00336 : _M_ht(__n, __hf, key_equal(), allocator_type()) {} 00337 00338 hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql, 00339 const allocator_type& __a = allocator_type()) 00340 : _M_ht(__n, __hf, __eql, __a) {} 00341 00342 template<class _InputIterator> 00343 hash_multiset(_InputIterator __f, _InputIterator __l) 00344 : _M_ht(100, hasher(), key_equal(), allocator_type()) 00345 { _M_ht.insert_equal(__f, __l); } 00346 00347 template<class _InputIterator> 00348 hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n) 00349 : _M_ht(__n, hasher(), key_equal(), allocator_type()) 00350 { _M_ht.insert_equal(__f, __l); } 00351 00352 template<class _InputIterator> 00353 hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n, 00354 const hasher& __hf) 00355 : _M_ht(__n, __hf, key_equal(), allocator_type()) 00356 { _M_ht.insert_equal(__f, __l); } 00357 00358 template<class _InputIterator> 00359 hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n, 00360 const hasher& __hf, const key_equal& __eql, 00361 const allocator_type& __a = allocator_type()) 00362 : _M_ht(__n, __hf, __eql, __a) 00363 { _M_ht.insert_equal(__f, __l); } 00364 00365 size_type 00366 size() const 00367 { return _M_ht.size(); } 00368 00369 size_type 00370 max_size() const 00371 { return _M_ht.max_size(); } 00372 00373 bool 00374 empty() const 00375 { return _M_ht.empty(); } 00376 00377 void 00378 swap(hash_multiset& hs) 00379 { _M_ht.swap(hs._M_ht); } 00380 00381 template<class _Val, class _HF, class _EqK, class _Al> 00382 friend bool 00383 operator==(const hash_multiset<_Val, _HF, _EqK, _Al>&, 00384 const hash_multiset<_Val, _HF, _EqK, _Al>&); 00385 00386 iterator 00387 begin() const 00388 { return _M_ht.begin(); } 00389 00390 iterator 00391 end() const 00392 { return _M_ht.end(); } 00393 00394 iterator 00395 insert(const value_type& __obj) 00396 { return _M_ht.insert_equal(__obj); } 00397 00398 template<class _InputIterator> 00399 void 00400 insert(_InputIterator __f, _InputIterator __l) 00401 { _M_ht.insert_equal(__f,__l); } 00402 00403 iterator 00404 insert_noresize(const value_type& __obj) 00405 { return _M_ht.insert_equal_noresize(__obj); } 00406 00407 iterator 00408 find(const key_type& __key) const 00409 { return _M_ht.find(__key); } 00410 00411 size_type 00412 count(const key_type& __key) const 00413 { return _M_ht.count(__key); } 00414 00415 pair<iterator, iterator> 00416 equal_range(const key_type& __key) const 00417 { return _M_ht.equal_range(__key); } 00418 00419 size_type 00420 erase(const key_type& __key) 00421 { return _M_ht.erase(__key); } 00422 00423 void 00424 erase(iterator __it) 00425 { _M_ht.erase(__it); } 00426 00427 void 00428 erase(iterator __f, iterator __l) 00429 { _M_ht.erase(__f, __l); } 00430 00431 void 00432 clear() 00433 { _M_ht.clear(); } 00434 00435 void 00436 resize(size_type __hint) 00437 { _M_ht.resize(__hint); } 00438 00439 size_type 00440 bucket_count() const 00441 { return _M_ht.bucket_count(); } 00442 00443 size_type 00444 max_bucket_count() const 00445 { return _M_ht.max_bucket_count(); } 00446 00447 size_type 00448 elems_in_bucket(size_type __n) const 00449 { return _M_ht.elems_in_bucket(__n); } 00450 }; 00451 00452 template<class _Val, class _HashFcn, class _EqualKey, class _Alloc> 00453 inline bool 00454 operator==(const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1, 00455 const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2) 00456 { return __hs1._M_ht == __hs2._M_ht; } 00457 00458 template<class _Val, class _HashFcn, class _EqualKey, class _Alloc> 00459 inline bool 00460 operator!=(const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1, 00461 const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2) 00462 { return !(__hs1 == __hs2); } 00463 00464 template<class _Val, class _HashFcn, class _EqualKey, class _Alloc> 00465 inline void 00466 swap(hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1, 00467 hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2) 00468 { __hs1.swap(__hs2); } 00469 00470 _GLIBCXX_END_NAMESPACE_VERSION 00471 } // namespace 00472 00473 namespace std _GLIBCXX_VISIBILITY(default) 00474 { 00475 _GLIBCXX_BEGIN_NAMESPACE_VERSION 00476 00477 // Specialization of insert_iterator so that it will work for hash_set 00478 // and hash_multiset. 00479 template<class _Value, class _HashFcn, class _EqualKey, class _Alloc> 00480 class insert_iterator<__gnu_cxx::hash_set<_Value, _HashFcn, 00481 _EqualKey, _Alloc> > 00482 { 00483 protected: 00484 typedef __gnu_cxx::hash_set<_Value, _HashFcn, _EqualKey, _Alloc> 00485 _Container; 00486 _Container* container; 00487 00488 public: 00489 typedef _Container container_type; 00490 typedef output_iterator_tag iterator_category; 00491 typedef void value_type; 00492 typedef void difference_type; 00493 typedef void pointer; 00494 typedef void reference; 00495 00496 insert_iterator(_Container& __x) 00497 : container(&__x) {} 00498 00499 insert_iterator(_Container& __x, typename _Container::iterator) 00500 : container(&__x) {} 00501 00502 insert_iterator<_Container>& 00503 operator=(const typename _Container::value_type& __value) 00504 { 00505 container->insert(__value); 00506 return *this; 00507 } 00508 00509 insert_iterator<_Container>& 00510 operator*() 00511 { return *this; } 00512 00513 insert_iterator<_Container>& 00514 operator++() 00515 { return *this; } 00516 00517 insert_iterator<_Container>& 00518 operator++(int) 00519 { return *this; } 00520 }; 00521 00522 template<class _Value, class _HashFcn, class _EqualKey, class _Alloc> 00523 class insert_iterator<__gnu_cxx::hash_multiset<_Value, _HashFcn, 00524 _EqualKey, _Alloc> > 00525 { 00526 protected: 00527 typedef __gnu_cxx::hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc> 00528 _Container; 00529 _Container* container; 00530 typename _Container::iterator iter; 00531 00532 public: 00533 typedef _Container container_type; 00534 typedef output_iterator_tag iterator_category; 00535 typedef void value_type; 00536 typedef void difference_type; 00537 typedef void pointer; 00538 typedef void reference; 00539 00540 insert_iterator(_Container& __x) 00541 : container(&__x) {} 00542 00543 insert_iterator(_Container& __x, typename _Container::iterator) 00544 : container(&__x) {} 00545 00546 insert_iterator<_Container>& 00547 operator=(const typename _Container::value_type& __value) 00548 { 00549 container->insert(__value); 00550 return *this; 00551 } 00552 00553 insert_iterator<_Container>& 00554 operator*() 00555 { return *this; } 00556 00557 insert_iterator<_Container>& 00558 operator++() 00559 { return *this; } 00560 00561 insert_iterator<_Container>& 00562 operator++(int) { return *this; } 00563 }; 00564 00565 _GLIBCXX_END_NAMESPACE_VERSION 00566 } // namespace 00567 00568 #endif