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