libstdc++
map.h
Go to the documentation of this file.
00001 // Profiling map 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/map.h
00025  *  This file is a GNU profile extension to the Standard C++ Library.
00026  */
00027 
00028 #ifndef _GLIBCXX_PROFILE_MAP_H
00029 #define _GLIBCXX_PROFILE_MAP_H 1
00030 
00031 #include <profile/base.h>
00032 #include <profile/ordered_base.h>
00033 
00034 namespace std _GLIBCXX_VISIBILITY(default)
00035 {
00036 namespace __profile
00037 {
00038   /// Class std::map wrapper with performance instrumentation.
00039   template<typename _Key, typename _Tp, typename _Compare = std::less<_Key>,
00040            typename _Allocator = std::allocator<std::pair<const _Key, _Tp> > >
00041     class map
00042     : public _GLIBCXX_STD_C::map<_Key, _Tp, _Compare, _Allocator>,
00043       public _Ordered_profile<map<_Key, _Tp, _Compare, _Allocator> >
00044     {
00045       typedef _GLIBCXX_STD_C::map<_Key, _Tp, _Compare, _Allocator> _Base;
00046 
00047       typedef typename _Base::iterator                  _Base_iterator;
00048       typedef typename _Base::const_iterator            _Base_const_iterator;
00049 
00050     public:
00051       // types:
00052       typedef _Key                                      key_type;
00053       typedef _Tp                                       mapped_type;
00054       typedef typename _Base::value_type                value_type;
00055       typedef _Compare                                  key_compare;
00056       typedef typename _Base::reference                 reference;
00057       typedef typename _Base::const_reference           const_reference;
00058 
00059       typedef __iterator_tracker<_Base_iterator, map>   iterator;
00060       typedef __iterator_tracker<_Base_const_iterator,
00061                                  map>                   const_iterator;
00062       typedef std::reverse_iterator<iterator>           reverse_iterator;
00063       typedef std::reverse_iterator<const_iterator>     const_reverse_iterator;
00064 
00065       typedef typename _Base::size_type                 size_type;
00066       typedef typename _Base::difference_type           difference_type;
00067 
00068       // 23.3.1.1 construct/copy/destroy:
00069 
00070 #if __cplusplus < 201103L
00071       map()
00072       : _Base() { }
00073       map(const map& __x)
00074         : _Base(__x) { }
00075       ~map()
00076       { }
00077 #else
00078       map() = default;
00079       map(const map&) = default;
00080       map(map&&) = default;
00081       ~map() = default;
00082 #endif
00083 
00084       explicit
00085       map(const _Compare& __comp,
00086           const _Allocator& __a = _Allocator())
00087       : _Base(__comp, __a) { }
00088 
00089 #if __cplusplus >= 201103L
00090       template<typename _InputIterator,
00091                typename = std::_RequireInputIter<_InputIterator>>
00092 #else
00093       template<typename _InputIterator>
00094 #endif
00095         map(_InputIterator __first, _InputIterator __last,
00096             const _Compare& __comp = _Compare(),
00097             const _Allocator& __a = _Allocator())
00098         : _Base(__first, __last, __comp, __a) { }
00099 
00100       map(const _Base& __x)
00101       : _Base(__x) { }
00102 
00103 #if __cplusplus >= 201103L
00104       map(initializer_list<value_type> __l,
00105           const _Compare& __c = _Compare(),
00106           const _Allocator& __a = _Allocator())
00107       : _Base(__l, __c, __a) { }
00108 
00109       explicit
00110       map(const _Allocator& __a)
00111       : _Base(__a) { }
00112 
00113       map(const map& __x, const _Allocator& __a)
00114       : _Base(__x, __a) { }
00115 
00116       map(map&& __x, const _Allocator& __a)
00117       noexcept( noexcept(_Base(std::move(__x), __a)) )
00118       : _Base(std::move(__x), __a) { }
00119 
00120       map(initializer_list<value_type> __l, const _Allocator& __a)
00121       : _Base(__l, __a) { }
00122 
00123       template<typename _InputIterator>
00124         map(_InputIterator __first, _InputIterator __last,
00125             const _Allocator& __a)
00126         : _Base(__first, __last, __a) { }
00127 #endif
00128 
00129 #if __cplusplus < 201103L
00130       map&
00131       operator=(const map& __x)
00132       {
00133         this->_M_profile_destruct();
00134         _M_base() = __x;
00135         this->_M_profile_construct();
00136         return *this;
00137       }
00138 #else
00139       map&
00140       operator=(const map&) = default;
00141 
00142       map&
00143       operator=(map&&) = default;
00144 
00145       map&
00146       operator=(initializer_list<value_type> __l)
00147       {
00148         this->_M_profile_destruct();
00149         _M_base() = __l;
00150         this->_M_profile_construct();
00151         return *this;
00152       }
00153 #endif
00154 
00155       // iterators
00156       iterator
00157       begin() _GLIBCXX_NOEXCEPT
00158       { return iterator(_Base::begin(), this); }
00159 
00160       const_iterator
00161       begin() const _GLIBCXX_NOEXCEPT
00162       { return const_iterator(_Base::begin(), this); }
00163 
00164       iterator
00165       end() _GLIBCXX_NOEXCEPT
00166       { return iterator(_Base::end(), this); }
00167 
00168       const_iterator
00169       end() const _GLIBCXX_NOEXCEPT
00170       { return const_iterator(_Base::end(), this); }
00171 
00172 #if __cplusplus >= 201103L
00173       const_iterator
00174       cbegin() const noexcept
00175       { return const_iterator(_Base::cbegin(), this); }
00176 
00177       const_iterator
00178       cend() const noexcept
00179       { return const_iterator(_Base::cend(), this); }
00180 #endif
00181 
00182       reverse_iterator
00183       rbegin() _GLIBCXX_NOEXCEPT
00184       {
00185         __profcxx_map2umap_invalidate(this->_M_map2umap_info);
00186         return reverse_iterator(end());
00187       }
00188 
00189       const_reverse_iterator
00190       rbegin() const _GLIBCXX_NOEXCEPT
00191       {
00192         __profcxx_map2umap_invalidate(this->_M_map2umap_info);
00193         return const_reverse_iterator(end());
00194       }
00195 
00196       reverse_iterator
00197       rend() _GLIBCXX_NOEXCEPT
00198       {
00199         __profcxx_map2umap_invalidate(this->_M_map2umap_info);
00200         return reverse_iterator(begin());
00201       }
00202 
00203       const_reverse_iterator
00204       rend() const _GLIBCXX_NOEXCEPT
00205       {
00206         __profcxx_map2umap_invalidate(this->_M_map2umap_info);
00207         return const_reverse_iterator(begin());
00208       }
00209 
00210 #if __cplusplus >= 201103L
00211       const_reverse_iterator
00212       crbegin() const noexcept
00213       {
00214         __profcxx_map2umap_invalidate(this->_M_map2umap_info);
00215         return const_reverse_iterator(cend());
00216       }
00217 
00218       const_reverse_iterator
00219       crend() const noexcept
00220       {
00221         __profcxx_map2umap_invalidate(this->_M_map2umap_info);
00222         return const_reverse_iterator(cbegin());
00223       }
00224 #endif
00225 
00226       // 23.3.1.2 element access:
00227       mapped_type&
00228       operator[](const key_type& __k)
00229       {
00230         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
00231         return _Base::operator[](__k);
00232       }
00233 
00234 #if __cplusplus >= 201103L
00235       mapped_type&
00236       operator[](key_type&& __k)
00237       {
00238         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
00239         return _Base::operator[](std::move(__k));
00240       }
00241 #endif
00242 
00243       mapped_type&
00244       at(const key_type& __k)
00245       {
00246         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
00247         return _Base::at(__k);
00248       }
00249 
00250       const mapped_type&
00251       at(const key_type& __k) const
00252       {
00253         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
00254         return _Base::at(__k);
00255       }
00256 
00257       // modifiers:
00258 #if __cplusplus >= 201103L
00259       template<typename... _Args>
00260         std::pair<iterator, bool>
00261         emplace(_Args&&... __args)
00262         {
00263           // The cost is the same whether or not the element is inserted so we
00264           // always report insertion of 1 element.
00265           __profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1);
00266           auto __base_ret = _Base::emplace(std::forward<_Args>(__args)...);
00267           return std::make_pair(iterator(__base_ret.first, this),
00268                                 __base_ret.second);
00269         }
00270 
00271       template<typename... _Args>
00272         iterator
00273         emplace_hint(const_iterator __pos, _Args&&... __args)
00274         {
00275           auto size_before = this->size();
00276           auto __res
00277             = _Base::emplace_hint(__pos.base(), std::forward<_Args>(__args)...);
00278           __profcxx_map2umap_insert(this->_M_map2umap_info,
00279                 size_before, _M_hint_used(__pos.base(), __res) ? 0 : 1);
00280           return iterator(__res, this);
00281         }
00282 #endif
00283 
00284       std::pair<iterator, bool>
00285       insert(const value_type& __x)
00286       {
00287         __profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1);
00288         std::pair<_Base_iterator, bool> __base_ret = _Base::insert(__x);
00289         return std::make_pair(iterator(__base_ret.first, this),
00290                               __base_ret.second);
00291       }
00292 
00293 #if __cplusplus >= 201103L
00294       template<typename _Pair, typename = typename
00295                std::enable_if<std::is_constructible<value_type,
00296                                                     _Pair&&>::value>::type>
00297         std::pair<iterator, bool>
00298         insert(_Pair&& __x)
00299         {
00300           __profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1);
00301           auto __base_ret= _Base::insert(std::forward<_Pair>(__x));
00302           return std::make_pair(iterator(__base_ret.first, this),
00303                                 __base_ret.second);
00304         }
00305 #endif
00306 
00307 #if __cplusplus >= 201103L
00308       void
00309       insert(std::initializer_list<value_type> __list)
00310       { insert(__list.begin(), __list.end()); }
00311 #endif
00312 
00313       iterator
00314 #if __cplusplus >= 201103L
00315       insert(const_iterator __pos, const value_type& __x)
00316 #else
00317       insert(iterator __pos, const value_type& __x)
00318 #endif
00319       {
00320         size_type size_before = this->size();
00321         _Base_iterator __res = _Base::insert(__pos.base(), __x);
00322         
00323         __profcxx_map2umap_insert(this->_M_map2umap_info,
00324                 size_before, _M_hint_used(__pos.base(), __res) ? 0 : 1);
00325         return iterator(__res, this);
00326       }
00327 
00328 #if __cplusplus >= 201103L
00329       template<typename _Pair, typename = typename
00330                std::enable_if<std::is_constructible<value_type,
00331                                                     _Pair&&>::value>::type>
00332         iterator
00333         insert(const_iterator __pos, _Pair&& __x)
00334         {
00335           size_type size_before = this->size();
00336           auto __res = _Base::insert(__pos.base(), std::forward<_Pair>(__x));
00337         
00338           __profcxx_map2umap_insert(this->_M_map2umap_info,
00339                 size_before, _M_hint_used(__pos.base(), __res) ? 0 : 1);
00340           return iterator(__res, this);
00341       }
00342 #endif
00343 
00344       template<typename _InputIterator>
00345         void
00346         insert(_InputIterator __first, _InputIterator __last)
00347         {
00348           for (; __first != __last; ++__first)
00349             insert(*__first);
00350         }
00351 
00352 #if __cplusplus >= 201103L
00353       iterator
00354       erase(const_iterator __pos)
00355       {
00356         __profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1);
00357         return iterator(_Base::erase(__pos.base()), this);
00358       }
00359 
00360       iterator
00361       erase(iterator __pos)
00362       {
00363         __profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1);
00364         return iterator(_Base::erase(__pos.base()), this);
00365       }
00366 #else
00367       void
00368       erase(iterator __pos)
00369       {
00370         __profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1);
00371         _Base::erase(__pos.base());
00372       }
00373 #endif
00374 
00375       size_type
00376       erase(const key_type& __x)
00377       {
00378         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
00379         __profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1);
00380         return _Base::erase(__x);
00381       }
00382 
00383 #if __cplusplus >= 201103L
00384       iterator
00385       erase(const_iterator __first, const_iterator __last)
00386       {
00387         if (__first != __last)
00388           {
00389             iterator __ret;
00390             for (; __first != __last;)
00391               __ret = erase(__first++);
00392             return __ret;
00393           }
00394         else
00395           return iterator(_Base::erase(__first.base(), __last.base()), this);
00396       }
00397 #else
00398       void
00399       erase(iterator __first, iterator __last)
00400       {
00401         for (; __first != __last;)
00402           erase(__first++);
00403       }
00404 #endif
00405 
00406       void
00407       swap(map& __x)
00408 #if __cplusplus >= 201103L
00409         noexcept( noexcept(declval<_Base>().swap(__x)) )
00410 #endif
00411       {
00412         _Base::swap(__x);
00413         this->_M_swap(__x);
00414       }
00415 
00416       void
00417       clear() _GLIBCXX_NOEXCEPT
00418       {
00419         this->_M_profile_destruct();
00420         _Base::clear();
00421         this->_M_profile_construct();
00422       }
00423 
00424       // 23.3.1.3 map operations:
00425       iterator
00426       find(const key_type& __x)
00427       {
00428         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
00429         return iterator(_Base::find(__x), this);
00430       }
00431 
00432       const_iterator
00433       find(const key_type& __x) const
00434       {
00435         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
00436         return const_iterator(_Base::find(__x), this);
00437       }
00438 
00439       size_type
00440       count(const key_type& __x) const
00441       {
00442         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
00443         return _Base::count(__x);
00444       }
00445 
00446       iterator
00447       lower_bound(const key_type& __x)
00448       {
00449         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
00450         __profcxx_map2umap_invalidate(this->_M_map2umap_info);
00451         return iterator(_Base::lower_bound(__x), this);
00452       }
00453 
00454       const_iterator
00455       lower_bound(const key_type& __x) const
00456       {
00457         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
00458         __profcxx_map2umap_invalidate(this->_M_map2umap_info);
00459         return const_iterator(_Base::lower_bound(__x), this);
00460       }
00461 
00462       iterator
00463       upper_bound(const key_type& __x)
00464       {
00465         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
00466         __profcxx_map2umap_invalidate(this->_M_map2umap_info);
00467         return iterator(_Base::upper_bound(__x), this);
00468       }
00469 
00470       const_iterator
00471       upper_bound(const key_type& __x) const
00472       {
00473         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
00474         __profcxx_map2umap_invalidate(this->_M_map2umap_info);
00475         return const_iterator(_Base::upper_bound(__x), this);
00476       }
00477 
00478       std::pair<iterator,iterator>
00479       equal_range(const key_type& __x)
00480       {
00481         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
00482         std::pair<_Base_iterator, _Base_iterator> __base_ret
00483           = _Base::equal_range(__x);
00484         return std::make_pair(iterator(__base_ret.first, this),
00485                               iterator(__base_ret.second, this));
00486       }
00487 
00488       std::pair<const_iterator,const_iterator>
00489       equal_range(const key_type& __x) const
00490       {
00491         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
00492         std::pair<_Base_const_iterator, _Base_const_iterator> __base_ret
00493           = _Base::equal_range(__x);
00494         return std::make_pair(const_iterator(__base_ret.first, this),
00495                               const_iterator(__base_ret.second, this));
00496       }
00497 
00498       _Base&
00499       _M_base() _GLIBCXX_NOEXCEPT       { return *this; }
00500 
00501       const _Base&
00502       _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
00503 
00504     private:
00505       /** If hint is used we consider that the map and unordered_map
00506        * operations have equivalent insertion cost so we do not update metrics
00507        * about it.
00508        * Note that to find out if hint has been used is libstdc++
00509        * implementation dependent.
00510        */
00511       bool
00512       _M_hint_used(_Base_const_iterator __hint, _Base_iterator __res)
00513       {
00514         return (__hint == __res
00515                 || (__hint == _M_base().end() && ++__res == _M_base().end())
00516                 || (__hint != _M_base().end() && (++__hint == __res
00517                                                   || ++__res == --__hint)));
00518       }
00519 
00520 
00521       template<typename _K1, typename _T1, typename _C1, typename _A1>
00522         friend bool
00523         operator==(const map<_K1, _T1, _C1, _A1>&,
00524                    const map<_K1, _T1, _C1, _A1>&);
00525 
00526       template<typename _K1, typename _T1, typename _C1, typename _A1>
00527         friend bool
00528         operator<(const map<_K1, _T1, _C1, _A1>&,
00529                   const map<_K1, _T1, _C1, _A1>&);      
00530     };
00531 
00532   template<typename _Key, typename _Tp,
00533            typename _Compare, typename _Allocator>
00534     inline bool
00535     operator==(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
00536                const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
00537     {
00538       __profcxx_map2umap_invalidate(__lhs._M_map2umap_info);
00539       __profcxx_map2umap_invalidate(__rhs._M_map2umap_info);
00540       return __lhs._M_base() == __rhs._M_base();
00541     }
00542 
00543   template<typename _Key, typename _Tp,
00544            typename _Compare, typename _Allocator>
00545     inline bool
00546     operator<(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
00547               const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
00548     {
00549       __profcxx_map2umap_invalidate(__lhs._M_map2umap_info);
00550       __profcxx_map2umap_invalidate(__rhs._M_map2umap_info);
00551       return __lhs._M_base() < __rhs._M_base();
00552     }
00553 
00554   template<typename _Key, typename _Tp,
00555            typename _Compare, typename _Allocator>
00556     inline bool
00557     operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
00558                const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
00559     { return !(__lhs == __rhs); }
00560 
00561   template<typename _Key, typename _Tp,
00562            typename _Compare, typename _Allocator>
00563     inline bool
00564     operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
00565                const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
00566     { return !(__rhs < __lhs); }
00567 
00568   template<typename _Key, typename _Tp,
00569            typename _Compare, typename _Allocator>
00570     inline bool
00571     operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
00572                const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
00573     { return !(__lhs < __rhs); }
00574 
00575   template<typename _Key, typename _Tp,
00576            typename _Compare, typename _Allocator>
00577     inline bool
00578     operator>(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
00579               const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
00580     { return __rhs < __lhs; }
00581 
00582   template<typename _Key, typename _Tp,
00583            typename _Compare, typename _Allocator>
00584     inline void
00585     swap(map<_Key, _Tp, _Compare, _Allocator>& __lhs,
00586          map<_Key, _Tp, _Compare, _Allocator>& __rhs)
00587     { __lhs.swap(__rhs); }
00588 
00589 } // namespace __profile
00590 } // namespace std
00591 
00592 #endif