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.
