to invalidate a range

[Jonathan M Davis]

On Friday, August 12, 2011 12:54 Ellery Newcomer wrote:
> in std.container, the stable* container functions advocate that they do
> not invalidate the ranges of their containers. What does it mean to
> invalidate a range?
> 
> my assumption is it means causing e.g. front or popFront to fail when
> empty says they should succeed or vice versa.

Short answer: The range doesn't point to what it's supposed to point to 
anymore. Don't use it. Its behavior is undefined.

Long answer: This is a classic issue in C++ with the STL, and it applies to 
D's ranges for the same reason. An iterator or a range is valid only so long 
as it continues to point to a valid element in the container that it points 
to. With a vector or Array for instance, if you have an iterator or range 
pointer to that vector/Array and the container is reallocated because you 
appended to it, and it didn't have any capacity left, then you have an 
iterator/range which points to memory which isn't in the container anymore. 
Iterating with that iterator/range would be problematic. In C++, you'd likely 
be iterating over memory which had been deleted, which could cause all kinds 
of problems and would blow up on you in a variety of ways at least some of the 
time. In D, the memory is probably still sitting on the stack exactly as it 
was, so iterating over it would mean iterating over an old version of the 
container. It probably wouldn't blow up, but it definitely wouldn't be what 
you wanted. Adding and removing elements without reallocations causes problems 
too, because the elements get shifted around. The iterator/range may still 
technically be valid and useable, but it doesn't necessarily point to the same 
data anymore.

In the case of container that uses nodes - such as a linked list - because you 
can add and remove elements without affecting other elements, iterators and 
ranges don't tend to get invalidated as easily. As long as you don't remove 
the element (or elements in the case of a range - assuming that it keeps track 
of its two end points, as is likely) that it points to, then adding or 
removing elements from the container shouldn't invalidate the iterator/range.

So, whether a particular operation invalidates an iterator or range depends 
very much on the container and the operation. std.container provides stableX 
functions which do whatever is necessary to guarantee that any ranges which 
point to the container stay valid. However, any other operation which alters a 
container risks invalidating any existing range for that container. It may or 
may not invalidate the range, depending on the container and the operation, 
but it's a risk. The only way to avoid any risk of invalidating ranges is to 
not keep ranges over a container when you alter that container.

So, basically what it comes down to is the short answer. A range which has 
been invalidated doesn't point to what it's supposed to point to anymore, and 
using it results in undefined behavior. It's less likely to blow up in D, 
because it's generally memory-safe, but you're going to get incorrect 
behavior.

- Jonathan M Davis