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