从C语言到C++_16(list的介绍和常用接口函数)网站首页 技术杂谈

从C语言到C++_16(list的介绍和常用接口函数)

GR C 2024-08-24 00:01:03

简介从C语言到C++_16(list的介绍和常用接口函数)

1. list 介绍和简单使用

list是个双向带头循环链表。

带头双向循环链表我们在数据结构与算法专栏中有过详细的讲解，并且还带大家实现过：

数据结构与算法⑦(第二章收尾)带头双向循环链表的实现_GR C的博客-CSDN博客

我们知道，带头双向循环链表是非常合适任意位置的插入和删除的，时间复杂度都是O（1）.

list 在实际的运用中用的没有 vector 多，包括大家在刷题的时候 list 也出现的很少，

因为 list 不支持随机访问，有很多数据堆在那里你可能还需要排序一下，list 要排序，

效率就慢一点，所以用 vector 的情况较多。

但 list 在一些场景也需用到，比如需要频繁的插入和删除，特别是需要在头尾部插入和删除。

1. list 介绍和简单使用

1.1 list介绍

像前面一样查查文档：https://cplusplus.com/reference/list/list/?kw=list

① list 是一个顺序容器：

是允许你在任意位置进行插入删除的顺序容器，并提供双向迭代器。

② list的底层是双向链表结构：

双向链表中每个元素存储在互不相关的独立结点中，在结点中通过两个指针指向其前后元素。

③ list 与 forward_list 非常相似：

它们很相似，最大的不同 forward_list 是单链表，只能向前迭代（也让其因此更简单高效）。

④ 与其他的序列式容器相比（array，vector，deque）：

list 通常在任意位置进行插入、移除元素的执行效率更好。

list 和 forward_list 最大的缺陷是不支持任意位置的随机访问。举个例子：

如果要访问 list 中的第 6 个元素，必须从已知的位置（比如头部或者尾部）迭代到该位置，

在这段位置上迭代需要线性的时间开销。不仅如此，list 还需要一些额外的空间，

以保存每个结点的 "相关联信息"（对于存储类型较小元素的大 list 来说这可能是一个重要的因素）

1.2 list简单接口函数

看看构造：

和vector差不多，看看其它接口函数：

看不懂英文又不想查的朋友看这里：

还是和vector差不多，还有一些特有的接口没截，等下着重讲讲。简单用下上面吧：

1.3 push_back 和遍历

首先思考一个问题：我们还能用 "下标 + 方框号" 的方式遍历吗？

不行的，因为 list 是链表，是通过指针连接的，所以 list 不支持随机访问！

而 string 和 vector 可以，是因为它底层的结构是连续的数组，它的物理结构是连续的。

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

	list<int>::iterator it = lt.begin();// 迭代器遍历1到5 
	while (it != lt.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	for (auto& e : lt)// 范围for 把1到5乘2
	{
		e *= 2;
		cout << e << " ";
	}
	cout << endl;

	list<int>::reverse_iterator rit = lt.rbegin();//反向迭代器倒着遍历
	while (rit != lt.rend()) 
	{
		cout << *rit << " ";
		rit++;
	}
	cout << endl;
}

1.4 list常规接口函数使用

void Test_other()
{
	list<int> lt;
	lt.push_front(10);//头插四个
	lt.push_front(20);
	lt.push_front(30);
	lt.push_front(40);
	list<int>::iterator it = find(lt.begin(), lt.end(), 20);//在20前面插入50
	if (it != lt.end())
	{
		lt.insert(it, 50);
	}
	for (const auto& e : lt)
	{
		cout << e << " ";
	}
	cout << "size = " << lt.size() << endl;

	lt.pop_back();//尾删
	lt.pop_front();//头删
	it = find(lt.begin(), lt.end(), 20);//删除20
	if (it != lt.end())
	{
		lt.erase(it);
	}
	for (const auto& e : lt)
	{
		cout << e << " ";
	}
	cout << "size = " << lt.size() << endl;
}

2. list 的其它接口函数

因为list的存储不是连续的，库里的一些函数用不了（比如sort和reverse），

所以list提供了一些接口函数：

2.1 splice 接合

简单来说就是把一个链表转移到另一个链表里去：

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

	list<int> lt2;	
	lt2.push_back(10);
	lt2.push_back(20);
	lt2.push_back(30);
	lt2.push_back(40);
	lt2.push_back(50);

	lt1.splice(lt1.end(), lt2);//把lt2接合到lt1后面
	for (const auto& e : lt1)// 范围for遍历
	{
		cout << e << " ";
	}
	cout << endl;
}

2.2 remove 删完一个值

remove 只需要给一个元素的值，它就可以自己找自己删！

erase 还需要搞个搞个迭代器，然后还要 if 判断一下，但 remove 就不一样了：

void Test_remove()
{
	list<int> lt;
	lt.push_back(10);
	lt.push_back(20);
	lt.push_back(30);
	lt.push_back(40);

	lt.push_back(10);
	lt.push_back(20);
	lt.push_back(30);
	lt.push_back(40);
	for (const auto& e : lt)
	{
		cout << e << " ";
	}
	cout << endl;

	// 如果存在元素，删完
	lt.remove(10);
	for (const auto& e : lt)
	{
		cout << e << " ";
	}
	cout << endl;

	// 如果待删元素不存在,则无事发生
	lt.remove(50);
	for (const auto& e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
}

2.3 sort和reverse

unique是去重，但是再后面点学的set天生带去重，所以其它接口后面有机会再讲行了。

前面说到：因为list的存储不是连续的，库里的一些函数用不了（比如sort和reverse）。

但是list提供的作用和其差不多，值得注意的是库里的sort底层是快排，快排，链表是用不了的，

那list用上面排序呢？冒泡等是可以的，就是效率太低，这时归并排序就派上用场了，

而且不会多开空间。但是排序大量数据时list的排序就比快排慢了，甚至你拷贝list的数据到vector

用库里的快排，排完再拷回list的时间还要比list自己排得快，但是数据量小的话也差不多：

void Test_sort_reverse()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(20);
	lt.push_back(2);
	lt.push_back(40);
	lt.push_back(5);
	lt.push_back(10);
	lt.push_back(30);
	lt.push_back(4);
	lt.push_back(4);
	lt.push_back(50);
	for (const auto& e : lt)
	{
		cout << e << " ";
	}
	cout << endl;

	lt.sort();
	for (const auto& e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
	
	lt.reverse();// 懂我意思把
	for (const auto& e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
}