debug/set.h

Go to the documentation of this file.
00001 // Debugging set implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 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/set.h
00027  *  This file is a GNU debug extension to the Standard C++ Library.
00028  */
00029 
00030 #ifndef _GLIBCXX_DEBUG_SET_H
00031 #define _GLIBCXX_DEBUG_SET_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::set with safety/checking/debug instrumentation.
00042   template<typename _Key, typename _Compare = std::less<_Key>,
00043        typename _Allocator = std::allocator<_Key> >
00044     class set
00045     : public _GLIBCXX_STD_D::set<_Key,_Compare,_Allocator>,
00046       public __gnu_debug::_Safe_sequence<set<_Key, _Compare, _Allocator> >
00047     {
00048       typedef _GLIBCXX_STD_D::set<_Key, _Compare, _Allocator> _Base;
00049       typedef __gnu_debug::_Safe_sequence<set> _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, set>
00062                                                     iterator;
00063       typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator, set>
00064                                                     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 set(const _Compare& __comp = _Compare(),
00075            const _Allocator& __a = _Allocator())
00076       : _Base(__comp, __a) { }
00077 
00078       template<typename _InputIterator>
00079         set(_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       set(const set& __x)
00086       : _Base(__x), _Safe_base() { }
00087 
00088       set(const _Base& __x)
00089       : _Base(__x), _Safe_base() { }
00090 
00091 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00092       set(set&& __x)
00093       : _Base(std::forward<set>(__x)), _Safe_base()
00094       { this->_M_swap(__x); }
00095 
00096       set(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       ~set() { }
00103 
00104       set&
00105       operator=(const set& __x)
00106       {
00107     *static_cast<_Base*>(this) = __x;
00108     this->_M_invalidate_all();
00109     return *this;
00110       }
00111 
00112 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00113       set&
00114       operator=(set&& __x)
00115       {
00116     // NB: DR 1204.
00117     // NB: DR 675.
00118     clear();
00119     swap(__x);
00120     return *this;
00121       }
00122 
00123       set&
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       std::pair<iterator, bool>
00192       insert(const value_type& __x)
00193       {
00194     typedef typename _Base::iterator _Base_iterator;
00195     std::pair<_Base_iterator, bool> __res = _Base::insert(__x);
00196     return std::pair<iterator, bool>(iterator(__res.first, this),
00197                      __res.second);
00198       }
00199 
00200       iterator
00201       insert(iterator __position, const value_type& __x)
00202       {
00203     __glibcxx_check_insert(__position);
00204     return iterator(_Base::insert(__position.base(), __x), this);
00205       }
00206 
00207       template <typename _InputIterator>
00208         void
00209         insert(_InputIterator __first, _InputIterator __last)
00210         {
00211       __glibcxx_check_valid_range(__first, __last);
00212       _Base::insert(__first, __last);
00213     }
00214 
00215 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00216       void
00217       insert(initializer_list<value_type> __l)
00218       { _Base::insert(__l); }
00219 #endif
00220 
00221 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00222       iterator
00223       erase(iterator __position)
00224       {
00225     __glibcxx_check_erase(__position);
00226     __position._M_invalidate();
00227     return iterator(_Base::erase(__position.base()), this);
00228       }
00229 #else
00230       void
00231       erase(iterator __position)
00232       {
00233     __glibcxx_check_erase(__position);
00234     __position._M_invalidate();
00235     _Base::erase(__position.base());
00236       }
00237 #endif
00238 
00239       size_type
00240       erase(const key_type& __x)
00241       {
00242     iterator __victim = find(__x);
00243     if (__victim == end())
00244           return 0;
00245     else
00246         {
00247       __victim._M_invalidate();
00248       _Base::erase(__victim.base());
00249       return 1;
00250         }
00251       }
00252 
00253 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00254       iterator
00255       erase(iterator __first, iterator __last)
00256       {
00257     // _GLIBCXX_RESOLVE_LIB_DEFECTS
00258     // 151. can't currently clear() empty container
00259     __glibcxx_check_erase_range(__first, __last);
00260     while (__first != __last)
00261       this->erase(__first++);
00262     return __last;
00263       }
00264 #else
00265       void
00266       erase(iterator __first, iterator __last)
00267       {
00268     // _GLIBCXX_RESOLVE_LIB_DEFECTS
00269     // 151. can't currently clear() empty container
00270     __glibcxx_check_erase_range(__first, __last);
00271     while (__first != __last)
00272       this->erase(__first++);
00273       }
00274 #endif
00275 
00276       void
00277       swap(set& __x)
00278       {
00279     _Base::swap(__x);
00280     this->_M_swap(__x);
00281       }
00282 
00283       void
00284       clear()
00285       { this->erase(begin(), end()); }
00286 
00287       // observers:
00288       using _Base::key_comp;
00289       using _Base::value_comp;
00290 
00291       // set operations:
00292       iterator
00293       find(const key_type& __x)
00294       { return iterator(_Base::find(__x), this); }
00295 
00296       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00297       // 214. set::find() missing const overload
00298       const_iterator
00299       find(const key_type& __x) const
00300       { return const_iterator(_Base::find(__x), this); }
00301 
00302       using _Base::count;
00303 
00304       iterator
00305       lower_bound(const key_type& __x)
00306       { return iterator(_Base::lower_bound(__x), this); }
00307 
00308       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00309       // 214. set::find() missing const overload
00310       const_iterator
00311       lower_bound(const key_type& __x) const
00312       { return const_iterator(_Base::lower_bound(__x), this); }
00313 
00314       iterator
00315       upper_bound(const key_type& __x)
00316       { return iterator(_Base::upper_bound(__x), this); }
00317 
00318       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00319       // 214. set::find() missing const overload
00320       const_iterator
00321       upper_bound(const key_type& __x) const
00322       { return const_iterator(_Base::upper_bound(__x), this); }
00323 
00324       std::pair<iterator,iterator>
00325       equal_range(const key_type& __x)
00326       {
00327     typedef typename _Base::iterator _Base_iterator;
00328     std::pair<_Base_iterator, _Base_iterator> __res =
00329         _Base::equal_range(__x);
00330     return std::make_pair(iterator(__res.first, this),
00331                   iterator(__res.second, this));
00332       }
00333 
00334       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00335       // 214. set::find() missing const overload
00336       std::pair<const_iterator,const_iterator>
00337       equal_range(const key_type& __x) const
00338       {
00339     typedef typename _Base::const_iterator _Base_iterator;
00340     std::pair<_Base_iterator, _Base_iterator> __res =
00341         _Base::equal_range(__x);
00342     return std::make_pair(const_iterator(__res.first, this),
00343                   const_iterator(__res.second, this));
00344       }
00345 
00346       _Base&
00347       _M_base() { return *this; }
00348 
00349       const _Base&
00350       _M_base() const { return *this; }
00351 
00352     private:
00353       void
00354       _M_invalidate_all()
00355       {
00356     typedef typename _Base::const_iterator _Base_const_iterator;
00357     typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
00358     this->_M_invalidate_if(_Not_equal(_M_base().end()));
00359       }
00360     };
00361 
00362   template<typename _Key, typename _Compare, typename _Allocator>
00363     inline bool
00364     operator==(const set<_Key, _Compare, _Allocator>& __lhs,
00365            const set<_Key, _Compare, _Allocator>& __rhs)
00366     { return __lhs._M_base() == __rhs._M_base(); }
00367 
00368   template<typename _Key, typename _Compare, typename _Allocator>
00369     inline bool
00370     operator!=(const set<_Key, _Compare, _Allocator>& __lhs,
00371            const set<_Key, _Compare, _Allocator>& __rhs)
00372     { return __lhs._M_base() != __rhs._M_base(); }
00373 
00374   template<typename _Key, typename _Compare, typename _Allocator>
00375     inline bool
00376     operator<(const set<_Key, _Compare, _Allocator>& __lhs,
00377           const set<_Key, _Compare, _Allocator>& __rhs)
00378     { return __lhs._M_base() < __rhs._M_base(); }
00379 
00380   template<typename _Key, typename _Compare, typename _Allocator>
00381     inline bool
00382     operator<=(const set<_Key, _Compare, _Allocator>& __lhs,
00383            const set<_Key, _Compare, _Allocator>& __rhs)
00384     { return __lhs._M_base() <= __rhs._M_base(); }
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     void
00400     swap(set<_Key, _Compare, _Allocator>& __x,
00401      set<_Key, _Compare, _Allocator>& __y)
00402     { return __x.swap(__y); }
00403 
00404 } // namespace __debug
00405 } // namespace std
00406 
00407 #endif