Container insertion and removal

[Robert Jacques]

On Sat, 06 Mar 2010 08:19:36 -0500, Steven Schveighoffer  
<schveiguy at yahoo.com> wrote:
> Andrei Alexandrescu Wrote:
>
>> In the STL world, writing container-independent code is generally
>> shunned (see e.g.
>> http://www.informit.com/content/images/0201749629/items/item2-2.pdf).
>>
>> One problem is a very small intersection between the functionalities
>> offered by the various STL containers, and the conceptual organization
>> that is weaker than that of iterators.
>>
>> A worse problem is iterator invalidation rules, something that we'll
>> need to address too. I'm thinking that the best defense is a strong
>> offense, and I plan to define the following naming convention:
>>
>> Methods such as insert, remove, pushFront, pushBack, removeFront,
>> removeBack, are assumed to affect the container's topology and must be
>> handled in user code as such.
>>
>> In addition to those, a container may also define functions named after
>> the above by adding a "soft" prefix (e.g. softInsert, softRemove...)
>> that are guaranteed to not affect the ranges currently iterating the
>> container.
>>
>> Generic code that needs specific iterator (non-)invalidation rules can
>> use softXxx methods, in confidence that containers not supporting it
>> will be ruled out during compilations.
>>
>> Sounds good?
>
> 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.

> 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.

> 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.