ext/hash_map

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

Generated on Thu Nov 1 13:11:31 2007 for libstdc++ by  doxygen 1.5.1