set difference

[Acr]

Good day.

I'm trying to get the set-theoretical difference of a map:

Example dataset:
1 3
1 6
2 3
2 4
2 5
4 6

difference(1,2) would be all elements that are with 1, but not with 2 (in example 6)

/* Set-theoretical diffence of node i and j */
int StorageMap::difference(int i, int j) {
	map<int,int>::iterator it2;
	map<int,int> difference;

	printf("\nI:\n");
	for (it=mymap.lower_bound (i) ; it != mymap.upper_bound (i); ++it)
		printf("%i =>  %i\n", it->first, it->second);

	printf("\nJ:\n");
	for (it=mymap.lower_bound (j) ; it != mymap.upper_bound (j); ++it)
		printf("%i =>  %i\n", it->first, it->second);

	set_difference(mymap.lower_bound (i), mymap.upper_bound (i),
				   mymap.lower_bound (j), mymap.upper_bound (j),
				   std::inserter(difference, difference.end()), mymap.value_comp()
				   ); 

	printf("\nSet difference:\n");
	
	for (it2=difference.begin() ; it2 != difference.end(); ++it2)
		printf("%i ", it2->second);
	printf("\n");

	return 0;
};

The multimap iterator is defined in the header file.

My output:

I:
1 =>  3
1 =>  6

J:
2 =>  3
2 =>  4
2 =>  5

Set difference:
3

Any ideas?

[bartoli]

Shouldn't you use a multimap for this? A map can only have one value associated to one key

[Acr]

You're right. After changing it I get a wrong result for difference(1,2):
3 6

I was expecting only 6.

I:
1 =>  3
1 =>  6

J:
2 =>  3
2 =>  4
2 =>  5

Set difference:
3 6

[Acr]

I'm thinking the flaw might be in the comparison function.

Two pair objects are compared equal if the first elements in both objects compare equal to each other and both second elements compare equal to each other - they all have to match.

In inequality comparisons (<, >), only the first element is compared, except if both first elements compare equal to each other, in this case only the second element is taken into consideration for the comparison operation.

http://www.cplusplus.com/reference/std/utility/pair/

However, I added 'mymap.value_comp()' to compare only the values..

Any ideas?

[Acr]

I fixed it. For those interested:

/* Set-theoretical difference of node i and j */
int StorageMap::difference(int i, int j) {
	multimap<int,int>::iterator it2;
	multimap<int,int> difference;

	/*
	printf("\nI:\n");
	for (it=mymap.lower_bound (i) ; it != mymap.upper_bound (i); ++it)
		printf("%i =>  %i\n", it->first, it->second);

	printf("\nJ:\n");
	for (it=mymap.lower_bound (j) ; it != mymap.upper_bound (j); ++it)
		printf("%i =>  %i\n", it->first, it->second);
	*/

	//vector<int> a;
	int counter = 0;
	it  = mymap.find(i);
	it2 = mymap.find(j);

	while (it->first == i)
	{
		if(it2->first != j) {
			//printf("List for %i longer than list for %i, include\n", it->first, it2->first);
			//a.push_back(it->second);
			++counter;
			++it;
		}
		else if (it->second < it2->second) {
			//printf("%i=>%i < %i=>%i, include\n", it->first, it->second, it2->first, it2->second);
			//a.push_back(it->second);
			++counter;
			++it;
		}
		else if (it->second > it2->second) {
			//printf("%i=>%i > %i=>%i, exclude\n", it->first, it->second, it2->first, it2->second);
			++it2;
		}
		else {
			//printf("%i=>%i = %i=>%i, exclude\n", it->first, it->second, it2->first, it2->second);
			++it;
			++it2;
		}
	}
	
	/*
	printf("\nSet difference: ");
	for(int i=0; i < a.size(); ++i)
		printf("%i ", a[i]);
	printf("\n");
	*/

	return counter;
};