Associative arrays in D and default comparators

[Sean Kelly]

xs0 wrote:
> Sean Kelly wrote:
>> xs0 wrote:
>> Ah good point.  So any ideas?  Personally, I'd be happy if the default 
>> AA used a linked-list for chaining and opEquals for comparison so this 
>> wasn't an issue, but that seems a foregone conclusion.  I'm mostly 
>> concerned about providing default behavior that makes sense for the 
>> common case.  The problem I've run into is that I have objects which 
>> need to be used as keys in an AA but are not inherently sortable.
> 
> Well, one possibly good solution would be to templatize AAs and remove 
> opCmp from Object. That way, you'd get an error when using comparison on 
> objects without opCmp (most other operators work that way) and the 
> template could test for its presence and use different implementations 
> for each.

Some fancier AA support would be nice, but I'm not sure how to add 
templates to the built-in syntax.  I just noticed something confusing in 
the spec however.  Why are classes intended to be used as keys in an AA 
required to implement both opCmp *and* opEquals?  Since the AA is backed 
by a binary tree I would expect it determine 'equality' as equivalence 
using opCmp.  It's quite common for me to define classes that are 
equivalent but not equal, and also classes that can be compared for 
equality but not sorted.  But it sounds like both would not be 
compatible with D's built-in AA implementation.  I'm beginning to feel 
that any possible performance advantage that can be offered from binary 
tree chaining over linked list chaining is overshadowed by the 
limitations it imposes on the use of AAs in general.  Can someone 
suggest an alternate default implementation for opCmp that solves these 
problems?


Sean