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