to invalidate a range

[Jonathan M Davis]

On Friday, August 12, 2011 20:03:59 Ellery Newcomer wrote:
> On 08/12/2011 06:34 PM, Jonathan M Davis wrote:
> >> Forgive my being dense, but where is this 'as long as' coming from? If
> >> your range only points to ends in e.g. a linked list, how is it
> >> supposed
> >> to retrieve elements in the middle? I'm having a hard time visualizing
> >> a
> >> range over a node based container that doesn't point to a node in the
> >> middle (at some point in time). The range points to the node to
> >> retrieve
> >> the current front quickly, the node can get removed, the removed
> >> function won't know its invalidating the range without playing yon
> >> internal games, ergo stable remove cannot be.
> > 
> > Are you familiar with iterators? This will be a lot easier if you are.
> > An
> > iterator points to one element and one element only. In C++, you tend to
> > pass around pairs of iterators - one pointing to the first element in a
> > range of elements and one pointing to one past the end. You then
> > usually iterate by incrementing the first iterator until it equals the
> > second.
> 
> Now you're just bludgeoning me into apathy (though my ability to
> communicate seems lacking). The iterator is an abstraction. Beneath it,
> in a node based container, [I expect] will be a pointer to a node, which
> might point to any node in the container. This means that removing any
> node could potentially invalidate a range somewhere. When such a
> conflict arises, you cannot both perform the removal and keep a valid
> range, regardless of whether you even knew of the conflict.

It means that if you're dealing with a node-based container, and you remove an 
element from that container, and you have a range which does not have that 
element at either of its ends, then you know that your range is valid. If 
you're keeping random ranges around and removing elements from the container, 
then no, you can't know whether the range is still valid or not.

What it really comes down to is that you don't keep ranges around long term, 
and that if you're altering a container, and you're using a range over that 
container at the same time, you need to be sure of what you're doing. If you 
are, then you can use the range in spite of altering the container. If you're 
not, then you're in trouble. The simplest thing to do, of course, is to just 
not alter a container while you have ranges which refer to it (or to get rid 
of any ranges that you have over a container when you do alter that 
container).

- Jonathan M Davis