news 2026/5/4 13:40:28

C++STL:list(双链表)的底层实现 部分源码解析

作者头像

张小明

前端开发工程师

1.2k 24
文章封面图
C++STL:list(双链表)的底层实现 部分源码解析

1.list部分源码解析

同样,现在我们是读不懂大部分源码的。还是跳着看,看看部分模块功能,重要的底层变量,不去深究

根据我们看vector源码的理解,list头文件而是其他头文件的封装,重要的是 list.h ,那我们直接打开看看

打开来就看到了一个结构体模板,显然这是节点,定义的是双向链表next,prev ,__list_node 但节点类型为什么是void*? 一起往下看

再往下,就是迭代器,看他的迭代器模板参数 , 有3个参数,究竟是为什么?后面再说,链表迭代器很复杂,暂时跳过。看不懂


再往下看,找到了链表的核心成员,节点 node,类型是 list_node* ,被 typedef为了 link_type,那它到底是什么?我们去看一下它的构造

找到了它的构造函数,构造函数里封装“空初始化函数”,转到定义,发现它是创建哨兵位头节点的,因为next和prev都指向node 那为什么是get_node,不是直接new一段空间?因为它的内存都是内存池来的,我们的new是直接在堆空间获取内存。内存池的空间也是堆空间。区别是 new是 动态分配,内存池是 预分配 ,内存池更高效。

往下看发现了create_node 函数,创建节点 ,其中调用了consturct,construct是用定位new对已有空间显式调用构造完成初始化 因为内存池申请的空间是未初始化的内存空间,不是像new,new是开空间加构造。 但是内存池申请空间更高效,所以这样。 所以用内存池申请,释放空间,就得显式调用它的析构,构造函数

这一部分是插入和删除,虽然有助于了解底层,不过都涉及迭代器,链表迭代器比较难,那就不去了解了,我们确认链表底层,一步步来实现

2.list 双链表 底层实现

基于源码,我们首先来设计一下链表底层:

补充:结构体也是类,需要写构造函数,不然插入新节点会出错(默认构造下,指针是(随机内存地址)野指针,_data是随机值),无法构造新节点。

源码中,节点类型是void* ,不过我们不使用void*,我们按照之前数据结构学的来定义。因为void*设计的不好。后面具体说

2.0 定义结点为什么是结构体模板,不是类模板?

为什么用struct结构体? 一个类,如果我们不期望它的成员被访问限定符限定的时候,我们用结构体struct。 因为结构体默认public ,也可以用class加public,不过习惯上喜欢定义为sturct,方便。结点作为list的子结构,默认就是要被list访问和使用因此结点不能设为私有成员编译器设为公有不怕被其他人随意访问吗?不怕,因为底层都是有层层封装,从外壳层角度,结点底层变量名是不可猜的,因为随机性很强。也没人闲的去翻源码来使用,没有意义。

2.1构造函数

我们就不使用内存池了,太繁琐,没学过。 用new:

2.1.1 默认构造的封装——方便其他构造调用

也可以封装一下这个构造,因为链表底层很多构造,那每个涉及构造的函数都得重复一遍创建哨兵位节点的操作,干脆封装起来

2.1.0 n 个 val 的 构造

重载两个,一个int,一个size_t,因为会和 迭代器区间构造函数模板 冲突

2.2 pusn_back 尾插

思路:尾插需要找到最后一个节点tail,如图,那 tail 就是_head->prev ,然后只需要改变一下节点指向,就完成了

并且这里的尾插不需要考虑为空的情况,因为哨兵位头节点的存在空也可以直接在哨兵位上正常尾插,十分方便

2.3 迭代器(重要)

2.3.0 vector 和 list 的迭代器比较

这是vector的迭代器,vector底层空间连续,它的指针功能刚好符合迭代器需求,这就是"天赋",所以vector的迭代器十分简单,指针就行。

版权声明: 本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若内容造成侵权/违法违规/事实不符,请联系邮箱:809451989@qq.com进行投诉反馈,一经查实,立即删除!
网站建设 2026/5/4 13:34:58

3步掌握B站直播推流码获取:突破官方限制的专业直播解决方案

3步掌握B站直播推流码获取:突破官方限制的专业直播解决方案 【免费下载链接】bilibili_live_stream_code 用于在准备直播时获取第三方推流码,以便可以绕开哔哩哔哩直播姬,直接在如OBS等软件中进行直播,软件同时提供定义直播分区和…

作者头像 李华
网站建设 2026/5/4 13:34:40

ONNX Runtime C++ API 避坑指南:TensorRT/CUDA提供者下Env变量必须设为static?

ONNX Runtime C API 深度解析:TensorRT/CUDA提供者环境配置的线程安全实践 在深度学习推理加速领域,ONNX Runtime因其跨平台特性和高性能执行能力成为众多开发者的首选。当我们将目光聚焦于GPU加速场景时,TensorRT和CUDA执行提供者能够显著提…

作者头像 李华
网站建设 2026/5/4 13:34:26

如何用Shortkeys实现浏览器键盘操作革命:从鼠标依赖到键盘高手

如何用Shortkeys实现浏览器键盘操作革命:从鼠标依赖到键盘高手 【免费下载链接】shortkeys A browser extension for custom keyboard shortcuts 项目地址: https://gitcode.com/gh_mirrors/sh/shortkeys 你是否厌倦了在浏览器中频繁切换鼠标和键盘&#xf…

作者头像 李华
网站建设 2026/5/4 13:32:28

HeidiSQL实战:5个高效查询与表管理技巧,让你数据库操作快人一步

HeidiSQL实战:5个高效查询与表管理技巧,让你数据库操作快人一步 在数据库管理的日常工作中,效率往往决定了开发者的生产力天花板。作为一款轻量级但功能强大的MySQL可视化工具,HeidiSQL在熟练用户手中可以发挥出远超基础查询的威力…

作者头像 李华