Associative arrays in D and default comparators

[Sean Kelly]

Steve Horne wrote:
> On Thu, 07 Sep 2006 14:54:41 -0700, Sean Kelly <sean at f4.ca> wrote:
> 
>> Since the AA is backed 
>> by a binary tree I would expect it determine 'equality' as equivalence 
>> using opCmp.
> 
> There may be special case operations on the AA where opCmp is
> unnecessary and opEquals is a little faster.
> 
> But... I had got the impression that the built-in associative arrays
> were done with hashtables. I think the manual says something about
> foreach not enumerating the items in order.
> 
> OTOH, I didn't see any kind of 'opHash' or similar.
> 
> So - binary trees, then? Red-black, perhaps?
> 
> Or are you talking about hash collision handling?

Traditional binary trees as used for collision handling in the DMD AA 
implementation.

>> Can someone 
>> suggest an alternate default implementation for opCmp that solves these 
>> problems?
> 
> Don't know if it helps, but sometimes a consistent-but-arbitrary
> ordering can give good keys. For instance, the ordering of hash values
> is meaningless, but you can still use it to divide-and-conquer your
> data.

I suppose the problem is how to do this without exposing an opCmp 
function to be used for more general sorting purposes.  The 
implementation I proposed on d.D.bugs (return this !is obj) works okay 
for binary trees, but as Ivan pointed out, it would be terrible for a 
sort operation.


Sean