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