libstdc++
multiset.h
Go to the documentation of this file.
00001 // Profiling multiset 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/multiset.h
00026  *  This file is a GNU profile extension to the Standard C++ Library.
00027  */
00028 
00029 #ifndef _GLIBCXX_PROFILE_MULTISET_H
00030 #define _GLIBCXX_PROFILE_MULTISET_H 1
00031 
00032 #include <utility>
00033 
00034 namespace std _GLIBCXX_VISIBILITY(default)
00035 {
00036 namespace __profile
00037 {
00038   /// Class std::multiset wrapper with performance instrumentation.
00039   template<typename _Key, typename _Compare = std::less<_Key>,
00040        typename _Allocator = std::allocator<_Key> >
00041     class multiset
00042     : public _GLIBCXX_STD_C::multiset<_Key, _Compare, _Allocator>
00043     {
00044       typedef _GLIBCXX_STD_C::multiset<_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       multiset()
00073       : _Base() { }
00074 
00075       explicit multiset(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         multiset(_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       multiset(const multiset& __x)
00092       : _Base(__x) { }
00093 #else
00094       multiset(const multiset&) = default;
00095       multiset(multiset&&) = default;
00096 
00097       multiset(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       multiset(const allocator_type& __a)
00104     : _Base(__a) { }
00105 
00106       multiset(const multiset& __x, const allocator_type& __a)
00107       : _Base(__x, __a) { }
00108 
00109       multiset(multiset&& __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       multiset(initializer_list<value_type> __l, const allocator_type& __a)
00115       : _Base(__l, __a) { }
00116 
00117       template<typename _InputIterator>
00118         multiset(_InputIterator __first, _InputIterator __last,
00119         const allocator_type& __a)
00120       : _Base(__first, __last, __a) { }
00121 #endif
00122 
00123       multiset(const _Base& __x)
00124       : _Base(__x) { }
00125 
00126       ~multiset() _GLIBCXX_NOEXCEPT { }
00127 
00128 #if __cplusplus < 201103L
00129       multiset&
00130       operator=(const multiset& __x)
00131       {
00132     _M_base() = __x;
00133     return *this;
00134       }
00135 #else
00136       multiset&
00137       operator=(const multiset&) = default;
00138 
00139       multiset&
00140       operator=(multiset&&) = default;
00141 
00142       multiset&
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     iterator
00212     emplace(_Args&&... __args)
00213     { return iterator(_Base::emplace(std::forward<_Args>(__args)...)); }
00214 
00215       template<typename... _Args>
00216     iterator
00217     emplace_hint(const_iterator __pos, _Args&&... __args)
00218     {
00219       return iterator(_Base::emplace_hint(__pos,
00220                           std::forward<_Args>(__args)...));
00221     }
00222 #endif
00223 
00224       iterator
00225       insert(const value_type& __x)
00226       { return iterator(_Base::insert(__x)); }
00227 
00228 #if __cplusplus >= 201103L
00229       iterator
00230       insert(value_type&& __x)
00231       { return iterator(_Base::insert(std::move(__x))); }
00232 #endif
00233 
00234       iterator
00235       insert(const_iterator __position, const value_type& __x)
00236       { return iterator(_Base::insert(__position, __x)); }
00237 
00238 #if __cplusplus >= 201103L
00239       iterator
00240       insert(const_iterator __position, value_type&& __x)
00241       { return iterator(_Base::insert(__position, std::move(__x))); }
00242 #endif
00243 
00244 #if __cplusplus >= 201103L
00245       template<typename _InputIterator,
00246            typename = std::_RequireInputIter<_InputIterator>>
00247 #else
00248       template<typename _InputIterator>
00249 #endif
00250         void
00251         insert(_InputIterator __first, _InputIterator __last)
00252         { _Base::insert(__first, __last); }
00253 
00254 #if __cplusplus >= 201103L
00255       void
00256       insert(initializer_list<value_type> __l)
00257       { _Base::insert(__l); }
00258 #endif
00259 
00260 #if __cplusplus >= 201103L
00261       iterator
00262       erase(const_iterator __position)
00263       { return iterator(_Base::erase(__position)); }
00264 #else
00265       void
00266       erase(iterator __position)
00267       { _Base::erase(__position); }
00268 #endif
00269 
00270       size_type
00271       erase(const key_type& __x)
00272       {
00273     std::pair<iterator, iterator> __victims = this->equal_range(__x);
00274     size_type __count = 0;
00275     while (__victims.first != __victims.second)
00276     {
00277       iterator __victim = __victims.first++;
00278       _Base::erase(__victim);
00279       ++__count;
00280     }
00281     return __count;
00282       }
00283 
00284 #if __cplusplus >= 201103L
00285       iterator
00286       erase(const_iterator __first, const_iterator __last)
00287       { return iterator(_Base::erase(__first, __last)); }
00288 #else
00289       void
00290       erase(iterator __first, iterator __last)
00291       { _Base::erase(__first, __last); }
00292 #endif
00293 
00294       void
00295       swap(multiset& __x)
00296 #if __cplusplus >= 201103L
00297       noexcept(_Alloc_traits::_S_nothrow_swap())
00298 #endif
00299       { _Base::swap(__x); }
00300 
00301       void
00302       clear() _GLIBCXX_NOEXCEPT
00303       { this->erase(begin(), end()); }
00304 
00305       // observers:
00306       using _Base::key_comp;
00307       using _Base::value_comp;
00308 
00309       // multiset operations:
00310       iterator
00311       find(const key_type& __x)
00312       { return iterator(_Base::find(__x)); }
00313 
00314       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00315       // 214. set::find() missing const overload
00316       const_iterator
00317       find(const key_type& __x) const
00318       { return const_iterator(_Base::find(__x)); }
00319 
00320       using _Base::count;
00321 
00322       iterator
00323       lower_bound(const key_type& __x)
00324       { return iterator(_Base::lower_bound(__x)); }
00325 
00326       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00327       // 214. set::find() missing const overload
00328       const_iterator
00329       lower_bound(const key_type& __x) const
00330       { return const_iterator(_Base::lower_bound(__x)); }
00331 
00332       iterator
00333       upper_bound(const key_type& __x)
00334       { return iterator(_Base::upper_bound(__x)); }
00335 
00336       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00337       // 214. set::find() missing const overload
00338       const_iterator
00339       upper_bound(const key_type& __x) const
00340       { return const_iterator(_Base::upper_bound(__x)); }
00341 
00342       std::pair<iterator,iterator>
00343       equal_range(const key_type& __x)
00344       {
00345     typedef typename _Base::iterator _Base_iterator;
00346     std::pair<_Base_iterator, _Base_iterator> __res =
00347         _Base::equal_range(__x);
00348     return std::make_pair(iterator(__res.first),
00349                   iterator(__res.second));
00350       }
00351 
00352       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00353       // 214. set::find() missing const overload
00354       std::pair<const_iterator,const_iterator>
00355       equal_range(const key_type& __x) const
00356       {
00357     typedef typename _Base::const_iterator _Base_iterator;
00358     std::pair<_Base_iterator, _Base_iterator> __res =
00359         _Base::equal_range(__x);
00360     return std::make_pair(const_iterator(__res.first),
00361                   const_iterator(__res.second));
00362       }
00363 
00364       _Base&
00365       _M_base() _GLIBCXX_NOEXCEPT       { return *this; }
00366 
00367       const _Base&
00368       _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
00369 
00370     };
00371 
00372   template<typename _Key, typename _Compare, typename _Allocator>
00373     inline bool
00374     operator==(const multiset<_Key, _Compare, _Allocator>& __lhs,
00375            const multiset<_Key, _Compare, _Allocator>& __rhs)
00376     { return __lhs._M_base() == __rhs._M_base(); }
00377 
00378   template<typename _Key, typename _Compare, typename _Allocator>
00379     inline bool
00380     operator!=(const multiset<_Key, _Compare, _Allocator>& __lhs,
00381            const multiset<_Key, _Compare, _Allocator>& __rhs)
00382     { return __lhs._M_base() != __rhs._M_base(); }
00383 
00384   template<typename _Key, typename _Compare, typename _Allocator>
00385     inline bool
00386     operator<(const multiset<_Key, _Compare, _Allocator>& __lhs,
00387           const multiset<_Key, _Compare, _Allocator>& __rhs)
00388     { return __lhs._M_base() < __rhs._M_base(); }
00389 
00390   template<typename _Key, typename _Compare, typename _Allocator>
00391     inline bool
00392     operator<=(const multiset<_Key, _Compare, _Allocator>& __lhs,
00393            const multiset<_Key, _Compare, _Allocator>& __rhs)
00394     { return __lhs._M_base() <= __rhs._M_base(); }
00395 
00396   template<typename _Key, typename _Compare, typename _Allocator>
00397     inline bool
00398     operator>=(const multiset<_Key, _Compare, _Allocator>& __lhs,
00399            const multiset<_Key, _Compare, _Allocator>& __rhs)
00400     { return __lhs._M_base() >= __rhs._M_base(); }
00401 
00402   template<typename _Key, typename _Compare, typename _Allocator>
00403     inline bool
00404     operator>(const multiset<_Key, _Compare, _Allocator>& __lhs,
00405           const multiset<_Key, _Compare, _Allocator>& __rhs)
00406     { return __lhs._M_base() > __rhs._M_base(); }
00407 
00408   template<typename _Key, typename _Compare, typename _Allocator>
00409     void
00410     swap(multiset<_Key, _Compare, _Allocator>& __x,
00411      multiset<_Key, _Compare, _Allocator>& __y)
00412     { return __x.swap(__y); }
00413 
00414 } // namespace __profile
00415 } // namespace std
00416 
00417 #endif