【C++庖丁解牛】List容器的介绍及使用 | 深度剖析 | list与vector的对比

🍁你好，我是 RO-BERRY
📗 致力于C、C++、数据结构、TCP/IP、数据库等等一系列知识
🎄感谢你的陪伴与支持 ，故事既有了开头，就要画上一个完美的句号，让我们一起加油

在这里插入图片描述

目录

  • 1. list的介绍
    • 1.1 list的介绍
    • 1.2 list的存储结构
    • 1.3 list的特点
  • 2. list的使用
    • 2.1 list的构造
    • 2.2 list iterator的使用
    • 2.3 list capacity
    • 2.4 list element access
    • 2.5 list modifiers
    • 2.6 list的迭代器失效
  • 3. list与vector的对比

1. list的介绍

1.1 list的介绍

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

相比于vector的连续线型空间，list显得复杂许多，但是它的好处在于插入或删除都只作用于一个元素空间，因此list对空间的运用是十分精准的，对任何位置元素的插入和删除都是常数时间。list不能保证节点在存储空间中连续存储，也拥有迭代器，迭代器的“++”、“–”操作对于的是指针的操作，list提供的迭代器类型是双向迭代器：Bidirectional iterators。

1.2 list的存储结构

list容器是一种线性的数据结构，它以链表的形式存储元素。每个元素都包含一个值和指向下一个元素的指针。相邻元素通过指针连接在一起，形成一个链表。链表的头部指针指向第一个元素，尾部指针指向最后一个元素或者为空。

list节点的结构见如下源码：

template <class T>
struct __list_node{
    typedef void* void_pointer;
    void_pointer prev;
    void_pointer next;
    T data;
}

从源码可看出list显然是一个双向链表。list与vector的另一个区别是，在插入和接合操作之后，都不会造成原迭代器失效，而vector可能因为空间重新配置导致迭代器失效。

此外list也是一个环形链表，因此只要一个指针便能完整表现整个链表。list中node节点指针始终指向尾端的一个空白节点，因此是一种“前闭后开”的区间结构

list的空间管理默认采用alloc作为空间配置器，为了方便的以节点大小为配置单位，还定义一个list_node_allocator函数可一次性配置多个节点空间

由于list的双向特性，其支持在头部（front)和尾部（back)两个方向进行push和pop操作，当然还支持erase，splice，sort，merge，reverse，sort等操作，这里不再详细阐述

在这里插入图片描述

1.3 list的特点

由于链表的特性，list容器具有以下特点：

  1. 动态内存分配：链表的节点可以在运行时动态分配内存，不需要预先指定容器的大小。
  2. 随机访问效率低：由于链表中的元素不是连续存储的，因此无法通过下标直接访问元素，需要从头部开始遍历链表，直到找到目标元素。
  3. 插入和删除效率高：由于链表的节点可以通过指针进行快速插入和删除操作，不需要移动其他元素。
  4. 不支持随机访问迭代器：list容器的迭代器只支持双向移动，无法像vector容器那样进行随机访问。

总结一下，list容器的存储结构是通过链表实现的，具有动态内存分配、插入和删除效率高等特点。

2. list的使用

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

2.1 list的构造

构造函数（ (constructor)）接口说明
list (size_type n, const value_type& val = value_type())构造的list中包含n个值为val的元素
list()构造空的list
list (const list& x)拷贝构造函数
list (InputIterator first, InputIterator last)用[first, last)区间中的元素构造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;
}

2.2 list iterator的使用

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

函数声明接口说明
begin + end返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器
rbegin + rend返回第一个元素的reverse_iterator,即end位置，返回最后一个元素下一个位置的reverse_iterator,即begin位置

在这里插入图片描述

【注意】

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

代码演示：

// 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;
}

2.3 list capacity

函数声明接口说明
empty检测list是否为空，是返回true，否则返回false
size0返回list中有效节点的个数

2.4 list element access

函数声明接口说明
front返回list的第一个节点中值的引用
back返回list的最后一个节点中值的引用

2.5 list modifiers

函数声明接口说明
push_front在list首元素前插入值为val的元素
pop_front删除list中第一个元素
push_back在list尾部插入值为val的元素
pop_back删除list中最后一个元素
insert在list position 位置中插入值为val的元素
erase删除list position位置的元素
swap交换两个list中的元素
clear清空list中的有效元素

代码演示：

// 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;
}

2.6 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())
	{
		l.erase(it++); // it = l.erase(it);
	}
}

3. list与vector的对比

vector与list都是STL中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及应用场景不同，其主要不同如下：

vectorlist
底层结构动态顺序表，一段连续空间带头结点的双向循环链表
随机访问支持随机访问，访问某个元素效率O(1)不支持随机访问，访问某个元素效率O(N)
插入和删除任意位置插入和删除效率低，需要搬移元素，时间复杂度为O(N)，插入时有可能需要增容，增容：开辟新空间，拷贝元素，释放旧空间，导致效率更低任意位置插入和删除效率高，不需要搬移元素，时间复杂度为O(1)
空间利用率底层为连续空间，不容易造成内存碎片，空间利用率高，缓存利用率高底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低
迭代器原生态指针对原生态指针(节点指针)进行封装
迭代器失效在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能会导致重新扩容，致使原来迭代器失效，删除时，当前迭代器需要重新赋值否则会失效插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响
使用场景需要高效存储，支持随机访问，不关心插入删除效率大量插入和删除操作，不关心随机访问

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

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

相关文章

每周一算法：双向深搜

每周一算法：双向深搜

题目描述 达达帮翰翰给女生送礼物&#xff0c;翰翰一共准备了 N N N 个礼物&#xff0c;其中第 i i i 个礼物的重量是 G [ i ] G[i] G[i]。 达达的力气很大&#xff0c;他一次可以搬动重量之和不超过 W W W的任意多个物品。 达达希望一次搬掉尽量重的一些物品&#xff0c;请…
阅读更多...
冲动是魔鬼，工作不顺心时不要把坏脾气带给家人

冲动是魔鬼，工作不顺心时不要把坏脾气带给家人

今天与一个跟踪了很久的客户准备签合同了&#xff0c;客户突然反悔&#xff0c;为此与他周旋了一整天&#xff0c;忙碌得一口水都没有喝。回到小区坐在车里抽着烟&#xff0c;久久不愿回家&#xff0c;只想一个人坐着&#xff0c;疲惫、无奈。这个月的奖金似乎又将成为泡影。 …
阅读更多...
mov格式视频怎么做二维码？视频在线做二维码的方法

mov格式视频怎么做二维码？视频在线做二维码的方法

如何将mov格式视频转二维码以后分享呢&#xff1f;视频二维码是现在手机获取视频内容很常用的一种方式&#xff0c;通过二维码生成器工具就可以快速在线生成二维码图片&#xff0c;使用手机扫码就可以播放视频。但是视频的格式有很多种&#xff0c;当我们需要将mov格式的视频生…
阅读更多...
网络安全——关于防火墙

网络安全——关于防火墙

网络安全防火墙是很重要的部分&#xff0c;关于防火墙我们要知道&#xff0c;他默认所有流量都是黑名单&#xff0c;只有开启允许通过才可以。 我们通过一个实验来学防火墙命令。 防火墙要登录才能使用&#xff0c;用户名是admin,默认密码是Admin123&#xff0c;在第一次登录…
阅读更多...
Spring AI Chat 简单示例

Spring AI Chat 简单示例

官方文档地址&#xff1a; https://docs.spring.io/spring-ai/reference/index.html Spring AI 可以方便 Java 开发者在代码中集成 AI 的功能&#xff0c;通过 Spring 提供的抽象&#xff0c;可以方便的切换不同的AI提供商&#xff0c;Spring AI 是对 AI 的使用&#xff0c;并…
阅读更多...
Android 地图SDK 绘制点 删除 指定

Android 地图SDK 绘制点 删除 指定

问题 Android 地图SDK 删除指定绘制点 详细问题 笔者进行Android 项目开发&#xff0c;对于已标记的绘制点&#xff0c;提供撤回按钮&#xff0c;即删除绘制点&#xff0c;如何实现。 解决方案 新增绘制点 private List<Marker> markerList new ArrayList<>…
阅读更多...
没有公式，不要代码，让你理解 RCNN：目标检测中的区域卷积神经网络

没有公式，不要代码，让你理解 RCNN：目标检测中的区域卷积神经网络

⭐️ 导言 在计算机视觉领域&#xff0c;目标检测是一项关键任务&#xff0c;它涉及识别图像中感兴趣的物体&#xff0c;并定位它们的位置。而RCNN&#xff08;Region-based Convolutional Neural Network&#xff09;是一种经典的目标检测算法&#xff0c;它以区域为基础进行…
阅读更多...
BMP280 arduino调试

BMP280 arduino调试

终于成功了。 #include <SPI.h> //定义数据类型 #define s32_t long signed int #define u32_t long unsigned int #define u16_t unsigned short #define s16_t signed short // 定义从设备选择引脚 const int chipSelectPin 10; //定义BMP280寄存器/// unsigned int …
阅读更多...
R语言：如何基于地球外辐射(Ra)和相对日照(n/N)计算太阳辐射Rs?

R语言：如何基于地球外辐射(Ra)和相对日照(n/N)计算太阳辐射Rs?

正在编写相关软著&#xff0c;借此机会了解R语言的基本语法和一些处理流程&#xff0c;所以解释稍微繁琐。 Note&#xff1a; 使用的R语言版本是 R version 4.3.2 (2023-10-31 ucrt) 使用的RStudio编辑器版本是&#xff1a; 01 基于随机森林的插值填补缺失值 这是目前处理…
阅读更多...
电子供应链的未来：电子元器件采购商城的洞察

电子供应链的未来：电子元器件采购商城的洞察

电子供应链的未来将受到数字化技术、智能化制造和全球化贸易等趋势的深刻影响。在这一背景下&#xff0c;电子元器件采购商城将发挥越来越重要的作用&#xff0c;并提供以下洞察&#xff1a; 数字化转型&#xff1a; 电子元器件采购商城将更加注重数字化转型&#xff0c;通过引…
阅读更多...
【计算机系统结构】重叠方式

【计算机系统结构】重叠方式

&#x1f4dd;本文介绍 本文主要内容位计算机系统结构的重叠方式 &#x1f44b;作者简介&#xff1a;一个正在积极探索的本科生 &#x1f4f1;联系方式&#xff1a;943641266(QQ) &#x1f6aa;Github地址&#xff1a;https://github.com/sankexilianhua &#x1f511;Gitee地址…
阅读更多...
不可变集合

不可变集合

2. 3. 如果键值对超过10个的话 优化之后 要生成不可变的集合直接使用copyof就可以
阅读更多...
Python XML处理实战指南：从基础到高级技巧

Python XML处理实战指南：从基础到高级技巧

Python XML处理实战指南&#xff1a;从基础到高级技巧 介绍XML基础XML的定义和特点XML结构组成命名空间&#xff08;Namespaces&#xff09;小结 Python中处理XML的库ElementTreeminidomlxml 使用ElementTree解析XML读取XML文件遍历XML元素查找特定元素修改XML文件 使用lxml处理…
阅读更多...
除了「au revoir」，「再见」还能怎么说？柯桥成人学外语来银泰附近

除了「au revoir」，「再见」还能怎么说？柯桥成人学外语来银泰附近

1. Je dois y alle#15857575376r I have to go there Y there&#xff0c;意思是“我要走了”。 例如&#xff0c;”Moi, je dois y aller.” 对不起&#xff0c;我该走了。 如果你和同伴都要离开&#xff0c;那就可以说"On y va"&#xff0c;它相当于英语里…
阅读更多...
C#集合和数据结构，随笔记录

C#集合和数据结构，随笔记录

C#集合和数据结构 System.Collections命名空间包含接口和类&#xff0c;这些接口和类定义各种对象&#xff08;如列表/链表、位数组、哈希表、队列和堆栈&#xff09;的集合 System.Collections.Generic命名空间&#xff1a; 所有集合都直接或间接基于ICollection接口 列表类集…
阅读更多...
Redis数据结构对象(一)

Redis数据结构对象(一)

对象 概述 Redis并没有直接使用简单动态字符串(SDS)、双端链表、字典、压缩列表、整数集合等这些数据结构来实现键值对数据库&#xff0c;而是基于这些数据结构创建了一个对象系统&#xff0c;这个系统包含字符串对象、列表对象、 哈希对象、集合对象和有序集合对象这五种类型…
阅读更多...
Cesium 获取 3dtileset的包围盒各顶点坐标

Cesium 获取 3dtileset的包围盒各顶点坐标

Cesium 获取 3dtileset的包围盒各顶点坐标 /*** 获取 3dtileset的包围盒各顶点坐标, z 方向取高度最低的位置* param {*} tileset* param {*} options* returns* ref https://blog.csdn.net/STANDBYF/article/details/135012273* ref https://community.cesium.com/t/accurate-…
阅读更多...
基于SpringBoot+Vue的IT博客管理系统

基于SpringBoot+Vue的IT博客管理系统

目录 一、绪论1.1 开发背景1.2 系统开发平台1.2.1 Java语言的简介1.2.2 MySQL的简介1.2.3 IntelliJ IDEA的简介 二、需求分析2.1 系统简介2.1.1 系统类型2.1.2 系统用法2.1.3 系统特点 2.2 需求分析2.2.1 系统设计任务2.2.2 系统设计目标2.2.3 系统设计步骤 三、系统设计3.1 用…
阅读更多...
视频素材库大全高清素材必备网站，总有一个值得收藏！

视频素材库大全高清素材必备网站，总有一个值得收藏！

喜欢制作短视频的朋友们&#xff0c;你们是否时常苦于寻找合适的视频素材库大全高清素材必备网站&#xff1f;今天&#xff0c;我为大家整理了五个超棒的短视频素材下载网站&#xff0c;希望能够为你们的视频创作提供更多灵感和选择&#xff01; 1.蛙学网&#xff1a; 蛙学网不…
阅读更多...
qt可以信号触发信号（信号与槽）信号串联

qt可以信号触发信号（信号与槽）信号串联

使用场景&#xff1a;一大堆lineEdit要更新数据上面10几个QLineEdit,z&#xff0c;只要任意改一个数据我都要把所有数据封装成一个包 connect(ui.radar_name_, &QLineEdit::textChanged, ui.antenna_height, &QLineEdit::textChanged); connect(ui.antenna_height, &a…
阅读更多...
最新文章

Copyright @ 2022~2023