(array)= (vector)= (list)= (linked-list)= # 0x04 数组与链表（列表） ```{epigraph} 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 ``` ```{margin} Python 中的列表 `list` 是一种动态数组，而非链表，其元素可以是任意类型的对象，与这里提到的概念截然不同。 ``` ```{note} **数组（Array）** 和 **链表（Linked list）** 都是顺序数据结构，但它们有很大的区别： - 存储方式不同：数组是一块连续的内存空间，而链表则是由多个节点按需要连接而成。 - 访问方式不同：数组元素可以通过下标直接访问，时间复杂度为 $O(1)$；而链表需要遍历找到节点，时间复杂度为 $O(n)$, 其中 $n$ 为链表长度。 - 插入和删除操作效率不同：对于数组来说，如果要插入或者删除元素，需要移动其他元素，时间复杂度为 $O(n)$; 而对于链表，只需要调整指针即可，时间复杂度为 $O(1)$. - 数组查找效率高，因为可以通过下标直接访问；链表插入和删除效率高，因为只需要调整指针。 数组、链表及其变种常被用作底层数据结构来实现堆、栈、队列和双端队列等抽象数据类型。 ``` ```{admonition} 容器（Container） 容器 [^std-array-and-list] 将数据和对数据的操作进行了抽象封装，隐藏了底层数据结构的具体实现细节。 通过抽象容器的概念，可以定义一组通用的接口和约定，使得不同类型的容器在使用上具有一致性。 抽象容器的概念使得可以设计和实现一组通用的算法，这些算法不依赖于具体的容器类型，而是适用于多种容器。 例如，排序、查找、遍历等算法可以在各种容器上使用，而不需要为每种容器实现一套专门的算法。 初学者可能需要一段时间体会容器的优点。对于非常简单的数据结构算法，可能不需要使用容器。 比如我们已经在 {ref}`doubly-linked-list-example` 中以非容器的形式，实现了双向链表的插入与删除操作。 ``` [^std-array-and-list]: 💡 C++ 标准库中已经实现了静态数组 `std::array` 与动态数组 `std::vector` 容器。 由于前者不太灵活，所以并不常用，在本 Wiki 中，提到数组时，通常指代动态数组，也即向量（Vector）。 C++ 标准库中也已经实现了单向链表 `std::forward_list` 和双向链表 `std::list` 容器， 但由于其性能较差，且表达能力有限，通常不推荐使用。 ```{seealso} 我们在 {doc}`stack-and-queue` 章节中会介绍一种支持高效的随机访问与头尾插入、删除操作的容器。 ``` ```{important} 通常我们需要了解如何设计一个简单的数组或链表，以及如何使用 C++ 标准库中的容器。 ``` ## 静态数组 Array {bdg-link-primary-line}`Wikipedia ` {bdg-link-primary-line}`Cppreference ` [^asan]: 不同编译器的 ASan 实现可能不同，因此需要你自行阅读相关文档，以了解如何使用它们。 通常我们直接使用 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]: 注意 ChaiGO STL 不能看作是一个完整的 STL 实现，它的设计初衷是方便初学者阅读和理解 STL 中算法和数据结构的实现。 其代码更多是用来读的而不是用来跑的，可能存在 Bug 和缺乏性能优化和安全保证，无法像 EASTL 一样用于生产环境。 如果你的 C++ 基本功扎实，可以尝试直接阅读 GNU/LLVM/EA 等公司或组织提供的 STL 实现。 ```{admonition} 阅读 ChaiGO STL::Array :class: seealso - 接口定义在 {doc}`../../reference/container/array`，具体实现请参考 源码; - 虽然这是最简单的容器，但由于模板参数中包含了类型参数，所以实现起来用到了一些特性： - 模板偏特化：模板参数为 `Array` 时，与 `Array` 的实现不同； - 古早版本的实现是动态（运行时）多态，现在通过静态（编译期）多态实现，即模板偏特化； - 为支持类型推导（如可以直接写 `Array a1{1, 2, 3}`），用了一些你可能没见过的语言特性： - 模板参数包：如 `template ` 支持变长参数列表； - 折叠表达式：在编译时对可变数量的表达式进行展开和计算； - 类模板参数推导：根据构造函数的参数类型来推导模板参数，C++17 标准引入。 - 概念（Concept）：方便对模板参数进行约束，C++20 标准引入。 大部分难以理解的地方会添加注释，希望你在阅读 ChaiGO STL [^chaigo-stl] 的过程中可以学到新东西。(●'◡'●) ``` ## 动态数组 Vector ```{margin} 计算机领域 Vector 的中文翻译习惯为向量，但其含义与数学上的向量大相径庭。 一些库将这样的数据结构称为动态数组（Dynamic array），以避免歧义。 ``` {bdg-link-primary-line}`Wikipedia ` {bdg-link-primary-line}`Cppreference ` 通常我们直接使用 STL 中的 `std::vector` 容器即可，值得注意以下几点： - `std::array` 数据存储在 **栈内存区** 上，而 `std::vector` 数据存储在 **堆内存区** 上； - 如果已知数据规模，可以在创建容器时指定容器大小，这样可以避免不必要的内存分配与拷贝； - 比如在在构造函数中传入 `count` 参数: `std::vector v(n);` - 亦或者调用 `reserve()` 方法: `std::vector 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)$. ```{admonition} 阅读 ChaiGO STL::Vector :class: seealso - 接口定义在 {doc}`../../reference/container/vector`，具体实现请参考 源码; - 网络上的许多 `Vector` 实现其实并不完备，在存储非 POD 类型时可能会出现内存泄漏； - STL 中的 `vector` 不是由 `bool` 组成的向量，而是一个 [特化版本](https://en.cppreference.com/w/cpp/container/vector_bool)。 ``` ```{admonition} 迭代器（Iterator） STL 迭代器的设计源于提供一种通用的、统一的访问容器元素的方式。 迭代器作为 STL 算法和容器之间的桥梁，提供了一种抽象的、统一的遍历和访问容器元素的接口。 算法与容器的具体实现解耦，使得可以轻松地将算法应用于不同类型的容器。 算法通过迭代器进行操作，而无需关心容器的具体实现，从而实现了算法与数据结构的分离。 除此以外，迭代器的抽象还能带来更多好处，目前可能还看不出，我们将在后续学习中加以体会。 ``` ```{admonition} 阅读 ChaiGO STL::VectorIterator :class: seealso - 具体实现请参考 源码； - 通过模板参数来控制迭代器的类型，在编译期就确定，避免了运行时的开销； - 我们会在实现双向链表迭代器时提供另一种实现迭代器方式（用于旧版本）。 ``` ## 位数组 BitArray {bdg-link-primary-line}`Wikipedia ` {bdg-link-primary-line}`Cppreference ` 位数组（BitArray）有很多别名，如位图（BitMap）、位向量（BitVector）、位集（BitSet）等， 是一种紧凑存储位的数组数据结构，可以有效地压缩存储空间。 但是由于位数组的元素只能是 0 或 1，因此其表达能力有限。 在 C++ STL 中，位数组的实现是 `std::bitset`，其大小在编译期就确定，且不可变。 BitArray 通常用于实现布隆过滤器（Bloom Filter）等数据结构，或者用于压缩存储大量的布尔值。 结合位运算，可以实现高效的位图算法，如位图排序、Eratosthenes 素数筛等。 STL 中的 `std::vector` 特化成一类动态的 `std::bitset`, 可以认为是历史设计的失误。 ## 双向链表 List {bdg-link-primary-line}`Wikipedia ` {bdg-link-primary-line}`Visualgo ` {bdg-link-primary-line}`Cppreference ` 链表的每个节点包含一个数据（data）和一个指向后继节点（successor）的引用（即 C++ 中的指针）。 如果是实现双向链表，每个节点还包含一个指向前驱节点（predecessor）的引用。 `````{grid} 2 ````{grid-item} ```{code-block} cpp 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) {} }; ``` ```` ````{grid-item} 单链表与双链表 ```{figure} https://upload.wikimedia.org/wikipedia/commons/6/6d/Singly-linked-list.svg --- alt: Linked List name: Linked list image align: center --- 单向链表示例 ``` ```{figure} https://upload.wikimedia.org/wikipedia/commons/5/5e/Doubly-linked-list.svg --- alt: Doubley linked List name: Doubley linked list image align: center --- 双向链表示例 ``` ```` ````` 理解链表，能够为我们理解后续的数据结构打下坚实的基础，如各种树结构、跳表等等。 ```{admonition} 阅读 ChaiGO STL::List :class: seealso - 接口定义在 {doc}`../../reference/container/list`，具体实现请参考 源码; - GNU STL 中的链表实现是循环双向链表，而 ChaiGO STL 中使用了两个哨兵节点； - `List::sort()` 的实现值得把玩，使用了归并排序，且没有用到额外的空间； ``` ```{admonition} 阅读 ChaiGO STL::ListIterator :class: seealso - 具体实现请参考 源码； - 我们分别实现了 `ListIterator` 和 `ListConstIterator`，前者可读写，后者只读； - 不难发现这种写法有着大量的重复代码，因此不再推荐。 ``` ## 单向链表 ForwardList {bdg-link-primary-line}`Wikipedia ` {bdg-link-primary-line}`Visualgo ` {bdg-link-primary-line}`Cppreference ` 单向链表由于没有前驱节点，因此只能从前往后遍历，无法从后往前遍历。 这也导致了其插入、删除操作的语义和双向链表不同，核心在于理解 `xxx_after()` 形式的接口。 如相较于双向链表的 `insert()` 接口定义，单向链表的接口名为 `insert_after()`. 同理有接口 `emplace_after()`, `erase_after()` 等， 以及很多人忽视掉的 `before_begin()` 迭代器，用于表示链表的头节点之前的位置。 尤其是 `splice_after()` 接口，在传入范围区间时视为开区间：`(first, last)`, 有如下等价： ```{code-block} cpp 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)); ``` 这些语义上的差异使得人们在使用单向链表时，往往会感到不适应，因此很少有人使用单向链表。 ```{admonition} 阅读 ChaiGO STL::ForwardList :class: seealso - 接口定义在 {doc}`../../reference/container/forward_list`，具体实现请参考 源码; - GNU STL 中的链表实现是循环双向链表，而 ChaiGO STL 中使用了两个哨兵节点； - `ForwardList` 和 `List` 的接口几乎一致，但是底层实现细节略有差异。 ``` ## 环形缓冲区 RingBuffer {bdg-link-primary-line}`Wikipedia ` {bdg-link-primary-line}`Boost ` ```{warning} RingBuffer 并非 STL 中的标准数据结构，一些接口的具体行为是由其实现决定的。 ``` ```{figure} https://upload.wikimedia.org/wikipedia/commons/b/b7/Circular_buffer.svg --- figclass: margin alt: Ring Buffer name: ring-buffer-img --- Circular buffer \ I, Cburnett, [CC BY-SA 3.0](https://creativecommons.org/licenses/by-sa/3.0) , \ via Wikimedia Commons ``` 循环缓冲区（Circular buffer）、循环队列（Circular Deque）、或环形缓冲区（Ring Buffer）是一种环形数据结构， **其具有固定大小**，表现为先进先出队列（FIFO）的抽象数据类型，即当缓冲区被填满后，新写入的数据会覆盖掉最早的数据。 此类数据结构最常应用于实时系统，如音频播放器、视频播放器、网络数据包缓冲区等。 由于不涉及到内存重新分配，因此环形缓冲区的效率非常高，但是其容量固定，且不支持动态扩容，因此使用时需要预先分配好内存空间。 我们在这里介绍 `RingBuffer` 是为了引入两类设计模式： ```{admonition} 设计模式之适配器（Adapter）模式 将基本数据结构实现为容器的目的之一是为了易于复用和扩展。 适配器的设计思想是将已有的实现复用和包装，通过重复利用现有的容器实现，可以将代码量和工作量降到最低。 由于物理上并不存在环状的内存区域，因此环形缓冲区只是概念上的环状，实际上底层是一个线性的内存区域。 我们已经实现了向量 `Vector` 和双向链表 `List` 等线性容器，因此可以通过适配器模式实现环形缓冲区。 通常选择将这样的数据结构实现并称之为容器适配器（Container adapter）。 ``` ```{admonition} 设计模式之迭代器（Iterator）模式 如何让物理连续的内存区域表现为逻辑上的环状呢？我们可以通过迭代器模式实现。 即设计一个迭代器，使得当迭代器已经指向最后一个元素时，再向后移动一个位置时，迭代器会回到第一个元素。 这样做的好处是我们可以实现一个通用的迭代器，适用于任何线性容器。 ``` ```{admonition} 阅读 ChaiGO STL::CircularIterator :class: seealso - 具体实现请参考 源码; - 关键阅读 `operator++()`, `operator--()` 和 `operator+=(n)` 的实现； - 其它类似接口的实现即对这个接口进行等价调用。 - 与 `ListIterator` 和 `ListConstIterator` 的设计相似，但实现方式不同： - 虽然两个类单独实现，但继承自同一个基类 `CircularIteratorBase`, 降低代码冗余； - 用到了 CRTP (Curiously Recurring Template Pattern) 技术； - 所有的实际操作交由基类实现，派生类仅提供类型信息。 - 阅读注释以了解为什么要这样设计，而不是效仿 `ListIterator`. ``` ```{admonition} 阅读 ChaiGO STL::RingBuffer :class: seealso - 接口定义在 {doc}`../../reference/container/ring_buffer`，具体实现请参考 源码; - 该数据结构不在 C++ STL 标准中，但在 Boost / EASTL 等其它第三方库中有实现； - 为了方便使用，额外提供了 `resize()` 和 `reserve()` 接口，仅在特定情况使用。 - 只需要简单改动底层容器为 `List`，我们就能得到循环双向链表 `RingList`； ```