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