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