【C++】STL学习:list容器的实现原理
一、list的底层结构双向循环链表在C标准库中std::list是一个双向链表容器它采用双向循环链表作为底层数据结构。这种设计使得list在任意位置插入和删除元素的时间复杂度都是O(1)但随机访问的效率较低。1.1 节点结构定义list的底层是一个双向循环链表每个节点通常包含三个部分数据域data)存储元素值前驱指针(prev)指向前一个节点后继指针(next)指向后一个节点在STL实现中节点结构通常定义如下templatetypename T struct list_node { list_node* prev; // 前驱指针 list_node* next; // 后继指针 T data; // 数据域 };1.2 循环链表设计list采用循环链表设计即头节点的prev指向尾节点尾节点的next指向头节点。这种设计简化了边界条件的处理空链表时头节点指向自身插入第一个元素时头尾节点都指向该元素删除最后一个元素时恢复为空链表状态以下是链表节点的实现namespace lx { templateclass T struct list_node { T _data; list_nodeT*_prev; list_nodeT*_next; list_node(const TxT()) :_data(x) ,_prev(nullptr) ,_next(nullptr) {} }; }二、list的核心接口实现2.1 构造函数list提供了多种构造函数包括默认构造、拷贝构造、范围构造等list() //默认构造 { _head new node; _head-_prev_head; _head-_next_head; } list(const listTlt) //拷贝构造 { _head new node; _head-_prev_head; _head-_next_head; for(auto e: lt) { push_back(e); } }2.2 insertpush_backlist的插入操作是其核心优势时间复杂度为O(1)// 在指定位置前插入元素 iterator insert(iterator pos, const T x) { Node *curpos.node; Node *prevcur-_prev; newnode new Node(x); prev-_next newnode; //prev newnode pos newnode-_nextcur; cur-_prevnewnode; newnode-_prevprev; } // push_back实现 void push_back(const T x) { insert(end(),x); } // push_front实现 void push_front(const T x) { insert(begin(),x); }2.3 erasepop_back删除操作同样高效时间复杂度为O(1)// 删除指定位置的元素 iterator erase(iterator pos) { NodeT* curpos.node; NodeT* prevcur-_prev; //prev pos next NodeT* nextcur-_next; prev-_nextnext; next-_prevprev; delete cur; return iterator(next); } // pop_back实现 void pop_back() { if (!empty()) { erase(--end()); } } // pop_front实现 void pop_front() { if (!empty()) { erase(begin()); } }2.4 clearclear函数用于清空list中的有效元素void clear() { iterator it begin(); while(it!end()) { iterase(it); } }三、迭代器设计3.1 普通迭代器list的迭代器是双向迭代器支持前向和后向移动templateclass T,class Ref struct list_iterator { using Self list_iteratorT,Ref; using Nodelist_nodeT; Node*_node; list_iterator(Node*node) :_node(node) {} Ref operator*() { return _node-_data; } Selfoperator() { _node_node-_next; return *this; } Selfoperator(int) { Self tmp(*this); _node_node-_next; return tmp; } Selfoperator--() { _node_node-_prev; return *this; } Selfoperator--(int) { Self tmp(*this); _node_node-_prev; return tmp; } bool operator!(const Selfs)const { return _node!s._node; } bool operator(const Selfs)const { return _nodes._node; } };3.2 const迭代器const迭代器是容器内部定义的只读迭代器本质是一个“指向常量的指针”可以移动它但不能通过它修改所指向的元素。templateclass T,class Ref struct __list_iterator { typedef list_nodeT Node; Node*_node; typedef __list_iteratorT,Ref self; __list_iterator(Node*_node); : _node(node) {} const self operator*() { return _node-_data; } self operator() { _node_node-_next; return *this; } selfoperator(int) { self tmp(*this); _node _node-_next; return tmp; } selfoperator--() { _node_node-_prev; return *this; } Self operator--(int) { Self tmp(*this);//浅拷贝 _node _node-prev; return *this; } bool operator!(const Self it)const { return _node ! it._node; } bool operator(const Self it)const { return _node it._node; } };3.3 迭代器失效问题list的迭代器在以下情况下不会失效插入元素所有迭代器保持有效删除元素只有指向被删除元素的迭代器失效其他迭代器保持有效这是list相对于vector和deque的一个重要优势。四、list的优缺点总结6.1 优点高效的插入删除任意位置O(1)时间复杂度迭代器稳定性插入删除不会使其他迭代器失效动态大小不需要预分配内存支持双向遍历可以从前往后或从后往前遍历6.2 缺点随机访问慢需要遍历时间复杂度O(n)内存开销大每个元素需要额外存储两个指针缓存不友好节点分散在内存中缓存命中率低空间局部性差连续访问性能不如vector6.3 适用场景1.需要频繁在中间位置插入删除元素的场景2.元素大小较大移动成本高的场景3.需要稳定迭代器的场景4.不需要随机访问的场景五、与vector和deque的对比特性listvectordeque底层结构双向链表动态数组分段数组随机访问O(n)O(1)O(1)头部插入O(1)O(n)O(1)中间插入O(1)O(n)O(n)尾部插入O(1)O(1)平摊O(1)内存连续性否是部分连续迭代器失效插入不失效删除仅当前失效插入删除可能全部失效中间插入删除可能失效

相关新闻

农田上空的“智慧天眼”:多光谱视觉系统在作物生长监测与病虫害大范围筛查中的落地方案

农田上空的“智慧天眼”:多光谱视觉系统在作物生长监测与病虫害大范围筛查中的落地方案

在现代智慧农业向数字化、精准化和智能化跨越式跃升的进程中,大范围农作物的精细化健康监测与早期病虫害防御已成为保障国家粮食安全和推动农业产业升级的核心驱动。传统农业巡检主要依赖人工步巡,面对成千上万亩的农田,不仅耗费巨大人力&…

2026/11/18 10:31:00 阅读更多 →
前端内存泄漏实战指南:闭包、事件监听与GC原理

前端内存泄漏实战指南:闭包、事件监听与GC原理

1. 这不是玄学,是能被观测、被定位、被修复的工程问题“内存泄漏”在前端圈子里常被说得神乎其神——面试官一问,候选人立刻背诵“闭包导致引用无法释放”;线上监控报警一响,团队第一反应是“赶紧重启服务”;开发中页面…

2026/11/18 10:31:10 阅读更多 →
Dart/Flutter 项目交付新助手:Skills CLI 将默契变为门禁

Dart/Flutter 项目交付新助手:Skills CLI 将默契变为门禁

最近两周我把自己手头一个 Flutter 项目里重复了无数遍的“交付前琐事”抽出来,做成了一个小工具,叫 Dart Skills CLI 1.0。做它的原因很简单:AI 写代码确实越来越快,但交付一个能跑的 Dart 项目,从来不是把代码堆完就…

2026/11/18 10:31:09 阅读更多 →

最新新闻

Electron桌面应用开发实战:从环境搭建到打包发布全流程

Electron桌面应用开发实战:从环境搭建到打包发布全流程

做前端这些年,我大部分时间都在跟浏览器标签页打交道,直到第一次把桌面应用跑起来,才发现原来自己一直被限制在地址栏和刷新按钮围起来的框框里。Electron这个词,最开始是在某段时间频繁出现在同事的讨论里,一个用HTML…

2026/11/19 21:38:27 阅读更多 →
滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

简介:亚太天能T109滑盖智能锁产品说明书是一份PDF格式的官方技术文档,主要面向智能锁安装人员、终端用户及售后维护者,帮助快速掌握产品安装、配置与常见故障处理。全包仅1个PDF文件,大小4.37MB,内容结构清晰&#xff…

2026/11/19 21:38:49 阅读更多 →
PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

上个月我在调试一台高速AGV的驱动系统,整车要求空载跑到8m/s,电机转速已经拉到额定点,驱动器的输出电压也顶到了母线电压极限附近。再往上踩速度指令,转速纹丝不动,三相电流反而开始震荡。那会儿我的第一反应就是&…

2026/11/19 21:39:09 阅读更多 →
C++核心知识点:从内存管理到STL的实战指南

C++核心知识点:从内存管理到STL的实战指南

C 这门语言我前前后后折腾了十几年,用它写过嵌入式驱动、做过游戏服务端,也搭过基础组件库。每次看到新人一头扎进"C 核心知识点"这个搜索词,我其实挺感慨的——这门语言的难点从来不是语法多,而是知识点之间的耦合太深…

2026/11/19 21:36:50 阅读更多 →
T109滑盖智能锁怎么装?安装调试与故障排查全攻略

T109滑盖智能锁怎么装?安装调试与故障排查全攻略

简介:亚太天能T109滑盖智能锁产品说明书以PDF格式发布,适合智能锁用户、安装人员与售后维修人员阅读。内容围绕T109系列指纹密码刷卡锁展开,先介绍前面板、后面板、锁体、机械钥匙、电池盒盖等部件名称与功能,再给出完整安装步骤&…

2026/11/19 21:37:45 阅读更多 →
LLM知识降熵:从信息垄断到理解权下放

LLM知识降熵:从信息垄断到理解权下放

你有没有过这种经历:翻开源码注释、论文摘要或者一份专业报告,每个字都认识,连在一起却像天书。想找人聊聊,身边要么没人懂,要么懂的懒得跟你解释。后来我试着把同一段内容丢给一个大语言模型,几秒钟之后&a…

2026/11/19 21:36:20 阅读更多 →

日新闻

周新闻

月新闻