本文主要分析gcc4.8版本的stl list的源码实现，与vector的线性空间结构不同，list的节点是任意分散的，节点之间通过指针连接，好处是在任何位置插入删除元素都只需要常数时间，缺点是不能随机访问，查询复杂度是O（n），n为list中的元素个数。所以list非常适合应用与数据插入删除频繁的场景。
一、 list节点
list节点定义如下，
struct _List_node_base { _List_node_base* _M_next; _List_node_base* _M_prev; ｝ template<typename _Tp> struct _List_node : public __detail::_List_node_base { _Tp _M_data; ｝
很明显list是一个双向链表，_M_next和_M_prev分别指向下一个和上一个节点，_M_data是节点存储的数据。
二、 list的迭代器
由于list不是线性空间结构，通用迭代器无法正常移动，所以list需要定义专门的迭代器。
template<typename _Tp> struct _List_iterator { typedef _List_iterator<_Tp> _Self; typedef _List_node<_Tp> _Node; typedef ptrdiff_t difference_type; typedef std::bidirectional_iterator_tag iterator_category; typedef _Tp value_type; typedef _Tp* pointer; typedef _Tp& reference; _List_iterator() : _M_node() { } explicit _List_iterator(__detail::_List_node_base* __x) : _M_node(__x) { } // Must downcast from _List_node_base to _List_node to get to _M_data. reference operator*() const { return static_cast<_Node*>(_M_node)->_M_data; } pointer operator->() const { return std::__addressof(static_cast<_Node*>(_M_node)->_M_data); } _Self& operator++() { _M_node = _M_node->_M_next; return *this; } _Self operator++(int) { _Self __tmp = *this; _M_node = _M_node->_M_next; return __tmp; } _Self& operator--() { _M_node = _M_node->_M_prev; return *this; } _Self operator--(int) { _Self __tmp = *this; _M_node = _M_node->_M_prev; return __tmp; } // 指向list节点指针 __detail::_List_node_base* _M_node; };
list迭代器指向list的node，所以解引用时必须返回 static_cast<_Node*>(_M_node)->_M_data。list迭代器不是随机访问迭代器，必须通过节点的next和prev指针一步步移动，元素访问复杂度是线性的。另外还定义了只读迭代器_List_const_iterator。
三、 list的定义
和vector一样，list继承于_List_base，内存分配释放工作由_List_base负责，
template<typename _Tp, typename _Alloc> class _List_base { protected: //使用traits方法，得到_List_node<_Tp>的内存分配器 typedef typename _Alloc::template rebind<_List_node<_Tp> >::other _Node_alloc_type; typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type; struct _List_impl : public _Node_alloc_type { //数据成员就只有一个头节点 __detail::_List_node_base _M_node; _List_impl() : _Node_alloc_type(), _M_node() { } _List_impl(const _Node_alloc_type& __a) : _Node_alloc_type(__a), _M_node() { } }; _List_impl _M_impl; //分配节点的接口 _List_node<_Tp>* _M_get_node() { return _M_impl._Node_alloc_type::allocate(1); } _List_base() : _M_impl() { _M_init(); } //list初始为空，头节点的next和prev都指向自身 void _M_init() { this->_M_impl._M_node._M_next = &this->_M_impl._M_node; this->_M_impl._M_node._M_prev = &this->_M_impl._M_node; } //从第一个数据节点开始依次删除并释放内存。 template<typename _Tp, typename _Alloc> void _List_base<_Tp, _Alloc>:: _M_clear() { typedef _List_node<_Tp> _Node; _Node* __cur = static_cast<_Node*>(_M_impl._M_node._M_next); while (__cur != &_M_impl._M_node) { _Node* __tmp = __cur; __cur = static_cast<_Node*>(__cur->_M_next); _M_get_Node_allocator().destroy(__tmp); _M_put_node(__tmp); } }
list继承了_List_base的头节点，
template<typename _Tp, typename _Alloc = std::allocator<_Tp> > class list : protected _List_base<_Tp, _Alloc> { // concept requirements typedef typename _Alloc::value_type _Alloc_value_type; __glibcxx_class_requires(_Tp, _SGIAssignableConcept) __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept) typedef _List_base<_Tp, _Alloc> _Base; typedef typename _Base::_Tp_alloc_type _Tp_alloc_type; typedef typename _Base::_Node_alloc_type _Node_alloc_type; public: typedef _Tp value_type; typedef typename _Tp_alloc_type::pointer pointer; typedef typename _Tp_alloc_type::const_pointer const_pointer; typedef typename _Tp_alloc_type::reference reference; typedef typename _Tp_alloc_type::const_reference const_reference; typedef _List_iterator<_Tp> iterator; typedef _List_const_iterator<_Tp> const_iterator; typedef std::reverse_iterator<const_iterator> const_reverse_iterator; typedef std::reverse_iterator<iterator> reverse_iterator; typedef size_t size_type; typedef ptrdiff_t difference_type; typedef _Alloc allocator_type; ......
四、 list构造方式
list提供了多种构造函数，
//默认构造函数 list() : _Base() { } //初始化为n个默认值 explicit list(size_type __n) : _Base() { _M_default_initialize(__n); } //初始化为n个__value值 list(size_type __n, const value_type& __value, const allocator_type& __a = allocator_type()) : _Base(_Node_alloc_type(__a)) { _M_fill_initialize(__n, __value); } //拷贝构造函数 list(const list& __x) : _Base(__x._M_get_Node_allocator()) { _M_initialize_dispatch(__x.begin(), __x.end(), __false_type()); } //移动构造函数 list(list&& __x) noexcept : _Base(std::move(__x)) { }
五、 list元素操作
篇幅有限，只讨论部分函数。
iterator begin() _GLIBCXX_NOEXCEPT { return iterator(this->_M_impl._M_node._M_next); } iterator end() _GLIBCXX_NOEXCEPT { return iterator(&this->_M_impl._M_node); } end指向头节点，begin指向第一个数据节点，begin和end仍然组成一个前闭后开区间。 Bool empty() const _GLIBCXX_NOEXCEPT { return this->_M_impl._M_node._M_next == &this->_M_impl._M_node; } 通过查看头节点是否指向自身来判断list是否为空。 void push_front(const value_type& __x) { this->_M_insert(begin(), __x); } void push_back(const value_type& __x) { this->_M_insert(end(), __x); } template<typename... _Args> void _M_insert(iterator __position, _Args&&... __args) { _Node* __tmp = _M_create_node(std::forward<_Args>(__args)...); __tmp->_M_hook(__position._M_node); } template<typename _Tp, typename _Alloc> typename list<_Tp, _Alloc>::iterator list<_Tp, _Alloc>:: insert(iterator __position, const value_type& __x) { _Node* __tmp = _M_create_node(__x); __tmp->_M_hook(__position._M_node); return iterator(__tmp); }
push_front，push_back和insert的时间复杂度都是O(1).
template<typename _Tp, typename _Alloc> void list<_Tp, _Alloc>::merge(list&& __x) { if (this != &__x) { _M_check_equal_allocators(__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; _M_transfer(__first1, __first2, ++__next); __first2 = __next; } else ++__first1; if (__first2 != __last2) _M_transfer(__last1, __first2, __last2); } }