multiset.h

Go to the documentation of this file.
00001 // Debugging multiset implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2003, 2004, 2005, 2006, 2007, 2009
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   template<typename _Key, typename _Compare = std::less<_Key>,
00042        typename _Allocator = std::allocator<_Key> >
00043     class multiset
00044     : public _GLIBCXX_STD_D::multiset<_Key, _Compare, _Allocator>,
00045       public __gnu_debug::_Safe_sequence<multiset<_Key, _Compare, _Allocator> >
00046     {
00047       typedef _GLIBCXX_STD_D::multiset<_Key, _Compare, _Allocator> _Base;
00048       typedef __gnu_debug::_Safe_sequence<multiset> _Safe_base;
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 __gnu_debug::_Safe_iterator<typename _Base::iterator, multiset>
00061       iterator;
00062       typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
00063                       multiset> const_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       typedef std::reverse_iterator<iterator>        reverse_iterator;
00070       typedef std::reverse_iterator<const_iterator>  const_reverse_iterator;
00071 
00072       // 23.3.3.1 construct/copy/destroy:
00073       explicit multiset(const _Compare& __comp = _Compare(),
00074             const _Allocator& __a = _Allocator())
00075       : _Base(__comp, __a) { }
00076 
00077       template<typename _InputIterator>
00078         multiset(_InputIterator __first, _InputIterator __last,
00079          const _Compare& __comp = _Compare(),
00080          const _Allocator& __a = _Allocator())
00081     : _Base(__gnu_debug::__check_valid_range(__first, __last), __last,
00082         __comp, __a) { }
00083 
00084       multiset(const multiset& __x)
00085       : _Base(__x), _Safe_base() { }
00086 
00087       multiset(const _Base& __x)
00088       : _Base(__x), _Safe_base() { }
00089 
00090 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00091       multiset(multiset&& __x)
00092       : _Base(std::forward<multiset>(__x)), _Safe_base()
00093       { this->_M_swap(__x); }
00094 
00095       multiset(initializer_list<value_type> __l,
00096            const _Compare& __comp = _Compare(),
00097            const allocator_type& __a = allocator_type())
00098       : _Base(__l, __comp, __a), _Safe_base() { }
00099 #endif
00100 
00101       ~multiset() { }
00102 
00103       multiset&
00104       operator=(const multiset& __x)
00105       {
00106     *static_cast<_Base*>(this) = __x;
00107     this->_M_invalidate_all();
00108     return *this;
00109       }
00110 
00111 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00112       multiset&
00113       operator=(multiset&& __x)
00114       {
00115         // NB: DR 675.
00116     clear();
00117     swap(__x);
00118     return *this;
00119       }
00120 
00121       multiset&
00122       operator=(initializer_list<value_type> __l)
00123       {
00124     this->clear();
00125     this->insert(__l);
00126     return *this;
00127       }
00128 #endif
00129 
00130       using _Base::get_allocator;
00131 
00132       // iterators:
00133       iterator
00134       begin()
00135       { return iterator(_Base::begin(), this); }
00136 
00137       const_iterator
00138       begin() const
00139       { return const_iterator(_Base::begin(), this); }
00140 
00141       iterator
00142       end()
00143       { return iterator(_Base::end(), this); }
00144 
00145       const_iterator
00146       end() const
00147       { return const_iterator(_Base::end(), this); }
00148 
00149       reverse_iterator
00150       rbegin()
00151       { return reverse_iterator(end()); }
00152 
00153       const_reverse_iterator
00154       rbegin() const
00155       { return const_reverse_iterator(end()); }
00156 
00157       reverse_iterator
00158       rend()
00159       { return reverse_iterator(begin()); }
00160 
00161       const_reverse_iterator
00162       rend() const
00163       { return const_reverse_iterator(begin()); }
00164 
00165 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00166       const_iterator
00167       cbegin() const
00168       { return const_iterator(_Base::begin(), this); }
00169 
00170       const_iterator
00171       cend() const
00172       { return const_iterator(_Base::end(), this); }
00173 
00174       const_reverse_iterator
00175       crbegin() const
00176       { return const_reverse_iterator(end()); }
00177 
00178       const_reverse_iterator
00179       crend() const
00180       { return const_reverse_iterator(begin()); }
00181 #endif
00182 
00183       // capacity:
00184       using _Base::empty;
00185       using _Base::size;
00186       using _Base::max_size;
00187 
00188       // modifiers:
00189       iterator
00190       insert(const value_type& __x)
00191       { return iterator(_Base::insert(__x), this); }
00192 
00193       iterator
00194       insert(iterator __position, const value_type& __x)
00195       {
00196     __glibcxx_check_insert(__position);
00197     return iterator(_Base::insert(__position.base(), __x), this);
00198       }
00199 
00200       template<typename _InputIterator>
00201       void
00202       insert(_InputIterator __first, _InputIterator __last)
00203       {
00204     __glibcxx_check_valid_range(__first, __last);
00205     _Base::insert(__first, __last);
00206       }
00207 
00208 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00209       void
00210       insert(initializer_list<value_type> __l)
00211       { _Base::insert(__l); }
00212 #endif
00213 
00214       void
00215       erase(iterator __position)
00216       {
00217     __glibcxx_check_erase(__position);
00218     __position._M_invalidate();
00219     _Base::erase(__position.base());
00220       }
00221 
00222       size_type
00223       erase(const key_type& __x)
00224       {
00225     std::pair<iterator, iterator> __victims = this->equal_range(__x);
00226     size_type __count = 0;
00227     while (__victims.first != __victims.second)
00228     {
00229       iterator __victim = __victims.first++;
00230       __victim._M_invalidate();
00231       _Base::erase(__victim.base());
00232       ++__count;
00233     }
00234     return __count;
00235       }
00236 
00237       void
00238       erase(iterator __first, iterator __last)
00239       {
00240     // _GLIBCXX_RESOLVE_LIB_DEFECTS
00241     // 151. can't currently clear() empty container
00242     __glibcxx_check_erase_range(__first, __last);
00243     while (__first != __last)
00244     this->erase(__first++);
00245       }
00246 
00247       void
00248 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00249       swap(multiset&& __x)
00250 #else
00251       swap(multiset& __x)
00252 #endif
00253       {
00254     _Base::swap(__x);
00255     this->_M_swap(__x);
00256       }
00257 
00258       void
00259       clear()
00260       { this->erase(begin(), end()); }
00261 
00262       // observers:
00263       using _Base::key_comp;
00264       using _Base::value_comp;
00265 
00266       // multiset operations:
00267       iterator
00268       find(const key_type& __x)
00269       { return iterator(_Base::find(__x), this); }
00270 
00271       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00272       // 214. set::find() missing const overload
00273       const_iterator
00274       find(const key_type& __x) const
00275       { return const_iterator(_Base::find(__x), this); }
00276 
00277       using _Base::count;
00278 
00279       iterator
00280       lower_bound(const key_type& __x)
00281       { return iterator(_Base::lower_bound(__x), this); }
00282 
00283       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00284       // 214. set::find() missing const overload
00285       const_iterator
00286       lower_bound(const key_type& __x) const
00287       { return const_iterator(_Base::lower_bound(__x), this); }
00288 
00289       iterator
00290       upper_bound(const key_type& __x)
00291       { return iterator(_Base::upper_bound(__x), this); }
00292 
00293       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00294       // 214. set::find() missing const overload
00295       const_iterator
00296       upper_bound(const key_type& __x) const
00297       { return const_iterator(_Base::upper_bound(__x), this); }
00298 
00299       std::pair<iterator,iterator>
00300       equal_range(const key_type& __x)
00301       {
00302     typedef typename _Base::iterator _Base_iterator;
00303     std::pair<_Base_iterator, _Base_iterator> __res =
00304         _Base::equal_range(__x);
00305     return std::make_pair(iterator(__res.first, this),
00306                   iterator(__res.second, this));
00307       }
00308 
00309       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00310       // 214. set::find() missing const overload
00311       std::pair<const_iterator,const_iterator>
00312       equal_range(const key_type& __x) const
00313       {
00314     typedef typename _Base::const_iterator _Base_iterator;
00315     std::pair<_Base_iterator, _Base_iterator> __res =
00316         _Base::equal_range(__x);
00317     return std::make_pair(const_iterator(__res.first, this),
00318                   const_iterator(__res.second, this));
00319       }
00320 
00321       _Base&
00322       _M_base() { return *this; }
00323 
00324       const _Base&
00325       _M_base() const { return *this; }
00326 
00327     private:
00328       void
00329       _M_invalidate_all()
00330       {
00331     typedef typename _Base::const_iterator _Base_const_iterator;
00332     typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
00333     this->_M_invalidate_if(_Not_equal(_M_base().end()));
00334       }
00335     };
00336 
00337   template<typename _Key, typename _Compare, typename _Allocator>
00338     inline bool
00339     operator==(const multiset<_Key, _Compare, _Allocator>& __lhs,
00340            const multiset<_Key, _Compare, _Allocator>& __rhs)
00341     { return __lhs._M_base() == __rhs._M_base(); }
00342 
00343   template<typename _Key, typename _Compare, typename _Allocator>
00344     inline bool
00345     operator!=(const multiset<_Key, _Compare, _Allocator>& __lhs,
00346            const multiset<_Key, _Compare, _Allocator>& __rhs)
00347     { return __lhs._M_base() != __rhs._M_base(); }
00348 
00349   template<typename _Key, typename _Compare, typename _Allocator>
00350     inline bool
00351     operator<(const multiset<_Key, _Compare, _Allocator>& __lhs,
00352           const multiset<_Key, _Compare, _Allocator>& __rhs)
00353     { return __lhs._M_base() < __rhs._M_base(); }
00354 
00355   template<typename _Key, typename _Compare, typename _Allocator>
00356     inline bool
00357     operator<=(const multiset<_Key, _Compare, _Allocator>& __lhs,
00358            const multiset<_Key, _Compare, _Allocator>& __rhs)
00359     { return __lhs._M_base() <= __rhs._M_base(); }
00360 
00361   template<typename _Key, typename _Compare, typename _Allocator>
00362     inline bool
00363     operator>=(const multiset<_Key, _Compare, _Allocator>& __lhs,
00364            const multiset<_Key, _Compare, _Allocator>& __rhs)
00365     { return __lhs._M_base() >= __rhs._M_base(); }
00366 
00367   template<typename _Key, typename _Compare, typename _Allocator>
00368     inline bool
00369     operator>(const multiset<_Key, _Compare, _Allocator>& __lhs,
00370           const multiset<_Key, _Compare, _Allocator>& __rhs)
00371     { return __lhs._M_base() > __rhs._M_base(); }
00372 
00373   template<typename _Key, typename _Compare, typename _Allocator>
00374     void
00375     swap(multiset<_Key, _Compare, _Allocator>& __x,
00376      multiset<_Key, _Compare, _Allocator>& __y)
00377     { return __x.swap(__y); }
00378 
00379 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00380   template<typename _Key, typename _Compare, typename _Allocator>
00381     void
00382     swap(multiset<_Key, _Compare, _Allocator>&& __x,
00383      multiset<_Key, _Compare, _Allocator>& __y)
00384     { return __x.swap(__y); }
00385 
00386   template<typename _Key, typename _Compare, typename _Allocator>
00387     void
00388     swap(multiset<_Key, _Compare, _Allocator>& __x,
00389      multiset<_Key, _Compare, _Allocator>&& __y)
00390     { return __x.swap(__y); }
00391 #endif
00392 
00393 } // namespace __debug
00394 } // namespace std
00395 
00396 #endif

Generated on Thu Jul 23 21:16:12 2009 for libstdc++ by  doxygen 1.5.8