要使用哪個STL容器？

Question

我應該使用哪個STL容器如果：

1. 數據被定期插入和移除。
2. 定期隨機訪問數據。

E.g：數據集（4,10,15），如果我想找到最接近的號碼9，那麼它應該返回我10

1. 我只存儲一個整數。
2. 它需要進行排序
3. 可以到100K的數據集

我想用載體，但載體插入和刪除是昂貴的。

vector<int> 

如果我要使用列表，我將不得不訪問O（n）元素才能到達數據。

list<int> 

我在考慮使用設置爲這將是很好的，如果它被分類了，但是我不是很肯定的效率使用SET

所以我希望有人可以給一個很好的解決方案！

Answer 1

我認爲你應該檢查該SO職位：In which scenario do I use a particular STL container?對於小尺寸的載體將不論你打算做什麼，適合大多數場景。

雖然圖表是一個指導，但定期訪問容器並不會影響容器的選擇，除非您關心容器的大小，否則存儲int的事實並不重要，在這種情況下，開銷列表容器或地圖中的指針對你有影響嗎？

排序是通過映射自動完成的，但如果容器大小足夠小以適應內存，則對矢量和列表進行排序可以非常快速。

數據插入針對容器中任何位置的列表和地圖進行了優化，對於地圖，您可以獲得將自行排序的好處，但是如果大小足夠小，那麼使用新條目構建新矢量的速度可能會很快。

您可能還想要考慮哈希映射，您仍然最好分析您的代碼，嘗試第二次猜測什麼是最優的取決於您的使用情況，您確實需要測量和配置文件。

您也可以決定STL <map>是一個足夠好的餘額或<set>並使用這些容器，因爲它們在插入和刪除時自動排序並且查找速度很快，但是維護每個條目中指針的開銷與矢量相比，使用的內存大小增加，如果你不關心這個，那麼你可以考慮這些容器。

如果它很重要，然後測試和配置文件，並比較每個容器的性能，你會驚訝於代碼將如何對你的假設執行。

Answer 2

對於你的問題的答案完全取決於你的數據集的大小，因爲列表增長到巨大的尺寸，線性遍歷到達需要移除/插入的元素所需的時間遠遠超過了矢量去除/插入所需的時間。 因此，如果您的數據集很小，請使用列表，如果它很大，則使用矢量。

Answer 3

如果需要進行排序，使用二叉搜索樹

Answer 4

一個集合足夠高效地插入/刪除/訪問，並且它總是被排序。唯一要考慮的事情是，在集項是常數（因此排序沒有損壞），因此改變，你應該刪除，更新和插入

Answer 5

如果要求就是性能，應選擇基本上一直是一std::vector。它避免了基於節點的數據結構（樹和列表）的許多內存分配，它利用空間局部性進行更有效的遍歷。

當然，在向量的中間插入/移除需要移動元素，但即使這樣也很少使得向量比其他數據結構慢。

我看到使用其他的數據結構的唯一的真正原因是這些：

• std::map/std::set：這些都是偉大的方便。尼斯和易於使用的，所以如果不需要最佳性能比較，我用這些當我需要一個排序容器或鍵/值映射。 （爲了獲得最佳性能，排序後的向量可能更可取）
• 所有其他容器：可能對正確性有用保證提供面對修改：向量經常重新分配並移動其內容，這會使指針和迭代器到矢量中。其他的數據結構提供更強的保證有（爲一個deque，指針被保證在端部插入/移除後後留下有效的，但迭代可能仍然無效。對於list，set和map，兩個指針和迭代器被保證留在插入/移除期間有效）

當然，這些只是經驗法則。

當涉及到性能時，唯一普遍適用的規則是「自己進行基準測試」。我可以告訴你一個vector通常在許多常見場景下的表現如何，但我不能告訴你它是如何在你的代碼中執行的，你的編譯器和你的標準庫。所以如果你擔心表現，就衡量它。嘗試不同的選擇，並看看哪個更快。