gcc 版本4.4.0
这次我们看看STL中list是怎样设计的。首先这个list要分为两个部分，list结构和list节点的结构。
首先看看list的节点(_List_node) 。
list 节点
由于 _List_node 是继承 _List_node_base。所以先来看看_List_node_base
struct _List_node : public _List_node_base
_List_node_base 中只有两个数据成员: 一个向前的指针，一个向后的指针。从这里可以看出list是一个双向链表
struct _List_node_base
{
_List_node_base* _M_next;
_List_node_base* _M_prev;
...
};
_List_node 中只有一个数据成员: data
template<typename _Tp>
struct _List_node : public _List_node_base
{
_Tp _M_data;
};
链表节点总结如图:
list iterator
在看迭代器之前，我们想想为什么list节点分为了两个部分，而不是在一个结构体里面呢?
也就是说为什么指针变量和数据变量分开定义？
这里是为了给迭代器做铺垫，因为迭代器遍历的时候不需要数据成员的，只需要前后指针就可以遍历该list。
来看看迭代器是怎样写的
template<typename _Tp>
struct _List_iterator
{
...
_List_node_base* _M_node;
};
_M_node 这个变量的类型是上面定义的 list 节点中的指针变量。
这里选出两个成员函数看看，如果想看全部源码可自行下载。
文件路径gcc-4.4.0/libstdc++ -v3/include/bits/stl_list.h
typedef _List_iterator<_Tp> _Self;
//前置 ++
_Self& operator++(){
_M_node = _M_node->_M_next;
return *this;
}
//后置 ++
_Self operator++(int) {
_Self __tmp = *this;
_M_node = _M_node->_M_next;
return __tmp;
}
List 链表结构
从源码里看List是继承 _List_base，而_List_base中有成员变量 _M_node，这个变量是_List_impl 类型的。_List_impl的成员变量是 _M_node, _M_node是_List_node_base 类型的
template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
class list : protected _List_base<_Tp, _Alloc>
_List_impl _M_impl;
struct _List_impl
: public _Node_alloc_type
{
_List_node_base _M_node;
...
};
为了方便理解，这里画了个类图。而至于 _List_node_base 上面都已经提及，这里就不在赘述。
以上介绍了list和list节点的数据结构。
如果让 _M_node指向尾端的一个空白节点，_M_node就能够符合STL前闭后开区间的要求。
多个节点的List结构如图:
list成员函数(节选)
insert
在迭代器position所在的位置插入一个节点。
iterator insert(iterator position, const T& x) {
link_type tmp = create_node(x);
tmp->next = position.node;
tmp->prev = position.node->prev;
(link_type(position.node->prev))->next = tmp;
position.node->prev = tmp;
return tmp;
}
push_front && push_back
内部调用insert
void push_front(const T& x) { insert(begin(), x); }
void push_bakc(const T& x) { insert(end(), x); }
erase
移除迭代器position所指向的节点
iterator erase(iterator position ) {
//在双向链表中删除一个节点
}
pop_front && pop_back
内部调用 erase
void pop_front() { erase(begin()); }
void pop_back() { iterator tmp = end(); erase(--tmp); }