Associative arrays in D and default comparators

[Walter Bright]

Sean Kelly wrote:
> 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?

Although the current AA implementation only uses opCmp, having both 
available means that an implementation could use both or either. 
Sometimes opEquals can be computed a lot more efficiently than opCmp.
The current implementation uses hashing with binary trees, but an 
implementation isn't required to do it that way.

Hashing with binary trees has proven in practice to be very efficient. 
It beats even C++ templated hash tables. I'm sure with some careful 
coding one can create a faster one customized to a particular data type, 
but the current general purpose one is pretty darned fast and compact. 
It's the central algorithm in DMDScript, for example, and DMDScript 
still beats the other javascript implementations around the block.