当前位置：首页 > article >正文

STL序列式容器之list

article 2024/11/18 19:12:49

相较于vector的连续性空间，list相对比较复杂；list内部使用了双向环形链表的方式对数据进行存储；list在增加元素时，采用了精准的方式分配一片空间对数据及附加指针等信息进行存储；

list节点定义如下

template<class T>
struct __list_node{
    __list_node<T>* pre;   // 此处采用了书中建议的写法；与实际定义略有差异
    __list_node<T>* next;
    T data;
};

因为list存储节点不是T，所以其迭代器不能使用T*，所以定义了其迭代器

template<class T, class Ref, class Ptr>
struct __list_iterator {
    // ...
    typedef __list_node<T> * link_type;
    // ...
    link_type node;
    // ...
};

__list_iterator迭代器的操作符*，->操作符比较明显为：node->data, &node->data;

对于操作符++，和--，分别对应于node=node->next,及node=node->pre;

list采用双向环形链表，list成员只包含一个节点node；

template <class T, class Alloc = alloc>
class list {
    protected:
        typedef __list_node<T> list_node;
    public :
        typedef list_node* link_type;
    protected:
        link_type node;
    ...
};

因为是环形结构，node本身即为list的end，node->next即为list的起始节点；

iterator begin() {return node->next;}
iterator end()   {return node;}
bool empty() const {return node->next == node;}
reference front() {return *begin();}
reference back() {return *(end()--);}

list的insert操作比较简明：

iterator insert(iterator position, const T&x) {
    link_type tmp = create_node(x);
    tmp->next = position.node;
    tmp->pre  = position.node->pre;
    position.node->pre->next = tmp;
    position.node->pre = tmp;
    return tmp;    

}

指针插入前后指向情况如下