list

概述

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

节点

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

template <class T> struct list node {
typedef void* void_pointer;
void_pointer prev； //型别为void*。其实可设为_ —list_node<T>* 	void_pointer next;
T data；

显然这是一个双向链表、

数据结构

list不仅是一个双向链表，而且还是一个环状双向链表。所以它只需要一个指针，便可以完整表现整个链表.

当我们以pUsh_back()将新元素插人于list尾端时，此函数内部调用insert():

void push_back(const T& x) { insert(end(), x); }

list的迭代器

list不再能够像vector —样以普通指针作为迭代器，因为其节点不保证在 储存空间中连续存在。list迭代器必须有能力指向list的节点，并有能力进行正确的递增、递减、取值、成员存取等操作。所谓“list迭代器正确的递增、递 减、取值、成员取用”操作是指，递增时指向下一个节点，递减时指向上一个节点， 取值时取的是节点的数据值，成员取用时取用的是节点的成员.

由于STLlist是一个双向链表（doublelinked-list)，迭代器必须具备前移、后移的能力，所以list提供的是Bidirectional Iterators。

list有一个重要性质：插入操作（insert)和接合操作（splice)都不会造成原有的list迭代器失效。

forward_list

forward_list是一个单向链表

forward_list和list的主要差别在于，前者的迭代器属于单向的ForwardIterator， 后者的迭代器属于双向的Bidirectionallterator。为此，forward_list的功能自然也就受到许多限制。不过，单向链表所耗用的空间更小，某些操作更快，不失为另一种选择。

forward_list和list共同具有的一个相同特色是，它们的插人（insert)、移除(erase)、接合（splice)等操作并不会造成原有的迭代器失效（当然啦，指向被移除元素的那个迭代器，在移除操作发生之后肯定是会失效的）。

注意，根据STL的习惯，插入操作会将新元素插入于指定位置之前，而非之后。然而作为一个单向链表，forward_list没有任何方便的办法可以回头定出前一个位置，因此它必须从头找起。

换句话说，除了 forward_list起点处附近的区域之外，在其它位置上采用 insert 或 erase 操作函数，都属不智之举。这便是forward_list相较于list之下的大缺点。为此，forward_list特别提供了 insert_after() 和 erase_after()供灵活运用。

基于同样的(效率)考虑，forward_list不提供push_back() ，只提供 push_front().