C++STL：list（双链表）的底层实现 部分源码解析

1.list部分源码解析同样现在我们是读不懂大部分源码的。还是跳着看看看部分模块功能重要的底层变量不去深究根据我们看vector源码的理解list头文件而是其他头文件的封装重要的是 list.h 那我们直接打开看看打开来就看到了一个结构体模板显然这是节点定义的是双向链表nextprev __list_node 但节点类型为什么是void* 一起往下看再往下就是迭代器看他的迭代器模板参数 有3个参数究竟是为什么后面再说链表迭代器很复杂暂时跳过。看不懂再往下看找到了链表的核心成员节点 node类型是 list_node* ,被 typedef为了 link_type,那它到底是什么我们去看一下它的构造找到了它的构造函数构造函数里封装“空初始化函数”转到定义发现它是创建哨兵位头节点的因为next和prev都指向node 那为什么是get_node不是直接new一段空间因为它的内存都是内存池来的我们的new是直接在堆空间获取内存。内存池的空间也是堆空间。区别是 new是 动态分配内存池是 预分配 内存池更高效。往下看发现了create_node 函数创建节点 其中调用了consturctconstruct是用定位new对已有空间显式调用构造完成初始化 因为内存池申请的空间是未初始化的内存空间不是像newnew是开空间加构造。 但是内存池申请空间更高效所以这样。 所以用内存池申请释放空间就得显式调用它的析构构造函数这一部分是插入和删除虽然有助于了解底层不过都涉及迭代器链表迭代器比较难那就不去了解了我们确认链表底层一步步来实现2.list 双链表 底层实现基于源码我们首先来设计一下链表底层补充结构体也是类需要写构造函数不然插入新节点会出错默认构造下指针是随机内存地址野指针_data是随机值无法构造新节点。源码中节点类型是void* 不过我们不使用void*我们按照之前数据结构学的来定义。因为void*设计的不好。后面具体说2.0 定义结点为什么是结构体模板不是类模板为什么用struct结构体 一个类如果我们不期望它的成员被访问限定符限定的时候我们用结构体struct。 因为结构体默认public 也可以用class加public不过习惯上喜欢定义为sturct方便。结点作为list的子结构默认就是要被list访问和使用因此结点不能设为私有成员编译器设为公有不怕被其他人随意访问吗不怕因为底层都是有层层封装从外壳层角度结点底层变量名是不可猜的因为随机性很强。也没人闲的去翻源码来使用没有意义。2.1构造函数我们就不使用内存池了太繁琐没学过。 用new2.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的迭代器十分简单指针就行。