std.collection - changing the collection while iterating

[Jonathan M Davis 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.

Personally, I have no problem with this whatsoever, but if that's 
considered too extreme, then I'd go with

> 3. Allow the removal but throw from the ranges if there's any 
> attempt to use a range following a remove.

but I'd make it throw an Error, not an Exception, since it'll 
seriously harm @nogc code otherwise, and I don't see how it can 
be considered anything but a logic error if you're continuing to 
iterate over a container with a range or iterator after calling 
erase/remove on the container, and it would invalidate the range 
or iterator. I can see making it so that the range continues to 
work if it wasn't invalidated by the removal (e.g. the removal 
was at some point before or after the range in the container), 
but if it was inside the range, then it should be considered a 
logic error IMHO. To do otherwise would violate how ranges work, 
because they currently guarantee that they only change in length 
with calls to popFront or popBack. And in general, range-based 
algorithms assume that even the values of elements don't change 
while they're being iterated over, so having the range change 
what elements it has without a call to popFront or popBack is 
just begging for trouble.

The other thing to consider is reallocation (e.g. a vector type 
which is appended to can end up being reallocated and invalidate 
its iterators). And I think that that should be treated the same 
way. Either we should just consider it undefined behavior or 
throw an Error.

There are some rare cases where it makes sense to remove elements 
from a container or add them while iterating over them, but in 
general, I don't see how that could be considered anything but a 
bad idea. Certainly, you have to understand exactly how the 
container in question works and whether what you're doing works 
with that type of container (e.g. adding or removing elements 
from the beginning of a linked list while iterating over the end 
of it would be no problem, but doing that with a vector would be 
a disaster). The one place where it can get a bit annoying to not 
be able to remove while iterating is when you're iterating over 
an entire container and removing elements as you go along, but it 
just doesn't make sense to expect a range to continue to work 
when an element has been removed from it, since it fundamentally 
violates how ranges work if how many elements they have changes 
without a call to popFront or popBack.

However, in order to combat the case where you're iterating over 
a container and removing elements from it as you go, we should 
probably go the C++ route and have a remove function which 
returns a range starting at the element after the last element in 
the range that was passed to the remove function. Then, you can 
have code like

for(auto range = container[]; !range.empty;)
{
     //...
     if(pred(range.front))
         range = container.remove(takeOne(range));
     else
         range.popFront();
}

Similarly, we could have a remove function which takes a 
predicate, which would be more idiomatic in many cases, but it 
doesn't work in the general case, since that assumes that you're 
not doing anything else while iterating and that the predicate 
doesn't change while iterating.

Regardless, overall, I don't mind the C++ route with regards to 
iterator invalidation, but if we're not going to go that route, I 
think that we should go with throwing Errors when operating on 
invalidated ranges. The resulting code is then essentially the 
same, but it catches when you screw up your container logic.

- Jonathan M Davis