associative arrays: iteration is finally here

[Steven Schveighoffer]

On Wed, 28 Oct 2009 10:22:00 -0400, 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.
>
> 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?

This is one of the benefits of opApply.

Rather than define some new names to make up for the deficiencies of  
range-foreach (especially so near the release of D2), why not focus on  
fixing the deficiencies?

i.e. here is my desired interface:

foreach(key, value; aa) // iterate both keys and values
foreach(value; aa) // default to iterating values (to be consistent with  
arrays)
foreach(key; aa.keys) // iterate keys lazily.

If ranges cannot support this interface, I think the range paradigm needs  
some work.  opApply works great for this since the delegate type defines  
the desired interface.  The problem with ranges is the potential "opRange"  
method in it's natural form should overload on the return value, and have  
no parameters.

Here's a possible idea: make foreach(X x, Y y, Z z,...; container)  
translate to foreach(X x, Y y, Z z,...; container.opRange!(X, Y, Z,  
...)()).  In the case of inferred types, maybe you can do something like:

opRange!(T : keytype, U : valuetype)() and have the compiler infer types  
for x and y as keytype and valuetype.

The only drawback I see is opRange can't be virtual.  However, how does  
one define a "virtual" range return, when a range is invariably a struct?   
It might be a moot issue.

Of course, you could always meet the virtual requirement by naming your  
range-generating method...

So with my scheme, the AA becomes:

struct AA(Key, Val)
{
   ... // implementation
   auto opRange(T : Key, U : Val)() { ... }
   auto opRange(T : Val)() { ... }
   auto keys() { ... }
}

One other thing left to define is what foreach calls to get the key(s) in  
the case of multiple arguments to foreach.  The value is generally  
accessed via front().  Might as well tackle the ref possibilities too :)

-Steve