libstdc++
unordered_map
Go to the documentation of this file.
00001 // Profiling unordered_map/unordered_multimap implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2009-2013 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 along
00021 // with this library; see the file COPYING3.  If not see
00022 // <http://www.gnu.org/licenses/>.
00023 
00024 /** @file profile/unordered_map
00025  *  This file is a GNU profile extension to the Standard C++ Library.
00026  */
00027 
00028 #ifndef _GLIBCXX_PROFILE_UNORDERED_MAP
00029 #define _GLIBCXX_PROFILE_UNORDERED_MAP 1
00030 
00031 #if __cplusplus < 201103L
00032 # include <bits/c++0x_warning.h>
00033 #else
00034 # include <unordered_map>
00035 
00036 #include <profile/base.h>
00037 #include <profile/unordered_base.h>
00038 
00039 #define _GLIBCXX_BASE unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>
00040 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE
00041 
00042 namespace std _GLIBCXX_VISIBILITY(default)
00043 {
00044 namespace __profile
00045 {
00046   /// Class std::unordered_map wrapper with performance instrumentation.
00047   template<typename _Key, typename _Tp,
00048        typename _Hash = std::hash<_Key>,
00049        typename _Pred = std::equal_to<_Key>,
00050        typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
00051     class unordered_map
00052     : public _GLIBCXX_STD_BASE,
00053       public _Unordered_profile<unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>,
00054                 true>
00055     {
00056       typedef typename _GLIBCXX_STD_BASE _Base;
00057 
00058       _Base&
00059       _M_base() noexcept       { return *this; }
00060 
00061       const _Base&
00062       _M_base() const noexcept { return *this; }
00063 
00064     public:
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       typedef typename _Base::key_type        key_type;
00070       typedef typename _Base::value_type      value_type;
00071       typedef typename _Base::difference_type difference_type;
00072       typedef typename _Base::reference       reference;
00073       typedef typename _Base::const_reference const_reference;
00074       typedef typename _Base::mapped_type      mapped_type;
00075 
00076       typedef typename _Base::iterator iterator;
00077       typedef typename _Base::const_iterator const_iterator;
00078 
00079       explicit
00080       unordered_map(size_type __n = 10,
00081             const hasher& __hf = hasher(),
00082             const key_equal& __eql = key_equal(),
00083             const allocator_type& __a = allocator_type())
00084     : _Base(__n, __hf, __eql, __a)
00085       { }
00086 
00087       template<typename _InputIterator>
00088         unordered_map(_InputIterator __f, _InputIterator __l,
00089               size_type __n = 0,
00090               const hasher& __hf = hasher(),
00091               const key_equal& __eql = key_equal(),
00092               const allocator_type& __a = allocator_type())
00093       : _Base(__f, __l, __n, __hf, __eql, __a)
00094         { }
00095 
00096       unordered_map(const unordered_map&) = default;
00097 
00098       unordered_map(const _Base& __x)
00099     : _Base(__x)
00100       { }
00101 
00102       unordered_map(unordered_map&&) = default;
00103 
00104       unordered_map(initializer_list<value_type> __l,
00105             size_type __n = 0,
00106             const hasher& __hf = hasher(),
00107             const key_equal& __eql = key_equal(),
00108             const allocator_type& __a = allocator_type())
00109     : _Base(__l, __n, __hf, __eql, __a)
00110       { }
00111 
00112       unordered_map&
00113       operator=(const unordered_map&) = default;
00114 
00115       unordered_map&
00116       operator=(unordered_map&&) = default;
00117 
00118       unordered_map&
00119       operator=(initializer_list<value_type> __l)
00120       {
00121     _M_base() = __l;
00122     return *this;
00123       }
00124 
00125       void
00126       clear() noexcept
00127       {
00128         __profcxx_hashtable_destruct(this, _Base::bucket_count(),
00129                      _Base::size());
00130         this->_M_profile_destruct();
00131     _Base::clear();
00132       }
00133 
00134       template<typename... _Args>
00135     std::pair<iterator, bool>
00136     emplace(_Args&&... __args)
00137     {
00138       size_type __old_size = _Base::bucket_count();
00139       std::pair<iterator, bool> __res
00140         = _Base::emplace(std::forward<_Args>(__args)...);
00141       _M_profile_resize(__old_size);
00142       return __res;
00143     }
00144 
00145       template<typename... _Args>
00146     iterator
00147     emplace_hint(const_iterator __it, _Args&&... __args)
00148     {
00149       size_type __old_size = _Base::bucket_count();
00150       iterator __res
00151         = _Base::emplace_hint(__it, std::forward<_Args>(__args)...);
00152       _M_profile_resize(__old_size);
00153       return __res;
00154     }
00155 
00156       void
00157       insert(std::initializer_list<value_type> __l)
00158       { 
00159         size_type __old_size = _Base::bucket_count(); 
00160         _Base::insert(__l);
00161         _M_profile_resize(__old_size); 
00162       }
00163 
00164       std::pair<iterator, bool>
00165       insert(const value_type& __obj)
00166       {
00167         size_type __old_size = _Base::bucket_count();
00168         std::pair<iterator, bool> __res = _Base::insert(__obj);
00169         _M_profile_resize(__old_size); 
00170         return __res;
00171       }
00172 
00173       iterator
00174       insert(const_iterator __iter, const value_type& __v)
00175       { 
00176         size_type __old_size = _Base::bucket_count(); 
00177         iterator __res = _Base::insert(__iter, __v);
00178         _M_profile_resize(__old_size); 
00179         return __res;
00180       }
00181 
00182       template<typename _Pair, typename = typename
00183            std::enable_if<std::is_constructible<value_type,
00184                             _Pair&&>::value>::type>
00185         std::pair<iterator, bool>
00186         insert(_Pair&& __obj)
00187         {
00188       size_type __old_size = _Base::bucket_count();
00189       std::pair<iterator, bool> __res
00190         = _Base::insert(std::forward<_Pair>(__obj));
00191       _M_profile_resize(__old_size); 
00192       return __res;
00193     }
00194 
00195       template<typename _Pair, typename = typename
00196            std::enable_if<std::is_constructible<value_type,
00197                             _Pair&&>::value>::type>
00198         iterator
00199         insert(const_iterator __iter, _Pair&& __v)
00200         { 
00201       size_type __old_size = _Base::bucket_count(); 
00202       iterator __res = _Base::insert(__iter, std::forward<_Pair>(__v));
00203       _M_profile_resize(__old_size); 
00204       return __res;
00205     }
00206 
00207       template<typename _InputIter>
00208         void
00209         insert(_InputIter __first, _InputIter __last)
00210         {
00211       size_type __old_size = _Base::bucket_count(); 
00212       _Base::insert(__first, __last);
00213       _M_profile_resize(__old_size); 
00214     }
00215 
00216       // operator[]
00217       mapped_type&
00218       operator[](const _Key& __k)
00219       {
00220         size_type __old_size = _Base::bucket_count();
00221         mapped_type& __res = _M_base()[__k];
00222         _M_profile_resize(__old_size); 
00223         return __res;
00224       }
00225 
00226       mapped_type&
00227       operator[](_Key&& __k)
00228       {
00229         size_type __old_size = _Base::bucket_count();
00230         mapped_type& __res = _M_base()[std::move(__k)];
00231         _M_profile_resize(__old_size); 
00232         return __res;
00233       }
00234 
00235       void
00236       swap(unordered_map& __x)
00237       { _Base::swap(__x._M_base()); }
00238 
00239       void rehash(size_type __n)
00240       {
00241     size_type __old_size = _Base::bucket_count();
00242     _Base::rehash(__n);
00243     _M_profile_resize(__old_size); 
00244       }
00245 
00246     private:
00247       void
00248       _M_profile_resize(size_type __old_size)
00249       {
00250     size_type __new_size = _Base::bucket_count();
00251     if (__old_size != __new_size)
00252       __profcxx_hashtable_resize(this, __old_size, __new_size);
00253       }
00254   };
00255 
00256   template<typename _Key, typename _Tp, typename _Hash,
00257        typename _Pred, typename _Alloc>
00258     inline void
00259     swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00260      unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00261     { __x.swap(__y); }
00262 
00263   template<typename _Key, typename _Tp, typename _Hash,
00264        typename _Pred, typename _Alloc>
00265     inline bool
00266     operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00267            const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00268     { return static_cast<const _GLIBCXX_STD_BASE&>(__x) == __y; }
00269 
00270   template<typename _Key, typename _Tp, typename _Hash,
00271        typename _Pred, typename _Alloc>
00272     inline bool
00273     operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00274            const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00275     { return !(__x == __y); }
00276 
00277 #undef _GLIBCXX_BASE
00278 #undef _GLIBCXX_STD_BASE
00279 #define _GLIBCXX_BASE unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>
00280 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE
00281 
00282   /// Class std::unordered_multimap wrapper with performance instrumentation.
00283   template<typename _Key, typename _Tp,
00284        typename _Hash = std::hash<_Key>,
00285        typename _Pred = std::equal_to<_Key>,
00286        typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
00287     class unordered_multimap
00288     : public _GLIBCXX_STD_BASE,
00289       public _Unordered_profile<unordered_multimap<_Key, _Tp,
00290                            _Hash, _Pred, _Alloc>,
00291                 false>
00292     {      
00293       typedef typename _GLIBCXX_STD_BASE _Base;
00294 
00295       _Base&
00296       _M_base() noexcept       { return *this; }
00297 
00298       const _Base&
00299       _M_base() const noexcept { return *this; }
00300 
00301     public:
00302       typedef typename _Base::size_type       size_type;
00303       typedef typename _Base::hasher          hasher;
00304       typedef typename _Base::key_equal       key_equal;
00305       typedef typename _Base::allocator_type  allocator_type;
00306       typedef typename _Base::key_type        key_type;
00307       typedef typename _Base::value_type      value_type;
00308       typedef typename _Base::difference_type difference_type;
00309       typedef typename _Base::reference       reference;
00310       typedef typename _Base::const_reference const_reference;
00311 
00312       typedef typename _Base::iterator iterator;
00313       typedef typename _Base::const_iterator const_iterator;
00314 
00315       explicit
00316       unordered_multimap(size_type __n = 10,
00317              const hasher& __hf = hasher(),
00318              const key_equal& __eql = key_equal(),
00319              const allocator_type& __a = allocator_type())
00320     : _Base(__n, __hf, __eql, __a)
00321       { }
00322 
00323       template<typename _InputIterator>
00324         unordered_multimap(_InputIterator __f, _InputIterator __l,
00325                size_type __n = 0,
00326                const hasher& __hf = hasher(),
00327                const key_equal& __eql = key_equal(),
00328                const allocator_type& __a = allocator_type())
00329       : _Base(__f, __l, __n, __hf, __eql, __a)
00330       { }
00331 
00332       unordered_multimap(const unordered_multimap&) = default;
00333 
00334       unordered_multimap(const _Base& __x)
00335     : _Base(__x)
00336       { }
00337 
00338       unordered_multimap(unordered_multimap&&) = default;
00339 
00340       unordered_multimap(initializer_list<value_type> __l,
00341              size_type __n = 0,
00342              const hasher& __hf = hasher(),
00343              const key_equal& __eql = key_equal(),
00344              const allocator_type& __a = allocator_type())
00345       : _Base(__l, __n, __hf, __eql, __a)
00346       { }
00347 
00348       unordered_multimap&
00349       operator=(const unordered_multimap&) = default;
00350 
00351       unordered_multimap&
00352       operator=(unordered_multimap&&) = default;
00353 
00354       unordered_multimap&
00355       operator=(initializer_list<value_type> __l)
00356       {
00357     _M_base() = __l;
00358     return *this;
00359       }
00360 
00361       void
00362       clear() noexcept
00363       {
00364     __profcxx_hashtable_destruct(this, _Base::bucket_count(), 
00365                      _Base::size());
00366     this->_M_profile_destruct();
00367     _Base::clear();
00368       }
00369 
00370       template<typename... _Args>
00371     iterator
00372     emplace(_Args&&... __args)
00373     {
00374       size_type __old_size = _Base::bucket_count();
00375       iterator __res
00376         = _Base::emplace(std::forward<_Args>(__args)...);
00377       _M_profile_resize(__old_size);
00378       return __res;
00379     }
00380 
00381       template<typename... _Args>
00382     iterator
00383     emplace_hint(const_iterator __it, _Args&&... __args)
00384     {
00385       size_type __old_size = _Base::bucket_count();
00386       iterator __res
00387         = _Base::emplace_hint(__it, std::forward<_Args>(__args)...);
00388       _M_profile_resize(__old_size);
00389       return __res;
00390     }
00391 
00392       void
00393       insert(std::initializer_list<value_type> __l)
00394       { 
00395         size_type __old_size = _Base::bucket_count();
00396         _Base::insert(__l);
00397         _M_profile_resize(__old_size);
00398       }
00399 
00400       iterator
00401       insert(const value_type& __obj)
00402       {
00403         size_type __old_size = _Base::bucket_count();
00404         iterator __res = _Base::insert(__obj);
00405         _M_profile_resize(__old_size); 
00406         return __res;
00407       }
00408 
00409       iterator
00410       insert(const_iterator __iter, const value_type& __v)
00411       { 
00412         size_type __old_size = _Base::bucket_count(); 
00413         iterator __res = _Base::insert(__iter, __v);
00414         _M_profile_resize(__old_size); 
00415         return __res;
00416       }
00417 
00418       template<typename _Pair, typename = typename
00419            std::enable_if<std::is_constructible<value_type,
00420                             _Pair&&>::value>::type>
00421         iterator
00422         insert(_Pair&& __obj)
00423         {
00424       size_type __old_size = _Base::bucket_count();
00425       iterator __res = _Base::insert(std::forward<_Pair>(__obj));
00426       _M_profile_resize(__old_size); 
00427       return __res;
00428     }
00429 
00430       template<typename _Pair, typename = typename
00431            std::enable_if<std::is_constructible<value_type,
00432                             _Pair&&>::value>::type>
00433         iterator
00434         insert(const_iterator __iter, _Pair&& __v)
00435         {
00436       size_type __old_size = _Base::bucket_count(); 
00437       iterator __res = _Base::insert(__iter, std::forward<_Pair>(__v));
00438       _M_profile_resize(__old_size); 
00439       return __res;
00440     }
00441 
00442       template<typename _InputIter>
00443         void
00444         insert(_InputIter __first, _InputIter __last)
00445         {
00446       size_type __old_size = _Base::bucket_count(); 
00447       _Base::insert(__first, __last);
00448       _M_profile_resize(__old_size); 
00449     }
00450 
00451       void
00452       swap(unordered_multimap& __x)
00453       { _Base::swap(__x._M_base()); }
00454 
00455       void
00456       rehash(size_type __n)
00457       {
00458         size_type __old_size = _Base::bucket_count();
00459         _Base::rehash(__n);
00460         _M_profile_resize(__old_size); 
00461       }
00462 
00463     private:
00464       void
00465       _M_profile_resize(size_type __old_size)
00466       {
00467     size_type __new_size = _Base::bucket_count();
00468         if (__old_size != __new_size)
00469           __profcxx_hashtable_resize(this, __old_size, __new_size);
00470       }
00471   };
00472 
00473   template<typename _Key, typename _Tp, typename _Hash,
00474        typename _Pred, typename _Alloc>
00475     inline void
00476     swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00477      unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00478     { __x.swap(__y); }
00479 
00480   template<typename _Key, typename _Tp, typename _Hash,
00481        typename _Pred, typename _Alloc>
00482     inline bool
00483     operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00484            const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00485     { return static_cast<const _GLIBCXX_STD_BASE&>(__x) == __y; }
00486 
00487   template<typename _Key, typename _Tp, typename _Hash,
00488        typename _Pred, typename _Alloc>
00489     inline bool
00490     operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00491            const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00492     { return !(__x == __y); }
00493 
00494 } // namespace __profile
00495 } // namespace std
00496 
00497 #undef _GLIBCXX_BASE
00498 #undef _GLIBCXX_STD_BASE
00499 
00500 #endif // C++11
00501 
00502 #endif