Re: associative arrays: iteration is finally here

[Andrei Alexandrescu]

Denis Koroskin wrote:
On Wed, 28 Oct 2009 17:22:00 +0300, Andrei Alexandrescu 
<seewebsiteforem...@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