Container insertion and removal

[Steven Schveighoffer]

On Sat, 06 Mar 2010 11:19:15 -0500, Robert Jacques <sandford at jhu.edu>  
wrote:

> On Sat, 06 Mar 2010 08:19:36 -0500, Steven Schveighoffer  
> <schveiguy at yahoo.com> wrote:
>>
>> How can softRemove not affect iterating ranges?  What if the range is  
>> positioned on the element removed?
>
> It always affects ranges in so far as the range and container are  
> inconsistent, but that is a problem of softInsert as well. Removing an  
> element from an array doesn't invalidate the underlying range, since the  
> memory is still there. And so long as you're not trying to use free  
> lists, linked-lists, trees, etc. can be written so that the ranges never  
> enter an invalid state. If they happen to be pointing at the removed  
> node, they just end up stopping early.

If my linked list range has two node pointers as the implementation, and  
you remove the end node, it's going to end later, not early.
Of course, you can get around this by just storing a current node and a  
length, but that may not be what the user is expecting.  For example, if  
you did a range of a sorted tree from "a" to "f" and it stops at "n", I  
think that would be extremely unexpected.

Stopping early is invalidation also IMO.  If your program logic depends on  
iterating over all the elements you originally intended to iterate, then  
we have big problems if they stop early.

>> The only two containers that would support softInsert would be linked  
>> list and sorted map/set.  Anything else might completely screw up the  
>> iteration.  I don't see a lot of "generic" use for it.
>
> There's all the containers based upon linked-lists, etc like hashes,  
> stacks, queues and dequeues.

Hashes may be rehashed when inserting, completely invalidating a range  
(possibly the end point will be before the starting point).

Yes, the others you mentioned will be valid.  But I still don't see it  
being more useful than just using documentation to indicate insertion will  
not invalidate ranges.  Perhaps I am wrong.

>> Another option is to use a "mutation" field that is checked every  
>> chance by the range.  If it changes, then the range is invalidated.
>
> The mutation field would have to be a version number to support multiple  
> ranges, and given experience with lock-free algorithms which use a 'tag'  
> in a similar manner, this concept is bug prone and should not be relied  
> upon. It would be better to 'lock' the node or container to topology  
> changes, though this does slow things down and has no conflict  
> resolution: removing a locked node would have to throw an exception.

I was not thinking of multithreaded applications.  I don't think it's  
worth making containers by default be multithreaded safe.

The mutation index has been used in Tango forever, and I think was in Doug  
Lea's original container implementations.  I'm pretty sure it is sound in  
single-threaded uses.

-Steve