STL源码笔记（10）—序列式容器之list_list m put node

STL源码笔记（10）—序列式容器之list

STL中的list容器本质上来说就是一个双向链表，可以高效的完成插入删除等，所以它的源码中与数据结构中的双向链表差不多，在STL源码中list是一个模板类，以封装一些操作。

list数据结构

我们知道链表的节点分为数据域和指针域，对于双向链表来说，其指针域包含额外的指向上一个节点的指针，在STL源码stl_list.h中，用了继承的方法来表示：

struct _List_node_base {
  _List_node_base* _M_next;
  _List_node_base* _M_prev;
};
template <class _Tp>
struct _List_node : public _List_node_base {
  _Tp _M_data;
};
template <class _Tp, class _Alloc>
class _List_base 
{
//...
protected:
  _List_node<_Tp>* _M_node;//双向链表维护的指针
//...
};
//在class list中，用typedef做了进一步修饰
template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
class list : protected _List_base<_Tp, _Alloc> {
//...
    typedef _List_node<_Tp> _Node;
//...
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

书中提到SGI list不仅是一个双向链表，还是一个环状的双向链表，为了保证STL容器前闭后开的一致性，这里可以在尾部插入一个空白节点，而list（事实上是在其父类定义的_List_node<_Tp>* _M_node;）维护的双向链表的“头指针”，就指向这个空白节点，由于在该双向链表是一个环，于是就有了：

template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
class list : protected _List_base<_Tp, _Alloc> {
public:
    iterator begin()             { return (_Node*)(_M_node->_M_next); }
    const_iterator begin() const { return (_Node*)(_M_node->_M_next); }

    //这里end()实际上返回的是空白节点，也就是最后一个节点的后一个位置，
    //就满足了前闭后开的原则
    iterator end()             { return _M_node; }
    const_iterator end() const { return _M_node; }
};
1
2
3
4
5
6
7
8
9
10
11

根据此可以容易获取链表的某些属性：

1