AA's and mutating keys

[Steven Schveighoffer]

"Jarrett Billingsley" wrote
>
> "Steven Schveighoffer" <schveiguy at yahoo.com> wrote in message 
> news:fgaf4j$1d18$1 at digitalmars.com...
>> It's ok if the AA makes a copy of the key, or uses something based on the 
>> key (like a hashcode).
>
> Not really.  Consider:
>
> int[char[]] map;
> char[] key = new char[5];
> key[] = "hello"[];
> map[key] = 8;
> key[0] = 'c';
> map["cello"] = 2;
>
> What happens is that you insert ("hello" => 8) into the table.  But then 
> you go and modify the key so it's "cello" instead.  However now you have 
> an inconsistent key: the key says "cello" but its hash is the hash of 
> "hello". So, when you try to change "cello", the new "cello" maps to 
> another slot and ("cello" => 2) is inserted.  In fact, if you run this 
> code and then print out the key value pairs, you'll get something like:
>
> cello 8
> cello 2

You are half right :)  The first part of my statement says "if the AA makes 
a copy of the key", so I think that is ok (and I think you agree).

But you are right about the hash table.  I understand that portion of it, 
but if the AA had a near-perfect hash function (like for an extreme example, 
md5sum of the text), then the AA would not even need to store the key, it 
would just store the hash.

That's besides the point.  I probably shouldn't have said the second part in 
my original statement.

>
> In fact it's now impossible to modify or remove the original key-value 
> pair because even if you can get something to hash to the right slot, the 
> keys won't compare equal, and so the AA implementation won't find it.

<splitting hairs>
In fact it is possible :)

key[0] = 'h';
map.remove(key);
</splitting hairs>

> Easy, nested functions to the rescue:

This is a good point, I absolutely love nested functions, and didn't think 
of that.

>
> The nice thing about it not doing it automatically for you is performance. 
> Most of the time you _don't_ need this behavior, and when you do it's easy 
> to implement it on top of the existing behavior.

The performance hit of copying the string on first insertion is very minimal 
in most cases.  I think the benefit far outweighs the cost.  C++ std::map 
does this, and nobody has ever complained about the performance hit.

It would be nice to have a class/struct that wraps an AA with this behavior.

-Steve