Re: Pruning a std::map efficiently?
On Apr 1, 10:04 am, Jorgen Grahn <grahn+n...@snipabacken.se> wrote:
Around here, March--April is apple tree pruning time. I have a
slighly different problem:
I have a std::map<K, T> where I want to move all T (or pair<K,
T>) which match some predicate Pred to some other container.
The map may have a size in the millions, and Pred often
matches all, or 50%, or 10% or so of the elements.
I'd prefer to use a standard algorithm for this, rather than
iterating manually, dealing with iterator invalidation and so
on. Avoiding repeated tree rebalancing would be welcome, but I
suspect it's not possible.
What's a good std algorithm for this? I guess std::remove_if()
doesn't work on maps -- since you cannot reorder the elements.
Correct.
Since T is a pointer type in my case, I have some other
options. I can build a new map with only the !Pred elements in
it, swap it with the original, and blow away the original. Not
sure that I would gain performance from that (even more
rebalancing?) but at least the code would be clean ...
If you're going to drop the original map, then there's no point
in removing the elements from it. Some variant on the
non-existant copy_if could be used. A more interesting solution
would be to write it yourself, using the hinting form of insert;
this should speed things up, since there would be no need for
std::map to find the correct insertion point for each insert.
If you had copy_if, I think using an insert_iterator would also
work like this:
std::map< K, T > newMap ;
copy_if( oldMap.begin(), oldMap.end(),
std::inserter( newMap, newMap.end() ),
predicate ) ;
--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orient=E9e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S=E9mard, 78210 St.-Cyr-l'=C9cole, France, +33 (0)1 30 23 00 34