爲什麼std :: map是紅黑樹而不是哈希表？

這對我來說很奇怪，我期望它是一個哈希表。爲什麼std :: map是紅黑樹而不是哈希表？

我在下面的答案中看到了3個原因（這可能是正確的，但我不認爲它們是真正的原因）。 Hash tables v self-balancing search trees

我認爲有一個更大的原因，但我不明白。在c＃中，例如Dictionary是一個哈希表。

2014-03-26 OopsUser

內存過去非常昂貴。使用'std :: unordered_map'來實現map的哈希表。 – segfault

紅黑樹也被訂購。 – GWW

這在很大程度上是一個歷史事故。標準容器（以及迭代器和算法）是標準的功能集被凍結之前最後一次添加的內容之一。實際上，他們沒有考慮到當時基於散列的地圖的適當定義，並且在功能被凍結之前沒有時間來添加它，所以原始規範僅包含基於樹的地圖。

C++ 11添加了std::unordered_map（以及std::unordered_set和multi兩個版本），它基於哈希雖然。

2014-03-26 15:37:59

當然標準容器在標準化之前已經在STL中工作了數年和數年。很難看到「沒有時間添加」。當然，這個問題只會成爲STL擁有這個屬性的原因之一，這讓我們不能接近答案。 –

@LightnessRacesinOrbit：他們一直在努力 - 但是請記住（整數）只有大約一半的STL被接受進標準。特別是在實際規格方面，似乎很少有人寫入標準的時間很少。 –

散列表需要額外的散列函數。使用樹的當前實現map可以通過使用operator<而無需額外的散列函數。此外，該地圖允許對元素進行排序訪問，這對某些應用程序可能有益。使用C++，我們現在可以以unordered_set的形式提供散列版本。

2014-03-26 15:38:07 Danvil

當然。修正了錯字。 – Danvil

應爲存儲在容器中的元素（例如map，vector，list，deque等）定義拷貝構造函數和賦值運算符'='，以及'<'和'=='運算符。）。因此，完全支持複製和比較。 –

@cplusplus ooa和d你有參考嗎？我從來沒有聽說過==是任何容器的要求。 – MatthiasB

原因是map被明確地叫作有序容器。它使元素保持排序並允許您按線性時間按排序順序進行迭代。散列表無法滿足這些要求。

在C++ 11中，他們添加了std::unordered_map這是一個散列表實現。

2014-03-26 15:38:46

不是侮辱，但我真的不明白爲什麼這是起牀投票。我將這個問題看作是：「爲什麼標準要求地圖需要訂購？」這就回答說：「因爲標準要求地圖需要訂購。」這確實是事實，但它確實*沒有*告訴*爲什麼*。 –

@Jerry Coffin我讀到（並回答）這個問題，「爲什麼'map'不是散列表的實現。 OP可能會澄清他們的*真實*問題。 –

問題澄清肯定會有所幫助。我也不明白OP在尋求什麼幫助。 –

簡單的回答：因爲散列表不能滿足迭代的複雜度要求，因此需要對std::map進行迭代。

爲什麼std::map有這些要求？無法回答的問題。歷史因素起作用，但總體而言，這只是它的方式。

哈希值爲std::unordered_map。

這兩個名字叫什麼也沒有關係，或者他們在其他語言中被稱爲什麼。

2014-03-26 17:23:40

回答