Container insertion and removal

[Andrei Alexandrescu]

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

Well consider an array of File objects, which are reference counted. I'd 
want the resizing of an array to not increment the reference count of 
the files. That means that resizing leaves the old array without 
meaningful content by calling clear() against the remaining files.

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

For remove that should be the case, but probably not for insert.

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

Iterator invalidation has been a notion thoroughly explored by the STL 
and a commonly-mentioned liability of STL iterators. People find it very 
jarring that syntactically identical interfaces have distinct effects on 
iterators, it's a dependency very difficult to track. I'm glad that that 
experience has already been accumulated and that we can build upon it.

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

I think debug vs. release should not affect complexity.


Andrei