libstdc++
set.h
Go to the documentation of this file.
00001 // Profiling set 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/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 #if __cplusplus >= 201103L
00227         noexcept( noexcept(declval<_Base>().swap(__x)) )
00228 #endif
00229       {
00230         _Base::swap(__x);
00231         this->_M_swap(__x);
00232       }
00233 
00234       // modifiers:
00235 #if __cplusplus >= 201103L
00236       template<typename... _Args>
00237         std::pair<iterator, bool>
00238         emplace(_Args&&... __args)
00239         {
00240           __profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1);
00241           auto __base_ret = _Base::emplace(std::forward<_Args>(__args)...);
00242           return std::make_pair(iterator(__base_ret.first, this),
00243                                 __base_ret.second);
00244         }
00245 
00246       template<typename... _Args>
00247         iterator
00248         emplace_hint(const_iterator __pos, _Args&&... __args)
00249         {
00250           auto size_before = this->size();
00251           auto __res
00252             = _Base::emplace_hint(__pos.base(), std::forward<_Args>(__args)...);
00253           __profcxx_map2umap_insert(this->_M_map2umap_info,
00254                 size_before, _M_hint_used(__pos.base(), __res) ? 0 : 1);
00255           return iterator(__res, this);
00256         }
00257 #endif
00258 
00259       std::pair<iterator, bool>
00260       insert(const value_type& __x)
00261       {
00262         __profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1);
00263         std::pair<_Base_iterator, bool> __base_ret = _Base::insert(__x);
00264         return std::make_pair(iterator(__base_ret.first, this),
00265                               __base_ret.second);
00266       }
00267 
00268 #if __cplusplus >= 201103L
00269       std::pair<iterator, bool>
00270       insert(value_type&& __x)
00271       {
00272         __profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1);
00273         std::pair<_Base_iterator, bool> __base_ret
00274           = _Base::insert(std::move(__x));
00275         return std::make_pair(iterator(__base_ret.first, this),
00276                               __base_ret.second);
00277       }
00278 #endif
00279 
00280       iterator
00281       insert(const_iterator __pos, const value_type& __x)
00282       {
00283         size_type size_before = this->size();
00284         _Base_iterator __res = _Base::insert(__pos.base(), __x);
00285         __profcxx_map2umap_insert(this->_M_map2umap_info,
00286                 size_before, _M_hint_used(__pos.base(), __res) ? 0 : 1);
00287         return iterator(__res, this);
00288       }
00289 
00290 #if __cplusplus >= 201103L
00291       iterator
00292       insert(const_iterator __pos, value_type&& __x)
00293       { return iterator(_Base::insert(__pos.base(), std::move(__x)), this); }
00294 #endif
00295 
00296       template<typename _InputIterator>
00297         void
00298         insert(_InputIterator __first, _InputIterator __last)
00299         {
00300           for (; __first != __last; ++__first)
00301             insert(*__first);
00302         }
00303 
00304 #if __cplusplus >= 201103L
00305       void
00306       insert(initializer_list<value_type> __l)
00307       { insert(__l.begin(), __l.end()); }
00308 #endif
00309 
00310 #if __cplusplus >= 201103L
00311       iterator
00312       erase(const_iterator __pos)
00313       {
00314         __profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1);
00315         return iterator(_Base::erase(__pos.base()), this);
00316       }
00317 #else
00318       void
00319       erase(iterator __pos)
00320       {
00321         __profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1);
00322         _Base::erase(__pos.base());
00323       }
00324 #endif
00325 
00326       size_type
00327       erase(const key_type& __x)
00328       {
00329         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
00330         __profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1);
00331         return _Base::erase(__x);
00332       }
00333 
00334 #if __cplusplus >= 201103L
00335       iterator
00336       erase(const_iterator __first, const_iterator __last)
00337       {
00338         if (__first != __last)
00339           {
00340             iterator __ret;
00341             for (; __first != __last;)
00342               __ret = erase(__first++);
00343             return __ret;
00344           }
00345 
00346         return iterator(_Base::erase(__first.base(), __last.base()), this);
00347       }
00348 #else
00349       void
00350       erase(iterator __first, iterator __last)
00351       {
00352         for (; __first != __last;)
00353              erase(__first++);
00354       }
00355 #endif
00356 
00357       void
00358       clear() _GLIBCXX_NOEXCEPT
00359       {
00360         this->_M_profile_destruct();
00361         _Base::clear();
00362         this->_M_profile_construct();
00363       }
00364 
00365       size_type
00366       count(const key_type& __x) const
00367       {
00368         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
00369         return _Base::count(__x);
00370       }
00371 
00372       // set operations:
00373       iterator
00374       find(const key_type& __x)
00375       {
00376         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
00377         return iterator(_Base::find(__x), this);
00378       }
00379 
00380       const_iterator
00381       find(const key_type& __x) const
00382       {
00383         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
00384         return const_iterator(_Base::find(__x), this);
00385       }
00386 
00387       iterator
00388       lower_bound(const key_type& __x)
00389       {
00390         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
00391         __profcxx_map2umap_invalidate(this->_M_map2umap_info);
00392         return iterator(_Base::lower_bound(__x), this);
00393       }
00394 
00395       const_iterator
00396       lower_bound(const key_type& __x) const
00397       {
00398         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
00399         __profcxx_map2umap_invalidate(this->_M_map2umap_info);
00400         return const_iterator(_Base::lower_bound(__x), this);
00401       }
00402 
00403       iterator
00404       upper_bound(const key_type& __x)
00405       {
00406         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
00407         __profcxx_map2umap_invalidate(this->_M_map2umap_info);
00408         return iterator(_Base::upper_bound(__x), this);
00409       }
00410 
00411       const_iterator
00412       upper_bound(const key_type& __x) const
00413       {
00414         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
00415         __profcxx_map2umap_invalidate(this->_M_map2umap_info);
00416         return const_iterator(_Base::upper_bound(__x), this);
00417       }
00418 
00419       std::pair<iterator, iterator>
00420       equal_range(const key_type& __x)
00421       {
00422         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
00423         std::pair<_Base_iterator, _Base_iterator> __base_ret
00424           = _Base::equal_range(__x);
00425         return std::make_pair(iterator(__base_ret.first, this),
00426                               iterator(__base_ret.second, this));
00427       }
00428 
00429       std::pair<const_iterator, const_iterator>
00430       equal_range(const key_type& __x) const
00431       {
00432         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
00433         std::pair<_Base_const_iterator, _Base_const_iterator> __base_ret
00434           = _Base::equal_range(__x);
00435         return std::make_pair(const_iterator(__base_ret.first, this),
00436                               const_iterator(__base_ret.second, this));
00437       }
00438 
00439       _Base&
00440       _M_base() _GLIBCXX_NOEXCEPT       { return *this; }
00441 
00442       const _Base&
00443       _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
00444 
00445     private:
00446       /** If hint is used we consider that the map and unordered_map
00447        * operations have equivalent insertion cost so we do not update metrics
00448        * about it.
00449        * Note that to find out if hint has been used is libstdc++
00450        * implementation dependent.
00451        */
00452       bool
00453       _M_hint_used(_Base_const_iterator __hint, _Base_iterator __res)
00454       {
00455         return (__hint == __res
00456                 || (__hint == _M_base().end() && ++__res == _M_base().end())
00457                 || (__hint != _M_base().end() && (++__hint == __res
00458                                                   || ++__res == --__hint)));
00459       }
00460 
00461       template<typename _K1, typename _C1, typename _A1>
00462         friend bool
00463         operator==(const set<_K1, _C1, _A1>&, const set<_K1, _C1, _A1>&);
00464 
00465       template<typename _K1, typename _C1, typename _A1>
00466         friend bool
00467         operator<(const set<_K1, _C1, _A1>&, const set<_K1, _C1, _A1>&);
00468     };
00469 
00470   template<typename _Key, typename _Compare, typename _Allocator>
00471     inline bool
00472     operator==(const set<_Key, _Compare, _Allocator>& __lhs,
00473                const set<_Key, _Compare, _Allocator>& __rhs)
00474     {
00475       __profcxx_map2umap_invalidate(__lhs._M_map2umap_info);
00476       __profcxx_map2umap_invalidate(__rhs._M_map2umap_info);
00477       return __lhs._M_base() == __rhs._M_base();
00478     }
00479 
00480   template<typename _Key, typename _Compare, typename _Allocator>
00481     inline bool
00482     operator<(const set<_Key, _Compare, _Allocator>& __lhs,
00483               const set<_Key, _Compare, _Allocator>& __rhs)
00484     {
00485       __profcxx_map2umap_invalidate(__lhs._M_map2umap_info);
00486       __profcxx_map2umap_invalidate(__rhs._M_map2umap_info);
00487       return __lhs._M_base() < __rhs._M_base();
00488     }
00489 
00490   template<typename _Key, typename _Compare, typename _Allocator>
00491     inline bool
00492     operator!=(const set<_Key, _Compare, _Allocator>& __lhs,
00493                const set<_Key, _Compare, _Allocator>& __rhs)
00494     { return !(__lhs == __rhs); }
00495 
00496   template<typename _Key, typename _Compare, typename _Allocator>
00497     inline bool
00498     operator<=(const set<_Key, _Compare, _Allocator>& __lhs,
00499                const set<_Key, _Compare, _Allocator>& __rhs)
00500     { return !(__rhs < __lhs); }
00501 
00502   template<typename _Key, typename _Compare, typename _Allocator>
00503     inline bool
00504     operator>=(const set<_Key, _Compare, _Allocator>& __lhs,
00505                const set<_Key, _Compare, _Allocator>& __rhs)
00506     { return !(__lhs < __rhs); }
00507 
00508   template<typename _Key, typename _Compare, typename _Allocator>
00509     inline bool
00510     operator>(const set<_Key, _Compare, _Allocator>& __lhs,
00511               const set<_Key, _Compare, _Allocator>& __rhs)
00512     { return __rhs < __lhs; }
00513 
00514   template<typename _Key, typename _Compare, typename _Allocator>
00515     void
00516     swap(set<_Key, _Compare, _Allocator>& __x,
00517          set<_Key, _Compare, _Allocator>& __y)
00518     { return __x.swap(__y); }
00519 
00520 } // namespace __profile
00521 } // namespace std
00522 
00523 #endif