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.
