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.
