Vector vs Deque插入中間

我知道deque比更有效當插入位於前端或末端時，如果我們必須執行指針運算，則向量更好。但是當我們必須在中間執行插入時使用哪一個？和爲什麼。？Vector vs Deque插入中間

2012-09-14 user1543957

德克可能不是更有效率，特別是如果只有少量的元素。 –

對於相對較小的廉價複製對象集合，無論操作如何，「矢量」都會擊敗其他容器。（對於最多12個字符的FIFO，我測量了'vector '與'deque '，儘管'deque'針對此利用率進行了優化，但我測試的機器上的「矢量」速度明顯更快。） –

你可能會認爲， deque會有優勢，因爲它將數據分解爲塊。但是要在不變的時間內執行operator[]，則需要所有這些塊的大小相同。在中間插入或刪除元素仍然需要移動一側或另一側的所有值，與vector相同。由於vector更簡單，並且具有更好的緩存位置，因此它應該超前。

來源

2012-09-14 14:51:55

的Deque仍然會更有效率，因爲它不具有一半的數組的每次插入一個元素一次移動。

當然，如果你考慮大數的元素，甚至比最好是運行一個基準，看看哪一個更符合特定情況下，這隻會真正的問題。請記住，premature optimization is the root of all evil。因爲它通常作爲連續的數據塊的連接的序列來實現，而不是在一個std::vector中使用的單塊大容器

來源

2012-09-14 14:39:06 Qnan

除非你在其中一端插入，'deque'將需要移動一些元素：或者在插入之前，或者在插入之後。 –

@JamesKanze是真實的，但通常只有有限的幾個人將被移動。我敢肯定它不會像矢量一樣是所有元素的一半。 – Qnan

std::deque

可以更好的表現。因此，在中間插入會導致從一個地方複製到另一個地方的數據更少，並且可能會減少重新分配。

當然，無論是重要與否取決於容器的大小和複製存儲元件的成本。隨着C++ 11移動語義，後者的成本並不重要。但最終，唯一的方法就是用現實的應用程序進行分析。

來源

2012-09-14 14:43:08 juanchopanza

我同意，但應該指出，第1段中的連續數據塊是邏輯的，而不是物理的。 OP應該更多地研究物理佈局，以充分理解插入物的分支 – WhozCraig

正如Doug T.對我的回答所指出的那樣，這是錯誤的。如果你在接近開始的位置插入，'deque'_could_只能在插入前移動元素，因此移動的時間少於'vector'。但是，我不知道是否有任何實現實際執行此操作，並且無論如何，它必須在插入的一側（無論是在之前還是之後）移動_all_元素。 –

@JamesKanze也許我的回答差勁。我對你說的沒有不同意見。我的觀點是，所有要移動的元素更可能是「」deque「」的一個小於「」矢量「」的數字。 – juanchopanza

與標準庫容器的選擇標準時，您可以選擇取決於容器：

數據類型要存儲&
類型要對數據進行操作。

如果您想在中間執行大量插入操作，使用std::list會更好。

如果選擇是隻是之間的std::deque和std::vector再就是要考慮許多因素：

通常，存在在雙端隊列存取元件的情況下，一個以上的間接，因此元件訪問並且deques的迭代器移動通常比較慢。
在具有用於存儲塊大小限制的系統中，雙端隊列可能包含更多的元素，因爲它使用的存儲器多於一個塊。因此，對於deques，max_size()可能更大。
Deques不提供支持來控制容量和重新分配的時刻。在特別地，任何插入或大於在開始或結束其它元素的刪除無效引用該雙端隊列的元素的所有指針，引用和迭代器。然而，再分配可以執行比矢量更好，因爲根據他們的典型的內部結構，雙端不必複製上重新分配的所有元素。內存
塊時，他們不再使用可能會釋放，所以雙端隊列的內存大小可能萎縮（這不是由標準強加的條件，但大多數實現做）

來源

2012-09-14 14:45:14

這並不像看起來那麼明顯。在現代架構中，'std :: list'效率非常低，一般來說，由於它的地理位置較差，並且如果內容的拷貝便宜，插入到vector的中間可能會更快，儘管拷貝。 –

此外，'deque'的內部結構要求它至少複製插入的一側上的所有元素，如果插入不在結尾。（更一般地說，可以說'vector'需要在插入之後移動所有元素，而'deque'需要移除之前或之前的所有元素之前的所有元素。） –

Vector vs Deque插入中間

回答

相關問題