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