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