libstdc++
vector
Go to the documentation of this file.
00001 // Debugging vector implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2003-2013 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 3, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 /** @file debug/vector
00026  *  This file is a GNU debug extension to the Standard C++ Library.
00027  */
00028 
00029 #ifndef _GLIBCXX_DEBUG_VECTOR
00030 #define _GLIBCXX_DEBUG_VECTOR 1
00031 
00032 #include <vector>
00033 #include <utility>
00034 #include <debug/safe_sequence.h>
00035 #include <debug/safe_iterator.h>
00036 
00037 namespace std _GLIBCXX_VISIBILITY(default)
00038 {
00039 namespace __debug
00040 {
00041   /// Class std::vector with safety/checking/debug instrumentation.
00042   template<typename _Tp,
00043        typename _Allocator = std::allocator<_Tp> >
00044     class vector
00045     : public _GLIBCXX_STD_C::vector<_Tp, _Allocator>,
00046       public __gnu_debug::_Safe_sequence<vector<_Tp, _Allocator> >
00047     {
00048       typedef _GLIBCXX_STD_C::vector<_Tp, _Allocator> _Base;
00049 
00050       typedef typename _Base::iterator _Base_iterator;
00051       typedef typename _Base::const_iterator _Base_const_iterator;
00052       typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
00053 
00054 #if __cplusplus >= 201103L
00055       typedef __gnu_cxx::__alloc_traits<_Allocator>  _Alloc_traits;
00056 #endif
00057 
00058     public:
00059       typedef typename _Base::reference             reference;
00060       typedef typename _Base::const_reference       const_reference;
00061 
00062       typedef __gnu_debug::_Safe_iterator<_Base_iterator,vector>
00063       iterator;
00064       typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,vector>
00065       const_iterator;
00066 
00067       typedef typename _Base::size_type             size_type;
00068       typedef typename _Base::difference_type       difference_type;
00069 
00070       typedef _Tp                   value_type;
00071       typedef _Allocator                allocator_type;
00072       typedef typename _Base::pointer               pointer;
00073       typedef typename _Base::const_pointer         const_pointer;
00074       typedef std::reverse_iterator<iterator>       reverse_iterator;
00075       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
00076 
00077       // 23.2.4.1 construct/copy/destroy:
00078       explicit
00079       vector(const _Allocator& __a = _Allocator())
00080       : _Base(__a), _M_guaranteed_capacity(0) { }
00081 
00082 #if __cplusplus >= 201103L
00083       explicit
00084       vector(size_type __n, const _Allocator& __a = _Allocator())
00085       : _Base(__n, __a), _M_guaranteed_capacity(__n) { }
00086 
00087       vector(size_type __n, const _Tp& __value,
00088          const _Allocator& __a = _Allocator())
00089       : _Base(__n, __value, __a), _M_guaranteed_capacity(__n) { }
00090 #else
00091       explicit
00092       vector(size_type __n, const _Tp& __value = _Tp(),
00093          const _Allocator& __a = _Allocator())
00094       : _Base(__n, __value, __a), _M_guaranteed_capacity(__n) { }
00095 #endif
00096 
00097 #if __cplusplus >= 201103L
00098       template<class _InputIterator,
00099            typename = std::_RequireInputIter<_InputIterator>>
00100 #else
00101       template<class _InputIterator>
00102 #endif
00103         vector(_InputIterator __first, _InputIterator __last,
00104            const _Allocator& __a = _Allocator())
00105         : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
00106                                      __last)),
00107         __gnu_debug::__base(__last), __a),
00108       _M_guaranteed_capacity(0)
00109         { _M_update_guaranteed_capacity(); }
00110 
00111       vector(const vector& __x)
00112       : _Base(__x), _M_guaranteed_capacity(__x.size()) { }
00113 
00114       /// Construction from a release-mode vector
00115       vector(const _Base& __x)
00116       : _Base(__x), _M_guaranteed_capacity(__x.size()) { }
00117 
00118 #if __cplusplus >= 201103L
00119       vector(vector&& __x) noexcept
00120       : _Base(std::move(__x)),
00121     _M_guaranteed_capacity(this->size())
00122       {
00123     this->_M_swap(__x);
00124     __x._M_guaranteed_capacity = 0;
00125       }
00126 
00127       vector(const vector& __x, const allocator_type& __a)
00128       : _Base(__x, __a), _M_guaranteed_capacity(__x.size()) { }
00129 
00130       vector(vector&& __x, const allocator_type& __a)
00131       : _Base(std::move(__x), __a),
00132         _M_guaranteed_capacity(this->size())
00133       {
00134     __x._M_invalidate_all();
00135     __x._M_guaranteed_capacity = 0;
00136       }
00137 
00138       vector(initializer_list<value_type> __l,
00139          const allocator_type& __a = allocator_type())
00140       : _Base(__l, __a),
00141     _M_guaranteed_capacity(__l.size()) { }
00142 #endif
00143 
00144       ~vector() _GLIBCXX_NOEXCEPT { }
00145 
00146       vector&
00147       operator=(const vector& __x)
00148       {
00149     static_cast<_Base&>(*this) = __x;
00150     this->_M_invalidate_all();
00151     _M_update_guaranteed_capacity();
00152     return *this;
00153       }
00154 
00155 #if __cplusplus >= 201103L
00156       vector&
00157       operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
00158       {
00159     __glibcxx_check_self_move_assign(__x);
00160     _Base::operator=(std::move(__x));
00161     this->_M_invalidate_all();
00162     _M_update_guaranteed_capacity();
00163     __x._M_invalidate_all();
00164     __x._M_guaranteed_capacity = 0;
00165     return *this;
00166       }
00167 
00168       vector&
00169       operator=(initializer_list<value_type> __l)
00170       {
00171     static_cast<_Base&>(*this) = __l;
00172     this->_M_invalidate_all();
00173     _M_update_guaranteed_capacity();
00174     return *this;
00175       }
00176 #endif
00177 
00178 #if __cplusplus >= 201103L
00179       template<typename _InputIterator,
00180            typename = std::_RequireInputIter<_InputIterator>>
00181 #else
00182       template<typename _InputIterator>
00183 #endif
00184         void
00185         assign(_InputIterator __first, _InputIterator __last)
00186         {
00187       __glibcxx_check_valid_range(__first, __last);
00188       _Base::assign(__gnu_debug::__base(__first),
00189             __gnu_debug::__base(__last));
00190       this->_M_invalidate_all();
00191       _M_update_guaranteed_capacity();
00192     }
00193 
00194       void
00195       assign(size_type __n, const _Tp& __u)
00196       {
00197     _Base::assign(__n, __u);
00198     this->_M_invalidate_all();
00199     _M_update_guaranteed_capacity();
00200       }
00201 
00202 #if __cplusplus >= 201103L
00203       void
00204       assign(initializer_list<value_type> __l)
00205       {
00206     _Base::assign(__l);
00207     this->_M_invalidate_all();
00208     _M_update_guaranteed_capacity();
00209       }
00210 #endif
00211 
00212       using _Base::get_allocator;
00213 
00214       // iterators:
00215       iterator
00216       begin() _GLIBCXX_NOEXCEPT
00217       { return iterator(_Base::begin(), this); }
00218 
00219       const_iterator
00220       begin() const _GLIBCXX_NOEXCEPT
00221       { return const_iterator(_Base::begin(), this); }
00222 
00223       iterator
00224       end() _GLIBCXX_NOEXCEPT
00225       { return iterator(_Base::end(), this); }
00226 
00227       const_iterator
00228       end() const _GLIBCXX_NOEXCEPT
00229       { return const_iterator(_Base::end(), this); }
00230 
00231       reverse_iterator
00232       rbegin() _GLIBCXX_NOEXCEPT
00233       { return reverse_iterator(end()); }
00234 
00235       const_reverse_iterator
00236       rbegin() const _GLIBCXX_NOEXCEPT
00237       { return const_reverse_iterator(end()); }
00238 
00239       reverse_iterator
00240       rend() _GLIBCXX_NOEXCEPT
00241       { return reverse_iterator(begin()); }
00242 
00243       const_reverse_iterator
00244       rend() const _GLIBCXX_NOEXCEPT
00245       { return const_reverse_iterator(begin()); }
00246 
00247 #if __cplusplus >= 201103L
00248       const_iterator
00249       cbegin() const noexcept
00250       { return const_iterator(_Base::begin(), this); }
00251 
00252       const_iterator
00253       cend() const noexcept
00254       { return const_iterator(_Base::end(), this); }
00255 
00256       const_reverse_iterator
00257       crbegin() const noexcept
00258       { return const_reverse_iterator(end()); }
00259 
00260       const_reverse_iterator
00261       crend() const noexcept
00262       { return const_reverse_iterator(begin()); }
00263 #endif
00264 
00265       // 23.2.4.2 capacity:
00266       using _Base::size;
00267       using _Base::max_size;
00268 
00269 #if __cplusplus >= 201103L
00270       void
00271       resize(size_type __sz)
00272       {
00273     bool __realloc = _M_requires_reallocation(__sz);
00274     if (__sz < this->size())
00275       this->_M_invalidate_after_nth(__sz);
00276     _Base::resize(__sz);
00277     if (__realloc)
00278       this->_M_invalidate_all();
00279     _M_update_guaranteed_capacity();
00280       }
00281 
00282       void
00283       resize(size_type __sz, const _Tp& __c)
00284       {
00285     bool __realloc = _M_requires_reallocation(__sz);
00286     if (__sz < this->size())
00287       this->_M_invalidate_after_nth(__sz);
00288     _Base::resize(__sz, __c);
00289     if (__realloc)
00290       this->_M_invalidate_all();
00291     _M_update_guaranteed_capacity();
00292       }
00293 #else
00294       void
00295       resize(size_type __sz, _Tp __c = _Tp())
00296       {
00297     bool __realloc = _M_requires_reallocation(__sz);
00298     if (__sz < this->size())
00299       this->_M_invalidate_after_nth(__sz);
00300     _Base::resize(__sz, __c);
00301     if (__realloc)
00302       this->_M_invalidate_all();
00303     _M_update_guaranteed_capacity();
00304       }
00305 #endif
00306 
00307 #if __cplusplus >= 201103L
00308       void
00309       shrink_to_fit()
00310       {
00311     if (_Base::_M_shrink_to_fit())
00312       {
00313         _M_guaranteed_capacity = _Base::capacity();
00314         this->_M_invalidate_all();
00315       }
00316       }
00317 #endif
00318 
00319       size_type
00320       capacity() const _GLIBCXX_NOEXCEPT
00321       {
00322 #ifdef _GLIBCXX_DEBUG_PEDANTIC
00323     return _M_guaranteed_capacity;
00324 #else
00325     return _Base::capacity();
00326 #endif
00327       }
00328 
00329       using _Base::empty;
00330 
00331       void
00332       reserve(size_type __n)
00333       {
00334     bool __realloc = _M_requires_reallocation(__n);
00335     _Base::reserve(__n);
00336     if (__n > _M_guaranteed_capacity)
00337       _M_guaranteed_capacity = __n;
00338     if (__realloc)
00339       this->_M_invalidate_all();
00340       }
00341 
00342       // element access:
00343       reference
00344       operator[](size_type __n)
00345       {
00346     __glibcxx_check_subscript(__n);
00347     return _M_base()[__n];
00348       }
00349 
00350       const_reference
00351       operator[](size_type __n) const
00352       {
00353     __glibcxx_check_subscript(__n);
00354     return _M_base()[__n];
00355       }
00356 
00357       using _Base::at;
00358 
00359       reference
00360       front()
00361       {
00362     __glibcxx_check_nonempty();
00363     return _Base::front();
00364       }
00365 
00366       const_reference
00367       front() const
00368       {
00369     __glibcxx_check_nonempty();
00370     return _Base::front();
00371       }
00372 
00373       reference
00374       back()
00375       {
00376     __glibcxx_check_nonempty();
00377     return _Base::back();
00378       }
00379 
00380       const_reference
00381       back() const
00382       {
00383     __glibcxx_check_nonempty();
00384     return _Base::back();
00385       }
00386 
00387       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00388       // DR 464. Suggestion for new member functions in standard containers.
00389       using _Base::data;
00390 
00391       // 23.2.4.3 modifiers:
00392       void
00393       push_back(const _Tp& __x)
00394       {
00395     bool __realloc = _M_requires_reallocation(this->size() + 1);
00396     _Base::push_back(__x);
00397     if (__realloc)
00398       this->_M_invalidate_all();
00399     _M_update_guaranteed_capacity();
00400       }
00401 
00402 #if __cplusplus >= 201103L
00403       template<typename _Up = _Tp>
00404         typename __gnu_cxx::__enable_if<!std::__are_same<_Up, bool>::__value,
00405                     void>::__type
00406         push_back(_Tp&& __x)
00407     { emplace_back(std::move(__x)); }
00408 
00409       template<typename... _Args>
00410         void
00411         emplace_back(_Args&&... __args)
00412     {
00413       bool __realloc = _M_requires_reallocation(this->size() + 1);
00414       _Base::emplace_back(std::forward<_Args>(__args)...);
00415       if (__realloc)
00416         this->_M_invalidate_all();
00417       _M_update_guaranteed_capacity();
00418     }
00419 #endif
00420 
00421       void
00422       pop_back()
00423       {
00424     __glibcxx_check_nonempty();
00425     this->_M_invalidate_if(_Equal(--_Base::end()));
00426     _Base::pop_back();
00427       }
00428 
00429 #if __cplusplus >= 201103L
00430       template<typename... _Args>
00431         iterator
00432         emplace(iterator __position, _Args&&... __args)
00433     {
00434       __glibcxx_check_insert(__position);
00435       bool __realloc = _M_requires_reallocation(this->size() + 1);
00436       difference_type __offset = __position.base() - _Base::begin();
00437       _Base_iterator __res = _Base::emplace(__position.base(),
00438                         std::forward<_Args>(__args)...);
00439       if (__realloc)
00440         this->_M_invalidate_all();
00441       else
00442         this->_M_invalidate_after_nth(__offset);
00443       _M_update_guaranteed_capacity();
00444       return iterator(__res, this);
00445     }
00446 #endif
00447 
00448       iterator
00449       insert(iterator __position, const _Tp& __x)
00450       {
00451     __glibcxx_check_insert(__position);
00452     bool __realloc = _M_requires_reallocation(this->size() + 1);
00453     difference_type __offset = __position.base() - _Base::begin();
00454     _Base_iterator __res = _Base::insert(__position.base(), __x);
00455     if (__realloc)
00456       this->_M_invalidate_all();
00457     else
00458       this->_M_invalidate_after_nth(__offset);
00459     _M_update_guaranteed_capacity();
00460     return iterator(__res, this);
00461       }
00462 
00463 #if __cplusplus >= 201103L
00464       template<typename _Up = _Tp>
00465         typename __gnu_cxx::__enable_if<!std::__are_same<_Up, bool>::__value,
00466                     iterator>::__type
00467         insert(iterator __position, _Tp&& __x)
00468         { return emplace(__position, std::move(__x)); }
00469 
00470       void
00471       insert(iterator __position, initializer_list<value_type> __l)
00472       { this->insert(__position, __l.begin(), __l.end()); }
00473 #endif
00474 
00475       void
00476       insert(iterator __position, size_type __n, const _Tp& __x)
00477       {
00478     __glibcxx_check_insert(__position);
00479     bool __realloc = _M_requires_reallocation(this->size() + __n);
00480     difference_type __offset = __position.base() - _Base::begin();
00481     _Base::insert(__position.base(), __n, __x);
00482     if (__realloc)
00483       this->_M_invalidate_all();
00484     else
00485       this->_M_invalidate_after_nth(__offset);
00486     _M_update_guaranteed_capacity();
00487       }
00488 
00489 #if __cplusplus >= 201103L
00490       template<class _InputIterator,
00491            typename = std::_RequireInputIter<_InputIterator>>
00492 #else
00493       template<class _InputIterator>
00494 #endif
00495         void
00496         insert(iterator __position,
00497            _InputIterator __first, _InputIterator __last)
00498         {
00499       __glibcxx_check_insert_range(__position, __first, __last);
00500 
00501       /* Hard to guess if invalidation will occur, because __last
00502          - __first can't be calculated in all cases, so we just
00503          punt here by checking if it did occur. */
00504       _Base_iterator __old_begin = _M_base().begin();
00505       difference_type __offset = __position.base() - _Base::begin();
00506       _Base::insert(__position.base(), __gnu_debug::__base(__first),
00507                        __gnu_debug::__base(__last));
00508 
00509       if (_M_base().begin() != __old_begin)
00510         this->_M_invalidate_all();
00511       else
00512         this->_M_invalidate_after_nth(__offset);
00513       _M_update_guaranteed_capacity();
00514     }
00515 
00516       iterator
00517       erase(iterator __position)
00518       {
00519     __glibcxx_check_erase(__position);
00520     difference_type __offset = __position.base() - _Base::begin();
00521     _Base_iterator __res = _Base::erase(__position.base());
00522     this->_M_invalidate_after_nth(__offset);
00523     return iterator(__res, this);
00524       }
00525 
00526       iterator
00527       erase(iterator __first, iterator __last)
00528       {
00529     // _GLIBCXX_RESOLVE_LIB_DEFECTS
00530     // 151. can't currently clear() empty container
00531     __glibcxx_check_erase_range(__first, __last);
00532 
00533     if (__first.base() != __last.base())
00534       {
00535         difference_type __offset = __first.base() - _Base::begin();
00536         _Base_iterator __res = _Base::erase(__first.base(),
00537                         __last.base());
00538         this->_M_invalidate_after_nth(__offset);
00539         return iterator(__res, this);
00540       }
00541     else
00542       return __first;
00543       }
00544 
00545       void
00546       swap(vector& __x)
00547 #if __cplusplus >= 201103L
00548             noexcept(_Alloc_traits::_S_nothrow_swap())
00549 #endif
00550       {
00551 #if __cplusplus >= 201103L
00552     if (!_Alloc_traits::_S_propagate_on_swap())
00553       __glibcxx_check_equal_allocs(__x);
00554 #endif
00555     _Base::swap(__x);
00556     this->_M_swap(__x);
00557         std::swap(_M_guaranteed_capacity, __x._M_guaranteed_capacity);
00558       }
00559 
00560       void
00561       clear() _GLIBCXX_NOEXCEPT
00562       {
00563     _Base::clear();
00564     this->_M_invalidate_all();
00565         _M_guaranteed_capacity = 0;
00566       }
00567 
00568       _Base&
00569       _M_base() _GLIBCXX_NOEXCEPT { return *this; }
00570 
00571       const _Base&
00572       _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
00573 
00574     private:
00575       size_type _M_guaranteed_capacity;
00576 
00577       bool
00578       _M_requires_reallocation(size_type __elements)
00579       { return __elements > this->capacity(); }
00580 
00581       void
00582       _M_update_guaranteed_capacity()
00583       {
00584     if (this->size() > _M_guaranteed_capacity)
00585       _M_guaranteed_capacity = this->size();
00586       }
00587 
00588       void
00589       _M_invalidate_after_nth(difference_type __n)
00590       {
00591     typedef __gnu_debug::_After_nth_from<_Base_const_iterator> _After_nth;
00592     this->_M_invalidate_if(_After_nth(__n, _Base::begin()));
00593       }
00594     };
00595 
00596   template<typename _Tp, typename _Alloc>
00597     inline bool
00598     operator==(const vector<_Tp, _Alloc>& __lhs,
00599            const vector<_Tp, _Alloc>& __rhs)
00600     { return __lhs._M_base() == __rhs._M_base(); }
00601 
00602   template<typename _Tp, typename _Alloc>
00603     inline bool
00604     operator!=(const vector<_Tp, _Alloc>& __lhs,
00605            const vector<_Tp, _Alloc>& __rhs)
00606     { return __lhs._M_base() != __rhs._M_base(); }
00607 
00608   template<typename _Tp, typename _Alloc>
00609     inline bool
00610     operator<(const vector<_Tp, _Alloc>& __lhs,
00611           const vector<_Tp, _Alloc>& __rhs)
00612     { return __lhs._M_base() < __rhs._M_base(); }
00613 
00614   template<typename _Tp, typename _Alloc>
00615     inline bool
00616     operator<=(const vector<_Tp, _Alloc>& __lhs,
00617            const vector<_Tp, _Alloc>& __rhs)
00618     { return __lhs._M_base() <= __rhs._M_base(); }
00619 
00620   template<typename _Tp, typename _Alloc>
00621     inline bool
00622     operator>=(const vector<_Tp, _Alloc>& __lhs,
00623            const vector<_Tp, _Alloc>& __rhs)
00624     { return __lhs._M_base() >= __rhs._M_base(); }
00625 
00626   template<typename _Tp, typename _Alloc>
00627     inline bool
00628     operator>(const vector<_Tp, _Alloc>& __lhs,
00629           const vector<_Tp, _Alloc>& __rhs)
00630     { return __lhs._M_base() > __rhs._M_base(); }
00631 
00632   template<typename _Tp, typename _Alloc>
00633     inline void
00634     swap(vector<_Tp, _Alloc>& __lhs, vector<_Tp, _Alloc>& __rhs)
00635     { __lhs.swap(__rhs); }
00636 
00637 } // namespace __debug
00638 
00639 #if __cplusplus >= 201103L
00640   // DR 1182.
00641   /// std::hash specialization for vector<bool>.
00642   template<typename _Alloc>
00643     struct hash<__debug::vector<bool, _Alloc>>
00644     : public __hash_base<size_t, __debug::vector<bool, _Alloc>>
00645     {
00646       size_t
00647       operator()(const __debug::vector<bool, _Alloc>& __b) const noexcept
00648       { return std::hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>()
00649       (__b._M_base()); }
00650     };
00651 #endif
00652 
00653 } // namespace std
00654 
00655 #endif