用更合適的類代替`std :: vector`

我最近從頭開始編寫我的第一個程序，但不是該領域的專業人員，我擔心我可能沒有使用最合適的解決方案。用更合適的類代替`std :: vector`

在我的程序中，我必須使用不斷添加和刪除元素的對象列表（以及列表清單），而不必在列表的開頭或結尾。
使用指針列表不是一個選項，提供了需求。

當我開始時，我知道只有std::vector類，因此我使用它，儘管知道它需要連續的內存，因此這種選擇會導致重複的重新分配。
在嘗試解決另一個問題時，我發現還有其他類可能更適合此任務，如std::list和std::deque。

我主要是通過使用索引

myvector[index].function();

的，並且我用的是最標準的功能訪問的對象是

myvector.size(); 
myvector.begin(); 
myvector.pop_back(); 
myvector.push_back(); 
myvector.insert(myvector.begin()+offset, number, new_element);

，我還沒有任何重載函數/操作員。

你能爲我的範圍建議最好的容器/雙向鏈表嗎？
是否有可能將std::vector無縫替換爲其他標準容器？
我有什麼特別的問題需要注意？

來源

2013-06-05 Federico

大多數'std :: vector'實現都非常聰明，並且預分配內存，所以每次添加或刪除元素時都不需要重新分配內存。在擔心性能之前，* benchmark *！ –

是的，所有的標準容器都有幾乎相同的界面，所以換個基準測試應該很容易。我還推薦參考[如此]（http://en.cppreference.com/w/cpp/container）（您可以在其中找到每個容器支持的定位表）。 –

[std :: vector vs. std :: list vs std :: slist？]的相對性能可能重複（http://stackoverflow.com/questions/238008/relative-performance-of-stdvector-vs-stdlist -vs-stdslist） – TemplateRex

你能爲我的範圍建議最好的容器/雙向鏈表嗎？

如果按索引訪問元素，鏈表不是一個好的解決方案：你必須從頭開始遍歷列表，所以它是一個O（N）操作。由於這個原因，std::list和std::forward_list在它們的界面中沒有這種訪問。

是否有可能無縫地用任何其他標準容器替換std :: vector？

不與std::list，因爲它沒有索引訪問。 std::deque可能是合適的，但只有當你不依賴於基礎數據在一個連續的塊是（我假設你不這樣做，因爲你是問鏈表）

是否有特殊的問題，我必須注意？

與表現一樣，您應該首先確定您是否有問題。如果您遇到性能問題std::vector，則嘗試其他方法，並且衡量在實際運行情況下的性能差異。不同容器的性能特點可能非常直觀，因此測量在這裏特別重要。相關鏈接：std::vector vs. std::list vs. std::deque comparison。 Bjarne Stroustrup的Going Native 2012 keynote speech。

來源

2013-06-05 07:29:17 juanchopanza

感謝您的答案！「如果您按索引訪問元素，鏈接列表不是一個好的解決方案」 - >您能否提出替代方案？（在訪問端）這裏的主要問題是對象的大小，每當我創建一個新對象時都需要一塊體面的內存。 – Federico

@Federico我的替代方案是使用'std :: vector'，除非我100％確定存在問題。然後嘗試使用'std :: deque'。如果仍然存在問題，要麼重新設計類型，以便移動便宜並且尺寸較小（例如，像大多數標準庫類型那樣，它們會包裝一些動態分配的內存）。或者存儲你的類型的'std :: unique_ptr'。 – juanchopanza

注意：當插入到中間時，「std :: deque」與「std :: vector」幾乎一樣差（與潛在地所有元素相比，最多移動元素的一半）。 –

Boost提供了一種替代方案：boost::stable_vector。

大O複雜度對於所有操作都是嚴格相同的，但是在內部它不會洗牌元素，而是指針（以損失連續性爲代價）。

對於一個額外的間接的在每個接入成本，stable_vector在兩種情況下一個很好的選擇：你希望有一個穩定的地址元素

，這樣你就可以保持一個引用/指針它
元素是極其昂貴的拷貝，所以要保證不復制將於無論你正在做

後者的操作應以探查指出的問題得到證實，obviousl年。

來源

2013-06-05 08:04:34

用更合適的類代替`std :: vector`

回答

相關問題