to invalidate a range

[Jonathan M Davis]

On Friday, August 12, 2011 15:29 Ellery Newcomer wrote:
> On 08/12/2011 03:54 PM, Jonathan M Davis wrote:
> > 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.
> 
> "shouldn't" isn't a guarantee. Where there is "shouldn't", there can't
> be stableRemove*, no?

An implementation can guarantee it as long as your range doesn't directly 
point to an element being removed (i.e. as long as the element isn't on the 
ends - or maybe one past the end, depending on the implementation). But _no_ 
container can guarantee that an iterator or range which directly references an 
element which is removed is going to stay valid - not without playing some 
serious games internally which make iterators and ranges too inefficent, and 
possibly not even then. So, stableRemove is only going to guarantee that a 
range stays valid on as long as the end points of that range aren't what was 
being removed.

> > 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
> 
> suppose your linked list range points to a node X. element in X is
> removed by the linked list, and the range automagically moves to X.next
> (or X.prev). Is the range invalid by this standard or not? (no way 'san
> ifrinn I'm going to implement that, though).

If the element that you removed was the end point of a range, then the range 
won't be valid anymore.

> heh heh. most of this business has only convinced me I want immutable
> containers.

It's only an issue if you keep ranges of a container around and then alter the 
container. If you're just use ranges to do an operation or two and then throw 
them away, it's not an issue. C++ has been this way for years, and it's 
generally not a problem. It _can_ be a problem if you try and keep 
iterators/ranges around while altering a container, but there's not really a 
good way around that. And as long as you're aware of that, you'll be fine. 
It's only when you try and alter a container while retaining ranges to it that 
you're going to have to start worrying about whether a range has been 
invalidated or not.

- Jonathan M Davis