# 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 _HASH_MAP
    00063 #define _HASH_MAP 1
    00064
    00065 #include <ext/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
    00076   // declaration.
    00077   template<class _Key, class _Tp, class _HashFcn  = hash<_Key>,
    00078         class _EqualKey = equal_to<_Key>, class _Alloc =  allocator<_Tp> >
    00079     class hash_map;
    00080
    00081   template<class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc>
    00082   inline bool operator==(const hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc>&,
    00083              const hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc>&);
    00084 /**
    00085  *  This is an SGI extension.
    00086  *  @ingroup SGIextensions
    00087  *  @doctodo
    00088 */
    00089 template <class _Key, class _Tp, class _HashFcn, class _EqualKey,
    00090           class _Alloc>
    00091 class hash_map
    00092 {
    00093 private:
    00094   typedef hashtable<pair<const _Key,_Tp>,_Key,_HashFcn,
    00095                     _Select1st<pair<const _Key,_Tp> >,_EqualKey,_Alloc> _Ht;
    00096   _Ht _M_ht;
    00097
    00098 public:
    00099   typedef typename _Ht::key_type key_type;
    00100   typedef _Tp data_type;
    00101   typedef _Tp mapped_type;
    00102   typedef typename _Ht::value_type value_type;
    00103   typedef typename _Ht::hasher hasher;
    00104   typedef typename _Ht::key_equal key_equal;
    00105
    00106   typedef typename _Ht::size_type size_type;
    00107   typedef typename _Ht::difference_type difference_type;
    00108   typedef typename _Ht::pointer pointer;
    00109   typedef typename _Ht::const_pointer const_pointer;
    00110   typedef typename _Ht::reference reference;
    00111   typedef typename _Ht::const_reference const_reference;
    00112
    00113   typedef typename _Ht::iterator iterator;
    00114   typedef typename _Ht::const_iterator const_iterator;
    00115
    00116   typedef typename _Ht::allocator_type allocator_type;
    00117
    00118   hasher hash_funct() const { return _M_ht.hash_funct(); }
    00119   key_equal key_eq() const { return _M_ht.key_eq(); }
    00120   allocator_type get_allocator() const { return _M_ht.get_allocator(); }
    00121
    00122 public:
    00123   hash_map() : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
    00124   explicit hash_map(size_type __n)
    00125     : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
    00126   hash_map(size_type __n, const hasher& __hf)
    00127     : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
    00128   hash_map(size_type __n, const hasher& __hf, const key_equal& __eql,
    00129            const allocator_type& __a = allocator_type())
    00130     : _M_ht(__n, __hf, __eql, __a) {}
    00131
    00132   template <class _InputIterator>
    00133   hash_map(_InputIterator __f, _InputIterator __l)
    00134     : _M_ht(100, hasher(), key_equal(), allocator_type())
    00135     { _M_ht.insert_unique(__f, __l); }
    00136   template <class _InputIterator>
    00137   hash_map(_InputIterator __f, _InputIterator __l, size_type __n)
    00138     : _M_ht(__n, hasher(), key_equal(), allocator_type())
    00139     { _M_ht.insert_unique(__f, __l); }
    00140   template <class _InputIterator>
    00141   hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
    00142            const hasher& __hf)
    00143     : _M_ht(__n, __hf, key_equal(), allocator_type())
    00144     { _M_ht.insert_unique(__f, __l); }
    00145   template <class _InputIterator>
    00146   hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
    00147            const hasher& __hf, const key_equal& __eql,
    00148            const allocator_type& __a = allocator_type())
    00149     : _M_ht(__n, __hf, __eql, __a)
    00150     { _M_ht.insert_unique(__f, __l); }
    00151
    00152 public:
    00153   size_type size() const { return _M_ht.size(); }
    00154   size_type max_size() const { return _M_ht.max_size(); }
    00155   bool empty() const { return _M_ht.empty(); }
    00156   void swap(hash_map& __hs) { _M_ht.swap(__hs._M_ht); }
    00157
    00158   template <class _K1, class _T1, class _HF, class _EqK, class _Al>
    00159   friend bool operator== (const hash_map<_K1, _T1, _HF, _EqK, _Al>&,
    00160                           const hash_map<_K1, _T1, _HF, _EqK, _Al>&);
    00161
    00162   iterator begin() { return _M_ht.begin(); }
    00163   iterator end() { return _M_ht.end(); }
    00164   const_iterator begin() const { return _M_ht.begin(); }
    00165   const_iterator end() const { return _M_ht.end(); }
    00166
    00167 public:
    00168   pair<iterator,bool> insert(const value_type& __obj)
    00169     { return _M_ht.insert_unique(__obj); }
    00170   template <class _InputIterator>
    00171   void insert(_InputIterator __f, _InputIterator __l)
    00172     { _M_ht.insert_unique(__f,__l); }
    00173   pair<iterator,bool> insert_noresize(const value_type& __obj)
    00174     { return _M_ht.insert_unique_noresize(__obj); }
    00175
    00176   iterator find(const key_type& __key) { return _M_ht.find(__key); }
    00177   const_iterator find(const key_type& __key) const
    00178     { return _M_ht.find(__key); }
    00179
    00180   _Tp& operator[](const key_type& __key) {
    00181     return _M_ht.find_or_insert(value_type(__key, _Tp())).second;
    00182   }
    00183
    00184   size_type count(const key_type& __key) const { return _M_ht.count(__key); }
    00185
    00186   pair<iterator, iterator> equal_range(const key_type& __key)
    00187     { return _M_ht.equal_range(__key); }
    00188   pair<const_iterator, const_iterator>
    00189   equal_range(const key_type& __key) const
    00190     { return _M_ht.equal_range(__key); }
    00191
    00192   size_type erase(const key_type& __key) {return _M_ht.erase(__key); }
    00193   void erase(iterator __it) { _M_ht.erase(__it); }
    00194   void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); }
    00195   void clear() { _M_ht.clear(); }
    00196
    00197   void resize(size_type __hint) { _M_ht.resize(__hint); }
    00198   size_type bucket_count() const { return _M_ht.bucket_count(); }
    00199   size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
    00200   size_type elems_in_bucket(size_type __n) const
    00201     { return _M_ht.elems_in_bucket(__n); }
    00202 };
    00203
    00204 template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc>
    00205 inline bool
    00206 operator==(const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1,
    00207            const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2)
    00208 {
    00209   return __hm1._M_ht == __hm2._M_ht;
    00210 }
    00211
    00212 template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc>
    00213 inline bool
    00214 operator!=(const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1,
    00215            const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2) {
    00216   return !(__hm1 == __hm2);
    00217 }
    00218
    00219 template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc>
    00220 inline void
    00221 swap(hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1,
    00222      hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2)
    00223 {
    00224   __hm1.swap(__hm2);
    00225 }
    00226
    00227 // Forward declaration of equality operator; needed for friend declaration.
    00228
    00229 template <class _Key, class _Tp,
    00230           class _HashFcn  = hash<_Key>,
    00231           class _EqualKey = equal_to<_Key>,
    00232           class _Alloc =  allocator<_Tp> >
    00233 class hash_multimap;
    00234
    00235 template <class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>
    00236 inline bool
    00237 operator==(const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm1,
    00238            const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm2);
    00239
    00240 /**
    00241  *  This is an SGI extension.
    00242  *  @ingroup SGIextensions
    00243  *  @doctodo
    00244 */
    00245 template <class _Key, class _Tp, class _HashFcn, class _EqualKey, class _Alloc>
    00246 class hash_multimap
    00247 {
    00248   // concept requirements
    00249   __glibcxx_class_requires(_Key, _SGIAssignableConcept)
    00250   __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
    00251   __glibcxx_class_requires3(_HashFcn, size_t, _Key, _UnaryFunctionConcept)
    00252   __glibcxx_class_requires3(_EqualKey, _Key, _Key, _BinaryPredicateConcept)
    00253
    00254 private:
    00255   typedef hashtable<pair<const _Key, _Tp>, _Key, _HashFcn,
    00256                     _Select1st<pair<const _Key, _Tp> >, _EqualKey, _Alloc>
    00257           _Ht;
    00258   _Ht _M_ht;
    00259
    00260 public:
    00261   typedef typename _Ht::key_type key_type;
    00262   typedef _Tp data_type;
    00263   typedef _Tp mapped_type;
    00264   typedef typename _Ht::value_type value_type;
    00265   typedef typename _Ht::hasher hasher;
    00266   typedef typename _Ht::key_equal key_equal;
    00267
    00268   typedef typename _Ht::size_type size_type;
    00269   typedef typename _Ht::difference_type difference_type;
    00270   typedef typename _Ht::pointer pointer;
    00271   typedef typename _Ht::const_pointer const_pointer;
    00272   typedef typename _Ht::reference reference;
    00273   typedef typename _Ht::const_reference const_reference;
    00274
    00275   typedef typename _Ht::iterator iterator;
    00276   typedef typename _Ht::const_iterator const_iterator;
    00277
    00278   typedef typename _Ht::allocator_type allocator_type;
    00279
    00280   hasher hash_funct() const { return _M_ht.hash_funct(); }
    00281   key_equal key_eq() const { return _M_ht.key_eq(); }
    00282   allocator_type get_allocator() const { return _M_ht.get_allocator(); }
    00283
    00284 public:
    00285   hash_multimap() : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
    00286   explicit hash_multimap(size_type __n)
    00287     : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
    00288   hash_multimap(size_type __n, const hasher& __hf)
    00289     : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
    00290   hash_multimap(size_type __n, const hasher& __hf, const key_equal& __eql,
    00291                 const allocator_type& __a = allocator_type())
    00292     : _M_ht(__n, __hf, __eql, __a) {}
    00293
    00294   template <class _InputIterator>
    00295   hash_multimap(_InputIterator __f, _InputIterator __l)
    00296     : _M_ht(100, hasher(), key_equal(), allocator_type())
    00297     { _M_ht.insert_equal(__f, __l); }
    00298   template <class _InputIterator>
    00299   hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n)
    00300     : _M_ht(__n, hasher(), key_equal(), allocator_type())
    00301     { _M_ht.insert_equal(__f, __l); }
    00302   template <class _InputIterator>
    00303   hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
    00304                 const hasher& __hf)
    00305     : _M_ht(__n, __hf, key_equal(), allocator_type())
    00306     { _M_ht.insert_equal(__f, __l); }
    00307   template <class _InputIterator>
    00308   hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
    00309                 const hasher& __hf, const key_equal& __eql,
    00310                 const allocator_type& __a = allocator_type())
    00311     : _M_ht(__n, __hf, __eql, __a)
    00312     { _M_ht.insert_equal(__f, __l); }
    00313
    00314 public:
    00315   size_type size() const { return _M_ht.size(); }
    00316   size_type max_size() const { return _M_ht.max_size(); }
    00317   bool empty() const { return _M_ht.empty(); }
    00318   void swap(hash_multimap& __hs) { _M_ht.swap(__hs._M_ht); }
    00319
    00320   template <class _K1, class _T1, class _HF, class _EqK, class _Al>
    00321   friend bool operator== (const hash_multimap<_K1, _T1, _HF, _EqK, _Al>&,
    00322                           const hash_multimap<_K1, _T1, _HF, _EqK, _Al>&);
    00323
    00324   iterator begin() { return _M_ht.begin(); }
    00325   iterator end() { return _M_ht.end(); }
    00326   const_iterator begin() const { return _M_ht.begin(); }
    00327   const_iterator end() const { return _M_ht.end(); }
    00328
    00329 public:
    00330   iterator insert(const value_type& __obj)
    00331     { return _M_ht.insert_equal(__obj); }
    00332   template <class _InputIterator>
    00333   void insert(_InputIterator __f, _InputIterator __l)
    00334     { _M_ht.insert_equal(__f,__l); }
    00335   iterator insert_noresize(const value_type& __obj)
    00336     { return _M_ht.insert_equal_noresize(__obj); }
    00337
    00338   iterator find(const key_type& __key) { return _M_ht.find(__key); }
    00339   const_iterator find(const key_type& __key) const
    00340     { return _M_ht.find(__key); }
    00341
    00342   size_type count(const key_type& __key) const { return _M_ht.count(__key); }
    00343
    00344   pair<iterator, iterator> equal_range(const key_type& __key)
    00345     { return _M_ht.equal_range(__key); }
    00346   pair<const_iterator, const_iterator>
    00347   equal_range(const key_type& __key) const
    00348     { return _M_ht.equal_range(__key); }
    00349
    00350   size_type erase(const key_type& __key) {return _M_ht.erase(__key); }
    00351   void erase(iterator __it) { _M_ht.erase(__it); }
    00352   void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); }
    00353   void clear() { _M_ht.clear(); }
    00354
    00355 public:
    00356   void resize(size_type __hint) { _M_ht.resize(__hint); }
    00357   size_type bucket_count() const { return _M_ht.bucket_count(); }
    00358   size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
    00359   size_type elems_in_bucket(size_type __n) const
    00360     { return _M_ht.elems_in_bucket(__n); }
    00361 };
    00362
    00363 template <class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>
    00364 inline bool
    00365 operator==(const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm1,
    00366            const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm2)
    00367 {
    00368   return __hm1._M_ht == __hm2._M_ht;
    00369 }
    00370
    00371 template <class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>
    00372 inline bool
    00373 operator!=(const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm1,
    00374            const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm2) {
    00375   return !(__hm1 == __hm2);
    00376 }
    00377
    00378 template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc>
    00379 inline void
    00380 swap(hash_multimap<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1,
    00381      hash_multimap<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2)
    00382 {
    00383   __hm1.swap(__hm2);
    00384 }
    00385
    00386 } // namespace __gnu_cxx
    00387
    00388 namespace std
    00389 {
    00390 // Specialization of insert_iterator so that it will work for hash_map
    00391 // and hash_multimap.
    00392
    00393 template <class _Key, class _Tp, class _HashFn,  class _EqKey, class _Alloc>
    00394 class insert_iterator<__gnu_cxx::hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc> > {
    00395 protected:
    00396   typedef __gnu_cxx::hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc> _Container;
    00397   _Container* container;
    00398 public:
    00399   typedef _Container          container_type;
    00400   typedef output_iterator_tag iterator_category;
    00401   typedef void                value_type;
    00402   typedef void                difference_type;
    00403   typedef void                pointer;
    00404   typedef void                reference;
    00405
    00406   insert_iterator(_Container& __x) : container(&__x) {}
    00407   insert_iterator(_Container& __x, typename _Container::iterator)
    00408     : container(&__x) {}
    00409   insert_iterator<_Container>&
    00410   operator=(const typename _Container::value_type& __value) {
    00411     container->insert(__value);
    00412     return *this;
    00413   }
    00414   insert_iterator<_Container>& operator*() { return *this; }
    00415   insert_iterator<_Container>& operator++() { return *this; }
    00416   insert_iterator<_Container>& operator++(int) { return *this; }
    00417 };
    00418
    00419 template <class _Key, class _Tp, class _HashFn,  class _EqKey, class _Alloc>
    00420 class insert_iterator<__gnu_cxx::hash_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc> > {
    00421 protected:
    00422   typedef __gnu_cxx::hash_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc> _Container;
    00423   _Container* container;
    00424   typename _Container::iterator iter;
    00425 public:
    00426   typedef _Container          container_type;
    00427   typedef output_iterator_tag iterator_category;
    00428   typedef void                value_type;
    00429   typedef void                difference_type;
    00430   typedef void                pointer;
    00431   typedef void                reference;
    00432
    00433   insert_iterator(_Container& __x) : container(&__x) {}
    00434   insert_iterator(_Container& __x, typename _Container::iterator)
    00435     : container(&__x) {}
    00436   insert_iterator<_Container>&
    00437   operator=(const typename _Container::value_type& __value) {
    00438     container->insert(__value);
    00439     return *this;
    00440   }
    00441   insert_iterator<_Container>& operator*() { return *this; }
    00442   insert_iterator<_Container>& operator++() { return *this; }
    00443   insert_iterator<_Container>& operator++(int) { return *this; }
    00444 };
    00445 } // namespace std
    00446
    00447 #endif