stl list原理和用法

List的节点

template <class T>
struct __list_node
{
typedef void* void_pointer; 
void_pointer next; //型别为void*，也可以设为__list_node<t>*
void_pointer prev;
T data;
};

List的迭代器

在Vector中如果进行插入和删除操作后迭代器会失效，List有一个重要的性质就是插入和接合操作都不会造成原有的List迭代器失效。而且，再删除一个节点时，也仅有指向被删除元素的那个迭代器失效，其他迭代器不受任何影响。下面来看看List迭代器的源码。

template<class T, class Ref, class Ptr>
struct __list_iterator
{
    ....
    typedef bidirectional_iterator_tag iterator_category; //List的迭代器类型为双向迭代器
    typedef __list_node<t>* link_type; 

    // 这个是迭代器实际管理的资源指针
    link_type node;

    // 迭代器构造函数
    __list_iterator(link_type x) : node(x) {}
    __list_iterator() {}
    __list_iterator(const iterator& x) : node(x.node) {}

    // 重载operator *, 返回实际维护的数据
    reference operator*() const { return (*node).data; }
    // 成员调用操作符
    pointer operator->() const { return &(operator*()); }

    // 前缀自加
    self& operator++()
    {
        node = (link_type)((*node).next);
        return *this;
    }

    // 后缀自加, 需要先产生自身的一个副本, 然会再对自身操作, 最后返回副本
    self operator++(int)
    {
        self tmp = *this;
        ++*this;
        return tmp;
    }

List的迭代器实现了==,!=,++,–,取值和成员调用等操作，由于是存放在不连续的内存空间，所以并不支持vector那样的p+n的操作。

List的数据结构

List的数据结构个List的节点数据结构是分开定义的，SGI的List不仅是一个双向链表，而且还是一个环状双向链表，所以它只需要一个指针，就能完整表现一个链表。

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;
....
}

iterator begin() { return (link_type)((*node).next);}
iterator end() { return node};

list构造时首先申请一个list_node节点，作为尾端的空白节点。list中node的值就是该list_node的地址。

List的操作和用法

构造函数

   list<int> c0; //空链表

　　list<int> c1(3); //建一个含三个默认值是0的元素的链表

　　list<int> c2(5,2); //建一个含五个元素的链表，值都是2

　　list<int> c4(c2); //建一个c2的copy链表

　　list<int> c5(c1.begin(),c1.end()); c5含c1一个区域的元素[_First, _Last)

大小、判断函数

    int size() const:返回容器元素个数

    bool empty() const:判断容器是否为空，若为空则返回true

增加、删除函数

    void push_back(const T& x):list元素尾部增加一个元素x

    void push_front(const T& x):list元素首元素钱添加一个元素X

    void pop_back():删除容器尾元素，当且仅当容器不为空

    void pop_front():删除容器首元素，当且仅当容器不为空

    void remove(const T& x):删除容器中所有元素值等于x的元素

    void clear():删除容器中的所有元素

    iterator insert(iterator it, const T& x ):在迭代器指针it前插入元素x,返回x迭代器指针

    void insert(iterator it,size_type n,const T& x):迭代器指针it前插入n个相同元素x

    void insert(iterator it,const_iterator first,const_iterator last):把[first,last)间的元素插入迭代器指针it前

    iterator erase(iterator it):删除迭代器指针it对应的元素,返回的是it下一个节点的迭代器

    iterator erase(iterator first,iterator last):删除迭代器指针[first,last)间的元素，返回last

遍历函数

iterator begin():返回首元素的迭代器指针

iterator end():返回尾元素之后位置的迭代器指针

reverse_iterator rbegin():返回尾元素的逆向迭代器指针，用于逆向遍历容器

reverse_iterator rend():返回首元素前一个位置的迭代器指针

reference front():返回首元素的引用

reference back():返回尾元素的