associative arrays: iteration is finally here

[Andrei Alexandrescu]

Denis Koroskin wrote:
> On Wed, 28 Oct 2009 17:22:00 +0300, Andrei Alexandrescu 
> <SeeWebsiteForEmail at erdani.org> wrote:
> 
>> 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.
>>
> 
> Wow, this is outstanding! (I hope it didn't have any negative impact on 
> compile-time AA capabilities).
> 
>> 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
> 
> If AA is providing a way to iterate over both keys and values (and it's 
> a default iteration scheme), why should AA provide 2 other iteration 
> schemes? Can't they be implemented externally (using adaptor ranges) 
> with the same efficiency?
> 
> foreach (e; keys(aa)) {
>     writefln("key: %s", e);
> }
> 
> foreach (e; values(aa)) {
>     writefln("value: %s", e);
> }

Of course. In fact, given the iterator with .key and .value, you can 
always apply map!"a.key" or map!"a.value" to select the desired member.

> I'd also like you to add a few things in an AA interface.
> 
> First, opIn should not return a pointer to Value, but a pointer to a 
> pair of Key and Value, if possible (i.e. if this change won't sacrifice 
> performance).

I'm coy about adding that because it forces the implementation to hold 
keys and values next to each other. I think that was a minor mistake of 
STL - there's too much exposure of layout details.

> Second, AA.remove method should accept result of opIn operation to avoid 
> an additional lookup for removal:
> 
> if (auto value = key in aa) {
>     aa.remove(key); // an unnecessary lookup
> }

I'll make aa.remove(key) always work and return a bool that tells you 
whether there was a mapping or not.

> Something like this would be perfect:
> 
> struct Element(K,V)
> {
>     const K key;
>     V value;
> }
> 
> struct AA(K,V)
> {
>     //...
>     ref Element opIn(K key) { /* throws an exception if element is not 
> found */ }
>     void remove(ref Element elem) { /* removes an element from an AA */ }
>     void remove(K key) { remove(key in this); }
> 
>     AARange!(K,V) opSlice() { /* iterates over both keys and values */ }
> }
> 
> Last, I believe foreach loop should automatically call opSlice() on 
> iteratee.

foreach in D2 should already call opSlice() whenever it's defined. If it 
doesn't, that's a bug in the compiler.


Andrei