to invalidate a range

[Steven Schveighoffer]

On Fri, 12 Aug 2011 16:58:15 -0400, Ellery Newcomer  
<ellery-newcomer at 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-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?

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