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