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

Question

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!

Answer 1

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
}

Answer 2

You can merge both maps to a "list". That should give you O(n) complexity solution where n is a total number of elements in both maps.
map elements are sorted from lower to higher, so simple iteration would yield an ordered list.
To merge maps, you need to iterate both of the maps, instead of insertion to a list, you can just output values to the screen.