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