debug/deque

Go to the documentation of this file.
00001 // Debugging deque implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2003, 2004, 2005, 2006, 2007
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 2, 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 // You should have received a copy of the GNU General Public License along
00018 // with this library; see the file COPYING.  If not, write to the Free
00019 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
00020 // USA.
00021 
00022 // As a special exception, you may use this file as part of a free software
00023 // library without restriction.  Specifically, if other files instantiate
00024 // templates or use macros or inline functions from this file, or you compile
00025 // this file and link it with other files to produce an executable, this
00026 // file does not by itself cause the resulting executable to be covered by
00027 // the GNU General Public License.  This exception does not however
00028 // invalidate any other reasons why the executable file might be covered by
00029 // the GNU General Public License.
00030 
00031 /** @file debug/deque
00032  *  This file is a GNU debug extension to the Standard C++ Library.
00033  */
00034 
00035 #ifndef _GLIBCXX_DEBUG_DEQUE
00036 #define _GLIBCXX_DEBUG_DEQUE 1
00037 
00038 #include <deque>
00039 #include <debug/safe_sequence.h>
00040 #include <debug/safe_iterator.h>
00041 
00042 namespace std
00043 {
00044 namespace __debug
00045 {
00046   template<typename _Tp, typename _Allocator = std::allocator<_Tp> >
00047     class deque
00048     : public _GLIBCXX_STD_D::deque<_Tp, _Allocator>,
00049       public __gnu_debug::_Safe_sequence<deque<_Tp, _Allocator> >
00050     {
00051       typedef  _GLIBCXX_STD_D::deque<_Tp, _Allocator> _Base;
00052       typedef __gnu_debug::_Safe_sequence<deque> _Safe_base;
00053 
00054     public:
00055       typedef typename _Base::reference             reference;
00056       typedef typename _Base::const_reference       const_reference;
00057 
00058       typedef __gnu_debug::_Safe_iterator<typename _Base::iterator,deque>
00059                             iterator;
00060       typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,deque>
00061                              const_iterator;
00062 
00063       typedef typename _Base::size_type             size_type;
00064       typedef typename _Base::difference_type       difference_type;
00065 
00066       typedef _Tp                   value_type;
00067       typedef _Allocator                allocator_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.2.1.1 construct/copy/destroy:
00074       explicit deque(const _Allocator& __a = _Allocator())
00075       : _Base(__a) { }
00076 
00077       explicit deque(size_type __n, const _Tp& __value = _Tp(),
00078              const _Allocator& __a = _Allocator())
00079       : _Base(__n, __value, __a) { }
00080 
00081       template<class _InputIterator>
00082         deque(_InputIterator __first, _InputIterator __last,
00083           const _Allocator& __a = _Allocator())
00084     : _Base(__gnu_debug::__check_valid_range(__first, __last), __last, __a)
00085         { }
00086 
00087       deque(const deque& __x)
00088       : _Base(__x), _Safe_base() { }
00089 
00090       deque(const _Base& __x)
00091       : _Base(__x), _Safe_base() { }
00092 
00093 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00094       deque(deque&& __x)
00095       : _Base(std::forward<deque>(__x)), _Safe_base()
00096       { this->_M_swap(__x); }
00097 #endif
00098 
00099       ~deque() { }
00100 
00101       deque&
00102       operator=(const deque& __x)
00103       {
00104     *static_cast<_Base*>(this) = __x;
00105     this->_M_invalidate_all();
00106     return *this;
00107       }
00108 
00109 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00110       deque&
00111       operator=(deque&& __x)
00112       {
00113         // NB: DR 675.
00114     clear();
00115     swap(__x);    
00116     return *this;
00117       }
00118 #endif
00119 
00120       template<class _InputIterator>
00121         void
00122         assign(_InputIterator __first, _InputIterator __last)
00123         {
00124       __glibcxx_check_valid_range(__first, __last);
00125       _Base::assign(__first, __last);
00126       this->_M_invalidate_all();
00127     }
00128 
00129       void
00130       assign(size_type __n, const _Tp& __t)
00131       {
00132     _Base::assign(__n, __t);
00133     this->_M_invalidate_all();
00134       }
00135 
00136       using _Base::get_allocator;
00137 
00138       // iterators:
00139       iterator
00140       begin()
00141       { return iterator(_Base::begin(), this); }
00142 
00143       const_iterator
00144       begin() const
00145       { return const_iterator(_Base::begin(), this); }
00146 
00147       iterator
00148       end()
00149       { return iterator(_Base::end(), this); }
00150 
00151       const_iterator
00152       end() const
00153       { return const_iterator(_Base::end(), this); }
00154 
00155       reverse_iterator
00156       rbegin()
00157       { return reverse_iterator(end()); }
00158 
00159       const_reverse_iterator
00160       rbegin() const
00161       { return const_reverse_iterator(end()); }
00162 
00163       reverse_iterator
00164       rend()
00165       { return reverse_iterator(begin()); }
00166 
00167       const_reverse_iterator
00168       rend() const
00169       { return const_reverse_iterator(begin()); }
00170 
00171 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00172       const_iterator
00173       cbegin() const
00174       { return const_iterator(_Base::begin(), this); }
00175 
00176       const_iterator
00177       cend() const
00178       { return const_iterator(_Base::end(), this); }
00179 
00180       const_reverse_iterator
00181       crbegin() const
00182       { return const_reverse_iterator(end()); }
00183 
00184       const_reverse_iterator
00185       crend() const
00186       { return const_reverse_iterator(begin()); }
00187 #endif
00188 
00189       // 23.2.1.2 capacity:
00190       using _Base::size;
00191       using _Base::max_size;
00192 
00193       void
00194       resize(size_type __sz, _Tp __c = _Tp())
00195       {
00196     typedef typename _Base::const_iterator _Base_const_iterator;
00197     typedef __gnu_debug::_After_nth_from<_Base_const_iterator> _After_nth;
00198 
00199     bool __invalidate_all = __sz > this->size();
00200     if (__sz < this->size())
00201       this->_M_invalidate_if(_After_nth(__sz, _M_base().begin()));
00202 
00203     _Base::resize(__sz, __c);
00204 
00205     if (__invalidate_all)
00206       this->_M_invalidate_all();
00207       }
00208 
00209       using _Base::empty;
00210 
00211       // element access:
00212       reference
00213       operator[](size_type __n)
00214       {
00215     __glibcxx_check_subscript(__n);
00216     return _M_base()[__n];
00217       }
00218 
00219       const_reference
00220       operator[](size_type __n) const
00221       {
00222     __glibcxx_check_subscript(__n);
00223     return _M_base()[__n];
00224       }
00225 
00226       using _Base::at;
00227 
00228       reference
00229       front()
00230       {
00231     __glibcxx_check_nonempty();
00232     return _Base::front();
00233       }
00234 
00235       const_reference
00236       front() const
00237       {
00238     __glibcxx_check_nonempty();
00239     return _Base::front();
00240       }
00241 
00242       reference
00243       back()
00244       {
00245     __glibcxx_check_nonempty();
00246     return _Base::back();
00247       }
00248 
00249       const_reference
00250       back() const
00251       {
00252     __glibcxx_check_nonempty();
00253     return _Base::back();
00254       }
00255 
00256       // 23.2.1.3 modifiers:
00257 #ifndef __GXX_EXPERIMENTAL_CXX0X__
00258       void
00259       push_front(const _Tp& __x)
00260       {
00261     _Base::push_front(__x);
00262     this->_M_invalidate_all();
00263       }
00264 
00265       void
00266       push_back(const _Tp& __x)
00267       {
00268     _Base::push_back(__x);
00269     this->_M_invalidate_all();
00270       }
00271 #else
00272       template<typename... _Args>
00273         void
00274         push_front(_Args&&... __args)
00275     {
00276       _Base::push_front(std::forward<_Args>(__args)...);
00277       this->_M_invalidate_all();
00278     }
00279 
00280       template<typename... _Args>
00281         void
00282         push_back(_Args&&... __args)
00283     {
00284       _Base::push_back(std::forward<_Args>(__args)...);
00285       this->_M_invalidate_all();
00286     }
00287 
00288       template<typename... _Args>
00289         iterator
00290         emplace(iterator __position, _Args&&... __args)
00291     {
00292       __glibcxx_check_insert(__position);
00293       typename _Base::iterator __res = _Base::emplace(__position.base(),
00294                         std::forward<_Args>(__args)...);
00295       this->_M_invalidate_all();
00296       return iterator(__res, this);
00297     }
00298 #endif
00299 
00300       iterator
00301       insert(iterator __position, const _Tp& __x)
00302       {
00303     __glibcxx_check_insert(__position);
00304     typename _Base::iterator __res = _Base::insert(__position.base(), __x);
00305     this->_M_invalidate_all();
00306     return iterator(__res, this);
00307       }
00308 
00309 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00310       iterator
00311       insert(iterator __position, _Tp&& __x)
00312       { return emplace(__position, std::move(__x)); }
00313 #endif
00314 
00315       void
00316       insert(iterator __position, size_type __n, const _Tp& __x)
00317       {
00318     __glibcxx_check_insert(__position);
00319     _Base::insert(__position.base(), __n, __x);
00320     this->_M_invalidate_all();
00321       }
00322 
00323       template<class _InputIterator>
00324         void
00325         insert(iterator __position,
00326            _InputIterator __first, _InputIterator __last)
00327         {
00328       __glibcxx_check_insert_range(__position, __first, __last);
00329       _Base::insert(__position.base(), __first, __last);
00330       this->_M_invalidate_all();
00331     }
00332 
00333       void
00334       pop_front()
00335       {
00336     __glibcxx_check_nonempty();
00337     iterator __victim = begin();
00338     __victim._M_invalidate();
00339     _Base::pop_front();
00340       }
00341 
00342       void
00343       pop_back()
00344       {
00345     __glibcxx_check_nonempty();
00346     iterator __victim = end();
00347     --__victim;
00348     __victim._M_invalidate();
00349     _Base::pop_back();
00350       }
00351 
00352       iterator
00353       erase(iterator __position)
00354       {
00355     __glibcxx_check_erase(__position);
00356     if (__position == begin() || __position == end()-1)
00357       {
00358         __position._M_invalidate();
00359         return iterator(_Base::erase(__position.base()), this);
00360       }
00361     else
00362       {
00363         typename _Base::iterator __res = _Base::erase(__position.base());
00364         this->_M_invalidate_all();
00365         return iterator(__res, this);
00366       }
00367       }
00368 
00369       iterator
00370       erase(iterator __first, iterator __last)
00371       {
00372     // _GLIBCXX_RESOLVE_LIB_DEFECTS
00373     // 151. can't currently clear() empty container
00374     __glibcxx_check_erase_range(__first, __last);
00375         if (__first == begin() || __last == end())
00376       {
00377         this->_M_detach_singular();
00378         for (iterator __position = __first; __position != __last; )
00379           {
00380         iterator __victim = __position++;
00381         __victim._M_invalidate();
00382           }
00383         try
00384           {
00385         return iterator(_Base::erase(__first.base(), __last.base()),
00386                 this);
00387           }
00388         catch(...)
00389           {
00390         this->_M_revalidate_singular();
00391         __throw_exception_again;
00392           }
00393       }
00394     else
00395       {
00396         typename _Base::iterator __res = _Base::erase(__first.base(),
00397                               __last.base());
00398         this->_M_invalidate_all();
00399         return iterator(__res, this);
00400       }
00401       }
00402 
00403       void
00404 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00405       swap(deque&& __x)
00406 #else
00407       swap(deque& __x)
00408 #endif
00409       {
00410     _Base::swap(__x);
00411     this->_M_swap(__x);
00412       }
00413 
00414       void
00415       clear()
00416       {
00417     _Base::clear();
00418     this->_M_invalidate_all();
00419       }
00420 
00421       _Base&
00422       _M_base()       { return *this; }
00423 
00424       const _Base&
00425       _M_base() const { return *this; }
00426     };
00427 
00428   template<typename _Tp, typename _Alloc>
00429     inline bool
00430     operator==(const deque<_Tp, _Alloc>& __lhs,
00431            const deque<_Tp, _Alloc>& __rhs)
00432     { return __lhs._M_base() == __rhs._M_base(); }
00433 
00434   template<typename _Tp, typename _Alloc>
00435     inline bool
00436     operator!=(const deque<_Tp, _Alloc>& __lhs,
00437            const deque<_Tp, _Alloc>& __rhs)
00438     { return __lhs._M_base() != __rhs._M_base(); }
00439 
00440   template<typename _Tp, typename _Alloc>
00441     inline bool
00442     operator<(const deque<_Tp, _Alloc>& __lhs,
00443           const deque<_Tp, _Alloc>& __rhs)
00444     { return __lhs._M_base() < __rhs._M_base(); }
00445 
00446   template<typename _Tp, typename _Alloc>
00447     inline bool
00448     operator<=(const deque<_Tp, _Alloc>& __lhs,
00449            const deque<_Tp, _Alloc>& __rhs)
00450     { return __lhs._M_base() <= __rhs._M_base(); }
00451 
00452   template<typename _Tp, typename _Alloc>
00453     inline bool
00454     operator>=(const deque<_Tp, _Alloc>& __lhs,
00455            const deque<_Tp, _Alloc>& __rhs)
00456     { return __lhs._M_base() >= __rhs._M_base(); }
00457 
00458   template<typename _Tp, typename _Alloc>
00459     inline bool
00460     operator>(const deque<_Tp, _Alloc>& __lhs,
00461           const deque<_Tp, _Alloc>& __rhs)
00462     { return __lhs._M_base() > __rhs._M_base(); }
00463 
00464   template<typename _Tp, typename _Alloc>
00465     inline void
00466     swap(deque<_Tp, _Alloc>& __lhs, deque<_Tp, _Alloc>& __rhs)
00467     { __lhs.swap(__rhs); }
00468 
00469 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00470   template<typename _Tp, typename _Alloc>
00471     inline void
00472     swap(deque<_Tp, _Alloc>&& __lhs, deque<_Tp, _Alloc>& __rhs)
00473     { __lhs.swap(__rhs); }
00474 
00475   template<typename _Tp, typename _Alloc>
00476     inline void
00477     swap(deque<_Tp, _Alloc>& __lhs, deque<_Tp, _Alloc>&& __rhs)
00478     { __lhs.swap(__rhs); }
00479 #endif
00480 
00481 } // namespace __debug
00482 } // namespace std
00483 
00484 #endif

Generated on Wed Mar 26 00:42:57 2008 for libstdc++ by  doxygen 1.5.1