associative arrays: iteration is finally here

[Andrei Alexandrescu]

Lars T. Kyllingstad wrote:
> Andrei Alexandrescu wrote:
>> 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.
> 
> Isn't that what the in operator does?
> 
>    T[U] aa;
>    U key = something;
>    T* p = key in aa;
> 
> -Lars

Correct, sorry for the oversight.

Andrei