to invalidate a range

[Jonathan M Davis]

On Friday, August 12, 2011 13:58 Ellery Newcomer wrote:
> On 08/12/2011 03:29 PM, Steven Schveighoffer wrote:
> > On Fri, 12 Aug 2011 15:54:53 -0400, Ellery Newcomer
> > 
> > <ellery-newcomer at utulsa.edu> 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?
> > 
> > Say for example, you are iterating a red black tree, and your current
> > "front" points at a certain node. Then that node is removed from the
> > tree. That range is now invalid, because the node it points to is not
> > valid.
> 
> Then there is no way to implement a stable remove from a node based
> container?

Removing elements from a node-based container only invalidates ranges if they 
specifically point to an element which was removed. Whether an iterator is 
invalidated is more obvious, because it points to a specific element, and as 
long as it's not the one which was removed, you're fine. For a range, it's not 
as obvious, because you don't really know how it was implemented internally. 
However, as long as it's effectively holding the begin and end iterators for 
the range (which is almost certainly what it has to do), then you know that 
your rang is fine as long as the first element pointed to and the last 
elemented pointed to weren't removed. You _do_ have the possible concern that 
your range doesn't contain the same elements that it did before (if an element 
was removed from its middle), but the range is still valid.

- Jonathan M Davis