C++ list insert源码简析

Posted on | In

stl::list是一个双向链表，list本身和list节点是不同的结构，stl::lilst中的节点（node）结构如下：

Tips：以下代码摘自《STL源码剖析–侯捷》
1
2
3
4
5
6
7
template <class T>
struct __list_node {
    typedef void* void_pointer;
    void_pointer prev; // 型别为void*。其实可设为__list_node<T>*
    void_pointer next;
    T data;
}

list::insert() 是一个重载函数，其中最简单的一种如下。首先配置并构造一个节点，然后在尾端进行适当的指针操作，将新节点插入进去:

1
2
3
4
5
6
7
8
9
10
11
iterator insert(iterator position, const T& x)
{
    linke_type tmp = creat_node(x); // 产生一个节点（设内容为x） 
    
    // 调整双向指针，使tmp插入进去
    tmp->next = position.node;
    tmp->prev = position.node->prev; // 与当前节点的上一节点建立连接
    (link_type(position.node->prev))->next = tmp; // 将tmp插入到上一节点之后
    position.node->prev = tmp; // 被插入的位置往后移动
    return tmp;
}
1
typedef __list_node<T>* linke_type // from __list_iterator
1
2
3
4
5
6
// 产生（配置并构造）一个节点，
link_type create_node(const T& x)
{
    link_type p = get_node();
    construct(&p->data, x); // 全局函数， 构造/析构基本工具
}
1
2
3
4
5
// 配置一个节点并传回
link_type get_node()
{
    return list_node_allocator::allocate();
}

stl::push_back()调用insert()将元素插入于list尾端：

1
2
3
4
void push_back(const T& x)
{
    insert(end(), x);
}