# vector

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