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