debug/vector

Go to the documentation of this file.
00001 // Debugging vector implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009
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/vector
00027  *  This file is a GNU debug extension to the Standard C++ Library.
00028  */
00029 
00030 #ifndef _GLIBCXX_DEBUG_VECTOR
00031 #define _GLIBCXX_DEBUG_VECTOR 1
00032 
00033 #include <vector>
00034 #include <utility>
00035 #include <debug/safe_sequence.h>
00036 #include <debug/safe_iterator.h>
00037 
00038 namespace std
00039 {
00040 namespace __debug
00041 {
00042   template<typename _Tp,
00043        typename _Allocator = std::allocator<_Tp> >
00044     class vector
00045     : public _GLIBCXX_STD_D::vector<_Tp, _Allocator>,
00046       public __gnu_debug::_Safe_sequence<vector<_Tp, _Allocator> >
00047     {
00048       typedef _GLIBCXX_STD_D::vector<_Tp, _Allocator> _Base;
00049       typedef __gnu_debug::_Safe_sequence<vector>              _Safe_base;
00050 
00051       typedef typename _Base::const_iterator _Base_const_iterator;
00052       typedef __gnu_debug::_After_nth_from<_Base_const_iterator> _After_nth;
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,vector>
00059       iterator;
00060       typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,vector>
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.4.1 construct/copy/destroy:
00074       explicit vector(const _Allocator& __a = _Allocator())
00075       : _Base(__a), _M_guaranteed_capacity(0) { }
00076 
00077       explicit vector(size_type __n, const _Tp& __value = _Tp(),
00078               const _Allocator& __a = _Allocator())
00079       : _Base(__n, __value, __a), _M_guaranteed_capacity(__n) { }
00080 
00081       template<class _InputIterator>
00082         vector(_InputIterator __first, _InputIterator __last,
00083            const _Allocator& __a = _Allocator())
00084     : _Base(__gnu_debug::__check_valid_range(__first, __last),
00085         __last, __a),
00086       _M_guaranteed_capacity(0)
00087         { _M_update_guaranteed_capacity(); }
00088 
00089       vector(const vector& __x)
00090       : _Base(__x), _Safe_base(), _M_guaranteed_capacity(__x.size()) { }
00091 
00092       /// Construction from a release-mode vector
00093       vector(const _Base& __x)
00094       : _Base(__x), _Safe_base(), _M_guaranteed_capacity(__x.size()) { }
00095 
00096 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00097       vector(vector&& __x)
00098       : _Base(std::forward<vector>(__x)), _Safe_base(),
00099     _M_guaranteed_capacity(this->size())
00100       {
00101     this->_M_swap(__x);
00102     __x._M_guaranteed_capacity = 0;
00103       }
00104 
00105       vector(initializer_list<value_type> __l,
00106          const allocator_type& __a = allocator_type())
00107       : _Base(__l, __a), _Safe_base(),
00108     _M_guaranteed_capacity(__l.size()) { }
00109 #endif
00110 
00111       ~vector() { }
00112 
00113       vector&
00114       operator=(const vector& __x)
00115       {
00116     static_cast<_Base&>(*this) = __x;
00117     this->_M_invalidate_all();
00118     _M_update_guaranteed_capacity();
00119     return *this;
00120       }
00121 
00122 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00123       vector&
00124       operator=(vector&& __x)
00125       {
00126         // NB: DR 675.
00127     clear();
00128     swap(__x);
00129     return *this;
00130       }
00131 
00132       vector&
00133       operator=(initializer_list<value_type> __l)
00134       {
00135     static_cast<_Base&>(*this) = __l;
00136     this->_M_invalidate_all();
00137     _M_update_guaranteed_capacity();
00138     return *this;
00139       }
00140 #endif
00141 
00142       template<typename _InputIterator>
00143         void
00144         assign(_InputIterator __first, _InputIterator __last)
00145         {
00146       __glibcxx_check_valid_range(__first, __last);
00147       _Base::assign(__first, __last);
00148       this->_M_invalidate_all();
00149       _M_update_guaranteed_capacity();
00150     }
00151 
00152       void
00153       assign(size_type __n, const _Tp& __u)
00154       {
00155     _Base::assign(__n, __u);
00156     this->_M_invalidate_all();
00157     _M_update_guaranteed_capacity();
00158       }
00159 
00160 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00161       void
00162       assign(initializer_list<value_type> __l)
00163       {
00164     _Base::assign(__l);
00165     this->_M_invalidate_all();
00166     _M_update_guaranteed_capacity();
00167       }
00168 #endif
00169 
00170       using _Base::get_allocator;
00171 
00172       // iterators:
00173       iterator
00174       begin()
00175       { return iterator(_Base::begin(), this); }
00176 
00177       const_iterator
00178       begin() const
00179       { return const_iterator(_Base::begin(), this); }
00180 
00181       iterator
00182       end()
00183       { return iterator(_Base::end(), this); }
00184 
00185       const_iterator
00186       end() const
00187       { return const_iterator(_Base::end(), this); }
00188 
00189       reverse_iterator
00190       rbegin()
00191       { return reverse_iterator(end()); }
00192 
00193       const_reverse_iterator
00194       rbegin() const
00195       { return const_reverse_iterator(end()); }
00196 
00197       reverse_iterator
00198       rend()
00199       { return reverse_iterator(begin()); }
00200 
00201       const_reverse_iterator
00202       rend() const
00203       { return const_reverse_iterator(begin()); }
00204 
00205 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00206       const_iterator
00207       cbegin() const
00208       { return const_iterator(_Base::begin(), this); }
00209 
00210       const_iterator
00211       cend() const
00212       { return const_iterator(_Base::end(), this); }
00213 
00214       const_reverse_iterator
00215       crbegin() const
00216       { return const_reverse_iterator(end()); }
00217 
00218       const_reverse_iterator
00219       crend() const
00220       { return const_reverse_iterator(begin()); }
00221 #endif
00222 
00223       // 23.2.4.2 capacity:
00224       using _Base::size;
00225       using _Base::max_size;
00226 
00227       void
00228       resize(size_type __sz, _Tp __c = _Tp())
00229       {
00230     bool __realloc = _M_requires_reallocation(__sz);
00231     if (__sz < this->size())
00232       this->_M_invalidate_if(_After_nth(__sz, _M_base().begin()));
00233     _Base::resize(__sz, __c);
00234     if (__realloc)
00235       this->_M_invalidate_all();
00236       }
00237 
00238       size_type
00239       capacity() const
00240       {
00241 #ifdef _GLIBCXX_DEBUG_PEDANTIC
00242     return _M_guaranteed_capacity;
00243 #else
00244     return _Base::capacity();
00245 #endif
00246       }
00247 
00248       using _Base::empty;
00249 
00250       void
00251       reserve(size_type __n)
00252       {
00253     bool __realloc = _M_requires_reallocation(__n);
00254     _Base::reserve(__n);
00255     if (__n > _M_guaranteed_capacity)
00256       _M_guaranteed_capacity = __n;
00257     if (__realloc)
00258       this->_M_invalidate_all();
00259       }
00260 
00261       // element access:
00262       reference
00263       operator[](size_type __n)
00264       {
00265     __glibcxx_check_subscript(__n);
00266     return _M_base()[__n];
00267       }
00268 
00269       const_reference
00270       operator[](size_type __n) const
00271       {
00272     __glibcxx_check_subscript(__n);
00273     return _M_base()[__n];
00274       }
00275 
00276       using _Base::at;
00277 
00278       reference
00279       front()
00280       {
00281     __glibcxx_check_nonempty();
00282     return _Base::front();
00283       }
00284 
00285       const_reference
00286       front() const
00287       {
00288     __glibcxx_check_nonempty();
00289     return _Base::front();
00290       }
00291 
00292       reference
00293       back()
00294       {
00295     __glibcxx_check_nonempty();
00296     return _Base::back();
00297       }
00298 
00299       const_reference
00300       back() const
00301       {
00302     __glibcxx_check_nonempty();
00303     return _Base::back();
00304       }
00305 
00306       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00307       // DR 464. Suggestion for new member functions in standard containers.
00308       using _Base::data;
00309 
00310       // 23.2.4.3 modifiers:
00311       void
00312       push_back(const _Tp& __x)
00313       {
00314     bool __realloc = _M_requires_reallocation(this->size() + 1);
00315     _Base::push_back(__x);
00316     if (__realloc)
00317       this->_M_invalidate_all();
00318     _M_update_guaranteed_capacity();
00319       }
00320 
00321 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00322       template<typename _Up = _Tp>
00323         typename __gnu_cxx::__enable_if<!std::__are_same<_Up, bool>::__value,
00324                     void>::__type
00325         push_back(_Tp&& __x)
00326     { emplace_back(std::move(__x)); }
00327 
00328       template<typename... _Args>
00329         void
00330         emplace_back(_Args&&... __args)
00331     {
00332       bool __realloc = _M_requires_reallocation(this->size() + 1);
00333       _Base::emplace_back(std::forward<_Args>(__args)...);
00334       if (__realloc)
00335         this->_M_invalidate_all();
00336       _M_update_guaranteed_capacity();
00337     }
00338 #endif
00339 
00340       void
00341       pop_back()
00342       {
00343     __glibcxx_check_nonempty();
00344     iterator __victim = end() - 1;
00345     __victim._M_invalidate();
00346     _Base::pop_back();
00347       }
00348 
00349 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00350       template<typename... _Args>
00351         iterator
00352         emplace(iterator __position, _Args&&... __args)
00353     {
00354       __glibcxx_check_insert(__position);
00355       bool __realloc = _M_requires_reallocation(this->size() + 1);
00356       difference_type __offset = __position - begin();
00357       typename _Base::iterator __res = _Base::emplace(__position.base(),
00358                         std::forward<_Args>(__args)...);
00359       if (__realloc)
00360         this->_M_invalidate_all();
00361       else
00362         this->_M_invalidate_if(_After_nth(__offset, _M_base().begin()));
00363       _M_update_guaranteed_capacity();
00364       return iterator(__res, this);
00365     }
00366 #endif
00367 
00368       iterator
00369       insert(iterator __position, const _Tp& __x)
00370       {
00371     __glibcxx_check_insert(__position);
00372     bool __realloc = _M_requires_reallocation(this->size() + 1);
00373     difference_type __offset = __position - begin();
00374     typename _Base::iterator __res = _Base::insert(__position.base(),__x);
00375     if (__realloc)
00376       this->_M_invalidate_all();
00377     else
00378       this->_M_invalidate_if(_After_nth(__offset, _M_base().begin()));
00379     _M_update_guaranteed_capacity();
00380     return iterator(__res, this);
00381       }
00382 
00383 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00384       template<typename _Up = _Tp>
00385         typename __gnu_cxx::__enable_if<!std::__are_same<_Up, bool>::__value,
00386                     iterator>::__type
00387         insert(iterator __position, _Tp&& __x)
00388         { return emplace(__position, std::move(__x)); }
00389 
00390       void
00391       insert(iterator __position, initializer_list<value_type> __l)
00392       { this->insert(__position, __l.begin(), __l.end()); }
00393 #endif
00394 
00395       void
00396       insert(iterator __position, size_type __n, const _Tp& __x)
00397       {
00398     __glibcxx_check_insert(__position);
00399     bool __realloc = _M_requires_reallocation(this->size() + __n);
00400     difference_type __offset = __position - begin();
00401     _Base::insert(__position.base(), __n, __x);
00402     if (__realloc)
00403       this->_M_invalidate_all();
00404     else
00405       this->_M_invalidate_if(_After_nth(__offset, _M_base().begin()));
00406     _M_update_guaranteed_capacity();
00407       }
00408 
00409       template<class _InputIterator>
00410         void
00411         insert(iterator __position,
00412            _InputIterator __first, _InputIterator __last)
00413         {
00414       __glibcxx_check_insert_range(__position, __first, __last);
00415 
00416       /* Hard to guess if invalidation will occur, because __last
00417          - __first can't be calculated in all cases, so we just
00418          punt here by checking if it did occur. */
00419       typename _Base::iterator __old_begin = _M_base().begin();
00420       difference_type __offset = __position - begin();
00421       _Base::insert(__position.base(), __first, __last);
00422 
00423       if (_M_base().begin() != __old_begin)
00424         this->_M_invalidate_all();
00425       else
00426         this->_M_invalidate_if(_After_nth(__offset, _M_base().begin()));
00427       _M_update_guaranteed_capacity();
00428     }
00429 
00430       iterator
00431       erase(iterator __position)
00432       {
00433     __glibcxx_check_erase(__position);
00434     difference_type __offset = __position - begin();
00435     typename _Base::iterator __res = _Base::erase(__position.base());
00436     this->_M_invalidate_if(_After_nth(__offset, _M_base().begin()));
00437     return iterator(__res, this);
00438       }
00439 
00440       iterator
00441       erase(iterator __first, iterator __last)
00442       {
00443     // _GLIBCXX_RESOLVE_LIB_DEFECTS
00444     // 151. can't currently clear() empty container
00445     __glibcxx_check_erase_range(__first, __last);
00446 
00447     difference_type __offset = __first - begin();
00448     typename _Base::iterator __res = _Base::erase(__first.base(),
00449                              __last.base());
00450     this->_M_invalidate_if(_After_nth(__offset, _M_base().begin()));
00451     return iterator(__res, this);
00452       }
00453 
00454       void
00455 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00456       swap(vector&& __x)
00457 #else
00458       swap(vector& __x)
00459 #endif
00460       {
00461     _Base::swap(__x);
00462     this->_M_swap(__x);
00463         std::swap(_M_guaranteed_capacity, __x._M_guaranteed_capacity);
00464       }
00465 
00466       void
00467       clear()
00468       {
00469     _Base::clear();
00470     this->_M_invalidate_all();
00471         _M_guaranteed_capacity = 0;
00472       }
00473 
00474       _Base&
00475       _M_base() { return *this; }
00476 
00477       const _Base&
00478       _M_base() const { return *this; }
00479 
00480     private:
00481       size_type _M_guaranteed_capacity;
00482 
00483       bool
00484       _M_requires_reallocation(size_type __elements)
00485       { return __elements > this->capacity(); }
00486 
00487       void
00488       _M_update_guaranteed_capacity()
00489       {
00490     if (this->size() > _M_guaranteed_capacity)
00491       _M_guaranteed_capacity = this->size();
00492       }
00493     };
00494 
00495   template<typename _Tp, typename _Alloc>
00496     inline bool
00497     operator==(const vector<_Tp, _Alloc>& __lhs,
00498            const vector<_Tp, _Alloc>& __rhs)
00499     { return __lhs._M_base() == __rhs._M_base(); }
00500 
00501   template<typename _Tp, typename _Alloc>
00502     inline bool
00503     operator!=(const vector<_Tp, _Alloc>& __lhs,
00504            const vector<_Tp, _Alloc>& __rhs)
00505     { return __lhs._M_base() != __rhs._M_base(); }
00506 
00507   template<typename _Tp, typename _Alloc>
00508     inline bool
00509     operator<(const vector<_Tp, _Alloc>& __lhs,
00510           const vector<_Tp, _Alloc>& __rhs)
00511     { return __lhs._M_base() < __rhs._M_base(); }
00512 
00513   template<typename _Tp, typename _Alloc>
00514     inline bool
00515     operator<=(const vector<_Tp, _Alloc>& __lhs,
00516            const vector<_Tp, _Alloc>& __rhs)
00517     { return __lhs._M_base() <= __rhs._M_base(); }
00518 
00519   template<typename _Tp, typename _Alloc>
00520     inline bool
00521     operator>=(const vector<_Tp, _Alloc>& __lhs,
00522            const vector<_Tp, _Alloc>& __rhs)
00523     { return __lhs._M_base() >= __rhs._M_base(); }
00524 
00525   template<typename _Tp, typename _Alloc>
00526     inline bool
00527     operator>(const vector<_Tp, _Alloc>& __lhs,
00528           const vector<_Tp, _Alloc>& __rhs)
00529     { return __lhs._M_base() > __rhs._M_base(); }
00530 
00531   template<typename _Tp, typename _Alloc>
00532     inline void
00533     swap(vector<_Tp, _Alloc>& __lhs, vector<_Tp, _Alloc>& __rhs)
00534     { __lhs.swap(__rhs); }
00535 
00536 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00537   template<typename _Tp, typename _Alloc>
00538     inline void
00539     swap(vector<_Tp, _Alloc>&& __lhs, vector<_Tp, _Alloc>& __rhs)
00540     { __lhs.swap(__rhs); }
00541 
00542   template<typename _Tp, typename _Alloc>
00543     inline void
00544     swap(vector<_Tp, _Alloc>& __lhs, vector<_Tp, _Alloc>&& __rhs)
00545     { __lhs.swap(__rhs); }
00546 #endif
00547 
00548 } // namespace __debug
00549 } // namespace std
00550 
00551 #endif

Generated on Thu Jul 23 21:16:35 2009 for libstdc++ by  doxygen 1.5.8