何時選擇關鍵值數據的std :: map over std :: map？

考慮到在主內存中搜索時緩存和數據局部性的積極影響，我傾向於使用std::vector<>和std::pair<>類似的鍵值項目，並對兩者執行線性搜索，如果我知道鍵值項目的總數將會永遠不要「太大」來嚴重影響性能。何時選擇關鍵值數據的std :: map over std :: map？

最近我一直在很多情況下我事先知道，我將有鍵值項的數額巨大，因此都選擇了std::map<>從此開始。

我想知道如何在上述情況下爲適當的容器做出決定。

你

始終使用std::vector<>（或類似）？
始終使用std::map<>（或類似）？
對於產品數量範圍內的哪一個比另一個更可取？
東西完全不同嗎？

謝謝！

來源

2010-04-27 Johann Gerell

我很少使用std::vector與線性搜索（除了與二進制搜索相結合，如下所述）。我認爲對於數據量足夠小的數據來說會更好，但對於那些小數據來說，任何事情都不可能提供巨大的優勢。

根據使用模式，std::vector上的二進制搜索可能有意義。當您需要在使用過程中定期更新數據時，A std::map可以很好地工作。然而，在很多情況下，您會加載一些數據然後使用這些數據 - 但是在您加載數據之後，它大部分保持靜態（即，如果有變化，它幾乎不會變化）。

在這種情況下，將數據加載到矢量中，必要時對其進行排序，然後對數據執行二分搜索（例如std::lower_bound,std::equal_range）可能具有很大意義。這幾乎是兩全其美的 - 低複雜度的二進制搜索和從高參考位置（即，該矢量是連續的，與std::map的鏈接結構相反），良好的高速緩存使用。當然，缺點是插入和刪除速度很慢 - 但這是我用過原始想法的一次 - 分別存儲新插入的數據，直到達到某個限制，然後纔將其與其餘的數據，所以單個搜索包括對數據主體的二進制搜索，然後是對（少量）新插入的數據進行線性搜索。

來源

2010-04-27 15:30:41

我永遠不會僅僅在「效率」的基礎上作出選擇（但可能是假的），但總是以我實際上對容器做的事情爲準。我想存儲重複嗎？廣告訂單是否重要？我有時會想要搜索的價值不是關鍵？那些東西。

來源

2010-04-27 15:27:50

我幾乎總是更喜歡使用map（或unordered_map，當散列容器變得更有意義）與矢量。

這就是說，我認爲你的推理是倒退的。當存在大量數據時，我會傾向於使用向量，因爲向量將佔用更小的內存空間，所以只有。

使用正確的數據集類型，您可以加載矢量，然後對其進行排序並進行二進制搜索，以較小的覆蓋區和與地圖類似的性能特徵，尤其是在數據集加載後穩定的情況下。

來源

2010-04-27 15:30:24 Joe

你有沒有考慮過使用排序後的數據結構？他們傾向於提供對數搜索和插入 - 一個合理的折衷。就我個人而言，除了喜歡地圖之外，我沒有任何硬性規則和快速規則來輸入可讀/可理解的值。

當然，還有很多關於地圖與列表/矢量（已排序和未排序）效率的討論 - 如果您的密鑰是一個字符數爲10,000個字符的字符串，則比搜索要花費更長的時間通過一個只有幾個項目的列表，所以你要確保你可以有效地比較密鑰。

來源

2010-04-27 15:30:37 awshepard

爲什麼不考慮unordered_map？

來源

2010-04-27 15:30:56

@Nemanja：因爲我通常在一個嚴重癱瘓的Windows CE/Mobile環境中工作，在這個環境中，TR1太費時，至少說要集成。 – 2010-04-27 15:40:14

何時選擇關鍵值數據的std :: map over std :: map？

回答

相關問題