Container insertion and removal

[Steven Schveighoffer]

On Sat, 06 Mar 2010 14:55:49 -0500, Andrei Alexandrescu  
<SeeWebsiteForEmail at erdani.org> wrote:

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

If you define invalidation by "not pointing to unallocated memory,"  
wouldn't normal remove (not soft remove) also result in valid memory being  
pointed to?  Why do we need a special soft version?

Even if this is what you mean, with allocators (which significantly speed  
up container insert/removal), you may be pointing to a newly valid piece  
of memory that may not be where you want.

I thought you meant by not invalidating that the range would iterate over  
the elements it was originally scheduled to iterate over, sans the removed  
element.

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

Hashes may rehash on insert, invalidating any ranges (it's one of the  
notes of dcollections' HashMap and HashSet).  I guess it depends on if an  
insert alters the ordering of the nodes.  This is why I said sorted  
containers which should be unaffected.

You have a point that this covers a lot of containers however, but I think  
the usefulness of just having a softInsert (I think softRemove is not a  
useful concept) is pretty limited.  It limits you to

BTW, I think its a good idea to think about how to make this work, if we  
can come up with something that covers a lot of ground, I think that's a  
good thing.  I thought of making ranges slower but more robust to  
container changes in debug mode, does this sound useful?  I.e. if you  
compile in non-release mode, removing/adding an element may trigger the  
range to do a O(n) check to validate itself.

-Steve