debug/multiset.h

Go to the documentation of this file.
00001 // Debugging multiset implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2003, 2004, 2005, 2006, 2007, 2009, 2010
00004 // Free Software Foundation, Inc.
00005 //
00006 // This file is part of the GNU ISO C++ Library.  This library is free
00007 // software; you can redistribute it and/or modify it under the
00008 // terms of the GNU General Public License as published by the
00009 // Free Software Foundation; either version 3, or (at your option)
00010 // any later version.
00011 
00012 // This library is distributed in the hope that it will be useful,
00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015 // GNU General Public License for more details.
00016 
00017 // Under Section 7 of GPL version 3, you are granted additional
00018 // permissions described in the GCC Runtime Library Exception, version
00019 // 3.1, as published by the Free Software Foundation.
00020 
00021 // You should have received a copy of the GNU General Public License and
00022 // a copy of the GCC Runtime Library Exception along with this program;
00023 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00024 // <http://www.gnu.org/licenses/>.
00025 
00026 /** @file debug/multiset.h
00027  *  This file is a GNU debug extension to the Standard C++ Library.
00028  */
00029 
00030 #ifndef _GLIBCXX_DEBUG_MULTISET_H
00031 #define _GLIBCXX_DEBUG_MULTISET_H 1
00032 
00033 #include <debug/safe_sequence.h>
00034 #include <debug/safe_iterator.h>
00035 #include <utility>
00036 
00037 namespace std
00038 {
00039 namespace __debug
00040 {
00041   /// Class std::multiset with safety/checking/debug instrumentation.
00042   template<typename _Key, typename _Compare = std::less<_Key>,
00043        typename _Allocator = std::allocator<_Key> >
00044     class multiset
00045     : public _GLIBCXX_STD_D::multiset<_Key, _Compare, _Allocator>,
00046       public __gnu_debug::_Safe_sequence<multiset<_Key, _Compare, _Allocator> >
00047     {
00048       typedef _GLIBCXX_STD_D::multiset<_Key, _Compare, _Allocator> _Base;
00049       typedef __gnu_debug::_Safe_sequence<multiset> _Safe_base;
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 _Allocator                 allocator_type;
00058       typedef typename _Base::reference              reference;
00059       typedef typename _Base::const_reference        const_reference;
00060 
00061       typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, multiset>
00062       iterator;
00063       typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
00064                       multiset> const_iterator;
00065 
00066       typedef typename _Base::size_type              size_type;
00067       typedef typename _Base::difference_type        difference_type;
00068       typedef typename _Base::pointer                pointer;
00069       typedef typename _Base::const_pointer          const_pointer;
00070       typedef std::reverse_iterator<iterator>        reverse_iterator;
00071       typedef std::reverse_iterator<const_iterator>  const_reverse_iterator;
00072 
00073       // 23.3.3.1 construct/copy/destroy:
00074       explicit multiset(const _Compare& __comp = _Compare(),
00075             const _Allocator& __a = _Allocator())
00076       : _Base(__comp, __a) { }
00077 
00078       template<typename _InputIterator>
00079         multiset(_InputIterator __first, _InputIterator __last,
00080          const _Compare& __comp = _Compare(),
00081          const _Allocator& __a = _Allocator())
00082     : _Base(__gnu_debug::__check_valid_range(__first, __last), __last,
00083         __comp, __a) { }
00084 
00085       multiset(const multiset& __x)
00086       : _Base(__x), _Safe_base() { }
00087 
00088       multiset(const _Base& __x)
00089       : _Base(__x), _Safe_base() { }
00090 
00091 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00092       multiset(multiset&& __x)
00093       : _Base(std::forward<multiset>(__x)), _Safe_base()
00094       { this->_M_swap(__x); }
00095 
00096       multiset(initializer_list<value_type> __l,
00097            const _Compare& __comp = _Compare(),
00098            const allocator_type& __a = allocator_type())
00099       : _Base(__l, __comp, __a), _Safe_base() { }
00100 #endif
00101 
00102       ~multiset() { }
00103 
00104       multiset&
00105       operator=(const multiset& __x)
00106       {
00107     *static_cast<_Base*>(this) = __x;
00108     this->_M_invalidate_all();
00109     return *this;
00110       }
00111 
00112 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00113       multiset&
00114       operator=(multiset&& __x)
00115       {
00116     // NB: DR 1204.
00117     // NB: DR 675.
00118     clear();
00119     swap(__x);
00120     return *this;
00121       }
00122 
00123       multiset&
00124       operator=(initializer_list<value_type> __l)
00125       {
00126     this->clear();
00127     this->insert(__l);
00128     return *this;
00129       }
00130 #endif
00131 
00132       using _Base::get_allocator;
00133 
00134       // iterators:
00135       iterator
00136       begin()
00137       { return iterator(_Base::begin(), this); }
00138 
00139       const_iterator
00140       begin() const
00141       { return const_iterator(_Base::begin(), this); }
00142 
00143       iterator
00144       end()
00145       { return iterator(_Base::end(), this); }
00146 
00147       const_iterator
00148       end() const
00149       { return const_iterator(_Base::end(), this); }
00150 
00151       reverse_iterator
00152       rbegin()
00153       { return reverse_iterator(end()); }
00154 
00155       const_reverse_iterator
00156       rbegin() const
00157       { return const_reverse_iterator(end()); }
00158 
00159       reverse_iterator
00160       rend()
00161       { return reverse_iterator(begin()); }
00162 
00163       const_reverse_iterator
00164       rend() const
00165       { return const_reverse_iterator(begin()); }
00166 
00167 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00168       const_iterator
00169       cbegin() const
00170       { return const_iterator(_Base::begin(), this); }
00171 
00172       const_iterator
00173       cend() const
00174       { return const_iterator(_Base::end(), this); }
00175 
00176       const_reverse_iterator
00177       crbegin() const
00178       { return const_reverse_iterator(end()); }
00179 
00180       const_reverse_iterator
00181       crend() const
00182       { return const_reverse_iterator(begin()); }
00183 #endif
00184 
00185       // capacity:
00186       using _Base::empty;
00187       using _Base::size;
00188       using _Base::max_size;
00189 
00190       // modifiers:
00191       iterator
00192       insert(const value_type& __x)
00193       { return iterator(_Base::insert(__x), this); }
00194 
00195       iterator
00196       insert(iterator __position, const value_type& __x)
00197       {
00198     __glibcxx_check_insert(__position);
00199     return iterator(_Base::insert(__position.base(), __x), this);
00200       }
00201 
00202       template<typename _InputIterator>
00203       void
00204       insert(_InputIterator __first, _InputIterator __last)
00205       {
00206     __glibcxx_check_valid_range(__first, __last);
00207     _Base::insert(__first, __last);
00208       }
00209 
00210 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00211       void
00212       insert(initializer_list<value_type> __l)
00213       { _Base::insert(__l); }
00214 #endif
00215 
00216 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00217       iterator
00218       erase(iterator __position)
00219       {
00220     __glibcxx_check_erase(__position);
00221     __position._M_invalidate();
00222     return iterator(_Base::erase(__position.base()), this);
00223       }
00224 #else
00225       void
00226       erase(iterator __position)
00227       {
00228     __glibcxx_check_erase(__position);
00229     __position._M_invalidate();
00230     _Base::erase(__position.base());
00231       }
00232 #endif
00233 
00234       size_type
00235       erase(const key_type& __x)
00236       {
00237     std::pair<iterator, iterator> __victims = this->equal_range(__x);
00238     size_type __count = 0;
00239     while (__victims.first != __victims.second)
00240     {
00241       iterator __victim = __victims.first++;
00242       __victim._M_invalidate();
00243       _Base::erase(__victim.base());
00244       ++__count;
00245     }
00246     return __count;
00247       }
00248 
00249 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00250       iterator
00251       erase(iterator __first, iterator __last)
00252       {
00253     // _GLIBCXX_RESOLVE_LIB_DEFECTS
00254     // 151. can't currently clear() empty container
00255     __glibcxx_check_erase_range(__first, __last);
00256     while (__first != __last)
00257       this->erase(__first++);
00258     return __last;
00259       }
00260 #else
00261       void
00262       erase(iterator __first, iterator __last)
00263       {
00264     // _GLIBCXX_RESOLVE_LIB_DEFECTS
00265     // 151. can't currently clear() empty container
00266     __glibcxx_check_erase_range(__first, __last);
00267     while (__first != __last)
00268       this->erase(__first++);
00269       }
00270 #endif
00271 
00272       void
00273       swap(multiset& __x)
00274       {
00275     _Base::swap(__x);
00276     this->_M_swap(__x);
00277       }
00278 
00279       void
00280       clear()
00281       { this->erase(begin(), end()); }
00282 
00283       // observers:
00284       using _Base::key_comp;
00285       using _Base::value_comp;
00286 
00287       // multiset operations:
00288       iterator
00289       find(const key_type& __x)
00290       { return iterator(_Base::find(__x), this); }
00291 
00292       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00293       // 214. set::find() missing const overload
00294       const_iterator
00295       find(const key_type& __x) const
00296       { return const_iterator(_Base::find(__x), this); }
00297 
00298       using _Base::count;
00299 
00300       iterator
00301       lower_bound(const key_type& __x)
00302       { return iterator(_Base::lower_bound(__x), this); }
00303 
00304       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00305       // 214. set::find() missing const overload
00306       const_iterator
00307       lower_bound(const key_type& __x) const
00308       { return const_iterator(_Base::lower_bound(__x), this); }
00309 
00310       iterator
00311       upper_bound(const key_type& __x)
00312       { return iterator(_Base::upper_bound(__x), this); }
00313 
00314       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00315       // 214. set::find() missing const overload
00316       const_iterator
00317       upper_bound(const key_type& __x) const
00318       { return const_iterator(_Base::upper_bound(__x), this); }
00319 
00320       std::pair<iterator,iterator>
00321       equal_range(const key_type& __x)
00322       {
00323     typedef typename _Base::iterator _Base_iterator;
00324     std::pair<_Base_iterator, _Base_iterator> __res =
00325         _Base::equal_range(__x);
00326     return std::make_pair(iterator(__res.first, this),
00327                   iterator(__res.second, this));
00328       }
00329 
00330       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00331       // 214. set::find() missing const overload
00332       std::pair<const_iterator,const_iterator>
00333       equal_range(const key_type& __x) const
00334       {
00335     typedef typename _Base::const_iterator _Base_iterator;
00336     std::pair<_Base_iterator, _Base_iterator> __res =
00337         _Base::equal_range(__x);
00338     return std::make_pair(const_iterator(__res.first, this),
00339                   const_iterator(__res.second, this));
00340       }
00341 
00342       _Base&
00343       _M_base() { return *this; }
00344 
00345       const _Base&
00346       _M_base() const { return *this; }
00347 
00348     private:
00349       void
00350       _M_invalidate_all()
00351       {
00352     typedef typename _Base::const_iterator _Base_const_iterator;
00353     typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
00354     this->_M_invalidate_if(_Not_equal(_M_base().end()));
00355       }
00356     };
00357 
00358   template<typename _Key, typename _Compare, typename _Allocator>
00359     inline bool
00360     operator==(const multiset<_Key, _Compare, _Allocator>& __lhs,
00361            const multiset<_Key, _Compare, _Allocator>& __rhs)
00362     { return __lhs._M_base() == __rhs._M_base(); }
00363 
00364   template<typename _Key, typename _Compare, typename _Allocator>
00365     inline bool
00366     operator!=(const multiset<_Key, _Compare, _Allocator>& __lhs,
00367            const multiset<_Key, _Compare, _Allocator>& __rhs)
00368     { return __lhs._M_base() != __rhs._M_base(); }
00369 
00370   template<typename _Key, typename _Compare, typename _Allocator>
00371     inline bool
00372     operator<(const multiset<_Key, _Compare, _Allocator>& __lhs,
00373           const multiset<_Key, _Compare, _Allocator>& __rhs)
00374     { return __lhs._M_base() < __rhs._M_base(); }
00375 
00376   template<typename _Key, typename _Compare, typename _Allocator>
00377     inline bool
00378     operator<=(const multiset<_Key, _Compare, _Allocator>& __lhs,
00379            const multiset<_Key, _Compare, _Allocator>& __rhs)
00380     { return __lhs._M_base() <= __rhs._M_base(); }
00381 
00382   template<typename _Key, typename _Compare, typename _Allocator>
00383     inline bool
00384     operator>=(const multiset<_Key, _Compare, _Allocator>& __lhs,
00385            const multiset<_Key, _Compare, _Allocator>& __rhs)
00386     { return __lhs._M_base() >= __rhs._M_base(); }
00387 
00388   template<typename _Key, typename _Compare, typename _Allocator>
00389     inline bool
00390     operator>(const multiset<_Key, _Compare, _Allocator>& __lhs,
00391           const multiset<_Key, _Compare, _Allocator>& __rhs)
00392     { return __lhs._M_base() > __rhs._M_base(); }
00393 
00394   template<typename _Key, typename _Compare, typename _Allocator>
00395     void
00396     swap(multiset<_Key, _Compare, _Allocator>& __x,
00397      multiset<_Key, _Compare, _Allocator>& __y)
00398     { return __x.swap(__y); }
00399 
00400 } // namespace __debug
00401 } // namespace std
00402 
00403 #endif