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

Question

据说由于优化了缓存，遍历一个 vector (如读取它的所有元素)比遍历一个列表更快。

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

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

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

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

Answer 1

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

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

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

性能差异在很大程度上取决于处理器和用于主 RAM 和缓存的内存类型，以及 std::allocator(最终是 operator new 和 malloc) 已经实现，所以不可能给出一个通用的数字。(注意:巨大的差异意味着 RAM 与缓存有关，但也可能意味着 list-s 上的执行不佳)