# 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