Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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!

share|improve this question
    
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

2 Answers 2

up vote 1 down vote accepted

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
}
share|improve this answer
    
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

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.

share|improve this answer
    
There is no need to merge the two maps. It does not make anything more efficient either. Even if I merge the two, there will be no way to know which keys have been available in both maps. Please read the question again. –  Meysam Nov 13 '12 at 4:55
    
As I've noted earlier, you do not have to create the list, but output values to the screen. Once you hit a condition when the current value does not exist in the second map, you stop processing. This way your code would visit each maps' element only once. –  Michael Sh Nov 13 '12 at 5:57
    
Isn't this what I have already done in my code? I am iterating only once. –  Meysam Nov 13 '12 at 6:39
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.