associative arrays: iteration is finally here

[Denis Koroskin]

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);
}

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).
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
}

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. There is currently an inconsistency with built-in types - you  
don't have to call [] on them, yet you must call it on all the other types:

// fine if array is T[] or K[V]
foreach (i; array) { ... }

// opSlice() is explicit and mandatory for user-defined containers because  
they are not ranges.
foreach (i; container[]) { ... }

Thanks!