Container insertion and removal

[Andrei Alexandrescu]

Steven Schveighoffer wrote:
> On Mon, 08 Mar 2010 13:21:14 -0500, Andrei Alexandrescu 
> <SeeWebsiteForEmail at erdani.org> wrote:
> 
>> Steven Schveighoffer wrote:
>>>  Hm... this seems to be a different problem than I originally was 
>>> thinking about.  So in essence, you want a set of "safe" functions 
>>> that will not adversely affect a range you are using to iterate with?
>>
>> That's the idea. Any documentation of STL containers specifies whether 
>> iterators are invalidated or not by a primitive. The plan is to simply 
>> define a nomenclature (i.e. "softXxx") for primitives that don't 
>> invalidate iterators. That moves the documentation into the name of 
>> the function.
> 
> What I meant was, your example only focuses on the iterator being 
> advanced in the loop.  Another iterator might be invalidated that is not 
> used in the remove function.  Was that the intent?

The examples were given just to illustrate common cases when 
invalidation is relevant. As I mentioned, interesting cases occur when 
long-distance effects occur. The Observer pattern is a perfect example.

>>> BTW, I solved this problem (removing while iterating) in a much 
>>> better/simpler way in dcollections.
>>
>> Do tell!
> 
> I created a method purge, which is used as an opApply in a foreach loop 
> like so:
> 
> foreach(ref erase, v; &container.purge)
> {
>    erase = should_delete_this_guy;
> }

Very nifty indeed!

> One nifty thing about this, purging an entire collection is an O(n) up 
> to O(nlgn) operation, whereas purging a vector as you wrote is an O(n*n) 
> operation.

Good point. The loop with erase is good if you have to occasionally 
erase some element; for bulk conditional erasures the canonical STL 
approach is to use remove() followed by erase():

http://en.wikibooks.org/wiki/More_C%2B%2B_Idioms/Erase-Remove

> I found that one of the biggest reasons I liked about STL's containers 
> over others that I've used is the ability to remove elements from the 
> container while iterating.  Java allows this also, but no foreach, and 
> it doesn't make optimizations, since the iterator is in charge of 
> removal, not the container itself.

Yah, the tail that removes the dog. That's one of the reasons I think 
Java's containers are missing more points than one. In fact the more I 
think of Java containers, the more reasons I find to dislike them. To me 
they're more of a point of negative potential in the design space that 
needs to be carefully navigated away from.


Andrei