C++要笑着学：list常用接口讲解

   ​​​​​​ 藍 爆笑教程   《C++要笑着学》  火速订阅  

 写在前面

一听 list ，我们就知道是个双向带头循环链表。list 在实际的运用中用的没有 vector 多，包括大家在刷题的时候 list 也出现的很少，因为 list 不支持随机访问，有很多数据堆在那里你可能还需要排序一下，list 要排序，就是一个大问题，所以用 vector 的情况较多。

但 list 也并不是一文不值的，如果需要频繁的插入和删除，特别是需要在头尾部插入和删除，坐拥  的 list 就有了用武之地，比如后期讲 LRUCache 的时候就用得到。

如果觉得不错，欢迎点赞收藏加关注。话不多说，我们正式开始！

---

Ⅰ. list 的介绍和使用 0x00 初识 list

我们已经学习过 string 和 vector 了，想必大家已经掌握了查文档的技能。

 现在我们要学习如何使用 list，最好的方式仍然是打开文档去学习！

 查看文档：list - C++ Reference

template < class T, class Alloc = allocator > class list;

① list 是一个顺序容器：

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

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

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

③ list 与 forward_list 非常相似：

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

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

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

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

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

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

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

0x01 创建 list

 头文件：

#include 
using namespace std;

 引入头文件后，我们创建一个 类型的 list，我们给它取名为 L ：

#include 
#include 
using namespace std;

int main(void) 
{
	list L;		// 创建一个  类型的 list

	return 0;
}

Ⅱ. list 的修改操作 0x00 引入：

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

我们知道，带头双向循环链表是非常合适任意位置的插入和删除的，因为通通都是  .

0x01 push_back 头插

 在 list 尾部插入值为 val 的元素。

 用 push_back 对 L 尾插：

#include 
#include 
using namespace std;

int main(void) 
{
	list L;		// 创建一个类型的list
	L.push_back(1);  
	L.push_back(2);
	L.push_back(3);
	L.push_back(4);

	return 0;
}

 随手尾插了  ，我们现在来打印，看看尾插的效果如何。

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

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

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

" 呵呵，现在到我迭代器了？"

 iterator：

int main(void) 
{
	
	list L;

	
	L.push_back(1);
	L.push_back(2);
	L.push_back(3);
	L.push_back(4);

	
	list::iterator it = L.begin();
	while (it != L.end()) {
		cout << *it << " ";
		it++;
	}
	cout << endl;

	return 0;
}

 运行结果如下：

 （成功打印）

如果我们想倒着遍历，我们就可以使用 —— 反向迭代器

反向迭代器是反着遍历访问元素的，我们用 rbegin() 和 rend() 去操作。

 "社稷有累卵之危，生灵有倒悬之急" —— 王司徒

 reverse_iterator：

int main(void) 
{
	
	list L;

	
	L.push_back(1);
	L.push_back(2);
	L.push_back(3);
	L.push_back(4);

	
	list::reverse_iterator rit = L.rbegin();
	while (rit != L.rend()) {
		cout << *rit << " ";
		rit++;
	}
	cout << endl;

	return 0;
}

 运行结果如下：

（像 const 迭代器，只能读不能写，这里我们就不壹壹演示了）

0x02 push_front 头插

 用 push_front 头插一些数据到 L 中：

void list_test2() {
	
	list L;

	
	L.push_front(1);
	L.push_front(2);
	L.push_front(3);
	L.push_front(4);

	
	for (auto e : L) cout << e << " ";
}

 运行结果如下：

 能用迭代器自然也就能用范围 for，因为语法简洁，我们下面都用范围 for 去打印。

（尾删和头删同理，这些操作我们已经接触过很多次了，下面介绍就直接贴代码，不做讲解了）

0x03 pop_back 尾删

 删除 L 中的最后一个数据：

void list_test3() {
	
	list L;

	
	L.push_back(1);
	L.push_back(2);
	L.push_back(3);
	L.push_back(4);
	cout << "删除前：";
	for (auto e : L) cout << e << " "; cout << endl;
	
	
	L.pop_back();
	cout << "删除后：";
	for (auto e : L) cout << e << " "; cout << endl;
}

 运行结果如下：

 当然，如果表内没有元素，进行删除操作，就会触发断言：

void list_test5() {
	list L;
	L.pop_back();
}

    

 （采用的是暴力的处理方式）

0x04 pop_front 头删

 删除 L 中的第一个数据：

void list_test4() {
	
	list L;

	
	L.push_back(1);
	L.push_back(2);
	L.push_back(3);
	L.push_back(4);
	cout << "删除前：";
	for (auto e : L) cout << e << " "; cout << endl;
	
	
	L.pop_front();
	cout << "删除后：";
	for (auto e : L) cout << e << " "; cout << endl;
}

 运行结果如下：

0x05 insert 插入

在上一节讲解 vector 实现的时候，我们对迭代器失效的问题进行了一些简单探讨。

这里 list 的 insert 同样也会涉及迭代器失效的问题，这个我们在模拟实现的时候再次探讨。

（这里笔者绝非偷懒，(～￣▽￣)～ 因为模拟实现的时候结合底层去讲解会更容易理解）

0x06 clear 清空

清空 list 中的有效元素，并使容器的大小 size 变为 0。

 用 clear 清空 L 中有效元素：

void list_test5() {
	list L;
	L.push_back(1);
	L.push_back(2);
	L.push_back(3);
	L.push_back(4);
	cout << "清空前：";
	for (auto e : L) cout << e << " "; cout << endl;

	
	L.clear();
	cout << "清空后：";
	for (auto e : L) cout << e << " "; cout << endl;
}

 运行结果如下：

0x07 erase 删除

 任意位置删除，这里仍然是用迭代器区间，find() 查找元素。

 erase：

void list_test6() {
	list L;
	L.push_back(1);
	L.push_back(2);
	L.push_back(3);
	L.push_back(4);
	for (auto e : L) cout << e << " "; cout << endl;

	list::iterator it = find(L.begin(), L.end(), 4);  // 删除元素：4
	if (it != L.end()) {		// 判断it是否存在
		L.erase(it);			// 删除it
	}
	else {
		cout << "没找到";
	}
	for (auto e : L) cout << e << " "; cout << endl;
}

  运行结果如下：

 再次提醒：erase 之前要做判断！如果待删目标不存在，会寄！

 （如果不判断，并且待删目标不存在）

Ⅲ. list 容量操作 0x00 size 返回有效节点个数

  size() 用于返回 list 中有效节点的个数。

 size：

void list_test6() {
	list L;
	L.push_back(1);
	L.push_back(2);
	L.push_back(3);
	L.push_back(4);
	for (auto e : L) cout << e << " "; cout << endl;

	cout << "有效节点个数：";
	cout << L.size() << endl;
}

 运行结果如下：

0x01 empty 检测容器是否为空

 （之前讲 string 和 vector 的时候忘记提了）

empty 是用来检测容器是否为空的，如果为空则返回 true，否则返回 false。

 这个我们在数据结构章节自己都实现过，返回一个布尔值：

  empty：

void list_test7() {
	list L;
	L.empty() == true ? cout << "为空" : cout << "不为空";
}

  运行结果如下：

0x02 resize 调整容器大小

list 中的 resize 和之前的 resize 的 "扩容" 有点不一样，它没有容量。

这里的 resize 是调整容器的大小，使其包含  个元素。

 用 resize 在 L 后面插入10 个 5：

void list_test8() {
	list L;
	L.push_back(1);
	L.push_back(2);
	L.push_back(3);
	L.push_back(4);
	for (auto e : L) cout << e << " "; cout << endl;

	L.resize(10, 5);   // 插入10个5
	for (auto e : L) cout << e << " "; cout << endl;
}

 运行结果如下：

Ⅳ. 其他操作 0x00 reverse 逆置

用来逆置 list 中的元素。 （注意是 reverse，不是 reserve）

 将 L 的元素逆置：

void list_test9() {
	list L;
	L.push_back(1);
	L.push_back(2);
	L.push_back(3);
	L.push_back(4);
	for (auto e : L) cout << e << " "; cout << endl;

	L.reverse();  // 将L的元素逆置
	for (auto e : L) cout << e << " "; cout << endl;
}

 运行结果如下：

0x01 sort 排序

 用 sort 对 L 中的元素进行排序：

void list_test9() {
	list L;
	L.push_back(4);
	L.push_back(2);
	L.push_back(6);
	L.push_back(1);
	for (auto e : L) cout << e << " "; cout << endl;

	L.sort();   // 对L进行排序
	for (auto e : L) cout << e << " "; cout << endl;
}

 运行结果如下：

 （从小到大排序）

0x02 unique 去重

 去重之前是有要求的，去重之前一定要先排序！如果不排序可能会去不干净。

 unique：

void list_test11() {
	list L;
	L.push_back(2);
	L.push_back(1);
	L.push_back(2);
	L.push_back(1);
	for (auto e : L) cout << e << " "; cout << endl;

	L.sort(); // 去重前排个序

	cout << "去重后：";
	L.unique();
	for (auto e : L) cout << e << " "; cout << endl;
}

 运行结果如下：

 如果不排序，会导致去不干净情况发生：

void list_test11() {
	list L;
	L.push_back(2);
	L.push_back(1);
	L.push_back(2);
	L.push_back(1);
	for (auto e : L) cout << e << " "; cout << endl;

	// L.sort(); // 去重前排个序

	cout << "去重后：";
	L.unique();
	for (auto e : L) cout << e << " "; cout << endl;
}

0x03 remove 直接爽删

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

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

 remove：

void list_test12() {
	list L;
	L.push_back(10);
	L.push_back(20);
	L.push_back(30);
	L.push_back(40);
	for (auto e : L) cout << e << " "; cout << endl;

	// 如果删一个存在的元素
	L.remove(10);
	for (auto e : L) cout << e << " "; cout << endl;

	// 如果待删元素不存在
	L.remove(0);
	for (auto e : L) cout << e << " "; cout << endl;
}

  运行结果如下：

自己去找自己去删，就是爽。而且就算要删元素不存在，也没有关系。

补充：remove() 函数用于从列表中删除所有出现的给定元素，而 remove_if() 函数用于从 list 中删除某些特定元素的集合。

0x04 splice 接合

简单来说就是把一个链表转移到另一个链表里去。LRUCache，访问一个数据要调优先级的时候就用得到这个接口。我们这里先简单介绍一下。

 把 L2 的内容，接到 L1 的 begin() 前面：

void list_test13() {
	list L1;
	L1.push_back(1);
	L1.push_back(2);
	L1.push_back(3);
	cout << "L1: ";
	for (auto e : L1) cout << e << " "; cout << endl;

	list L2;
	L2.push_back(10);
	L2.push_back(20);
	L2.push_back(30);
	cout << "L2: ";
	for (auto e : L2) cout << e << " "; cout << endl;

	list::iterator pos = L1.begin();
	L1.splice(pos, L2);  // 把L2的内容，接到L1的begin()前面
	cout << "接合后：";
	for (auto e : L1) cout << e << " "; cout << endl;
}

 运行结果如下：

 [ 笔者 ]   王亦优
 [ 更新 ]   2022.5.17
❌ [ 勘误 ]   
 [ 声明 ]   由于作者水平有限，本文有错误和不准确之处在所难免，
              本人也很想知道这些错误，恳望读者批评指正！

 参考资料

C++reference[EB/OL]. []. http://www.cplusplus.com/reference/. Microsoft. MSDN(Microsoft Developer Network)[EB/OL]. []. . 百度百科[EB/OL]. []. https://baike.baidu.com/. 比特科技. C++[EB/OL]. 2021[2021.8.31]. .