std :: list vs std :: vector迭代

Question

據說遍歷一個向量（就像讀取它的所有元素一樣）比迭代遍歷列表要快，因爲優化了緩存。

網絡上是否有任何資源可以量化它對性能的影響？

此外，使用自定義鏈接列表會更好嗎，哪些元素將被預先定位以便它們在內存中連續？

背後的想法是，我想存儲元素的順序不會改變。我仍然需要能夠在運行時迅速插入midle，但其中大部分仍然是連續的，因爲順序不會改變。

請問這些元素是否連續的事實對緩存有影響，還是因爲我仍然會調用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

不知道如果我能解釋正確的，但這裏是我的觀點（我沿着下面:)翻譯機器指令的思路思考，

矢量迭代器（連續內存）： 當你增加一個矢量迭代器，迭代器的值只是將對象的大小（在編譯時已知）添加到指向下一個對象。在大多數CPU中，這最多隻有一條到三條指令。

列表迭代器（鏈表http://www.sgi.com/tech/stl/List.html）： 當你增加一個列表迭代器（尖銳的物體），前向鏈路的位置增加了一些數字對象的基地設指出，然後裝起來的迭代器的新值。有多個內存訪問，比矢量迭代操作慢。

Answer 3

向量和列表之間的主要區別在於向量元素隨後在預先分配的緩衝區內構建，而列表中的元素是逐個構建的。 因此，向量中的元素被授予佔用連續的內存空間，而列表元素（除非某些特定情況，如自定義分配器以這種方式工作）不被授予如此，並且可以「稀疏」記憶。

現在，由於處理器在重新映射主存儲器的整個頁面的高速緩存上（可以高達主RAM的1000倍）運行，所以如果元素是連續的，則它們很可能適合相同的存儲器頁面，並因此在迭代開始時被全部移到緩存中。在繼續進行的過程中，所有事情都發生在緩存中，而無需進一步移動數據或進一步訪問較慢的RAM。

使用list -s，由於元素在每個地方都是稀疏的，因此「進入下一個」意味着引用的地址可能不在其先前的同一個內存頁中，因此緩存需要在每次更新時更新迭代步驟，在每次迭代中訪問速度較慢的RAM。

性能差異很大程度上取決於處理器和用於兩個主RAM和高速緩存的存儲器的類型，並且在途中std::allocator（並且最終operator new和malloc）被實現的，所以一般的數量是不可能給予。 （注意：差異很大意味着壞RAM對緩存的尊重，但也可能意味着在列表上執行錯誤）