Safe to remove AA elements while iterating over it via .byKeyValue?

Steven Schveighoffer schveiguy at gmail.com
Mon Sep 28 21:52:03 UTC 2020


On 9/28/20 1:18 PM, ikod wrote:
> On Monday, 28 September 2020 at 14:58:15 UTC, Steven Schveighoffer wrote:
>> On 9/27/20 4:43 PM, Per Nordlöw wrote:
>>> On Sunday, 27 September 2020 at 14:23:11 UTC, H. S. Teoh wrote:
>>>> No.  Modifying a container while iterating over it is, in general, a 
>>>> bad idea (unless the container is designed to be
> 
>> So the major problem of removing keys while iterating is that the AA 
>> can decide to rehash and shrink. If it does this, your iterator is 
>> invalidated -- you might skip elements that are
> ....
>>
>> How do you "detect" this at compile time?
> 
> I think idea was to have some attributes that collection programmer may 
> attach to implementation, like enums: SafeToRemoveOnIteration, 
> SafeToAddOnIteration and so on, which may be checked at compile time 
> when foreach is handled by compiler. Then in the foreach body compiler 
> can refuse to call some unsafe methods. I do not know if it is worth of 
> implementation, just this this was an idea.

auto sneaky = aa;
foreach(k, v; aa)
{
    sneaky.remove(k); // oops
}

It doesn't work. You can't restrict this at compile time. Possibly 
runtime, but not compile time.

> 
>>
>> One could write a specific function to iterate and remove. I
> 
> This looks like dead end to me, as you may not only remove items from 
> arbitrary positions while iterating over collection, but also insert 
> items. Also this can happens not only inside foreach body, but in other 
> kinds of iteration. And also there can be nested iterations over same 
> collection.

What do you mean dead end? You provide what is supported through a 
controlled interface. It works well, I wrote and used it in 
dcollections. Using the standard insertion and removal functions is not 
allowed (at least without invalidating the range).

If you want insertion, then potentially you could expose those methods 
via the specific iteration construct as well. But you must be prepared 
to do some really funky things.

If we are talking about AAs, insertion may end up expanding the bucket 
list, which means rehashing. That leads to iterating over the same keys 
again. Unless you do some kind of copy-on-write, or combination of 
iterated container + true container? I don't know.

However, deletion is possible (either delay the rehash until after, or 
don't do a rehash during that iteration) via the iteration construct 
(range). You still need to disallow removal via the original type, or 
you might get a rehash.

-Steve


More information about the Digitalmars-d-learn mailing list