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_D::vector<_Tp, _Allocator>,
00051 public __gnu_debug::_Safe_sequence<vector<_Tp, _Allocator> >
00052 {
00053 typedef _GLIBCXX_STD_D::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& __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 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00102 vector(vector&& __x)
00103 : _Base(std::forward<vector>(__x)), _Safe_base(),
00104 _M_guaranteed_capacity(this->size())
00105 {
00106 this->_M_swap(__x);
00107 __x._M_guaranteed_capacity = 0;
00108 }
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
00127 clear();
00128 swap(__x);
00129 return *this;
00130 }
00131 #endif
00132
00133 template<typename _InputIterator>
00134 void
00135 assign(_InputIterator __first, _InputIterator __last)
00136 {
00137 __glibcxx_check_valid_range(__first, __last);
00138 _Base::assign(__first, __last);
00139 this->_M_invalidate_all();
00140 _M_update_guaranteed_capacity();
00141 }
00142
00143 void
00144 assign(size_type __n, const _Tp& __u)
00145 {
00146 _Base::assign(__n, __u);
00147 this->_M_invalidate_all();
00148 _M_update_guaranteed_capacity();
00149 }
00150
00151 using _Base::get_allocator;
00152
00153
00154 iterator
00155 begin()
00156 { return iterator(_Base::begin(), this); }
00157
00158 const_iterator
00159 begin() const
00160 { return const_iterator(_Base::begin(), this); }
00161
00162 iterator
00163 end()
00164 { return iterator(_Base::end(), this); }
00165
00166 const_iterator
00167 end() const
00168 { return const_iterator(_Base::end(), this); }
00169
00170 reverse_iterator
00171 rbegin()
00172 { return reverse_iterator(end()); }
00173
00174 const_reverse_iterator
00175 rbegin() const
00176 { return const_reverse_iterator(end()); }
00177
00178 reverse_iterator
00179 rend()
00180 { return reverse_iterator(begin()); }
00181
00182 const_reverse_iterator
00183 rend() const
00184 { return const_reverse_iterator(begin()); }
00185
00186 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00187 const_iterator
00188 cbegin() const
00189 { return const_iterator(_Base::begin(), this); }
00190
00191 const_iterator
00192 cend() const
00193 { return const_iterator(_Base::end(), this); }
00194
00195 const_reverse_iterator
00196 crbegin() const
00197 { return const_reverse_iterator(end()); }
00198
00199 const_reverse_iterator
00200 crend() const
00201 { return const_reverse_iterator(begin()); }
00202 #endif
00203
00204
00205 using _Base::size;
00206 using _Base::max_size;
00207
00208 void
00209 resize(size_type __sz, _Tp __c = _Tp())
00210 {
00211 bool __realloc = _M_requires_reallocation(__sz);
00212 if (__sz < this->size())
00213 this->_M_invalidate_if(_After_nth(__sz, _M_base().begin()));
00214 _Base::resize(__sz, __c);
00215 if (__realloc)
00216 this->_M_invalidate_all();
00217 }
00218
00219 using _Base::capacity;
00220 using _Base::empty;
00221
00222 void
00223 reserve(size_type __n)
00224 {
00225 bool __realloc = _M_requires_reallocation(__n);
00226 _Base::reserve(__n);
00227 if (__n > _M_guaranteed_capacity)
00228 _M_guaranteed_capacity = __n;
00229 if (__realloc)
00230 this->_M_invalidate_all();
00231 }
00232
00233
00234 reference
00235 operator[](size_type __n)
00236 {
00237 __glibcxx_check_subscript(__n);
00238 return _M_base()[__n];
00239 }
00240
00241 const_reference
00242 operator[](size_type __n) const
00243 {
00244 __glibcxx_check_subscript(__n);
00245 return _M_base()[__n];
00246 }
00247
00248 using _Base::at;
00249
00250 reference
00251 front()
00252 {
00253 __glibcxx_check_nonempty();
00254 return _Base::front();
00255 }
00256
00257 const_reference
00258 front() const
00259 {
00260 __glibcxx_check_nonempty();
00261 return _Base::front();
00262 }
00263
00264 reference
00265 back()
00266 {
00267 __glibcxx_check_nonempty();
00268 return _Base::back();
00269 }
00270
00271 const_reference
00272 back() const
00273 {
00274 __glibcxx_check_nonempty();
00275 return _Base::back();
00276 }
00277
00278
00279
00280 using _Base::data;
00281
00282
00283 #ifndef __GXX_EXPERIMENTAL_CXX0X__
00284 void
00285 push_back(const _Tp& __x)
00286 {
00287 bool __realloc = _M_requires_reallocation(this->size() + 1);
00288 _Base::push_back(__x);
00289 if (__realloc)
00290 this->_M_invalidate_all();
00291 _M_update_guaranteed_capacity();
00292 }
00293 #else
00294 template<typename... _Args>
00295 void
00296 push_back(_Args&&... __args)
00297 {
00298 bool __realloc = _M_requires_reallocation(this->size() + 1);
00299 _Base::push_back(std::forward<_Args>(__args)...);
00300 if (__realloc)
00301 this->_M_invalidate_all();
00302 _M_update_guaranteed_capacity();
00303 }
00304 #endif
00305
00306 void
00307 pop_back()
00308 {
00309 __glibcxx_check_nonempty();
00310 iterator __victim = end() - 1;
00311 __victim._M_invalidate();
00312 _Base::pop_back();
00313 }
00314
00315 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00316 template<typename... _Args>
00317 iterator
00318 emplace(iterator __position, _Args&&... __args)
00319 {
00320 __glibcxx_check_insert(__position);
00321 bool __realloc = _M_requires_reallocation(this->size() + 1);
00322 difference_type __offset = __position - begin();
00323 typename _Base::iterator __res = _Base::emplace(__position.base(),
00324 std::forward<_Args>(__args)...);
00325 if (__realloc)
00326 this->_M_invalidate_all();
00327 else
00328 this->_M_invalidate_if(_After_nth(__offset, _M_base().begin()));
00329 _M_update_guaranteed_capacity();
00330 return iterator(__res, this);
00331 }
00332 #endif
00333
00334 iterator
00335 insert(iterator __position, const _Tp& __x)
00336 {
00337 __glibcxx_check_insert(__position);
00338 bool __realloc = _M_requires_reallocation(this->size() + 1);
00339 difference_type __offset = __position - begin();
00340 typename _Base::iterator __res = _Base::insert(__position.base(),__x);
00341 if (__realloc)
00342 this->_M_invalidate_all();
00343 else
00344 this->_M_invalidate_if(_After_nth(__offset, _M_base().begin()));
00345 _M_update_guaranteed_capacity();
00346 return iterator(__res, this);
00347 }
00348
00349 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00350 iterator
00351 insert(iterator __position, _Tp&& __x)
00352 { return emplace(__position, std::move(__x)); }
00353 #endif
00354
00355 void
00356 insert(iterator __position, size_type __n, const _Tp& __x)
00357 {
00358 __glibcxx_check_insert(__position);
00359 bool __realloc = _M_requires_reallocation(this->size() + __n);
00360 difference_type __offset = __position - begin();
00361 _Base::insert(__position.base(), __n, __x);
00362 if (__realloc)
00363 this->_M_invalidate_all();
00364 else
00365 this->_M_invalidate_if(_After_nth(__offset, _M_base().begin()));
00366 _M_update_guaranteed_capacity();
00367 }
00368
00369 template<class _InputIterator>
00370 void
00371 insert(iterator __position,
00372 _InputIterator __first, _InputIterator __last)
00373 {
00374 __glibcxx_check_insert_range(__position, __first, __last);
00375
00376
00377
00378
00379 typename _Base::iterator __old_begin = _M_base().begin();
00380 difference_type __offset = __position - begin();
00381 _Base::insert(__position.base(), __first, __last);
00382
00383 if (_M_base().begin() != __old_begin)
00384 this->_M_invalidate_all();
00385 else
00386 this->_M_invalidate_if(_After_nth(__offset, _M_base().begin()));
00387 _M_update_guaranteed_capacity();
00388 }
00389
00390 iterator
00391 erase(iterator __position)
00392 {
00393 __glibcxx_check_erase(__position);
00394 difference_type __offset = __position - begin();
00395 typename _Base::iterator __res = _Base::erase(__position.base());
00396 this->_M_invalidate_if(_After_nth(__offset, _M_base().begin()));
00397 return iterator(__res, this);
00398 }
00399
00400 iterator
00401 erase(iterator __first, iterator __last)
00402 {
00403
00404
00405 __glibcxx_check_erase_range(__first, __last);
00406
00407 difference_type __offset = __first - begin();
00408 typename _Base::iterator __res = _Base::erase(__first.base(),
00409 __last.base());
00410 this->_M_invalidate_if(_After_nth(__offset, _M_base().begin()));
00411 return iterator(__res, this);
00412 }
00413
00414 void
00415 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00416 swap(vector&& __x)
00417 #else
00418 swap(vector& __x)
00419 #endif
00420 {
00421 _Base::swap(__x);
00422 this->_M_swap(__x);
00423 std::swap(_M_guaranteed_capacity, __x._M_guaranteed_capacity);
00424 }
00425
00426 void
00427 clear()
00428 {
00429 _Base::clear();
00430 this->_M_invalidate_all();
00431 _M_guaranteed_capacity = 0;
00432 }
00433
00434 _Base&
00435 _M_base() { return *this; }
00436
00437 const _Base&
00438 _M_base() const { return *this; }
00439
00440 private:
00441 size_type _M_guaranteed_capacity;
00442
00443 bool
00444 _M_requires_reallocation(size_type __elements)
00445 {
00446 #ifdef _GLIBCXX_DEBUG_PEDANTIC
00447 return __elements > this->capacity();
00448 #else
00449 return __elements > _M_guaranteed_capacity;
00450 #endif
00451 }
00452
00453 void
00454 _M_update_guaranteed_capacity()
00455 {
00456 if (this->size() > _M_guaranteed_capacity)
00457 _M_guaranteed_capacity = this->size();
00458 }
00459 };
00460
00461 template<typename _Tp, typename _Alloc>
00462 inline bool
00463 operator==(const vector<_Tp, _Alloc>& __lhs,
00464 const vector<_Tp, _Alloc>& __rhs)
00465 { return __lhs._M_base() == __rhs._M_base(); }
00466
00467 template<typename _Tp, typename _Alloc>
00468 inline bool
00469 operator!=(const vector<_Tp, _Alloc>& __lhs,
00470 const vector<_Tp, _Alloc>& __rhs)
00471 { return __lhs._M_base() != __rhs._M_base(); }
00472
00473 template<typename _Tp, typename _Alloc>
00474 inline bool
00475 operator<(const vector<_Tp, _Alloc>& __lhs,
00476 const vector<_Tp, _Alloc>& __rhs)
00477 { return __lhs._M_base() < __rhs._M_base(); }
00478
00479 template<typename _Tp, typename _Alloc>
00480 inline bool
00481 operator<=(const vector<_Tp, _Alloc>& __lhs,
00482 const vector<_Tp, _Alloc>& __rhs)
00483 { return __lhs._M_base() <= __rhs._M_base(); }
00484
00485 template<typename _Tp, typename _Alloc>
00486 inline bool
00487 operator>=(const vector<_Tp, _Alloc>& __lhs,
00488 const vector<_Tp, _Alloc>& __rhs)
00489 { return __lhs._M_base() >= __rhs._M_base(); }
00490
00491 template<typename _Tp, typename _Alloc>
00492 inline bool
00493 operator>(const vector<_Tp, _Alloc>& __lhs,
00494 const vector<_Tp, _Alloc>& __rhs)
00495 { return __lhs._M_base() > __rhs._M_base(); }
00496
00497 template<typename _Tp, typename _Alloc>
00498 inline void
00499 swap(vector<_Tp, _Alloc>& __lhs, vector<_Tp, _Alloc>& __rhs)
00500 { __lhs.swap(__rhs); }
00501
00502 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00503 template<typename _Tp, typename _Alloc>
00504 inline void
00505 swap(vector<_Tp, _Alloc>&& __lhs, vector<_Tp, _Alloc>& __rhs)
00506 { __lhs.swap(__rhs); }
00507
00508 template<typename _Tp, typename _Alloc>
00509 inline void
00510 swap(vector<_Tp, _Alloc>& __lhs, vector<_Tp, _Alloc>&& __rhs)
00511 { __lhs.swap(__rhs); }
00512 #endif
00513
00514 }
00515 }
00516
00517 #endif