浅谈list

目录：
1.list概述
2.list节点
3.list迭代器
4.list数据结构

list概述

相较于vector的连续线性空间，list就显得复杂的多，它的好处是每次插入或删除一个元素，就配置或释放一个元素的空间，因此，list对空间的运用有绝对的精准，一点也不浪费。而且对于任何位置的元素插入或删除，list永远只是常数时间。

list的节点

list本身和list的节点是不同的结构，需要分开设计。以下是list的节点（node）结构：

template <class T>
struct _list_node{
    typedef void* void_pointer;
    void_pointer prev;    //类型其实可以设置为_list_node<T>*
    void_pointer next;
    T data;
}

显然这是一个双向链表（其实还是一个环状双向链表）。

list的迭代器

list不再能像vector一样以普通的指针作为迭代器，因为它的节点不保证在存储空间中连续存在。list迭代器必须有能力指向下一个或上一个节点，并有能力进行正确的递增，递减，取值，成员存取等操作。

list有一个重要性质：插入操作（insert）和接合操作（splice）都不会造成原有的list迭代器失效。这在vector是不成立的，因为vector的插入操作可能导致记忆体重新配置，导致原有的迭代器全部失效。

list数据结构

template <class T,Alloc = alloc>	//缺省使用alloc为配置器
class list{
	protected:
		typedef _list_node<T> list_node;
	public:
		typedef list_node* link_type;
	protected:
		link_type node;		//只要一个指针，便可表示整个环状双向链表
}