深入解析C++ STL List:双向链表的特性与高级操作
一、引言
在C++ STL容器家族中,list
作为双向链表容器,具有独特的性能特征。本文将通过完整代码示例,深入剖析链表的核心操作,揭示其底层实现机制,并对比其他容器的适用场景。文章包含4000余字详细解析,适合需要高效数据操作的开发者阅读。
https://example.com/list-structure.png
二、环境准备
- 编译器:支持C++11及以上标准
- 开发环境:Visual Studio/CLion/Code::Blocks
- 关键头文件:
#include <list>
- 命名空间:
using namespace std;
三、完整代码示例
cpp
#include <iostream>
#include <list>
using namespace std;#define arr_size 10int main() {list<int> arr;for (int i = 0; i < arr_size; i++) {arr.push_back(i + 1);}list<int> mine_arr = { 1, 4, 6, 7 };arr.push_back(11); // 链表末尾添加值11arr.push_front(0); // 链表头部添加值0int size = arr.size(); // 链表的元素个数auto it = arr.begin();arr.insert(it, -1); // 在链表的指定位置插入值arr.pop_back(); // 删除链表尾部的值arr.pop_front(); // 删除链表头部的值it = arr.begin(); // 重新获取迭代器arr.erase(it); // 删除链表指定位置的元素bool if_not = arr.empty(); // 链表判空操作,若为空则返回truearr.sort(); // 按字典序排序链表中的元素arr.merge(mine_arr); // 合并 mine_arr 到 arr// 遍历链表并输出for (auto it = arr.begin(); it != arr.end(); ++it) {cout << *it << " ";}cout << endl;return 0;
}
四、核心操作解析
4.1 容器初始化
cpp
list<int> arr; // 创建空双向链表
for (int i=0; i<arr_size; i++) {arr.push_back(i+1); // 尾部插入元素1~10
}
链表特性:
- 每个节点包含前驱/后继指针
- 内存非连续分配,插入删除无需内存迁移
- 初始化状态:
[1,2,3,4,5,6,7,8,9,10]
4.2 元素操作对比
操作 | vector时间复杂度 | list时间复杂度 | 特点说明 |
---|---|---|---|
push_back | O(1)摊销 | O(1) | 尾部插入高效 |
push_front | O(n) | O(1) | 头部插入无需元素移动 |
insert | O(n) | O(1) | 指定位置插入常数时间 |
erase | O(n) | O(1) | 删除元素不引起内存拷贝 |
4.3 关键操作详解
cpp
arr.push_back(11); // 尾部添加11 → [1,2,...,10,11]
arr.push_front(0); // 头部插入0 → [0,1,2,...,11]auto it = arr.begin();
arr.insert(it, -1); // 在首元素前插入-1 → [-1,0,1,...,11]arr.pop_back(); // 删除尾部11 → [-1,0,1,...,10]
arr.pop_front(); // 删除头部-1 → [0,1,2,...,10]it = arr.begin();
arr.erase(it); // 删除首元素0 → [1,2,3,...,10]
迭代器特性:
- 插入/删除操作不会使其他迭代器失效(被删除元素的迭代器除外)
erase()
返回下一个有效迭代器
五、高级操作实践
5.1 排序与合并
cpp
arr.sort(); // 原地排序 → [1,2,3,...,10]
arr.merge(mine_arr); // 合并有序链表 → [1,1,2,3,4,4,6,7,10]
合并特性:
- 要求两个链表都已排序
- 合并后mine_arr变为空链表
- 时间复杂度O(n+m)
5.2 splice高效转移
cpp
list<int> temp = {100, 200};
arr.splice(arr.begin(), temp); // 转移temp所有元素到arr头部
优势:
- 零拷贝操作,时间复杂度O(1)
- 不会影响原容器迭代器
六、迭代器深度剖析
6.1 迭代器类型
cpp
auto it = arr.begin(); // 双向迭代器(支持++/--)
auto rend = arr.rend(); // 反向迭代器(指向尾部之前的元素)
操作支持:
++
/--
前进/后退*
解引用==
/!=
比较
6.2 迭代器失效场景
cpp
// 正确操作
auto it = arr.insert(arr.begin(), 99);
arr.erase(it); // 直接删除插入的元素// 危险操作
auto it = arr.begin();
arr.push_front(88);
arr.erase(it); // 未定义行为(迭代器可能失效)
安全准则:
- 插入操作不会使现有迭代器失效
- 删除操作会使被删元素的迭代器失效
七、性能优化策略
7.1 预分配节点空间
cpp
list<int> arr;
arr.reserve(arr_size); // 预分配节点(非容量概念)
实现原理:
- 提前分配节点内存池
- 减少动态内存分配次数
7.2 splice代替拷贝
cpp
list<int> source = {1,2,3};
list<int> target;
target.splice(target.end(), source); // 转移元素而非复制
性能对比:
- splice:O(1)时间,零拷贝
- insert:O(n)时间,需复制元素
八、常见陷阱与解决方案
8.1 合并后的容器状态
cpp
list<int> a = {1,2}, b = {3,4};
a.merge(b); // a变为[1,2,3,4],b变为空
注意:合并后原容器需要重新初始化
8.2 迭代器跨越end()
cpp
auto it = arr.end();
--it; // 合法,指向最后一个元素
++it; // 合法,回到end()
危险操作:
cpp
++(--arr.end()); // 可能越界
九、与其他容器的对比
特性 | list | vector | deque |
---|---|---|---|
内存布局 | 非连续 | 连续 | 分段连续 |
头部插入/删除 | O(1) | O(n) | O(1) |
随机访问 | 不支持 | O(1) | O(1) |
迭代器失效 | 仅被删元素 | 批量失效 | 批量失效 |
适用场景 | 频繁插入删除 | 随机访问需求 | 头尾高效操作 |
十、实战应用场景
- 任务调度器:频繁的添加/删除任务场景
- 撤销重做实现:需要维护操作历史记录
- 内存池管理:高效管理非连续内存块
- 大数据排序:外部排序的分块处理
十一、总结与展望
本文通过完整代码示例,系统讲解了list的核心特性:
- 双向链表结构带来的高效插入删除
- 迭代器的稳定性优势
- 与其他容器的适用场景对比
选择建议:
- 需要频繁在两端操作 → 优先考虑deque
- 需要随机访问 → 选择vector
- 需要大量中间插入删除 → list是最佳选择
扩展学习:
- 研究list的底层节点分配策略
- 实现自定义的链表容器
- 对比不同STL容器的迭代器实现
相关文章:
深入解析C++ STL List:双向链表的特性与高级操作
一、引言 在C STL容器家族中,list作为双向链表容器,具有独特的性能特征。本文将通过完整代码示例,深入剖析链表的核心操作,揭示其底层实现机制,并对比其他容器的适用场景。文章包含4000余字详细解析,适合需…...
在 master 分支上进行了 commit 但还没有 push,怎么安全地切到新分支并保留这些更改
确保你的 commit 确实没有 push(否则会覆盖远程分支): git log --oneline # 查看本地 commit git log --oneline origin/master # 查看远程 master 的 commit 确保你的 commit 只存在于本地,远程 origin/master 没有…...
spark jar依赖顺序
1. 执行顺序 spark-submit --config "spark.{driver/executor}.extraClassPathsomeJar"提交的依赖包SystemClasspath – Spark安装时候提供的依赖包spark-submit --jars 提交的依赖包 2. 依赖解释 提交任务时指定的依赖 Spark-submit --config "spark.{drive…...
docker 国内源和常用命令
Ubuntu | Docker Docs 参考docker官方安装docker # Add Dockers official GPG key: sudo apt-get update sudo apt-get install ca-certificates curl sudo install -m 0755 -d /etc/apt/keyrings sudo curl -fsSL https://download.docker.com/linux/ubuntu/gpg -o /etc/apt…...
【目标检测】对YOLO系列发展的简单理解
目录 1.YOLOv12.YOLOv23.YOLOv34.YOLOv45.YOLOv66.YOLOv77.YOLOv9 YOLO系列文章汇总: 【论文#目标检测】You Only Look Once: Unified, Real-Time Object Detection 【论文#目标检测】YOLO9000: Better, Faster, Stronger 【论文#目标检测】YOLOv3: An Incremental …...
C# AppContext.BaseDirectory 应用程序的启动目录
Application.StartupPath定义与用途局限性示例 Path.GetDirectoryName(Assembly.GetExecutingAssembly().Location)定义与用途局限性示例 Directory.GetCurrentDirectory()定义与用途局限性示例 关键区别总结推荐使用场景需要应用程序安装目录需要动态工作目录插件或模块化应用…...
Sentinel数据S2_SR_HARMONIZED连续云掩膜+中位数合成
在GEE中实现时,发现简单的QA60是无法去云的,最近S2地表反射率数据集又进行了更新,原有的属性集也进行了变化,现在的SR数据集名称是“S2_SR_HARMONIZED”。那么: 要想得到研究区无云的图像,可以参考执行以下…...
探索Cangjie Magic:仓颉编程语言原生的LLM Agent开发新范式
引言:智能体开发的革命性突破 2025年3月,仓颉社区开源了Cangjie Magic——这是首个基于仓颉编程语言原生构建的LLM Agent开发平台,标志着智能体开发领域的一次重大突破。作为一名长期关注AI发展的技术爱好者,我有幸第一时间体验了…...
css三大特性
css三大特性:层叠性 继承性 优先性 一.层叠性 二.继承性 子标签会继承父标签的某些样式 恰当地使用继承性,减少代码复杂性子元素会继承父元素地某些样式(text-,font-,line-这些元素开头的可以继承,以及color属性) 2…...
Centos7安装Jenkins(图文教程)
本章教程,主要记录在centos7安装部署Jenkins 的详细过程。 [root@localhost ~]# cat /etc/redhat-release CentOS Linux release 7.9.2009 (Core) 一、基础环境安装 内存大小要求:256 MB 内存以上 硬盘大小要求:10 GB 及以上 安装基础java环境:Java 17 ( JRE 或者 JDK 都可…...
Hyper-V 管理工具
什么是 Hyper-V Microsoft Hyper-V是一个虚拟化平台,可在Windows客户端和服务器上创建并运行虚拟计算机。操作系统(OS)被称为“监管程序”(supervisor),因为它负责为程序分配物理资源。在虚拟环境中&#…...
小雨滴的奇妙旅行
以下是基于原稿的优化版本,在保留童趣的基础上,进一步贴近5岁孩子的语言习惯和表演需求。修改处用(优化)标注,供参考: 《小雨滴的奇妙旅行》(优化标题,更易记忆) “滴答…...
极狐GitLab 权限和角色如何设置?
极狐GitLab 是 GitLab 在中国的发行版,关于中文参考文档和资料有: 极狐GitLab 中文文档极狐GitLab 中文论坛极狐GitLab 官网 权限和角色 (BASIC ALL) 将用户添加到项目或群组时,您可以为他们分配角色。该角色决定他们在极狐GitLab 中可以执…...
NLP高频面试题(五十一)——LSTM详解
长短期记忆网络(LSTM)相较于传统循环神经网络(RNN)的核心改进在于通过引入记忆单元(cell state)和门机制(gating mechanism)来有效缓解梯度消失与梯度爆炸问题,从而更好地捕捉长距离依赖关系 。在其网络结构中,信息通过输入门(input gate)、遗忘门(forget gate)和…...
C++学习之游戏服务器开发十二nginx和http
目录 1.容器运行游戏需求分析 2.静态编译游戏服务 3.手动创建游戏镜像 4.编写游戏启动脚本 5.脚本创建游戏服务器镜像 6.登录服务器架构选择 7.http协议初识 8.http报文分析 9.nginx简介和安装 10.nginx配置静态页面 11.nginx配置反向代理 1.容器运行游戏需求分析 2.…...
Spark集群搭建-spark-local
(一)安装Spark 安装Spark的过程就是下载和解压的过程。接下来的操作,我们把它上传到集群中的节点,并解压运行。 1.启动虚拟机 2.通过finalshell连接虚拟机,并上传安装文件到 /opt/software下 3.解压spark安装文件到/op…...
突破 RAG 检索瓶颈:Trae+MCP 构建高精度知识库检索系统实践
一、引言:RAG 技术的落地困境与破局思路 在企业级 AI 应用中,基于检索增强生成(RAG)的知识库系统已成为构建智能问答、文档分析的核心方案。然而随着实践深入,从业者逐渐发现传统 RAG 架构存在三大典型痛点࿱…...
PyQt5、NumPy、Pandas 及 ModelArts 综合笔记
PyQt5、NumPy、Pandas 及 ModelArts 综合笔记 PyQt5 GUI 开发 信号与槽 概念:对象间解耦通信机制。 信号:对象状态改变时发射,例如 btn.clicked。槽:接收信号的普通函数或方法。 连接:signal.connect(slot)ÿ…...
TM2SP-Net阅读
TCSVT 2025 创新点 结合图像显著性和视频时空特征进行视频显著性预测。 提出一个多尺度时空特征金字塔(MLSTFPN),能够更好的融合不同级别的特征,解决了显著性检测在多尺度时空特征表示的不足。 对比MLSTFPN和普通的FPN和BiFPN的区别。 Pipeline 时空语义信息和图…...
C++ 拷贝构造函数 浅拷贝 深拷贝
C 的拷贝构造函数(Copy Constructor)是一种特殊的构造函数,用于通过已有对象初始化新创建的对象。它在对象复制场景中起关键作用,尤其在涉及动态内存管理时需特别注意深浅拷贝问题。 一、定义与语法 拷贝构造函数的参数…...
Linux系统用户迁移到其它盘方法
步骤 1:创建脚本文件 使用文本编辑器(如 nano 或 vim)创建脚本文件,例如 migrate_users.sh: sudo nano /root/migrate_users.sh 脚本代码如下: #!/bin/bash # 迁移用户主目录到 /mnt/sdb1 的批量脚本# 用…...
NDSS 2025|侧信道与可信计算攻击技术导读(二)系统化评估新旧缓存侧信道攻击技术
本文为 NDSS 2025 导读系列 之一,聚焦本届会议中与 硬件安全与侧信道技术 相关的代表性论文。 NDSS(Network and Distributed System Security Symposium) 是网络与系统安全领域的顶级国际会议之一,由 Internet Society 主办&…...
Kafka 面试,java实战贴
面试问题列表 Kafka的ISR机制是什么?如何保证数据一致性? 如何实现Kafka的Exactly-Once语义? Kafka的Rebalance机制可能引发什么问题?如何优化? Kafka的Topic分区数如何合理设置? 如何设计Kafka的高可用跨…...
第十五届蓝桥杯 2024 C/C++组 下一次相遇
目录 题目: 题目描述: 题目链接: 思路: 自己的思路详解: 更好的思路详解: 代码: 自己的思路代码详解: 更好的思路代码详解: 题目: 题目描述…...
2024年全国青少年信息素养大赛-算法创意实践C++ 华中赛区(初赛真题)
完整的试卷可点击下方去查看,可在线考试,在线答题,在线编程: 2024年全国青少年信息素养大赛-算法创意实践C 华中赛区(初赛)_c_少儿编程题库学习中心-嗨信奥https://www.hixinao.com/tidan/cpp/show-96.htm…...
“思考更长时间”而非“模型更大”是提升模型在复杂软件工程任务中表现的有效途径 | 学术研究系列
作者:明巍/临城/水德 还在为部署动辄数百 GB 显存的庞大模型而烦恼吗?还在担心私有代码库的安全和成本问题吗?通义灵码团队最新研究《Thinking Longer, Not Larger: Enhancing Software Engineering Agents via Scaling Test-Time Compute》…...
测试OMS(订单管理系统)时,对Elasticsearch(ES)数据和算法数据进行测试(如何测试几百万条数据)
1. 测试目标 在测试OMS中的ES数据和算法数据时,主要目标包括: 数据完整性 数据完整性:确保所有需要的数据都被正确采集、存储和索引。 数据准确性:确保数据内容正确无误,符合业务逻辑。 性能:确保系统在处…...
Java中链表的深入了解及实现
一、链表 1.链表的概念 1.1链表是⼀种物理存储结构上⾮连续存储结构,数据元素的逻辑顺序是通过链表中的引⽤链接次序实现的 实际中链表的结构⾮常多样,以下情况组合起来就有8种链表结构: 2.链表的实现 1.⽆头单向⾮循环链表实现 链表中的…...
继承相关知识
概念 定义类时,代码中有共性的成员,还有自己的属性,使用继承可以减少重复的代码, 继承的语法 class 子类:继承方式 父类 继承方式有:public,private,protected 公共继承&#x…...
《开源大模型选型全攻略:开启智能应用新征程》
《开源大模型选型全攻略:开启智能应用新征程》 在当今数字化浪潮中,人工智能的发展可谓日新月异,而开源大模型作为其中的关键驱动力,正以惊人的速度改变着各个领域的面貌。从智能客服高效解答客户疑问,到智能写作助力创作者灵感迸发,开源大模型展现出了强大的应用潜力。…...
PyTorch DDP 跨节点通信的底层机制
我们已经知道 torch.nn.parallel.DistributedDataParallel (DDP) 是 PyTorch 中实现高性能分布式训练的利器,它通过高效的梯度同步机制,让多个 GPU 甚至多台机器协同工作,大大加速模型训练。 当我们的训练扩展到多个节点(不同的物…...
Prompt工程:大模型的「精准导航系统」
在Elasticsearch中,DSL通过精确的查询语法帮助开发者从海量数据中定位目标文档;而在大模型应用中,Prompt就是用户的「意图导航仪」,通过结构化的语言模板引导模型生成符合业务需求的答案。两者的核心逻辑相似——通过精准的指令设…...
25.4.22华为--算法真题整理(2025年4月22日)
120.三角形最小路径和(120.三角形最小路径和) 题目分析: 给定一个三角形,用二维列表triangle表示,现在约定:自顶向下移动,每一步只能移动到下一行中相邻的节点上,即当前行的下标为…...
C语言高频面试题——指针函数和函数指针的区别
在 C 语言中,指针函数 和 函数指针 是两个容易混淆的概念,但它们的功能和用途完全不同。以下是详细的对比分析,帮助你彻底理解它们的区别。 1. 指针函数(Function Returning a Pointer) 定义 指针函数 是一个返回值为…...
MQTTClient_message 源码深度解析与架构设计
一、结构体内存布局与版本控制机制 #mermaid-svg-i9W8883mELYm6HUj {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-i9W8883mELYm6HUj .error-icon{fill:#552222;}#mermaid-svg-i9W8883mELYm6HUj .error-text{fill:#…...
4.21—4.22学习总结 JavaWeb:HTML-CSS
Web:能够通过浏览器访问到的网站。 Web标准: HTML: vscode中进行注释的快捷键为ctrl斜线/ h1的字体最大,依次递减,只存在h1—h6。 超链接: 设置字体颜色: 方式三写一个css文件,将方…...
STM32的定时器输出PWM时,死区时间(DTR)如何计算
在 STM32F429(以及所有 STM32F4 “高级定时器”)中,死区时间由 TIMx_BDTR 寄存器的 8 位 “Dead‑Time Generator” 字段 DTG[7:0] 来配置。其计算分三步: 计算死区时钟周期 tDTS TIM1 时钟源为 APB2 定时器时钟(PCL…...
4.LinkedList的模拟实现:
LinkedList的底层是一个不带头的双向链表。 不带头双向链表中的每一个节点有三个域:值域,上一个节点的域,下一个节点的域。 不带头双向链表的实现: public class Mylinkdelist{//定义一个内部类(节点)stat…...
使用PyTorch构建神经网络笔记
专有名词 Batch Size 在深度学习中,批大小(Batch Size) 是指每次前向传播和反向传播时使用的样本数量。它是训练神经网络时的一个关键超参数,直接影响训练速度、内存占用和模型性能。 (1) 计算梯度 在训练时,模型通过…...
麒麟系统网络连接问题排查
麒麟系统网络连接有红色叹号,不能上外网 了。 首先执行 ping -c4 8.8.8.8 和 nc -zv 8.8.8.8 53,如果 都能正常通信,说明你的网络可以访问公共 DNS 服务器(如 Google DNS 8.8.8.8),但域名解析仍然失败,可能是 DNS 解析配置问题 或 系统 DNS 缓存/代理干扰。以下是进一步…...
python高级特性01
装饰器 基本语法 在不改变原函数的基础上,新增/修改一些功能 在被装饰函数/类前使用:decorator_name 装饰器接收一个函数返回一个新函数 def decorator_name(func):# 装饰器的操作...def wrapper(*args, **kwargs):# 前置操作...result func()# 后置…...
shared_ptr八股收集 C++
(1)、具体讲一下shared_ptr自动管理内存的原理/引用计数的具体原理/shared_ptr引用计数什么时候会增加,什么时候会减少? 在shared_ptr的内部维护了⼀个计数器,来跟踪有多少个shared_ptr对象指向了某⼀个资源。当计数器…...
【gpt生成-其二】以go语言为例,详细讲解 并发模型:线程/协程/ Actor 实现
Go语言并发模型详解:线程、协程与Actor实现 1. 线程模型 概念 线程是操作系统调度的最小单位,每个线程拥有独立的栈和寄存器上下文,但共享进程的内存空间。线程的创建、切换和同步需要较高的系统开销。 Go中的实现…...
nodejs创建文件
环境要求:nodejs 运行命令: node createComponent.js各文件内容: createComponent.js /** 功能概述:* 1. 通过命令行交互,用户输入组件名称,选择模板类型。* 2. 根据用户输入生成对应的Vue组件、Service…...
三餐四季、灯火阑珊
2025年4月22日,15~28℃,挺好的 待办: 教学技能大赛教案(2025年4月24日,校赛,小组合作,其他成员给力,暂不影响校赛进度,搁置) 教学技能大赛PPT(202…...
HTTP状态码有哪些常见的类型?
HTTP 状态码用于表示服务器对客户端请求的响应状态,常见的 HTTP 状态码可以分为以下几类: 一、1xx:信息提示 状态码以 1 开头,表示请求已接收,客户端应继续其请求。常见的状态码有: • 100 Continue&…...
01-STM32基本知识点和keil5的安装
一、微控制器: 1、微控制器也被称为MCU(国内称为单片机),微控制器集成了处理器、内存、输入/输出接口等多种功能模块,能够独立完成特定的控制任务。它主要用于对设备或系统的控制和监测,MCU通常是一个高度…...
前端如何优雅地对接后端
作为一名前端开发者,与后端对接是我们日常工作中不可避免的一部分。从API设计的理解到错误处理的优雅实现,前端需要的不只是调用接口的代码,更是一种协作的艺术。本文将从Vue 3项目出发,分享如何与后端高效协作,减少联…...
Centos虚拟机远程连接缓慢
文章目录 Centos虚拟机远程连接缓慢1. 问题:SSH远程连接卡顿现象2. 原因:SSH服务端DNS检测机制3. 解决方案:禁用DNS检测与性能调优3.1 核心修复步骤3.2 辅助优化措施 4. 扩展认识:SSH协议的核心机制4.1 SSH工作原理4.2 关键配置文…...
Centos 、Linux 基础运维命令
查看系统IP ifconfig 巡检常用 显示磁盘空间使用情况 df -h 配置主机名查称看主机名称 hostname 修改主机名称 打开修改的配置文件 vim /etc/sysconfig/network 防火墙 查看防火墙状态 service iptables status 临时关闭防火墙:关机重启后防火墙还会开启 …...