Inserting to associative array do not return a lvalue.

Steven Schveighoffer schveiguy at yahoo.com
Tue Oct 16 11:51:27 PDT 2007


"Bill Baxter" wrote
> BCS wrote:
>> Reply to Yang,
>>
>>> Sorry. I thought I have a mistake. Holding a pointer to the value of
>>> an associative array is very dangerious.Yang Bo ??:
>>>
>>
>>
>> this works
>>
>> int[int] a;
>> a[1] = 2;
>> int* r = 1 in a;
>> (*r)++;
>>
>> assert(2 == a[1]);
>
> Yeh, I don't think there's anything wrong with modifying the value.
>
> But your version does two lookups also.  Yang makes a good point.  The AA 
> *has* a pointer to the node it just inserted, it just doesn't return it 
> (or a pointer to the value).  Compare with STL map where the insert 
> function returns an iterator to the inserted node.
>
> Really the problem is that D doesn't have a reference type constructor 
> (just a parameter storage class).  In a D-with-references world, a[1] = 2 
> would return a reference to the value instead of a copy.
>
> Another possible solution would be to require all pointer arithmetic to 
> use an explicit &, similar to how function pointers work in D.  Then a 
> plain Foo* would be able act like basically like a reference, and a[1] = 2 
> could happily return a pointer.  But that's probably too big a change to 
> happen now.  And probably too confusing for C/C++ folks, anyway.
>    Foo *foo;  foo = 3;  // huh?
>
> --bb

Technically, the extra lookup isn't very costly.  Most likely you add keys 
rarely.  To make the code more optimized, you would do something like:

int *r = null;
if(!(r = 1 in a))
{
    a[1] = 0;
    r = 1 in a;
}
*r = 2;
(*r)++;

This allows you to avoid the extra lookup (actually extra 2 lookups) if the 
node already exists, which should be the more common case.  If you analyze 
it in big-O notation, the extra-lookup factor is really only a constant, and 
so the complexity is the same.

However, we already have properties on AA's that are built into the 
language.  Would it not make sense to do this as a property? e.g.:

int *r = a.setval(1, 2);
(*r)++;

Due to the way functions on arrays can be used as properties, you could even 
have:

int *setval(int[int] arr, int key, int val)
{
  int *r = key in arr;
  if(!r) // triple lookup only on first call to setval
  {
     arr[key] = val;
     r = key in arr;
  }
  else
    *r = val;
  return r;
}

This can be done without augmenting the language spec, although it still has 
the triple lookup cost on the first call which could be avoided if it was 
done in the language itself.  I'm sure someone out there can templatize this 
:)

-Steve 





More information about the Digitalmars-d mailing list