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