1. 首頁
  2. 問答
  3. std :: vector與std :: list與std :: slist的相對性能？

std :: vector與std :: list與std :: slist的相對性能？

2008-10-26 97 views
42

對於使用std::list代替std::vector而言，對列表元素的隨機訪問不是必需的簡單鏈接列表，是否有任何顯着的優勢（性能或其他）？如果需要向後遍歷，在迭代元素之前使用std::slist和reverse()列表會更有效嗎？std :: vector與std :: list與std :: slist的相對性能？

來源

2008-10-26 An̲̳̳drew

+8

（晚評論，只是備案）：鏈接到由Bjarne Stroustrup的演講： 「爲什麼你應該避免鏈接列表」，他聲稱向量總是比列表好。他給出的原因是，平均而言，插入點的搜索主宰了努力，而元素（向量中）的移動在比較*中是微不足道的。另外：緩存未命中，但已在下面的答案中提到。視頻：http：//www.youtube.com/watch？v = YQs6IC-vgmo – 2014-01-16 13:04:23

+1

即使列表幾乎總是比向量慢（除了進行高級拼接時），有一次您絕對需要一個列表：stable迭代器。如果你需要保留迭代器的副本，它總是指向相同的元素（除非被移除），這不是一個保證向量可以提供的（例如，對push_back的調用可以使所有迭代器失效）。使用內存池可以使列表的速度更接近矢量的速度。 – coderforlife 2014-07-01 22:00:35

回答

52

像往常一樣，性能問題的最佳答案是profile這兩個實現爲您的用例，看看哪個更快。

一般來說，如果你有插入到數據結構（比在端部以外）然後vector可能比較慢，否則在大多數情況下vector預計表現比list更好，如果只爲data locality issues，這意味着，如果兩個數據集中相鄰的元素在內存中相鄰，那麼下一個元素將已經在處理器的緩存中，並且不必將內存錯誤地分頁到緩存中。

同時請注意，對於vector空間開銷是恆定的（3個指針）而用於list空間開銷支付對於每個元件，這也降低了滿元件（數據加上開銷），其可以駐留在數在任何時候在緩存中。

來源

2008-10-26 13:41:22 Motti

+5

還要記住，即使插入的矢量比鏈接列表中的插入速度快，如果要插入的位置必須被搜索。例如，取一堆隨機整數並將它們按排序順序插入到矢量或鏈接列表中 - 無論項目總數如何，矢量總是會更快，這是因爲在搜索插入點時緩存未命中鏈表。 – Collin 2012-09-29 22:45:24

+6

幾乎所有鏈接列表更快的是當你進行大量拼接時，因爲它不涉及大量的緩存未命中，並且每個拼接都是一個常量操作（可以移動大量的從一個鏈接列表到另一個鏈接的項目）。 – Collin 2012-09-29 22:47:53

+0

「還要記住，矢量的空間開銷是不變的」只有當你非常小心。對於隨意使用，它具有線性空間開銷，與「列表」相同。請參閱：分期付款線性push_back。 – 2017-03-13 21:46:24

11

只是沒有。 List比Vector有優勢，但順序訪問不是其中之一 - 如果這就是你所做的一切，那麼向量就更好了。

但是，添加附加元素比列表更加昂貴，特別是在中間插入時。

瞭解如何實現這些集合：矢量是一個連續的數據數組，一個列表是一個包含數據和指向下一個元素的指針的元素。一旦你明白了，你就會明白爲什麼列表適合插入，並且不適合隨機訪問。

（所以，向量的反向迭代與正向迭代完全相同 - 迭代器每次只減去數據項的大小，列表仍然必須通過指針跳到下一個項）

來源

2008-10-26 13:41:22 gbjbaanb

4

如果您需要向後遍歷，slist不太可能成爲您的數據結構。

傳統（雙向）鏈接列表爲您提供恆定的插入和刪除時間在列表中的任何位置;一個向量只能在列表末尾提供分期固定的時間插入和刪除。對於一個矢量插入和刪除時間是線性的，而不是結束。這不是全部內容;也有不變的因素。矢量是一個更簡單的數據結構，根據上下文具有優點和缺點。

瞭解這一點的最好方法是瞭解它們是如何實現的。鏈表爲每個元素都有一個下一個和一個前一個指針。一個向量有一個由索引尋址的元素數組。由此可以看出，兩者都可以進行高效的前向和後向遍歷，而只有向量可以提供高效的隨機訪問。你也可以看到鏈表的內存開銷是每個元素，而向量則是不變的。你也可以看到爲什麼兩個結構之間的插入時間不同。

來源

2008-10-26 13:42:31 janm

21

在C++中想到的默認數據結構是向量。

考慮以下幾點......

1]穿越：
列表節點都是在內存中到處散佈，因此列表遍歷導致高速緩存未命中。但矢量的遍歷是平滑的。

2]插入和刪除：當你這樣做的矢量，但緩存是在那個非常好
元素的平均50％必須移位！但是，用列表，你需要遍歷到插入/刪除的點...所以再次...緩存未命中！ 令人驚訝的是矢量贏得這種情況！

3]存儲：
當您使用列表中，每個元素（向前向後&）2個指針這樣一個列表比矢量大得多！ 向量只需要比實際元素需要更多的內存。

Yout應該有一個理由不使用一個向量。

參考： https://youtu.be/0iWb_qi2-uI?t=2680

來源

2013-01-25 16:45:23 Sam

4

的話題有些嚴格的基準： http://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html

如已被別人注意的，連續的內存存儲裝置STD
我在耶和華了Bjarne Stroustrup的的談話得知這個： ：矢量對大多數事物都更好。實際上沒有什麼好的理由使用std :: list，除了少量的數據（它們都可以放入緩存中）和/或擦除和重新插入頻繁的地方。 複雜性保證與高速緩存和主內存速度（200x）之間的差異以及連續內存訪問如何影響高速緩存使用率之間的差異與實際性能無關。見錢德勒卡魯斯（谷歌）談論這裏的問題： https://www.youtube.com/watch?v=fHNmRkzxHWs

這裏邁克阿克頓的數據化設計的談話： https://www.youtube.com/watch?v=rX0ItVEVjHc

來源

2016-04-02 07:35:37 metamorphosis

相關問題

 相關問題