Re: associative arrays: iteration is finally here

[Denis Koroskin]

On Wed, 28 Oct 2009 22:24:46 +0300, Robert Jacques <sandf...@jhu.edu>  
wrote:

On Wed, 28 Oct 2009 15:06:34 -0400, Denis Koroskin <2kor...@gmail.com>  
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);
}

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 */ }

Not finding an element is a common use case, not an exception. Using  
exceptions to pass information is bad style, slow and prevents the use  
of AAs in pure/nothrow functions. Returning a pointer to an element  
would allow both key and value to be accessed and could be null if no  
element is found.


Ooops, right, I first wrote it to return a pointer but changed to a  
reference in last moment (mixed it up with opIndex for some reason).
AA.remove should accept a pointer, too.

     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!