【C++】—— list 的了解与使用

1 list 的函数接口

  STL库中的 $list$，其底层是一个带头双向循环链表

  STL库 的容器都有很强的相似性，我们有了前面 $string$、$vector$ 的基础，再来学习 $list$ 就会轻松很多。
  我把 $list$ 的函数接口放出来，相信都加看一眼就知道如何使用了。

成员函数

迭代器

容量

元素访问

修改

  上述接口我们都很熟悉了，本文就不再一一进行介绍，大家自行查阅文档即可

  但是关于操作的接口我们还比较陌生，等下我们会一一学习

操作

2 迭代器

2.1 简单使用 list 的迭代器

  我们先来简单使用一下 $list$ 的迭代器

void test1()
{
	list<int> l1;
	l1.push_back(1);
	l1.push_back(2);
	l1.push_back(3);
	l1.push_back(4);
	l1.push_back(5);
	list<int>::iterator it = l1.begin();
	while (it != l1.end())
	{
		cout << *it << endl;
		++it;
	}
}

运行结果：

  可以看到，$list$ 的迭代器访问和 $string$、$vector$ 等是一样的。

  那么 $list$ 的迭代器可不可以使用 + 呢？

l1.insert(l1.begin() + 3, 10);

不可以的！

  那既然不可以直接 +3，我们想在第三个位置之前插入数据怎么办呢？

方法如下：

void test1()
{
	list<int> l1;
	l1.push_back(1);
	l1.push_back(2);
	l1.push_back(3);
	l1.push_back(4);
	l1.push_back(5);

	auto it = l1.begin();
	int k = 3;
	while (k--)
	{
		++it;
	}
	l1.insert(it, 10);

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

运行结果：

2.2 迭代器的划分

  这里，我先来给大家介绍一下迭代器的划分

从功能上进行划分

• iterator
• reverse_iterator
• const_iterator
• const_reverse_iterator

从性质上进行划分

• 单向迭代器：$forwad$$list$ / $unordered$$map$ / $unordered$_$set$ 等为单向迭代器。他们只支持 ++。
• 双向迭代器：$list$ / $map$ / $set$ 等都是双向迭代器。他们支持++/–，但不支持+/-。
• 随机迭代器：$vector$ / $string$ / $deque$ 等都是随机迭代器。他们支持++/–/+/-。

• 决定迭代器的性质的是容器的底层结构。

  $list$ 的迭代器是一个双向迭代器

2.3 不同迭代器的使用场景

  决定迭代器的性质的是容器的底层结构。而底层结构也决定了容器可以使用那些算法
  

2.3.1 sort

  用 $sort$ 算法进行排序，并不是传什么迭代器都可以的，必须传随机迭代器，否则就会报错。
  为什么呢？因为 $sort$ 底层是快速排序。快排里面要做类似三数取中的东西，它需要支持随机访问。
  

2.3.2 reverse

  $reverse$ 是将指定范围内的数据进行翻转。

  这个算法底层用了 '-'操作符，因此要传双向迭代器。

  那 $vector$、$string$ 这些随机迭代器能用逆置算法吗？
  肯定能。因为他们功能上是一个包含的关系，双向是一种特殊的单向，随机是一种特殊的双向
  

2.3.3 find

  那 $find$ 算法又需传递什么迭代器呢？
  InputIterator 是什么迭代器呢？它不是单向，双向，随机种的任意一种

这里我们再简单介绍一下：

  库里面对迭代器性质的定义使用了 C++ 中继承的概念，继承就是子类是一个特殊的父类，所以它认为这里的单向、双向、随机是一个继承关系：随机是一个特殊的双向 ，双向是一个特殊的单向。
  同时，库中引申出了两个不存在的迭代器：只读和只写迭代器（严格来说没有容器的迭代器类型对应这两类，是抽象的概念）。InputIterator迭代器 意味着单向、双向、随机都是其子类。
  出现InputIterator就说明可以给任意类型的迭代器
  
  这里因为 $find$ 底层只用了 ++

3 emplace_back

  现阶段，我们可以认为 push_back 与 emplace_back 是一样的，都是尾插一个数据

void test2()
{
	list<int> l1;
	l1.emplace_back(1);
	l1.emplace_back(2);
	l1.emplace_back(3);
	l1.emplace_back(4);
	l1.emplace_back(5);
	list<int>::iterator it = l1.begin();
	while (it != l1.end())
	{
		cout << *it << endl;
		++it;
	}
}

运行结果：

  但是在用法上，如果插入数据的参数是多个的，emplace_back效率会高一些。
  
假设我们现在要插入自定义类型 A

struct A
{
	A(int a1 = 1, int a2 = 1)
		:_a1(a1)
		,_a2(a2)
	{}

	int _a1;
	int _a2;
};

对应插入自定义类型 A 有两种常见的方法

• 插入有名对象
• 插入匿名对象

void test3()
{
	list<A> lt;

	A aa1(1, 1);
	lt.push_back(aa1);
	lt.push_back(A(2, 2));

	lt.emplace_back(aa1);
	lt.emplace_back(A(3, 3));
}

  这两种方式 $push$$back$ 和 $emplace$$back$ 都支持
  
  但是 emplace_back 还支持这样写：

void test4()
{
	list<A> lt;
	lt.emplace_back(3, 3);
}

  $emplace$_$back$ 支持直接传构造 A 的参数。
  这里不是隐式类型转换，现阶段我们先不管其底层，学会用法即可。
  
  

4 操作函数

4.1 sort

4.1.1 list中sort介绍

  我们前面看到，算法库中的 sort 要求是随机迭代器，$list$ 的迭代器并不符合，因此它自己实现了一个排序算法。和算法库中的 $sort$ 一样，$list$ 中的 $sort$ 排序默认排的是升序，如果要排降序则要用到仿函数(后面会讲)。
  $list$ 实现的 $sort$ 底层用的是归并排序，而算法库中的 $sort$ 底层用的是快速排序

void test5()
{
	list<int> lt;
	lt.push_back(3);
	lt.push_back(5);
	lt.push_back(4);
	lt.push_back(1);
	lt.push_back(2);

	lt.sort();
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;

	lt.sort(greater<int>());
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
}

运行结果：

4.1.2 list 中 sort 与算法库中 sort 效率比较

  虽然 $list$ 中实现了 $sort$ 排序算法，但是它的排序效率很低，尽量不要用它来排序。

  我们将他与算法库中的 $sort$ 进行性能对比

• 我们产生 1000000 个相同的数，放进 $vector$ 和 $list$ 中，再分别用算法库中 $sort$，和 $list$ 中 $sort$ 排序，看运行时间

void test10()
{
	srand(time(0));
	const int N = 1000000;

	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);
	}

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

	int begin2 = clock();
	lt1.sort();
	int end2 = clock();

	printf("vector sort:%d\n", end1 - begin1);
	printf("list sort:%d\n", end2 - begin2);
}

运行结果：

  差距 2 倍多

• 这一次我们用两个链表进行排序：一个链表将数据拷贝进 $vector$，用库中的 $sort$ 排序，后再拷贝回来；另一个直接调用 $list$ 中的 $sort$

void test11()
{
	srand(time(0));
	const int N = 1000000;

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

	for (int i = 0; i < N; ++i)
	{
		auto e = rand() + i;
		lt1.push_back(e);
		lt2.push_back(e);
	}

	int begin1 = clock();
	// 拷贝vector
	vector<int> v(lt2.begin(), lt2.end());

	// 排序
	sort(v.begin(), v.end());

	// 拷贝回lt2
	lt2.assign(v.begin(), v.end());

	int end1 = clock();

	int begin2 = clock();
	lt1.sort();
	int end2 = clock();

	printf("list copy vector sort copy list sort:%d\n", end1 - begin1);
	printf("list sort:%d\n", end2 - begin2);
}

  上述代码用了 $list$ 中的 $assign$ 接口，我们简单介绍一下

  $assgin$ 功能是用一段迭代器区间对调用函数的 $list$ 对象进行拷贝，任何容器的迭代器都可以。像 $vector$ 等都有 $assgin$ 接口

运行结果：

  可以看到，即使多了两次拷贝，依然是算法库中的 sort 效率更高。同时这也说明了拷贝的代价其实是很低的。
  

4.2 merge

  $merge$ 接口的功能是：将两个链表合并。合并的前提是两个链表是有序的。

void test6()
{
	std::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);

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

运行结果：

  需要注意：合并会让其中一个链表空掉。
  其底层是创建一个新链表，依次去两个链表中小的尾插，最后再将新链表与first链表进行交换。

4.3 unique

  $unique$ 是一个去重接口，但它要求数据必须是有序的

void test7()
{
	std::list<int> lt;

	lt.push_back(3);
	lt.push_back(3);
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(4);
	lt.push_back(4);
	lt.push_back(5);
	lt.push_back(5);
	lt.push_back(1);
	lt.push_back(5);
	lt.push_back(2);
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;

	lt.sort();
	lt.unique();

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

运行结果：

4.4 remove

  $remove$ 接口是对一个值进行删除，他和 $erase$ 有点像。不同的是 $erase$ 是传一个迭代器；$remove$ 是传一个值，我找到了我就删，没找到也不会报错

4.5 splice

  $splice$ 是粘贴的意思，但这函数接口功能更像剪切
  $splice$ 的功能本质是一种转移：将 $x$ 链表中的元素转移到调用该函数的 $position$ 位置之前(是转移不是粘贴)
  
实例：将 $mylist2$ 数据转移到 $mylist1$ 中 2 的前面

void test8()
{
	std::list<int> mylist1, mylist2;
	std::list<int>::iterator it;

	// set some initial values:
	for (int i = 1; i <= 4; ++i)
		mylist1.push_back(i);      // mylist1: 1 2 3 4

	for (int i = 1; i <= 3; ++i)
		mylist2.push_back(i * 10);   // mylist2: 10 20 30

	it = mylist1.begin();
	++it;							// points to 2

	mylist1.splice(it, mylist2);	// mylist1: 1 10 20 30 2 3 4
									// mylist2 (empty)
									// "it" still points to 2 (the 5th element)
	cout << "mylist1：";
	for (auto e : mylist1)
	{
		cout << e << " ";
	}
	cout << endl;
	cout << "mylist2：";
	for (auto e : mylist2)
	{
		cout << e << " ";
	}
	cout << endl;
}

运行结果：

  
  $splice$ 还有以下用法：调整当前链表节点的顺序
  比如我想将第一个链表中的 5 放在第一个，怎么做呢

void test9()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_back(5);
	lt.push_back(6);

}

  第一种方法就是将 5 这个节点删除，再进行头插。但这一来一去又是删除又是 $new$ 的，效率较低。
  我们还有一种方法：运用 splice 接口。$splice$ 允许自己转移给自己。

void test9()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_back(5);
	lt.push_back(6);

	list<int>::iterator it = find(lt.begin(), lt.end(), 5);
	if (it != lt.end())
	{
		lt.splice(lt.begin(), lt, it);
	}
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
}

运行结果：

  
  不仅如此，我们函转移一段范围

list<int>::iterator it = find(lt.begin(), lt.end(), 4);
if (it != lt.end())
{
	lt.splice(++lt.begin(), lt, it, lt.end());
}

运行结果：

  好啦，本期关于 $list$ 的知识就介绍到这里啦，希望本期博客能对你有所帮助。同时，如果有错误的地方请多多指正，让我们在 C++ 的学习路上一起进步！