associative arrays: iteration is finally here

[rmcguire]

Andrei Alexandrescu <SeeWebsiteForEmail at erdani.org> wrote:
 
> Denis Koroskin 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);
>> }
> 
> 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
> 


Wouldn't opIn be more useful if it returned a range starting with
the element that was found?