On Fri, 12 Aug 2011 16:58:15 -0400, Ellery Newcomer
<ellery-newco...@utulsa.edu> wrote:
On 08/12/2011 03:29 PM, Steven Schveighoffer wrote:
On Fri, 12 Aug 2011 15:54:53 -0400, Ellery Newcomer
<ellery-newco...@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?
Not one that guarantees stability. However, you can implement a remove
that can be proven to be stable for certain cases (basically, as long as
you don't remove one of the endpoints).
Another example of an invalidated range, let's say you have a hash map.
The range has a start and a finish, with the finish being iterated after
the start. If you add a node, it could cause a rehash, which could
potentially put the finish *before* the start!
Then the invalidation is that the range failed to produce an element of
the container?
No, it may crash the program, for example if empty does:
return this.beginNode is this.endNode;
If beginNode is sequentially after endNode, this condition will never be
true.
But there are other definitions of "invalid", I'd call any of these cases
invalidated ranges:
* it fails to iterate valid nodes that were in the range before the
operation, and are still valid after the operation.
* it iterates a node more than once (for example, iterates a node before
the operation, then iterates it again after the operation)
* it iterates invalid nodes (nodes that have been removed).
-Steve
