Re: container stuff

[Andrei Alexandrescu]

On 05/25/2010 06:04 PM, Steven Schveighoffer wrote:
What about the purge function of dcollections (i.e. removal while
iterating)?

I operated a few changes to the nomenclature to introduce better support 
for removal, in particular removal while iterating. In particular I 
tightened the complexity of remove and added linearRemove.

http://erdani.com/d/phobos/std_container.html

There are two idioms of choice:

a) If the container supports remove(), then you can remove during 
iteration as follows:

Range r = container[];
while (!r.empty)
{
    if (remove_this_guy)
        r = container.remove(r.take(1));
    else
        r.popFront();
}

That's the case for many associative containers which have low cost for 
removal. Regular arrays won't be able to implement remove() because it 
must have logarithmic complexity.

b) If the container doesn't support remove(), removal is done by packing 
towards the front the stuff to be kept, and then getting rid of it:

Range r = container[];
Range yank = r;
for (; !r.empty; r.popFront())
{
    if (!remove_this_guy)
    {
        yank.front = r.front;
        yank.popFront();
    }
}
container.linearRemove(yank);

See also the remove primitive in std.algorithm which does this (of 
course without the linearRemove call) using a predicate for remove_this_guy.


Andrei