libstdc++
set.h
Go to the documentation of this file.
00001 // Profiling set implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2009-2014 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 <utility>
00033 
00034 namespace std _GLIBCXX_VISIBILITY(default) 
00035 {
00036 namespace __profile
00037 {
00038   /// Class std::set wrapper with performance instrumentation.
00039   template<typename _Key, typename _Compare = std::less<_Key>,
00040        typename _Allocator = std::allocator<_Key> >
00041     class set
00042     : public _GLIBCXX_STD_C::set<_Key,_Compare,_Allocator>
00043     {
00044       typedef _GLIBCXX_STD_C::set<_Key, _Compare, _Allocator> _Base;
00045 
00046 #if __cplusplus >= 201103L
00047       typedef __gnu_cxx::__alloc_traits<_Allocator> _Alloc_traits;
00048 #endif
00049 
00050     public:
00051       // types:
00052       typedef _Key                  key_type;
00053       typedef _Key                  value_type;
00054       typedef _Compare                  key_compare;
00055       typedef _Compare                  value_compare;
00056       typedef _Allocator                allocator_type;
00057       typedef typename _Base::reference             reference;
00058       typedef typename _Base::const_reference       const_reference;
00059 
00060       typedef typename _Base::iterator               iterator;
00061       typedef typename _Base::const_iterator         const_iterator;
00062       typedef typename _Base::reverse_iterator       reverse_iterator;
00063       typedef typename _Base::const_reverse_iterator const_reverse_iterator;
00064 
00065       typedef typename _Base::size_type             size_type;
00066       typedef typename _Base::difference_type       difference_type;
00067       typedef typename _Base::pointer               pointer;
00068       typedef typename _Base::const_pointer         const_pointer;
00069 
00070       // 23.3.3.1 construct/copy/destroy:
00071 
00072       set()
00073       : _Base() { }
00074 
00075       explicit set(const _Compare& __comp,
00076            const _Allocator& __a = _Allocator())
00077       : _Base(__comp, __a) { }
00078 
00079 #if __cplusplus >= 201103L
00080       template<typename _InputIterator,
00081            typename = std::_RequireInputIter<_InputIterator>>
00082 #else
00083       template<typename _InputIterator>
00084 #endif
00085         set(_InputIterator __first, _InputIterator __last,
00086         const _Compare& __comp = _Compare(),
00087         const _Allocator& __a = _Allocator())
00088     : _Base(__first, __last, __comp, __a) { }
00089 
00090 #if __cplusplus < 201103L
00091       set(const set& __x)
00092       : _Base(__x) { }
00093 #else
00094       set(const set&) = default;
00095       set(set&&) = default;
00096 
00097       set(initializer_list<value_type> __l,
00098       const _Compare& __comp = _Compare(),
00099       const allocator_type& __a = allocator_type())
00100       : _Base(__l, __comp, __a) { }
00101 
00102       explicit
00103       set(const allocator_type& __a)
00104     : _Base(__a) { }
00105 
00106       set(const set& __x, const allocator_type& __a)
00107       : _Base(__x, __a) { }
00108 
00109       set(set&& __x, const allocator_type& __a)
00110       noexcept(is_nothrow_copy_constructible<_Compare>::value
00111            && _Alloc_traits::_S_always_equal())
00112       : _Base(std::move(__x), __a) { }
00113 
00114       set(initializer_list<value_type> __l, const allocator_type& __a)
00115       : _Base(__l, __a) { }
00116 
00117       template<typename _InputIterator>
00118         set(_InputIterator __first, _InputIterator __last,
00119         const allocator_type& __a)
00120       : _Base(__first, __last, __a) { }
00121 #endif
00122 
00123       set(const _Base& __x)
00124       : _Base(__x) { }
00125 
00126       ~set() _GLIBCXX_NOEXCEPT { }
00127 
00128 #if __cplusplus < 201103L
00129       set&
00130       operator=(const set& __x)
00131       {
00132     _M_base() = __x;
00133     return *this;
00134       }
00135 #else
00136       set&
00137       operator=(const set&) = default;
00138 
00139       set&
00140       operator=(set&&) = default;
00141 
00142       set&
00143       operator=(initializer_list<value_type> __l)
00144       {
00145     _M_base() = __l;
00146     return *this;
00147       }
00148 #endif
00149 
00150       using _Base::get_allocator;
00151 
00152       // iterators:
00153       iterator
00154       begin() _GLIBCXX_NOEXCEPT
00155       { return iterator(_Base::begin()); }
00156 
00157       const_iterator
00158       begin() const _GLIBCXX_NOEXCEPT
00159       { return const_iterator(_Base::begin()); }
00160 
00161       iterator
00162       end() _GLIBCXX_NOEXCEPT
00163       { return iterator(_Base::end()); }
00164 
00165       const_iterator
00166       end() const _GLIBCXX_NOEXCEPT
00167       { return const_iterator(_Base::end()); }
00168 
00169       reverse_iterator
00170       rbegin() _GLIBCXX_NOEXCEPT
00171       { return reverse_iterator(end()); }
00172 
00173       const_reverse_iterator
00174       rbegin() const _GLIBCXX_NOEXCEPT
00175       { return const_reverse_iterator(end()); }
00176 
00177       reverse_iterator
00178       rend() _GLIBCXX_NOEXCEPT
00179       { return reverse_iterator(begin()); }
00180 
00181       const_reverse_iterator
00182       rend() const _GLIBCXX_NOEXCEPT
00183       { return const_reverse_iterator(begin()); }
00184 
00185 #if __cplusplus >= 201103L
00186       const_iterator
00187       cbegin() const noexcept
00188       { return const_iterator(_Base::begin()); }
00189 
00190       const_iterator
00191       cend() const noexcept
00192       { return const_iterator(_Base::end()); }
00193 
00194       const_reverse_iterator
00195       crbegin() const noexcept
00196       { return const_reverse_iterator(end()); }
00197 
00198       const_reverse_iterator
00199       crend() const noexcept
00200       { return const_reverse_iterator(begin()); }
00201 #endif
00202 
00203       // capacity:
00204       using _Base::empty;
00205       using _Base::size;
00206       using _Base::max_size;
00207 
00208       // modifiers:
00209 #if __cplusplus >= 201103L
00210       template<typename... _Args>
00211     std::pair<iterator, bool>
00212     emplace(_Args&&... __args)
00213     {
00214       auto __res = _Base::emplace(std::forward<_Args>(__args)...);
00215       return std::pair<iterator, bool>(iterator(__res.first),
00216                        __res.second);
00217     }
00218 
00219       template<typename... _Args>
00220     iterator
00221     emplace_hint(const_iterator __pos, _Args&&... __args)
00222     {
00223       return iterator(_Base::emplace_hint(__pos,
00224                           std::forward<_Args>(__args)...));
00225     }
00226 #endif
00227 
00228       std::pair<iterator, bool>
00229       insert(const value_type& __x)
00230       {
00231     typedef typename _Base::iterator _Base_iterator;
00232     std::pair<_Base_iterator, bool> __res = _Base::insert(__x);
00233     return std::pair<iterator, bool>(iterator(__res.first),
00234                      __res.second);
00235       }
00236 
00237 #if __cplusplus >= 201103L
00238       std::pair<iterator, bool>
00239       insert(value_type&& __x)
00240       {
00241     typedef typename _Base::iterator _Base_iterator;
00242     std::pair<_Base_iterator, bool> __res
00243       = _Base::insert(std::move(__x));
00244     return std::pair<iterator, bool>(iterator(__res.first),
00245                      __res.second);
00246       }
00247 #endif
00248 
00249       iterator
00250       insert(const_iterator __position, const value_type& __x)
00251       { return iterator(_Base::insert(__position, __x)); }
00252 
00253 #if __cplusplus >= 201103L
00254       iterator
00255       insert(const_iterator __position, value_type&& __x)
00256       { return iterator(_Base::insert(__position, std::move(__x))); }
00257 #endif
00258 
00259 #if __cplusplus >= 201103L
00260       template<typename _InputIterator,
00261            typename = std::_RequireInputIter<_InputIterator>>
00262 #else
00263       template<typename _InputIterator>
00264 #endif
00265         void
00266         insert(_InputIterator __first, _InputIterator __last)
00267         { _Base::insert(__first, __last); }
00268 
00269 #if __cplusplus >= 201103L
00270       void
00271       insert(initializer_list<value_type> __l)
00272       { _Base::insert(__l); }
00273 #endif
00274 
00275 #if __cplusplus >= 201103L
00276       iterator
00277       erase(const_iterator __position)
00278       { return iterator(_Base::erase(__position)); }
00279 #else
00280       void
00281       erase(iterator __position)
00282       { _Base::erase(__position); }
00283 #endif
00284 
00285       size_type
00286       erase(const key_type& __x)
00287       {
00288     iterator __victim = find(__x);
00289     if (__victim == end())
00290           return 0;
00291     else
00292         {
00293       _Base::erase(__victim);
00294       return 1;
00295         }
00296       }
00297 
00298 #if __cplusplus >= 201103L
00299       iterator
00300       erase(const_iterator __first, const_iterator __last)
00301       { return iterator(_Base::erase(__first, __last)); }
00302 #else
00303       void
00304       erase(iterator __first, iterator __last)
00305       { _Base::erase(__first, __last); }
00306 #endif
00307 
00308       void
00309       swap(set& __x)
00310 #if __cplusplus >= 201103L
00311       noexcept(_Alloc_traits::_S_nothrow_swap())
00312 #endif
00313       { _Base::swap(__x); }
00314 
00315       void
00316       clear() _GLIBCXX_NOEXCEPT
00317       { this->erase(begin(), end()); }
00318 
00319       // observers:
00320       using _Base::key_comp;
00321       using _Base::value_comp;
00322 
00323       // set operations:
00324       iterator
00325       find(const key_type& __x)
00326       { return iterator(_Base::find(__x)); }
00327 
00328       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00329       // 214. set::find() missing const overload
00330       const_iterator
00331       find(const key_type& __x) const
00332       { return const_iterator(_Base::find(__x)); }
00333 
00334       using _Base::count;
00335 
00336       iterator
00337       lower_bound(const key_type& __x)
00338       { return iterator(_Base::lower_bound(__x)); }
00339 
00340       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00341       // 214. set::find() missing const overload
00342       const_iterator
00343       lower_bound(const key_type& __x) const
00344       { return const_iterator(_Base::lower_bound(__x)); }
00345 
00346       iterator
00347       upper_bound(const key_type& __x)
00348       { return iterator(_Base::upper_bound(__x)); }
00349 
00350       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00351       // 214. set::find() missing const overload
00352       const_iterator
00353       upper_bound(const key_type& __x) const
00354       { return const_iterator(_Base::upper_bound(__x)); }
00355 
00356       std::pair<iterator,iterator>
00357       equal_range(const key_type& __x)
00358       {
00359     typedef typename _Base::iterator _Base_iterator;
00360     std::pair<_Base_iterator, _Base_iterator> __res =
00361         _Base::equal_range(__x);
00362     return std::make_pair(iterator(__res.first),
00363                   iterator(__res.second));
00364       }
00365 
00366       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00367       // 214. set::find() missing const overload
00368       std::pair<const_iterator,const_iterator>
00369       equal_range(const key_type& __x) const
00370       {
00371     typedef typename _Base::const_iterator _Base_iterator;
00372     std::pair<_Base_iterator, _Base_iterator> __res =
00373         _Base::equal_range(__x);
00374     return std::make_pair(const_iterator(__res.first),
00375                   const_iterator(__res.second));
00376       }
00377 
00378       _Base&
00379       _M_base() _GLIBCXX_NOEXCEPT       { return *this; }
00380 
00381       const _Base&
00382       _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
00383 
00384     };
00385 
00386   template<typename _Key, typename _Compare, typename _Allocator>
00387     inline bool
00388     operator==(const set<_Key, _Compare, _Allocator>& __lhs,
00389            const set<_Key, _Compare, _Allocator>& __rhs)
00390     { return __lhs._M_base() == __rhs._M_base(); }
00391 
00392   template<typename _Key, typename _Compare, typename _Allocator>
00393     inline bool
00394     operator!=(const set<_Key, _Compare, _Allocator>& __lhs,
00395            const set<_Key, _Compare, _Allocator>& __rhs)
00396     { return __lhs._M_base() != __rhs._M_base(); }
00397 
00398   template<typename _Key, typename _Compare, typename _Allocator>
00399     inline bool
00400     operator<(const set<_Key, _Compare, _Allocator>& __lhs,
00401           const set<_Key, _Compare, _Allocator>& __rhs)
00402     { return __lhs._M_base() < __rhs._M_base(); }
00403 
00404   template<typename _Key, typename _Compare, typename _Allocator>
00405     inline bool
00406     operator<=(const set<_Key, _Compare, _Allocator>& __lhs,
00407            const set<_Key, _Compare, _Allocator>& __rhs)
00408     { return __lhs._M_base() <= __rhs._M_base(); }
00409 
00410   template<typename _Key, typename _Compare, typename _Allocator>
00411     inline bool
00412     operator>=(const set<_Key, _Compare, _Allocator>& __lhs,
00413            const set<_Key, _Compare, _Allocator>& __rhs)
00414     { return __lhs._M_base() >= __rhs._M_base(); }
00415 
00416   template<typename _Key, typename _Compare, typename _Allocator>
00417     inline bool
00418     operator>(const set<_Key, _Compare, _Allocator>& __lhs,
00419           const set<_Key, _Compare, _Allocator>& __rhs)
00420     { return __lhs._M_base() > __rhs._M_base(); }
00421 
00422   template<typename _Key, typename _Compare, typename _Allocator>
00423     void
00424     swap(set<_Key, _Compare, _Allocator>& __x,
00425      set<_Key, _Compare, _Allocator>& __y)
00426     { return __x.swap(__y); }
00427 
00428 } // namespace __profile
00429 } // namespace std
00430 
00431 #endif