libstdc++
unordered_map
Go to the documentation of this file.
00001 // Profiling unordered_map/unordered_multimap implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2009-2014 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       explicit
00105       unordered_map(const allocator_type& __a)
00106     : _Base(__a)
00107       { }
00108 
00109       unordered_map(const unordered_map& __umap,
00110             const allocator_type& __a)
00111     : _Base(__umap, __a)
00112       { }
00113 
00114       unordered_map(unordered_map&& __umap,
00115             const allocator_type& __a)
00116     : _Base(std::move(__umap._M_base()), __a)
00117       { }
00118 
00119       unordered_map(initializer_list<value_type> __l,
00120             size_type __n = 0,
00121             const hasher& __hf = hasher(),
00122             const key_equal& __eql = key_equal(),
00123             const allocator_type& __a = allocator_type())
00124     : _Base(__l, __n, __hf, __eql, __a)
00125       { }
00126 
00127       unordered_map&
00128       operator=(const unordered_map&) = default;
00129 
00130       unordered_map&
00131       operator=(unordered_map&&) = default;
00132 
00133       unordered_map&
00134       operator=(initializer_list<value_type> __l)
00135       {
00136     _M_base() = __l;
00137     return *this;
00138       }
00139 
00140       void
00141       clear() noexcept
00142       {
00143         __profcxx_hashtable_destruct(this, _Base::bucket_count(),
00144                      _Base::size());
00145         this->_M_profile_destruct();
00146     _Base::clear();
00147       }
00148 
00149       template<typename... _Args>
00150     std::pair<iterator, bool>
00151     emplace(_Args&&... __args)
00152     {
00153       size_type __old_size = _Base::bucket_count();
00154       std::pair<iterator, bool> __res
00155         = _Base::emplace(std::forward<_Args>(__args)...);
00156       _M_profile_resize(__old_size);
00157       return __res;
00158     }
00159 
00160       template<typename... _Args>
00161     iterator
00162     emplace_hint(const_iterator __it, _Args&&... __args)
00163     {
00164       size_type __old_size = _Base::bucket_count();
00165       iterator __res
00166         = _Base::emplace_hint(__it, std::forward<_Args>(__args)...);
00167       _M_profile_resize(__old_size);
00168       return __res;
00169     }
00170 
00171       void
00172       insert(std::initializer_list<value_type> __l)
00173       { 
00174         size_type __old_size = _Base::bucket_count(); 
00175         _Base::insert(__l);
00176         _M_profile_resize(__old_size); 
00177       }
00178 
00179       std::pair<iterator, bool>
00180       insert(const value_type& __obj)
00181       {
00182         size_type __old_size = _Base::bucket_count();
00183         std::pair<iterator, bool> __res = _Base::insert(__obj);
00184         _M_profile_resize(__old_size); 
00185         return __res;
00186       }
00187 
00188       iterator
00189       insert(const_iterator __iter, const value_type& __v)
00190       { 
00191         size_type __old_size = _Base::bucket_count(); 
00192         iterator __res = _Base::insert(__iter, __v);
00193         _M_profile_resize(__old_size); 
00194         return __res;
00195       }
00196 
00197       template<typename _Pair, typename = typename
00198            std::enable_if<std::is_constructible<value_type,
00199                             _Pair&&>::value>::type>
00200         std::pair<iterator, bool>
00201         insert(_Pair&& __obj)
00202         {
00203       size_type __old_size = _Base::bucket_count();
00204       std::pair<iterator, bool> __res
00205         = _Base::insert(std::forward<_Pair>(__obj));
00206       _M_profile_resize(__old_size); 
00207       return __res;
00208     }
00209 
00210       template<typename _Pair, typename = typename
00211            std::enable_if<std::is_constructible<value_type,
00212                             _Pair&&>::value>::type>
00213         iterator
00214         insert(const_iterator __iter, _Pair&& __v)
00215         { 
00216       size_type __old_size = _Base::bucket_count(); 
00217       iterator __res = _Base::insert(__iter, std::forward<_Pair>(__v));
00218       _M_profile_resize(__old_size); 
00219       return __res;
00220     }
00221 
00222       template<typename _InputIter>
00223         void
00224         insert(_InputIter __first, _InputIter __last)
00225         {
00226       size_type __old_size = _Base::bucket_count(); 
00227       _Base::insert(__first, __last);
00228       _M_profile_resize(__old_size); 
00229     }
00230 
00231       // operator[]
00232       mapped_type&
00233       operator[](const _Key& __k)
00234       {
00235         size_type __old_size = _Base::bucket_count();
00236         mapped_type& __res = _M_base()[__k];
00237         _M_profile_resize(__old_size); 
00238         return __res;
00239       }
00240 
00241       mapped_type&
00242       operator[](_Key&& __k)
00243       {
00244         size_type __old_size = _Base::bucket_count();
00245         mapped_type& __res = _M_base()[std::move(__k)];
00246         _M_profile_resize(__old_size); 
00247         return __res;
00248       }
00249 
00250       void
00251       swap(unordered_map& __x)
00252       noexcept( noexcept(__x._M_base().swap(__x)) )
00253       { _Base::swap(__x._M_base()); }
00254 
00255       void rehash(size_type __n)
00256       {
00257     size_type __old_size = _Base::bucket_count();
00258     _Base::rehash(__n);
00259     _M_profile_resize(__old_size); 
00260       }
00261 
00262     private:
00263       void
00264       _M_profile_resize(size_type __old_size)
00265       {
00266     size_type __new_size = _Base::bucket_count();
00267     if (__old_size != __new_size)
00268       __profcxx_hashtable_resize(this, __old_size, __new_size);
00269       }
00270   };
00271 
00272   template<typename _Key, typename _Tp, typename _Hash,
00273        typename _Pred, typename _Alloc>
00274     inline void
00275     swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00276      unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00277     { __x.swap(__y); }
00278 
00279   template<typename _Key, typename _Tp, typename _Hash,
00280        typename _Pred, typename _Alloc>
00281     inline bool
00282     operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00283            const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00284     { return static_cast<const _GLIBCXX_STD_BASE&>(__x) == __y; }
00285 
00286   template<typename _Key, typename _Tp, typename _Hash,
00287        typename _Pred, typename _Alloc>
00288     inline bool
00289     operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00290            const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00291     { return !(__x == __y); }
00292 
00293 #undef _GLIBCXX_BASE
00294 #undef _GLIBCXX_STD_BASE
00295 #define _GLIBCXX_BASE unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>
00296 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE
00297 
00298   /// Class std::unordered_multimap wrapper with performance instrumentation.
00299   template<typename _Key, typename _Tp,
00300        typename _Hash = std::hash<_Key>,
00301        typename _Pred = std::equal_to<_Key>,
00302        typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
00303     class unordered_multimap
00304     : public _GLIBCXX_STD_BASE,
00305       public _Unordered_profile<unordered_multimap<_Key, _Tp,
00306                            _Hash, _Pred, _Alloc>,
00307                 false>
00308     {      
00309       typedef typename _GLIBCXX_STD_BASE _Base;
00310 
00311       _Base&
00312       _M_base() noexcept       { return *this; }
00313 
00314       const _Base&
00315       _M_base() const noexcept { return *this; }
00316 
00317     public:
00318       typedef typename _Base::size_type       size_type;
00319       typedef typename _Base::hasher          hasher;
00320       typedef typename _Base::key_equal       key_equal;
00321       typedef typename _Base::allocator_type  allocator_type;
00322       typedef typename _Base::key_type        key_type;
00323       typedef typename _Base::value_type      value_type;
00324       typedef typename _Base::difference_type difference_type;
00325       typedef typename _Base::reference       reference;
00326       typedef typename _Base::const_reference const_reference;
00327 
00328       typedef typename _Base::iterator iterator;
00329       typedef typename _Base::const_iterator const_iterator;
00330 
00331       explicit
00332       unordered_multimap(size_type __n = 10,
00333              const hasher& __hf = hasher(),
00334              const key_equal& __eql = key_equal(),
00335              const allocator_type& __a = allocator_type())
00336     : _Base(__n, __hf, __eql, __a)
00337       { }
00338 
00339       template<typename _InputIterator>
00340         unordered_multimap(_InputIterator __f, _InputIterator __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(__f, __l, __n, __hf, __eql, __a)
00346       { }
00347 
00348       unordered_multimap(const unordered_multimap&) = default;
00349 
00350       unordered_multimap(const _Base& __x)
00351     : _Base(__x)
00352       { }
00353 
00354       unordered_multimap(unordered_multimap&&) = default;
00355 
00356       explicit
00357       unordered_multimap(const allocator_type& __a)
00358     : _Base(__a)
00359       { }
00360 
00361       unordered_multimap(const unordered_multimap& __ummap,
00362              const allocator_type& __a)
00363     : _Base(__ummap._M_base(), __a)
00364       { }
00365 
00366       unordered_multimap(unordered_multimap&& __ummap,
00367              const allocator_type& __a)
00368     : _Base(std::move(__ummap._M_base()), __a)
00369       { }
00370 
00371       unordered_multimap(initializer_list<value_type> __l,
00372              size_type __n = 0,
00373              const hasher& __hf = hasher(),
00374              const key_equal& __eql = key_equal(),
00375              const allocator_type& __a = allocator_type())
00376       : _Base(__l, __n, __hf, __eql, __a)
00377       { }
00378 
00379       unordered_multimap&
00380       operator=(const unordered_multimap&) = default;
00381 
00382       unordered_multimap&
00383       operator=(unordered_multimap&&) = default;
00384 
00385       unordered_multimap&
00386       operator=(initializer_list<value_type> __l)
00387       {
00388     _M_base() = __l;
00389     return *this;
00390       }
00391 
00392       void
00393       clear() noexcept
00394       {
00395     __profcxx_hashtable_destruct(this, _Base::bucket_count(), 
00396                      _Base::size());
00397     this->_M_profile_destruct();
00398     _Base::clear();
00399       }
00400 
00401       template<typename... _Args>
00402     iterator
00403     emplace(_Args&&... __args)
00404     {
00405       size_type __old_size = _Base::bucket_count();
00406       iterator __res
00407         = _Base::emplace(std::forward<_Args>(__args)...);
00408       _M_profile_resize(__old_size);
00409       return __res;
00410     }
00411 
00412       template<typename... _Args>
00413     iterator
00414     emplace_hint(const_iterator __it, _Args&&... __args)
00415     {
00416       size_type __old_size = _Base::bucket_count();
00417       iterator __res
00418         = _Base::emplace_hint(__it, std::forward<_Args>(__args)...);
00419       _M_profile_resize(__old_size);
00420       return __res;
00421     }
00422 
00423       void
00424       insert(std::initializer_list<value_type> __l)
00425       { 
00426         size_type __old_size = _Base::bucket_count();
00427         _Base::insert(__l);
00428         _M_profile_resize(__old_size);
00429       }
00430 
00431       iterator
00432       insert(const value_type& __obj)
00433       {
00434         size_type __old_size = _Base::bucket_count();
00435         iterator __res = _Base::insert(__obj);
00436         _M_profile_resize(__old_size); 
00437         return __res;
00438       }
00439 
00440       iterator
00441       insert(const_iterator __iter, const value_type& __v)
00442       { 
00443         size_type __old_size = _Base::bucket_count(); 
00444         iterator __res = _Base::insert(__iter, __v);
00445         _M_profile_resize(__old_size); 
00446         return __res;
00447       }
00448 
00449       template<typename _Pair, typename = typename
00450            std::enable_if<std::is_constructible<value_type,
00451                             _Pair&&>::value>::type>
00452         iterator
00453         insert(_Pair&& __obj)
00454         {
00455       size_type __old_size = _Base::bucket_count();
00456       iterator __res = _Base::insert(std::forward<_Pair>(__obj));
00457       _M_profile_resize(__old_size); 
00458       return __res;
00459     }
00460 
00461       template<typename _Pair, typename = typename
00462            std::enable_if<std::is_constructible<value_type,
00463                             _Pair&&>::value>::type>
00464         iterator
00465         insert(const_iterator __iter, _Pair&& __v)
00466         {
00467       size_type __old_size = _Base::bucket_count(); 
00468       iterator __res = _Base::insert(__iter, std::forward<_Pair>(__v));
00469       _M_profile_resize(__old_size); 
00470       return __res;
00471     }
00472 
00473       template<typename _InputIter>
00474         void
00475         insert(_InputIter __first, _InputIter __last)
00476         {
00477       size_type __old_size = _Base::bucket_count(); 
00478       _Base::insert(__first, __last);
00479       _M_profile_resize(__old_size); 
00480     }
00481 
00482       void
00483       swap(unordered_multimap& __x)
00484       noexcept( noexcept(__x._M_base().swap(__x)) )
00485       { _Base::swap(__x._M_base()); }
00486 
00487       void
00488       rehash(size_type __n)
00489       {
00490         size_type __old_size = _Base::bucket_count();
00491         _Base::rehash(__n);
00492         _M_profile_resize(__old_size); 
00493       }
00494 
00495     private:
00496       void
00497       _M_profile_resize(size_type __old_size)
00498       {
00499     size_type __new_size = _Base::bucket_count();
00500         if (__old_size != __new_size)
00501           __profcxx_hashtable_resize(this, __old_size, __new_size);
00502       }
00503   };
00504 
00505   template<typename _Key, typename _Tp, typename _Hash,
00506        typename _Pred, typename _Alloc>
00507     inline void
00508     swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00509      unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00510     { __x.swap(__y); }
00511 
00512   template<typename _Key, typename _Tp, typename _Hash,
00513        typename _Pred, typename _Alloc>
00514     inline bool
00515     operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00516            const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00517     { return static_cast<const _GLIBCXX_STD_BASE&>(__x) == __y; }
00518 
00519   template<typename _Key, typename _Tp, typename _Hash,
00520        typename _Pred, typename _Alloc>
00521     inline bool
00522     operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00523            const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00524     { return !(__x == __y); }
00525 
00526 } // namespace __profile
00527 } // namespace std
00528 
00529 #undef _GLIBCXX_BASE
00530 #undef _GLIBCXX_STD_BASE
00531 
00532 #endif // C++11
00533 
00534 #endif