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