hash_map

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

Generated on Thu Jul 23 21:16:07 2009 for libstdc++ by  doxygen 1.5.8