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 _GLIBCXX_VISIBILITY(default)
00038 {
00039 namespace __debug
00040 {
00041
00042 template<typename _Tp, typename _Allocator = std::allocator<_Tp> >
00043 class list
00044 : public _GLIBCXX_STD_C::list<_Tp, _Allocator>,
00045 public __gnu_debug::_Safe_sequence<list<_Tp, _Allocator> >
00046 {
00047 typedef _GLIBCXX_STD_C::list<_Tp, _Allocator> _Base;
00048 typedef __gnu_debug::_Safe_sequence<list> _Safe_base;
00049
00050 typedef typename _Base::iterator _Base_iterator;
00051 typedef typename _Base::const_iterator _Base_const_iterator;
00052 typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
00053 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
00054 public:
00055 typedef typename _Base::reference reference;
00056 typedef typename _Base::const_reference const_reference;
00057
00058 typedef __gnu_debug::_Safe_iterator<_Base_iterator, list>
00059 iterator;
00060 typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, list>
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
00075 list(const _Allocator& __a = _Allocator())
00076 : _Base(__a) { }
00077
00078 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00079 explicit
00080 list(size_type __n)
00081 : _Base(__n) { }
00082
00083 list(size_type __n, const _Tp& __value,
00084 const _Allocator& __a = _Allocator())
00085 : _Base(__n, __value, __a) { }
00086 #else
00087 explicit
00088 list(size_type __n, const _Tp& __value = _Tp(),
00089 const _Allocator& __a = _Allocator())
00090 : _Base(__n, __value, __a) { }
00091 #endif
00092
00093 template<class _InputIterator>
00094 list(_InputIterator __first, _InputIterator __last,
00095 const _Allocator& __a = _Allocator())
00096 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
00097 __last)),
00098 __gnu_debug::__base(__last), __a)
00099 { }
00100
00101
00102 list(const list& __x)
00103 : _Base(__x), _Safe_base() { }
00104
00105 list(const _Base& __x)
00106 : _Base(__x), _Safe_base() { }
00107
00108 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00109 list(list&& __x)
00110 : _Base(std::move(__x)), _Safe_base()
00111 { this->_M_swap(__x); }
00112
00113 list(initializer_list<value_type> __l,
00114 const allocator_type& __a = allocator_type())
00115 : _Base(__l, __a), _Safe_base() { }
00116 #endif
00117
00118 ~list() { }
00119
00120 list&
00121 operator=(const list& __x)
00122 {
00123 static_cast<_Base&>(*this) = __x;
00124 this->_M_invalidate_all();
00125 return *this;
00126 }
00127
00128 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00129 list&
00130 operator=(list&& __x)
00131 {
00132
00133
00134 clear();
00135 swap(__x);
00136 return *this;
00137 }
00138
00139 list&
00140 operator=(initializer_list<value_type> __l)
00141 {
00142 static_cast<_Base&>(*this) = __l;
00143 this->_M_invalidate_all();
00144 return *this;
00145 }
00146
00147 void
00148 assign(initializer_list<value_type> __l)
00149 {
00150 _Base::assign(__l);
00151 this->_M_invalidate_all();
00152 }
00153 #endif
00154
00155 template<class _InputIterator>
00156 void
00157 assign(_InputIterator __first, _InputIterator __last)
00158 {
00159 __glibcxx_check_valid_range(__first, __last);
00160 _Base::assign(__gnu_debug::__base(__first),
00161 __gnu_debug::__base(__last));
00162 this->_M_invalidate_all();
00163 }
00164
00165 void
00166 assign(size_type __n, const _Tp& __t)
00167 {
00168 _Base::assign(__n, __t);
00169 this->_M_invalidate_all();
00170 }
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
00226 using _Base::empty;
00227 using _Base::size;
00228 using _Base::max_size;
00229
00230 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00231 void
00232 resize(size_type __sz)
00233 {
00234 this->_M_detach_singular();
00235
00236
00237 _Base_iterator __victim = _Base::begin();
00238 _Base_iterator __end = _Base::end();
00239 for (size_type __i = __sz; __victim != __end && __i > 0; --__i)
00240 ++__victim;
00241
00242 for (; __victim != __end; ++__victim)
00243 {
00244 this->_M_invalidate_if(_Equal(__victim));
00245 }
00246
00247 __try
00248 {
00249 _Base::resize(__sz);
00250 }
00251 __catch(...)
00252 {
00253 this->_M_revalidate_singular();
00254 __throw_exception_again;
00255 }
00256 }
00257
00258 void
00259 resize(size_type __sz, const _Tp& __c)
00260 {
00261 this->_M_detach_singular();
00262
00263
00264 _Base_iterator __victim = _Base::begin();
00265 _Base_iterator __end = _Base::end();
00266 for (size_type __i = __sz; __victim != __end && __i > 0; --__i)
00267 ++__victim;
00268
00269 for (; __victim != __end; ++__victim)
00270 {
00271 this->_M_invalidate_if(_Equal(__victim));
00272 }
00273
00274 __try
00275 {
00276 _Base::resize(__sz, __c);
00277 }
00278 __catch(...)
00279 {
00280 this->_M_revalidate_singular();
00281 __throw_exception_again;
00282 }
00283 }
00284 #else
00285 void
00286 resize(size_type __sz, _Tp __c = _Tp())
00287 {
00288 this->_M_detach_singular();
00289
00290
00291 _Base_iterator __victim = _Base::begin();
00292 _Base_iterator __end = _Base::end();
00293 for (size_type __i = __sz; __victim != __end && __i > 0; --__i)
00294 ++__victim;
00295
00296 for (; __victim != __end; ++__victim)
00297 {
00298 this->_M_invalidate_if(_Equal(__victim));
00299 }
00300
00301 __try
00302 {
00303 _Base::resize(__sz, __c);
00304 }
00305 __catch(...)
00306 {
00307 this->_M_revalidate_singular();
00308 __throw_exception_again;
00309 }
00310 }
00311 #endif
00312
00313
00314 reference
00315 front()
00316 {
00317 __glibcxx_check_nonempty();
00318 return _Base::front();
00319 }
00320
00321 const_reference
00322 front() const
00323 {
00324 __glibcxx_check_nonempty();
00325 return _Base::front();
00326 }
00327
00328 reference
00329 back()
00330 {
00331 __glibcxx_check_nonempty();
00332 return _Base::back();
00333 }
00334
00335 const_reference
00336 back() const
00337 {
00338 __glibcxx_check_nonempty();
00339 return _Base::back();
00340 }
00341
00342
00343 using _Base::push_front;
00344
00345 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00346 using _Base::emplace_front;
00347 #endif
00348
00349 void
00350 pop_front()
00351 {
00352 __glibcxx_check_nonempty();
00353 this->_M_invalidate_if(_Equal(_Base::begin()));
00354 _Base::pop_front();
00355 }
00356
00357 using _Base::push_back;
00358
00359 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00360 using _Base::emplace_back;
00361 #endif
00362
00363 void
00364 pop_back()
00365 {
00366 __glibcxx_check_nonempty();
00367 this->_M_invalidate_if(_Equal(--_Base::end()));
00368 _Base::pop_back();
00369 }
00370
00371 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00372 template<typename... _Args>
00373 iterator
00374 emplace(iterator __position, _Args&&... __args)
00375 {
00376 __glibcxx_check_insert(__position);
00377 return iterator(_Base::emplace(__position.base(),
00378 std::forward<_Args>(__args)...), this);
00379 }
00380 #endif
00381
00382 iterator
00383 insert(iterator __position, const _Tp& __x)
00384 {
00385 __glibcxx_check_insert(__position);
00386 return iterator(_Base::insert(__position.base(), __x), this);
00387 }
00388
00389 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00390 iterator
00391 insert(iterator __position, _Tp&& __x)
00392 { return emplace(__position, std::move(__x)); }
00393
00394 void
00395 insert(iterator __p, initializer_list<value_type> __l)
00396 {
00397 __glibcxx_check_insert(__p);
00398 _Base::insert(__p, __l);
00399 }
00400 #endif
00401
00402 void
00403 insert(iterator __position, size_type __n, const _Tp& __x)
00404 {
00405 __glibcxx_check_insert(__position);
00406 _Base::insert(__position.base(), __n, __x);
00407 }
00408
00409 template<class _InputIterator>
00410 void
00411 insert(iterator __position, _InputIterator __first,
00412 _InputIterator __last)
00413 {
00414 __glibcxx_check_insert_range(__position, __first, __last);
00415 _Base::insert(__position.base(), __gnu_debug::__base(__first),
00416 __gnu_debug::__base(__last));
00417 }
00418
00419 private:
00420 _Base_iterator
00421 _M_erase(_Base_iterator __position)
00422 {
00423 this->_M_invalidate_if(_Equal(__position));
00424 return _Base::erase(__position);
00425 }
00426 public:
00427 iterator
00428 erase(iterator __position)
00429 {
00430 __glibcxx_check_erase(__position);
00431 return iterator(_M_erase(__position.base()), this);
00432 }
00433
00434 iterator
00435 erase(iterator __position, iterator __last)
00436 {
00437
00438
00439 __glibcxx_check_erase_range(__position, __last);
00440 for (_Base_iterator __victim = __position.base();
00441 __victim != __last.base(); ++__victim)
00442 {
00443 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
00444 _M_message(__gnu_debug::__msg_valid_range)
00445 ._M_iterator(__position, "position")
00446 ._M_iterator(__last, "last"));
00447 this->_M_invalidate_if(_Equal(__victim));
00448 }
00449 return iterator(_Base::erase(__position.base(), __last.base()), this);
00450 }
00451
00452 void
00453 swap(list& __x)
00454 {
00455 _Base::swap(__x);
00456 this->_M_swap(__x);
00457 }
00458
00459 void
00460 clear()
00461 {
00462 _Base::clear();
00463 this->_M_invalidate_all();
00464 }
00465
00466
00467 void
00468 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00469 splice(iterator __position, list&& __x)
00470 #else
00471 splice(iterator __position, list& __x)
00472 #endif
00473 {
00474 _GLIBCXX_DEBUG_VERIFY(&__x != this,
00475 _M_message(__gnu_debug::__msg_self_splice)
00476 ._M_sequence(*this, "this"));
00477 this->_M_transfer_from_if(__x, _Not_equal(__x._M_base().end()));
00478 _Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base()));
00479 }
00480
00481 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00482 void
00483 splice(iterator __position, list& __x)
00484 { splice(__position, std::move(__x)); }
00485 #endif
00486
00487 void
00488 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00489 splice(iterator __position, list&& __x, iterator __i)
00490 #else
00491 splice(iterator __position, list& __x, iterator __i)
00492 #endif
00493 {
00494 __glibcxx_check_insert(__position);
00495
00496
00497
00498
00499 _GLIBCXX_DEBUG_VERIFY(__i._M_dereferenceable(),
00500 _M_message(__gnu_debug::__msg_splice_bad)
00501 ._M_iterator(__i, "__i"));
00502 _GLIBCXX_DEBUG_VERIFY(__i._M_attached_to(&__x),
00503 _M_message(__gnu_debug::__msg_splice_other)
00504 ._M_iterator(__i, "__i")._M_sequence(__x, "__x"));
00505
00506
00507
00508 this->_M_transfer_from_if(__x, _Equal(__i.base()));
00509 _Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base()),
00510 __i.base());
00511 }
00512
00513 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00514 void
00515 splice(iterator __position, list& __x, iterator __i)
00516 { splice(__position, std::move(__x), __i); }
00517 #endif
00518
00519 void
00520 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00521 splice(iterator __position, list&& __x, iterator __first,
00522 iterator __last)
00523 #else
00524 splice(iterator __position, list& __x, iterator __first,
00525 iterator __last)
00526 #endif
00527 {
00528 __glibcxx_check_insert(__position);
00529 __glibcxx_check_valid_range(__first, __last);
00530 _GLIBCXX_DEBUG_VERIFY(__first._M_attached_to(&__x),
00531 _M_message(__gnu_debug::__msg_splice_other)
00532 ._M_sequence(__x, "x")
00533 ._M_iterator(__first, "first"));
00534
00535
00536
00537
00538 for (_Base_iterator __tmp = __first.base();
00539 __tmp != __last.base(); ++__tmp)
00540 {
00541 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
00542 _M_message(__gnu_debug::__msg_valid_range)
00543 ._M_iterator(__first, "first")
00544 ._M_iterator(__last, "last"));
00545 _GLIBCXX_DEBUG_VERIFY(&__x != this || __tmp != __position,
00546 _M_message(__gnu_debug::__msg_splice_overlap)
00547 ._M_iterator(__tmp, "position")
00548 ._M_iterator(__first, "first")
00549 ._M_iterator(__last, "last"));
00550
00551
00552 this->_M_transfer_from_if(__x, _Equal(__tmp));
00553 }
00554
00555 _Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base()),
00556 __first.base(), __last.base());
00557 }
00558
00559 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00560 void
00561 splice(iterator __position, list& __x, iterator __first, iterator __last)
00562 { splice(__position, std::move(__x), __first, __last); }
00563 #endif
00564
00565 void
00566 remove(const _Tp& __value)
00567 {
00568 for (_Base_iterator __x = _Base::begin(); __x != _Base::end(); )
00569 {
00570 if (*__x == __value)
00571 __x = _M_erase(__x);
00572 else
00573 ++__x;
00574 }
00575 }
00576
00577 template<class _Predicate>
00578 void
00579 remove_if(_Predicate __pred)
00580 {
00581 for (_Base_iterator __x = _Base::begin(); __x != _Base::end(); )
00582 {
00583 if (__pred(*__x))
00584 __x = _M_erase(__x);
00585 else
00586 ++__x;
00587 }
00588 }
00589
00590 void
00591 unique()
00592 {
00593 _Base_iterator __first = _Base::begin();
00594 _Base_iterator __last = _Base::end();
00595 if (__first == __last)
00596 return;
00597 _Base_iterator __next = __first; ++__next;
00598 while (__next != __last)
00599 {
00600 if (*__first == *__next)
00601 __next = _M_erase(__next);
00602 else
00603 __first = __next++;
00604 }
00605 }
00606
00607 template<class _BinaryPredicate>
00608 void
00609 unique(_BinaryPredicate __binary_pred)
00610 {
00611 _Base_iterator __first = _Base::begin();
00612 _Base_iterator __last = _Base::end();
00613 if (__first == __last)
00614 return;
00615 _Base_iterator __next = __first; ++__next;
00616 while (__next != __last)
00617 {
00618 if (__binary_pred(*__first, *__next))
00619 __next = _M_erase(__next);
00620 else
00621 __first = __next++;
00622 }
00623 }
00624
00625 void
00626 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00627 merge(list&& __x)
00628 #else
00629 merge(list& __x)
00630 #endif
00631 {
00632
00633
00634 if (this != &__x)
00635 {
00636 __glibcxx_check_sorted(_Base::begin(), _Base::end());
00637 __glibcxx_check_sorted(__x.begin().base(), __x.end().base());
00638 this->_M_transfer_from_if(__x, _Not_equal(__x._M_base().end()));
00639 _Base::merge(_GLIBCXX_MOVE(__x._M_base()));
00640 }
00641 }
00642
00643 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00644 void
00645 merge(list& __x)
00646 { merge(std::move(__x)); }
00647 #endif
00648
00649 template<class _Compare>
00650 void
00651 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00652 merge(list&& __x, _Compare __comp)
00653 #else
00654 merge(list& __x, _Compare __comp)
00655 #endif
00656 {
00657
00658
00659 if (this != &__x)
00660 {
00661 __glibcxx_check_sorted_pred(_Base::begin(), _Base::end(),
00662 __comp);
00663 __glibcxx_check_sorted_pred(__x.begin().base(), __x.end().base(),
00664 __comp);
00665 this->_M_transfer_from_if(__x, _Not_equal(__x._M_base().end()));
00666 _Base::merge(_GLIBCXX_MOVE(__x._M_base()), __comp);
00667 }
00668 }
00669
00670 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00671 template<typename _Compare>
00672 void
00673 merge(list& __x, _Compare __comp)
00674 { merge(std::move(__x), __comp); }
00675 #endif
00676
00677 void
00678 sort() { _Base::sort(); }
00679
00680 template<typename _StrictWeakOrdering>
00681 void
00682 sort(_StrictWeakOrdering __pred) { _Base::sort(__pred); }
00683
00684 using _Base::reverse;
00685
00686 _Base&
00687 _M_base() { return *this; }
00688
00689 const _Base&
00690 _M_base() const { return *this; }
00691
00692 private:
00693 void
00694 _M_invalidate_all()
00695 {
00696 this->_M_invalidate_if(_Not_equal(_Base::end()));
00697 }
00698 };
00699
00700 template<typename _Tp, typename _Alloc>
00701 inline bool
00702 operator==(const list<_Tp, _Alloc>& __lhs,
00703 const list<_Tp, _Alloc>& __rhs)
00704 { return __lhs._M_base() == __rhs._M_base(); }
00705
00706 template<typename _Tp, typename _Alloc>
00707 inline bool
00708 operator!=(const list<_Tp, _Alloc>& __lhs,
00709 const list<_Tp, _Alloc>& __rhs)
00710 { return __lhs._M_base() != __rhs._M_base(); }
00711
00712 template<typename _Tp, typename _Alloc>
00713 inline bool
00714 operator<(const list<_Tp, _Alloc>& __lhs,
00715 const list<_Tp, _Alloc>& __rhs)
00716 { return __lhs._M_base() < __rhs._M_base(); }
00717
00718 template<typename _Tp, typename _Alloc>
00719 inline bool
00720 operator<=(const list<_Tp, _Alloc>& __lhs,
00721 const list<_Tp, _Alloc>& __rhs)
00722 { return __lhs._M_base() <= __rhs._M_base(); }
00723
00724 template<typename _Tp, typename _Alloc>
00725 inline bool
00726 operator>=(const list<_Tp, _Alloc>& __lhs,
00727 const list<_Tp, _Alloc>& __rhs)
00728 { return __lhs._M_base() >= __rhs._M_base(); }
00729
00730 template<typename _Tp, typename _Alloc>
00731 inline bool
00732 operator>(const list<_Tp, _Alloc>& __lhs,
00733 const list<_Tp, _Alloc>& __rhs)
00734 { return __lhs._M_base() > __rhs._M_base(); }
00735
00736 template<typename _Tp, typename _Alloc>
00737 inline void
00738 swap(list<_Tp, _Alloc>& __lhs, list<_Tp, _Alloc>& __rhs)
00739 { __lhs.swap(__rhs); }
00740
00741 }
00742 }
00743
00744 #endif