c++ - 为什么 std::map 是红黑树而不是哈希表？

Question

这对我来说很奇怪，我以为它是一个哈希表。

我在以下答案中看到了 3 个原因(这可能是正确的，但我认为它们不是真正的原因)。 Hash tables v self-balancing search trees

1. 虽然哈希可能不是一个简单的操作。我认为对于大多数类型来说它都非常简单。

2. 当您使用 map 时，您期望某些东西会给您带来分期 O(1) 插入、删除、查找，而不是 log(n)。

3. 我同意树在最坏情况下的性能更好。

我认为有一个更大的原因，但我无法弄清楚。在 c# 中，例如 Dictionary 是一个哈希表。

Answer 1

这在很大程度上是一个历史事故。标准容器(连同迭代器和算法)是标准特性集被卡住之前的最后添加之一。碰巧的是，他们当时没有他们认为的基于哈希的 map 的充分定义，并且在卡住特征之前没有时间添加它，因此原始规范仅包含基于树的 map .

C++ 11 添加了 std::unordered_map(以及 std::unordered_set 和 multi 两个版本)，它基于虽然散列。