Find common value in two maps without iterating

Question

I have these two maps, each storing 10000+ of entries:

std::map<std::string,ObjectA> mapA;
std::map<std::string,ObjectB> mapB;

I want to retrieve only those values from the maps whose keys are present in both maps.

For example, if key "10001" is found in both mapA and mapB, then I want the corresponding objects from both the maps. Something like doing a join on SQL tables. Easiest way would be to iterate over the smaller map, and then do std::find(iter->first) in each iteration to find the keys that qualify. That would also be very expensive.

Instead, I am considering maintaining a set like this:

std::set<std::string> common;

1) Every time I insert into one of the map, I will check whether it exists in the other map. If it does, I add the key to the above common set.

2) Every time I remove an entry from one of the map, I will remove the key from common set, if it exists.

The common set always maintains the keys that are in both maps. When I want to do the join, I already have the qualifying keys. Is there a faster/better way?

Answer 1

The algorithm is pretty simple. First, you treat the two maps as sequences (using iterators).

• If either remaining sequence is empty, you're done.
• If the keys at the front of the sequence are the same, you have found a match.
• If the keys differ, discard the lower (according to the map's sorting order) of the two.

You'll be iterating over both maps, which means a complexity of O(n+m), which is significantly better than the naive approach with its O(n log m) or O(m log n) complexity.