unordered_map.h

Go to the documentation of this file.
00001 // unordered_map implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2010 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 3, 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 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 /** @file bits/unordered_map.h
00026  *  This is an internal header file, included by other library headers.
00027  *  You should not attempt to use it directly.
00028  */
00029 
00030 #ifndef _UNORDERED_MAP_H
00031 #define _UNORDERED_MAP_H
00032 
00033 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D)
00034 
00035   // XXX When we get typedef templates these class definitions
00036   // will be unnecessary.
00037   template<class _Key, class _Tp,
00038        class _Hash = hash<_Key>,
00039        class _Pred = std::equal_to<_Key>,
00040        class _Alloc = std::allocator<std::pair<const _Key, _Tp> >,
00041        bool __cache_hash_code = false>
00042     class __unordered_map
00043     : public _Hashtable<_Key, std::pair<const _Key, _Tp>, _Alloc,
00044             std::_Select1st<std::pair<const _Key, _Tp> >, _Pred, 
00045             _Hash, __detail::_Mod_range_hashing,
00046             __detail::_Default_ranged_hash,
00047             __detail::_Prime_rehash_policy,
00048             __cache_hash_code, false, true>
00049     {
00050       typedef _Hashtable<_Key, std::pair<const _Key, _Tp>, _Alloc,
00051              std::_Select1st<std::pair<const _Key, _Tp> >, _Pred,
00052              _Hash, __detail::_Mod_range_hashing,
00053              __detail::_Default_ranged_hash,
00054              __detail::_Prime_rehash_policy,
00055              __cache_hash_code, false, true>
00056         _Base;
00057 
00058     public:
00059       typedef typename _Base::size_type       size_type;
00060       typedef typename _Base::hasher          hasher;
00061       typedef typename _Base::key_equal       key_equal;
00062       typedef typename _Base::allocator_type  allocator_type;
00063 
00064       explicit
00065       __unordered_map(size_type __n = 10,
00066               const hasher& __hf = hasher(),
00067               const key_equal& __eql = key_equal(),
00068               const allocator_type& __a = allocator_type())
00069       : _Base(__n, __hf, __detail::_Mod_range_hashing(),
00070           __detail::_Default_ranged_hash(),
00071           __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a)
00072       { }
00073 
00074       template<typename _InputIterator>
00075         __unordered_map(_InputIterator __f, _InputIterator __l, 
00076             size_type __n = 10,
00077             const hasher& __hf = hasher(), 
00078             const key_equal& __eql = key_equal(), 
00079             const allocator_type& __a = allocator_type())
00080     : _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(),
00081         __detail::_Default_ranged_hash(),
00082         __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a)
00083     { }
00084 
00085       __unordered_map(__unordered_map&& __x)
00086       : _Base(std::forward<_Base>(__x)) { }
00087     };
00088   
00089   template<class _Key, class _Tp,
00090        class _Hash = hash<_Key>,
00091        class _Pred = std::equal_to<_Key>,
00092        class _Alloc = std::allocator<std::pair<const _Key, _Tp> >,
00093        bool __cache_hash_code = false>
00094     class __unordered_multimap
00095     : public _Hashtable<_Key, std::pair<const _Key, _Tp>,
00096             _Alloc,
00097             std::_Select1st<std::pair<const _Key, _Tp> >, _Pred,
00098             _Hash, __detail::_Mod_range_hashing,
00099             __detail::_Default_ranged_hash,
00100             __detail::_Prime_rehash_policy,
00101             __cache_hash_code, false, false>
00102     {
00103       typedef _Hashtable<_Key, std::pair<const _Key, _Tp>,
00104              _Alloc,
00105              std::_Select1st<std::pair<const _Key, _Tp> >, _Pred,
00106              _Hash, __detail::_Mod_range_hashing,
00107              __detail::_Default_ranged_hash,
00108              __detail::_Prime_rehash_policy,
00109              __cache_hash_code, false, false>
00110         _Base;
00111 
00112     public:
00113       typedef typename _Base::size_type       size_type;
00114       typedef typename _Base::hasher          hasher;
00115       typedef typename _Base::key_equal       key_equal;
00116       typedef typename _Base::allocator_type  allocator_type;
00117       
00118       explicit
00119       __unordered_multimap(size_type __n = 10,
00120                const hasher& __hf = hasher(),
00121                const key_equal& __eql = key_equal(),
00122                const allocator_type& __a = allocator_type())
00123       : _Base(__n, __hf, __detail::_Mod_range_hashing(),
00124           __detail::_Default_ranged_hash(),
00125           __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a)
00126       { }
00127 
00128 
00129       template<typename _InputIterator>
00130         __unordered_multimap(_InputIterator __f, _InputIterator __l, 
00131                  typename _Base::size_type __n = 0,
00132                  const hasher& __hf = hasher(), 
00133                  const key_equal& __eql = key_equal(), 
00134                  const allocator_type& __a = allocator_type())
00135     : _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(),
00136         __detail::_Default_ranged_hash(),
00137         __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a)
00138         { }
00139 
00140       __unordered_multimap(__unordered_multimap&& __x)
00141       : _Base(std::forward<_Base>(__x)) { }
00142     };
00143 
00144   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc,
00145        bool __cache_hash_code>
00146     inline void
00147     swap(__unordered_map<_Key, _Tp, _Hash, _Pred,
00148      _Alloc, __cache_hash_code>& __x,
00149      __unordered_map<_Key, _Tp, _Hash, _Pred,
00150      _Alloc, __cache_hash_code>& __y)
00151     { __x.swap(__y); }
00152 
00153   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc,
00154        bool __cache_hash_code>
00155     inline void
00156     swap(__unordered_multimap<_Key, _Tp, _Hash, _Pred,
00157      _Alloc, __cache_hash_code>& __x,
00158      __unordered_multimap<_Key, _Tp, _Hash, _Pred,
00159      _Alloc, __cache_hash_code>& __y)
00160     { __x.swap(__y); }
00161 
00162   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc,
00163        bool __cache_hash_code>
00164     inline bool
00165     operator==(const __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc,
00166            __cache_hash_code>& __x,
00167            const __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc,
00168            __cache_hash_code>& __y)
00169     { return __x._M_equal(__y); }
00170 
00171   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc,
00172        bool __cache_hash_code>
00173     inline bool
00174     operator!=(const __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc,
00175            __cache_hash_code>& __x,
00176            const __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc,
00177            __cache_hash_code>& __y)
00178     { return !(__x == __y); }
00179 
00180   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc,
00181        bool __cache_hash_code>
00182     inline bool
00183     operator==(const __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc,
00184            __cache_hash_code>& __x,
00185            const __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc,
00186            __cache_hash_code>& __y)
00187     { return __x._M_equal(__y); }
00188 
00189   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc,
00190        bool __cache_hash_code>
00191     inline bool
00192     operator!=(const __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc,
00193            __cache_hash_code>& __x,
00194            const __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc,
00195            __cache_hash_code>& __y)
00196     { return !(__x == __y); }
00197 
00198   /**
00199    *  @brief A standard container composed of unique keys (containing
00200    *  at most one of each key value) that associates values of another type
00201    *  with the keys.
00202    *
00203    *  @ingroup unordered_associative_containers
00204    *
00205    *  Meets the requirements of a <a href="tables.html#65">container</a>, and
00206    *  <a href="tables.html#xx">unordered associative container</a>
00207    *
00208    *  @param  Key  Type of key objects.
00209    *  @param  Tp  Type of mapped objects.
00210    *  @param  Hash  Hashing function object type, defaults to hash<Value>.
00211    *  @param  Pred  Predicate function object type, defaults to equal_to<Value>.
00212    *  @param  Alloc  Allocator type, defaults to allocator<Key>.
00213    *
00214    * The resulting value type of the container is std::pair<const Key, Tp>.
00215    */
00216   template<class _Key, class _Tp,
00217        class _Hash = hash<_Key>,
00218        class _Pred = std::equal_to<_Key>,
00219        class _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
00220     class unordered_map
00221     : public __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>
00222     {
00223       typedef __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>  _Base;
00224 
00225     public:
00226       typedef typename _Base::value_type      value_type;
00227       typedef typename _Base::size_type       size_type;
00228       typedef typename _Base::hasher          hasher;
00229       typedef typename _Base::key_equal       key_equal;
00230       typedef typename _Base::allocator_type  allocator_type;
00231 
00232       explicit
00233       unordered_map(size_type __n = 10,
00234             const hasher& __hf = hasher(),
00235             const key_equal& __eql = key_equal(),
00236             const allocator_type& __a = allocator_type())
00237       : _Base(__n, __hf, __eql, __a)
00238       { }
00239 
00240       template<typename _InputIterator>
00241         unordered_map(_InputIterator __f, _InputIterator __l, 
00242               size_type __n = 10,
00243               const hasher& __hf = hasher(), 
00244               const key_equal& __eql = key_equal(), 
00245               const allocator_type& __a = allocator_type())
00246     : _Base(__f, __l, __n, __hf, __eql, __a)
00247         { }
00248 
00249       unordered_map(unordered_map&& __x)
00250       : _Base(std::forward<_Base>(__x)) { }
00251 
00252       unordered_map(initializer_list<value_type> __l,
00253             size_type __n = 10,
00254             const hasher& __hf = hasher(),
00255             const key_equal& __eql = key_equal(),
00256             const allocator_type& __a = allocator_type())
00257     : _Base(__l.begin(), __l.end(), __n, __hf, __eql, __a)
00258       { }
00259 
00260       unordered_map&
00261       operator=(unordered_map&& __x)
00262       {
00263     // NB: DR 1204.
00264     // NB: DR 675.
00265     this->clear();
00266     this->swap(__x);
00267     return *this;   
00268       }
00269 
00270       unordered_map&
00271       operator=(initializer_list<value_type> __l)
00272       {
00273     this->clear();
00274     this->insert(__l.begin(), __l.end());
00275     return *this;
00276       }
00277     };
00278   
00279   /**
00280    *  @brief A standard container composed of equivalent keys
00281    *  (possibly containing multiple of each key value) that associates
00282    *  values of another type with the keys.
00283    *
00284    *  @ingroup unordered_associative_containers
00285    *
00286    *  Meets the requirements of a <a href="tables.html#65">container</a>, and
00287    *  <a href="tables.html#xx">unordered associative container</a>
00288    *
00289    *  @param  Key  Type of key objects.
00290    *  @param  Tp  Type of mapped objects.
00291    *  @param  Hash  Hashing function object type, defaults to hash<Value>.
00292    *  @param  Pred  Predicate function object type, defaults to equal_to<Value>.
00293    *  @param  Alloc  Allocator type, defaults to allocator<Key>.
00294    *
00295    * The resulting value type of the container is std::pair<const Key, Tp>.
00296    */
00297   template<class _Key, class _Tp,
00298        class _Hash = hash<_Key>,
00299        class _Pred = std::equal_to<_Key>,
00300        class _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
00301     class unordered_multimap
00302     : public __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>
00303     {
00304       typedef __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>  _Base;
00305 
00306     public:
00307       typedef typename _Base::value_type      value_type;
00308       typedef typename _Base::size_type       size_type;
00309       typedef typename _Base::hasher          hasher;
00310       typedef typename _Base::key_equal       key_equal;
00311       typedef typename _Base::allocator_type  allocator_type;
00312       
00313       explicit
00314       unordered_multimap(size_type __n = 10,
00315              const hasher& __hf = hasher(),
00316              const key_equal& __eql = key_equal(),
00317              const allocator_type& __a = allocator_type())
00318       : _Base(__n, __hf, __eql, __a)
00319       { }
00320 
00321 
00322       template<typename _InputIterator>
00323         unordered_multimap(_InputIterator __f, _InputIterator __l, 
00324                typename _Base::size_type __n = 0,
00325                const hasher& __hf = hasher(), 
00326                const key_equal& __eql = key_equal(), 
00327                const allocator_type& __a = allocator_type())
00328     : _Base(__f, __l, __n, __hf, __eql, __a)
00329         { }
00330 
00331       unordered_multimap(unordered_multimap&& __x)
00332       : _Base(std::forward<_Base>(__x)) { }
00333 
00334       unordered_multimap(initializer_list<value_type> __l,
00335              size_type __n = 10,
00336              const hasher& __hf = hasher(),
00337              const key_equal& __eql = key_equal(),
00338              const allocator_type& __a = allocator_type())
00339     : _Base(__l.begin(), __l.end(), __n, __hf, __eql, __a)
00340       { }
00341 
00342       unordered_multimap&
00343       operator=(unordered_multimap&& __x)
00344       {
00345     // NB: DR 1204.
00346     // NB: DR 675.
00347     this->clear();
00348     this->swap(__x);
00349     return *this;   
00350       }
00351 
00352       unordered_multimap&
00353       operator=(initializer_list<value_type> __l)
00354       {
00355     this->clear();
00356     this->insert(__l.begin(), __l.end());
00357     return *this;
00358       }
00359     };
00360 
00361   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
00362     inline void
00363     swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00364      unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00365     { __x.swap(__y); }
00366 
00367   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
00368     inline void
00369     swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00370      unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00371     { __x.swap(__y); }
00372 
00373   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
00374     inline bool
00375     operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00376            const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00377     { return __x._M_equal(__y); }
00378 
00379   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
00380     inline bool
00381     operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00382            const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00383     { return !(__x == __y); }
00384 
00385   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
00386     inline bool
00387     operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00388            const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00389     { return __x._M_equal(__y); }
00390 
00391   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
00392     inline bool
00393     operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00394            const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00395     { return !(__x == __y); }
00396 
00397 _GLIBCXX_END_NESTED_NAMESPACE
00398 
00399 #endif /* _UNORDERED_MAP_H */