我们之前学过string，vector，对于容器有了更深了解接下来我们进一步了解list。这个list指的是双向链表。

list的初始化

与vector一样

迭代器除了可以传迭代器区间，也可以传数组的指针。

指针就是一种特殊的迭代器，前提是指针是指向数组的指针。

既然如此sort也是可以使用的

接下来来看遍历

迭代器来实现，基本和vector类似

但是在这里我们能看到有些不一样

可以看到不同种类的迭代器包括随机迭代器，单向迭代器和双向迭代器，命名不同他的作用也不同

通用的就是++，！=，*。

算法的实现对迭代器都是有要求的，迭代器的命名就是对于这个迭代器实现的要求。

但是迭代器可以这样认为双迭代器是一种特殊单向迭代器，随机迭代器是一种特殊的双向迭代器，所单向迭代器可以实现的后面两种都可以进行实现，以此类推。

我们可以看到算法里面sort是支持随机迭代器的，但是我们的list是一个底层由双向迭代器来实现的

要是要用我们就只能调用list的成员函数sort

modify

list支持头插头删，尾插尾删

void test03()
{
	list<int> lt1 = { 1,2,3,6,5,5,0 };
	for (auto e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;


	lt1.push_back(99);
	lt1.push_front(88);
	for (auto e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;

	lt1.pop_back();
	lt1.pop_front();

	for (auto e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;
}

list是双向迭代器是不支持这样的操作

当然这样也是不支持，因为end是指最后一个数据的下一个位置，范围for遍历时会奔溃

，这里就是可以简单实现头插头删，尾插尾删，用的比较少，搭配find或者advance等其他的可以实现多种位置插入删除，

resize和前面vector也是类似的

operation

我们先来看sort

由于算法库里面的vector是要求随机迭代器，所以list自己实现了一个成员函数的sort，但是两者实现的底层逻辑是不同算法库用的是快排，list自己实现用的则是归并算法。两者在数据很大的时候时间效率，list的远小于算法库的实现。

然后我们来看下一组

让list->copy->vector->sort->copy->list

发现这个速度比直接在list里面排序还要再快。所以我们在使用时list的sort使用频率还是比较少的，在数据量比较少的时候。

remove去除所有特定的元素

merge合并两个有序链表

unique是去除重复元素，前提是有序链表

splice

就是将一个容器里面的数据移动到list里面然后在将原来储存的位置删除

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<list>
#include<vector>
#include<algorithm>
using namespace std;

//construct
void test01()
{
	list<int> lt1;
	list<int> li2(10,1);//创10个，初始化为1
	vector<int> v1 = { 1,2,3,6,5,5,0 };
	list<int> li3(v1.begin(),v1.end());//迭代器来进行初始化
	list<int> li4 = { 9,8,7,6,5,2,3};//用花括号来进行初始化
	//对于之前的容器,list也可以用下面这种方式来进行初始化
	//迭代器除了可以传迭代器区间，也可以传数组的指针。
	//指针就是一种特殊的迭代器，前提是指针是指向数组的指针。
	int a[] = { 1,29,3,4,56 };
	list<int> li5 (a,a+5);
	sort(a, a + 5);
	
	for (auto e : a)
	{
		cout << e << " ";
	}
	cout << endl;

}
//迭代器
void test02()
{
	//1.通用的相似的遍历容器的方式，并封装屏蔽
	//容器结构的差异和实现底层细节
	//2.复用，实现算法时用迭代器函数模板实现，跟底层结构
	list<int> lt1 = { 1,2,3,6,5,5,0 };
	list<int>::iterator it = lt1.begin();
	while (it != lt1.end())
	{
		cout << (*it)<<" ";
		it++;
	}
	cout << endl;

	vector<int> v1 = { 1,2,3,6,5,5,0 };
	sort(v1.begin(), v1.end());
	for (auto e : v1)
	{
		cout << e << " ";
	}
	cout << endl;


	/*sort(lt1.begin(), lt1.end());
	for (auto e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;*/
}


void test03()
{
	list<int> lt1 = { 1,2,3,6,5,5,0 };
	for (auto e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;


	lt1.push_back(99);
	lt1.push_front(88);
	for (auto e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;

	lt1.pop_back();
	lt1.pop_front();

	for (auto e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;


	lt1.insert(lt1.begin(), 100);
	for (auto e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;

	lt1.erase(lt1.begin());
	for (auto e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;


	lt1.resize(5);
	for (auto e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;


	lt1.resize(50, 1);
	for (auto e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;

}


void test04()
{
	list<int> lt1 = { 1,2,3,6,5,5,0,5,5,5,5 };
	lt1.remove(5);
	for (auto e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;


	//merge

	list<double> first, second;

	first.push_back(3.1);
	first.push_back(2.2);
	first.push_back(2.9);

	second.push_back(3.7);
	second.push_back(7.1);
	second.push_back(1.4);
	//要求是两个有序的链表
	first.sort();
	second.sort();

	first.merge(second);
	//second会变成空的
	for (auto e : first)
	{
		cout << e << " ";
	}
	cout << endl;

	list<double> l1;
	l1 = { 1,2,5,2,3,6,9,6,5,5,5, };
	l1.sort();
	l1.unique();
	for (auto e : l1)
	{
		cout << e << " ";
	}
	cout << endl;

}

void test05()
{
	//const int N = 10000000;  // 数据量大小
	//srand(time(0));        // 初始化随机数种子

	//list<int> lt1;
	//vector<int> v;

	//// 填充数据
	//for (int i = 0; i < N; ++i) {
	//	auto e = rand() + i;
	//	lt1.push_back(e);
	//	v.push_back(e);
	//}

	//// vector排序
	//int begin1 = clock();
	//sort(v.begin(), v.end());  // vector用快速排序
	//int end1 = clock();

	//// list排序
	//int begin2 = clock();
	//lt1.sort();  // list用归并排序
	//int end2 = clock();

	//// 输出耗时
	//printf("vector sort time: %d ms\n", end1 - begin1);
	//printf("list sort time: %d ms\n", end2 - begin2);


	const int N = 1000000;  // 数据量大小
	srand(time(0));        // 初始化随机数种子

	list<int> lt1;
	list<int> lt2;

	// 填充两个list相同的数据
	for (int i = 0; i < N; ++i) {
		auto e = rand() + i;
		lt1.push_back(e);
		lt2.push_back(e);
	}

	// 1. list直接排序（使用list::sort，归并算法）
	int begin1 = clock();
	lt1.sort();  // list自身的归并排序
	int end1 = clock();

	// 2. list -> vector -> sort -> list（利用vector的快速排序）
	int begin2 = clock();

	// 先拷贝list到vector
	vector<int> temp(lt2.begin(), lt2.end());

	// 用vector的sort排序
	sort(temp.begin(), temp.end());

	// 再拷贝回list
	lt2.clear();
	lt2.insert(lt2.begin(), temp.begin(), temp.end());

	int end2 = clock();

	// 输出耗时
	printf("list直接排序(归并): %d ms\n", end1 - begin1);
	printf("list->vector->list排序(快速排序): %d ms\n", end2 - begin2);


}



void test06()
{

	list<int> lt1 = { 1,2,3,6,5,5,0,5,5,5,5 };
	//list<int> lt2 = { 1,2,3 };
	//list<int>::iterator it = lt1.begin();
	//++it;
	//lt1.splice(it, lt2);
	//for (auto e : lt1)
	//{
	//	cout << e << " ";
	//}
	//cout << endl;

	
	auto it = find(lt1.begin(), lt1.end(), 6);
	lt1.splice(lt1.begin(), lt1, it);
	for (auto e : lt1)
		{
			cout << e << " ";
		}
		cout << endl;
}
int main()
{
	test06();
	return 0;
}