1

I have declared two maps m1 and m2.

Map m1's keys are in the keys of m2. But all the keys of m2 are not in the keys of m1.

Can anyone help me how to find the uncommon keys in m2 compared to the keys of m1?

Example

m1 contains:

3=> 1  2  4
6=> 3  4 6

m2 contains:

3 =>  3  5  6
6 =>  6  4  8
8 =>  2  4  3
10 => 2  5  7  9

The output would be 8 and 10.

Ray Toal
  • 86,166
  • 18
  • 182
  • 232
user3625208
  • 21
  • 1

3 Answers3

3

You can do it by std::set_difference. Example:

std::map<int, std::string> m1;
m1[3] = "1 2 4";
m1[6] = "3 4 6";
std::map<int, std::string> m2;
m2[3] = "3 5 6";
m2[6] = "6 4 8";
m2[8] = "2 4 3";
m2[10] = "2 5 7 9";

std::map<int, std::string> m3;
std::set_difference(m2.begin(), m2.end(), m1.begin(), m1.end(), std::inserter(m3, m3.begin()), m1.value_comp());

for (auto i = m3.begin(); i != m3.end(); ++i) {
    std::cout << "[" << i->first << "," << i->second << "]";
}
std::cout << std::endl;

Result:

[8,2 4 3][10,2 5 7 9]

LIVE

songyuanyao
  • 169,198
  • 16
  • 310
  • 405
  • +1: I also had this solution, but refused to post it because the OP explicitly asked for the *keys* (suppose you have some huge objects in your map's second entry). Can you alter your code somehow such that it inserts the keys into, say, a `std::vector`? – davidhigh Oct 15 '14 at 08:22
  • Here would be the ingredient which allows working only with the vector keys: [http://stackoverflow.com/a/16527081/2412846](http://stackoverflow.com/a/16527081/2412846) – davidhigh Oct 15 '14 at 08:29
  • @davidhigh To achieve that, we need a key iterator on the map, by using Boost's `transform_iterator`, or implement it by oneself. Anyway, it depends on OP. :) – songyuanyao Oct 15 '14 at 08:48
1

Here is a solution which works on the keys by defining a new key_iterator, which returns the key elements only. The solution is inspirde by this post.

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

using namespace std;

typedef std::map<int,std::string> MapType;
typedef MapType::iterator IteratorType;

struct key_iterator : public IteratorType
{
    key_iterator() : IteratorType() {}
    key_iterator(IteratorType it) : IteratorType(it) {}
    int* operator->() {return (int* const)& IteratorType::operator->()->first;}
    int operator*()  {return IteratorType::operator*().first;}
};

int main() {

std::map<int,std::string> m1;
m1[3]="1 2 4";
m1[6]="3 4 6";

std::map<int,std::string> m2;
m2[3]="3 5 6";
m2[6]="6 4 8";
m2[8]="2 4 3";
m2[10]="2 5 7 9";

std::vector<int> v;

key_iterator it1_begin=m1.begin();
key_iterator it1_end=m1.end();
key_iterator it2_begin=m2.begin();
key_iterator it2_end=m2.end();

std::set_difference(it2_begin, it2_end, it1_begin, it1_end, std::inserter(v,v.begin()));

for(auto i : v)
    std::cout<<i<<"  ";
std::cout<<std::endl;

    // your code goes here
    return 0;
}

This code prints

8 10

Live example.

If someone comes up with a nicer syntax for invoking std::set_difference, go ahead.

Community
  • 1
  • 1
davidhigh
  • 14,652
  • 2
  • 44
  • 75
0

You didn't specify a programming language, so here's some pseudocode:

m2.keySet() - m1.keySet()

Languages like Python have a - operator that works on sets, so the above is all that is needed.

Here is some actual Python code:

>>> m1 = {'x':4, 'y':3}
>>> m2 = {'x':4, 'y':3, 'z':5}
>>> set(m2.keys())-set(m1.keys())
set(['z'])
Ray Toal
  • 86,166
  • 18
  • 182
  • 232
  • Thanks, actually, I want to write the code in C++, can you help me the code in C++? since I am not familiar in Python. – user3625208 Oct 15 '14 at 07:02
  • Sure, the same technique applies. You probably have two objects of class `std::map`. Extract the keys into a set using the technique described in [this StackOverflow question](http://stackoverflow.com/q/681943/831878) and then you can use `std::set_difference` to subtract the sets. – Ray Toal Oct 15 '14 at 07:20
  • Can we use this techniques without using objects of classes?. I'm new to C++. – user3625208 Oct 15 '14 at 07:23
  • The only way I know of to make a (real) map is to use instances of `std::map`. If you are not using this class, how are you expressing maps? As structs? – Ray Toal Oct 15 '14 at 07:50