爲什麼C++ STL使用RBtree來實現「std :: map」？

現在我正在尋找python源代碼，並且我發現python和C＃都使用hash來實現Dictionary。爲什麼C++ STL使用RBtree來實現「std :: map」？

哈希的時間複雜度爲O(1)和RBtree是O(lgn)，所以任何人可以告訴我爲什麼C++ STL使用RBtree實施std::map的原因是什麼？

2012-03-17 lai

你不應該被漸近盲法。 BST和哈希表是非常不同的數據結構，通過測量，您只能真正知道哪一個更適合您的問題。由於散列表對鍵類型有更多困難的要求並且更復雜，所以基於樹的*有序*映射對於關聯容器來說是更自然的首選，但就C++ 11而言，我們都有。 – 2012-03-17 01:03:36

因爲它有一個單獨的散列表容器：std::unordered_map<>。還要注意的是，除了Dictionary<>之外，.NET還有SortedDictionary<>。

來源

2012-03-17 00:49:25 ildjarn

你可能想提一下'std :: map'（正在被分類）的附加要求，這使得它不同於'Dictionary'並等於'SortedDictionary'。 – 2012-03-17 00:57:52

謝謝，所以在RBtree中可以挑選出某個範圍內的所有項目，但在哈希表中我們不能這樣做，對吧？ – lai 2012-03-17 01:03:49

「散列的時間複雜度爲O（1）」 - 最好的情況。最壞的情況仍然是O（n）。 rb樹使用平衡技術來實現所有情況下的log（n）。而且，當然還有順序的差異。 – innochenti 2012-03-17 01:05:33

答案可以在「The Standard C++ Library，A Tutorial and Reference」中找到，可在此處在線獲取：http://cs-people.bu.edu/jingbinw/program/The%20C++STL-T&R.pdf。

短報價說明：

一般來說，整個標準（語言和庫）是大量的討論，並從數百人在世界各地影響的結果。例如，日本人提出了國際化的重要支持。當然，錯誤被做了，頭腦被改變了，並且人們有不同的意見。然後，在1994年，當人們認爲標準接近完成時，STL被整合，從根本上改變了整個圖書館。但是，到完成後，關於主要擴展的想法最終停止了，不管如何有用擴展將是。因此，散列表不是標準的一部分，儘管它們應該是STL的一部分，作爲通用數據結構。

顯然自那時以來，C++ 11已經問世，並且由於名稱map已被接受，和hash_map是一個已經廣泛經由公共擴展庫使用（eg__gnu_cxx ::的hash_map）的名稱，該名稱unordered_map被選爲哈希映射。

來源

2012-03-17 01:09:27 Kevin

爲什麼C++ STL使用RBtree來實現「std :: map」？

回答

相關問題