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
