動態數組寬度ID？

Question

我需要某種在C++中的動態數組，其中每個元素都有一個int表示的自己的id。

數據類型需要這些功能：

• INT插入（） - 返回ID
• 刪除（INT ID）
• 獲取（ID） - 返回元素

什麼數據類型應我用？我查看了矢量和列表，但似乎無法找到任何類型的ID。另外我看了一下地圖和hastable，這些可能是有用的。但我不知道該選什麼。

Answer 1

A std::map可以爲你工作，它允許將一個鍵與一個值相關聯。 密鑰將是您的ID，但在將元素添加到地圖時應自己提供。

散列表是一種可用於實現無序映射的基本機制。它對應於std :: unordered_map。

Answer 2

看來最好使用的容器是unordered_map。 它基於哈希。您可以插入，刪除或搜索O（n）中的元素。

目前unordered_map不在STL中。如果你想使用STL容器使用std :: map。 它基於樹。插入，刪除和搜索O（n * log（n））中的元素。

容器的選擇依賴於使用強度。例如，如果你會發現罕見的元素，矢量和列表可以確定。這些容器沒有find方法，但<algorithm>庫包含它。

Answer 3

我可能會使用一個向量和空閒id列表來處理刪除，然後索引是id。這是非常快的插入和獲取，並相當容易管理（唯一的竅門是免費清單刪除項目）。

否則，您可能想要使用地圖，並跟蹤最低未使用的ID並在插入時指定它。

Answer 4

A vector給出恆定時間隨機存取，「id」可以簡單地是向量中的偏移（索引）。 A deque與此類似，但不會連續存儲所有項目。

如果ID值可以從0開始（或從0開始的已知偏移量並單調增加），這兩種方法都適用。隨着時間的推移，如果有大量的清除，vector或deque可能會變得稀疏，這可能是有害的。

std::map不存在人口稀少的問題，但外觀從常量時間變爲對數時間，這可能會影響性能。

boost::unordered_map可能是最好的，因爲作爲散列表的最佳情況可能具有給出該問題的最佳總體性能特徵。但是，可能需要使用boost庫，但如果在STL實現中可用，還可以使用std::tr1中的unordered容器類型。