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 _HASH_MAP 00063 #define _HASH_MAP 1 00064 00065 #include <ext/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 00076 // declaration. 00077 template<class _Key, class _Tp, class _HashFcn = hash<_Key>, 00078 class _EqualKey = equal_to<_Key>, class _Alloc = allocator<_Tp> > 00079 class hash_map; 00080 00081 template<class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc> 00082 inline bool operator==(const hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc>&, 00083 const hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc>&); 00084 /** 00085 * This is an SGI extension. 00086 * @ingroup SGIextensions 00087 * @doctodo 00088 */ 00089 template <class _Key, class _Tp, class _HashFcn, class _EqualKey, 00090 class _Alloc> 00091 class hash_map 00092 { 00093 private: 00094 typedef hashtable<pair<const _Key,_Tp>,_Key,_HashFcn, 00095 _Select1st<pair<const _Key,_Tp> >,_EqualKey,_Alloc> _Ht; 00096 _Ht _M_ht; 00097 00098 public: 00099 typedef typename _Ht::key_type key_type; 00100 typedef _Tp data_type; 00101 typedef _Tp mapped_type; 00102 typedef typename _Ht::value_type value_type; 00103 typedef typename _Ht::hasher hasher; 00104 typedef typename _Ht::key_equal key_equal; 00105 00106 typedef typename _Ht::size_type size_type; 00107 typedef typename _Ht::difference_type difference_type; 00108 typedef typename _Ht::pointer pointer; 00109 typedef typename _Ht::const_pointer const_pointer; 00110 typedef typename _Ht::reference reference; 00111 typedef typename _Ht::const_reference const_reference; 00112 00113 typedef typename _Ht::iterator iterator; 00114 typedef typename _Ht::const_iterator const_iterator; 00115 00116 typedef typename _Ht::allocator_type allocator_type; 00117 00118 hasher hash_funct() const { return _M_ht.hash_funct(); } 00119 key_equal key_eq() const { return _M_ht.key_eq(); } 00120 allocator_type get_allocator() const { return _M_ht.get_allocator(); } 00121 00122 public: 00123 hash_map() : _M_ht(100, hasher(), key_equal(), allocator_type()) {} 00124 explicit hash_map(size_type __n) 00125 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {} 00126 hash_map(size_type __n, const hasher& __hf) 00127 : _M_ht(__n, __hf, key_equal(), allocator_type()) {} 00128 hash_map(size_type __n, const hasher& __hf, const key_equal& __eql, 00129 const allocator_type& __a = allocator_type()) 00130 : _M_ht(__n, __hf, __eql, __a) {} 00131 00132 template <class _InputIterator> 00133 hash_map(_InputIterator __f, _InputIterator __l) 00134 : _M_ht(100, hasher(), key_equal(), allocator_type()) 00135 { _M_ht.insert_unique(__f, __l); } 00136 template <class _InputIterator> 00137 hash_map(_InputIterator __f, _InputIterator __l, size_type __n) 00138 : _M_ht(__n, hasher(), key_equal(), allocator_type()) 00139 { _M_ht.insert_unique(__f, __l); } 00140 template <class _InputIterator> 00141 hash_map(_InputIterator __f, _InputIterator __l, size_type __n, 00142 const hasher& __hf) 00143 : _M_ht(__n, __hf, key_equal(), allocator_type()) 00144 { _M_ht.insert_unique(__f, __l); } 00145 template <class _InputIterator> 00146 hash_map(_InputIterator __f, _InputIterator __l, size_type __n, 00147 const hasher& __hf, const key_equal& __eql, 00148 const allocator_type& __a = allocator_type()) 00149 : _M_ht(__n, __hf, __eql, __a) 00150 { _M_ht.insert_unique(__f, __l); } 00151 00152 public: 00153 size_type size() const { return _M_ht.size(); } 00154 size_type max_size() const { return _M_ht.max_size(); } 00155 bool empty() const { return _M_ht.empty(); } 00156 void swap(hash_map& __hs) { _M_ht.swap(__hs._M_ht); } 00157 00158 template <class _K1, class _T1, class _HF, class _EqK, class _Al> 00159 friend bool operator== (const hash_map<_K1, _T1, _HF, _EqK, _Al>&, 00160 const hash_map<_K1, _T1, _HF, _EqK, _Al>&); 00161 00162 iterator begin() { return _M_ht.begin(); } 00163 iterator end() { return _M_ht.end(); } 00164 const_iterator begin() const { return _M_ht.begin(); } 00165 const_iterator end() const { return _M_ht.end(); } 00166 00167 public: 00168 pair<iterator,bool> insert(const value_type& __obj) 00169 { return _M_ht.insert_unique(__obj); } 00170 template <class _InputIterator> 00171 void insert(_InputIterator __f, _InputIterator __l) 00172 { _M_ht.insert_unique(__f,__l); } 00173 pair<iterator,bool> insert_noresize(const value_type& __obj) 00174 { return _M_ht.insert_unique_noresize(__obj); } 00175 00176 iterator find(const key_type& __key) { return _M_ht.find(__key); } 00177 const_iterator find(const key_type& __key) const 00178 { return _M_ht.find(__key); } 00179 00180 _Tp& operator[](const key_type& __key) { 00181 return _M_ht.find_or_insert(value_type(__key, _Tp())).second; 00182 } 00183 00184 size_type count(const key_type& __key) const { return _M_ht.count(__key); } 00185 00186 pair<iterator, iterator> equal_range(const key_type& __key) 00187 { return _M_ht.equal_range(__key); } 00188 pair<const_iterator, const_iterator> 00189 equal_range(const key_type& __key) const 00190 { return _M_ht.equal_range(__key); } 00191 00192 size_type erase(const key_type& __key) {return _M_ht.erase(__key); } 00193 void erase(iterator __it) { _M_ht.erase(__it); } 00194 void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); } 00195 void clear() { _M_ht.clear(); } 00196 00197 void resize(size_type __hint) { _M_ht.resize(__hint); } 00198 size_type bucket_count() const { return _M_ht.bucket_count(); } 00199 size_type max_bucket_count() const { return _M_ht.max_bucket_count(); } 00200 size_type elems_in_bucket(size_type __n) const 00201 { return _M_ht.elems_in_bucket(__n); } 00202 }; 00203 00204 template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc> 00205 inline bool 00206 operator==(const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1, 00207 const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2) 00208 { 00209 return __hm1._M_ht == __hm2._M_ht; 00210 } 00211 00212 template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc> 00213 inline bool 00214 operator!=(const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1, 00215 const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2) { 00216 return !(__hm1 == __hm2); 00217 } 00218 00219 template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc> 00220 inline void 00221 swap(hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1, 00222 hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2) 00223 { 00224 __hm1.swap(__hm2); 00225 } 00226 00227 // Forward declaration of equality operator; needed for friend declaration. 00228 00229 template <class _Key, class _Tp, 00230 class _HashFcn = hash<_Key>, 00231 class _EqualKey = equal_to<_Key>, 00232 class _Alloc = allocator<_Tp> > 00233 class hash_multimap; 00234 00235 template <class _Key, class _Tp, class _HF, class _EqKey, class _Alloc> 00236 inline bool 00237 operator==(const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm1, 00238 const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm2); 00239 00240 /** 00241 * This is an SGI extension. 00242 * @ingroup SGIextensions 00243 * @doctodo 00244 */ 00245 template <class _Key, class _Tp, class _HashFcn, class _EqualKey, class _Alloc> 00246 class hash_multimap 00247 { 00248 // concept requirements 00249 __glibcxx_class_requires(_Key, _SGIAssignableConcept) 00250 __glibcxx_class_requires(_Tp, _SGIAssignableConcept) 00251 __glibcxx_class_requires3(_HashFcn, size_t, _Key, _UnaryFunctionConcept) 00252 __glibcxx_class_requires3(_EqualKey, _Key, _Key, _BinaryPredicateConcept) 00253 00254 private: 00255 typedef hashtable<pair<const _Key, _Tp>, _Key, _HashFcn, 00256 _Select1st<pair<const _Key, _Tp> >, _EqualKey, _Alloc> 00257 _Ht; 00258 _Ht _M_ht; 00259 00260 public: 00261 typedef typename _Ht::key_type key_type; 00262 typedef _Tp data_type; 00263 typedef _Tp mapped_type; 00264 typedef typename _Ht::value_type value_type; 00265 typedef typename _Ht::hasher hasher; 00266 typedef typename _Ht::key_equal key_equal; 00267 00268 typedef typename _Ht::size_type size_type; 00269 typedef typename _Ht::difference_type difference_type; 00270 typedef typename _Ht::pointer pointer; 00271 typedef typename _Ht::const_pointer const_pointer; 00272 typedef typename _Ht::reference reference; 00273 typedef typename _Ht::const_reference const_reference; 00274 00275 typedef typename _Ht::iterator iterator; 00276 typedef typename _Ht::const_iterator const_iterator; 00277 00278 typedef typename _Ht::allocator_type allocator_type; 00279 00280 hasher hash_funct() const { return _M_ht.hash_funct(); } 00281 key_equal key_eq() const { return _M_ht.key_eq(); } 00282 allocator_type get_allocator() const { return _M_ht.get_allocator(); } 00283 00284 public: 00285 hash_multimap() : _M_ht(100, hasher(), key_equal(), allocator_type()) {} 00286 explicit hash_multimap(size_type __n) 00287 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {} 00288 hash_multimap(size_type __n, const hasher& __hf) 00289 : _M_ht(__n, __hf, key_equal(), allocator_type()) {} 00290 hash_multimap(size_type __n, const hasher& __hf, const key_equal& __eql, 00291 const allocator_type& __a = allocator_type()) 00292 : _M_ht(__n, __hf, __eql, __a) {} 00293 00294 template <class _InputIterator> 00295 hash_multimap(_InputIterator __f, _InputIterator __l) 00296 : _M_ht(100, hasher(), key_equal(), allocator_type()) 00297 { _M_ht.insert_equal(__f, __l); } 00298 template <class _InputIterator> 00299 hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n) 00300 : _M_ht(__n, hasher(), key_equal(), allocator_type()) 00301 { _M_ht.insert_equal(__f, __l); } 00302 template <class _InputIterator> 00303 hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n, 00304 const hasher& __hf) 00305 : _M_ht(__n, __hf, key_equal(), allocator_type()) 00306 { _M_ht.insert_equal(__f, __l); } 00307 template <class _InputIterator> 00308 hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n, 00309 const hasher& __hf, const key_equal& __eql, 00310 const allocator_type& __a = allocator_type()) 00311 : _M_ht(__n, __hf, __eql, __a) 00312 { _M_ht.insert_equal(__f, __l); } 00313 00314 public: 00315 size_type size() const { return _M_ht.size(); } 00316 size_type max_size() const { return _M_ht.max_size(); } 00317 bool empty() const { return _M_ht.empty(); } 00318 void swap(hash_multimap& __hs) { _M_ht.swap(__hs._M_ht); } 00319 00320 template <class _K1, class _T1, class _HF, class _EqK, class _Al> 00321 friend bool operator== (const hash_multimap<_K1, _T1, _HF, _EqK, _Al>&, 00322 const hash_multimap<_K1, _T1, _HF, _EqK, _Al>&); 00323 00324 iterator begin() { return _M_ht.begin(); } 00325 iterator end() { return _M_ht.end(); } 00326 const_iterator begin() const { return _M_ht.begin(); } 00327 const_iterator end() const { return _M_ht.end(); } 00328 00329 public: 00330 iterator insert(const value_type& __obj) 00331 { return _M_ht.insert_equal(__obj); } 00332 template <class _InputIterator> 00333 void insert(_InputIterator __f, _InputIterator __l) 00334 { _M_ht.insert_equal(__f,__l); } 00335 iterator insert_noresize(const value_type& __obj) 00336 { return _M_ht.insert_equal_noresize(__obj); } 00337 00338 iterator find(const key_type& __key) { return _M_ht.find(__key); } 00339 const_iterator find(const key_type& __key) const 00340 { return _M_ht.find(__key); } 00341 00342 size_type count(const key_type& __key) const { return _M_ht.count(__key); } 00343 00344 pair<iterator, iterator> equal_range(const key_type& __key) 00345 { return _M_ht.equal_range(__key); } 00346 pair<const_iterator, const_iterator> 00347 equal_range(const key_type& __key) const 00348 { return _M_ht.equal_range(__key); } 00349 00350 size_type erase(const key_type& __key) {return _M_ht.erase(__key); } 00351 void erase(iterator __it) { _M_ht.erase(__it); } 00352 void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); } 00353 void clear() { _M_ht.clear(); } 00354 00355 public: 00356 void resize(size_type __hint) { _M_ht.resize(__hint); } 00357 size_type bucket_count() const { return _M_ht.bucket_count(); } 00358 size_type max_bucket_count() const { return _M_ht.max_bucket_count(); } 00359 size_type elems_in_bucket(size_type __n) const 00360 { return _M_ht.elems_in_bucket(__n); } 00361 }; 00362 00363 template <class _Key, class _Tp, class _HF, class _EqKey, class _Alloc> 00364 inline bool 00365 operator==(const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm1, 00366 const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm2) 00367 { 00368 return __hm1._M_ht == __hm2._M_ht; 00369 } 00370 00371 template <class _Key, class _Tp, class _HF, class _EqKey, class _Alloc> 00372 inline bool 00373 operator!=(const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm1, 00374 const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm2) { 00375 return !(__hm1 == __hm2); 00376 } 00377 00378 template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc> 00379 inline void 00380 swap(hash_multimap<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1, 00381 hash_multimap<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2) 00382 { 00383 __hm1.swap(__hm2); 00384 } 00385 00386 } // namespace __gnu_cxx 00387 00388 namespace std 00389 { 00390 // Specialization of insert_iterator so that it will work for hash_map 00391 // and hash_multimap. 00392 00393 template <class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc> 00394 class insert_iterator<__gnu_cxx::hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc> > { 00395 protected: 00396 typedef __gnu_cxx::hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc> _Container; 00397 _Container* container; 00398 public: 00399 typedef _Container container_type; 00400 typedef output_iterator_tag iterator_category; 00401 typedef void value_type; 00402 typedef void difference_type; 00403 typedef void pointer; 00404 typedef void reference; 00405 00406 insert_iterator(_Container& __x) : container(&__x) {} 00407 insert_iterator(_Container& __x, typename _Container::iterator) 00408 : container(&__x) {} 00409 insert_iterator<_Container>& 00410 operator=(const typename _Container::value_type& __value) { 00411 container->insert(__value); 00412 return *this; 00413 } 00414 insert_iterator<_Container>& operator*() { return *this; } 00415 insert_iterator<_Container>& operator++() { return *this; } 00416 insert_iterator<_Container>& operator++(int) { return *this; } 00417 }; 00418 00419 template <class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc> 00420 class insert_iterator<__gnu_cxx::hash_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc> > { 00421 protected: 00422 typedef __gnu_cxx::hash_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc> _Container; 00423 _Container* container; 00424 typename _Container::iterator iter; 00425 public: 00426 typedef _Container container_type; 00427 typedef output_iterator_tag iterator_category; 00428 typedef void value_type; 00429 typedef void difference_type; 00430 typedef void pointer; 00431 typedef void reference; 00432 00433 insert_iterator(_Container& __x) : container(&__x) {} 00434 insert_iterator(_Container& __x, typename _Container::iterator) 00435 : container(&__x) {} 00436 insert_iterator<_Container>& 00437 operator=(const typename _Container::value_type& __value) { 00438 container->insert(__value); 00439 return *this; 00440 } 00441 insert_iterator<_Container>& operator*() { return *this; } 00442 insert_iterator<_Container>& operator++() { return *this; } 00443 insert_iterator<_Container>& operator++(int) { return *this; } 00444 }; 00445 } // namespace std 00446 00447 #endif

Generated on Tue Sep 7 10:05:06 2004 for libstdc++-v3 Source by doxygen 1.3.8