。

list的底层是双向链表结构#xff0c;双向链表中每个元素存储在互不相关的独立节点中#xff0c;在节点中…一、介绍

list是可以在常数范围内在任意位置进行插入和删除的序列式容器并且该容器可以前后双向迭代。

list的底层是双向链表结构双向链表中每个元素存储在互不相关的独立节点中在节点中通过指针指向其前一个元素和后一个元素。

list与forward_list非常相似最主要的不同在于forward_list是单链表只能朝前迭代已让其更简单高效。

与其他的序列式容器相比(arrayvectordeque)list通常在任意位置进行插入、移除元素的执行效率更好。

与其他序列式容器相比list和forward_list最大的缺陷是不支持任意位置的随机访问比如要访问list的第6个元素必须从已知的位置(比如头部或者尾部)迭代到该位置在这段位置上迭代需要线性的时间开销list还需要一些额外的空间以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素。

这个时候大家可能觉得都是有序列表那么和vector有什么区别和对比吗实际上和我们学习数据结构时对链表和数组的对比很像我来介绍一下

std::list

是一个双向链表支持在常数时间内对序列的任何位置进行插入和删除操作。

由于其链表的性质list

list[5]

更适用于元素频繁插入和删除的场景尤其是在序列的头部和尾部或者你不需要通过索引来访问元素。

迭代器失效问题较少插入和删除操作不会导致除了被操作的元素之外的迭代器失效。

在内存中不是连续存储的因此不支持指针算术运算并且可能导致较差的缓存性能。

std::vector

是一个动态数组可以在末尾快速地添加或移除元素均摊常数时间复杂度而且支持快速随机访问即可以以常数时间访问任意位置的元素。

在

vector

的中间或开头插入或删除元素可能会导致较高的性能开销因为这些操作需要移动插入点之后或删除点之后的所有元素。

适用于需要经常随机访问元素但对于插入和删除的频率较低的场景。

在内存中是连续存储的这意味着可以使用指针算术并且有助于优化缓存使用。

当

vector

重新分配更大的内存空间以容纳更多元素时所有的迭代器、引用和指针都可能失效。

作为STL(标准模板库)中的一个类我们这篇blog的任务就是学习其的使用。

构造函数

value_type())构造的list中包含n个值为val的元素list

(const

上面虽然用了不少代名词我们直接上代码例子分析自然就清楚了分析在代码中。

如果迭代器看不懂可以看这一篇【C】C中的vector-CSDN博客里面详细介绍了

#include

其实我们可以看出来list这个类和之前的使用类的方法是基本一致的不过他需要一个int来确定这个序列容器的类型比如intchar....就是listint可以当成一个整体和vector很像。

list

此处大家可暂时将迭代器理解成一个指针该指针指向list中的某个节点

函数声明

获取第一个数据位置的iterator/const_iterator

rbegin

获取最后一个数据位置的reverse_iterator获取第一个数据前一个位置的

reverse_iterator

保护数据通过将l声明为常量引用我们保证了在print_list函数内部无法修改列表l的内容。

//

这意味着无法添加、删除或修改列表中的任何元素。

这是一种良好的编程实践//

l.begin();

接口说明push_front在list首元素前插入值为val的元素pop_front删除list中第一个元素push_back在list尾部插入值为val的元素pop_back删除list中最后一个元素insert在list

position

position位置的元素swap交换两个list中的元素clear清空list中的有效元素

上代码看实现

push_back/pop_back/push_front/pop_front

void

在list的尾部插入4头部插入0L.push_back(4);L.push_front(0);PrintList(L);//

删除list尾部节点和头部节点L.pop_back();L.pop_front();PrintList(L);

insert

删除pos位置上的元素L.erase(pos);PrintList(L);//

删除list中[begin,

end)区间中的元素即删除list中的所有元素L.erase(L.begin(),

resize/swap/clear

sizeof(array1[0]));PrintList(l1);//

l2;l1.swap(l2);PrintList(l1);PrintList(l2);

//使用resize将l2的大小先增加到5个元素所有新添加的元素都将被赋值为99l2.resize(5,

99);PrintList(l2);//

{TestList1();TestList2();TestList3();return

好了目前通过上面这一段精简的代码我们把常用的成员方法基本解决了但是list的成员方法实在太多很多操作都是很特殊不常见的但是如果刚好需要又非常方便所以就是可以在需要的时候查官方文档。

在之前我们学习过vector的迭代器会有失效的情况原因很简单指针失效了那么list会不会有这种情况呢答案是有的前面说过此处大家可将迭代器暂时理解成类似于指针迭代器失效即迭代器所指向的节点的无效即该节点被删除了。

因为list的底层结构为带头结点的双向循环链表因此在list中进行插入时是不会导致list的迭代器失效的只有在删除时才会失效并且失效的只是指向被删除节点的迭代器其他迭代器不会受到影响。

所以影响相对vector来说比较小。

#include

{TestListIterator1();TestListIterator2();return

TestListIterator1

其实很简单第一个当调用erase(it)后it被删除使得it失效。

尝试在失效的迭代器上进行操作比如递增it是未定义行为。

第二个l.erase(it)这里使用了“后置递增”运算符它创建了it的一个副本然后将副本传递给erase方法。

erase删除了当前迭代器指向的元素然后it被递增指向下一个元素。

因为it在递增前已经复制给erase所以即使在删除当前元素后递增操作是在一个新的、未被修改的迭代器上进行的这保证了迭代器的有效性。

或者可以这样写等价的it

l.erase(it);erase函数返回下一个有效的迭代器然后将其赋值给it。

这样it始终保持有效且指向当前元素的下一个元素。

三、结语

到此为止我们已经把list的基本使用方法学习结束了list的成员方法十分丰富这篇文章就是介绍了常用的让大家基本会使用目前你也可以用这种双向列表来实现一些复杂的算法我在下面了可以给大家写一个。

等我有时间再出一篇模拟实现list的blog理解他的底层实现有缘再见朋友

约瑟夫环问题Josephus

Problem。

这个问题的一个版本可以描述如下N个人围成一圈从第一个人开始报数每报到M时该人被淘汰接着从下一个人开始继续报数直到所有人都被淘汰。

任务是按顺序输出被淘汰人的编号。

#include