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 Thu Feb 10 23:22:55 2005 for libstdc++-v3 Source by  doxygen 1.4.0