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

[H. S. Teoh]

On Mon, Sep 28, 2020 at 05:18:41PM +0000, ikod via Digitalmars-d-learn wrote:
> On Monday, 28 September 2020 at 14:58:15 UTC, Steven Schveighoffer wrote:
[...]
> > 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.

The problem with arbitrary, unrestricted modification of a container
while iterating over it, is that it inevitably leads to counterintuitive
results.

For example, suppose you have a container containing the elements A, B,
C, D, E, and you're iterating over it in that order.

1) Suppose you're at element C, and you decide that you need to insert
F. Then there's the question: should F be included in the current
iteration or not?  What if F sorts before C in the current sort order?
What if F sorts after C?  Should the two cases behave similarly (i.e.,
new elements consistently get included in the current iteration, or they
consistently don't get included in the current iteration)?  What if the
act of inserting F requires an internal reordering of elements in the
container?

2) Suppose you're at element C, and you decide to delete D.
"Obviously", the current iteration should not include D. Or should it?
If you delete A while you're at C, you've already iterated over A, so
there's an inconsistency: deleted elements sometimes get included in the
current iteration, sometimes not.  The problem is, which case is the
"correct" one depends on the user's purpose, which is information that
the container may not have.

Also, what if the act of deleting D requires an internal reorganization
of the container?  If this reorg changes the iteration order, how should
the current iteration proceed? According to the old order, or the new
order?  Note that proceeding with the new order may lead to
counterintuitive results: suppose the new order becomes E -> C -> B ->
A.  That means the current iteration will proceed with B and A, which
have already been encountered before, and skips E.

However, proceeding with the old order may be inefficient: it may
require allocating extra storage to preserve the current iteration order
because the reorganized container no longer has that information.  Or it
may require the container itself to maintain extra information in order
to retain the current iteration order.

3) Suppose you're at element A, and you decide to insert F, with the
resulting order A -> B -> C -> D -> E -> F.  So you proceed as usual.
But at B, you decide to delete F, but that causes the container to
reorganize itself to B -> A -> C -> D -> E.  So in the next iteration
you encounter A again, and insert F again, which causes the container to
reorganize itself to A -> B -> C -> D -> E -> F.  So you get stuck in a
loop between A and B, and termination is no longer guaranteed in
iteration.

Basically, the whole concept of iteration is undermined when the
container can mutate while you're iterating.  It leads to inconsistent
behaviour -- sometimes new elements show up in the current iteration,
sometimes they don't; or some elements may get visited multiple times or
missed altogether -- and iteration may not terminate if your sequence of
operations interacts badly with the container's internal
reorganizations.

Furthermore, trying to work around this by postponing container
reorganizations may lead to other problems, like container inconsistency
(some data structures require immediate reorganization in order to
maintain correctness, etc.).

//

The only way to support container mutation while iterating over it, is
if (1) the allowed operations is constrained (e.g., you can only delete
the current element, not any arbitrary element), and (2) the container
itself must explicitly support such an operation (otherwise deleting the
current element may lead to premature termination of the current
iteration, or errors like dangling pointers or some compromise of
container consistency).

Mixing iteration with arbitrary, unrestricted container mutation is a
road that leads to madness.


T

-- 
Recently, our IT department hired a bug-fix engineer. He used to work for Volkswagen.