c++ - std::list 与 std::vector 迭代

Question

据说遍历向量（如读取它的所有元素）比遍历列表更快，因为优化了缓存。

网络上是否有任何资源可以量化它对性能的影响程度？

另外，使用自定义链表会更好，哪些元素将被预先分配，以便它们在内存中是连续的？

其背后的想法是我想以不会改变的特定顺序存储元素。我仍然需要能够在运行时在中间快速插入一些，但它们中的大多数仍然是连续的，因为顺序不会改变。

元素是连续的这一事实是否会对缓存产生影响，或者因为我仍然会调用list_element->next而不是++list_element它并没有改善任何东西？

Answer 1

由于数据结构的紧凑表示而从缓存一致性中获得的效率可能相当显着。在与列表相比的向量的情况下，紧凑表示不仅可以更好地用于读取，甚至可以用于某些特定架构的高达 500K 元素数量级的元素的插入（向量中的移动），如 Bjarne 的本文图 3 所示斯特鲁普：

http://www2.research.att.com/~bs/Computer-Jan12.pdf

（发布者网站： http: //www.computer.org/portal/web/csdl/doi/10.1109/MC.2011.353）

我认为如果这对你的程序来说是一个关键因素，你应该在你的架构上对其进行分析。

Answer 2

向量和列表之间的主要区别在于，向量中的元素是随后在预分配的缓冲区中构造的，而列表中的元素是一个接一个地构造的。因此，向量中的元素被授予占用连续内存空间，而列表元素（除非某些特定情况，例如以这种方式工作的自定义分配器）不被授予如此，并且可以在周围“稀疏”记忆。

现在，由于处理器在重新映射主存储器的整个页面的高速缓存（可以比主 RAM 快 1000 倍）上运行，如果元素是连续的，则它们很可能适合相同的内存页面，因此是迭代开始时在缓存中一起移动。在继续进行时，一切都发生在缓存中，无需进一步移动数据或进一步访问较慢的 RAM。

使用 list-s，由于元素到处都是稀疏的，“去下一个”意味着引用一个地址，它可能不在其前一个内存页面中，因此，缓存需要在每个迭代步骤中更新，访问每次迭代的 RAM 越慢。

性能差异很大程度上取决于处理器和用于主 RAM 和高速缓存的内存类型，以及std::allocator（最终operator new和malloc）的实现方式，因此无法给出一般数字。（注意：巨大的差异意味着 RAM 对缓存的不利影响，但也可能意味着在 list-s 上的错误实现）

Answer 3

不确定我是否可以正确解释，但这是我的观点（我正在考虑下面翻译的机器指令：），

向量迭代器（连续内存）：当您增加向量迭代器时，迭代器值简单地添加对象的大小（在编译时已知）以指向下一个对象。在大多数 CPU 中，这最多是一到三个指令。

列表迭代器（链表http://www.sgi.com/tech/stl/List.html）：当你增加一个列表迭代器（指向的对象）时，前向链接的位置通过添加一些数字来定位指向对象的基址，然后作为迭代器的新值加载。有不止一个内存访问，并且比向量迭代操作慢。