libstdc++
unordered_map
Go to the documentation of this file.
00001 // Profiling unordered_map/unordered_multimap implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2009-2015 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     { __x.swap(__y); }
00303 
00304   template<typename _Key, typename _Tp, typename _Hash,
00305            typename _Pred, typename _Alloc>
00306     inline bool
00307     operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00308                const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00309     { return static_cast<const _GLIBCXX_STD_BASE&>(__x) == __y; }
00310 
00311   template<typename _Key, typename _Tp, typename _Hash,
00312            typename _Pred, typename _Alloc>
00313     inline bool
00314     operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00315                const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00316     { return !(__x == __y); }
00317 
00318 #undef _GLIBCXX_BASE
00319 #undef _GLIBCXX_STD_BASE
00320 #define _GLIBCXX_BASE unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>
00321 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE
00322 
00323   /// Class std::unordered_multimap wrapper with performance instrumentation.
00324   template<typename _Key, typename _Tp,
00325            typename _Hash = std::hash<_Key>,
00326            typename _Pred = std::equal_to<_Key>,
00327            typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
00328     class unordered_multimap
00329     : public _GLIBCXX_STD_BASE,
00330       public _Unordered_profile<unordered_multimap<_Key, _Tp,
00331                                                    _Hash, _Pred, _Alloc>,
00332                                 false>
00333     {
00334       typedef typename _GLIBCXX_STD_BASE _Base;
00335 
00336       _Base&
00337       _M_base() noexcept        { return *this; }
00338 
00339       const _Base&
00340       _M_base() const noexcept  { return *this; }
00341 
00342     public:
00343       typedef typename _Base::size_type         size_type;
00344       typedef typename _Base::hasher            hasher;
00345       typedef typename _Base::key_equal         key_equal;
00346       typedef typename _Base::allocator_type    allocator_type;
00347       typedef typename _Base::key_type          key_type;
00348       typedef typename _Base::value_type        value_type;
00349       typedef typename _Base::difference_type   difference_type;
00350       typedef typename _Base::reference         reference;
00351       typedef typename _Base::const_reference   const_reference;
00352 
00353       typedef typename _Base::iterator          iterator;
00354       typedef typename _Base::const_iterator    const_iterator;
00355 
00356       unordered_multimap() = default;
00357 
00358       explicit
00359       unordered_multimap(size_type __n,
00360                          const hasher& __hf = hasher(),
00361                          const key_equal& __eql = key_equal(),
00362                          const allocator_type& __a = allocator_type())
00363       : _Base(__n, __hf, __eql, __a) { }
00364 
00365       template<typename _InputIterator>
00366         unordered_multimap(_InputIterator __f, _InputIterator __l,
00367                            size_type __n = 0,
00368                            const hasher& __hf = hasher(),
00369                            const key_equal& __eql = key_equal(),
00370                            const allocator_type& __a = allocator_type())
00371         : _Base(__f, __l, __n, __hf, __eql, __a) { }
00372 
00373       unordered_multimap(const unordered_multimap&) = default;
00374 
00375       unordered_multimap(const _Base& __x)
00376       : _Base(__x) { }
00377 
00378       unordered_multimap(unordered_multimap&&) = default;
00379 
00380       explicit
00381       unordered_multimap(const allocator_type& __a)
00382       : _Base(__a) { }
00383 
00384       unordered_multimap(const unordered_multimap& __ummap,
00385                          const allocator_type& __a)
00386       : _Base(__ummap._M_base(), __a) { }
00387 
00388       unordered_multimap(unordered_multimap&& __ummap,
00389                          const allocator_type& __a)
00390       : _Base(std::move(__ummap._M_base()), __a) { }
00391 
00392       unordered_multimap(initializer_list<value_type> __l,
00393                          size_type __n = 0,
00394                          const hasher& __hf = hasher(),
00395                          const key_equal& __eql = key_equal(),
00396                          const allocator_type& __a = allocator_type())
00397       : _Base(__l, __n, __hf, __eql, __a) { }
00398 
00399       unordered_multimap(size_type __n, const allocator_type& __a)
00400       : unordered_multimap(__n, hasher(), key_equal(), __a)
00401       { }
00402 
00403       unordered_multimap(size_type __n, const hasher& __hf,
00404                          const allocator_type& __a)
00405       : unordered_multimap(__n, __hf, key_equal(), __a)
00406       { }
00407 
00408       template<typename _InputIterator>
00409         unordered_multimap(_InputIterator __first, _InputIterator __last,
00410                            size_type __n,
00411                            const allocator_type& __a)
00412           : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a)
00413         { }
00414 
00415       template<typename _InputIterator>
00416         unordered_multimap(_InputIterator __first, _InputIterator __last,
00417                            size_type __n, const hasher& __hf,
00418                            const allocator_type& __a)
00419           : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a)
00420         { }
00421 
00422       unordered_multimap(initializer_list<value_type> __l,
00423                          size_type __n,
00424                          const allocator_type& __a)
00425         : unordered_multimap(__l, __n, hasher(), key_equal(), __a)
00426       { }
00427 
00428       unordered_multimap(initializer_list<value_type> __l,
00429                          size_type __n, const hasher& __hf,
00430                          const allocator_type& __a)
00431         : unordered_multimap(__l, __n, __hf, key_equal(), __a)
00432       { }
00433 
00434       unordered_multimap&
00435       operator=(const unordered_multimap&) = default;
00436 
00437       unordered_multimap&
00438       operator=(unordered_multimap&&) = default;
00439 
00440       unordered_multimap&
00441       operator=(initializer_list<value_type> __l)
00442       {
00443         this->_M_profile_destruct();
00444         _M_base() = __l;
00445         this->_M_profile_construct();
00446         return *this;
00447       }
00448 
00449       void
00450       clear() noexcept
00451       {
00452         this->_M_profile_destruct();
00453         _Base::clear();
00454         this->_M_profile_construct();
00455       }
00456 
00457       template<typename... _Args>
00458         iterator
00459         emplace(_Args&&... __args)
00460         {
00461           size_type __old_size = _Base::bucket_count();
00462           iterator __res
00463             = _Base::emplace(std::forward<_Args>(__args)...);
00464           this->_M_profile_resize(__old_size);
00465           return __res;
00466         }
00467 
00468       template<typename... _Args>
00469         iterator
00470         emplace_hint(const_iterator __it, _Args&&... __args)
00471         {
00472           size_type __old_size = _Base::bucket_count();
00473           iterator __res
00474             = _Base::emplace_hint(__it, std::forward<_Args>(__args)...);
00475           this->_M_profile_resize(__old_size);
00476           return __res;
00477         }
00478 
00479       void
00480       insert(std::initializer_list<value_type> __l)
00481       {
00482         size_type __old_size = _Base::bucket_count();
00483         _Base::insert(__l);
00484         this->_M_profile_resize(__old_size);
00485       }
00486 
00487       iterator
00488       insert(const value_type& __obj)
00489       {
00490         size_type __old_size = _Base::bucket_count();
00491         iterator __res = _Base::insert(__obj);
00492         this->_M_profile_resize(__old_size);
00493         return __res;
00494       }
00495 
00496       iterator
00497       insert(const_iterator __iter, const value_type& __v)
00498       {
00499         size_type __old_size = _Base::bucket_count();
00500         iterator __res = _Base::insert(__iter, __v);
00501         this->_M_profile_resize(__old_size);
00502         return __res;
00503       }
00504 
00505       template<typename _Pair, typename = typename
00506                std::enable_if<std::is_constructible<value_type,
00507                                                     _Pair&&>::value>::type>
00508         iterator
00509         insert(_Pair&& __obj)
00510         {
00511           size_type __old_size = _Base::bucket_count();
00512           iterator __res = _Base::insert(std::forward<_Pair>(__obj));
00513           this->_M_profile_resize(__old_size);
00514           return __res;
00515         }
00516 
00517       template<typename _Pair, typename = typename
00518                std::enable_if<std::is_constructible<value_type,
00519                                                     _Pair&&>::value>::type>
00520         iterator
00521         insert(const_iterator __iter, _Pair&& __v)
00522         {
00523           size_type __old_size = _Base::bucket_count();
00524           iterator __res = _Base::insert(__iter, std::forward<_Pair>(__v));
00525           this->_M_profile_resize(__old_size);
00526           return __res;
00527         }
00528 
00529       template<typename _InputIter>
00530         void
00531         insert(_InputIter __first, _InputIter __last)
00532         {
00533           size_type __old_size = _Base::bucket_count();
00534           _Base::insert(__first, __last);
00535           this->_M_profile_resize(__old_size);
00536         }
00537 
00538       void
00539       swap(unordered_multimap& __x)
00540       noexcept( noexcept(__x._M_base().swap(__x)) )
00541       {
00542         _Base::swap(__x._M_base());
00543         this->_M_swap(__x);
00544       }
00545 
00546       void
00547       rehash(size_type __n)
00548       {
00549         size_type __old_size = _Base::bucket_count();
00550         _Base::rehash(__n);
00551         this->_M_profile_resize(__old_size);
00552       }
00553   };
00554 
00555   template<typename _Key, typename _Tp, typename _Hash,
00556            typename _Pred, typename _Alloc>
00557     inline void
00558     swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00559          unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00560     { __x.swap(__y); }
00561 
00562   template<typename _Key, typename _Tp, typename _Hash,
00563            typename _Pred, typename _Alloc>
00564     inline bool
00565     operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00566                const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00567     { return static_cast<const _GLIBCXX_STD_BASE&>(__x) == __y; }
00568 
00569   template<typename _Key, typename _Tp, typename _Hash,
00570            typename _Pred, typename _Alloc>
00571     inline bool
00572     operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00573                const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00574     { return !(__x == __y); }
00575 
00576 } // namespace __profile
00577 } // namespace std
00578 
00579 #undef _GLIBCXX_BASE
00580 #undef _GLIBCXX_STD_BASE
00581 
00582 #endif // C++11
00583 
00584 #endif