libstdc++
multimap.h
Go to the documentation of this file.
00001 // Profiling 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 and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 /** @file profile/multimap.h
00026  *  This file is a GNU profile extension to the Standard C++ Library.
00027  */
00028 
00029 #ifndef _GLIBCXX_PROFILE_MULTIMAP_H
00030 #define _GLIBCXX_PROFILE_MULTIMAP_H 1
00031 
00032 #include <profile/base.h>
00033 #include <profile/ordered_base.h>
00034 
00035 namespace std _GLIBCXX_VISIBILITY(default)
00036 {
00037 namespace __profile
00038 {
00039   /// Class std::multimap wrapper with performance instrumentation.
00040   template<typename _Key, typename _Tp, typename _Compare = std::less<_Key>,
00041            typename _Allocator = std::allocator<std::pair<const _Key, _Tp> > >
00042     class multimap
00043     : public _GLIBCXX_STD_C::multimap<_Key, _Tp, _Compare, _Allocator>,
00044       public _Ordered_profile<map<_Key, _Tp, _Compare, _Allocator> >
00045     {
00046       typedef _GLIBCXX_STD_C::multimap<_Key, _Tp, _Compare, _Allocator> _Base;
00047 
00048       typedef typename _Base::iterator                  _Base_iterator;
00049       typedef typename _Base::const_iterator            _Base_const_iterator;
00050 
00051     public:
00052       // types:
00053       typedef _Key                                      key_type;
00054       typedef _Tp                                       mapped_type;
00055       typedef std::pair<const _Key, _Tp>                value_type;
00056       typedef _Compare                                  key_compare;
00057       typedef typename _Base::reference                 reference;
00058       typedef typename _Base::const_reference           const_reference;
00059 
00060       typedef __iterator_tracker<_Base_iterator,
00061                                  multimap>              iterator;
00062       typedef __iterator_tracker<_Base_const_iterator,
00063                                  multimap>              const_iterator;
00064       typedef std::reverse_iterator<iterator>           reverse_iterator;
00065       typedef std::reverse_iterator<const_iterator>     const_reverse_iterator;
00066 
00067       typedef typename _Base::size_type                 size_type;
00068       typedef typename _Base::difference_type           difference_type;
00069 
00070       // 23.3.1.1 construct/copy/destroy:
00071 
00072 #if __cplusplus < 201103L
00073       multimap()
00074       : _Base() { }
00075       multimap(const multimap& __x)
00076       : _Base(__x) { }
00077       ~multimap() { }
00078 #else
00079       multimap() = default;
00080       multimap(const multimap&) = default;
00081       multimap(multimap&&) = default;
00082       ~multimap() = default;
00083 #endif
00084 
00085       explicit multimap(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         multimap(_InputIterator __first, _InputIterator __last,
00096                  const _Compare& __comp = _Compare(),
00097                  const _Allocator& __a = _Allocator())
00098         : _Base(__first, __last, __comp, __a) { }
00099 
00100 #if __cplusplus >= 201103L
00101       multimap(initializer_list<value_type> __l,
00102                const _Compare& __c = _Compare(),
00103                const _Allocator& __a = _Allocator())
00104       : _Base(__l, __c, __a) { }
00105 
00106       explicit
00107       multimap(const _Allocator& __a)
00108       : _Base(__a) { }
00109 
00110       multimap(const multimap& __x, const _Allocator& __a)
00111       : _Base(__x, __a) { }
00112 
00113       multimap(multimap&& __x, const _Allocator& __a)
00114       noexcept( noexcept(_Base(std::move(__x), __a)) )
00115       : _Base(std::move(__x), __a) { }
00116 
00117       multimap(initializer_list<value_type> __l, const _Allocator& __a)
00118       : _Base(__l, __a) { }
00119 
00120       template<typename _InputIterator>
00121         multimap(_InputIterator __first, _InputIterator __last,
00122                  const _Allocator& __a)
00123         : _Base(__first, __last, __a) { }
00124 #endif
00125 
00126       multimap(const _Base& __x)
00127       : _Base(__x) { }
00128 
00129 #if __cplusplus < 201103L
00130       multimap&
00131       operator=(const multimap& __x)
00132       {
00133         this->_M_profile_destruct();
00134         _M_base() = __x;
00135         this->_M_profile_construct();
00136         return *this;
00137       }
00138 #else
00139       multimap&
00140       operator=(const multimap&) = default;
00141 
00142       multimap&
00143       operator=(multimap&&) = default;
00144 
00145       multimap&
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       // modifiers:
00227 #if __cplusplus >= 201103L
00228       template<typename... _Args>
00229         iterator
00230         emplace(_Args&&... __args)
00231         {
00232           __profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1);
00233           return iterator(_Base::emplace(std::forward<_Args>(__args)...), this);
00234         }
00235 
00236       template<typename... _Args>
00237         iterator
00238         emplace_hint(const_iterator __pos, _Args&&... __args)
00239         {
00240           auto size_before = this->size();
00241           auto __res
00242             = _Base::emplace_hint(__pos.base(), std::forward<_Args>(__args)...);
00243           __profcxx_map2umap_insert(this->_M_map2umap_info,
00244                 size_before, _M_hint_used(__pos.base(), __res) ? 0 : 1);
00245           return iterator(__res, this);
00246         }
00247 #endif
00248 
00249       iterator
00250       insert(const value_type& __x)
00251       {
00252         __profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1);
00253         return iterator(_Base::insert(__x), this);
00254       }
00255 
00256 #if __cplusplus >= 201103L
00257       template<typename _Pair, typename = typename
00258                std::enable_if<std::is_constructible<value_type,
00259                                                     _Pair&&>::value>::type>
00260         iterator
00261         insert(_Pair&& __x)
00262         {
00263           __profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1);
00264           return iterator(_Base::insert(std::forward<_Pair>(__x)), this);
00265         }
00266 #endif
00267 
00268 #if __cplusplus >= 201103L
00269       void
00270       insert(std::initializer_list<value_type> __list)
00271       { insert(__list.begin(), __list.end()); }
00272 #endif
00273 
00274       iterator
00275 #if __cplusplus >= 201103L
00276       insert(const_iterator __pos, const value_type& __x)
00277 #else
00278       insert(iterator __pos, const value_type& __x)
00279 #endif
00280       {
00281         size_type size_before = this->size();
00282         _Base_iterator __res = _Base::insert(__pos.base(), __x);
00283         __profcxx_map2umap_insert(this->_M_map2umap_info,
00284                 size_before, _M_hint_used(__pos.base(), __res) ? 0 : 1);
00285         return iterator(__res, this);
00286       }
00287 
00288 #if __cplusplus >= 201103L
00289       template<typename _Pair, typename = typename
00290                std::enable_if<std::is_constructible<value_type,
00291                                                     _Pair&&>::value>::type>
00292         iterator
00293         insert(const_iterator __pos, _Pair&& __x)
00294         {
00295           size_type size_before = this->size();
00296           auto __res = _Base::insert(__pos.base(), std::forward<_Pair>(__x));
00297           __profcxx_map2umap_insert(this->_M_map2umap_info,
00298                 size_before, _M_hint_used(__pos.base(), __res) ? 0 : 1);
00299           return iterator(__res, this);
00300         }
00301 #endif
00302 
00303       template<typename _InputIterator>
00304         void
00305         insert(_InputIterator __first, _InputIterator __last)
00306         {
00307           for (; __first != __last; ++__first)
00308             insert(*__first);
00309         }
00310 
00311 #if __cplusplus >= 201103L
00312       iterator
00313       erase(const_iterator __pos)
00314       {
00315         __profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1);
00316         return iterator(_Base::erase(__pos.base()), this);
00317       }
00318 
00319       iterator
00320       erase(iterator __pos)
00321       {
00322         __profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1);
00323         return iterator(_Base::erase(__pos.base()), this);
00324       }
00325 #else
00326       void
00327       erase(iterator __pos)
00328       {
00329         __profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1);
00330         _Base::erase(__pos.base());
00331       }
00332 #endif
00333 
00334       size_type
00335       erase(const key_type& __x)
00336       {
00337         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
00338         __profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1);
00339         return _Base::erase(__x);
00340       }
00341 
00342 #if __cplusplus >= 201103L
00343       iterator
00344       erase(const_iterator __first, const_iterator __last)
00345       {
00346         if (__first != __last)
00347           {
00348             iterator __ret;
00349             for (; __first != __last;)
00350               __ret = erase(__first++);
00351             return __ret;
00352           }
00353         else
00354           return iterator(_Base::erase(__first.base(), __last.base()), this);
00355       }
00356 #else
00357       void
00358       erase(iterator __first, iterator __last)
00359       {
00360         for (; __first != __last;)
00361           erase(__first++);
00362       }
00363 #endif
00364 
00365       void
00366       swap(multimap& __x)
00367 #if __cplusplus >= 201103L
00368         noexcept( noexcept(declval<_Base>().swap(__x)) )
00369 #endif
00370       {
00371         std::swap(this->_M_map2umap_info, __x._M_map2umap_info);
00372         _Base::swap(__x);
00373       }
00374  
00375       void
00376       clear() _GLIBCXX_NOEXCEPT
00377       {
00378         this->_M_profile_destruct();
00379         _Base::clear();
00380         this->_M_profile_construct();
00381       }
00382 
00383       // 23.3.1.3 multimap operations:
00384       iterator
00385       find(const key_type& __x)
00386       {
00387         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
00388         return iterator(_Base::find(__x), this);
00389       }
00390 
00391       const_iterator
00392       find(const key_type& __x) const
00393       {
00394         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
00395         return const_iterator(_Base::find(__x), this);
00396       }
00397 
00398       size_type
00399       count(const key_type& __x) const
00400       {
00401         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
00402         return _Base::count(__x);
00403       }
00404 
00405       iterator
00406       lower_bound(const key_type& __x)
00407       {
00408         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
00409         __profcxx_map2umap_invalidate(this->_M_map2umap_info);
00410         return iterator(_Base::lower_bound(__x), this);
00411       }
00412 
00413       const_iterator
00414       lower_bound(const key_type& __x) const
00415       {
00416         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
00417         __profcxx_map2umap_invalidate(this->_M_map2umap_info);
00418         return const_iterator(_Base::lower_bound(__x), this);
00419       }
00420 
00421       iterator
00422       upper_bound(const key_type& __x)
00423       {
00424         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
00425         __profcxx_map2umap_invalidate(this->_M_map2umap_info);
00426         return iterator(_Base::upper_bound(__x), this);
00427       }
00428 
00429       const_iterator
00430       upper_bound(const key_type& __x) const
00431       {
00432         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
00433         __profcxx_map2umap_invalidate(this->_M_map2umap_info);
00434         return const_iterator(_Base::upper_bound(__x), this);
00435       }
00436 
00437       std::pair<iterator,iterator>
00438       equal_range(const key_type& __x)
00439       {
00440         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
00441         std::pair<_Base_iterator, _Base_iterator> __base_ret
00442           = _Base::equal_range(__x);
00443         return std::make_pair(iterator(__base_ret.first, this),
00444                               iterator(__base_ret.second, this));
00445       }
00446 
00447       std::pair<const_iterator,const_iterator>
00448       equal_range(const key_type& __x) const
00449       {
00450         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
00451         std::pair<_Base_const_iterator, _Base_const_iterator> __base_ret
00452           = _Base::equal_range(__x);
00453         return std::make_pair(const_iterator(__base_ret.first, this),
00454                               const_iterator(__base_ret.second, this));
00455       }
00456 
00457       _Base&
00458       _M_base() _GLIBCXX_NOEXCEPT       { return *this; }
00459 
00460       const _Base&
00461       _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
00462 
00463     private:
00464       /** If hint is used we consider that the map and unordered_map
00465        * operations have equivalent insertion cost so we do not update metrics
00466        * about it.
00467        * Note that to find out if hint has been used is libstdc++
00468        * implementation dependent.
00469        */
00470       bool
00471       _M_hint_used(_Base_const_iterator __hint, _Base_iterator __res)
00472       {
00473         return (__hint == __res
00474                 || (__hint == _M_base().end() && ++__res == _M_base().end())
00475                 || (__hint != _M_base().end() && (++__hint == __res
00476                                                   || ++__res == --__hint)));
00477       }
00478 
00479       template<typename _K1, typename _T1, typename _C1, typename _A1>
00480         friend bool
00481         operator==(const multimap<_K1, _T1, _C1, _A1>&,
00482                    const multimap<_K1, _T1, _C1, _A1>&);
00483 
00484       template<typename _K1, typename _T1, typename _C1, typename _A1>
00485         friend bool
00486         operator<(const multimap<_K1, _T1, _C1, _A1>&,
00487                   const multimap<_K1, _T1, _C1, _A1>&);
00488     };
00489 
00490   template<typename _Key, typename _Tp,
00491            typename _Compare, typename _Allocator>
00492     inline bool
00493     operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
00494                const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
00495     {
00496       __profcxx_map2umap_invalidate(__lhs._M_map2umap_info);
00497       __profcxx_map2umap_invalidate(__rhs._M_map2umap_info);
00498       return __lhs._M_base() == __rhs._M_base();
00499     }
00500 
00501   template<typename _Key, typename _Tp,
00502            typename _Compare, typename _Allocator>
00503     inline bool
00504     operator<(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
00505               const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
00506     {
00507       __profcxx_map2umap_invalidate(__lhs._M_map2umap_info);
00508       __profcxx_map2umap_invalidate(__rhs._M_map2umap_info);
00509       return __lhs._M_base() < __rhs._M_base();
00510     }
00511 
00512   template<typename _Key, typename _Tp,
00513            typename _Compare, typename _Allocator>
00514     inline bool
00515     operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
00516                const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
00517     { return !(__lhs == __rhs); }
00518 
00519   template<typename _Key, typename _Tp,
00520            typename _Compare, typename _Allocator>
00521     inline bool
00522     operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
00523                const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
00524     { return !(__rhs < __lhs); }
00525 
00526   template<typename _Key, typename _Tp,
00527            typename _Compare, typename _Allocator>
00528     inline bool
00529     operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
00530                const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
00531     { return !(__lhs < __rhs); }
00532 
00533   template<typename _Key, typename _Tp,
00534            typename _Compare, typename _Allocator>
00535     inline bool
00536     operator>(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
00537               const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
00538     { return __rhs < __lhs; }
00539 
00540   template<typename _Key, typename _Tp,
00541            typename _Compare, typename _Allocator>
00542     inline void
00543     swap(multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
00544          multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
00545     { __lhs.swap(__rhs); }
00546 
00547 } // namespace __profile
00548 } // namespace std
00549 
00550 #endif