associative arrays: iteration is finally here

[Andrei Alexandrescu]

dsimcha wrote:
> == Quote from Andrei Alexandrescu (SeeWebsiteForEmail at erdani.org)'s article
>> Walter has magically converted his work on T[new] into work on making
>> associative arrays true templates defined in druntime and not considered
>> very special by the compiler.
>> This is very exciting because it opens up or simplifies a number of
>> possibilities. One is that of implementing true iteration. I actually
>> managed to implement last night something that allows you to do:
>> int[int] aa = [ 1:1 ];
>> auto iter = aa.each;
>> writeln(iter.front.key);
>> writeln(iter.front.value);
>> Two other iterations are possible: by key and by value (in those cases
>> iter.front just returns a key or a value).
>> One question is, what names should these bear? I am thinking of makign
>> opSlice() a universal method of getting the "all" iterator, a default
>> that every container must implement.
>> For AAs, there would be a "iterate keys" and "iterate values" properties
>> or functions. How should they be called?
>> Thanks,
>> Andrei
> 
> Awesome, this definitely improves the interface, but how about the implementation?
>  The current implementation, while fast for reading, is unbelievably slow for
> adding elements, requires a heap allocation (read:  a global lock) on *every*
> insertion, and generates an insane amount of false pointers.  Even if I succeed in
> making heap scanning (mostly) precise, it's not clear if the current AA impl.
> could easily be made to benefit, since it isn't template based.  It uses RTTI
> internally instead, and the types it's operating on aren't known to the
> implementation at compile time, so I wouldn't be able to use templates to generate
> the bitmask at compile time.  The structs it uses internally would therefor have
> to be scanned conservatively.

I'm afraid that efficiency is a matter I need to defer to the community 
for now. Right now, I am trying to get TDPL done. Having or not having 
range-style iteration influences the material. Making that efficient is 
a matter that would not influence the material (as long as there is a 
strong belief that that's doable).

Unrelated: one thing that we need to change about AAs is the inability 
to get a true reference to the stored element. aa[k] returns an rvalue, 
and a[k] = v is done in a manner akin to opIndexAssign. But a serious AA 
should have a method of reaching the actual storage for a value, I think.


Andrei