associative arrays: iteration is finally here

[Pelle Månsson]

Robert Jacques wrote:
> 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.

Also, if opIn throws an exception, it kind of defeats the point of opIn, 
and turns it to opIndex.