为什么在一个大的 std::list 上迭代这么慢？

正如标题所示，我的一个程序遇到了问题，我使用 std::list 作为堆栈，并且还迭代列表的所有元素。当列表变得非常大时，程序花费的时间就太长了。

有人对此有好的解释吗？是一些堆栈/缓存行为吗？

（通过将列表更改为 std::vector 和 std::deque （顺便说一句，这是一个令人惊奇的数据结构）解决了问题，一切突然变得更快了）

编辑：我不是傻瓜，我不访问列表中间的元素。我对列表所做的唯一一件事是在末尾/开头删除/添加元素并迭代all列表的元素。 我总是使用迭代器来迭代列表。

列表的缓存位置很糟糕（不存在）。每个节点都是一个新的内存分配，并且可能是anywhere. So every当您沿着指针从一个节点到下一个节点时，您会跳转到内存中一个新的、不相关的位置。是的，这对性能有很大影响。高速缓存未命中可能比高速缓存命中慢两个数量级。在向量或双端队列中，几乎每次访问都会命中缓存。向量是一个连续的内存块，因此对其进行迭代的速度尽可能快。双端队列是几个较小的内存块，因此它会偶尔出现缓存未命中的情况，但它们仍然很少见，并且迭代仍然非常快，因为您主要获得缓存命中。

一个列表将几乎所有缓存未命中。而且性能会很糟糕。

实际上，从性能的角度来看，链表几乎不是正确的选择。

Edit: 正如评论所指出的，列表的另一个问题是数据依赖性。现代 CPU 喜欢重叠操作。但如果下一条指令取决于这条指令的结果，它就无法做到这一点。

如果你迭代一个向量，那没问题。您可以即时计算要读取的下一个地址，而无需检查内存。如果您正在阅读地址x现在，下一个元素将位于地址x + sizeof(T)其中 T 是元素类型。因此，那里没有依赖关系，CPU 可以立即开始加载下一个元素或其后的元素，同时仍然处理较早的元素。这样，我们就可以在需要时准备好数据，这进一步有助于掩盖访问 RAM 中数据的成本。

在列表中，我们需要跟踪来自节点的指针i到节点i+1，直到i+1已加载，我们甚至不知道去哪里寻找i+2。我们存在数据依赖性，因此 CPU 被迫一次读取一个节点，并且它无法提前开始读取未来的节点，因为它还不知道它们在哪里。

如果列表不全是缓存未命中，这不会是一个大问题，但由于我们遇到了大量缓存未命中，这些延迟的成本很高。