搜索和更新整數值列表的最快數據結構是什麼？

我必須維護無序整數的列表，其中整數的數量是未知的。它可能在一段時間內增加或減少。我需要經常更新這個整數列表。我曾嘗試使用矢量。但它真的很慢。數組似乎更快，但由於列表的長度不固定，調整大小需要花費大量時間。請建議任何其他選項。搜索和更新整數值列表的最快數據結構是什麼？

2013-04-02 rwik

我傾向於喜歡這張圖片：http://www.liamdevine.co.uk/code/images/container.png – Nbr44

您是否考慮過使用排序/搜索樹？ –

你能更清楚你的要求嗎？「更新」究竟包含什麼？ –

如果值的順序不重要，則使用hash table。時間是O（1）。我很確定你會在標準模板庫中找到一個實現。

如果不成功，那麼splay tree的速度會非常快，尤其是如果您想保持訂購清單的順序：每次操作的O（ln n）的攤銷成本以及非常低的常數因子。我認爲C++ stdlib映射是這樣的。

瞭解你的數據結構。

2013-04-02 06:17:37

-1

std :: list絕對是爲這樣的問題而創建的，添加和刪除列表中的元素不需要像向量中那樣進行內存重新分配。但是，由於列表的非交換內存分配，搜索元素可能被證明是一種痛苦的體驗，但如果您不經常搜索它的條目，則可以使用它。

2013-04-02 06:22:28

在我看來，可怕的是在履行OP對性能要求的「搜索」部分。 – WhozCraig

如果順序數據結構無法滿足要求，可以嘗試查看樹（二進制，AVL，m-way，紅黑等）。我建議你嘗試實現AVL樹，因爲它會產生一個平衡或接近平衡的二叉搜索樹，它可以優化你的操作。有關AVL樹的更多信息：http://en.wikipedia.org/wiki/AVL_tree

2013-04-02 06:26:16

好吧，deque沒有調整大小的成本，但是如果它是無序的，它的搜索時間是線性的，並且它的自身中間的刪除和插入操作時間甚至比向量值得。
如果您不需要按數字值搜索，hashmap或map可能是您的選擇。不調整成本大小，然後您將地圖的關鍵字設置爲數字的索引，並將值設置爲數字的值。搜索和插入操作比線性更好。

2013-04-02 06:31:36 JoeyMiu

如果你有興趣動態增量的數組大小，你可以做到這一點。

current =0; 
x = (int**)malloc(temp * sizeof(int*)); 
x[current]=(int*)malloc(RequiredLength * sizeof(int));

所以元素添加到陣列，當件充滿在X [當前] 您可以通過執行

x[++current]=(int*)malloc(RequiredLength * sizeof(int));

做這個元素添加更多的空間可以容納RequiredLength多個元素。

可以重複此高達1024倍，這意味着1024 * RequiredLength元素可以

容納，這裏給你機會，增加數組的大小，只要你想它。

您可以隨時通過X [n/1024] [n％1024]訪問第n個元素;

2013-04-02 08:14:12 MissingNumber

考慮到您的意見，它看起來像是std::set或std::unordered_set適合您的需求比std::vector更好。

2013-04-02 08:48:08 ogni42

用'std :: set'（和'std :: unordered_set'）可以解決的一個問題是關於內存;一個'std :: vector'在內存中非常緊湊，非常適合小型集合。 –

@MatthieuM。：你說的對，但是開線程序應該決定是換內存換速度，反之亦然。從我認爲的意見，這是插入操作導致性能問題時尋找重複（在Vector中搜索是O（n）在設置它是O（日誌n） – ogni42

我同意;問題顯然是缺乏..實際上，我提出了你的答案，因爲它推薦了容器具有最好的語義來解決手頭的問題;措施將告訴你它們是否表現得不錯。 –

回答