As the subject states, what is the best idiomatic way for doing that?

Thanks in advance
/Paolo

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

On Wednesday, 26 October 2016 at 19:03:45 UTC, Ali Çehreli wrote:
> On 10/26/2016 08:03 AM, Paolo Invernizzi wrote:
>> [...]
>
> 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);
> }
>
> [...]

Thank you Ali, very exhaustive!