0x04 数组与链表（列表）#

You cannot connect the dots looking forward, you can only connect them looking backwards. The only way to do great work is to love what you do.

—Steve Jobs

备注

数组（Array） 和 链表（Linked list） 都是顺序数据结构，但它们有很大的区别：

存储方式不同：数组是一块连续的内存空间，而链表则是由多个节点按需要连接而成。
访问方式不同：数组元素可以通过下标直接访问，时间复杂度为 \(O(1)\)；而链表需要遍历找到节点，时间复杂度为 \(O(n)\), 其中 \(n\) 为链表长度。
插入和删除操作效率不同：对于数组来说，如果要插入或者删除元素，需要移动其他元素，时间复杂度为 \(O(n)\); 而对于链表，只需要调整指针即可，时间复杂度为 \(O(1)\).
数组查找效率高，因为可以通过下标直接访问；链表插入和删除效率高，因为只需要调整指针。

数组、链表及其变种常被用作底层数据结构来实现堆、栈、队列和双端队列等抽象数据类型。

¹💡 C++ 标准库中已经实现了静态数组 std::array 与动态数组 std::vector 容器。由于前者不太灵活，所以并不常用，在本 Wiki 中，提到数组时，通常指代动态数组，也即向量（Vector）。 C++ 标准库中也已经实现了单向链表 std::forward_list 和双向链表 std::list 容器，但由于其性能较差，且表达能力有限，通常不推荐使用。

容器（Container）

容器 ¹ ¹💡 C++ 标准库中已经实现了静态数组 std::array 与动态数组 std::vector 容器。由于前者不太灵活，所以并不常用，在本 Wiki 中，提到数组时，通常指代动态数组，也即向量（Vector）。 C++ 标准库中也已经实现了单向链表 std::forward_list 和双向链表 std::list 容器，但由于其性能较差，且表达能力有限，通常不推荐使用。将数据和对数据的操作进行了抽象封装，隐藏了底层数据结构的具体实现细节。通过抽象容器的概念，可以定义一组通用的接口和约定，使得不同类型的容器在使用上具有一致性。抽象容器的概念使得可以设计和实现一组通用的算法，这些算法不依赖于具体的容器类型，而是适用于多种容器。例如，排序、查找、遍历等算法可以在各种容器上使用，而不需要为每种容器实现一套专门的算法。

初学者可能需要一段时间体会容器的优点。对于非常简单的数据结构算法，可能不需要使用容器。比如我们已经在以双向链表为例中以非容器的形式，实现了双向链表的插入与删除操作。

参见

我们在 0x05 栈与队列章节中会介绍一种支持高效的随机访问与头尾插入、删除操作的容器。

重要

通常我们需要了解如何设计一个简单的数组或链表，以及如何使用 C++ 标准库中的容器。

静态数组 Array#

Wikipedia Cppreference

通常我们直接使用 STL 中的 std::array 容器即可，值得注意以下几点：

不倾向使用 C 风格的数组 int a[100]，因为 C 风格的数组无法使用 STL 中的其它容器接口与算法；
- 如 [] 操作符不做越界检查，而 at() 接口会在越界时抛出异常，但会带来额外的性能开销；
- 因此在 Debug 的时候，可以使用 at() 接口（实际上推荐使用 AddressSanitizer, ASan ² ²不同编译器的 ASan 实现可能不同，因此需要你自行阅读相关文档，以了解如何使用它们。）；
std::array 容器的大小是固定的，不可变的，如果需要动态数组，应该使用 std::vector 容器；
std::array 的 swap() 方法的时间复杂度为 \(O(n)\).

³注意 ChaiGO STL 不能看作是一个完整的 STL 实现，它的设计初衷是方便初学者阅读和理解 STL 中算法和数据结构的实现。其代码更多是用来读的而不是用来跑的，可能存在 Bug 和缺乏性能优化和安全保证，无法像 EASTL 一样用于生产环境。如果你的 C++ 基本功扎实，可以尝试直接阅读 GNU/LLVM/EA 等公司或组织提供的 STL 实现。

阅读 ChaiGO STL::Array

接口定义在 Array，具体实现请参考 ChaiGO container/sequence/array 源码;
虽然这是最简单的容器，但由于模板参数中包含了类型参数，所以实现起来用到了一些特性：
- 模板偏特化：模板参数为 Array<T, 0> 时，与 Array<T, N> 的实现不同；
- 古早版本的实现是动态（运行时）多态，现在通过静态（编译期）多态实现，即模板偏特化；
为支持类型推导（如可以直接写 Array a1{1, 2, 3}），用了一些你可能没见过的语言特性：
- 模板参数包：如 template <class T, class... U> 支持变长参数列表；
- 折叠表达式：在编译时对可变数量的表达式进行展开和计算；
- 类模板参数推导：根据构造函数的参数类型来推导模板参数，C++17 标准引入。
- 概念（Concept）：方便对模板参数进行约束，C++20 标准引入。

大部分难以理解的地方会添加注释，希望你在阅读 ChaiGO STL ³ ³注意 ChaiGO STL 不能看作是一个完整的 STL 实现，它的设计初衷是方便初学者阅读和理解 STL 中算法和数据结构的实现。其代码更多是用来读的而不是用来跑的，可能存在 Bug 和缺乏性能优化和安全保证，无法像 EASTL 一样用于生产环境。如果你的 C++ 基本功扎实，可以尝试直接阅读 GNU/LLVM/EA 等公司或组织提供的 STL 实现。的过程中可以学到新东西。(●’◡’●)

动态数组 Vector#

Wikipedia Cppreference

通常我们直接使用 STL 中的 std::vector 容器即可，值得注意以下几点：

std::array 数据存储在 栈内存区 上，而 std::vector 数据存储在 堆内存区 上；
如果已知数据规模，可以在创建容器时指定容器大小，这样可以避免不必要的内存分配与拷贝；
- 比如在在构造函数中传入 count 参数: std::vector<int> v(n);
- 亦或者调用 reserve() 方法: std::vector<int> v; v.reserve(n);
clear() 方法的时间复杂度为 \(O(n)\)，而非 \(O(1)\)，因为它需要调用每个元素的析构函数；
- 对于内置类型，析构函数为空，所以可以认为此时 clear() 的时间复杂度为 \(O(1)\)；
- 对于自定义类型，析构函数可能会做一些复杂的操作，所以 clear() 的时间复杂度为 \(O(n)\)；
clear() 方法并不释放内存，如果需要释放内存，可以调用 shrink_to_fit() 方法；
emplace_back() 方法可以直接在容器尾部构造对象，而不是先构造临时对象再拷贝，效率更高；
push_back() 临时对象时，底层调用已经不再是 insert()，而是 emplace_back()；
swap() 方法的时间复杂度为 \(O(1)\).

阅读 ChaiGO STL::Vector

接口定义在 Vector，具体实现请参考 ChaiGO container/sequence/vector 源码;
网络上的许多 Vector 实现其实并不完备，在存储非 POD 类型时可能会出现内存泄漏；
STL 中的 vector<bool> 不是由 bool 组成的向量，而是一个特化版本。

迭代器（Iterator）

STL 迭代器的设计源于提供一种通用的、统一的访问容器元素的方式。迭代器作为 STL 算法和容器之间的桥梁，提供了一种抽象的、统一的遍历和访问容器元素的接口。

算法与容器的具体实现解耦，使得可以轻松地将算法应用于不同类型的容器。算法通过迭代器进行操作，而无需关心容器的具体实现，从而实现了算法与数据结构的分离。

除此以外，迭代器的抽象还能带来更多好处，目前可能还看不出，我们将在后续学习中加以体会。

阅读 ChaiGO STL::VectorIterator

具体实现请参考 ChaiGO iterator/vector 源码；
通过模板参数来控制迭代器的类型，在编译期就确定，避免了运行时的开销；
我们会在实现双向链表迭代器时提供另一种实现迭代器方式（用于旧版本）。

位数组 BitArray#

Wikipedia Cppreference

位数组（BitArray）有很多别名，如位图（BitMap）、位向量（BitVector）、位集（BitSet）等，是一种紧凑存储位的数组数据结构，可以有效地压缩存储空间。但是由于位数组的元素只能是 0 或 1，因此其表达能力有限。在 C++ STL 中，位数组的实现是 std::bitset，其大小在编译期就确定，且不可变。

BitArray 通常用于实现布隆过滤器（Bloom Filter）等数据结构，或者用于压缩存储大量的布尔值。结合位运算，可以实现高效的位图算法，如位图排序、Eratosthenes 素数筛等。

STL 中的 std::vector<bool> 特化成一类动态的 std::bitset, 可以认为是历史设计的失误。

双向链表 List#

Wikipedia Visualgo Cppreference

链表的每个节点包含一个数据（data）和一个指向后继节点（successor）的引用（即 C++ 中的指针）。如果是实现双向链表，每个节点还包含一个指向前驱节点（predecessor）的引用。

struct node {
    int val;     // data
    node* prev;  // predecessor (doubly)
    node* next;  // successor

    node(int e = 0, \
         node* p = nullptr, \
         node* n = nullptr) \
        : val(e), prev(p), next(n) {}
};

单链表与双链表

理解链表，能够为我们理解后续的数据结构打下坚实的基础，如各种树结构、跳表等等。

阅读 ChaiGO STL::List

接口定义在 List，具体实现请参考 ChaiGO container/sequence/list 源码;
GNU STL 中的链表实现是循环双向链表，而 ChaiGO STL 中使用了两个哨兵节点；
List::sort() 的实现值得把玩，使用了归并排序，且没有用到额外的空间；

阅读 ChaiGO STL::ListIterator

具体实现请参考 ChaiGO iterator/list 源码；
我们分别实现了 ListIterator 和 ListConstIterator，前者可读写，后者只读；
不难发现这种写法有着大量的重复代码，因此不再推荐。

单向链表 ForwardList#

Wikipedia Visualgo Cppreference

单向链表由于没有前驱节点，因此只能从前往后遍历，无法从后往前遍历。这也导致了其插入、删除操作的语义和双向链表不同，核心在于理解 xxx_after() 形式的接口。如相较于双向链表的 insert() 接口定义，单向链表的接口名为 insert_after(). 同理有接口 emplace_after(), erase_after() 等，以及很多人忽视掉的 before_begin() 迭代器，用于表示链表的头节点之前的位置。

尤其是 splice_after() 接口，在传入范围区间时视为开区间：(first, last), 有如下等价：

splice_after(pos, other);
splice_after(pos, other, other.before_begin(), other.end());

splice_after(pos, other, it);
splice_after(pos, other, it, std::next(it, 2));

这些语义上的差异使得人们在使用单向链表时，往往会感到不适应，因此很少有人使用单向链表。

阅读 ChaiGO STL::ForwardList

接口定义在 ForwardList，具体实现请参考 ChaiGO container/sequence/forward_list 源码;
GNU STL 中的链表实现是循环双向链表，而 ChaiGO STL 中使用了两个哨兵节点；
ForwardList 和 List 的接口几乎一致，但是底层实现细节略有差异。

环形缓冲区 RingBuffer#

Wikipedia Boost

警告

RingBuffer 并非 STL 中的标准数据结构，一些接口的具体行为是由其实现决定的。

循环缓冲区（Circular buffer）、循环队列（Circular Deque）、或环形缓冲区（Ring Buffer）是一种环形数据结构， 其具有固定大小，表现为先进先出队列（FIFO）的抽象数据类型，即当缓冲区被填满后，新写入的数据会覆盖掉最早的数据。此类数据结构最常应用于实时系统，如音频播放器、视频播放器、网络数据包缓冲区等。

由于不涉及到内存重新分配，因此环形缓冲区的效率非常高，但是其容量固定，且不支持动态扩容，因此使用时需要预先分配好内存空间。我们在这里介绍 RingBuffer 是为了引入两类设计模式：

设计模式之适配器（Adapter）模式

将基本数据结构实现为容器的目的之一是为了易于复用和扩展。适配器的设计思想是将已有的实现复用和包装，通过重复利用现有的容器实现，可以将代码量和工作量降到最低。由于物理上并不存在环状的内存区域，因此环形缓冲区只是概念上的环状，实际上底层是一个线性的内存区域。我们已经实现了向量 Vector 和双向链表 List 等线性容器，因此可以通过适配器模式实现环形缓冲区。

通常选择将这样的数据结构实现并称之为容器适配器（Container adapter）。

设计模式之迭代器（Iterator）模式

如何让物理连续的内存区域表现为逻辑上的环状呢？我们可以通过迭代器模式实现。即设计一个迭代器，使得当迭代器已经指向最后一个元素时，再向后移动一个位置时，迭代器会回到第一个元素。这样做的好处是我们可以实现一个通用的迭代器，适用于任何线性容器。

阅读 ChaiGO STL::CircularIterator

具体实现请参考 ChaiGO iterator/adapter/circular 源码;
- 关键阅读 operator++(), operator--() 和 operator+=(n) 的实现；
- 其它类似接口的实现即对这个接口进行等价调用。
与 ListIterator 和 ListConstIterator 的设计相似，但实现方式不同：
- 虽然两个类单独实现，但继承自同一个基类 CircularIteratorBase, 降低代码冗余；
- 用到了 CRTP (Curiously Recurring Template Pattern) 技术；
- 所有的实际操作交由基类实现，派生类仅提供类型信息。
- 阅读注释以了解为什么要这样设计，而不是效仿 ListIterator.

阅读 ChaiGO STL::RingBuffer

接口定义在 RingBuffer，具体实现请参考 ChaiGO container/adapter/ring_buffer 源码;
该数据结构不在 C++ STL 标准中，但在 Boost / EASTL 等其它第三方库中有实现；
为了方便使用，额外提供了 resize() 和 reserve() 接口，仅在特定情况使用。
只需要简单改动底层容器为 List，我们就能得到循环双向链表 RingList；

0x04 数组与链表（列表）

目录

0x04 数组与链表（列表）#

静态数组 Array#

动态数组 Vector#

位数组 BitArray#

双向链表 List#

单向链表 ForwardList#

环形缓冲区 RingBuffer#