hash_map

Go to the documentation of this file.
00001 // Hashing map implementation -*- C++ -*- 00002 00003 // Copyright (C) 2001, 2002 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 2, 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 // You should have received a copy of the GNU General Public License along 00017 // with this library; see the file COPYING. If not, write to the Free 00018 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 00019 // USA. 00020 00021 // As a special exception, you may use this file as part of a free software 00022 // library without restriction. Specifically, if other files instantiate 00023 // templates or use macros or inline functions from this file, or you compile 00024 // this file and link it with other files to produce an executable, this 00025 // file does not by itself cause the resulting executable to be covered by 00026 // the GNU General Public License. This exception does not however 00027 // invalidate any other reasons why the executable file might be covered by 00028 // the GNU General Public License. 00029 00030 /* 00031 * Copyright (c) 1996 00032 * Silicon Graphics Computer Systems, Inc. 00033 * 00034 * Permission to use, copy, modify, distribute and sell this software 00035 * and its documentation for any purpose is hereby granted without fee, 00036 * provided that the above copyright notice appear in all copies and 00037 * that both that copyright notice and this permission notice appear 00038 * in supporting documentation. Silicon Graphics makes no 00039 * representations about the suitability of this software for any 00040 * purpose. It is provided "as is" without express or implied warranty. 00041 * 00042 * 00043 * Copyright (c) 1994 00044 * Hewlett-Packard Company 00045 * 00046 * Permission to use, copy, modify, distribute and sell this software 00047 * and its documentation for any purpose is hereby granted without fee, 00048 * provided that the above copyright notice appear in all copies and 00049 * that both that copyright notice and this permission notice appear 00050 * in supporting documentation. Hewlett-Packard Company makes no 00051 * representations about the suitability of this software for any 00052 * purpose. It is provided "as is" without express or implied warranty. 00053 * 00054 */ 00055 00056 /** @file ext/hash_map 00057 * This file is a GNU extension to the Standard C++ Library (possibly 00058 * containing extensions from the HP/SGI STL subset). You should only 00059 * include this header if you are using GCC 3 or later. 00060 */ 00061 00062 #ifndef __SGI_STL_INTERNAL_HASH_MAP_H 00063 #define __SGI_STL_INTERNAL_HASH_MAP_H 00064 00065 #include <ext/stl_hashtable.h> 00066 #include <bits/concept_check.h> 00067 00068 namespace __gnu_cxx 00069 { 00070 using std::equal_to; 00071 using std::allocator; 00072 using std::pair; 00073 using std::_Select1st; 00074 00075 // Forward declaration of equality operator; needed for friend declaration. 00076 00077 template <class _Key, class _Tp, 00078 class _HashFcn = hash<_Key>, 00079 class _EqualKey = equal_to<_Key>, 00080 class _Alloc = allocator<_Tp> > 00081 class hash_map; 00082 00083 template <class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc> 00084 inline bool operator==(const hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc>&, 00085 const hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc>&); 00086 /** 00087 * This is an SGI extension. 00088 * @ingroup SGIextensions 00089 * @doctodo 00090 */ 00091 template <class _Key, class _Tp, class _HashFcn, class _EqualKey, 00092 class _Alloc> 00093 class hash_map 00094 { 00095 private: 00096 typedef hashtable<pair<const _Key,_Tp>,_Key,_HashFcn, 00097 _Select1st<pair<const _Key,_Tp> >,_EqualKey,_Alloc> _Ht; 00098 _Ht _M_ht; 00099 00100 public: 00101 typedef typename _Ht::key_type key_type; 00102 typedef _Tp data_type; 00103 typedef _Tp mapped_type; 00104 typedef typename _Ht::value_type value_type; 00105 typedef typename _Ht::hasher hasher; 00106 typedef typename _Ht::key_equal key_equal; 00107 00108 typedef typename _Ht::size_type size_type; 00109 typedef typename _Ht::difference_type difference_type; 00110 typedef typename _Ht::pointer pointer; 00111 typedef typename _Ht::const_pointer const_pointer; 00112 typedef typename _Ht::reference reference; 00113 typedef typename _Ht::const_reference const_reference; 00114 00115 typedef typename _Ht::iterator iterator; 00116 typedef typename _Ht::const_iterator const_iterator; 00117 00118 typedef typename _Ht::allocator_type allocator_type; 00119 00120 hasher hash_funct() const { return _M_ht.hash_funct(); } 00121 key_equal key_eq() const { return _M_ht.key_eq(); } 00122 allocator_type get_allocator() const { return _M_ht.get_allocator(); } 00123 00124 public: 00125 hash_map() : _M_ht(100, hasher(), key_equal(), allocator_type()) {} 00126 explicit hash_map(size_type __n) 00127 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {} 00128 hash_map(size_type __n, const hasher& __hf) 00129 : _M_ht(__n, __hf, key_equal(), allocator_type()) {} 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 template <class _InputIterator> 00139 hash_map(_InputIterator __f, _InputIterator __l, size_type __n) 00140 : _M_ht(__n, hasher(), key_equal(), allocator_type()) 00141 { _M_ht.insert_unique(__f, __l); } 00142 template <class _InputIterator> 00143 hash_map(_InputIterator __f, _InputIterator __l, size_type __n, 00144 const hasher& __hf) 00145 : _M_ht(__n, __hf, key_equal(), allocator_type()) 00146 { _M_ht.insert_unique(__f, __l); } 00147 template <class _InputIterator> 00148 hash_map(_InputIterator __f, _InputIterator __l, size_type __n, 00149 const hasher& __hf, const key_equal& __eql, 00150 const allocator_type& __a = allocator_type()) 00151 : _M_ht(__n, __hf, __eql, __a) 00152 { _M_ht.insert_unique(__f, __l); } 00153 00154 public: 00155 size_type size() const { return _M_ht.size(); } 00156 size_type max_size() const { return _M_ht.max_size(); } 00157 bool empty() const { return _M_ht.empty(); } 00158 void swap(hash_map& __hs) { _M_ht.swap(__hs._M_ht); } 00159 00160 template <class _K1, class _T1, class _HF, class _EqK, class _Al> 00161 friend bool operator== (const hash_map<_K1, _T1, _HF, _EqK, _Al>&, 00162 const hash_map<_K1, _T1, _HF, _EqK, _Al>&); 00163 00164 iterator begin() { return _M_ht.begin(); } 00165 iterator end() { return _M_ht.end(); } 00166 const_iterator begin() const { return _M_ht.begin(); } 00167 const_iterator end() const { return _M_ht.end(); } 00168 00169 public: 00170 pair<iterator,bool> insert(const value_type& __obj) 00171 { return _M_ht.insert_unique(__obj); } 00172 template <class _InputIterator> 00173 void insert(_InputIterator __f, _InputIterator __l) 00174 { _M_ht.insert_unique(__f,__l); } 00175 pair<iterator,bool> insert_noresize(const value_type& __obj) 00176 { return _M_ht.insert_unique_noresize(__obj); } 00177 00178 iterator find(const key_type& __key) { return _M_ht.find(__key); } 00179 const_iterator find(const key_type& __key) const 00180 { return _M_ht.find(__key); } 00181 00182 _Tp& operator[](const key_type& __key) { 00183 return _M_ht.find_or_insert(value_type(__key, _Tp())).second; 00184 } 00185 00186 size_type count(const key_type& __key) const { return _M_ht.count(__key); } 00187 00188 pair<iterator, iterator> equal_range(const key_type& __key) 00189 { return _M_ht.equal_range(__key); } 00190 pair<const_iterator, const_iterator> 00191 equal_range(const key_type& __key) const 00192 { return _M_ht.equal_range(__key); } 00193 00194 size_type erase(const key_type& __key) {return _M_ht.erase(__key); } 00195 void erase(iterator __it) { _M_ht.erase(__it); } 00196 void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); } 00197 void clear() { _M_ht.clear(); } 00198 00199 void resize(size_type __hint) { _M_ht.resize(__hint); } 00200 size_type bucket_count() const { return _M_ht.bucket_count(); } 00201 size_type max_bucket_count() const { return _M_ht.max_bucket_count(); } 00202 size_type elems_in_bucket(size_type __n) const 00203 { return _M_ht.elems_in_bucket(__n); } 00204 }; 00205 00206 template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc> 00207 inline bool 00208 operator==(const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1, 00209 const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2) 00210 { 00211 return __hm1._M_ht == __hm2._M_ht; 00212 } 00213 00214 template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc> 00215 inline bool 00216 operator!=(const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1, 00217 const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2) { 00218 return !(__hm1 == __hm2); 00219 } 00220 00221 template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc> 00222 inline void 00223 swap(hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1, 00224 hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2) 00225 { 00226 __hm1.swap(__hm2); 00227 } 00228 00229 // Forward declaration of equality operator; needed for friend declaration. 00230 00231 template <class _Key, class _Tp, 00232 class _HashFcn = hash<_Key>, 00233 class _EqualKey = equal_to<_Key>, 00234 class _Alloc = allocator<_Tp> > 00235 class hash_multimap; 00236 00237 template <class _Key, class _Tp, class _HF, class _EqKey, class _Alloc> 00238 inline bool 00239 operator==(const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm1, 00240 const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm2); 00241 00242 /** 00243 * This is an SGI extension. 00244 * @ingroup SGIextensions 00245 * @doctodo 00246 */ 00247 template <class _Key, class _Tp, class _HashFcn, class _EqualKey, class _Alloc> 00248 class hash_multimap 00249 { 00250 // concept requirements 00251 __glibcpp_class_requires(_Key, _SGIAssignableConcept) 00252 __glibcpp_class_requires(_Tp, _SGIAssignableConcept) 00253 __glibcpp_class_requires3(_HashFcn, size_t, _Key, _UnaryFunctionConcept); 00254 __glibcpp_class_requires3(_EqualKey, _Key, _Key, _BinaryPredicateConcept); 00255 00256 private: 00257 typedef hashtable<pair<const _Key, _Tp>, _Key, _HashFcn, 00258 _Select1st<pair<const _Key, _Tp> >, _EqualKey, _Alloc> 00259 _Ht; 00260 _Ht _M_ht; 00261 00262 public: 00263 typedef typename _Ht::key_type key_type; 00264 typedef _Tp data_type; 00265 typedef _Tp mapped_type; 00266 typedef typename _Ht::value_type value_type; 00267 typedef typename _Ht::hasher hasher; 00268 typedef typename _Ht::key_equal key_equal; 00269 00270 typedef typename _Ht::size_type size_type; 00271 typedef typename _Ht::difference_type difference_type; 00272 typedef typename _Ht::pointer pointer; 00273 typedef typename _Ht::const_pointer const_pointer; 00274 typedef typename _Ht::reference reference; 00275 typedef typename _Ht::const_reference const_reference; 00276 00277 typedef typename _Ht::iterator iterator; 00278 typedef typename _Ht::const_iterator const_iterator; 00279 00280 typedef typename _Ht::allocator_type allocator_type; 00281 00282 hasher hash_funct() const { return _M_ht.hash_funct(); } 00283 key_equal key_eq() const { return _M_ht.key_eq(); } 00284 allocator_type get_allocator() const { return _M_ht.get_allocator(); } 00285 00286 public: 00287 hash_multimap() : _M_ht(100, hasher(), key_equal(), allocator_type()) {} 00288 explicit hash_multimap(size_type __n) 00289 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {} 00290 hash_multimap(size_type __n, const hasher& __hf) 00291 : _M_ht(__n, __hf, key_equal(), allocator_type()) {} 00292 hash_multimap(size_type __n, const hasher& __hf, const key_equal& __eql, 00293 const allocator_type& __a = allocator_type()) 00294 : _M_ht(__n, __hf, __eql, __a) {} 00295 00296 template <class _InputIterator> 00297 hash_multimap(_InputIterator __f, _InputIterator __l) 00298 : _M_ht(100, hasher(), key_equal(), allocator_type()) 00299 { _M_ht.insert_equal(__f, __l); } 00300 template <class _InputIterator> 00301 hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n) 00302 : _M_ht(__n, hasher(), key_equal(), allocator_type()) 00303 { _M_ht.insert_equal(__f, __l); } 00304 template <class _InputIterator> 00305 hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n, 00306 const hasher& __hf) 00307 : _M_ht(__n, __hf, key_equal(), allocator_type()) 00308 { _M_ht.insert_equal(__f, __l); } 00309 template <class _InputIterator> 00310 hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n, 00311 const hasher& __hf, const key_equal& __eql, 00312 const allocator_type& __a = allocator_type()) 00313 : _M_ht(__n, __hf, __eql, __a) 00314 { _M_ht.insert_equal(__f, __l); } 00315 00316 public: 00317 size_type size() const { return _M_ht.size(); } 00318 size_type max_size() const { return _M_ht.max_size(); } 00319 bool empty() const { return _M_ht.empty(); } 00320 void swap(hash_multimap& __hs) { _M_ht.swap(__hs._M_ht); } 00321 00322 template <class _K1, class _T1, class _HF, class _EqK, class _Al> 00323 friend bool operator== (const hash_multimap<_K1, _T1, _HF, _EqK, _Al>&, 00324 const hash_multimap<_K1, _T1, _HF, _EqK, _Al>&); 00325 00326 iterator begin() { return _M_ht.begin(); } 00327 iterator end() { return _M_ht.end(); } 00328 const_iterator begin() const { return _M_ht.begin(); } 00329 const_iterator end() const { return _M_ht.end(); } 00330 00331 public: 00332 iterator insert(const value_type& __obj) 00333 { return _M_ht.insert_equal(__obj); } 00334 template <class _InputIterator> 00335 void insert(_InputIterator __f, _InputIterator __l) 00336 { _M_ht.insert_equal(__f,__l); } 00337 iterator insert_noresize(const value_type& __obj) 00338 { return _M_ht.insert_equal_noresize(__obj); } 00339 00340 iterator find(const key_type& __key) { return _M_ht.find(__key); } 00341 const_iterator find(const key_type& __key) const 00342 { return _M_ht.find(__key); } 00343 00344 size_type count(const key_type& __key) const { return _M_ht.count(__key); } 00345 00346 pair<iterator, iterator> equal_range(const key_type& __key) 00347 { return _M_ht.equal_range(__key); } 00348 pair<const_iterator, const_iterator> 00349 equal_range(const key_type& __key) const 00350 { return _M_ht.equal_range(__key); } 00351 00352 size_type erase(const key_type& __key) {return _M_ht.erase(__key); } 00353 void erase(iterator __it) { _M_ht.erase(__it); } 00354 void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); } 00355 void clear() { _M_ht.clear(); } 00356 00357 public: 00358 void resize(size_type __hint) { _M_ht.resize(__hint); } 00359 size_type bucket_count() const { return _M_ht.bucket_count(); } 00360 size_type max_bucket_count() const { return _M_ht.max_bucket_count(); } 00361 size_type elems_in_bucket(size_type __n) const 00362 { return _M_ht.elems_in_bucket(__n); } 00363 }; 00364 00365 template <class _Key, class _Tp, class _HF, class _EqKey, class _Alloc> 00366 inline bool 00367 operator==(const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm1, 00368 const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm2) 00369 { 00370 return __hm1._M_ht == __hm2._M_ht; 00371 } 00372 00373 template <class _Key, class _Tp, class _HF, class _EqKey, class _Alloc> 00374 inline bool 00375 operator!=(const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm1, 00376 const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm2) { 00377 return !(__hm1 == __hm2); 00378 } 00379 00380 template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc> 00381 inline void 00382 swap(hash_multimap<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1, 00383 hash_multimap<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2) 00384 { 00385 __hm1.swap(__hm2); 00386 } 00387 00388 } // namespace __gnu_cxx 00389 00390 namespace std 00391 { 00392 // Specialization of insert_iterator so that it will work for hash_map 00393 // and hash_multimap. 00394 00395 template <class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc> 00396 class insert_iterator<__gnu_cxx::hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc> > { 00397 protected: 00398 typedef __gnu_cxx::hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc> _Container; 00399 _Container* container; 00400 public: 00401 typedef _Container container_type; 00402 typedef output_iterator_tag iterator_category; 00403 typedef void value_type; 00404 typedef void difference_type; 00405 typedef void pointer; 00406 typedef void reference; 00407 00408 insert_iterator(_Container& __x) : container(&__x) {} 00409 insert_iterator(_Container& __x, typename _Container::iterator) 00410 : container(&__x) {} 00411 insert_iterator<_Container>& 00412 operator=(const typename _Container::value_type& __value) { 00413 container->insert(__value); 00414 return *this; 00415 } 00416 insert_iterator<_Container>& operator*() { return *this; } 00417 insert_iterator<_Container>& operator++() { return *this; } 00418 insert_iterator<_Container>& operator++(int) { return *this; } 00419 }; 00420 00421 template <class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc> 00422 class insert_iterator<__gnu_cxx::hash_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc> > { 00423 protected: 00424 typedef __gnu_cxx::hash_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc> _Container; 00425 _Container* container; 00426 typename _Container::iterator iter; 00427 public: 00428 typedef _Container container_type; 00429 typedef output_iterator_tag iterator_category; 00430 typedef void value_type; 00431 typedef void difference_type; 00432 typedef void pointer; 00433 typedef void reference; 00434 00435 insert_iterator(_Container& __x) : container(&__x) {} 00436 insert_iterator(_Container& __x, typename _Container::iterator) 00437 : container(&__x) {} 00438 insert_iterator<_Container>& 00439 operator=(const typename _Container::value_type& __value) { 00440 container->insert(__value); 00441 return *this; 00442 } 00443 insert_iterator<_Container>& operator*() { return *this; } 00444 insert_iterator<_Container>& operator++() { return *this; } 00445 insert_iterator<_Container>& operator++(int) { return *this; } 00446 }; 00447 00448 } // namespace std 00449 00450 #endif /* __SGI_STL_INTERNAL_HASH_MAP_H */ 00451 00452 // Local Variables: 00453 // mode:C++ 00454 // End:

Generated on Sun Sep 19 16:33:49 2004 for libstdc++-v3 Source by doxygen 1.3.8