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