|
onst list<_Tp,_Alloc>& __y) { ///此处必须使用const_iterator,因const list所得到的迭代器均为const_iterator typedef typename list<_Tp,_Alloc>::const_iterator const_iterator; const_iterator __end1 = __x.end(); const_iterator __end2 = __y.end(); const_iterator __i1 = __x.begin(); const_iterator __i2 = __y.begin(); while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2) { ++__i1; ++__i2; } return __i1 == __end1 && __i2 == __end2; } template
inline bool operator<(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y) { return lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); } template
template
void list<_Tp, _Alloc>::_M_insert_dispatch(iterator __position, _InputIter __first, _InputIter __last, __false_type) { for ( ; __first != __last; ++__first) insert(__position, *__first); } template
void list<_Tp, _Alloc>::_M_fill_insert(iterator __position, size_type __n, const _Tp& __x) { for ( ; __n > 0; --__n) insert(__position, __x); } template
typename list<_Tp,_Alloc>::iterator list<_Tp, _Alloc>::erase(iterator __first, iterator __last) { while (__first != __last) erase(__first++); return __last; } template
void list<_Tp, _Alloc>::resize(size_type __new_size, const _Tp& __x) { iterator __i = begin(); size_type __len = 0; for ( ; __i != end() && __len < __new_size; ++__i, ++__len); if (__len == __new_size) ///__new_size <= this->size() erase(__i, end()); else /// __new_size > this->size() insert(end(), __new_size - __len, __x); } template
list<_Tp, _Alloc>& list<_Tp, _Alloc>::operator=(const list<_Tp, _Alloc>& __x) { if (this != &__x) { iterator __first1 = begin(); iterator __last1 = end(); const_iterator __first2 = __x.begin(); const_iterator __last2 = __x.end(); ///先挨个赋值 while (__first1 != __last1 && __first2 != __last2) *__first1++ = *__first2++; if (__first2 == __last2) ///x.size() <= this->size() erase(__first1, __last1); else ///x.size() > this->size() insert(__last1, __first2, __last2); } return *this; } template
void list<_Tp, _Alloc>::_M_fill_assign(size_type __n, const _Tp& __val) { iterator __i = begin(); for ( ; __i != end() && __n > 0; ++__i, --__n) *__i = __val; if (__n > 0) insert(end(), __n, __val); else erase(__i, end()); } template
template
void list<_Tp, _Alloc>::_M_assign_dispatch(_InputIter __first2, _InputIter __last2, __false_type) { iterator __first1 = begin(); iterator __last1 = end(); for ( ; __first1 != __last1 && __first2 != __last2; ++__first1, ++__first2) *__first1 = *__first2; if (__first2 == __last2) erase(__first1, __last1); else insert(__last1, __first2, __last2); } template
void list<_Tp, _Alloc>::remove(const _Tp& __value) { iterator __first = begin(); iterator __last = end(); while (__first != __last) { iterator __next = __first; ++__next; if (*__first == __value) erase(__first); __first = __next; } } template
void list<_Tp, _Alloc>::unique() { iterator __first = begin(); iterator __last = end(); if (__first == __last) return; iterator __next = __first; while (++__next != __last) { if (*__first == *__next) erase(__next); else __first = __next; __next = __first; } } ///将两个非递增排序的链表合并为一个非递增排序的链表 ///合并后x链表为空 template
void list<_Tp, _Alloc>::merge(list<_Tp, _Alloc>& __x) { iterator __first1 = begin(); iterator __last1 = end(); iterator __first2 = __x.begin(); iterator __last2 = __x.end(); while (__first1 != __last1 && __first2 != __last2) if (*__first2 < *__first1) { iterator __next = __first2; transfer(__first1, __first2, ++__next); __first2 = __next; } else ++__first1; if (__first2 != __last2) transfer(__last1, __first2, __last2); } ///从指针p开始,将list翻转 inline void __List_base_reverse(_List_node_base* __p) { _List_node_base* __tmp = __p; do { __STD::swap(__tmp->_M_next, __tmp->_M_prev); __tmp = __tmp->_M_prev; /// Old next node is now prev. } while (__tmp != __p); ///由于是循环链表,故指针再次指向p时,说明list翻转完毕 } template
inline void list<_Tp, _Alloc>::reverse() { __List_base_reverse(this->_M_node); } ///由于STL sort算法要求必须为随机迭代器,因此list实现了自己的专用sort算法 ///该算法采用的是归并排序的思想 template
void list<_Tp, _Alloc>::sort() { /// Do nothing if the list has length 0 or 1. if (_M_node->_M_next != _M_node && _M_node->_M_next-> |