Container insertion and removal

[Andrei Alexandrescu]

Steven Schveighoffer 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?

With GC, you can softRemove things without invalidating iterators.

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

Singly linked lists, doubly linked lists, various trees - three's a 
crowd. Most node-based containers support softInsert.


Andrei