C ++:无序容器如何防止重复?

问题描述 投票:0回答:3

让我们以unordered_set为例。用于确定两个元素是否相等的默认谓词是std::equal_to<T>(t1,t2),就是t1==t2。现在,假设对于这种T类型,我已经实现了operator==(),因此并非所有成员变量都属于此比较的一部分,即,两个不同的T元素t1,t2在比较时可以相等。

如果基础哈希表为这些t1和t2中的每一个计算不同的哈希,那么它甚至什么时候执行t1==t2检查是否有重复的密钥?如果还有更多支票,它如何平均保持恒定时间?

c++ hash stl unordered-map unordered-set
3个回答
2
投票
有哈希函数,它从一个对象计算一个数字。

有一个比较功能,比较两个对象的“等效性”。

就像@Eljay在他的评论中说的,对于两个比较“等效”的对象(比较函数返回true),哈希函数

必须返回相同的值。

如果您的功能不提供此保证,则容器将无法正常工作。


1
投票
如果基础哈希表为这些t1和t2中的每一个计算不同的哈希,那么它甚至什么时候执行t1 == t2检查键重复?
[当散列函数使新插入的元素放入非空存储桶时。将比较该存储桶中已有的元素,以确保其唯一性。

它平均如何保持恒定时间?

假设散列函数将随机密钥平均分配到存储桶中,并随着元素数量的增加而增加存储桶的数量。

std :: hash如何知道我如何实现openrator ==()

谁为您的类编写std :: hash的专业化知识,必须知道如何实现operator ==。

哈希函数必须为比较相等的所有元素产生相同的哈希。如果没有,则程序的行为将是不确定的。


0
投票

Hash类型的容器对象-由hash表示-被称为容器的哈希函数。类型为Pred的容器对象(用pred表示)称为容器的键相等谓词。

两个值k1k2被认为是等效的,如果容器的键相等性谓词pred(k1, k2)有效并且在传递这些值时返回true。如果k1k2相等,则容器的哈希函数应为两者返回相同的值。

您的operator==std::hash实现必须保持一致。如果不是,那么您就没有满足使用类作为无序关联容器中的键所必需的先决条件。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.