爲什麼數組被認爲比STL容器更好？

array與std::queue，這在時間上更好，爲什麼？爲什麼數組被認爲比STL容器更好？

我寫了一個圖形處理算法，其中邊界頂點存儲在std::queue中，並使用push_back()和pop_front()來訪問。當我重新實現前端和前端指針指向邊界頂點開始和結束的陣列時，我獲得了更好的時間結果。對於數據量足夠大的數組，數組是否真的比隊列更快？

來源

2016-09-21 Bibek Bhattarai

您正在比較蘋果和橘子。如果你需要一個隊列結構，爲什麼要使用不是隊列的東西？ – NathanOliver

訪問數組中和矢量中的元素都是O（1）。時間差異，如果有的話，可以忽略不計。 *不同*是向量是*動態*，當您向矢量添加元素時，可能需要調整其自身的大小，其中包括複製現有數據。這可能很慢。如果您大致瞭解所需元素的數量，則可以爲矢量預留該數量，速度差可以回到幾乎爲零。如果你想要一個具有編譯時固定數量的元素的容器，請改用'std :: array'。 –

一個是靜態的，另一個是動態的。 –

對於大多數機器來說，數組速度更快，因爲數組的連續元素可以加載到同一個高速緩存行（或者預先加載到高速緩存中）。由於L1緩存讀取速度比主存儲器訪問速度快200倍，因此任何需要獲取指針的內容都可能不在緩存中，並且需要更長的主內存獲取週期。

https://www.youtube.com/watch?v=YQs6IC-vgmo

來源

2016-09-21 17:28:08 Gregg

std :: queue的實現傾向於分配增加大小的連續內存塊（例如，前16個元素的塊，然後是他下32個元素的塊），其大小或高於高速緩存行大小。所以區別在於後續緩存未命中是否連續，這通常不會產生影響。 –

爲什麼數組被認爲比STL容器更好？

回答

相關問題