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