STL之list

一. list介绍

1. 相对于vector是连续的线性空间，list是一个不连续的存储空间。每次在list中插入或删除一个元素，就配置一个或释放一个元素空间，因此list对于空间的使用有绝对的精准，一点都不会浪费的。

2. STL中list的结点结构，在STL中list是一个双向链表。list结点如下图所示

template<typename T>
struct _list_node{
    typedef void *void_pointer;
    void_pointer prev; //指向前面一个结点
    void_pointer next; //指向后面一个结点
    T data;  //数据
};

3. STL list是一个双向环状链表，list的类模板如下所示。结点结构和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; //只要一个指针就可以表示环状链表
	...
};

4. STL中所有的区间都是满足“前闭后开”区间，因此list的示意图如下所示。链表的尾端有一个空白结点表示的是end，这样就可以满足STL规范的“前闭后开”区间。

 

二. list相关操作

1. 插入结点：在结点3的位置上插入结点99，此时结点99是插入在结点3的前面。通过find找到值为3的结点的位置，然后在那个位置插入值为99的结点。

2. 删除结点：删除值为1的结点，通过find找到元素值为1的结点的位置，然后删除之。

三. list使用例子

#include<list>
#include<iostream>
#include<algorithm>
using namespace std;

int main(){
	//建立一个list
    list<int> ilist;
    cout<<"size = "<<ilist.size()<<endl; //size = 0 

    ilist.push_back(0);
	ilist.push_back(1);
	ilist.push_back(2);
    ilist.push_back(3);
	ilist.push_back(4);
	cout<<"size = "<<ilist.size()<<endl; //size = 5

	//迭代器
	list<int>::iterator it;
	for(it = ilist.begin(); it != ilist.end(); it++){
         cout<<*it<<" ";    // 0 1 2 3 4 5
    }
    cout<<endl;

    //查找插入值为99结点
    it = ilist.find(ilist.begin(), ilist.end(), 3);
	if(it != 0){
       ilist.insert(it, 99);
    }

    cout<<"size = "<<ilist.size()<<endl;   //size = 6
	cout<<*it<<endl;  //3,插入完成之后迭代器往后移动一位

	for(it = ilist.begin(); it != ilist.end(); it++){
         cout<<*it<<" ";    // 0 1 2 99 3 4 5
    }
    cout<<endl;

    //删除结点
	it = ilist.find(ilist.begin(), ilist.end(), 1);
	if(it != 0){
       ilist.erase(it);
    }
    for(it = ilist.begin(); it != ilist.end(); it++){
         cout<<*it<<" ";    // 0 2 99 3 4 5
    }
    cout<<endl;

    return 0;
}

四.list相关方法