Associative arrays in D and default comparators

Ivan Senji ivan.senji_REMOVE_ at _THIS__gmail.com
Thu Sep 7 15:53:49 PDT 2006


Sean Kelly wrote:
> 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 think xs0 was thinking of making AAs templates, and then the compiler 
would add syntactic sugar to that template to achieve current syntax.
So something like
char[float[]] a; would become something like AA!(char, float[]) a;

> 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.

I would too.

> 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.  

It is a rather big limitation.

> 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?

Yes: here is a suggestion: remove opCmp from Object. I think the only 
reason it is there is that when AAs where first implemented templates 
weren't where they are now so there was no way to check if an object has 
opCmp. These days a template version of AAs would be much better, and it 
would (if I'm not mistaken) remove the need for opCmp to be in Object.



More information about the Digitalmars-d mailing list