【STL 源码剖析】系列五：序列式容器 --list

发表于 2023-10-23 更新于 2024-04-20 分类于 STL 源码剖析阅读次数： 25 本文字数： 2k 阅读时长 ≈ 7 分钟

前言

本篇内容是《STL 源码剖析》中对于 list 容器的读书笔记和个人理解。主要内容是：

1.list 容器在概念上对应于线性表的链式存储结构，实现上是双向循环链表；

2.list 的构造与内存管理，重点是如何插入一个元素；

3.list 中的一些关键操作实现，包括 splice、merge、reverse、sort 等以及底层实现 transfer。

list

概述

list 与 vector 相比，主要区别是底层存储空间不同。vector 使用连续存储结构表示线性表，list 使用链式存储结构表示线性表。
使用链式存储结构的好处就是每次插入和删除一个元素，就配置或者释放一个元素空间。另外就是对于任何位置的元素插入和删除是常数时间。

list 的节点

list 的迭代器

因为 list 的存储结构并不是连续的，所以不能像 vector 一样使用普通指针作为迭代器完成随机存取。

list 的迭代器需要具备的功能有：1. 递增，指向下一个节点；2. 递减，指向前一个结点；3. 取值，解引用时取的是节点的数据；4. 成员访问，成员访问时是节点的成员。

由于 STL 中的 list 是双向链表。所以迭代器的类型是双向迭代器。

list 迭代器与 vector 迭代器的不同：插入、删除和连接操作不会使原有的 list 迭代器失效（删除只会让被删除的迭代器失效），这是因为对于 list 的操作不会影响现有的空间，对于 vector 的任何操作有可能会导致空间重新分配。

list 迭代器源代码：

list 的数据结构

SGI 的 list 是一个双向循环链表，因此只需要一个指针就可以表示整个链表。

为了满足前闭后开区间的要求，这里需要让这个指针指向最后一个元素后面的一个空结点：

由此便可以实现下面几个函数：

list 的构造与内存管理

list 默认使用 alloc（默认是第二级配置器）作为空间配置器，并据此借助接口 simple_alloc 定义一个专属配置器 list_node_allocator，方便以元素为单位申请空间。

所以就可以使用 list_node_allocator (n) 表示申请 n 个节点的空间。下面四个函数用于配置、释放、构造、销毁一个节点：

以默认构造函数为例说明 list 的创建过程：

当调用 push_back () 插入新元素时，该函数调用其中一个重载版本的 insert 函数：

注意插入节点之后返回的是哨兵迭代器（插入点）的前方。

关于插入节点的操作顺序：

插入节点主要是对指针进行操作，这里的关键在于修改指针之后要保证能够找到需要被操作的节点，不要出现修改指针之后丢失节点问题。所以插入时进行每一步指针操作时都要考虑清楚这步操作完成之后能否找到需要被操作的节点。

以单链表为例，假如需要在节点 P 后面（单链表只有 next 指针所以只能在后面插入）插入一个节点 S：

这里一共有两个指针操作，即 P 的 next 指针和 S 的 next 指针。这两个操作的顺序是要有先后顺序的，一定是先让 S 的 next 指针指向 P->next，然后再让 P 的 next 指针指向 S。这里的原因是，我们目前可以明确知道 P 和 S 节点，获取未知节点（P->next）的唯一方法就是通过 P 的 next 指针。如果我们先修改 P 的 next 指针使其指向 S，那么就丢失了获取 P 节点后面节点的方法。所以这里一定是先让 S 的 next 指针指向后面的节点，此时有两种方式（S->next 和 P->next）可以获取到后面的节点，所以接下来就可以修改其中一种方式（P->next）。

下面以双链表为例，假如需要在节点 P 之前插入一个新节点 S：

首先这里一共需要四个指针操作，分别是 P->prev、T (P->prev)->next、S->next、S->prev。
这里需要注意的是，T 是未知节点，目前只能通过 P->prev 来访问。所以如果想要更新这个指针，必须先增加一个指针指向 T 节点，也就是必须先令 S->prev 指向 T，所以必须先更新 S->prev 才能更新 P->prev。其它的操作顺序没有要求。
这里采用的顺序先确定从 S 节点出去的指针，即 S->next 和 S->prev；再确定指向 S 节点的指针，即 T->next 和 P->prev。

list 的一些元素操作

插入和删除操作

迁移操作

list 内容提供一个迁移操作：将某段连续范围的元素迁移到某个指定位置之前。这个操作为其它复杂操作如 splice、sort、merge 提供了基础。

对于迁移操作，一共需要操作 6 个指针。需要将范围 [first, last - 1] 插入到 P 节点之前，这是 4 个指针的操作；还需要将 first - 1 的节点与 last 节点相连，这是 2 个指针的操作。

这里需要明确的是，涉及的节点一共有 5 个，已知的是 P、first、last，不能直接取得的是 P - 1 (P->prev)、firs - 1 (first->prev)、last - 1 (last->prev)，再修改这些指针之前一定要保证存在另一个指向这个节点的指针。但是这里注意，由于 firs - 1 (first->prev) 需要指向 P - 1 (P->prev)，所以这里一定是需要一个临时指针取保存其中一个的。因此 6 次指针再加一次保存临时指针的操作，一共是 7 个操作。
下面对于这 7 次操作的顺序进行演示，这里的逻辑是：先连通一个方向（保证 first-1 ->last 和 P-1->first->…->last - 1->P），再连通另一个方向（last->first-1 和 P-1->last-1 -> …->first->P-1）。