Re: intersection of two std::maps
jacek.dziedzic@gmail.com wrote:
Mark P wrote:
Pushing
all of the values into a set is one possibility. I don't see any
advantage to your multiset proposal. I think what I would do is:
1. Copy all values from each map to a separate vector.
2. Sort each vector.
3. Use std::set_intersection to obtain the intersection.
I understand, except for the vector part. Why not copy
each map to a separate set and then do set_intersection?
You could do that as well. It's fewer lines of code, perhaps, but
conventional wisdom is that unless you need to sort "online", it's
generally more efficient to collect all values and perform a single sort
operation at the end (as I suggest) rather than maintaining a sorted
structure as items are individually added (the set approach). See Scott
Meyers "Effective STL" and do keep in mind the usual caveats about
premature optimization, but I would expect better performance with the
vector.
If copying values is too costly you can also use vectors of pointers to
the original values in the map, but then you'll need to write your own
comparison functions for steps 2 and 3, and do some additional copying
at the end.
Nope, the elements are lightweight (size_t's), but there
are a lot of them. Typically there would be 1M elements in
each of the maps and the maps would be almost identical,
with differences in the order of several elements.
thanks, I guess I'll stick with your proposal,
- J.