Are AAs broken? (Was: Why isn't bool allowed as AA key type?)

[Timon Gehr]

> On Thu, 02 Jun 2011 06:21:28 -0400, Timon Gehr <timon.gehr at gmx.ch> wrote:
>
>> Steven Schveighoffer wrote:
>>> There is always dcollections (has both Hash- and TreeSet).  It is boost
>>> 1.0, so feel free to steal anything to propose for std.container (in
>>> fact,
>>> RedBlackTree is from dcollections).  Note that I'm nowhere near an
>>> expert
>>> on hashing, so I'm not sure how it will perform against AAs.  I know it
>>> does beat them using my custom allocator, but that's not a truly fair
>>> comparison -- AA's could be written with a custom allocator too.
>>>
>>> -Steve
>>
>> Well, how? Since an 'in' expression returns an internal pointer into the
>> AA for
>> value types, they cannot do better than to rely on GC.
>> This rules out heavy AA use for real-time applications. I think AAs are
>> broken.
>
> What is the issue here?  Are you saying you can use the pointer after
> destroying the element, because you can't.  AA's free an element when it
> is removed.

Huh?

import std.stdio,core.memory;

int* test(){
    int[int] aa=[0:0,1:1,2:2,3:3,4:4,5:5];
    return 1 in aa;
}

void main(){
    int* u=test();
    GC.collect();
    assert(*u==1);
    /*use u for fun and profit*/
}

>
> BTW, dcollections' custom allocator does use the GC, it just uses it in
> bulk instead of allocating for each node.
>
> -Steve

If AAs would do that, the whole bulk could be pinned by one pointer to one element
inside it, which is still not optimal. Returning internal pointers into a data
structure is always a bad idea (assuming it must be safe).

Timon