C++向量和列表插入

有誰知道爲什麼插入一個元素到列表中間比向元素中插入一個元素更快？C++向量和列表插入

我更喜歡使用矢量，但如果可以，我被告知使用列表。任何人都可以解釋爲什麼？而且它總是建議使用矢量列表嗎？

2013-04-25 user2310042

鏈表和數組的本質是任何程序員（任何語言）必須瞭解。我會建議獲得一個[很好的C++書]（http://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list）這將有答案這個問題（和更多）。 – 2013-04-25 01:58:01

如果我逐字逐句提問，找到一個數組的中間（std :: vector）是一個簡單的操作，可以將長度除以2，然後向上或向下四捨五入以獲得索引。查找雙向鏈表（std :: list）的中間需要遍歷所有元素。即使你知道它的大小，你仍然需要走過一半的元素。因此，std :: vector比std :: list更快，換言之，一個是O（1），另一個是O（n）。

插入一個已知的位置需要對數組的相鄰元素進行shuffing，並在另一個節點中鏈接一個雙向鏈表，正如其他人在這裏所解釋的那樣。因此，具有O（1）的std :: list比具有O（n）的std :: vector更快。對於數組，O（1）+ O（n）爲雙向鏈表，O（n）+ O（1）爲雙向鏈表，使得插入中間的O（n + 1） n）兩種容器類型。所有這些都遺漏了諸如CPU緩存和分配器速度之類的東西，它只是比較「簡單」操作的數量。總之，你需要了解你如何使用容器。如果你真的在隨機位置插入/刪除很多，std :: list可能會更好。如果你很少這麼做，然後只讀取容器，std :: vector可能會更好。如果你只有十個元素，那麼所有的O（x）都可能毫無價值，你應該選擇一個你最喜歡的元素。

來源

2013-04-25 06:25:20

插入到矢量的中間需要插入點之後的所有元素進行混洗以形成空間，這可能涉及大量複製。

該列表實現爲鏈接列表，每個節點佔用自己的內存空間並引用相鄰節點，因此添加新節點只需要更改2個引用即可指向新節點。

根據您使用的數據類型，向量的執行速度可能比列表快得多。但是複製的對象越複雜，矢量越糟糕。

來源

2013-04-25 01:56:40 Kylotan

簡而言之，矢量是一個數組。因此，它的元素被存儲在連續的存儲器位置（即一個緊挨着另一個）。唯一的例外是矢量允許在運行時調整大小，而不會導致數據丟失。

現在，要插入到列表中，您需要標識該節點，然後創建新元素（內存中的任何位置），存儲該值並連接指針。

但是在矢量（數組）的情況下，您必須物理地將元素從一個單元移動到另一個單元，以便爲新元素創建空間。這種物理移動是造成延遲的原因，特別是如果需要移動許多元素（即數據）。你不是在物理上移動數組元素。而是它的內容。

來源

2013-04-25 01:58:55 itsols

@ValekHalfHeart在C++中，'std :: vector'是使用底層的動態分配數組實現的。標準的要求使得這是唯一可能的實現。 – 2013-04-25 02:05:27

Ulrich Eckhardt的回答很不錯。我沒有足夠的聲望來添加評論，所以我會自己寫一個答案。就像烏爾裏奇所說的那樣，列表和向量的插入速度在理論上都是O（n）。在實踐中，現代CPU有一個叫做「預取器」的東西。它在獲取連續數據方面非常出色。由於矢量在內存中是連續的，因爲預取器，移動很多元素非常快。你需要操縱真正的，非常大的載體，以便插入比列表慢。有關詳情，請這真棒博客文章：

http://gameprogrammingpatterns.com/data-locality.html

來源

2017-02-02 11:57:38

C++向量和列表插入

回答

相關問題