debug/vector

Go to the documentation of this file.
00001 // Debugging vector implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2003, 2004, 2005
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/vector
00032  *  This file is a GNU debug extension to the Standard C++ Library.
00033  */
00034 
00035 #ifndef _GLIBCXX_DEBUG_VECTOR
00036 #define _GLIBCXX_DEBUG_VECTOR 1
00037 
00038 #include <vector>
00039 #include <utility>
00040 #include <debug/safe_sequence.h>
00041 #include <debug/safe_iterator.h>
00042 
00043 namespace std
00044 {
00045 namespace __debug
00046 {
00047   template<typename _Tp,
00048        typename _Allocator = std::allocator<_Tp> >
00049     class vector
00050     : public _GLIBCXX_STD::vector<_Tp, _Allocator>,
00051       public __gnu_debug::_Safe_sequence<vector<_Tp, _Allocator> >
00052     {
00053       typedef _GLIBCXX_STD::vector<_Tp, _Allocator> _Base;
00054       typedef __gnu_debug::_Safe_sequence<vector>              _Safe_base;
00055 
00056       typedef typename _Base::const_iterator _Base_const_iterator;
00057       typedef __gnu_debug::_After_nth_from<_Base_const_iterator> _After_nth;
00058 
00059     public:
00060       typedef typename _Base::reference             reference;
00061       typedef typename _Base::const_reference       const_reference;
00062 
00063       typedef __gnu_debug::_Safe_iterator<typename _Base::iterator,vector>
00064       iterator;
00065       typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,vector>
00066       const_iterator;
00067 
00068       typedef typename _Base::size_type             size_type;
00069       typedef typename _Base::difference_type       difference_type;
00070 
00071       typedef _Tp                   value_type;
00072       typedef _Allocator                allocator_type;
00073       typedef typename _Base::pointer               pointer;
00074       typedef typename _Base::const_pointer         const_pointer;
00075       typedef std::reverse_iterator<iterator>       reverse_iterator;
00076       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
00077 
00078       // 23.2.4.1 construct/copy/destroy:
00079       explicit vector(const _Allocator& __a = _Allocator())
00080       : _Base(__a), _M_guaranteed_capacity(0) { }
00081 
00082       explicit vector(size_type __n, const _Tp& __value = _Tp(),
00083               const _Allocator& __a = _Allocator())
00084       : _Base(__n, __value, __a), _M_guaranteed_capacity(__n) { }
00085 
00086       template<class _InputIterator>
00087         vector(_InputIterator __first, _InputIterator __last,
00088            const _Allocator& __a = _Allocator())
00089     : _Base(__gnu_debug::__check_valid_range(__first, __last),
00090         __last, __a),
00091       _M_guaranteed_capacity(0)
00092         { _M_update_guaranteed_capacity(); }
00093 
00094       vector(const vector<_Tp,_Allocator>& __x)
00095       : _Base(__x), _Safe_base(), _M_guaranteed_capacity(__x.size()) { }
00096 
00097       /// Construction from a release-mode vector
00098       vector(const _Base& __x)
00099       : _Base(__x), _Safe_base(), _M_guaranteed_capacity(__x.size()) { }
00100 
00101       ~vector() { }
00102 
00103       vector<_Tp,_Allocator>&
00104       operator=(const vector<_Tp,_Allocator>& __x)
00105       {
00106     static_cast<_Base&>(*this) = __x;
00107     this->_M_invalidate_all();
00108     _M_update_guaranteed_capacity();
00109     return *this;
00110       }
00111 
00112       template<typename _InputIterator>
00113         void
00114         assign(_InputIterator __first, _InputIterator __last)
00115         {
00116       __glibcxx_check_valid_range(__first, __last);
00117       _Base::assign(__first, __last);
00118       this->_M_invalidate_all();
00119       _M_update_guaranteed_capacity();
00120     }
00121 
00122       void
00123       assign(size_type __n, const _Tp& __u)
00124       {
00125     _Base::assign(__n, __u);
00126     this->_M_invalidate_all();
00127     _M_update_guaranteed_capacity();
00128       }
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       // 23.2.4.2 capacity:
00166       using _Base::size;
00167       using _Base::max_size;
00168 
00169       void
00170       resize(size_type __sz, _Tp __c = _Tp())
00171       {
00172     bool __realloc = _M_requires_reallocation(__sz);
00173     if (__sz < this->size())
00174       this->_M_invalidate_if(_After_nth(__sz, _M_base().begin()));
00175     _Base::resize(__sz, __c);
00176     if (__realloc)
00177       this->_M_invalidate_all();
00178       }
00179 
00180       using _Base::capacity;
00181       using _Base::empty;
00182 
00183       void
00184       reserve(size_type __n)
00185       {
00186     bool __realloc = _M_requires_reallocation(__n);
00187     _Base::reserve(__n);
00188     if (__n > _M_guaranteed_capacity)
00189       _M_guaranteed_capacity = __n;
00190     if (__realloc)
00191       this->_M_invalidate_all();
00192       }
00193 
00194       // element access:
00195       reference
00196       operator[](size_type __n)
00197       {
00198     __glibcxx_check_subscript(__n);
00199     return _M_base()[__n];
00200       }
00201 
00202       const_reference
00203       operator[](size_type __n) const
00204       {
00205     __glibcxx_check_subscript(__n);
00206     return _M_base()[__n];
00207       }
00208 
00209       using _Base::at;
00210 
00211       reference
00212       front()
00213       {
00214     __glibcxx_check_nonempty();
00215     return _Base::front();
00216       }
00217 
00218       const_reference
00219       front() const
00220       {
00221     __glibcxx_check_nonempty();
00222     return _Base::front();
00223       }
00224 
00225       reference
00226       back()
00227       {
00228     __glibcxx_check_nonempty();
00229     return _Base::back();
00230       }
00231 
00232       const_reference
00233       back() const
00234       {
00235     __glibcxx_check_nonempty();
00236     return _Base::back();
00237       }
00238 
00239       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00240       // DR 464. Suggestion for new member functions in standard containers.
00241       using _Base::data;
00242 
00243       // 23.2.4.3 modifiers:
00244       void
00245       push_back(const _Tp& __x)
00246       {
00247     bool __realloc = _M_requires_reallocation(this->size() + 1);
00248     _Base::push_back(__x);
00249     if (__realloc)
00250       this->_M_invalidate_all();
00251     _M_update_guaranteed_capacity();
00252       }
00253 
00254       void
00255       pop_back()
00256       {
00257     __glibcxx_check_nonempty();
00258     iterator __victim = end() - 1;
00259     __victim._M_invalidate();
00260     _Base::pop_back();
00261       }
00262 
00263       iterator
00264       insert(iterator __position, const _Tp& __x)
00265       {
00266     __glibcxx_check_insert(__position);
00267     bool __realloc = _M_requires_reallocation(this->size() + 1);
00268     difference_type __offset = __position - begin();
00269     typename _Base::iterator __res = _Base::insert(__position.base(),__x);
00270     if (__realloc)
00271       this->_M_invalidate_all();
00272     else
00273       this->_M_invalidate_if(_After_nth(__offset, _M_base().begin()));
00274     _M_update_guaranteed_capacity();
00275     return iterator(__res, this);
00276       }
00277 
00278       void
00279       insert(iterator __position, size_type __n, const _Tp& __x)
00280       {
00281     __glibcxx_check_insert(__position);
00282     bool __realloc = _M_requires_reallocation(this->size() + __n);
00283     difference_type __offset = __position - begin();
00284     _Base::insert(__position.base(), __n, __x);
00285     if (__realloc)
00286       this->_M_invalidate_all();
00287     else
00288       this->_M_invalidate_if(_After_nth(__offset, _M_base().begin()));
00289     _M_update_guaranteed_capacity();
00290       }
00291 
00292       template<class _InputIterator>
00293         void
00294         insert(iterator __position,
00295            _InputIterator __first, _InputIterator __last)
00296         {
00297       __glibcxx_check_insert_range(__position, __first, __last);
00298 
00299       /* Hard to guess if invalidation will occur, because __last
00300          - __first can't be calculated in all cases, so we just
00301          punt here by checking if it did occur. */
00302       typename _Base::iterator __old_begin = _M_base().begin();
00303       difference_type __offset = __position - begin();
00304       _Base::insert(__position.base(), __first, __last);
00305 
00306       if (_M_base().begin() != __old_begin)
00307         this->_M_invalidate_all();
00308       else
00309         this->_M_invalidate_if(_After_nth(__offset, _M_base().begin()));
00310       _M_update_guaranteed_capacity();
00311     }
00312 
00313       iterator
00314       erase(iterator __position)
00315       {
00316     __glibcxx_check_erase(__position);
00317     difference_type __offset = __position - begin();
00318     typename _Base::iterator __res = _Base::erase(__position.base());
00319     this->_M_invalidate_if(_After_nth(__offset, _M_base().begin()));
00320     return iterator(__res, this);
00321       }
00322 
00323       iterator
00324       erase(iterator __first, iterator __last)
00325       {
00326     // _GLIBCXX_RESOLVE_LIB_DEFECTS
00327     // 151. can't currently clear() empty container
00328     __glibcxx_check_erase_range(__first, __last);
00329 
00330     difference_type __offset = __first - begin();
00331     typename _Base::iterator __res = _Base::erase(__first.base(),
00332                              __last.base());
00333     this->_M_invalidate_if(_After_nth(__offset, _M_base().begin()));
00334     return iterator(__res, this);
00335       }
00336 
00337       void
00338       swap(vector<_Tp,_Allocator>& __x)
00339       {
00340     _Base::swap(__x);
00341     this->_M_swap(__x);
00342         std::swap(_M_guaranteed_capacity, __x._M_guaranteed_capacity);
00343       }
00344 
00345       void
00346       clear()
00347       {
00348     _Base::clear();
00349     this->_M_invalidate_all();
00350         _M_guaranteed_capacity = 0;
00351       }
00352 
00353       _Base&
00354       _M_base() { return *this; }
00355 
00356       const _Base&
00357       _M_base() const { return *this; }
00358 
00359     private:
00360       size_type _M_guaranteed_capacity;
00361 
00362       bool
00363       _M_requires_reallocation(size_type __elements)
00364       {
00365 #ifdef _GLIBCXX_DEBUG_PEDANTIC
00366     return __elements > this->capacity();
00367 #else
00368     return __elements > _M_guaranteed_capacity;
00369 #endif
00370       }
00371 
00372       void
00373       _M_update_guaranteed_capacity()
00374       {
00375     if (this->size() > _M_guaranteed_capacity)
00376       _M_guaranteed_capacity = this->size();
00377       }
00378     };
00379 
00380   template<typename _Tp, typename _Alloc>
00381     inline bool
00382     operator==(const vector<_Tp, _Alloc>& __lhs,
00383            const vector<_Tp, _Alloc>& __rhs)
00384     { return __lhs._M_base() == __rhs._M_base(); }
00385 
00386   template<typename _Tp, typename _Alloc>
00387     inline bool
00388     operator!=(const vector<_Tp, _Alloc>& __lhs,
00389            const vector<_Tp, _Alloc>& __rhs)
00390     { return __lhs._M_base() != __rhs._M_base(); }
00391 
00392   template<typename _Tp, typename _Alloc>
00393     inline bool
00394     operator<(const vector<_Tp, _Alloc>& __lhs,
00395           const vector<_Tp, _Alloc>& __rhs)
00396     { return __lhs._M_base() < __rhs._M_base(); }
00397 
00398   template<typename _Tp, typename _Alloc>
00399     inline bool
00400     operator<=(const vector<_Tp, _Alloc>& __lhs,
00401            const vector<_Tp, _Alloc>& __rhs)
00402     { return __lhs._M_base() <= __rhs._M_base(); }
00403 
00404   template<typename _Tp, typename _Alloc>
00405     inline bool
00406     operator>=(const vector<_Tp, _Alloc>& __lhs,
00407            const vector<_Tp, _Alloc>& __rhs)
00408     { return __lhs._M_base() >= __rhs._M_base(); }
00409 
00410   template<typename _Tp, typename _Alloc>
00411     inline bool
00412     operator>(const vector<_Tp, _Alloc>& __lhs,
00413           const vector<_Tp, _Alloc>& __rhs)
00414     { return __lhs._M_base() > __rhs._M_base(); }
00415 
00416   template<typename _Tp, typename _Alloc>
00417     inline void
00418     swap(vector<_Tp, _Alloc>& __lhs, vector<_Tp, _Alloc>& __rhs)
00419     { __lhs.swap(__rhs); }
00420 } // namespace __debug
00421 } // namespace std
00422 
00423 #endif

Generated on Thu Nov 1 13:13:07 2007 for libstdc++ by  doxygen 1.5.1