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
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060 #ifndef __SGI_STL_INTERNAL_LIST_H
00061 #define __SGI_STL_INTERNAL_LIST_H
00062
00063 #include <bits/concept_check.h>
00064
00065 namespace std
00066 {
00067
00068 struct _List_node_base {
00069 _List_node_base* _M_next;
00070 _List_node_base* _M_prev;
00071 };
00072
00073 template <class _Tp>
00074 struct _List_node : public _List_node_base {
00075 _Tp _M_data;
00076 };
00077
00078 struct _List_iterator_base {
00079 typedef size_t size_type;
00080 typedef ptrdiff_t difference_type;
00081 typedef bidirectional_iterator_tag iterator_category;
00082
00083 _List_node_base* _M_node;
00084
00085 _List_iterator_base(_List_node_base* __x) : _M_node(__x) {}
00086 _List_iterator_base() {}
00087
00088 void _M_incr() { _M_node = _M_node->_M_next; }
00089 void _M_decr() { _M_node = _M_node->_M_prev; }
00090
00091 bool operator==(const _List_iterator_base& __x) const {
00092 return _M_node == __x._M_node;
00093 }
00094 bool operator!=(const _List_iterator_base& __x) const {
00095 return _M_node != __x._M_node;
00096 }
00097 };
00098
00099 template<class _Tp, class _Ref, class _Ptr>
00100 struct _List_iterator : public _List_iterator_base {
00101 typedef _List_iterator<_Tp,_Tp&,_Tp*> iterator;
00102 typedef _List_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;
00103 typedef _List_iterator<_Tp,_Ref,_Ptr> _Self;
00104
00105 typedef _Tp value_type;
00106 typedef _Ptr pointer;
00107 typedef _Ref reference;
00108 typedef _List_node<_Tp> _Node;
00109
00110 _List_iterator(_Node* __x) : _List_iterator_base(__x) {}
00111 _List_iterator() {}
00112 _List_iterator(const iterator& __x) : _List_iterator_base(__x._M_node) {}
00113
00114 reference operator*() const { return ((_Node*) _M_node)->_M_data; }
00115 pointer operator->() const { return &(operator*()); }
00116
00117 _Self& operator++() {
00118 this->_M_incr();
00119 return *this;
00120 }
00121 _Self operator++(int) {
00122 _Self __tmp = *this;
00123 this->_M_incr();
00124 return __tmp;
00125 }
00126 _Self& operator--() {
00127 this->_M_decr();
00128 return *this;
00129 }
00130 _Self operator--(int) {
00131 _Self __tmp = *this;
00132 this->_M_decr();
00133 return __tmp;
00134 }
00135 };
00136
00137
00138
00139
00140
00141
00142
00143
00144
00145
00146
00147 template <class _Tp, class _Allocator, bool _IsStatic>
00148 class _List_alloc_base {
00149 public:
00150 typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type
00151 allocator_type;
00152 allocator_type get_allocator() const { return _Node_allocator; }
00153
00154 _List_alloc_base(const allocator_type& __a) : _Node_allocator(__a) {}
00155
00156 protected:
00157 _List_node<_Tp>* _M_get_node()
00158 { return _Node_allocator.allocate(1); }
00159 void _M_put_node(_List_node<_Tp>* __p)
00160 { _Node_allocator.deallocate(__p, 1); }
00161
00162 protected:
00163 typename _Alloc_traits<_List_node<_Tp>, _Allocator>::allocator_type
00164 _Node_allocator;
00165 _List_node<_Tp>* _M_node;
00166 };
00167
00168
00169
00170 template <class _Tp, class _Allocator>
00171 class _List_alloc_base<_Tp, _Allocator, true> {
00172 public:
00173 typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type
00174 allocator_type;
00175 allocator_type get_allocator() const { return allocator_type(); }
00176
00177 _List_alloc_base(const allocator_type&) {}
00178
00179 protected:
00180 typedef typename _Alloc_traits<_List_node<_Tp>, _Allocator>::_Alloc_type
00181 _Alloc_type;
00182 _List_node<_Tp>* _M_get_node() { return _Alloc_type::allocate(1); }
00183 void _M_put_node(_List_node<_Tp>* __p) { _Alloc_type::deallocate(__p, 1); }
00184
00185 protected:
00186 _List_node<_Tp>* _M_node;
00187 };
00188
00189 template <class _Tp, class _Alloc>
00190 class _List_base
00191 : public _List_alloc_base<_Tp, _Alloc,
00192 _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
00193 {
00194 public:
00195 typedef _List_alloc_base<_Tp, _Alloc,
00196 _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
00197 _Base;
00198 typedef typename _Base::allocator_type allocator_type;
00199
00200 _List_base(const allocator_type& __a) : _Base(__a) {
00201 _M_node = _M_get_node();
00202 _M_node->_M_next = _M_node;
00203 _M_node->_M_prev = _M_node;
00204 }
00205 ~_List_base() {
00206 clear();
00207 _M_put_node(_M_node);
00208 }
00209
00210 void clear();
00211 };
00212
00213
00214 template <class _Tp, class _Alloc>
00215 void
00216 _List_base<_Tp,_Alloc>::clear()
00217 {
00218 _List_node<_Tp>* __cur = (_List_node<_Tp>*) _M_node->_M_next;
00219 while (__cur != _M_node) {
00220 _List_node<_Tp>* __tmp = __cur;
00221 __cur = (_List_node<_Tp>*) __cur->_M_next;
00222 _Destroy(&__tmp->_M_data);
00223 _M_put_node(__tmp);
00224 }
00225 _M_node->_M_next = _M_node;
00226 _M_node->_M_prev = _M_node;
00227 }
00228
00229 template <class _Tp, class _Alloc = allocator<_Tp> >
00230 class list : protected _List_base<_Tp, _Alloc>
00231 {
00232
00233 __glibcpp_class_requires(_Tp, _SGIAssignableConcept);
00234
00235 typedef _List_base<_Tp, _Alloc> _Base;
00236 protected:
00237 typedef void* _Void_pointer;
00238
00239 public:
00240 typedef _Tp value_type;
00241 typedef value_type* pointer;
00242 typedef const value_type* const_pointer;
00243 typedef value_type& reference;
00244 typedef const value_type& const_reference;
00245 typedef _List_node<_Tp> _Node;
00246 typedef size_t size_type;
00247 typedef ptrdiff_t difference_type;
00248
00249 typedef typename _Base::allocator_type allocator_type;
00250 allocator_type get_allocator() const { return _Base::get_allocator(); }
00251
00252 public:
00253 typedef _List_iterator<_Tp,_Tp&,_Tp*> iterator;
00254 typedef _List_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;
00255
00256 typedef reverse_iterator<const_iterator> const_reverse_iterator;
00257 typedef reverse_iterator<iterator> reverse_iterator;
00258
00259 protected:
00260 using _Base::_M_node;
00261 using _Base::_M_put_node;
00262 using _Base::_M_get_node;
00263
00264 protected:
00265 _Node* _M_create_node(const _Tp& __x)
00266 {
00267 _Node* __p = _M_get_node();
00268 __STL_TRY {
00269 _Construct(&__p->_M_data, __x);
00270 }
00271 __STL_UNWIND(_M_put_node(__p));
00272 return __p;
00273 }
00274
00275 _Node* _M_create_node()
00276 {
00277 _Node* __p = _M_get_node();
00278 __STL_TRY {
00279 _Construct(&__p->_M_data);
00280 }
00281 __STL_UNWIND(_M_put_node(__p));
00282 return __p;
00283 }
00284
00285 public:
00286 explicit list(const allocator_type& __a = allocator_type()) : _Base(__a) {}
00287
00288 iterator begin() { return (_Node*)(_M_node->_M_next); }
00289 const_iterator begin() const { return (_Node*)(_M_node->_M_next); }
00290
00291 iterator end() { return _M_node; }
00292 const_iterator end() const { return _M_node; }
00293
00294 reverse_iterator rbegin()
00295 { return reverse_iterator(end()); }
00296 const_reverse_iterator rbegin() const
00297 { return const_reverse_iterator(end()); }
00298
00299 reverse_iterator rend()
00300 { return reverse_iterator(begin()); }
00301 const_reverse_iterator rend() const
00302 { return const_reverse_iterator(begin()); }
00303
00304 bool empty() const { return _M_node->_M_next == _M_node; }
00305 size_type size() const {
00306 size_type __result = 0;
00307 distance(begin(), end(), __result);
00308 return __result;
00309 }
00310 size_type max_size() const { return size_type(-1); }
00311
00312 reference front() { return *begin(); }
00313 const_reference front() const { return *begin(); }
00314 reference back() { return *(--end()); }
00315 const_reference back() const { return *(--end()); }
00316
00317 void swap(list<_Tp, _Alloc>& __x) { std::swap(_M_node, __x._M_node); }
00318
00319 iterator insert(iterator __position, const _Tp& __x) {
00320 _Node* __tmp = _M_create_node(__x);
00321 __tmp->_M_next = __position._M_node;
00322 __tmp->_M_prev = __position._M_node->_M_prev;
00323 __position._M_node->_M_prev->_M_next = __tmp;
00324 __position._M_node->_M_prev = __tmp;
00325 return __tmp;
00326 }
00327 iterator insert(iterator __position) { return insert(__position, _Tp()); }
00328
00329
00330 template<class _Integer>
00331 void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
00332 __true_type) {
00333 _M_fill_insert(__pos, (size_type) __n, (_Tp) __x);
00334 }
00335
00336 template <class _InputIterator>
00337 void _M_insert_dispatch(iterator __pos,
00338 _InputIterator __first, _InputIterator __last,
00339 __false_type);
00340
00341 template <class _InputIterator>
00342 void insert(iterator __pos, _InputIterator __first, _InputIterator __last) {
00343 typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
00344 _M_insert_dispatch(__pos, __first, __last, _Integral());
00345 }
00346
00347 void insert(iterator __pos, size_type __n, const _Tp& __x)
00348 { _M_fill_insert(__pos, __n, __x); }
00349 void _M_fill_insert(iterator __pos, size_type __n, const _Tp& __x);
00350
00351 void push_front(const _Tp& __x) { insert(begin(), __x); }
00352 void push_front() {insert(begin());}
00353 void push_back(const _Tp& __x) { insert(end(), __x); }
00354 void push_back() {insert(end());}
00355
00356 iterator erase(iterator __position) {
00357 _List_node_base* __next_node = __position._M_node->_M_next;
00358 _List_node_base* __prev_node = __position._M_node->_M_prev;
00359 _Node* __n = (_Node*) __position._M_node;
00360 __prev_node->_M_next = __next_node;
00361 __next_node->_M_prev = __prev_node;
00362 _Destroy(&__n->_M_data);
00363 _M_put_node(__n);
00364 return iterator((_Node*) __next_node);
00365 }
00366 iterator erase(iterator __first, iterator __last);
00367 void clear() { _Base::clear(); }
00368
00369 void resize(size_type __new_size, const _Tp& __x);
00370 void resize(size_type __new_size) { this->resize(__new_size, _Tp()); }
00371
00372 void pop_front() { erase(begin()); }
00373 void pop_back() {
00374 iterator __tmp = end();
00375 erase(--__tmp);
00376 }
00377 list(size_type __n, const _Tp& __value,
00378 const allocator_type& __a = allocator_type())
00379 : _Base(__a)
00380 { insert(begin(), __n, __value); }
00381 explicit list(size_type __n)
00382 : _Base(allocator_type())
00383 { insert(begin(), __n, _Tp()); }
00384
00385
00386
00387 template <class _InputIterator>
00388 list(_InputIterator __first, _InputIterator __last,
00389 const allocator_type& __a = allocator_type())
00390 : _Base(__a)
00391 { insert(begin(), __first, __last); }
00392
00393 list(const list<_Tp, _Alloc>& __x) : _Base(__x.get_allocator())
00394 { insert(begin(), __x.begin(), __x.end()); }
00395
00396 ~list() { }
00397
00398 list<_Tp, _Alloc>& operator=(const list<_Tp, _Alloc>& __x);
00399
00400 public:
00401
00402
00403
00404
00405
00406 void assign(size_type __n, const _Tp& __val) { _M_fill_assign(__n, __val); }
00407
00408 void _M_fill_assign(size_type __n, const _Tp& __val);
00409
00410 template <class _InputIterator>
00411 void assign(_InputIterator __first, _InputIterator __last) {
00412 typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
00413 _M_assign_dispatch(__first, __last, _Integral());
00414 }
00415
00416 template <class _Integer>
00417 void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
00418 { _M_fill_assign((size_type) __n, (_Tp) __val); }
00419
00420 template <class _InputIterator>
00421 void _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
00422 __false_type);
00423
00424 protected:
00425 void transfer(iterator __position, iterator __first, iterator __last) {
00426 if (__position != __last) {
00427
00428 __last._M_node->_M_prev->_M_next = __position._M_node;
00429 __first._M_node->_M_prev->_M_next = __last._M_node;
00430 __position._M_node->_M_prev->_M_next = __first._M_node;
00431
00432
00433 _List_node_base* __tmp = __position._M_node->_M_prev;
00434 __position._M_node->_M_prev = __last._M_node->_M_prev;
00435 __last._M_node->_M_prev = __first._M_node->_M_prev;
00436 __first._M_node->_M_prev = __tmp;
00437 }
00438 }
00439
00440 public:
00441 void splice(iterator __position, list& __x) {
00442 if (!__x.empty())
00443 this->transfer(__position, __x.begin(), __x.end());
00444 }
00445 void splice(iterator __position, list&, iterator __i) {
00446 iterator __j = __i;
00447 ++__j;
00448 if (__position == __i || __position == __j) return;
00449 this->transfer(__position, __i, __j);
00450 }
00451 void splice(iterator __position, list&, iterator __first, iterator __last) {
00452 if (__first != __last)
00453 this->transfer(__position, __first, __last);
00454 }
00455 void remove(const _Tp& __value);
00456 void unique();
00457 void merge(list& __x);
00458 void reverse();
00459 void sort();
00460
00461 template <class _Predicate> void remove_if(_Predicate);
00462 template <class _BinaryPredicate> void unique(_BinaryPredicate);
00463 template <class _StrictWeakOrdering> void merge(list&, _StrictWeakOrdering);
00464 template <class _StrictWeakOrdering> void sort(_StrictWeakOrdering);
00465 };
00466
00467 template <class _Tp, class _Alloc>
00468 inline bool
00469 operator==(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y)
00470 {
00471 typedef typename list<_Tp,_Alloc>::const_iterator const_iterator;
00472 const_iterator __end1 = __x.end();
00473 const_iterator __end2 = __y.end();
00474
00475 const_iterator __i1 = __x.begin();
00476 const_iterator __i2 = __y.begin();
00477 while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2) {
00478 ++__i1;
00479 ++__i2;
00480 }
00481 return __i1 == __end1 && __i2 == __end2;
00482 }
00483
00484 template <class _Tp, class _Alloc>
00485 inline bool operator<(const list<_Tp,_Alloc>& __x,
00486 const list<_Tp,_Alloc>& __y)
00487 {
00488 return lexicographical_compare(__x.begin(), __x.end(),
00489 __y.begin(), __y.end());
00490 }
00491
00492 template <class _Tp, class _Alloc>
00493 inline bool operator!=(const list<_Tp,_Alloc>& __x,
00494 const list<_Tp,_Alloc>& __y) {
00495 return !(__x == __y);
00496 }
00497
00498 template <class _Tp, class _Alloc>
00499 inline bool operator>(const list<_Tp,_Alloc>& __x,
00500 const list<_Tp,_Alloc>& __y) {
00501 return __y < __x;
00502 }
00503
00504 template <class _Tp, class _Alloc>
00505 inline bool operator<=(const list<_Tp,_Alloc>& __x,
00506 const list<_Tp,_Alloc>& __y) {
00507 return !(__y < __x);
00508 }
00509
00510 template <class _Tp, class _Alloc>
00511 inline bool operator>=(const list<_Tp,_Alloc>& __x,
00512 const list<_Tp,_Alloc>& __y) {
00513 return !(__x < __y);
00514 }
00515
00516 template <class _Tp, class _Alloc>
00517 inline void
00518 swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y)
00519 {
00520 __x.swap(__y);
00521 }
00522
00523 template <class _Tp, class _Alloc> template <class _InputIter>
00524 void
00525 list<_Tp, _Alloc>::_M_insert_dispatch(iterator __position,
00526 _InputIter __first, _InputIter __last,
00527 __false_type)
00528 {
00529 for ( ; __first != __last; ++__first)
00530 insert(__position, *__first);
00531 }
00532
00533 template <class _Tp, class _Alloc>
00534 void
00535 list<_Tp, _Alloc>::_M_fill_insert(iterator __position,
00536 size_type __n, const _Tp& __x)
00537 {
00538 for ( ; __n > 0; --__n)
00539 insert(__position, __x);
00540 }
00541
00542 template <class _Tp, class _Alloc>
00543 typename list<_Tp,_Alloc>::iterator list<_Tp, _Alloc>::erase(iterator __first,
00544 iterator __last)
00545 {
00546 while (__first != __last)
00547 erase(__first++);
00548 return __last;
00549 }
00550
00551 template <class _Tp, class _Alloc>
00552 void list<_Tp, _Alloc>::resize(size_type __new_size, const _Tp& __x)
00553 {
00554 iterator __i = begin();
00555 size_type __len = 0;
00556 for ( ; __i != end() && __len < __new_size; ++__i, ++__len)
00557 ;
00558 if (__len == __new_size)
00559 erase(__i, end());
00560 else
00561 insert(end(), __new_size - __len, __x);
00562 }
00563
00564 template <class _Tp, class _Alloc>
00565 list<_Tp, _Alloc>& list<_Tp, _Alloc>::operator=(const list<_Tp, _Alloc>& __x)
00566 {
00567 if (this != &__x) {
00568 iterator __first1 = begin();
00569 iterator __last1 = end();
00570 const_iterator __first2 = __x.begin();
00571 const_iterator __last2 = __x.end();
00572 while (__first1 != __last1 && __first2 != __last2)
00573 *__first1++ = *__first2++;
00574 if (__first2 == __last2)
00575 erase(__first1, __last1);
00576 else
00577 insert(__last1, __first2, __last2);
00578 }
00579 return *this;
00580 }
00581
00582 template <class _Tp, class _Alloc>
00583 void list<_Tp, _Alloc>::_M_fill_assign(size_type __n, const _Tp& __val) {
00584 iterator __i = begin();
00585 for ( ; __i != end() && __n > 0; ++__i, --__n)
00586 *__i = __val;
00587 if (__n > 0)
00588 insert(end(), __n, __val);
00589 else
00590 erase(__i, end());
00591 }
00592
00593 template <class _Tp, class _Alloc> template <class _InputIter>
00594 void
00595 list<_Tp, _Alloc>::_M_assign_dispatch(_InputIter __first2, _InputIter __last2,
00596 __false_type)
00597 {
00598 iterator __first1 = begin();
00599 iterator __last1 = end();
00600 for ( ; __first1 != __last1 && __first2 != __last2; ++__first1, ++__first2)
00601 *__first1 = *__first2;
00602 if (__first2 == __last2)
00603 erase(__first1, __last1);
00604 else
00605 insert(__last1, __first2, __last2);
00606 }
00607
00608 template <class _Tp, class _Alloc>
00609 void list<_Tp, _Alloc>::remove(const _Tp& __value)
00610 {
00611 iterator __first = begin();
00612 iterator __last = end();
00613 while (__first != __last) {
00614 iterator __next = __first;
00615 ++__next;
00616 if (*__first == __value) erase(__first);
00617 __first = __next;
00618 }
00619 }
00620
00621 template <class _Tp, class _Alloc>
00622 void list<_Tp, _Alloc>::unique()
00623 {
00624 iterator __first = begin();
00625 iterator __last = end();
00626 if (__first == __last) return;
00627 iterator __next = __first;
00628 while (++__next != __last) {
00629 if (*__first == *__next)
00630 erase(__next);
00631 else
00632 __first = __next;
00633 __next = __first;
00634 }
00635 }
00636
00637 template <class _Tp, class _Alloc>
00638 void list<_Tp, _Alloc>::merge(list<_Tp, _Alloc>& __x)
00639 {
00640 iterator __first1 = begin();
00641 iterator __last1 = end();
00642 iterator __first2 = __x.begin();
00643 iterator __last2 = __x.end();
00644 while (__first1 != __last1 && __first2 != __last2)
00645 if (*__first2 < *__first1) {
00646 iterator __next = __first2;
00647 transfer(__first1, __first2, ++__next);
00648 __first2 = __next;
00649 }
00650 else
00651 ++__first1;
00652 if (__first2 != __last2) transfer(__last1, __first2, __last2);
00653 }
00654
00655 inline void __List_base_reverse(_List_node_base* __p)
00656 {
00657 _List_node_base* __tmp = __p;
00658 do {
00659 std::swap(__tmp->_M_next, __tmp->_M_prev);
00660 __tmp = __tmp->_M_prev;
00661 } while (__tmp != __p);
00662 }
00663
00664 template <class _Tp, class _Alloc>
00665 inline void list<_Tp, _Alloc>::reverse()
00666 {
00667 __List_base_reverse(this->_M_node);
00668 }
00669
00670 template <class _Tp, class _Alloc>
00671 void list<_Tp, _Alloc>::sort()
00672 {
00673
00674 if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node) {
00675 list<_Tp, _Alloc> __carry;
00676 list<_Tp, _Alloc> __counter[64];
00677 int __fill = 0;
00678 while (!empty()) {
00679 __carry.splice(__carry.begin(), *this, begin());
00680 int __i = 0;
00681 while(__i < __fill && !__counter[__i].empty()) {
00682 __counter[__i].merge(__carry);
00683 __carry.swap(__counter[__i++]);
00684 }
00685 __carry.swap(__counter[__i]);
00686 if (__i == __fill) ++__fill;
00687 }
00688
00689 for (int __i = 1; __i < __fill; ++__i)
00690 __counter[__i].merge(__counter[__i-1]);
00691 swap(__counter[__fill-1]);
00692 }
00693 }
00694
00695 template <class _Tp, class _Alloc> template <class _Predicate>
00696 void list<_Tp, _Alloc>::remove_if(_Predicate __pred)
00697 {
00698 iterator __first = begin();
00699 iterator __last = end();
00700 while (__first != __last) {
00701 iterator __next = __first;
00702 ++__next;
00703 if (__pred(*__first)) erase(__first);
00704 __first = __next;
00705 }
00706 }
00707
00708 template <class _Tp, class _Alloc> template <class _BinaryPredicate>
00709 void list<_Tp, _Alloc>::unique(_BinaryPredicate __binary_pred)
00710 {
00711 iterator __first = begin();
00712 iterator __last = end();
00713 if (__first == __last) return;
00714 iterator __next = __first;
00715 while (++__next != __last) {
00716 if (__binary_pred(*__first, *__next))
00717 erase(__next);
00718 else
00719 __first = __next;
00720 __next = __first;
00721 }
00722 }
00723
00724 template <class _Tp, class _Alloc> template <class _StrictWeakOrdering>
00725 void list<_Tp, _Alloc>::merge(list<_Tp, _Alloc>& __x,
00726 _StrictWeakOrdering __comp)
00727 {
00728 iterator __first1 = begin();
00729 iterator __last1 = end();
00730 iterator __first2 = __x.begin();
00731 iterator __last2 = __x.end();
00732 while (__first1 != __last1 && __first2 != __last2)
00733 if (__comp(*__first2, *__first1)) {
00734 iterator __next = __first2;
00735 transfer(__first1, __first2, ++__next);
00736 __first2 = __next;
00737 }
00738 else
00739 ++__first1;
00740 if (__first2 != __last2) transfer(__last1, __first2, __last2);
00741 }
00742
00743 template <class _Tp, class _Alloc> template <class _StrictWeakOrdering>
00744 void list<_Tp, _Alloc>::sort(_StrictWeakOrdering __comp)
00745 {
00746
00747 if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node) {
00748 list<_Tp, _Alloc> __carry;
00749 list<_Tp, _Alloc> __counter[64];
00750 int __fill = 0;
00751 while (!empty()) {
00752 __carry.splice(__carry.begin(), *this, begin());
00753 int __i = 0;
00754 while(__i < __fill && !__counter[__i].empty()) {
00755 __counter[__i].merge(__carry, __comp);
00756 __carry.swap(__counter[__i++]);
00757 }
00758 __carry.swap(__counter[__i]);
00759 if (__i == __fill) ++__fill;
00760 }
00761
00762 for (int __i = 1; __i < __fill; ++__i)
00763 __counter[__i].merge(__counter[__i-1], __comp);
00764 swap(__counter[__fill-1]);
00765 }
00766 }
00767
00768 }
00769
00770 #endif
00771
00772
00773
00774