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