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