std.collection - changing the collection while iterating

[Morbid.Obesity via Digitalmars-d]

On Sunday, 21 June 2015 at 23:02:38 UTC, Andrei Alexandrescu 
wrote:
> While I work on making std.allocator better, here's some food 
> for thought regarding std.collection.
>
> Consider a traditional container with reference semantics, 
> Java-style. Regarding changing the collection (e.g. 
> adding/removing elements) while iterating, we have the 
> following possibilities:
>
> 1. Leave it undefined, like the STL does. Probably this is too 
> extreme.
>
> 2. Throw an exception if a remove is attempted while ranges 
> exist. This works but it's conservative - e.g. it throws even 
> if those ranges are never to be used again etc.
>
> 3. Allow the removal but throw from the ranges if there's any 
> attempt to use a range following a remove.
>
> 4. Make it work such that ranges continue to be valid post 
> removal. Perhaps this is on the inefficient side.
>
>
> Andrei

First,

There is an alternative: Lazy Removal.  This allows one to remove 
from the container while iterating over it by not removing 
immediately but after the iteration has actually happened. Lazy 
Removal can easily be implemented efficiently by using a bit 
sequence to represent the removed state of each item. This is to 
provide the appropriate null reference when retrieving an item 
that has been removed. Of course, one could lead it up to the 
user to avoid accessing removed elements. (if they removed them, 
it should be easy to know or keep track manually)

Second,
Case 1, unfortunately. There is no valid solution as T. S. has 
mentioned EXCEPT to prevent any immediate removal. (since T.S. 
showed that removal while iterating is bad, we can't have it) 
Hence to simulate this see :First:.

To make immediate changes when they are ok. The programmer can 
have access to a "Flush" which will immediately remove all 
"cached removals".


In fact, to make like easier all removals should be cached while 
iterating. Once iterating is done, the removals are flushed. This 
is a clearly defined and easily implementable solution that 
provides the best of both worlds.

e.g.,

     Remove(x)  - Removes the item x from the container 
immediately if the container is not being iterated over, else it 
waits until the container is no longer being iterated over. This 
is safe since no real action on the container is taken while the 
container is "in use".
     Flush()  - Removes all cached items from Remove(x) from the 
container. Unsafe while iterating over.
     RemoveNow(x) - Immediately removes the item x from the 
container regardless of iteration. Usafe while iterating over.