【C++】list的介绍与使用

�� ‍个人主页：简 料

  所属专栏：C++

  个人社区：越努力越幸运社区

  简       介：简料简料，简单有料~在校大学生一枚，专注C/C++/GO的干货分享，立志成为您的好帮手 ~

前言

前面对STL进行了介绍 【 戳此了解STL】，本章就给大家带来STL当中的list~

list的底层是数据结构中的带头双向循环链表，它本质上是对一个序列进行管理，提高我们写代码的效率。在C语言我们想用链表的时候，需要自己造轮子，而有了list之后，一切都变得简单了许多~

能够熟练的使用list，可以很大程度上提高写算法题的效率，有许多的困难算法题，都需要对一串序列数据进行操作，这时候list以及它里面的方法就是个杀手锏了，虽然还有个vector，但有时候由于底层数据结构的原因，list会更能提高算法的效率~

使用STL的三个境界：能用，明理，能扩展 ，那么下面学习list，我们也是按照这个方法去学习

‍list的介绍

list的文档介绍

在C++中，list是一个双向链表容器，属于标准模板库（STL）的一部分。list容器在头文件中定义。

1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)

list的特点包括：

1. 双向性：list中的每一个元素都有一个指向前一个元素和后一个元素的指针，这样的设计使得在list中的任何位置进行插入和删除操作都非常高效。
2. 不支持随机访问：不同于vector和array，我们不能通过索引直接访问list中的元素，这与其底层实现有关。
3. 动态性：list是动态的，可以在运行时进行增长和收缩，这意味着它可以根据需要添加或删除元素。
4. 内存效率：相比于vector，list的内存分配更为高效，当添加或删除大量元素时，list不需要像vector那样重新分配内存空间。
5. 插入和删除效率高：在list的中间插入和删除元素非常快，不需要移动其它元素，只需要改变一些指针。

C++中的list具有重要的实用性和价值，原因如下：

1. 高效的插入和删除操作：相比于其他线性容器，如vector和deque，list在序列的任何位置进行插入和删除操作都是常数时间复杂度，即O(1)。这是因为list是一个双向链表，可以通过改变指针来移动元素，而无需移动其他元素。
2. 内存管理：list在插入和删除大量元素时，与vector相比，内存重新分配的开销较小。这是因为vector是连续存储的，当需要更多空间时，可能需要复制和移动元素。而list是链式存储，插入和删除元素只需要更改相邻元素的指针。
3. 迭代器稳定性：在list中，插入和删除元素不会使指向其他元素的迭代器失效。这在编写涉及迭代器的复杂算法时，可以提高代码的稳定性和效率。
4. 适用性：list适用于需要在任何位置进行高效插入和删除操作的场景。例如，在实现缓存、队列、堆栈等数据结构时，list可以是一个很好的选择。

总的来说，C++中的list为程序员提供了一种灵活且高效的容器选择。虽然它不支持随机访问，并且在某些情况下的空间效率不如vector，但其高效的插入和删除操作以及稳定的迭代器使其在特定场景中具有重要的实用价值。

‍list的使用

list中的接口比较多，此处类似，只需要掌握如何正确的使用，然后再去深入研究背后的原理，已达到可扩展的能力。以下为list中一些常见的重要接口。

✅list的构造

// list的构造void TestList1(){    list l1;                         // 构造空的l1    list l2(4, 100);                 // l2中放4个值为100的元素    list l3(l2.begin(), l2.end());  // 用l2的[begin(), end()）左闭右开的区间构造l3    list l4(l3);                    // 用l3拷贝构造l4    // 以数组为迭代器区间构造l5    int array[] = { 16,2,77,29 };    list l5(array, array + sizeof(array) / sizeof(int));    // 列表格式初始化C++11    list l6{ 1,2,3,4,5 };    // 用迭代器方式打印l5中的元素    list::iterator it = l5.begin();    while (it != l5.end())    {        cout     // 注意这里调用的是list的 begin() const，返回list的const_iterator对象    for (list        cout     int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };    list        cout         cout     int array[] = { 1, 2, 3 };    list    int array1[] = { 1, 2, 3 };    list 7, 8, 9 };    L.insert(pos, v.begin(), v.end());    PrintList(L);    // 删除pos位置上的元素    L.erase(pos);    PrintList(L);    // 删除list中[begin, end)区间中的元素，即删除list中的所有元素    L.erase(L.begin(), L.end());    PrintList(L);}// resize/swap/clearvoid TestList5(){    // 用数组来构造list    int array1[] = { 1, 2, 3 };    listint array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list// erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给其赋值l.erase(it); ++it;}}// 改正void TestListIterator(){int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };listit = l.erase(it);}}