to invalidate a range

[Steven Schveighoffer]

On Fri, 12 Aug 2011 18:29:00 -0400, Ellery Newcomer  
<ellery-newcomer at utulsa.edu> wrote:

> On 08/12/2011 03:54 PM, Jonathan M Davis wrote:
>>
>> In the case of container that uses nodes - such as a linked list -  
>> because you
>> can add and remove elements without affecting other elements, iterators  
>> and
>> ranges don't tend to get invalidated as easily. As long as you don't  
>> remove
>> the element (or elements in the case of a range - assuming that it  
>> keeps track
>> of its two end points, as is likely) that it points to, then adding or
>> removing elements from the container shouldn't invalidate the  
>> iterator/range.
>
> "shouldn't" isn't a guarantee. Where there is "shouldn't", there can't  
> be stableRemove*, no?

I don't think it's possible to implement stableRemove IMO.  I believe  
SList does claim it, but IMO once you remove an element from a container,  
any range that iterates that element is invalid.

Once we get custom allocators, this is going to become a lot dicier,  
because removing elements actually may deallocate them.

stableAdd is more possible for implementing, as long as adding does not  
significantly change the topology of the container (for example, adding to  
a hash may do a rehash which changes the topology).

-Steve