1. list 介绍和简单使用

1.1 list介绍

1.2 list简单接口函数

1.3 push_back 和遍历

1.4 list常规接口函数使用

2. list 的其它接口函数

2.1 splice 接合

2.2 remove 删完一个值

2.3 sort和reverse

本章完。

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前面插入50if (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);//删除20if (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;
}