什么是list

list是序列式容器中的一种，底层是一个带头结点的双向循环链表。

list的使用

头文件#include
常用接口介绍

构造函数接口

测试用例：

void test_constructor()

	//1.无参构造
	list<int>vv1;
	//2.n个相同元素的构造
	list<int>vv2(5, 1);
	//3.区间构造
	int arr[] =  1,2,3,4,5 ;
	list<int>vv3(arr,arr+3);
	//4.拷贝构造
	list<int>vv4(vv3);

list相关迭代器使用

测试用例：
通过迭代器实现元素访问：

void test_iterator()

	list<int>v1 1,2,3,4,5 ;
	auto it = v1.begin();
	while (it != v1.end())
	
		cout << *it << " ";
		++it;
	
	cout << endl;
	auto it1=v1.rbegin();
	while (it1!= v1.rend())
	
		cout << *it1 << " ";
		++it1;
	
	cout << endl;

容量相关的操作

测试用例：

void test_size()

	list<int>v1 1,2,3,4,5 ;
	if (v1.empty())
	
		cout << "v1 is empty" << endl;
	
	else
	
		cout << "v1 is not empty" << endl;
	
	cout << v1.size() << endl;
	v1.resize(10, 1);
	cout << v1.size();

测试链表的修改操作

template<class T>
void Print(list<T>& P)

	auto it = P.begin();
	while (it != P.end())
	
		cout << *it << " ";
		it++;
	
	cout << endl;

void test_modoify()

	//push_back()/popback()
	list<int>vv1;
	vv1.push_back(1);
	vv1.push_back(2);
	vv1.push_back(3);
	vv1.push_back(4);
	Print(vv1);
	vv1.pop_back();
	Print(vv1);
	//push_front()与pop_front()
	vv1.push_front(5);
	Print(vv1);
	vv1.pop_front();
	Print(vv1);
	//测试insert()1.插入单个元素
	auto it=vv1.insert(find(vv1.begin(), vv1.end(), 2), 5);
	//插入多个元素
	vv1.insert(it, 5, 1);
	Print(vv1);
	int arr[] =  9,8,7,6 ;
	//插入一段区间
	vv1.insert(vv1.begin(), arr, arr + 3);
	Print(vv1);
	//测试erase 删除某一位置元素
	vv1.erase(vv1.begin());
	//删除一段区间
	vv1.erase(vv1.begin(), vv1.end());
	//验证swap
	list<int>vv2 1,2,3,4,5 ;
	vv1.swap(vv2);
	cout << vv1.size() << endl;
	cout << vv2.size() << endl;
	//验证clear
	vv1.clear();
	if (vv1.empty())
	
		cout << "vv1 is empty" << endl;
	
	else
	
		cout << "vv1 is not empty" << endl;
	

链表的一些其他操作

void test_operation()

	list<int>vv1 1,2,3,4,5,5,2,4,1,3 ;
	vv1.remove(2);
	cout << "删除2元素后" << endl;
	Print(vv1);
	vv1.unique();
	cout << "未排序去重后" << endl;
	Print(vv1);
	vv1.sort();
	vv1.unique();
	cout << "排序去重后" << endl;
	Print(vv1);
	//传递函数参数去除偶数操作
	vv1.remove_if(is_ood);
	cout << "去除偶数时" << endl;
	Print(vv1);
	list<int>vv2 3,1,5 ;
	list<int>vv3 2,8,6 ;
	//vv2.merge(vv3);
	//cout << "未排序合并" << endl;
	//Print(vv2);
	vv2.sort();
	vv3.sort();
	vv2.merge(vv3);
	cout << "排序合并" << endl;
	Print(vv2);

list中的赋值运算符

void test_operator()

	list<int>vv1(5, 0);
	list<int>vv2(3, 0);
	cout << "before the =" << endl;
	cout << "size of vv1 is " << vv1.size() << endl;
	cout << "size of vv2 is " << vv2.size() << endl;
	vv1 = vv2;
	cout << "after the =" << endl;
	cout << "size of vv1 is " << vv1.size() << endl;
	cout << "size of vv2 is " << vv2.size() << endl;

list中的迭代器失效问题

1.当删除迭代器位置上的元素时，迭代器失效

解决方法：

void test_iteratoruseless()

	list<int>vv1 1,2,3,4,5 ;
	auto it = vv1.begin();
	//1.删除所引起的迭代器失效
	while (it != vv1.end())
	
		//解决方式1.后置++解决。后置++指先拷贝it的一个副本，然后对it执行++操作，然后返回it的副本。
		//vv1.erase(it++);
		//解决方式2：利用返回值来解决
		it=vv1.erase(it);
		
	
	cout << vv1.size() << endl;

2.swap所引起的迭代器失效

//迭代器失效的第二种情况
void test_iteratoruseless1()

	list<int>vv1 1,2,3,4,5 ;
	auto it = vv1.begin();
	list<int>vv2 2,3,4,5 ;
	vv1.swap(vv2);
	while (it != vv1.end())
	
		cout << *it << " ";
		++it;
	
	cout << endl;

vector与list区别（重点）

1.在底层。vector底层是通过数组，也就是一块连续的空间实现的，list底层是一个带头结点的双向循环链表。
2.元素的随机访问。 vector支持元素的随机访问，时间复杂度为O（1），list不支持随机访问，访问某个元素的时间复杂度O(n);
3.插入与删除。 vector任意位置元素的插入与删除效率低，因为涉及到搬移元素,插入元素时可能还需要扩容，开辟新空间，拷贝元素，释放旧空间的操作，导致效率降低。而list任意位置的插入与删除效率高，不需要搬移元素，时间复杂度为O(1).
4.在空间利用率方面。vector底层是一段连续的空间，不容易造成内存碎片，空间利用率高，缓存利用率高。(就是将内存的数据放到寄存器里，因为底层是连续的，所以少去了寻找下一个值的开销).。list底层为动态开辟的，小节点容易造成内存碎片，空间利用率低，缓存利用率低。
5，迭代器。vector为原生态指针，list底层对原生态指针进行了封装。
6.迭代器失效。vector在插入元素时，需要给迭代器重新赋值来避免插入引起扩容操作导致迭代器失效的问题。在删除时，当前迭代器也会失效，也必须重新赋值，而list，插入元素不会导致迭代器的失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响。
使用场景说明：
list适用于大量的插入与删除操作，不关心随机访问的情况。而vector适用于高效的存储，支持随机访问，不关心插入、删除效率。