associative arrays: iteration is finally here

[Lars T. Kyllingstad]

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