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