container stuff
Andrei Alexandrescu
SeeWebsiteForEmail at erdani.org
Wed May 26 08:38:47 PDT 2010
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
More information about the Digitalmars-d
mailing list