hash_map

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

Generated on Thu Nov 1 17:35:58 2007 for libstdc++ by  doxygen 1.5.1