- 1 相关文件
- 2 链表节点结构
- 3 链表的内存分配
- 4 list接口
- 4.1 默认构造
- 4.2 从元素个数与值构造
- 4.3 从容器区间构造
- 4.4 复制构造
- 4.5 析构函数
- 4.6 resize
- 4.7 reverse
- 4.8 sort
1 相关文件
list list.h stl_list.h
2 链表节点结构
基类_List_node_base只有_M_prev, _M_prev，分别指向前置节点和后继节点，由此看出STL list是双向链表（首节点为空）
struct _List_node_base { _List_node_base* _M_next; _List_node_base* _M_prev; }
派生类_List_node还有_M_data，用于存放数据项
template <class _Tp> struct _List_node : public _List_node_base { _Tp _M_data; }
3 链表的内存分配
同vector, 申请内存的调用链如下。allocator见STL源码分析--内存分配器
_Alloc_type::allocate -> simple_alloc<_List_node<_Tp>, _Alloc>::allocate -> _Alloc::allocate (list中_Alloc缺省为__STL_DEFAULT_ALLOCATOR(_Tp)) -> allocator<_Tp>
4 list接口
4.1 默认构造
注意用户可为list实例自定义内存分配器，内存分配器类型通过模板参数传入，内存分配器实例通过函数参数传入。_M_get_node从内存分配器中申请一个链表节点
_List_node<_Tp>大小的内存。使用默认构造函数时，list中并没有任何元素，因此_M_get_node中只申请内存，但并不在其上构造_Tp对象，即该节点是空的哨兵节点。
explicit list(const allocator_type& __a = allocator_type()) : _Base(__a) {} _List_base(const allocator_type&) { _M_node = _M_get_node(); _M_node->_M_next = _M_node; _M_node->_M_prev = _M_node; }
4.2 从元素个数与值构造
实现：连续向list中插入__n个值为__value的元素
调用链如下。
list::list -> list::insert(批量版本，一次插入n条数据) -> list::_M_fill_insert -> list::insert(非批量，一次插入1条数据)
相关代码片段如下：
``` c++ // list::list list(size_type __n, const _Tp& __value, const allocator_type& __a = allocator_type()) : _Base(__a) { insert(begin(), __n, __value); } // list::insert(批量版本，一次插入n条数据) void insert(iterator __pos, size_type __n, const _Tp& __x) { _M_fill_insert(__pos, __n, __x); } // list::_M_fill_insert template <class _Tp, class _Alloc> void list<_Tp, _Alloc>::_M_fill_insert(iterator __position, size_type __n, const _Tp& __x) { for ( ; __n > 0; --__n) insert(__position, __x); } // list::insert(非批量，一次插入1条数据) iterator insert(iterator __position, const _Tp& __x) { _Node* __tmp = _M_create_node(__x); __tmp->_M_next = __position._M_node; __tmp->_M_prev = __position._M_node->_M_prev; __position._M_node->_M_prev->_M_next = __tmp; __position._M_node->_M_prev = __tmp; return __tmp; }
_M_create_node也会新建链表节点，其与_M_get_node的不同在于会在内存上构造值为__x的_Tp对象。
_Node* _M_create_node(const _Tp& __x) { _Node* __p = _M_get_node(); __STL_TRY { _Construct(&__p->_M_data, __x); } __STL_UNWIND(_M_put_node(__p)); return __p; }
4.3 从容器区间构造
遍历容器区间[__first, __last), 依次将元素插入list中
// We don't need any dispatching tricks here, because insert does all of // that anyway. template <class _InputIterator> list(_InputIterator __first, _InputIterator __last, const allocator_type& __a = allocator_type()) : _Base(__a) { insert(begin(), __first, __last); } template <class _Tp, class _Alloc> void list<_Tp, _Alloc>::insert(iterator __position, const_iterator __first, const_iterator __last) { for ( ; __first != __last; ++__first) insert(__position, *__first); }
4.4 复制构造
实现上同从容器区间构造类似，在此略过。
list(const list<_Tp, _Alloc>& __x) : _Base(__x.get_allocator()) { insert(begin(), __x.begin(), __x.end()); }
4.5 析构函数
实现上分两步：
- 对于每个除
_M_node的节点，依次遍历并对其中的_Tp执行析构，并释放节点内存。
- 对于头节点，直接释放节点内存。
_M_put_node调用_Alloc_type::deallocate释放内存。
~list() { } ~_List_base() { clear(); _M_put_node(_M_node); template <class _Tp, class _Alloc> void _List_base<_Tp,_Alloc>::clear() { _List_node<_Tp>* __cur = (_List_node<_Tp>*) _M_node->_M_next; while (__cur != _M_node) { _List_node<_Tp>* __tmp = __cur; __cur = (_List_node<_Tp>*) __cur->_M_next; _Destroy(&__tmp->_M_data); _M_put_node(__tmp); } _M_node->_M_next = _M_node; _M_node->_M_prev = _M_node; } void _M_put_node(_List_node<_Tp>* __p) { _Alloc_type::deallocate(__p, 1); }
4.6 resize
遍历一遍list, 得到链表长度，然后根据长度判断是否对链表进行增长或减短
- 如果是前者，调用insert在链表尾部插入
new_size - __len个值为__x的节点
- 如果是后者，调用erase在链表尾部删除
__len - new_size个节点 因为会遍历全部节点，最好不要执行list::resize,list.size同理
template <class _Tp, class _Alloc> 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) erase(__i, end()); else // __i == end() insert(end(), __new_size - __len, __x); }
4.7 reverse
从头节点_M_node开始逆序遍历链表，交换所有节点的prev和next指针
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); }
4.8 sort
sort代码如下所示。list排序时，链表中维护临时链表__carry和链表数组__counter[64], 和__fill状态。其中__counter用于暂存当前的排序结果，__fill表示当前已被使用的__counter数组中的链表数量。
注意：代码中调用merge方法时，会将两个list按照顺序合并成一个。假设有两个list a与b, 调用a.merge(b)之后，b中所有节点都被转移到a中，b为空链表，a中包含了所有的节点，并按照顺序排列。
template <class _Tp, class _Alloc> 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->_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); __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]); swap(__counter[__fill-1]); } }
举个例子可能更好理解一些：假设链表中有4个值，从前到后分别为v0, v1, v2, v3。__counter数组长度为4, 即__counter[0], __counter[1], __counter[2], __counter[3]
- 初始状态：
__fill= 0,__counter中所有链表为空
- 第一轮循环：加入
v0, 状态变成__counter[0] = {v0}, __fill = 1
- 第二轮循环：加入
v1, 变成__counter[0] = {}, __counter[1] = {v0, v1}, __fill = 2
- 第三轮：加入
v2, 变成__counter[0] = {v2}, __counter[1] = {v0, v1}, __fill = 2
- 第四轮：加入
v3, 变成__counter[0] = {}, __counter[1] = {}, __counter[2] = {v0, v1, v2, v3}, __fill = 3
- 最终得到一组
__counter[4]，从左到右merge所有__counter中的链表，最终得到排过序的{v0, v1, v2, v3}结果, 并通过swap将结果转移给list对象本身。
其实list中sort算法就是非递归版本的归并排序，时间复杂度为O(n logn)
