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