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


  •   🧑‍🎓个人主页:简 料

  •   🏆所属专栏:C++

  •   🏆个人社区:越努力越幸运社区

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


C/C++学习路线 (点击解锁)
❤️C语言
❤️初阶数据结构与算法
❤️C++
❤️高阶数据结构
❤️Linux系统编程与网络编程

🏆前言

🌀 前面对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<int> l1;                         // 构造空的l1
    list<int> l2(4, 100);                 // l2中放4个值为100的元素
    list<int> l3(l2.begin(), l2.end());  // 用l2的[begin(), end())左闭右开的区间构造l3
    list<int> l4(l3);                    // 用l3拷贝构造l4

    // 以数组为迭代器区间构造l5
    int array[] = { 16,2,77,29 };
    list<int> l5(array, array + sizeof(array) / sizeof(int));

    // 列表格式初始化C++11
    list<int> l6{ 1,2,3,4,5 };

    // 用迭代器方式打印l5中的元素
    list<int>::iterator it = l5.begin();
    while (it != l5.end())
    {
        cout << *it << " ";
        ++it;
    }       
    cout << endl;

    // C++11范围for的方式遍历
    for (auto& e : l5)
        cout << e << " ";

    cout << endl;
}

✅list iterator的使用

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

在这里插入图片描述

// list迭代器的使用
// 注意:遍历链表只能用迭代器和范围for
void PrintList(const list<int>& l)
{
    // 注意这里调用的是list的 begin() const,返回list的const_iterator对象
    for (list<int>::const_iterator it = l.begin(); it != l.end(); ++it)
    {
        cout << *it << " ";
        // *it = 10; 编译不通过
    }

    cout << endl;
}

void TestList2()
{
    int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
    list<int> l(array, array + sizeof(array) / sizeof(array[0]));
    // 使用正向迭代器正向list中的元素
    // list<int>::iterator it = l.begin();   // C++98中语法
    auto it = l.begin();                     // C++11之后推荐写法
    while (it != l.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;

    // 使用反向迭代器逆向打印list中的元素
    // list<int>::reverse_iterator rit = l.rbegin();
    auto rit = l.rbegin();
    while (rit != l.rend())
    {
        cout << *rit << " ";
        ++rit;
    }
    cout << endl;
}

注意

  1. begin与end为正向迭代器,对迭代器执行++操作,迭代器向后移动。
  2. rbegin(end)与rend(begin)为反向迭代器,对迭代器执行++操作,迭代器向前移动。

✅list capacity

在这里插入图片描述

✅list element access

在这里插入图片描述

✅list modifiers

在这里插入图片描述

// list插入和删除
// push_back/pop_back/push_front/pop_front
void TestList3()
{
    int array[] = { 1, 2, 3 };
    list<int> L(array, array + sizeof(array) / sizeof(array[0]));

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

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

// insert /erase 
void TestList4()
{
    int array1[] = { 1, 2, 3 };
    list<int> L(array1, array1 + sizeof(array1) / sizeof(array1[0]));

    // 获取链表中第二个节点
    auto pos = ++L.begin();
    cout << *pos << endl;

    // 在pos前插入值为4的元素
    L.insert(pos, 4);
    PrintList(L);

    // 在pos前插入5个值为5的元素
    L.insert(pos, 5, 5);
    PrintList(L);

    // 在pos前插入[v.begin(), v.end)区间中的元素
    vector<int> v{ 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/clear
void TestList5()
{
    // 用数组来构造list
    int array1[] = { 1, 2, 3 };
    list<int> l1(array1, array1 + sizeof(array1) / sizeof(array1[0]));
    PrintList(l1);

    // 交换l1和l2中的元素
    list<int> l2;
    l1.swap(l2);
    PrintList(l1);
    PrintList(l2);

    // 将l2中的元素清空
    l2.clear();
    cout << l2.size() << endl;
}

list中还有一些操作,需要用到时大家可参阅list的文档说明。

✅list的迭代器失效问题

前面说过,此处大家可将迭代器暂时理解成类似于指针,迭代器失效即迭代器所指向的节点的无效,即该节点被删除了。因为list的底层结构为带头结点的双向循环链表,因此在list中进行插入时是不会导致list的迭代器失效的,只有在删除时才会失效,并且失效的只是指向被删除节点的迭代器,其他迭代器不会受到影响。

void TestListIterator1()
{
	int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
	list<int> l(array, array+sizeof(array)/sizeof(array[0]));
	auto it = l.begin();
	while (it != l.end())
	{
		// erase()函数执行后,it所指向的节点已被删除,因此it无效,在下一次使用it时,必须先给其赋值
		l.erase(it); 
		++it;
	}
}

// 改正
void TestListIterator()
{
	int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
	list<int> l(array, array+sizeof(array)/sizeof(array[0]));
	auto it = l.begin();
	while (it != l.end())
	{
		it = l.erase(it);
	}
}

🧑‍🎓list与vector的对比

 

  • 底层结构:
    ⭐ list是一个双向链表。它的每个元素都知道其前一个和后一个元素。
    ⭐ vector是一个动态数组。元素是连续存储的,且支持随机访问。

  • 迭代器:
    ⭐ list的迭代器是双向的,不支持随机访问,即不能使用加减法移动迭代器。
    ⭐ vector的迭代器支持随机访问,可以使用加减法来移动迭代器。

  • 插入和删除效率:
    ⭐ 在list的中间插入和删除元素是非常快的,因为只需要更改一些指针。时间复杂度为O(1)。
    ⭐ 在vector中插入或删除元素可能需要移动其他元素来填补空间,尤其是当元素数量接近其容量时。时间复杂度可能高达O(n)。

  • 内存分配和扩展:
    ⭐ 当vector的当前容量不足以存储更多元素时,它会重新分配更大的内存空间,并复制原有元素到新空间,这可能导致大量的CPU和内存开销。
    ⭐ list则不会有此问题,因为它通过链表的方式存储,只需为新增元素分配内存,不需要为所有元素重新分配。

  • 空间和时间权衡:
    ⭐ vector的空间利用率较高,因为它连续存储元素,但插入和删除操作的时间复杂度可能较高。
    ⭐ list的空间利用率较低,因为每个元素除了数据外还需要存储前后指针,但其插入和删除操作的时间复杂度低。

  • 选择考虑:
    ⭐ 如果你需要频繁地在序列中间进行插入和删除操作,且不需要随机访问,那么list可能是更好的选择。
    ⭐ 如果你需要随机访问元素,且不会有大量的中间插入和删除操作,那么vector可能更合适。

总的来说,list和vector各有优缺点,选择哪个容器取决于你的特定需求和优化目标。


🏆写在最后

💝本章主要是给大家介绍list~ 在C++中,list是一个非常重要的数据结构。它具有双向性, 动态性, 内存效率, 插入和删除效率高等优点。它是一种通用的、可扩展的容器,适用于各种不同的编程场景。学习和掌握list的使用对于编写高效的C++程序非常重要。因此,大家可要好好噢~😊


❤️‍🔥后续将会继续输出有关C++的文章,你们的支持就是我写作的最大动力!

感谢阅读本小白的博客,错误的地方请严厉指出噢~


请添加图片描述


本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/184487.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

基于opencv+ImageAI+tensorflow的智能动漫人物识别系统——深度学习算法应用(含python、JS、模型源码)+数据集(一)

目录 前言总体设计系统整体结构图系统流程图 运行环境爬虫1.安装Anaconda2.安装Python3.63.更换pip源4.安装Python包5.下载phantomjs 模型训练1.安装依赖2.安装lmageAl 实际应用1.前端2.安装Flask3.安装Nginx 相关其它博客工程源代码下载其它资料下载 前言 本项目通过爬虫技术…

JVM-基础

jdk7及以前&#xff1a; 通过-XX:PermSize 来设置永久代初始分配空间&#xff0c;默认值是20.75m -XX:MaxPermSize来设定永久代最大可分配空间&#xff0c;32位是64m&#xff0c;64位是82m jdk8及之后&#xff1a; 通过-XX:MetaspaceSize 来设置永久代初始分配空间&#xff…

Linux python安装 虚拟环境 virtualenv

根目录创建 venvs 文件夹 sudo mkdir /venvs 进入 /venvs 目录 cd /venvsp 创建虚拟环境&#xff0c;前提要按照 python3 安装 的 命令 sudo apt install python3 sudo python3 -m venv 虚拟环境名 激活虚拟环境 source /venvs/zen-venv/bin/activate 安装flask pip install fl…

小程序中的大道理之二--抽象与封装

继续扒 接着 上一篇 的叙述, 健壮性也有了, 现在是时候处理点实际的东西了, 但我们依然不会一步到底, 让我们来看看. 一而再地抽象(Abstraction Again) 让我们继续无视那些空格以及星号等细节, 我们看到什么呢? 我们只看到一整行的内容, 当传入 3 时就有 3 行, 传入 4 时就…

2023-11-24 事业-代号s-行业数据研报网站-记录

摘要&#xff1a; 2023-11-24 事业-代号s-行业数据研报网站-记录 行业数据研报网站 1、萝卜投研&#xff1a;https://robo.datayes.com 看数据、下载研报、上市公司PE/PB研究等。2、镝数聚&#xff1a;www.dydata.io 全行业数据&报告查找下载平台&#xff0c;覆盖100行业报…

关于python 语音转字幕,字幕转语音大杂烩

文字转语音 Python语音合成之第三方库gTTs/pyttsx3/speech横评(内附使用方法)_python_脚本之家 代码示例 from gtts import gTTStts gTTS(你好你在哪儿&#xff01;,langzh-CN)tts.save(hello.mp3)import pyttsx3engine pyttsx3.init() #创建对象"""语速"…

Unity使用DOTween实现分段进度条

文章目录 需求下载安装 DOTween实现实现效果 需求 用组件进度条&#xff08;Slider&#xff09;&#xff0c;利用分段加载进行以假乱真的进度效果&#xff0c;比如说2秒钟到达20%的进度&#xff0c;10秒钟加载20%到50%进度&#xff0c;1分钟加载50%到90%的进度&#xff0c;30秒…

JMeter测试报错422 Unprocessable Entity

添加HTTP信息头&#xff1a; ​ HTTP请求-》添加-〉配置元件-》HTTP信息头管理器 ​ 如果需要送json&#xff0c;需要添加Content-Type:application/json&#xff0c;否则会报【422 Unprocessable Entity】

基于单片机的光伏发电并网系统设计(论文+源码)

1.系统设计 片作为主控制器。由于太阳能板本身的能量输出受到负载影响&#xff0c;因此需要在太阳能板后面加入一级DC/DC电路&#xff0c;来实现最大功率跟踪&#xff0c;以提高整个系统的效率。接着&#xff0c;由于光伏逆变器需要产生220V的交流电给居民使用&#xff0c;因此…

win10 eclipse安装教程 (java)

前言&#xff1a;安装eclipse之前必须安装JDK&#xff0c;JDK是编译环境&#xff0c;eclipse是集成开发平台。 一、JDK的安装 Java Development Kit 简称 JDK (一) 官方下载地址&#xff1a; Java Archive Downloads - Java SE 8u211 and later (oracle.com) 找到&#xff…

麒麟KYSEC使用方法04-开启及关闭fpro

原文链接&#xff1a;麒麟KYSEC使用方法04-开启及关闭fpro hello&#xff0c;大家好啊&#xff0c;今天给大家带来麒麟KYLINOS的kysec使用方法系列文章第四篇内容----使用命令开启及关闭fpro&#xff0c;文件保护策略有两种模式&#xff0c;off/on&#xff0c;今天给大家介绍一…

JSP EL 算数运算符逻辑运算符

除了 empty 我们这边还有一些基本的运算符 第一种 等等于 jsp代码如下 <% page contentType"text/html; charsetUTF-8" pageEncoding"UTF-8" %> <%request.setCharacterEncoding("UTF-8");%> <!DOCTYPE html> <html> …

多线程Thread(初阶二:Thread类及常⻅⽅法)

目录 一、Thread 的常⻅构造⽅法 继承Thread代码&#xff1a; 实现Runnable接口代码: 二、Thread 的⼏个常⻅属性 1、id&#xff1a; 2、获取线程的名字。 3、进程的状态&#xff1a; 4、在java中设置的优先级&#xff0c; 5、是否后台线程&#xff0c; 6、是否存活&a…

OpenAI惊天100小时,事件全记录

以下内容为结合这次OpenAI事件经过所做的梳理和总结&#xff0c;里面包含各种八卦和谣言&#xff0c;也是此次事件的狼人杀同人传记&#xff0c;借用了狼人杀游戏中的各种桥段&#xff0c;请各位看官酌情服用。 剧中人物&#xff1a; 好人阵营&#xff08;Sam&Greg&#xf…

【深度学习】基于深度学习的超分辨率图像技术一览

超分辨率(Super-Resolution)即通过硬件或软件的方法提高原有图像的分辨率&#xff0c;图像超分辨率是计算机视觉和图像处理领域一个非常重要的研究问题&#xff0c;在医疗图像分析、生物特征识别、视频监控与安全等实际场景中有着广泛的应用。 SR取得了显著进步。一般可以将现有…

在自己的项目中调用别人的库的方法(static lib库,dynamic lib库以及dll动态库)

众所周知&#xff0c;出现.lib, .dll这种文件的原因是为了保护源代码&#xff0c;这个就不细说了。 用OpenCV的开源库来举个例子看一下就知道了&#xff1a; bin文件夹里面放的都是dll文件&#xff1b; lib文件夹里面放的都是伴随dll文件的动态lib文件&#xff1b; staticli…

20231124给RK3399的挖掘机开发板在Andorid10下加鼠标右键返回

20231124给RK3399的挖掘机开发板在Andorid10下加鼠标右键返回 2023/11/24 12:19 百度&#xff1a;RK3399 Android10 右键返回 https://blog.csdn.net/danhu/article/details/122467256 android9/android10 鼠标右键返回(已验证) danhu 于 2022-01-13 09:46:42 发布 android10 …

Django JSONField/HStoreField SQL注入漏洞(CVE-2019-14234)

漏洞描述 Django 于2019年8月1日 日发布了安全更新&#xff0c;修复了 JSONField 和 HStoreField 两个模型字段的 SQL 注入漏洞。 参考链接&#xff1a; Django security releases issued: 2.2.4, 2.1.11 and 1.11.23 | Weblog | DjangoDjango JSONField SQL注入漏洞&#x…

【Git】一文教你学会 submodule 的增、查、改、删

添加子模块 $ git submodule add <url> <path>url 为想要添加的子模块路径path 为子模块存放的本地路径 示例&#xff0c;添加 r-tinymaix 为子模块到主仓库 ./sdk/packages/online-packages/r-tinymaix 路径下&#xff0c;命令如下所示&#xff1a; $ git subm…

让工作效率提升10倍:十大AIGC工具评测【建议收藏】

AI技术的普及已经在近年来不断增长。这种技术已经改变了我们与电脑的互动方式&#xff0c;让我们能够更高效、更自然地完成任务。本文将展示10个基于ChatGPT、GPT-3.5和 GPT-4.0 AI模型构建的最强大的资源&#xff0c;使您更容易充分利用它们的潜力。因此&#xff0c;如果您想利…