associative arrays: iteration is finally here

[Robert Jacques]

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

>      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!