c++ 工程基础之STL系列 （二） list

list内部数据结构是一个双向循环链表，这样的数据结构在插入和删除上的时间复杂度相对vector会更好些，但是其两个指针占用的内存会更大一些

list在实际工程中主要应用在大量的插入和删除操作的场景，例如缓存淘汰LRU算法就可以用list实现。

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

struct node
{
	int key;
	int value;
	bool operator < (const node& p)
	{
		return key > p.key;
	}
};

bool comp(const node& p)
{
	return p.key == 1 ;
}

bool comp_sort(const node& p1, const node& p2)
{
	return p1.key < p2.key ;
}

int main()
{
	list<int> a;
	//前后插入
	cout<<"a.size="<<a.size()<<' '<<"a.empty="<<a.empty()<<endl;
	a.push_front(0);
	a.push_back(1);
	a.push_front(2);
	cout<<"a.front="<<a.front()<<' '<<"a.back="<<a.back()<<endl;
	//翻转	
	a.reverse();	
	cout<<"reverse="<<"a.front="<<a.front()<<' '<<"a.back="<<a.back()<<endl;
	//前后删除
	a.pop_front();
	a.pop_back();
	cout<<"a.front="<<a.front()<<' '<<"a.back="<<a.back()<<endl;
	a.clear();
	cout<<"empty="<<a.empty()<<endl;
	//随机插入
	int i = 0;
	for(list<int>::iterator it = a.begin();;)
	{
		it = a.insert(it, i++);
		if(a.size()>=10)
			break;
	}	
	//随机删除
	for(list<int>::iterator it = a.begin(); it != a.end(); )
	{
		cout<<*it<<endl;
		it = a.erase(it);
	}
	cout<<"empty="<<a.empty()<<endl;
	//unique 只有在相邻的相同元素才能删除
	a.push_back(1);	
	a.push_back(2);	
	a.push_back(2);	
	a.unique();	
	cout<<"uniq_size="<<a.size()<<endl;	
	a.push_back(1);	
	a.unique();	
	cout<<"uniq_size="<<a.size()<<endl;
	//删除指定值的元素
	a.remove(1);
	cout<<a.size()<<endl;
	node t1 = {1,1};
	node t2 = {2,2};
	list<node> b;
	b.push_back(t1);
	b.push_back(t2);
	//排序，对于结构体和类需要重载小于号，或者是增加比较函数
	b.sort();
	cout<<b.front().key<<endl;
	b.sort(comp_sort);
	cout<<b.front().key<<endl;
	//按条件删除
	b.remove_if(comp);
	cout<<b.size()<<endl;
}