Re: intersection of two std::maps

From:

Mark P <usenet@fall2005REMOVE.fastmailCAPS.fm>

Newsgroups:

comp.lang.c++

Date:

Mon, 05 Nov 2007 11:02:01 -0800

Message-ID:

<JMJXi.239$TR5.220@nlpi061.nbdc.sbc.com>

jacek.dziedzic@gmail.com wrote:

Hi!

What is the canonical way of finding an intersection of two
std::maps?

I'm not sure there is one. It's a pretty strange request since,
ignoring the keys, the map is not a very useful value container.
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.

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.

-Mark

i.e. I have

std::map<whatever,size_t> map1;
std::map<whatever,size_t> map2;

... and I need an std::vector containing all the values that occur
simultaneously in both of the maps, nevermind the keys. In each
of the maps the values do not repeat.

One idea is to copy all values from map1 into a vector, and then
for each value from map2 check if it's present in the vector already,
if not -- then push it into the vector. This, of course, has ugly
complexity, so perhaps a set would do better. Is there a better
way?

I was also thinking of putting the values into a multiset and then
taking out all values with a count of 2, but there must be a simpler
way.

TIA,
- J.