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
00061
#ifndef __GLIBCPP_INTERNAL_LIST_H
00062
#define __GLIBCPP_INTERNAL_LIST_H
00063
00064
#include <bits/concept_check.h>
00065
00066
namespace std
00067 {
00068
00069
struct _List_node_base
00070 {
00071 _List_node_base* _M_next;
00072 _List_node_base* _M_prev;
00073 };
00074
00075
template<
typename _Tp>
00076
struct _List_node :
public _List_node_base
00077 {
00078 _Tp _M_data;
00079 };
00080
00081
struct _List_iterator_base
00082 {
00083
typedef size_t size_type;
00084
typedef ptrdiff_t difference_type;
00085
typedef bidirectional_iterator_tag iterator_category;
00086
00087 _List_node_base* _M_node;
00088
00089 _List_iterator_base(_List_node_base* __x)
00090 : _M_node(__x)
00091 { }
00092
00093 _List_iterator_base()
00094 { }
00095
00096
void
00097 _M_incr()
00098 { _M_node = _M_node->_M_next; }
00099
00100
void
00101 _M_decr()
00102 { _M_node = _M_node->_M_prev; }
00103
00104
bool
00105
operator==(
const _List_iterator_base& __x)
const
00106
{
return _M_node == __x._M_node; }
00107
00108
bool
00109
operator!=(
const _List_iterator_base& __x)
const
00110
{
return _M_node != __x._M_node; }
00111 };
00112
00113
template<
typename _Tp,
typename _Ref,
typename _Ptr>
00114
struct _List_iterator :
public _List_iterator_base
00115 {
00116
typedef _List_iterator<_Tp,_Tp&,_Tp*> iterator;
00117
typedef _List_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;
00118
typedef _List_iterator<_Tp,_Ref,_Ptr> _Self;
00119
00120
typedef _Tp value_type;
00121
typedef _Ptr pointer;
00122
typedef _Ref reference;
00123
typedef _List_node<_Tp> _Node;
00124
00125 _List_iterator(_Node* __x)
00126 : _List_iterator_base(__x)
00127 { }
00128
00129 _List_iterator()
00130 { }
00131
00132 _List_iterator(
const iterator& __x)
00133 : _List_iterator_base(__x._M_node)
00134 { }
00135
00136 reference
00137 operator*()
const
00138
{
return ((_Node*) _M_node)->_M_data; }
00139
00140 pointer
00141 operator->()
const
00142
{
return &(operator*()); }
00143
00144 _Self&
00145 operator++()
00146 {
00147 this->_M_incr();
00148
return *
this;
00149 }
00150
00151 _Self
00152 operator++(
int)
00153 {
00154 _Self __tmp = *
this;
00155 this->_M_incr();
00156
return __tmp;
00157 }
00158
00159 _Self&
00160 operator--()
00161 {
00162 this->_M_decr();
00163
return *
this;
00164 }
00165
00166 _Self
00167 operator--(
int)
00168 {
00169 _Self __tmp = *
this;
00170 this->_M_decr();
00171
return __tmp;
00172 }
00173 };
00174
00175
00176
00177
00178
00179
00180
00181
00182
00183
00184
00185
template<
typename _Tp,
typename _Allocator,
bool _IsStatic>
00186
class _List_alloc_base
00187 {
00188
public:
00189
typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type
00190 allocator_type;
00191
00192 allocator_type
00193 get_allocator()
const
00194
{
return _Node_allocator; }
00195
00196 _List_alloc_base(
const allocator_type& __a)
00197 : _Node_allocator(__a)
00198 { }
00199
00200
protected:
00201 _List_node<_Tp>*
00202 _M_get_node()
00203 {
return _Node_allocator.allocate(1); }
00204
00205
void
00206 _M_put_node(_List_node<_Tp>* __p)
00207 { _Node_allocator.deallocate(__p, 1); }
00208
00209
protected:
00210
typename _Alloc_traits<_List_node<_Tp>, _Allocator>::allocator_type
00211 _Node_allocator;
00212
00213 _List_node<_Tp>* _M_node;
00214 };
00215
00216
00217
00218
template<
typename _Tp,
typename _Allocator>
00219
class _List_alloc_base<_Tp, _Allocator, true>
00220 {
00221
public:
00222
typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type
00223 allocator_type;
00224
00225 allocator_type
00226 get_allocator()
const
00227
{
return allocator_type(); }
00228
00229 _List_alloc_base(
const allocator_type&)
00230 { }
00231
00232
protected:
00233
typedef typename _Alloc_traits<_List_node<_Tp>, _Allocator>::_Alloc_type
00234 _Alloc_type;
00235
00236 _List_node<_Tp>*
00237 _M_get_node()
00238 {
return _Alloc_type::allocate(1); }
00239
00240
void
00241 _M_put_node(_List_node<_Tp>* __p)
00242 { _Alloc_type::deallocate(__p, 1); }
00243
00244
protected:
00245 _List_node<_Tp>* _M_node;
00246 };
00247
00248
template<
typename _Tp,
typename _Alloc>
00249
class _List_base
00250 :
public _List_alloc_base<_Tp, _Alloc,
00251 _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
00252 {
00253
public:
00254
typedef _List_alloc_base<_Tp, _Alloc,
00255 _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
00256 _Base;
00257
typedef typename _Base::allocator_type allocator_type;
00258
00259 _List_base(
const allocator_type& __a)
00260 : _Base(__a)
00261 {
00262 _M_node = _M_get_node();
00263 _M_node->_M_next = _M_node;
00264 _M_node->_M_prev = _M_node;
00265 }
00266
00267 ~_List_base()
00268 {
00269 clear();
00270 _M_put_node(_M_node);
00271 }
00272
00273
void clear();
00274 };
00275
00289
template<
typename _Tp,
typename _Alloc = allocator<_Tp> >
00290
class list :
protected _List_base<_Tp, _Alloc>
00291 {
00292
00293 __glibcpp_class_requires(_Tp, _SGIAssignableConcept)
00294
00295
typedef _List_base<_Tp, _Alloc> _Base;
00296
protected:
00297
typedef void* _Void_pointer;
00298
00299
public:
00300
typedef _Tp value_type;
00301
typedef value_type* pointer;
00302
typedef const value_type* const_pointer;
00303
typedef value_type& reference;
00304
typedef const value_type& const_reference;
00305
typedef _List_node<_Tp> _Node;
00306
typedef size_t size_type;
00307
typedef ptrdiff_t difference_type;
00308
00309
typedef typename _Base::allocator_type allocator_type;
00310
00311
typedef _List_iterator<_Tp,_Tp&,_Tp*> iterator;
00312
typedef _List_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;
00313
00314
typedef reverse_iterator<const_iterator> const_reverse_iterator;
00315
typedef reverse_iterator<iterator> reverse_iterator;
00316
00317
protected:
00318
using _Base::_M_node;
00319
using _Base::_M_put_node;
00320
using _Base::_M_get_node;
00321
00322
protected:
00323 _Node*
00324 _M_create_node(
const _Tp& __x)
00325 {
00326 _Node* __p = _M_get_node();
00327
try {
00328 _Construct(&__p->_M_data, __x);
00329 }
00330
catch(...)
00331 {
00332 _M_put_node(__p);
00333 __throw_exception_again;
00334 }
00335
return __p;
00336 }
00337
00338 _Node*
00339 _M_create_node()
00340 {
00341 _Node* __p = _M_get_node();
00342
try {
00343 _Construct(&__p->_M_data);
00344 }
00345
catch(...)
00346 {
00347 _M_put_node(__p);
00348 __throw_exception_again;
00349 }
00350
return __p;
00351 }
00352
00353
public:
00354 allocator_type
00355 get_allocator()
const
00356
{
return _Base::get_allocator(); }
00357
00358
explicit
00359
list(
const allocator_type& __a = allocator_type())
00360 : _Base(__a)
00361 { }
00362
00363 iterator
00364 begin()
00365 {
return static_cast<_Node*>(_M_node->_M_next); }
00366
00367 const_iterator
00368 begin()
const
00369
{
return static_cast<_Node*>(_M_node->_M_next); }
00370
00371 iterator
00372 end()
00373 {
return _M_node; }
00374
00375 const_iterator
00376 end()
const
00377
{
return _M_node; }
00378
00379 reverse_iterator
00380 rbegin()
00381 {
return reverse_iterator(end()); }
00382
00383 const_reverse_iterator
00384 rbegin()
const
00385
{
return const_reverse_iterator(end()); }
00386
00387 reverse_iterator
00388 rend()
00389 {
return reverse_iterator(begin()); }
00390
00391 const_reverse_iterator
00392 rend()
const
00393
{
return const_reverse_iterator(begin()); }
00394
00395
bool
00396 empty()
const
00397
{
return _M_node->_M_next == _M_node; }
00398
00399 size_type
00400 size()
const
00401
{
return distance(begin(), end()); }
00402
00403 size_type
00404 max_size()
const
00405
{
return size_type(-1); }
00406
00407 reference
00408 front()
00409 {
return *begin(); }
00410
00411 const_reference
00412 front()
const
00413
{
return *begin(); }
00414
00415 reference
00416 back()
00417 {
return *(--end()); }
00418
00419 const_reference
00420 back()
const
00421
{
return *(--end()); }
00422
00423
void
00424
swap(
list<_Tp, _Alloc>& __x)
00425 {
std::swap(_M_node, __x._M_node); }
00426
00427 iterator
00428 insert(iterator __position,
const _Tp& __x)
00429 {
00430 _Node* __tmp = _M_create_node(__x);
00431 __tmp->_M_next = __position._M_node;
00432 __tmp->_M_prev = __position._M_node->_M_prev;
00433 __position._M_node->_M_prev->_M_next = __tmp;
00434 __position._M_node->_M_prev = __tmp;
00435
return __tmp;
00436 }
00437
00438 iterator
00439 insert(iterator __position)
00440 {
return insert(__position, _Tp()); }
00441
00442
00443
template<
typename _Integer>
00444
void
00445 _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x, __true_type)
00446 { _M_fill_insert(__pos, (size_type) __n, (_Tp) __x); }
00447
00448
template<
typename _InputIterator>
00449
void
00450 _M_insert_dispatch(iterator __pos,
00451 _InputIterator __first, _InputIterator __last,
00452 __false_type);
00453
00454
template<
typename _InputIterator>
00455
void
00456 insert(iterator __pos, _InputIterator __first, _InputIterator __last)
00457 {
00458
typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
00459 _M_insert_dispatch(__pos, __first, __last, _Integral());
00460 }
00461
00462
void
00463 insert(iterator __pos, size_type __n,
const _Tp& __x)
00464 { _M_fill_insert(__pos, __n, __x); }
00465
00466
void
00467 _M_fill_insert(iterator __pos, size_type __n,
const _Tp& __x);
00468
00469
void
00470 push_front(
const _Tp& __x)
00471 { insert(begin(), __x); }
00472
00473
void
00474 push_front()
00475 { insert(begin()); }
00476
00477
void
00478 push_back(
const _Tp& __x)
00479 { insert(end(), __x); }
00480
00481
void
00482 push_back()
00483 { insert(end()); }
00484
00485 iterator
00486 erase(iterator __position)
00487 {
00488 _List_node_base* __next_node = __position._M_node->_M_next;
00489 _List_node_base* __prev_node = __position._M_node->_M_prev;
00490 _Node* __n = static_cast<_Node*>(__position._M_node);
00491 __prev_node->_M_next = __next_node;
00492 __next_node->_M_prev = __prev_node;
00493 _Destroy(&__n->_M_data);
00494 _M_put_node(__n);
00495
return iterator(static_cast<_Node*>(__next_node));
00496 }
00497
00498 iterator
00499 erase(iterator __first, iterator __last);
00500
00501
void
00502 clear()
00503 { _Base::clear(); }
00504
00505
void
00506 resize(size_type __new_size,
const _Tp& __x);
00507
00508
void
00509 resize(size_type __new_size)
00510 { this->resize(__new_size, _Tp()); }
00511
00512
void
00513 pop_front()
00514 { erase(begin()); }
00515
00516
void
00517 pop_back()
00518 {
00519 iterator __tmp = end();
00520 erase(--__tmp);
00521 }
00522
00523
list(size_type __n,
const _Tp& __value,
00524
const allocator_type& __a = allocator_type())
00525 : _Base(__a)
00526 { insert(begin(), __n, __value); }
00527
00528
explicit
00529
list(size_type __n)
00530 : _Base(allocator_type())
00531 { insert(begin(), __n, _Tp()); }
00532
00533
00534
00535
template<
typename _InputIterator>
00536
list(_InputIterator __first, _InputIterator __last,
00537
const allocator_type& __a = allocator_type())
00538 : _Base(__a)
00539 { insert(begin(), __first, __last); }
00540
00541
list(
const list<_Tp, _Alloc>& __x)
00542 : _Base(__x.
get_allocator())
00543 { insert(begin(), __x.
begin(), __x.
end()); }
00544
00545 ~
list()
00546 { }
00547
00548
list<_Tp, _Alloc>&
00549 operator=(
const list<_Tp, _Alloc>& __x);
00550
00551
public:
00552
00553
00554
00555
00556
00557
void
00558 assign(size_type __n,
const _Tp& __val)
00559 { _M_fill_assign(__n, __val); }
00560
00561
void
00562 _M_fill_assign(size_type __n,
const _Tp& __val);
00563
00564
template<
typename _InputIterator>
00565
void
00566 assign(_InputIterator __first, _InputIterator __last)
00567 {
00568
typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
00569 _M_assign_dispatch(__first, __last, _Integral());
00570 }
00571
00572
template<
typename _Integer>
00573
void
00574 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
00575 { _M_fill_assign((size_type) __n, (_Tp) __val); }
00576
00577
template<
typename _InputIterator>
00578
void
00579 _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
00580 __false_type);
00581
00582
protected:
00583
void
00584 _M_transfer(iterator __position, iterator __first, iterator __last)
00585 {
00586
if (__position != __last) {
00587
00588 __last._M_node->_M_prev->_M_next = __position._M_node;
00589 __first._M_node->_M_prev->_M_next = __last._M_node;
00590 __position._M_node->_M_prev->_M_next = __first._M_node;
00591
00592
00593 _List_node_base* __tmp = __position._M_node->_M_prev;
00594 __position._M_node->_M_prev = __last._M_node->_M_prev;
00595 __last._M_node->_M_prev = __first._M_node->_M_prev;
00596 __first._M_node->_M_prev = __tmp;
00597 }
00598 }
00599
00600
public:
00601
void
00602 splice(iterator __position,
list& __x)
00603 {
00604
if (!__x.
empty())
00605 this->_M_transfer(__position, __x.
begin(), __x.
end());
00606 }
00607
00608
void
00609 splice(iterator __position,
list&, iterator __i)
00610 {
00611 iterator __j = __i;
00612 ++__j;
00613
if (__position == __i || __position == __j)
return;
00614 this->_M_transfer(__position, __i, __j);
00615 }
00616
00617
void
00618 splice(iterator __position,
list&, iterator __first, iterator __last)
00619 {
00620
if (__first != __last)
00621 this->_M_transfer(__position, __first, __last);
00622 }
00623
00624
void
00625
remove(
const _Tp& __value);
00626
00627
void
00628
unique();
00629
00630
void
00631
merge(
list& __x);
00632
00633
void
00634
reverse();
00635
00636
void
00637
sort();
00638
00639
template<
typename _Predicate>
00640
void
00641
remove_if(_Predicate);
00642
00643
template<
typename _BinaryPredicate>
00644
void
00645
unique(_BinaryPredicate);
00646
00647
template<
typename _StrictWeakOrdering>
00648
void
00649
merge(
list&, _StrictWeakOrdering);
00650
00651
template<
typename _StrictWeakOrdering>
00652
void
00653
sort(_StrictWeakOrdering);
00654 };
00655
00656
template<
typename _Tp,
typename _Alloc>
00657
inline bool
00658
operator==(
const list<_Tp,_Alloc>& __x,
const list<_Tp,_Alloc>& __y)
00659 {
00660
typedef typename list<_Tp,_Alloc>::const_iterator const_iterator;
00661 const_iterator __end1 = __x.
end();
00662 const_iterator __end2 = __y.
end();
00663
00664 const_iterator __i1 = __x.
begin();
00665 const_iterator __i2 = __y.
begin();
00666
while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2) {
00667 ++__i1;
00668 ++__i2;
00669 }
00670
return __i1 == __end1 && __i2 == __end2;
00671 }
00672
00673
template<
typename _Tp,
typename _Alloc>
00674
inline bool
00675 operator<(const list<_Tp,_Alloc>& __x,
const list<_Tp,_Alloc>& __y)
00676 {
00677
return lexicographical_compare(__x.begin(), __x.end(),
00678 __y.begin(), __y.end());
00679 }
00680
00681
template<
typename _Tp,
typename _Alloc>
00682
inline bool
00683
operator!=(
const list<_Tp,_Alloc>& __x,
const list<_Tp,_Alloc>& __y)
00684 {
return !(__x == __y); }
00685
00686
template<
typename _Tp,
typename _Alloc>
00687
inline bool
00688
operator>(
const list<_Tp,_Alloc>& __x,
const list<_Tp,_Alloc>& __y)
00689 {
return __y < __x; }
00690
00691
template<
typename _Tp,
typename _Alloc>
00692
inline bool
00693 operator<=(const list<_Tp,_Alloc>& __x,
const list<_Tp,_Alloc>& __y)
00694 {
return !(__y < __x); }
00695
00696
template<
typename _Tp,
typename _Alloc>
00697
inline bool
00698
operator>=(
const list<_Tp,_Alloc>& __x,
const list<_Tp,_Alloc>& __y)
00699 {
return !(__x < __y); }
00700
00701
template<
typename _Tp,
typename _Alloc>
00702
inline void
00703
swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y)
00704 { __x.swap(__y); }
00705
00706
00707
00708
template<
typename _Tp,
typename _Alloc>
00709
void _List_base<_Tp,_Alloc>::
00710 clear()
00711 {
00712 _List_node<_Tp>* __cur = static_cast<_List_node<_Tp>*>(_M_node->_M_next);
00713
while (__cur != _M_node) {
00714 _List_node<_Tp>* __tmp = __cur;
00715 __cur = static_cast<_List_node<_Tp>*>(__cur->_M_next);
00716 _Destroy(&__tmp->_M_data);
00717 _M_put_node(__tmp);
00718 }
00719 _M_node->_M_next = _M_node;
00720 _M_node->_M_prev = _M_node;
00721 }
00722
00723
template<
typename _Tp,
typename _Alloc>
00724
template <
typename _InputIter>
00725
void list<_Tp, _Alloc>::
00726 _M_insert_dispatch(iterator __position, _InputIter __first, _InputIter __last,
00727 __false_type)
00728 {
00729
for ( ; __first != __last; ++__first)
00730 insert(__position, *__first);
00731
00732 }
00733
00734
template<
typename _Tp,
typename _Alloc>
00735
void list<_Tp, _Alloc>::
00736 _M_fill_insert(iterator __position, size_type __n,
const _Tp& __x)
00737 {
00738
for ( ; __n > 0; --__n)
00739 insert(__position, __x);
00740 }
00741
00742
template<
typename _Tp,
typename _Alloc>
00743
typename list<_Tp,_Alloc>::iterator list<_Tp, _Alloc>::
00744 erase(iterator __first, iterator __last)
00745 {
00746
while (__first != __last)
00747 erase(__first++);
00748
return __last;
00749 }
00750
00751
template<
typename _Tp,
typename _Alloc>
00752
void list<_Tp, _Alloc>::
00753 resize(size_type __new_size,
const _Tp& __x)
00754 {
00755 iterator __i = begin();
00756 size_type __len = 0;
00757
for ( ; __i != end() && __len < __new_size; ++__i, ++__len)
00758 ;
00759
if (__len == __new_size)
00760 erase(__i, end());
00761
else
00762 insert(end(), __new_size - __len, __x);
00763 }
00764
00765
template<
typename _Tp,
typename _Alloc>
00766 list<_Tp, _Alloc>& list<_Tp, _Alloc>::
00767 operator=(
const list<_Tp, _Alloc>& __x)
00768 {
00769
if (
this != &__x) {
00770 iterator __first1 = begin();
00771 iterator __last1 = end();
00772 const_iterator __first2 = __x.begin();
00773 const_iterator __last2 = __x.end();
00774
while (__first1 != __last1 && __first2 != __last2)
00775 *__first1++ = *__first2++;
00776
if (__first2 == __last2)
00777 erase(__first1, __last1);
00778
else
00779 insert(__last1, __first2, __last2);
00780 }
00781
return *
this;
00782 }
00783
00784
template<
typename _Tp,
typename _Alloc>
00785
void list<_Tp, _Alloc>::
00786 _M_fill_assign(size_type __n,
const _Tp& __val) {
00787 iterator __i = begin();
00788
for ( ; __i != end() && __n > 0; ++__i, --__n)
00789 *__i = __val;
00790
if (__n > 0)
00791 insert(end(), __n, __val);
00792
else
00793 erase(__i, end());
00794 }
00795
00796
template<
typename _Tp,
typename _Alloc>
00797
template <
typename _InputIter>
00798
void list<_Tp, _Alloc>::
00799 _M_assign_dispatch(_InputIter __first2, _InputIter __last2, __false_type)
00800 {
00801 iterator __first1 = begin();
00802 iterator __last1 = end();
00803
for ( ; __first1 != __last1 && __first2 != __last2; ++__first1, ++__first2)
00804 *__first1 = *__first2;
00805
if (__first2 == __last2)
00806 erase(__first1, __last1);
00807
else
00808 insert(__last1, __first2, __last2);
00809 }
00810
00811
template<
typename _Tp,
typename _Alloc>
00812
void list<_Tp, _Alloc>::
00813 remove(
const _Tp& __value)
00814 {
00815 iterator __first = begin();
00816 iterator __last = end();
00817
while (__first != __last) {
00818 iterator __next = __first;
00819 ++__next;
00820
if (*__first == __value) erase(__first);
00821 __first = __next;
00822 }
00823 }
00824
00825
template<
typename _Tp,
typename _Alloc>
00826
void list<_Tp, _Alloc>::
00827 unique()
00828 {
00829 iterator __first = begin();
00830 iterator __last = end();
00831
if (__first == __last)
return;
00832 iterator __next = __first;
00833
while (++__next != __last) {
00834
if (*__first == *__next)
00835 erase(__next);
00836
else
00837 __first = __next;
00838 __next = __first;
00839 }
00840 }
00841
00842
template<
typename _Tp,
typename _Alloc>
00843
void list<_Tp, _Alloc>::
00844 merge(list<_Tp, _Alloc>& __x)
00845 {
00846 iterator __first1 = begin();
00847 iterator __last1 = end();
00848 iterator __first2 = __x.begin();
00849 iterator __last2 = __x.end();
00850
while (__first1 != __last1 && __first2 != __last2)
00851
if (*__first2 < *__first1) {
00852 iterator __next = __first2;
00853 _M_transfer(__first1, __first2, ++__next);
00854 __first2 = __next;
00855 }
00856
else
00857 ++__first1;
00858
if (__first2 != __last2) _M_transfer(__last1, __first2, __last2);
00859 }
00860
00861
inline void
00862 __List_base_reverse(_List_node_base* __p)
00863 {
00864 _List_node_base* __tmp = __p;
00865
do {
00866
std::swap(__tmp->_M_next, __tmp->_M_prev);
00867 __tmp = __tmp->_M_prev;
00868 }
while (__tmp != __p);
00869 }
00870
00871
template<
typename _Tp,
typename _Alloc>
00872
inline void list<_Tp, _Alloc>::
00873 reverse()
00874 { __List_base_reverse(this->_M_node); }
00875
00876
template<
typename _Tp,
typename _Alloc>
00877
void list<_Tp, _Alloc>::
00878 sort()
00879 {
00880
00881
if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node) {
00882 list<_Tp, _Alloc> __carry;
00883 list<_Tp, _Alloc> __counter[64];
00884
int __fill = 0;
00885
while (!empty()) {
00886 __carry.splice(__carry.begin(), *
this, begin());
00887
int __i = 0;
00888
while(__i < __fill && !__counter[__i].empty()) {
00889 __counter[__i].merge(__carry);
00890 __carry.swap(__counter[__i++]);
00891 }
00892 __carry.swap(__counter[__i]);
00893
if (__i == __fill) ++__fill;
00894 }
00895
00896
for (
int __i = 1; __i < __fill; ++__i)
00897 __counter[__i].merge(__counter[__i-1]);
00898
swap(__counter[__fill-1]);
00899 }
00900 }
00901
00902
template<
typename _Tp,
typename _Alloc>
00903
template <
typename _Predicate>
00904
void list<_Tp, _Alloc>::
00905 remove_if(_Predicate __pred)
00906 {
00907 iterator __first = begin();
00908 iterator __last = end();
00909
while (__first != __last) {
00910 iterator __next = __first;
00911 ++__next;
00912
if (__pred(*__first)) erase(__first);
00913 __first = __next;
00914 }
00915 }
00916
00917
template<
typename _Tp,
typename _Alloc>
00918
template <
typename _BinaryPredicate>
00919
void list<_Tp, _Alloc>::
00920 unique(_BinaryPredicate __binary_pred)
00921 {
00922 iterator __first = begin();
00923 iterator __last = end();
00924
if (__first == __last)
return;
00925 iterator __next = __first;
00926
while (++__next != __last) {
00927
if (__binary_pred(*__first, *__next))
00928 erase(__next);
00929
else
00930 __first = __next;
00931 __next = __first;
00932 }
00933 }
00934
00935
template<
typename _Tp,
typename _Alloc>
00936
template <
typename _StrictWeakOrdering>
00937
void list<_Tp, _Alloc>::
00938 merge(list<_Tp, _Alloc>& __x, _StrictWeakOrdering __comp)
00939 {
00940 iterator __first1 = begin();
00941 iterator __last1 = end();
00942 iterator __first2 = __x.begin();
00943 iterator __last2 = __x.end();
00944
while (__first1 != __last1 && __first2 != __last2)
00945
if (__comp(*__first2, *__first1)) {
00946 iterator __next = __first2;
00947 _M_transfer(__first1, __first2, ++__next);
00948 __first2 = __next;
00949 }
00950
else
00951 ++__first1;
00952
if (__first2 != __last2) _M_transfer(__last1, __first2, __last2);
00953 }
00954
00955
template<
typename _Tp,
typename _Alloc>
00956
template <
typename _StrictWeakOrdering>
00957
void list<_Tp, _Alloc>::
00958 sort(_StrictWeakOrdering __comp)
00959 {
00960
00961
if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node) {
00962 list<_Tp, _Alloc> __carry;
00963 list<_Tp, _Alloc> __counter[64];
00964
int __fill = 0;
00965
while (!empty()) {
00966 __carry.splice(__carry.begin(), *
this, begin());
00967
int __i = 0;
00968
while(__i < __fill && !__counter[__i].empty()) {
00969 __counter[__i].merge(__carry, __comp);
00970 __carry.swap(__counter[__i++]);
00971 }
00972 __carry.swap(__counter[__i]);
00973
if (__i == __fill) ++__fill;
00974 }
00975
00976
for (
int __i = 1; __i < __fill; ++__i)
00977 __counter[__i].merge(__counter[__i-1], __comp);
00978
swap(__counter[__fill-1]);
00979 }
00980 }
00981
00982 }
00983
00984
#endif
00985
00986
00987
00988
00989