Does associative array change the location of values?
Steven Schveighoffer
schveiguy at gmail.com
Sat Oct 30 21:56:34 UTC 2021
On 10/30/21 2:31 PM, Andrey Zherikov wrote:
> On Saturday, 30 October 2021 at 00:52:23 UTC, Imperatorn wrote:
>> On Saturday, 30 October 2021 at 00:49:04 UTC, Stanislav Blinov wrote:
>>> On Friday, 29 October 2021 at 21:00:48 UTC, Steven Schveighoffer wrote:
>>>
>>>> This is incorrect, the buckets are each heap allocated. Just the
>>>> array of bucket pointers would change.
>>>>
>>>> In addition, AAs do not deallocate the key/value pairs ever. You are
>>>> safe to obtain a pointer to a value and it will stay there, even if
>>>> you remove the key.
>>>>
>>>
>>> Who's going to document these implementation details? ;) I mean, if
>>> no one, then the above shouldn't be stated. Wouldn't you agree?
>>>
>>> Given the premise of the question at hand, it does seem useful to
>>> know these. But at least one should stress what is and isn't subject
>>> to change (even if unlikely).
>>
>> This should be documented for sure
>
> I did small test and it printed the same values three times so even
> rehash doesn't change the address of the value:
>
> ```d
> long[long] aa = [0:0];
> writeln(&aa[0]);
> foreach(i; 0 .. 100_000_000)
> aa[i]=i;
> writeln(&aa[0]);
> aa.rehash;
> writeln(&aa[0]);
> ```
>
> So it seems pretty safe to store a pointer to a value in AA. And I agree
> that this should definitely be documented.
Here is the rehash code, it definitely just moves around the buckets:
https://github.com/dlang/druntime/blob/20963f956c550b7b1b52849e5cf41f436d0df788/src/rt/aaA.d#L144-L157
That free at the end is just for the original `Bucket[]` array.
A Bucket is just a hash and a void pointer to the actual key/value pair.
When you get a pointer to an AA value, it's to the key/value pair block
(there is no struct for this, it's done via runtime type information,
which is horrific legacy).
-Steve
More information about the Digitalmars-d-learn
mailing list