associative arrays: iteration is finally here
Robert Jacques
sandford at jhu.edu
Wed Oct 28 12:24:46 PDT 2009
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!
More information about the Digitalmars-d
mailing list