Home | History | Annotate | Download | only in profile
      1 // Profiling multiset implementation -*- C++ -*-
      2 
      3 // Copyright (C) 2009, 2010 Free Software Foundation, Inc.
      4 //
      5 // This file is part of the GNU ISO C++ Library.  This library is free
      6 // software; you can redistribute it and/or modify it under the
      7 // terms of the GNU General Public License as published by the
      8 // Free Software Foundation; either version 3, or (at your option)
      9 // any later version.
     10 
     11 // This library is distributed in the hope that it will be useful,
     12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
     13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
     14 // GNU General Public License for more details.
     15 
     16 // Under Section 7 of GPL version 3, you are granted additional
     17 // permissions described in the GCC Runtime Library Exception, version
     18 // 3.1, as published by the Free Software Foundation.
     19 
     20 // You should have received a copy of the GNU General Public License and
     21 // a copy of the GCC Runtime Library Exception along with this program;
     22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
     23 // <http://www.gnu.org/licenses/>.
     24 
     25 /** @file profile/multiset.h
     26  *  This file is a GNU profile extension to the Standard C++ Library.
     27  */
     28 
     29 #ifndef _GLIBCXX_PROFILE_MULTISET_H
     30 #define _GLIBCXX_PROFILE_MULTISET_H 1
     31 
     32 #include <utility>
     33 
     34 namespace std _GLIBCXX_VISIBILITY(default)
     35 {
     36 namespace __profile
     37 {
     38   /// Class std::multiset wrapper with performance instrumentation.
     39   template<typename _Key, typename _Compare = std::less<_Key>,
     40 	   typename _Allocator = std::allocator<_Key> >
     41     class multiset
     42     : public _GLIBCXX_STD_C::multiset<_Key, _Compare, _Allocator>
     43     {
     44       typedef _GLIBCXX_STD_C::multiset<_Key, _Compare, _Allocator> _Base;
     45 
     46     public:
     47       // types:
     48       typedef _Key				     key_type;
     49       typedef _Key				     value_type;
     50       typedef _Compare				     key_compare;
     51       typedef _Compare				     value_compare;
     52       typedef _Allocator			     allocator_type;
     53       typedef typename _Base::reference	             reference;
     54       typedef typename _Base::const_reference        const_reference;
     55 
     56       typedef typename _Base::iterator               iterator;
     57       typedef typename _Base::const_iterator         const_iterator;
     58       typedef typename _Base::reverse_iterator       reverse_iterator;
     59       typedef typename _Base::const_reverse_iterator const_reverse_iterator;
     60 
     61       typedef typename _Base::size_type              size_type;
     62       typedef typename _Base::difference_type        difference_type;
     63       typedef typename _Base::pointer                pointer;
     64       typedef typename _Base::const_pointer          const_pointer;
     65 
     66       // 23.3.3.1 construct/copy/destroy:
     67       explicit multiset(const _Compare& __comp = _Compare(),
     68 			const _Allocator& __a = _Allocator())
     69       : _Base(__comp, __a) { }
     70 
     71       template<typename _InputIterator>
     72         multiset(_InputIterator __first, _InputIterator __last,
     73 		 const _Compare& __comp = _Compare(),
     74 		 const _Allocator& __a = _Allocator())
     75 	: _Base(__first, __last, __comp, __a) { }
     76 
     77       multiset(const multiset& __x)
     78       : _Base(__x) { }
     79 
     80       multiset(const _Base& __x)
     81       : _Base(__x) { }
     82 
     83 #ifdef __GXX_EXPERIMENTAL_CXX0X__
     84       multiset(multiset&& __x)
     85       : _Base(std::move(__x))
     86       { }
     87 
     88       multiset(initializer_list<value_type> __l,
     89 	       const _Compare& __comp = _Compare(),
     90 	       const allocator_type& __a = allocator_type())
     91       : _Base(__l, __comp, __a) { }
     92 #endif
     93 
     94       ~multiset() { }
     95 
     96       multiset&
     97       operator=(const multiset& __x)
     98       {
     99 	*static_cast<_Base*>(this) = __x;
    100 	return *this;
    101       }
    102 
    103 #ifdef __GXX_EXPERIMENTAL_CXX0X__
    104       multiset&
    105       operator=(multiset&& __x)
    106       {
    107 	// NB: DR 1204.
    108 	// NB: DR 675.
    109 	this->clear();
    110 	this->swap(__x);
    111 	return *this;
    112       }
    113 
    114       multiset&
    115       operator=(initializer_list<value_type> __l)
    116       {
    117 	this->clear();
    118 	this->insert(__l);
    119 	return *this;
    120       }
    121 #endif
    122 
    123       using _Base::get_allocator;
    124 
    125       // iterators:
    126       iterator
    127       begin()
    128       { return iterator(_Base::begin()); }
    129 
    130       const_iterator
    131       begin() const
    132       { return const_iterator(_Base::begin()); }
    133 
    134       iterator
    135       end()
    136       { return iterator(_Base::end()); }
    137 
    138       const_iterator
    139       end() const
    140       { return const_iterator(_Base::end()); }
    141 
    142       reverse_iterator
    143       rbegin()
    144       { return reverse_iterator(end()); }
    145 
    146       const_reverse_iterator
    147       rbegin() const
    148       { return const_reverse_iterator(end()); }
    149 
    150       reverse_iterator
    151       rend()
    152       { return reverse_iterator(begin()); }
    153 
    154       const_reverse_iterator
    155       rend() const
    156       { return const_reverse_iterator(begin()); }
    157 
    158 #ifdef __GXX_EXPERIMENTAL_CXX0X__
    159       const_iterator
    160       cbegin() const
    161       { return const_iterator(_Base::begin()); }
    162 
    163       const_iterator
    164       cend() const
    165       { return const_iterator(_Base::end()); }
    166 
    167       const_reverse_iterator
    168       crbegin() const
    169       { return const_reverse_iterator(end()); }
    170 
    171       const_reverse_iterator
    172       crend() const
    173       { return const_reverse_iterator(begin()); }
    174 #endif
    175 
    176       // capacity:
    177       using _Base::empty;
    178       using _Base::size;
    179       using _Base::max_size;
    180 
    181       // modifiers:
    182       iterator
    183       insert(const value_type& __x)
    184       { return iterator(_Base::insert(__x)); }
    185 
    186 #ifdef __GXX_EXPERIMENTAL_CXX0X__
    187       iterator
    188       insert(value_type&& __x)
    189       { return iterator(_Base::insert(std::move(__x))); }
    190 #endif
    191 
    192       iterator
    193       insert(const_iterator __position, const value_type& __x)
    194       { return iterator(_Base::insert(__position, __x)); }
    195 
    196 #ifdef __GXX_EXPERIMENTAL_CXX0X__
    197       iterator
    198       insert(const_iterator __position, value_type&& __x)
    199       { return iterator(_Base::insert(__position, std::move(__x))); }
    200 #endif
    201 
    202       template<typename _InputIterator>
    203         void
    204         insert(_InputIterator __first, _InputIterator __last)
    205         { _Base::insert(__first, __last); }
    206 
    207 #ifdef __GXX_EXPERIMENTAL_CXX0X__
    208       void
    209       insert(initializer_list<value_type> __l)
    210       { _Base::insert(__l); }
    211 #endif
    212 
    213 #ifdef __GXX_EXPERIMENTAL_CXX0X__
    214       iterator
    215       erase(const_iterator __position)
    216       { return iterator(_Base::erase(__position)); }
    217 #else
    218       void
    219       erase(iterator __position)
    220       { _Base::erase(__position); }
    221 #endif
    222 
    223       size_type
    224       erase(const key_type& __x)
    225       {
    226 	std::pair<iterator, iterator> __victims = this->equal_range(__x);
    227 	size_type __count = 0;
    228 	while (__victims.first != __victims.second)
    229 	{
    230 	  iterator __victim = __victims.first++;
    231 	  _Base::erase(__victim);
    232 	  ++__count;
    233 	}
    234 	return __count;
    235       }
    236 
    237 #ifdef __GXX_EXPERIMENTAL_CXX0X__
    238       iterator
    239       erase(const_iterator __first, const_iterator __last)
    240       { return iterator(_Base::erase(__first, __last)); }
    241 #else
    242       void
    243       erase(iterator __first, iterator __last)
    244       { _Base::erase(__first, __last); }
    245 #endif
    246 
    247       void
    248       swap(multiset& __x)
    249       { _Base::swap(__x); }
    250 
    251       void
    252       clear()
    253       { this->erase(begin(), end()); }
    254 
    255       // observers:
    256       using _Base::key_comp;
    257       using _Base::value_comp;
    258 
    259       // multiset operations:
    260       iterator
    261       find(const key_type& __x)
    262       { return iterator(_Base::find(__x)); }
    263 
    264       // _GLIBCXX_RESOLVE_LIB_DEFECTS
    265       // 214. set::find() missing const overload
    266       const_iterator
    267       find(const key_type& __x) const
    268       { return const_iterator(_Base::find(__x)); }
    269 
    270       using _Base::count;
    271 
    272       iterator
    273       lower_bound(const key_type& __x)
    274       { return iterator(_Base::lower_bound(__x)); }
    275 
    276       // _GLIBCXX_RESOLVE_LIB_DEFECTS
    277       // 214. set::find() missing const overload
    278       const_iterator
    279       lower_bound(const key_type& __x) const
    280       { return const_iterator(_Base::lower_bound(__x)); }
    281 
    282       iterator
    283       upper_bound(const key_type& __x)
    284       { return iterator(_Base::upper_bound(__x)); }
    285 
    286       // _GLIBCXX_RESOLVE_LIB_DEFECTS
    287       // 214. set::find() missing const overload
    288       const_iterator
    289       upper_bound(const key_type& __x) const
    290       { return const_iterator(_Base::upper_bound(__x)); }
    291 
    292       std::pair<iterator,iterator>
    293       equal_range(const key_type& __x)
    294       {
    295 	typedef typename _Base::iterator _Base_iterator;
    296 	std::pair<_Base_iterator, _Base_iterator> __res =
    297         _Base::equal_range(__x);
    298 	return std::make_pair(iterator(__res.first),
    299 			      iterator(__res.second));
    300       }
    301 
    302       // _GLIBCXX_RESOLVE_LIB_DEFECTS
    303       // 214. set::find() missing const overload
    304       std::pair<const_iterator,const_iterator>
    305       equal_range(const key_type& __x) const
    306       {
    307 	typedef typename _Base::const_iterator _Base_iterator;
    308 	std::pair<_Base_iterator, _Base_iterator> __res =
    309         _Base::equal_range(__x);
    310 	return std::make_pair(const_iterator(__res.first),
    311 			      const_iterator(__res.second));
    312       }
    313 
    314       _Base&
    315       _M_base() { return *this; }
    316 
    317       const _Base&
    318       _M_base() const { return *this; }
    319 
    320     };
    321 
    322   template<typename _Key, typename _Compare, typename _Allocator>
    323     inline bool
    324     operator==(const multiset<_Key, _Compare, _Allocator>& __lhs,
    325 	       const multiset<_Key, _Compare, _Allocator>& __rhs)
    326     { return __lhs._M_base() == __rhs._M_base(); }
    327 
    328   template<typename _Key, typename _Compare, typename _Allocator>
    329     inline bool
    330     operator!=(const multiset<_Key, _Compare, _Allocator>& __lhs,
    331 	       const multiset<_Key, _Compare, _Allocator>& __rhs)
    332     { return __lhs._M_base() != __rhs._M_base(); }
    333 
    334   template<typename _Key, typename _Compare, typename _Allocator>
    335     inline bool
    336     operator<(const multiset<_Key, _Compare, _Allocator>& __lhs,
    337 	      const multiset<_Key, _Compare, _Allocator>& __rhs)
    338     { return __lhs._M_base() < __rhs._M_base(); }
    339 
    340   template<typename _Key, typename _Compare, typename _Allocator>
    341     inline bool
    342     operator<=(const multiset<_Key, _Compare, _Allocator>& __lhs,
    343 	       const multiset<_Key, _Compare, _Allocator>& __rhs)
    344     { return __lhs._M_base() <= __rhs._M_base(); }
    345 
    346   template<typename _Key, typename _Compare, typename _Allocator>
    347     inline bool
    348     operator>=(const multiset<_Key, _Compare, _Allocator>& __lhs,
    349 	       const multiset<_Key, _Compare, _Allocator>& __rhs)
    350     { return __lhs._M_base() >= __rhs._M_base(); }
    351 
    352   template<typename _Key, typename _Compare, typename _Allocator>
    353     inline bool
    354     operator>(const multiset<_Key, _Compare, _Allocator>& __lhs,
    355 	      const multiset<_Key, _Compare, _Allocator>& __rhs)
    356     { return __lhs._M_base() > __rhs._M_base(); }
    357 
    358   template<typename _Key, typename _Compare, typename _Allocator>
    359     void
    360     swap(multiset<_Key, _Compare, _Allocator>& __x,
    361 	 multiset<_Key, _Compare, _Allocator>& __y)
    362     { return __x.swap(__y); }
    363 
    364 } // namespace __profile
    365 } // namespace std
    366 
    367 #endif
    368