_M_next != _M_node) { list<_Tp, _Alloc> __carry; list<_Tp, _Alloc> __counter[64]; int __fill = 0; while (!empty()) { __carry.splice(__carry.begin(), *this, begin()); ///__carry得到list第一个元素 int __i = 0; ///此循环将counter[__fill]之前所有非空链表合并为一个链表 while(__i < __fill && !__counter[__i].empty()) { __counter[__i].merge(__carry); ///此时__carry为空 __carry.swap(__counter[__i++]); ///此时__counter[i]为空,i变为i+1 } __carry.swap(__counter[__i]); ///至此处i之前的所有链表均被合并至__counter[i] if (__i == __fill) ++__fill; } for (int __i = 1; __i < __fill; ++__i) __counter[__i].merge(__counter[__i-1]); swap(__counter[__fill-1]); } } template
template
void list<_Tp, _Alloc>::remove_if(_Predicate __pred) { iterator __first = begin(); iterator __last = end(); while (__first != __last) { iterator __next = __first; ++__next; ///必须先得到下一个节点位置,再删除当前结点,否则将无法找到下一个结点 if (__pred(*__first)) erase(__first); __first = __next; } } template
template
void list<_Tp, _Alloc>::unique(_BinaryPredicate __binary_pred) { iterator __first = begin(); iterator __last = end(); if (__first == __last) return; iterator __next = __first; while (++__next != __last) { if (__binary_pred(*__first, *__next)) erase(__next); else __first = __next; __next = __first; } } template
template
void list<_Tp, _Alloc>::merge(list<_Tp, _Alloc>& __x, _StrictWeakOrdering __comp) { iterator __first1 = begin(); iterator __last1 = end(); iterator __first2 = __x.begin(); iterator __last2 = __x.end(); while (__first1 != __last1 && __first2 != __last2) if (__comp(*__first2, *__first1)) { iterator __next = __first2; transfer(__first1, __first2, ++__next); __first2 = __next; } else ++__first1; if (__first2 != __last2) transfer(__last1, __first2, __last2); } template
template
void list<_Tp, _Alloc>::sort(_StrictWeakOrdering __comp) { /// Do nothing if the list has length 0 or 1. if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node) { list<_Tp, _Alloc> __carry; list<_Tp, _Alloc> __counter[64]; int __fill = 0; while (!empty()) { __carry.splice(__carry.begin(), *this, begin()); int __i = 0; while(__i < __fill && !__counter[__i].empty()) { __counter[__i].merge(__carry, __comp); __carry.swap(__counter[__i++]); } __carry.swap(__counter[__i]); if (__i == __fill) ++__fill; } for (int __i = 1; __i < __fill; ++__i) __counter[__i].merge(__counter[__i-1], __comp); swap(__counter[__fill-1]); } }
|