c – 为什么std :: map是红黑树,不是哈希表？

发布时间：2020-12-16 02:59:30 所属栏目：百科来源：网络整理

导读：这对我来说很奇怪,我希望它是一个哈希表. 我在以下答案中看到3个原因(这可能是正确的,但我不认为他们是真正的原因). Hash tables v self-balancing search trees 尽管哈希可能不是一个微不足道的操作.我认为,对于大多数类型来说,这很简单. 当你使用地图时,你

这对我来说很奇怪,我希望它是一个哈希表.

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

尽管哈希可能不是一个微不足道的操作.我认为,对于大多数类型来说,这很简单.
>当你使用地图时,你会发现一些东西会给你分摊O(1)插入,删除,找到,而不是log(n).
>我同意树木的表现最好.

我认为有更大的理由,但我无法理解.
在c#中,例如Dictionary是一个哈希表.

解决方法

这在很大程度上是一个历史事故.标准容器(以及迭代器和算法)是在标准的功能集被冻结之前的最后一个补充之一.事实上,他们没有什么他们认为当时基于哈希的地图的适当定义,并没有时间添加它之前功能被冻结,所以原始的规范只包括一个基于树的地图.

C 11添加了std :: unordered_map(以及std :: unordered_set和两个的多个版本),这是基于散列.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!