首页 > 代码库 > STL之序列式容器list与forward_list
STL之序列式容器list与forward_list
List (双向链表) 与 forwardlist (单向链表) 算是非常基础的数据结构了，这里只是简单介绍下其结构及应用。
以list为例：
其节点模板：
template <class T>struct _list_node { _list_node<T>* prev; _list_node<T>* next; T data;};
结构示意图
关于list的迭代器
由于list的节点并不一定在存储空间中连续存在，所以list不再能够像vector一样以普通指针作为迭代器。由于list是一个双向链表，迭代器应该具备前移，后移的能力，所以list提供的是Bidirectional iterators.(双向迭代器)
List有一个重要性质：插入操作（insert）和接合操作(splice)都不会造成原有的list迭代器的失效。这在vector是不成立的。（vector的插入操作可能会造成空间的重新分配，导致原有的迭代器全部失效）。甚至list的元素删除操作(erase)，也只有“指向被删除元素”的那个迭代器失效，其他迭代器不受任何影响。（迭代器结构，如图：）
SGI list不仅是一个双向链表，而且还是个环状双向链表。List模板如下：
template <class T, class Alloc = allocator<T> >class list {//…protected: link_type node; // _list_node<T>* node};
其构造如图所示：
测试代码如下：
#include <list>#include <iostream>#include <algorithm>using namespace std;int main(){ list<int, allocator<int>> mylist; cout << "size = " << mylist.size() << endl; // size = 0 mylist.push_back(1); mylist.push_back(4); mylist.push_back(3); mylist.push_back(9); mylist.push_back(9); cout << "size = " << mylist.size() << endl; // size = 5 list<int>::iterator iter; for (iter = mylist.begin(); iter != mylist.end(); iter++) { cout << *iter << " "; // 1 4 3 9 9 } cout << endl; iter = find(mylist.begin(), mylist.end(), 3); if (*iter == 3) { mylist.insert(iter, 99); } cout << "size = " << mylist.size() << endl; // size = 6 cout << *iter << endl; // 3 iter = find(mylist.begin(), mylist.end(), 1); if (*iter == 1) { cout << *(mylist.erase(iter)) << endl; // 4 } for (iter = mylist.begin(); iter != mylist.end(); iter++) { cout << *iter << " "; // 4 99 3 9 9 } cout << endl; return 0;}
forward_list（单向链表）与list(双向链表）的区别主要在于，前者的迭代器属于单向的forward iterator, 后者的迭代器属于双向的bidirectional iterator. 为此，forward_list的功能自然也就受到了很多限制。不过，单向链表所消耗的空间更小（没有指向前面节点的指针），某些操作更快，也不失为一种选择。这里就不详细介绍了，附2张结构示意图。
forward_list迭代器示意图：
存储构造如图所示：
STL之序列式容器list与forward_list