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