test for equality of the content of two AA

[Ali Çehreli via Digitalmars-d-learn]

On 10/26/2016 08:03 AM, Paolo Invernizzi wrote:
> As the subject states, what is the best idiomatic way for doing that?
>
> Thanks in advance
> /Paolo

If you mean D's AAs, then that is already implemented:

   void main() {
     auto a = [ "hello" : 1, "world" : 2 ];
     auto b = [ "world" : 2, "hello" : 1 ];
     assert(a == b);
}

The source makes sense:

   https://github.com/dlang/druntime/blob/master/src/rt/aaA.d#L615

* First check that the lengths are equal

* Then check each element

The last step is already fast without needing any other data structure 
(e.g. one may imagine a sorted array) because hash table lookup is O(1) 
and there are N elements that needs to be processed (i.e. compared), so 
the whole operation must be O(N).

If the equality comparison is very frequent, then a hash table that 
maintains a hash of all keys and values can be used, which would be 
O(1). (As far as I know D's AAs don't have such a feature.) This would 
make the comparison of non-equal tables O(1) but if this overall hash 
were equal between two tables, one would still have to compare every 
element to be sure, which would be O(N).

Ali