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