Bjarne Stroustrup说我们必须避免使用链表。

Question

我在YouTube上看到了这个视频: https://www.youtube.com/watch?v=YQs6IC-vgmo，Bjarne 在其中说使用向量比链表更好。我无法完全理解这一点，所以有没有人能以通俗易懂的方式解释他的意思呢?

P.S: 我是一名高中生，可以轻松掌握链表，但学习向量时遇到困难。你能推荐任何学习向量的资源吗？

- ShankRam

---

链表对于缓存丢失可能非常不利。向量将把基础内存存储在连续块中，这有助于缓解这个问题。因此，虽然使用链表某些操作的大 O 复杂度可能较低，在实践中，由于它们在常见架构（如 x86）上的实现，有时会发现它们的性能相当差。 - shuttle87

自学向量，是学习如何实现一个向量还是如何使用一个向量？ - T.C.

以下是需要翻译的内容：https://dev59.com/_3RC5IYBdhLWcg3wK9yV答案：这个问题列出了一些最好的 C 语言书籍，包括入门级别和高级别。每本书都有一段简短的评论来帮助你选择适合自己的书籍。 - T.C.

@ShankRam：存在堆内存碎片问题和每个单独元素的内存开销。std::list需要为每个元素配备两个指针的单独内存块。 - Minor Threat

需要牢记的是没有完美的容器，它们都有优缺点。为了获得最佳性能，在选择容器之前，您应该仔细分析自己的需求。 - Jonathan Potter

Answer 1

向量和链表的优劣势

相比链表，向量的主要优势在于内存局部性。

通常情况下，链表中的每个元素都是单独分配的。因此这些元素可能不会在内存中相邻（元素之间可能存在间隙）。

向量保证存储所有元素的连续性（相邻元素之间没有间隙）。

注意：以下内容为简化描述... ;)

我认为关于连续存储数据模式相对于非连续存储数据模式的卓越性能的简化关键点是：

1. 缓存未命中

现代CPU不会从内存中抓取单个字节，而是会抓取更大的数据块。因此，如果您的数据对象大小小于这些块的大小，并且存储是连续的，您可以一次获取多个元素，因为多个元素可能在一个块中。

例子：

64字节块（通常的缓存行大小）可以同时容纳16个32位整数。因此，最早在处理第一个元素后从缓存中获取16个元素时会发生缓存未命中（数据尚未在缓存中 -> 需要从主内存中加载）。如果使用链表，第一个元素可能是唯一存在于64字节块内的元素。理论上可能会发生每个列表元素都发生缓存未命中的情况。

具体例子：

std::vector<std::uint32_t> v;
// somehow fill 64 values into v
std::uint32_t s{};
for(std::size_t i{0}; i<v.size(); ++i)
{
  s += v[i];
}

假设 v 的内容还没有被缓存。

在 for 循环的数据处理过程中会发生什么？

1）检查 v[0] 是否在缓存中。--> 不是

2）从主内存的地址开始获取包含 v[0] 的 64 个字节，存入一个缓存行

3）从缓存中加载 v[0] 并将其值加到 s 中

4）v1 是否在缓存中？--> 是，因为它与前面的 v[0] 相邻，已经随同前面的数据一起被加载

5）从缓存中加载 v1 并将其值加到 s 中

6）v[2] 是否在缓存中？--> 是...

7）从缓存中加载 v[2] 并将其值加到 s 中

... 等等 ...

34）v[16] 是否在缓存中？--> 不是

35）从主内存的地址开始获取包含 v[16] 的 64 个字节，存入一个缓存行

36）从缓存中加载 v[16] 并将其值加到 s 中

37）v[17] 是否在缓存中？--> 是，因为它与前面的 v[16] 相邻，已经随同前面的数据一起被加载

等等 ...

将数据从主内存加载到缓存中需要比从缓存加载到处理器寄存器并执行简单操作所需的时间长得多。因此，多个值可能驻留在单个缓存行中这一事实可以显著提高性能。

链表不提供连续存储保证，您不能指望获得此性能提升。这也是为什么对于连续容器而言，随机迭代（随机访问元素）的性能不如正向迭代（按顺序访问元素）。

2. 预取

上述效果由 CPU 功能 "预取器" 放大。

如果从主内存加载了一个块，则预取器会准备加载下一个块 / 已经将其放入缓存中，显著降低从该部分主内存加载数据的惩罚。

当且仅当您实际需要下一个准备好的块中的数据时，这当然非常有效。

向量通常是如何工作的（内部）？

参见：c++ Vector, what happens whenever it expands/reallocate on stack?

- Pixelchemist

Answer 2

Stroustrup写了一篇文章https://isocpp.org/blog/2014/06/stroustrup-lists，说他被误解了，并没有说要避免使用链表。

我无法评论C++中向量和链表的实现。但是，你说你理解链表而不理解向量。我可以说，在Java中，人们理解向量，但不一定理解链表。C#有一个List数据类型，大多数人并不真正了解它是作为链表还是向量实现的。这里有一个关于用法差异的好讨论https://www.reddit.com/r/learnprogramming/comments/15mxrt/what_are_the_real_world_applications_of_linked/。其中一条评论说：“存储在链接列表中的数据，在内存中分配后，将留在同一位置。这意味着随着您的链接列表大小变化，任何元素的数据都不会移动（在内存中），因此可以安全地指向它。”

Straustrup的文章中提到：“是的，我的建议是默认使用std::vector。更一般地说，除非有充分的理由不这样做，否则请使用连续表示。像C一样，C++默认情况下就是这样设计的。此外，请不要在没有测量的情况下对性能进行评估。”

我曾经看到Stroustrup在一次采访中说，删除一个元素并将它们全部向上移动的速度非常快，比从链表中删除一个元素要快。但我想我们不应该从中得出结论，认为链表没有用例。

- barlop