Associative arrays in D and default comparators
sean at f4.ca
Thu Sep 7 23:34:21 PDT 2006
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
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!
More information about the Digitalmars-d