哈希映射，字符串比較和std :: map？

首先，我想提出一些我認爲是正確的觀點。請問這些可以驗證嗎？哈希映射，字符串比較和std :: map？

哈希映射存儲串由將它們轉換成一個整數不知。
std :: map不是一個哈希映射，如果我使用字符串，我應該考慮使用哈希映射的內存問題？
字符串比較不好依靠。

如果std :: map不是一個哈希映射，我不應該依賴字符串比較（基本上，我有一個映射字符串作爲鍵...我被告知使用哈希映射來查找？），C++ STL中是否有哈希映射？如果不是，Boost怎麼樣？第二，哈希圖是否值得[原] std::map< std::string, non-POD GameState >？

我認爲我的觀點是越過......我打算有一個不同的遊戲狀態存儲，我可以查找並註冊到工廠。如果需要更多信息，請詢問。

謝謝你的時間。

來源

2010-08-01 The Communist Duck

在STL擴展stdext :: hash_map中有一個哈希映射。 – Plow 2010-08-29 15:58:14

我不相信你的觀點是正確的。

在當前標準中沒有哈希映射。 C++ 0x引入了unordered_map，誰的實現將是一個哈希表，你的編譯器可能已經支持它了。
std :: map實現爲平衡樹，而不是散列表。當使用帶有字符串的映射類型時，不存在「內存問題」，無論是作爲鍵還是數據。
在任何一種情況下字符串都不以數字形式存儲 - unordered_map將使用散列函數從字符串中派生數字鍵，但不會存儲該字符串。
我的經驗是，unordered_map大概是地圖速度的兩倍 - 它們基本上具有相同的界面，所以你可以用你自己的數據嘗試兩種方式 - 每當你對性能感興趣時，你應該總是用你的自我測試擁有真實的數據，而不是依賴於他人的經驗。這兩種地圖類型都會對字符串鍵的長度稍微敏感。

假設你有一些類A，你想通過一個字符串鍵來訪問，地圖將被宣佈爲：

map <string, A> amap; 
unordered_map <string, A> umap;

來源

2010-08-01 10:58:59

哈希映射通常有一個字符串的一些積分表示，是的。

std :: map有要求排序的條件，因此不可能將它作爲散列表實現，而且我從來沒有在實踐中看到它。

字符串比較的好壞取決於你在做什麼，你正在比較哪些數據以及多久。例如，如果第一個字母不同，那麼它與整數比較幾乎沒有任何區別。

你想unordered_map（這就是Boost版本 - 如果你的編譯器有這個版本，那麼在TR1標準庫中也有一個版本）。

它是否值得遊戲邦？是的，但僅僅是因爲使用unordered_map很簡單。在這個階段你過早地擔心優化。對於每秒要查看數千次的內容（即，當您的分析器告訴您這是一個問題時），請避免對訪問模式的擔憂。

來源

2010-08-01 11:01:13 Kylotan

我做了一個比較std :: map和boost :: unordered_map的基準測試。我的結論基本上是這樣的：如果你不需要像equal_range這樣的地圖專用的東西，那麼總是使用boost :: unordered_map。可以找到完整的基準測試here

來源

2010-08-29 15:34:17 doep

哈希映射，字符串比較和std :: map？

回答

相關問題