c++ - 为什么STL选择基于树的映射而不是基于散列的映射？

Question

我想知道为什么STL的 map 是基于rb树的？我的意思是，基于哈希的映射似乎在插入/删除甚至获取值方面更有效。有什么具体的注意事项吗？

Answer 1

STL 最初选择了两者。它有一个哈希表和基于树的 map 。

然而，当它被纳入标准时，许多部分被剥离以简化任务(更容易说服委员会包括一个更小的库，并且在实际指定它们的行为方面需要更少的工作).

因此跳过了哈希表。

不过，这两种数据结构各有优势。特别是，二叉树允许 map 的内容排序(您可以按排序顺序迭代 map 的内容，或者您​​可以要求所有小于特定元素的元素，例如例如)，我只能猜测这个属性被认为比 HashMap 的性能优势更重要。

但是在C++11中，加入了std::unordered_map，也就是失传已久的哈希表。它最初的遗漏仅仅是由于时间压力，而且很可能是委员会政治(保持图书馆规模较小以尽量减少对它的抵制)