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_DEQUE
00036 #define _GLIBCXX_DEBUG_DEQUE 1
00037
00038 #include <deque>
00039 #include <debug/safe_sequence.h>
00040 #include <debug/safe_iterator.h>
00041
00042 namespace std
00043 {
00044 namespace __debug
00045 {
00046 template<typename _Tp, typename _Allocator = std::allocator<_Tp> >
00047 class deque
00048 : public _GLIBCXX_STD_D::deque<_Tp, _Allocator>,
00049 public __gnu_debug::_Safe_sequence<deque<_Tp, _Allocator> >
00050 {
00051 typedef _GLIBCXX_STD_D::deque<_Tp, _Allocator> _Base;
00052 typedef __gnu_debug::_Safe_sequence<deque> _Safe_base;
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,deque>
00059 iterator;
00060 typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,deque>
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 deque(const _Allocator& __a = _Allocator())
00075 : _Base(__a) { }
00076
00077 explicit deque(size_type __n, const _Tp& __value = _Tp(),
00078 const _Allocator& __a = _Allocator())
00079 : _Base(__n, __value, __a) { }
00080
00081 template<class _InputIterator>
00082 deque(_InputIterator __first, _InputIterator __last,
00083 const _Allocator& __a = _Allocator())
00084 : _Base(__gnu_debug::__check_valid_range(__first, __last), __last, __a)
00085 { }
00086
00087 deque(const deque& __x)
00088 : _Base(__x), _Safe_base() { }
00089
00090 deque(const _Base& __x)
00091 : _Base(__x), _Safe_base() { }
00092
00093 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00094 deque(deque&& __x)
00095 : _Base(std::forward<deque>(__x)), _Safe_base()
00096 { this->_M_swap(__x); }
00097 #endif
00098
00099 ~deque() { }
00100
00101 deque&
00102 operator=(const deque& __x)
00103 {
00104 *static_cast<_Base*>(this) = __x;
00105 this->_M_invalidate_all();
00106 return *this;
00107 }
00108
00109 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00110 deque&
00111 operator=(deque&& __x)
00112 {
00113
00114 clear();
00115 swap(__x);
00116 return *this;
00117 }
00118 #endif
00119
00120 template<class _InputIterator>
00121 void
00122 assign(_InputIterator __first, _InputIterator __last)
00123 {
00124 __glibcxx_check_valid_range(__first, __last);
00125 _Base::assign(__first, __last);
00126 this->_M_invalidate_all();
00127 }
00128
00129 void
00130 assign(size_type __n, const _Tp& __t)
00131 {
00132 _Base::assign(__n, __t);
00133 this->_M_invalidate_all();
00134 }
00135
00136 using _Base::get_allocator;
00137
00138
00139 iterator
00140 begin()
00141 { return iterator(_Base::begin(), this); }
00142
00143 const_iterator
00144 begin() const
00145 { return const_iterator(_Base::begin(), this); }
00146
00147 iterator
00148 end()
00149 { return iterator(_Base::end(), this); }
00150
00151 const_iterator
00152 end() const
00153 { return const_iterator(_Base::end(), this); }
00154
00155 reverse_iterator
00156 rbegin()
00157 { return reverse_iterator(end()); }
00158
00159 const_reverse_iterator
00160 rbegin() const
00161 { return const_reverse_iterator(end()); }
00162
00163 reverse_iterator
00164 rend()
00165 { return reverse_iterator(begin()); }
00166
00167 const_reverse_iterator
00168 rend() const
00169 { return const_reverse_iterator(begin()); }
00170
00171 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00172 const_iterator
00173 cbegin() const
00174 { return const_iterator(_Base::begin(), this); }
00175
00176 const_iterator
00177 cend() const
00178 { return const_iterator(_Base::end(), this); }
00179
00180 const_reverse_iterator
00181 crbegin() const
00182 { return const_reverse_iterator(end()); }
00183
00184 const_reverse_iterator
00185 crend() const
00186 { return const_reverse_iterator(begin()); }
00187 #endif
00188
00189
00190 using _Base::size;
00191 using _Base::max_size;
00192
00193 void
00194 resize(size_type __sz, _Tp __c = _Tp())
00195 {
00196 typedef typename _Base::const_iterator _Base_const_iterator;
00197 typedef __gnu_debug::_After_nth_from<_Base_const_iterator> _After_nth;
00198
00199 bool __invalidate_all = __sz > this->size();
00200 if (__sz < this->size())
00201 this->_M_invalidate_if(_After_nth(__sz, _M_base().begin()));
00202
00203 _Base::resize(__sz, __c);
00204
00205 if (__invalidate_all)
00206 this->_M_invalidate_all();
00207 }
00208
00209 using _Base::empty;
00210
00211
00212 reference
00213 operator[](size_type __n)
00214 {
00215 __glibcxx_check_subscript(__n);
00216 return _M_base()[__n];
00217 }
00218
00219 const_reference
00220 operator[](size_type __n) const
00221 {
00222 __glibcxx_check_subscript(__n);
00223 return _M_base()[__n];
00224 }
00225
00226 using _Base::at;
00227
00228 reference
00229 front()
00230 {
00231 __glibcxx_check_nonempty();
00232 return _Base::front();
00233 }
00234
00235 const_reference
00236 front() const
00237 {
00238 __glibcxx_check_nonempty();
00239 return _Base::front();
00240 }
00241
00242 reference
00243 back()
00244 {
00245 __glibcxx_check_nonempty();
00246 return _Base::back();
00247 }
00248
00249 const_reference
00250 back() const
00251 {
00252 __glibcxx_check_nonempty();
00253 return _Base::back();
00254 }
00255
00256
00257 #ifndef __GXX_EXPERIMENTAL_CXX0X__
00258 void
00259 push_front(const _Tp& __x)
00260 {
00261 _Base::push_front(__x);
00262 this->_M_invalidate_all();
00263 }
00264
00265 void
00266 push_back(const _Tp& __x)
00267 {
00268 _Base::push_back(__x);
00269 this->_M_invalidate_all();
00270 }
00271 #else
00272 template<typename... _Args>
00273 void
00274 push_front(_Args&&... __args)
00275 {
00276 _Base::push_front(std::forward<_Args>(__args)...);
00277 this->_M_invalidate_all();
00278 }
00279
00280 template<typename... _Args>
00281 void
00282 push_back(_Args&&... __args)
00283 {
00284 _Base::push_back(std::forward<_Args>(__args)...);
00285 this->_M_invalidate_all();
00286 }
00287
00288 template<typename... _Args>
00289 iterator
00290 emplace(iterator __position, _Args&&... __args)
00291 {
00292 __glibcxx_check_insert(__position);
00293 typename _Base::iterator __res = _Base::emplace(__position.base(),
00294 std::forward<_Args>(__args)...);
00295 this->_M_invalidate_all();
00296 return iterator(__res, this);
00297 }
00298 #endif
00299
00300 iterator
00301 insert(iterator __position, const _Tp& __x)
00302 {
00303 __glibcxx_check_insert(__position);
00304 typename _Base::iterator __res = _Base::insert(__position.base(), __x);
00305 this->_M_invalidate_all();
00306 return iterator(__res, this);
00307 }
00308
00309 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00310 iterator
00311 insert(iterator __position, _Tp&& __x)
00312 { return emplace(__position, std::move(__x)); }
00313 #endif
00314
00315 void
00316 insert(iterator __position, size_type __n, const _Tp& __x)
00317 {
00318 __glibcxx_check_insert(__position);
00319 _Base::insert(__position.base(), __n, __x);
00320 this->_M_invalidate_all();
00321 }
00322
00323 template<class _InputIterator>
00324 void
00325 insert(iterator __position,
00326 _InputIterator __first, _InputIterator __last)
00327 {
00328 __glibcxx_check_insert_range(__position, __first, __last);
00329 _Base::insert(__position.base(), __first, __last);
00330 this->_M_invalidate_all();
00331 }
00332
00333 void
00334 pop_front()
00335 {
00336 __glibcxx_check_nonempty();
00337 iterator __victim = begin();
00338 __victim._M_invalidate();
00339 _Base::pop_front();
00340 }
00341
00342 void
00343 pop_back()
00344 {
00345 __glibcxx_check_nonempty();
00346 iterator __victim = end();
00347 --__victim;
00348 __victim._M_invalidate();
00349 _Base::pop_back();
00350 }
00351
00352 iterator
00353 erase(iterator __position)
00354 {
00355 __glibcxx_check_erase(__position);
00356 if (__position == begin() || __position == end()-1)
00357 {
00358 __position._M_invalidate();
00359 return iterator(_Base::erase(__position.base()), this);
00360 }
00361 else
00362 {
00363 typename _Base::iterator __res = _Base::erase(__position.base());
00364 this->_M_invalidate_all();
00365 return iterator(__res, this);
00366 }
00367 }
00368
00369 iterator
00370 erase(iterator __first, iterator __last)
00371 {
00372
00373
00374 __glibcxx_check_erase_range(__first, __last);
00375 if (__first == begin() || __last == end())
00376 {
00377 this->_M_detach_singular();
00378 for (iterator __position = __first; __position != __last; )
00379 {
00380 iterator __victim = __position++;
00381 __victim._M_invalidate();
00382 }
00383 try
00384 {
00385 return iterator(_Base::erase(__first.base(), __last.base()),
00386 this);
00387 }
00388 catch(...)
00389 {
00390 this->_M_revalidate_singular();
00391 __throw_exception_again;
00392 }
00393 }
00394 else
00395 {
00396 typename _Base::iterator __res = _Base::erase(__first.base(),
00397 __last.base());
00398 this->_M_invalidate_all();
00399 return iterator(__res, this);
00400 }
00401 }
00402
00403 void
00404 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00405 swap(deque&& __x)
00406 #else
00407 swap(deque& __x)
00408 #endif
00409 {
00410 _Base::swap(__x);
00411 this->_M_swap(__x);
00412 }
00413
00414 void
00415 clear()
00416 {
00417 _Base::clear();
00418 this->_M_invalidate_all();
00419 }
00420
00421 _Base&
00422 _M_base() { return *this; }
00423
00424 const _Base&
00425 _M_base() const { return *this; }
00426 };
00427
00428 template<typename _Tp, typename _Alloc>
00429 inline bool
00430 operator==(const deque<_Tp, _Alloc>& __lhs,
00431 const deque<_Tp, _Alloc>& __rhs)
00432 { return __lhs._M_base() == __rhs._M_base(); }
00433
00434 template<typename _Tp, typename _Alloc>
00435 inline bool
00436 operator!=(const deque<_Tp, _Alloc>& __lhs,
00437 const deque<_Tp, _Alloc>& __rhs)
00438 { return __lhs._M_base() != __rhs._M_base(); }
00439
00440 template<typename _Tp, typename _Alloc>
00441 inline bool
00442 operator<(const deque<_Tp, _Alloc>& __lhs,
00443 const deque<_Tp, _Alloc>& __rhs)
00444 { return __lhs._M_base() < __rhs._M_base(); }
00445
00446 template<typename _Tp, typename _Alloc>
00447 inline bool
00448 operator<=(const deque<_Tp, _Alloc>& __lhs,
00449 const deque<_Tp, _Alloc>& __rhs)
00450 { return __lhs._M_base() <= __rhs._M_base(); }
00451
00452 template<typename _Tp, typename _Alloc>
00453 inline bool
00454 operator>=(const deque<_Tp, _Alloc>& __lhs,
00455 const deque<_Tp, _Alloc>& __rhs)
00456 { return __lhs._M_base() >= __rhs._M_base(); }
00457
00458 template<typename _Tp, typename _Alloc>
00459 inline bool
00460 operator>(const deque<_Tp, _Alloc>& __lhs,
00461 const deque<_Tp, _Alloc>& __rhs)
00462 { return __lhs._M_base() > __rhs._M_base(); }
00463
00464 template<typename _Tp, typename _Alloc>
00465 inline void
00466 swap(deque<_Tp, _Alloc>& __lhs, deque<_Tp, _Alloc>& __rhs)
00467 { __lhs.swap(__rhs); }
00468
00469 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00470 template<typename _Tp, typename _Alloc>
00471 inline void
00472 swap(deque<_Tp, _Alloc>&& __lhs, deque<_Tp, _Alloc>& __rhs)
00473 { __lhs.swap(__rhs); }
00474
00475 template<typename _Tp, typename _Alloc>
00476 inline void
00477 swap(deque<_Tp, _Alloc>& __lhs, deque<_Tp, _Alloc>&& __rhs)
00478 { __lhs.swap(__rhs); }
00479 #endif
00480
00481 }
00482 }
00483
00484 #endif