www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Structs as Keys for AAs

reply Q. Schroll <qs.il.paperinik gmail.com> writes:
In [1] it says at 5. that

 For this reason, and for legacy reasons, an associative array 
 key is not allowed to define a specialized opCmp, but omit a 
 specialized opEquals. This restriction may be removed in future 
 versions of D.
I'm not completely sure what that means. Does "specialized" mean "user-defined"? I just challenged the spec and found an error by the way: [2]. Apart from that, it compiles. For 5. I used struct Key { int id; string tag; int opCmp(const Key other) const { return this.id < other.id ? -1 : this.id == other.id ? 0 : 1; } bool opEquals(ref const Key other) const safe pure nothrow { return this.id == other.id; } size_t toHash() const safe pure nothrow { return id; } } as a key type. To me the part "is not allowed to define a specialized opCmp" is clearly wrong, either a compiler bug or an error in the spec. Concerning opEquals and opCmp in general: Why isn't opEquals lowered to opCmp returning 0 if not present? [1] https://dlang.org/spec/hash-map.html#using_struct_as_key [2] https://github.com/dlang/dlang.org/pull/1861
Aug 09
next sibling parent "H. S. Teoh via Digitalmars-d" <digitalmars-d puremagic.com> writes:
On Wed, Aug 09, 2017 at 11:31:44PM +0000, Q. Schroll via Digitalmars-d wrote:
 In [1] it says at 5. that
 
 For this reason, and for legacy reasons, an associative array key is
 not allowed to define a specialized opCmp, but omit a specialized
 opEquals.  This restriction may be removed in future versions of D.
I'm not completely sure what that means. Does "specialized" mean "user-defined"? I just challenged the spec and found an error by the way: [2]. Apart from that, it compiles.
The main issue is that the current AA implementation uses TypeInfo's .equal method for comparing keys. (This dates from before D has templates, and also because at the time, the AA implementation was too tightly bound to the compiler and couldn't be easily changed.) The way TypeInfo works, .equal will not do the right thing if you only define opCmp without also defining opEquals. This is why the spec was updated to say that you must essentially always define opEquals if you define opCmp. Otherwise, you may get strange or wrong behaviour when using the type as an AA key.
 For 5. I used
 
 struct Key
 {
     int id;
     string tag;
 
     int opCmp(const Key other) const
     {
         return this.id < other.id ? -1 : this.id == other.id ?  0 : 1;
     }
 
     bool opEquals(ref const Key other) const  safe pure nothrow
     {
         return this.id == other.id;
     }
 
     size_t toHash() const  safe pure nothrow
     {
         return id;
     }
 }
 
 as a key type. To me the part "is not allowed to define a specialized
 opCmp" is clearly wrong, either a compiler bug or an error in the
 spec.
Did you test the result at runtime with a real AA? A telling sign would be if you added the same Key twice, then iterate over the AA to print out the entries. You may get the same key more than once, which would be indicative of this problem. Just because the compiler accepts the code, doesn't necessarily mean it's right. (Of course, it's arguably a bug that the compiler accepts it in the first place. But the AA implementation in the compiler is a bit fragile to handle at the moment, I'm not sure if it can be easily fixed without causing other problems. We'll have to wait for Martin's library AA to get merged...)
 Concerning opEquals and opCmp in general: Why isn't opEquals lowered to
 opCmp returning 0 if not present?
[...] Mainly (1) for efficiency, and also, (2) to paraphrase Andrei, to allow partial orders that may not be linear. (1) because some types may have expensive computations to determine whether something is bigger or smaller, but trivial to determine equality. (2) because conceivably you can implement the subset relation in opCmp with a type that represents a set, so opCmp()==0 could mean the sets are equal, OR it could mean the sets are not subsets of each other (they are either disjoint, or have elements not in common with each other). Then you'd need opEquals() to tell you whether or not they are equal. For a less exotic example, consider a custom floating-point type where NAN < NAN and NAN > NAN are both false, so opCmp()==0 is the only reasonable return value, yet opEquals() also == 0 because NAN != NAN. T -- INTEL = Only half of "intelligence".
Aug 09
prev sibling parent Steven Schveighoffer <schveiguy yahoo.com> writes:
On 8/9/17 7:31 PM, Q. Schroll wrote:
 In [1] it says at 5. that
 
 For this reason, and for legacy reasons, an associative array key is 
 not allowed to define a specialized opCmp, but omit a specialized 
 opEquals. This restriction may be removed in future versions of D.
I'm not completely sure what that means. Does "specialized" mean "user-defined"?
Yes, that's what it means.
 I just challenged the spec and found an error by the 
 way: [2]. Apart from that, it compiles.
 
 For 5. I used
 
 struct Key
 {
      int id;
      string tag;
 
      int opCmp(const Key other) const
      {
          return this.id < other.id ? -1 : this.id == other.id ?  0 : 1;
      }
 
      bool opEquals(ref const Key other) const  safe pure nothrow
      {
          return this.id == other.id;
      }
 
      size_t toHash() const  safe pure nothrow
      {
          return id;
      }
 }
 
 as a key type. To me the part "is not allowed to define a specialized 
 opCmp" is clearly wrong, either a compiler bug or an error in the spec.
You need to read it with the other part "but omit a specialized opEquals". In other words, you must implement opEquals if you implement opCmp. The reason is simple, because opEquals defaults to a comparison of all fields, and most likely if you are defining opCmp, it won't match the default opEquals. opHash uses opEquals, but does not use opCmp. Therefore, if this restriction wasn't in place, then you may just define opCmp thinking the AA would use it. Note that in your example, your opEquals is more efficient than opCmp == 0. This is the main reason opEquals is defined differently than opCmp.
 Concerning opEquals and opCmp in general: Why isn't opEquals lowered to 
 opCmp returning 0 if not present?
It really should IMO, but that's not how it works. I'm almost positive there's an enhancement request on this somewhere. -Steve
Aug 09