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的迭代器十分简单，指针就行。