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