Associative arrays in D and default comparators

[Chris Nicholson-Sauls]

Sean Kelly wrote:
> Walter Bright wrote:
> 
>>
>> 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.
> 
> 
> This is good to know.  I'd considered playing with the current 
> implementation, but was concerned about altering spec-defined behavior.
> 
>> 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.
> 
> 
> I agree that it's got fantastic performance--my concerns here are really 
> more practical, as I have objects I want to use as keys that don't 
> contain any data which could be used for sorting purposes.  But it 
> sounds like there's enough wiggle room in the spec to find some 
> reasonable middle ground.  Thanks!
> 
> 
> Sean

If I recall correctly, the old "standard" Object.opCmp simply compared addresses.  Maybe 
that could be written into a mixin somewhere to be used by classes with no inherent 
logical order of their own.

-- Chris Nicholson-Sauls