# Iterating through one map and one multimap and printing the vlaue of common keys

I've got one multimap: mm1 and a map: mm2. The size of mm1 is usually expected to be smaller than mm2. So I begin by iterating through mm1, and for each key in mm1 that also exists in mm2, will print the values of them. e.g. in the following example, first I come up with 2 in mm1, which also exists in mm2; therefor I print "aa" and "bb" from mm1 and "b" from mm2. If we encounter any key in mm1 that cannot be found in mm2, the whole process will be stopped. Example:

(in each pair, number is key, string is value)

mm1:

2, "aa"
2, "bb"
4, "cc"
4, "dd"
5, "ee"

mm2:

1, "a"
2, "b"
3, "c"
4, "d"
6, "e"

output should be:

aa
bb
b
cc
dd
d

For the following input, 4 is not found in the second map and therefore we stop printing values after 2 (even though 5 exists in both of them, it's not printed).

mm1:

2, "aa"
2, "bb"
4, "cc"
4, "dd"
5, "ee"

mm2:

1, "a"
2, "b"
3, "c"
5, "d"

output should be:

aa
bb
b

And here is my code:

#include <map>
#include <string>
#include <iostream>

using namespace std;

int main()
{
multimap<int,string> mm1;
mm1.insert(make_pair(2, "aa"));
mm1.insert(make_pair(2, "bb"));
mm1.insert(make_pair(4, "cc"));
mm1.insert(make_pair(4, "dd"));
mm1.insert(make_pair(5, "ee"));

map<int,string> mm2;
mm2.insert(make_pair(1, "a"));
mm2.insert(make_pair(2, "b"));
mm2.insert(make_pair(3, "c"));
mm2.insert(make_pair(4, "d"));
mm2.insert(make_pair(5, "e"));

typedef multimap<int,string>::iterator Iter;

pair<Iter, Iter> range1(mm1.begin(), mm1.begin());
Iter next1 = mm1.begin();
map<int,string>::iterator next2 = mm2.begin();

range1 = mm1.equal_range(next1->first);
while (!(range1.first == mm1.end() && range1.second == mm1.end()))
{
next2 = mm2.find(next1->first);
if(next2 == mm2.end()) break;
for (Iter itr = range1.first;itr!=range1.second;itr++)
{
cout << itr->second << endl;
}
cout << next2->second << endl;
next1 = range1.second;
next2++;
if(next1 == mm1.end() || next2 == mm2.end())
break;
range1 = mm1.equal_range(next1->first);
}
return 0;
}


My intention was to iterate over each map only once. Any advice on improving the performance and size of this program would be appreciated!

-
I don't understand what you are trying to achieve. The English description does not seem to match the first example. The key "aa" in mm1 is not in mm2 so why is it in the expected output? –  Loki Astari Nov 12 '12 at 17:23
@LokiAstari "aa" is not a key, it's a value. The numbers are keys. –  Meysam Nov 12 '12 at 18:25
@LokiAstari Updated my question to make it more clear. –  Meysam Nov 12 '12 at 18:36
Sorry. Misread that. Totally my mistake. –  Loki Astari Nov 12 '12 at 19:18

A simple variation on the classic 'find common entries in 2 sorted lists' will do:

void printIntersection(multimap<int,string> mm1, map<int,string> mm2)
{
map<int,string>::iterator iter1 = mm1.begin(), iter2 = mm2.begin();
while (iter1 != mm1.end() && iter2 != mm2.end()) {
if (iter1->first < iter2->first)
iter1++;
else if (iter1->first > iter2->first)
iter2++;
else {   // equal keys, print values
while (iter1 != mm1.end() && iter1->first == iter2->first)
cout << iter1++->second << endl;
cout << iter2++->second << endl;   // unique map key, no need to loop
}   // else
}   // while
}

-
Upon reaching a key in mm1 which is not available in mm2, the iteration should stop. –  Meysam Nov 13 '12 at 6:34
so replace iter1++ with return –  avip Nov 13 '12 at 6:53
mm2.find does a binary search with O(log n) complexity, so strictly speaking your are iterating more than once on mm2 –  Michael Sh Nov 13 '12 at 9:57
You are right, mm2.find is always searching from the first element which is not necessary. Thank you –  Meysam Nov 13 '12 at 10:23