hash_map

Go to the documentation of this file.
00001 // Hashing map implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2001, 2002, 2004, 2005, 2006, 2009, 2010
00004 // Free Software Foundation, Inc.
00005 //
00006 // This file is part of the GNU ISO C++ Library.  This library is free
00007 // software; you can redistribute it and/or modify it under the
00008 // terms of the GNU General Public License as published by the
00009 // Free Software Foundation; either version 3, or (at your option)
00010 // any later version.
00011 
00012 // This library is distributed in the hope that it will be useful,
00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015 // GNU General Public License for more details.
00016 
00017 // Under Section 7 of GPL version 3, you are granted additional
00018 // permissions described in the GCC Runtime Library Exception, version
00019 // 3.1, as published by the Free Software Foundation.
00020 
00021 // You should have received a copy of the GNU General Public License and
00022 // a copy of the GCC Runtime Library Exception along with this program;
00023 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00024 // <http://www.gnu.org/licenses/>.
00025 
00026 /*
00027  * Copyright (c) 1996
00028  * Silicon Graphics Computer Systems, Inc.
00029  *
00030  * Permission to use, copy, modify, distribute and sell this software
00031  * and its documentation for any purpose is hereby granted without fee,
00032  * provided that the above copyright notice appear in all copies and
00033  * that both that copyright notice and this permission notice appear
00034  * in supporting documentation.  Silicon Graphics makes no
00035  * representations about the suitability of this software for any
00036  * purpose.  It is provided "as is" without express or implied warranty.
00037  *
00038  *
00039  * Copyright (c) 1994
00040  * Hewlett-Packard Company
00041  *
00042  * Permission to use, copy, modify, distribute and sell this software
00043  * and its documentation for any purpose is hereby granted without fee,
00044  * provided that the above copyright notice appear in all copies and
00045  * that both that copyright notice and this permission notice appear
00046  * in supporting documentation.  Hewlett-Packard Company makes no
00047  * representations about the suitability of this software for any
00048  * purpose.  It is provided "as is" without express or implied warranty.
00049  *
00050  */
00051 
00052 /** @file backward/hash_map
00053  *  This file is a GNU extension to the Standard C++ Library (possibly
00054  *  containing extensions from the HP/SGI STL subset).
00055  */
00056 
00057 #ifndef _BACKWARD_HASH_MAP
00058 #define _BACKWARD_HASH_MAP 1
00059 
00060 #include "backward_warning.h"
00061 #include <bits/c++config.h>
00062 #include <backward/hashtable.h>
00063 #include <bits/concept_check.h>
00064 
00065 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)
00066 
00067   using std::equal_to;
00068   using std::allocator;
00069   using std::pair;
00070   using std::_Select1st;
00071 
00072   /**
00073    *  This is an SGI extension.
00074    *  @ingroup SGIextensions
00075    *  @doctodo
00076    */
00077   template<class _Key, class _Tp, class _HashFn = hash<_Key>,
00078        class _EqualKey = equal_to<_Key>, class _Alloc = allocator<_Tp> >
00079     class hash_map
00080     {
00081     private:
00082       typedef hashtable<pair<const _Key, _Tp>,_Key, _HashFn,
00083             _Select1st<pair<const _Key, _Tp> >,
00084             _EqualKey, _Alloc> _Ht;
00085 
00086       _Ht _M_ht;
00087 
00088     public:
00089       typedef typename _Ht::key_type key_type;
00090       typedef _Tp data_type;
00091       typedef _Tp mapped_type;
00092       typedef typename _Ht::value_type value_type;
00093       typedef typename _Ht::hasher hasher;
00094       typedef typename _Ht::key_equal key_equal;
00095       
00096       typedef typename _Ht::size_type size_type;
00097       typedef typename _Ht::difference_type difference_type;
00098       typedef typename _Ht::pointer pointer;
00099       typedef typename _Ht::const_pointer const_pointer;
00100       typedef typename _Ht::reference reference;
00101       typedef typename _Ht::const_reference const_reference;
00102       
00103       typedef typename _Ht::iterator iterator;
00104       typedef typename _Ht::const_iterator const_iterator;
00105       
00106       typedef typename _Ht::allocator_type allocator_type;
00107       
00108       hasher
00109       hash_funct() const
00110       { return _M_ht.hash_funct(); }
00111 
00112       key_equal
00113       key_eq() const
00114       { return _M_ht.key_eq(); }
00115 
00116       allocator_type
00117       get_allocator() const
00118       { return _M_ht.get_allocator(); }
00119 
00120       hash_map()
00121       : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
00122   
00123       explicit
00124       hash_map(size_type __n)
00125       : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
00126 
00127       hash_map(size_type __n, const hasher& __hf)
00128       : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
00129 
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 
00139       template<class _InputIterator>
00140         hash_map(_InputIterator __f, _InputIterator __l, size_type __n)
00141     : _M_ht(__n, hasher(), key_equal(), allocator_type())
00142         { _M_ht.insert_unique(__f, __l); }
00143 
00144       template<class _InputIterator>
00145         hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
00146          const hasher& __hf)
00147     : _M_ht(__n, __hf, key_equal(), allocator_type())
00148         { _M_ht.insert_unique(__f, __l); }
00149 
00150       template<class _InputIterator>
00151         hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
00152          const hasher& __hf, const key_equal& __eql,
00153          const allocator_type& __a = allocator_type())
00154     : _M_ht(__n, __hf, __eql, __a)
00155         { _M_ht.insert_unique(__f, __l); }
00156 
00157       size_type
00158       size() const
00159       { return _M_ht.size(); }
00160       
00161       size_type
00162       max_size() const
00163       { return _M_ht.max_size(); }
00164       
00165       bool
00166       empty() const
00167       { return _M_ht.empty(); }
00168   
00169       void
00170       swap(hash_map& __hs)
00171       { _M_ht.swap(__hs._M_ht); }
00172 
00173       template<class _K1, class _T1, class _HF, class _EqK, class _Al>
00174         friend bool
00175         operator== (const hash_map<_K1, _T1, _HF, _EqK, _Al>&,
00176             const hash_map<_K1, _T1, _HF, _EqK, _Al>&);
00177 
00178       iterator
00179       begin()
00180       { return _M_ht.begin(); }
00181 
00182       iterator
00183       end()
00184       { return _M_ht.end(); }
00185 
00186       const_iterator
00187       begin() const
00188       { return _M_ht.begin(); }
00189 
00190       const_iterator
00191       end() const
00192       { return _M_ht.end(); }
00193 
00194       pair<iterator, bool>
00195       insert(const value_type& __obj)
00196       { return _M_ht.insert_unique(__obj); }
00197 
00198       template<class _InputIterator>
00199         void
00200         insert(_InputIterator __f, _InputIterator __l)
00201         { _M_ht.insert_unique(__f, __l); }
00202 
00203       pair<iterator, bool>
00204       insert_noresize(const value_type& __obj)
00205       { return _M_ht.insert_unique_noresize(__obj); }
00206 
00207       iterator
00208       find(const key_type& __key)
00209       { return _M_ht.find(__key); }
00210 
00211       const_iterator
00212       find(const key_type& __key) const
00213       { return _M_ht.find(__key); }
00214 
00215       _Tp&
00216       operator[](const key_type& __key)
00217       { return _M_ht.find_or_insert(value_type(__key, _Tp())).second; }
00218 
00219       size_type
00220       count(const key_type& __key) const
00221       { return _M_ht.count(__key); }
00222 
00223       pair<iterator, iterator>
00224       equal_range(const key_type& __key)
00225       { return _M_ht.equal_range(__key); }
00226 
00227       pair<const_iterator, const_iterator>
00228       equal_range(const key_type& __key) const
00229       { return _M_ht.equal_range(__key); }
00230 
00231       size_type
00232       erase(const key_type& __key)
00233       {return _M_ht.erase(__key); }
00234 
00235       void
00236       erase(iterator __it)
00237       { _M_ht.erase(__it); }
00238 
00239       void
00240       erase(iterator __f, iterator __l)
00241       { _M_ht.erase(__f, __l); }
00242 
00243       void
00244       clear()
00245       { _M_ht.clear(); }
00246 
00247       void
00248       resize(size_type __hint)
00249       { _M_ht.resize(__hint); }
00250 
00251       size_type
00252       bucket_count() const
00253       { return _M_ht.bucket_count(); }
00254 
00255       size_type
00256       max_bucket_count() const
00257       { return _M_ht.max_bucket_count(); }
00258 
00259       size_type
00260       elems_in_bucket(size_type __n) const
00261       { return _M_ht.elems_in_bucket(__n); }
00262     };
00263 
00264   template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
00265     inline bool
00266     operator==(const hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
00267            const hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
00268     { return __hm1._M_ht == __hm2._M_ht; }
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 == __hm2); }
00275 
00276   template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
00277     inline void
00278     swap(hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
00279      hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
00280     { __hm1.swap(__hm2); }
00281 
00282 
00283   /**
00284    *  This is an SGI extension.
00285    *  @ingroup SGIextensions
00286    *  @doctodo
00287    */
00288   template<class _Key, class _Tp,
00289        class _HashFn = hash<_Key>,
00290        class _EqualKey = equal_to<_Key>,
00291        class _Alloc = allocator<_Tp> >
00292     class hash_multimap
00293     {
00294       // concept requirements
00295       __glibcxx_class_requires(_Key, _SGIAssignableConcept)
00296       __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
00297       __glibcxx_class_requires3(_HashFn, size_t, _Key, _UnaryFunctionConcept)
00298       __glibcxx_class_requires3(_EqualKey, _Key, _Key, _BinaryPredicateConcept)
00299     
00300     private:
00301       typedef hashtable<pair<const _Key, _Tp>, _Key, _HashFn,
00302             _Select1st<pair<const _Key, _Tp> >, _EqualKey, _Alloc>
00303           _Ht;
00304 
00305       _Ht _M_ht;
00306 
00307     public:
00308       typedef typename _Ht::key_type key_type;
00309       typedef _Tp data_type;
00310       typedef _Tp mapped_type;
00311       typedef typename _Ht::value_type value_type;
00312       typedef typename _Ht::hasher hasher;
00313       typedef typename _Ht::key_equal key_equal;
00314       
00315       typedef typename _Ht::size_type size_type;
00316       typedef typename _Ht::difference_type difference_type;
00317       typedef typename _Ht::pointer pointer;
00318       typedef typename _Ht::const_pointer const_pointer;
00319       typedef typename _Ht::reference reference;
00320       typedef typename _Ht::const_reference const_reference;
00321       
00322       typedef typename _Ht::iterator iterator;
00323       typedef typename _Ht::const_iterator const_iterator;
00324       
00325       typedef typename _Ht::allocator_type allocator_type;
00326       
00327       hasher
00328       hash_funct() const
00329       { return _M_ht.hash_funct(); }
00330 
00331       key_equal
00332       key_eq() const
00333       { return _M_ht.key_eq(); }
00334 
00335       allocator_type
00336       get_allocator() const
00337       { return _M_ht.get_allocator(); }
00338 
00339       hash_multimap()
00340       : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
00341 
00342       explicit
00343       hash_multimap(size_type __n)
00344       : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
00345 
00346       hash_multimap(size_type __n, const hasher& __hf)
00347       : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
00348 
00349       hash_multimap(size_type __n, const hasher& __hf, const key_equal& __eql,
00350             const allocator_type& __a = allocator_type())
00351       : _M_ht(__n, __hf, __eql, __a) {}
00352 
00353       template<class _InputIterator>
00354         hash_multimap(_InputIterator __f, _InputIterator __l)
00355     : _M_ht(100, hasher(), key_equal(), allocator_type())
00356         { _M_ht.insert_equal(__f, __l); }
00357 
00358       template<class _InputIterator>
00359         hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n)
00360     : _M_ht(__n, hasher(), key_equal(), allocator_type())
00361         { _M_ht.insert_equal(__f, __l); }
00362 
00363       template<class _InputIterator>
00364         hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
00365               const hasher& __hf)
00366     : _M_ht(__n, __hf, key_equal(), allocator_type())
00367         { _M_ht.insert_equal(__f, __l); }
00368 
00369       template<class _InputIterator>
00370         hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
00371               const hasher& __hf, const key_equal& __eql,
00372               const allocator_type& __a = allocator_type())
00373     : _M_ht(__n, __hf, __eql, __a)
00374         { _M_ht.insert_equal(__f, __l); }
00375 
00376       size_type
00377       size() const
00378       { return _M_ht.size(); }
00379 
00380       size_type
00381       max_size() const
00382       { return _M_ht.max_size(); }
00383 
00384       bool
00385       empty() const
00386       { return _M_ht.empty(); }
00387 
00388       void
00389       swap(hash_multimap& __hs)
00390       { _M_ht.swap(__hs._M_ht); }
00391 
00392       template<class _K1, class _T1, class _HF, class _EqK, class _Al>
00393         friend bool
00394         operator==(const hash_multimap<_K1, _T1, _HF, _EqK, _Al>&,
00395            const hash_multimap<_K1, _T1, _HF, _EqK, _Al>&);
00396 
00397       iterator
00398       begin()
00399       { return _M_ht.begin(); }
00400 
00401       iterator
00402       end()
00403       { return _M_ht.end(); }
00404 
00405       const_iterator
00406       begin() const
00407       { return _M_ht.begin(); }
00408 
00409       const_iterator
00410       end() const
00411       { return _M_ht.end(); }
00412 
00413       iterator
00414       insert(const value_type& __obj)
00415       { return _M_ht.insert_equal(__obj); }
00416 
00417       template<class _InputIterator>
00418         void
00419         insert(_InputIterator __f, _InputIterator __l)
00420         { _M_ht.insert_equal(__f,__l); }
00421 
00422       iterator
00423       insert_noresize(const value_type& __obj)
00424       { return _M_ht.insert_equal_noresize(__obj); }
00425 
00426       iterator
00427       find(const key_type& __key)
00428       { return _M_ht.find(__key); }
00429 
00430       const_iterator
00431       find(const key_type& __key) const
00432       { return _M_ht.find(__key); }
00433 
00434       size_type
00435       count(const key_type& __key) const
00436       { return _M_ht.count(__key); }
00437 
00438       pair<iterator, iterator>
00439       equal_range(const key_type& __key)
00440       { return _M_ht.equal_range(__key); }
00441 
00442       pair<const_iterator, const_iterator>
00443       equal_range(const key_type& __key) const
00444       { return _M_ht.equal_range(__key); }
00445 
00446       size_type
00447       erase(const key_type& __key)
00448       { return _M_ht.erase(__key); }
00449 
00450       void
00451       erase(iterator __it)
00452       { _M_ht.erase(__it); }
00453 
00454       void
00455       erase(iterator __f, iterator __l)
00456       { _M_ht.erase(__f, __l); }
00457 
00458       void
00459       clear()
00460       { _M_ht.clear(); }
00461 
00462       void
00463       resize(size_type __hint)
00464       { _M_ht.resize(__hint); }
00465 
00466       size_type
00467       bucket_count() const
00468       { return _M_ht.bucket_count(); }
00469 
00470       size_type
00471       max_bucket_count() const
00472       { return _M_ht.max_bucket_count(); }
00473       
00474       size_type
00475       elems_in_bucket(size_type __n) const
00476       { return _M_ht.elems_in_bucket(__n); }
00477     };
00478 
00479   template<class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>
00480     inline bool
00481     operator==(const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm1,
00482            const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm2)
00483     { return __hm1._M_ht == __hm2._M_ht; }
00484 
00485   template<class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>
00486     inline bool
00487     operator!=(const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm1,
00488            const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm2)
00489     { return !(__hm1 == __hm2); }
00490 
00491   template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
00492     inline void
00493     swap(hash_multimap<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
00494      hash_multimap<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
00495     { __hm1.swap(__hm2); }
00496 
00497 _GLIBCXX_END_NAMESPACE
00498 
00499 _GLIBCXX_BEGIN_NAMESPACE(std)
00500 
00501   // Specialization of insert_iterator so that it will work for hash_map
00502   // and hash_multimap.
00503   template<class _Key, class _Tp, class _HashFn,  class _EqKey, class _Alloc>
00504     class insert_iterator<__gnu_cxx::hash_map<_Key, _Tp, _HashFn, 
00505                           _EqKey, _Alloc> >
00506     {
00507     protected:
00508       typedef __gnu_cxx::hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc>
00509         _Container;
00510       _Container* container;
00511 
00512     public:
00513       typedef _Container          container_type;
00514       typedef output_iterator_tag iterator_category;
00515       typedef void                value_type;
00516       typedef void                difference_type;
00517       typedef void                pointer;
00518       typedef void                reference;
00519       
00520       insert_iterator(_Container& __x)
00521       : container(&__x) {}
00522 
00523       insert_iterator(_Container& __x, typename _Container::iterator)
00524       : container(&__x) {}
00525 
00526       insert_iterator<_Container>&
00527       operator=(const typename _Container::value_type& __value)
00528       {
00529     container->insert(__value);
00530     return *this;
00531       }
00532 
00533       insert_iterator<_Container>&
00534       operator*()
00535       { return *this; }
00536 
00537       insert_iterator<_Container>&
00538       operator++() { return *this; }
00539 
00540       insert_iterator<_Container>&
00541       operator++(int)
00542       { return *this; }
00543     };
00544 
00545   template<class _Key, class _Tp, class _HashFn,  class _EqKey, class _Alloc>
00546     class insert_iterator<__gnu_cxx::hash_multimap<_Key, _Tp, _HashFn,
00547                            _EqKey, _Alloc> >
00548     {
00549     protected:
00550       typedef __gnu_cxx::hash_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc>
00551         _Container;
00552       _Container* container;
00553       typename _Container::iterator iter;
00554 
00555     public:
00556       typedef _Container          container_type;
00557       typedef output_iterator_tag iterator_category;
00558       typedef void                value_type;
00559       typedef void                difference_type;
00560       typedef void                pointer;
00561       typedef void                reference;
00562 
00563       insert_iterator(_Container& __x)
00564       : container(&__x) {}
00565 
00566       insert_iterator(_Container& __x, typename _Container::iterator)
00567       : container(&__x) {}
00568 
00569       insert_iterator<_Container>&
00570       operator=(const typename _Container::value_type& __value)
00571       {
00572     container->insert(__value);
00573     return *this;
00574       }
00575 
00576       insert_iterator<_Container>&
00577       operator*()
00578       { return *this; }
00579 
00580       insert_iterator<_Container>&
00581       operator++()
00582       { return *this; }
00583 
00584       insert_iterator<_Container>&
00585       operator++(int)
00586       { return *this; }
00587     };
00588 
00589 _GLIBCXX_END_NAMESPACE
00590 
00591 #endif

Generated on 19 Jun 2018 for libstdc++ by  doxygen 1.6.1