用於快速查找和檢索的數據容器

實際上，我需要一個數據結構來幫助我減少查找和檢索各個鍵值的時間。用於快速查找和檢索的數據容器

現在我正在使用一個帶鍵的地圖容器作爲結構，並且希望儘可能快地檢索它的值。

我在Fedora 12上使用gcc。我也嘗試過無序映射，但它不能與我的編譯器一起工作。

另外，哈希映射在命名空間std中不可用。

你能詳細說明你的鍵，鍵空間，值和值空間嗎？ – perreal 2012-02-06 14:41:44

'unordered_map'以何種方式無效？ – 2012-02-06 14:42:50

爲了得到'std :: unordered_map'，你需要爲'C++ 11'編譯。你可以通過指定'-std = C++ 0x'來實現。 – Grizzly 2012-02-06 15:22:34

如果您使用的是C++ 11，請使用std::unordered_map，定義見<unordered_map>。

否則，使用std::tr1::unordered_map，在<tr1/unordered_map>或boost::unordered_map中定義，在<boost/unordered_map.hpp>中定義。

如果您的密鑰是用戶定義的類型，那麼您需要爲該類型定義hash和operator==，或者提供合適的函數類型作爲unordered_map的模板參數。

當然，你也應該測量性能相比std::map;在某些情況下可能會更快。

2012-02-06 14:42:07

非常感謝:)我想使用無序的地圖。 – 2012-02-07 06:29:07

實際上要使用推動hashmap我將不得不下載很多庫...我想要一些易於使用..無序的地圖應該證明對我有幫助..我會試着回到這..謝謝很多。 – 2012-02-07 06:34:58

@ user1087895：如果您需要支持不提供''的編譯器，則只需要Boost。如果你只使用GCC，那麼你應該已經有了。 – 2012-02-07 07:03:34

哈希映射稱爲unordered_map。你可以從boost得到它，即使你不能得到一個std/tr1工作，也可能工作。通常，查找時間是「不變的」，這意味着它不會隨着元素的複雜性而增加。但是，您必須更詳細地看一下：

「常量」假定您永遠不會有超過固定數量的「衝突」。這是不可能的，你不會有任何，然後你必須衡量會有一些碰撞的事實。
「常量」包括散列密鑰所花費的時間。這是一個不變的時間，因爲集合中有多少其他元素沒有什麼區別，但是它仍然是一個需要完成的任務，到那時候你的std :: map可能已經找到了你的元素。

如果密鑰的哈希速度非常快並且分佈很好，所以發生很少的碰撞，那麼哈希確實會更快。

我總是在使用哈希映射時發現的一件事情是，爲了獲得最佳性能，您幾乎總是通過編寫自己的實現而不是使用標準實現而獲勝。這是因爲您可以爲您知道要處理的數據自定義自己的數據。也許這就是爲什麼他們沒有把散列圖加入原始標準。

寫我自己的時候做的一件事是用密鑰存儲實際的哈希值（最初生成的哈希值）。這是第一個比較點（通常比比較鍵快，因爲它只是一個int），也意味着如果調整了散列表的大小，則不需要重新生成它。

請注意，如果您從不刪除任何內容，即加載和只讀，則散列表更容易實現。

2012-02-06 15:42:24 CashCow

是的，這是我想確認散列密鑰的時間開銷會導致比std :: map更多的時間。 – 2012-02-07 06:32:33

我認爲這個我可以用數字幫助確認.. – 2012-02-07 06:33:05

這通常取決於你的地圖大小和每個節點的比較時間。請記住，您在散列圖上也會進行一些比較，因爲碰撞（具有重新分配的碰撞的平坦表是最常見的實施方式）。 – CashCow 2012-02-07 10:53:50

回答