STL向量vs列表：對圖鄰接列表最有效？

當push_back時，列表消耗大部分時間分配內存。另一方面，當需要調整大小時，矢量必須複製它們的元素。因此，哪個容器對於存儲鄰接列表最有效？STL向量vs列表：對圖鄰接列表最有效？

2011-03-26 Alexandros

誰說向量做副本？ – quasiverse 2011-03-26 06:22:39

@quasiverse：對「vector」的要求本質上需要一個副本，隨着它的增長。 'vector's需要連續存儲它們的元素。在添加元素時，最終會佔用分配的空間，在下一次添加時，您將獲得新內存分配，然後是當前元素的副本到新空間，然後是舊空間的釋放。 – 2011-03-26 07:51:18

我不認爲這可以絕對肯定地回答。儘管如此，我估計至少有90％的可能性會讓載體變得更好。鄰接列表實際上比許多應用程序更傾向於使用矢量，因爲鄰接列表中的元素順序通常不重要。這意味着當你添加元素時，通常是在容器的末尾，當你刪除一個元素時，你可以先將它換到容器的末尾，這樣你只能在最後添加或刪除。

是的，矢量在擴展時必須複製元素，但實際上這幾乎不是一個實質性的問題。特別是，矢量的指數擴展率意味着元素被複制的平均次數趨於恆定 - 在典型的實施中，該常數大約爲3.

如果您處於某種情況誠實的複製是一個真正的問題（例如，複製元素是非常昂貴的），我的下一個選擇矢量仍然不會列出。相反，我可能會考慮使用std :: deque。它基本上是指向對象塊的向量。它很少需要複製任何東西來進行擴展，在罕見的情況下，它只需要複製指針而不是對象。除非你需要deque的其他獨特功能（在任何一端的常量時間插入/刪除），矢量通常是更好的選擇，但即使如此，deque幾乎總是比列表更好的選擇（即矢量通常第一個選擇，相當接近的第二個選項，並列出相當遙遠的最後一個）。

來源

2011-03-26 06:47:08

答案取決於用例。 P.S. @quasiverse - 當你隱式或顯式地「:: reserve」內存耗盡時，向量調用realloc

如果你有一個不斷變化的鄰接列表（插入和刪除），列表將是最好的。如果你有一個或多或少的靜態鄰接列表，並且大部分時間你正在進行遍歷/查找，那麼一個向量會給你最好的性能。

來源

2011-03-26 06:28:23 Sandeep

STL容器沒有嚴格定義，因此實現方式各不相同。如果你非常小心，你可以編寫代碼，以便它不關心它是一個矢量還是一個正在使用的列表，你可以試着看看哪個更快。考慮到緩存效果等的複雜性，以任何精度預測相對速度幾乎是不可能的。

來源

2011-03-26 06:29:58

您可以添加第三個選項到這個比較：帶有專門分配器的列表。

使用分配器爲固定大小的小對象可能會大大提高分配/釋放的速度...

來源

2011-03-26 07:23:56 maxim1000

STL向量vs列表：對圖鄰接列表最有效？

回答

相關問題