Is it safe to remove AA-elements from an `aa` I'm iterating over via aa.byKeyValue?

I'm currently doing this:

    foreach (ref kv; aa.byKeyValue)
    {
        if (pred(kv.key))
            aa.remove(kv.key); // ok?
    }
    if (aa.length == 0)
        aa = null;

Is there a better way?

On Sunday, 27 September 2020 at 13:02:04 UTC, Per Nordlöw wrote:
> Is it safe to remove AA-elements from an `aa` I'm iterating over via aa.byKeyValue?
>
> I'm currently doing this:
>
>     foreach (ref kv; aa.byKeyValue)
>     {
>         if (pred(kv.key))
>             aa.remove(kv.key); // ok?
>     }
>     if (aa.length == 0)
>         aa = null;
>
> Is there a better way?

Normally this is not advisable since you're modifying the iterated source.

Same thing in C#, there it's a compiler error.

On Sunday, 27 September 2020 at 13:02:04 UTC, Per Nordlöw wrote:
> Is it safe to remove AA-elements from an `aa` I'm iterating over via aa.byKeyValue?
>
> I'm currently doing this:
>
>     foreach (ref kv; aa.byKeyValue)
>     {
>         if (pred(kv.key))
>             aa.remove(kv.key); // ok?
>     }
>     if (aa.length == 0)
>         aa = null;
>
> Is there a better way?

The boring way is to store an array of the spent keys and remove afterwards.

KeyType!(typeof(aa))[] garbage;
garbage.reserve(aa.length);

foreach (ref kv; aa.byKeyValue)
{
    if (pred(kv.key))
        garbage ~= kv.key;
}

foreach (const key; garbage)
{
    aa.remove(key);
}

This works with normal arrays too (and std.algorithm.mutation.remove), if you foreach_reverse the garbage array.

On Sunday, 27 September 2020 at 13:02:04 UTC, Per Nordlöw wrote:
> Is it safe to remove AA-elements from an `aa` I'm iterating over via aa.byKeyValue?
>
> I'm currently doing this:
>
>     foreach (ref kv; aa.byKeyValue)
>     {
>         if (pred(kv.key))
>             aa.remove(kv.key); // ok?
>     }
>     if (aa.length == 0)
>         aa = null;
>
> Is there a better way?

What you could do is find all matches (pred) and remove range of indices

On Sun, Sep 27, 2020 at 01:02:04PM +0000, Per Nordlöw via Digitalmars-d-learn wrote:
> Is it safe to remove AA-elements from an `aa` I'm iterating over via aa.byKeyValue?

No.  Modifying a container while iterating over it is, in general, a bad idea (unless the container is designed to be used that way, but even then, such removal is generally restricted), because it often leads to highly counterintuitive results.  In the case of AA's, removing an element may lead to a rehashing, which reorders elements, and your iteration may miss some elements or repeat some elements or terminate prematurely. Even without a rehashing, you may encounter inconsistent behaviours, like some elements going "missing".

You probably want to build a list of keys to remove, then remove them after the iteration instead.


T

-- 
Why can't you just be a nonconformist like everyone else? -- YHL

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 used that way, but even then, such removal is generally restricted), because it often leads to highly counterintuitive results.  In the case of AA's, removing an element may lead to a rehashing, which reorders elements, and your iteration may miss some elements or repeat some elements or terminate prematurely. Even without a rehashing, you may encounter inconsistent behaviours, like some elements going "missing".

I believe it's high time we start thinking about detecting these violations at compile-time. I recall it's in the spec somewhere so we should start a deprecation process at least for AAs.

On Sunday, 27 September 2020 at 14:23:11 UTC, H. S. Teoh wrote:
> On Sun, Sep 27, 2020 at 01:02:04PM +0000, Per Nordlöw via Digitalmars-d-learn wrote:
>> Is it safe to remove AA-elements from an `aa` I'm iterating over via aa.byKeyValue?
>
> No.  Modifying a container while iterating over it is, in general, a bad idea (unless the container is designed to be used that way, but even then, such removal is generally restricted), because it often leads to highly counterintuitive results.  In the case of AA's, removing an element may lead to a rehashing, which reorders elements, and your iteration may miss some elements or repeat some elements or terminate prematurely. Even without a rehashing, you may encounter inconsistent behaviours, like some elements going "missing".

I think sane rule for AA iterator cane be like this:

1. you must not visit keys removed during iteration regardless of their position.
2. you must be able to visit all keys available when iteration started.
3. you may not visit keys added during iteration (as AA is unordered container)

Looks like this can be implemented for open addressing hash map without performance loss (in terms of speed). My has hmap implementation support rules 2 and 3, I'll try to add rule 1 to the list (right now it iterate over immutable copy of keys).

On Sunday, 27 September 2020 at 20:43:19 UTC, Per Nordlöw wrote:
> On Sunday, 27 September 2020 at 14:23:11 UTC, H. S. Teoh wrote:
>> [...]
>
> I believe it's high time we start thinking about detecting these violations at compile-time. I recall it's in the spec somewhere so we should start a deprecation process at least for AAs.

Yes, this should be a compile-time error

On Monday, 28 September 2020 at 07:15:27 UTC, Imperatorn wrote:
> Yes, this should be a compile-time error

Spec here: https://dlang.org/spec/statement.html#foreach_restrictions

On Monday, 28 September 2020 at 09:41:02 UTC, Per Nordlöw wrote:
> On Monday, 28 September 2020 at 07:15:27 UTC, Imperatorn wrote:
>> Yes, this should be a compile-time error
>
> Spec here: https://dlang.org/spec/statement.html#foreach_restrictions

Is it specific to some types? What if collection supports stable "foreach"?