list（链表）

} }

list（链表）

list设计

每个元素都是放在一块内存中，他的内存空间可以是不连续的，通过指针来进行数据的访问

在哪里添加删除元素性能都很高，不需要移动内存，当然也不需要对每个元素都进行构造与析构了，所以常用来做随机插入和删除操作容器

list属于双向链表，其结点与list本身是分开设计的：

template<class T, class Alloc = alloc> class list {

protected:

typedef listnode <T> listnode;

public:

typedef listnode link_type;

typedef listiterator<T, T &, T> iterator;

protected:

link_type node;

};

学习到了一个分析方法，拿到这样一个类，先看它的数据比如上面的linktype node，然后我们再看它的前缀， linktype，去上面在linktype,找到typedef listnode linktype;按这个方法继续找到上面的typedef listnode listnode;

我们发现list_node是下面的类，我们一层层的寻找，就能看懂这些源码

template<class T> struct _listnode {

typedef void voidpointer;

void_pointer prev;

void_pointer next;

T data;

};

list是一个环状的双向链表，同时它也满足STL对于“前闭后开”的原则，即在链表尾端可以加上空白节点

list的迭代器的设计：

迭代器是泛化的指针所以里面重载了->，--，++，*（），等运算符，同时迭代器是算法与容器之间的桥梁，算法需要了解容器的方方面面，于是就诞生了5种关联类型，(这5种类型是必备的，可能还需要其他类型)我们知道算法传

入的是迭代器或者指针，算法根据传入的迭代器或指针推断出算法所想要了解的容器里的5种关联类型的相关信息。由于光传入指针，算法推断不出来其想要的信息，所以我们需要一个中间商（萃取器）也就是我们所说的

iterator traits类，对于一般的迭代器，它直接提供迭代器里的关联类型值，而对于指针和常量指针，它采用的类

// 针对一般的迭代器类型,直接取迭代器内定义的关联类型 template<class I>

struct iterator_traits { typedef typename I::iteratorcategory iteratorcategory;

typedef typename I::valuetype valuetype;

typedef typename I::differencetype differencetype;

typedef typename I::pointer pointer;

typedef typename I::reference reference;

};

•// 针对指针类型进行特化,指定关联类型的值 template<class T>

struct iteratortraits<T> { typedef randomaccessiteratortag iteratorcategory;

typedef T value_type;

typedef ptrdifft differencetype;

typedef T *pointer;

typedef T &reference;

};

// 针对指针常量类型进行特化,指定关联类型的值 template<class T>

struct iteratortraits<const T> { typedef randomaccessiteratortag iteratorcategory;

typedef T valuetype;// valuetye被用于创建变量,为灵活起见,取 T 而非 const T 作为 value_type

typedef ptrdifft differencetype;

typedef const T *pointer;

typedef const T &reference;

};