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