AA with complex keytype?

[Frits van Bommel]

Joel Salomon wrote:
>>> Mathematically speaking, a group like ℤ₃ is unordered,
>>> precisely for the reason given.  If we need to impose an ordering
>>> for array purposes (I don’t understand that bit, just
>>> (mis)repeating something I’ve seen said on the subject), then
>>> give the ordering lexicographic properties. 
>> It is faster to not impose an ordering on an unordered set.
> 
> Do you know where D insists that “some” ordering be applied to a type,
> and why?

Associative arrays. http://www.digitalmars.com/d/arrays.html#associative

They're implemented as a hash table with a binary tree per bucket. 
Binary trees require some ordering between the elements.
This isn't the only implementation option of course, for example it 
could also be a linked list instead of a binary tree. Or it could not 
use a hash table at all and just use one big binary tree[1]. (But AFAICT 
the only reasonably efficient option without requiring ordering would be 
a hash table with a linked list per bucket)



[1]: Presumably some self-balancing tree like red-black or AVL.