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