What does it mean for opCmp and opEquals to be consistent?

monarch_dodra monarchdodra at gmail.com
Thu Apr 3 11:45:40 PDT 2014


On Thursday, 3 April 2014 at 16:47:05 UTC, Steven Schveighoffer 
wrote:
> On Thu, 03 Apr 2014 06:42:32 -0400, monarch_dodra 
> <monarchdodra at gmail.com> wrote:
>
>> On Thursday, 3 April 2014 at 10:15:46 UTC, Jonathan M Davis 
>> wrote:
>>> _Any_ type which overloads both opEquals and opCmp and does 
>>> not make them
>>> match exactly is just plain broken.
>>
>> I disagree:
>>
>>> If a.opEquals(b) is true, then a.opCmp(b) must be 0.
>>> If a.opCmp(b) is non-zero, then a.opEquals(b) must be false.
>>
>> Yes.
>>
>>> If a.opEquals(b) is false, then a.opCmp(b) must be non-zero.
>>> If a.opCmp(b) is 0, then a.opEquals(b) must be true.
>>
>> I disagree.
>>
>> You could have types with full comparison, but only *partial 
>> ordering*, depending on the "norm" you used to define their 
>> weight.
>
> Then you shouldn't use opCmp.
>
>> A correctly implemented AA would use opCmp to store objects in 
>> each bucket in cases of hash collisions, but still use opEqual 
>> in case of equivalence.
>
> This can lead to false positives if opCmp(x, y) == 0 is assumed 
> to mean equal.
>
> An example: if you used RBTree to store 2d points, and defined 
> opCmp like you did, then you wouldn't be able to store both (1, 
> 0) and (0, 1) in the same RBTree without duplicates.
>
> -Steve

RBTree make no claim to test for equality, but only equivalence, 
and I'd find it perfectly normal for RBTree to not store both (0, 
1) / (1, 0).

An AA, on the other hand, really shouldn't care about 
equivalence, only equality.

That's how it works in C++ set/unordered_set anyways.


More information about the Digitalmars-d-learn mailing list