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
