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 #include "backward_warning.h" 00061 #include <bits/c++config.h> 00062 #include <backward/hashtable.h> 00063 #include <bits/concept_check.h> 00064 00065 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) 00066 00067 using std::equal_to; 00068 using std::allocator; 00069 using std::pair; 00070 using std::_Identity; 00071 00072 /** 00073 * This is an SGI extension. 00074 * @ingroup SGIextensions 00075 * @doctodo 00076 */ 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 // concept requirements 00083 __glibcxx_class_requires(_Value, _SGIAssignableConcept) 00084 __glibcxx_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept) 00085 __glibcxx_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept) 00086 00087 private: 00088 typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>, 00089 _EqualKey, _Alloc> _Ht; 00090 _Ht _M_ht; 00091 00092 public: 00093 typedef typename _Ht::key_type key_type; 00094 typedef typename _Ht::value_type value_type; 00095 typedef typename _Ht::hasher hasher; 00096 typedef typename _Ht::key_equal key_equal; 00097 00098 typedef typename _Ht::size_type size_type; 00099 typedef typename _Ht::difference_type difference_type; 00100 typedef typename _Alloc::pointer pointer; 00101 typedef typename _Alloc::const_pointer const_pointer; 00102 typedef typename _Alloc::reference reference; 00103 typedef typename _Alloc::const_reference const_reference; 00104 00105 typedef typename _Ht::const_iterator iterator; 00106 typedef typename _Ht::const_iterator const_iterator; 00107 00108 typedef typename _Ht::allocator_type allocator_type; 00109 00110 hasher 00111 hash_funct() const 00112 { return _M_ht.hash_funct(); } 00113 00114 key_equal 00115 key_eq() const 00116 { return _M_ht.key_eq(); } 00117 00118 allocator_type 00119 get_allocator() const 00120 { return _M_ht.get_allocator(); } 00121 00122 hash_set() 00123 : _M_ht(100, hasher(), key_equal(), allocator_type()) {} 00124 00125 explicit 00126 hash_set(size_type __n) 00127 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {} 00128 00129 hash_set(size_type __n, const hasher& __hf) 00130 : _M_ht(__n, __hf, key_equal(), allocator_type()) {} 00131 00132 hash_set(size_type __n, const hasher& __hf, const key_equal& __eql, 00133 const allocator_type& __a = allocator_type()) 00134 : _M_ht(__n, __hf, __eql, __a) {} 00135 00136 template<class _InputIterator> 00137 hash_set(_InputIterator __f, _InputIterator __l) 00138 : _M_ht(100, hasher(), key_equal(), allocator_type()) 00139 { _M_ht.insert_unique(__f, __l); } 00140 00141 template<class _InputIterator> 00142 hash_set(_InputIterator __f, _InputIterator __l, size_type __n) 00143 : _M_ht(__n, 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 const hasher& __hf) 00149 : _M_ht(__n, __hf, key_equal(), allocator_type()) 00150 { _M_ht.insert_unique(__f, __l); } 00151 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 size_type 00160 size() const 00161 { return _M_ht.size(); } 00162 00163 size_type 00164 max_size() const 00165 { return _M_ht.max_size(); } 00166 00167 bool 00168 empty() const 00169 { return _M_ht.empty(); } 00170 00171 void 00172 swap(hash_set& __hs) 00173 { _M_ht.swap(__hs._M_ht); } 00174 00175 template<class _Val, class _HF, class _EqK, class _Al> 00176 friend bool 00177 operator==(const hash_set<_Val, _HF, _EqK, _Al>&, 00178 const hash_set<_Val, _HF, _EqK, _Al>&); 00179 00180 iterator 00181 begin() const 00182 { return _M_ht.begin(); } 00183 00184 iterator 00185 end() const 00186 { return _M_ht.end(); } 00187 00188 pair<iterator, bool> 00189 insert(const value_type& __obj) 00190 { 00191 pair<typename _Ht::iterator, bool> __p = _M_ht.insert_unique(__obj); 00192 return pair<iterator,bool>(__p.first, __p.second); 00193 } 00194 00195 template<class _InputIterator> 00196 void 00197 insert(_InputIterator __f, _InputIterator __l) 00198 { _M_ht.insert_unique(__f, __l); } 00199 00200 pair<iterator, bool> 00201 insert_noresize(const value_type& __obj) 00202 { 00203 pair<typename _Ht::iterator, bool> __p 00204 = _M_ht.insert_unique_noresize(__obj); 00205 return pair<iterator, bool>(__p.first, __p.second); 00206 } 00207 00208 iterator 00209 find(const key_type& __key) const 00210 { return _M_ht.find(__key); } 00211 00212 size_type 00213 count(const key_type& __key) const 00214 { return _M_ht.count(__key); } 00215 00216 pair<iterator, iterator> 00217 equal_range(const key_type& __key) const 00218 { return _M_ht.equal_range(__key); } 00219 00220 size_type 00221 erase(const key_type& __key) 00222 {return _M_ht.erase(__key); } 00223 00224 void 00225 erase(iterator __it) 00226 { _M_ht.erase(__it); } 00227 00228 void 00229 erase(iterator __f, iterator __l) 00230 { _M_ht.erase(__f, __l); } 00231 00232 void 00233 clear() 00234 { _M_ht.clear(); } 00235 00236 void 00237 resize(size_type __hint) 00238 { _M_ht.resize(__hint); } 00239 00240 size_type 00241 bucket_count() const 00242 { return _M_ht.bucket_count(); } 00243 00244 size_type 00245 max_bucket_count() const 00246 { return _M_ht.max_bucket_count(); } 00247 00248 size_type 00249 elems_in_bucket(size_type __n) const 00250 { return _M_ht.elems_in_bucket(__n); } 00251 }; 00252 00253 template<class _Value, class _HashFcn, class _EqualKey, class _Alloc> 00254 inline bool 00255 operator==(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs1, 00256 const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs2) 00257 { return __hs1._M_ht == __hs2._M_ht; } 00258 00259 template<class _Value, class _HashFcn, class _EqualKey, class _Alloc> 00260 inline bool 00261 operator!=(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs1, 00262 const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs2) 00263 { return !(__hs1 == __hs2); } 00264 00265 template<class _Val, class _HashFcn, class _EqualKey, class _Alloc> 00266 inline void 00267 swap(hash_set<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1, 00268 hash_set<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2) 00269 { __hs1.swap(__hs2); } 00270 00271 00272 /** 00273 * This is an SGI extension. 00274 * @ingroup SGIextensions 00275 * @doctodo 00276 */ 00277 template<class _Value, 00278 class _HashFcn = hash<_Value>, 00279 class _EqualKey = equal_to<_Value>, 00280 class _Alloc = allocator<_Value> > 00281 class hash_multiset 00282 { 00283 // concept requirements 00284 __glibcxx_class_requires(_Value, _SGIAssignableConcept) 00285 __glibcxx_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept) 00286 __glibcxx_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept) 00287 00288 private: 00289 typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>, 00290 _EqualKey, _Alloc> _Ht; 00291 _Ht _M_ht; 00292 00293 public: 00294 typedef typename _Ht::key_type key_type; 00295 typedef typename _Ht::value_type value_type; 00296 typedef typename _Ht::hasher hasher; 00297 typedef typename _Ht::key_equal key_equal; 00298 00299 typedef typename _Ht::size_type size_type; 00300 typedef typename _Ht::difference_type difference_type; 00301 typedef typename _Alloc::pointer pointer; 00302 typedef typename _Alloc::const_pointer const_pointer; 00303 typedef typename _Alloc::reference reference; 00304 typedef typename _Alloc::const_reference const_reference; 00305 00306 typedef typename _Ht::const_iterator iterator; 00307 typedef typename _Ht::const_iterator const_iterator; 00308 00309 typedef typename _Ht::allocator_type allocator_type; 00310 00311 hasher 00312 hash_funct() const 00313 { return _M_ht.hash_funct(); } 00314 00315 key_equal 00316 key_eq() const 00317 { return _M_ht.key_eq(); } 00318 00319 allocator_type 00320 get_allocator() const 00321 { return _M_ht.get_allocator(); } 00322 00323 hash_multiset() 00324 : _M_ht(100, hasher(), key_equal(), allocator_type()) {} 00325 00326 explicit 00327 hash_multiset(size_type __n) 00328 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {} 00329 00330 hash_multiset(size_type __n, const hasher& __hf) 00331 : _M_ht(__n, __hf, key_equal(), allocator_type()) {} 00332 00333 hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql, 00334 const allocator_type& __a = allocator_type()) 00335 : _M_ht(__n, __hf, __eql, __a) {} 00336 00337 template<class _InputIterator> 00338 hash_multiset(_InputIterator __f, _InputIterator __l) 00339 : _M_ht(100, hasher(), key_equal(), allocator_type()) 00340 { _M_ht.insert_equal(__f, __l); } 00341 00342 template<class _InputIterator> 00343 hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n) 00344 : _M_ht(__n, 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 const hasher& __hf) 00350 : _M_ht(__n, __hf, key_equal(), allocator_type()) 00351 { _M_ht.insert_equal(__f, __l); } 00352 00353 template<class _InputIterator> 00354 hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n, 00355 const hasher& __hf, const key_equal& __eql, 00356 const allocator_type& __a = allocator_type()) 00357 : _M_ht(__n, __hf, __eql, __a) 00358 { _M_ht.insert_equal(__f, __l); } 00359 00360 size_type 00361 size() const 00362 { return _M_ht.size(); } 00363 00364 size_type 00365 max_size() const 00366 { return _M_ht.max_size(); } 00367 00368 bool 00369 empty() const 00370 { return _M_ht.empty(); } 00371 00372 void 00373 swap(hash_multiset& hs) 00374 { _M_ht.swap(hs._M_ht); } 00375 00376 template<class _Val, class _HF, class _EqK, class _Al> 00377 friend bool 00378 operator==(const hash_multiset<_Val, _HF, _EqK, _Al>&, 00379 const hash_multiset<_Val, _HF, _EqK, _Al>&); 00380 00381 iterator 00382 begin() const 00383 { return _M_ht.begin(); } 00384 00385 iterator 00386 end() const 00387 { return _M_ht.end(); } 00388 00389 iterator 00390 insert(const value_type& __obj) 00391 { return _M_ht.insert_equal(__obj); } 00392 00393 template<class _InputIterator> 00394 void 00395 insert(_InputIterator __f, _InputIterator __l) 00396 { _M_ht.insert_equal(__f,__l); } 00397 00398 iterator 00399 insert_noresize(const value_type& __obj) 00400 { return _M_ht.insert_equal_noresize(__obj); } 00401 00402 iterator 00403 find(const key_type& __key) const 00404 { return _M_ht.find(__key); } 00405 00406 size_type 00407 count(const key_type& __key) const 00408 { return _M_ht.count(__key); } 00409 00410 pair<iterator, iterator> 00411 equal_range(const key_type& __key) const 00412 { return _M_ht.equal_range(__key); } 00413 00414 size_type 00415 erase(const key_type& __key) 00416 { return _M_ht.erase(__key); } 00417 00418 void 00419 erase(iterator __it) 00420 { _M_ht.erase(__it); } 00421 00422 void 00423 erase(iterator __f, iterator __l) 00424 { _M_ht.erase(__f, __l); } 00425 00426 void 00427 clear() 00428 { _M_ht.clear(); } 00429 00430 void 00431 resize(size_type __hint) 00432 { _M_ht.resize(__hint); } 00433 00434 size_type 00435 bucket_count() const 00436 { return _M_ht.bucket_count(); } 00437 00438 size_type 00439 max_bucket_count() const 00440 { return _M_ht.max_bucket_count(); } 00441 00442 size_type 00443 elems_in_bucket(size_type __n) const 00444 { return _M_ht.elems_in_bucket(__n); } 00445 }; 00446 00447 template<class _Val, class _HashFcn, class _EqualKey, class _Alloc> 00448 inline bool 00449 operator==(const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1, 00450 const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2) 00451 { return __hs1._M_ht == __hs2._M_ht; } 00452 00453 template<class _Val, class _HashFcn, class _EqualKey, class _Alloc> 00454 inline bool 00455 operator!=(const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1, 00456 const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2) 00457 { return !(__hs1 == __hs2); } 00458 00459 template<class _Val, class _HashFcn, class _EqualKey, class _Alloc> 00460 inline void 00461 swap(hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1, 00462 hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2) 00463 { __hs1.swap(__hs2); } 00464 00465 _GLIBCXX_END_NAMESPACE 00466 00467 _GLIBCXX_BEGIN_NAMESPACE(std) 00468 00469 // Specialization of insert_iterator so that it will work for hash_set 00470 // and hash_multiset. 00471 template<class _Value, class _HashFcn, class _EqualKey, class _Alloc> 00472 class insert_iterator<__gnu_cxx::hash_set<_Value, _HashFcn, 00473 _EqualKey, _Alloc> > 00474 { 00475 protected: 00476 typedef __gnu_cxx::hash_set<_Value, _HashFcn, _EqualKey, _Alloc> 00477 _Container; 00478 _Container* container; 00479 00480 public: 00481 typedef _Container container_type; 00482 typedef output_iterator_tag iterator_category; 00483 typedef void value_type; 00484 typedef void difference_type; 00485 typedef void pointer; 00486 typedef void reference; 00487 00488 insert_iterator(_Container& __x) 00489 : container(&__x) {} 00490 00491 insert_iterator(_Container& __x, typename _Container::iterator) 00492 : container(&__x) {} 00493 00494 insert_iterator<_Container>& 00495 operator=(const typename _Container::value_type& __value) 00496 { 00497 container->insert(__value); 00498 return *this; 00499 } 00500 00501 insert_iterator<_Container>& 00502 operator*() 00503 { return *this; } 00504 00505 insert_iterator<_Container>& 00506 operator++() 00507 { return *this; } 00508 00509 insert_iterator<_Container>& 00510 operator++(int) 00511 { return *this; } 00512 }; 00513 00514 template<class _Value, class _HashFcn, class _EqualKey, class _Alloc> 00515 class insert_iterator<__gnu_cxx::hash_multiset<_Value, _HashFcn, 00516 _EqualKey, _Alloc> > 00517 { 00518 protected: 00519 typedef __gnu_cxx::hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc> 00520 _Container; 00521 _Container* container; 00522 typename _Container::iterator iter; 00523 00524 public: 00525 typedef _Container container_type; 00526 typedef output_iterator_tag iterator_category; 00527 typedef void value_type; 00528 typedef void difference_type; 00529 typedef void pointer; 00530 typedef void reference; 00531 00532 insert_iterator(_Container& __x) 00533 : container(&__x) {} 00534 00535 insert_iterator(_Container& __x, typename _Container::iterator) 00536 : container(&__x) {} 00537 00538 insert_iterator<_Container>& 00539 operator=(const typename _Container::value_type& __value) 00540 { 00541 container->insert(__value); 00542 return *this; 00543 } 00544 00545 insert_iterator<_Container>& 00546 operator*() 00547 { return *this; } 00548 00549 insert_iterator<_Container>& 00550 operator++() 00551 { return *this; } 00552 00553 insert_iterator<_Container>& 00554 operator++(int) { return *this; } 00555 }; 00556 00557 _GLIBCXX_END_NAMESPACE 00558 00559 #endif