Container insertion and removal

[Steven Schveighoffer]

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?

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

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.

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.

-Steve