# 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