std :: list vs std :: vector iteration

Question

据说,迭代遍历向量(如在读取所有元素时)比迭代遍历列表更快,因为优化了缓存.

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

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

这背后的想法是我想以某种不会改变的顺序存储元素.我仍然需要能够在运行时快速插入一些,但是大多数仍然是连续的,因为顺序不会改变.

元素是连续的这一事实是否会对缓存产生影响,或者因为我仍然会调用它list_element->next而++list_element不是改进它？

Answer 1

由于数据结构的紧凑表示，高速缓存一致性所带来的效率提升可能相当显着。就向量而言，与列表相比，紧凑表示不仅对于读取更好，对于某些特定架构的元素插入（在向量中移位）也更好，如 Bjarne 的本文图 3 所示斯特鲁斯特鲁普：

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

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

我认为，如果这是您的程序的关键因素，您应该在您的架构中对其进行分析。