problem with erasing element from a std::set of pointers

[panecasareccio]

Dear all,

I have a problem with set, something very weird happens.

I have a std::set of pointers, in which I use a personalized comparator. The personalized comparator which dereferences the pointers to make the comparison.

The weird stuff happens when I try to erase an element from my set. Besides possible memory leaks issues, I get something that in no way I can explain:

Specifically, in origin I have a set of four pointers. Each pointer points to a dynamically allocated object with [new].
Then I identify the iterator of the pointer to be removed by calling std::set::find(...). Then I erase the element by calling std::set::erase(...).
Then I print out the new size of the set, and I get the value size = 3 as we expect.

However, and this is the problem, then I iterate again on the set to print out the values, and it prints out only two elements!!!!

Do anyone has experience with this type of issue? has anyone encountered similar problems before?

Any suggestion would be more than welcome.


Thanks in advance, Panecasareccio

[long double main]

A short snippet of code demonstrating the issue would be most helpful.

For instance, this works as you might expect:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

#include <iostream> #include <set> class myComp { public: bool operator()(int* a, int *b) { return *a < *b; } }; int main() { std::set<int*,myComp> mySet; for (int i = 0; i < 5; ++i) mySet.insert(new int(i)); mySet.erase(mySet.begin()); // Never mind the memory leak for (int* i : mySet) std::cout << *i << ' '; // Whoops, more memory leaks xD }

1 2 3 4

[panecasareccio]

Hi,

I have struggled a bit to make a smaller version of the code which is:

1. Small enough to fit in a post
2. Complete enough so that the bug will show up.

Following there is a snippet of the concerned code.

std::set<AbstractComponent<T>*, AbstractComponentCmp<T> > touches = (ptr_sconn)->addPointCheckTouchs(vox);
{
	ptr_sconn->merge(*it_touches, vox);
	
	//sconn is my set of pointers to Component<T,OP>, with customized comparator ComponentCmp<T,OP>.
	
	//Here I determine [my_ptr], which is is the element I want to erase
	Component<T,OP>* my_ptr = static_cast<Component<T,OP>*>(*it_touches);
	
	
	//Here I search for my_ptr in the set. if not found, I print out a message
	//whrn I compile and run, I get the message
	typename std::set<Component<T,OP>*, ComponentCmp<T,OP> >::iterator my_ite = sconn.find(my_ptr);
	if (my_ite == sconn.end()) printf("element not found!!!\n");
	
	
	//Here I loop through the entire set, and the element IS FOUND
	for (typename std::set<Component<T,OP>*, ComponentCmp<T,OP> >::iterator it = sconn.begin(); it!=sconn.end(); ++it)
	{
		ComponentCmp<T,OP> comparator;			//comparator is the operator that is used to determine if two elements in the set are the same
		bool b1 = !comparator(*it, my_ptr); 
		bool b2 = !comparator(my_ptr, *it);
		printf("*it = %p, my_ptr = %p, b = %d\n\n", *it, my_ptr, b1&&b2);
		if(b1 && b2) printf("CONTRADDICTION!! element found!!!\n");
		Component<T,OP> my_cmp = **it; 
	}
	
	//here I try to erase the element by passing the iterator.
	//HERE IT CRASHES
	sconn.erase(my_ite);
	
	
	//ALTERNATIVE: here I try to erase the element by passing the element directly instead of the iterator
	//IT DOES NOT CRASH. HOWEVER, THE SIZE OF THE SET IS REDUCED BY TWO, WHICH MAKES NO SENSE!!!
	
	//sconn.erase(my_ptr);
	//printf("erased\n");
	//printf("sconn.size = %d, distance = %d\n", sconn.size(), std::distance(sconn.begin(), sconn.end()));
	
	//delete my_ptr;
}

The issue is on the line:

sconn.erase(my_ite);

if that line is commented out, the program runs without issue. Even inside valgrind it does not have any issue (other than some memory leaks, but that is not a point now)

but it crashes on that line, and I do not understand why.

I have also tried to erase the element by passing the element itself rather than the iterator.
Something even scarier happens: the code does not crash, but it removes TWO elements....

I have spent the last few days trying to debug it, with no result.
Maybe someone of you have some hints for me?

In case you want to do some test, I have put here a smaller version of the code that compiles, runs, and causes the bug to occur:
https://dl.dropboxusercontent.com/u/35716710/code.zip


I thank you in advance for your kind help.
Panecasareccio.

[cire]

Does your custom comparator preserve a strict weak ordering of elements as the standard requires?

https://ece.uwaterloo.ca/~dwharder/aads/Abstract_data_types/Weak_ordering/

[panecasareccio]

Hello Cire,

Yes, I think it does.
But let's look at it again, just in case I am missing something important

Here is the implementation:

template<class T, template<class U> class OP>
class ComponentCmp 
{
public:
	ComponentCmp() {}
	bool operator() (const Component<T,OP>* c1, const Component<T,OP>* c2) const
	{
		bool b = OP<T>::cmp(c1->innExtrVal(), c2->innExtrVal()) || ((c1->innExtrVal()==c2->innExtrVal()) && (c1->index<c2->index));
		
		return b;
	}
};

Here, OP<T>::cmp is either equivalent to std::less or to std::greater, depending on OP. Therefore, the comparison returns true if c1->innExtrVal() is less c2->innExtrVal() or, in case they are equal, if c1->index<c2->index.

Because there are never two components with the same value of index, it seems to me that this is a strict weak ordering.

Am I correct?


I thank you again,
Panecasareccio

[cire]

	typename std::set<Component<T,OP>*, ComponentCmp<T,OP> >::iterator my_ite = sconn.find(my_ptr);
	if (my_ite == sconn.end()) printf("element not found!!!\n");
	
	
	//Here I loop through the entire set, and the element IS FOUND
	for (typename std::set<Component<T,OP>*, ComponentCmp<T,OP> >::iterator it = sconn.begin(); it!=sconn.end(); ++it)
	{
		ComponentCmp<T,OP> comparator;			//comparator is the operator that is used to determine if two elements in the set are the same
		bool b1 = !comparator(*it, my_ptr); 
		bool b2 = !comparator(my_ptr, *it);
		printf("*it = %p, my_ptr = %p, b = %d\n\n", *it, my_ptr, b1&&b2);
		if(b1 && b2) printf("CONTRADDICTION!! element found!!!\n");
		Component<T,OP> my_cmp = **it; 
	}
	
	//here I try to erase the element by passing the iterator.
	//HERE IT CRASHES
	sconn.erase(my_ite);

That final line is an issue any time the second line evaluates to true. Even if you have an invalid iterator for erase and print our your "not found" message, you pass the iterator to erase.

In the case of the "alternate" code, I don't see the behavior you do. The erase fails to remove any element from the set, which I would expect since find also fails to locate the element.

In the alternative erase code it might be informative to change:

	sconn.erase(my_ptr);
	printf("erased\n");

to
printf( "%u elements removed by erase\n", sconn.erase(my_ptr));

No further time to look at the moment.

[norm b]

I agree with Cire. The crash is probably because you are calling erase on an invalid iterator.

panecasareccio wrote:

OP<T>::cmp is either equivalent to std::less or to std::greater, depending on OP. Therefore, the comparison returns true if c1->innExtrVal() is less c2->innExtrVal() or, in case they are equal, if c1->index<c2->index.

Isn't the above why std::set::find fails. You're looking for a match but you get:

bool b = false (innExtrVal()'s are equal) || false (true && false(indexes are equal))

Looks to me like you need another comparator to check for equality.

[panecasareccio]

Dear Cire,

I wish to thank you for the time you spent on my code.

You write:

In the case of the "alternate" code, I don't see the behavior you do. The erase fails to remove any element from the set, which I would expect since find also fails to locate the element.

This is one of the things that is driving me crazy.
Indeed, as you say, if I try to remove by passing the iterator to erase, it crashes because the iterator identified by find() is invalid.

However, if I try to remove the element by passing my_ptr, it removes 2 elements. In fact, I have replaced that line of code in the way you suggest and when I run it it tells me that 2 elements are removed. Indeed, the size of the set was 4 elements before erasing, it is 2 after erasing.

Very surprisingly, this is what I get when I compile the code and run it.

Not only this contraddicts the fact that the the element is not found, but it is a nonsense itself, since std::set does not allow element repetition, so in no way you can remove 2 elements with a single erase. Am I correct?



===================================================

for norm b:

Hi, you say this:

Isn't the above why std::set::find fails. You're looking for a match but you get:
bool b = false (innExtrVal()'s are equal) || false (true && false(indexes are equal)) 

I do not really get you, the comparator is supposed to return false if c1 and c2 are equal. equality is defined as !comparator(c1,c2) && !comparator(c2,c1). if c1 == c2, then I would get TRUE. Am I correct?


Thank you so much again,
Panecasareccio.

[norm b]

Edit: Obviously my knowledge of associative containers is lacking. Striking through to avoid confusion for anyone who might not read the whole thread.

panecasareccio wrote:

the comparator is supposed to return false if c1 and c2 are equal

That is the point that I was trying to make. For set::find() to work your comparator needs to return true if there is a match.

You can do that by defining operator==() for your class. Your iterator declaration would then be:
typename std::set<Component<T,OP>* >::iterator my_ite = sconn.find(my_ptr);

Or you can supply another template class:

template<class T, template<class U> class OP>
class ComponentEq
{
public:
    ComponentEq() {}
    bool operator() (const Component<T,OP>* c1, const Component<T,OP>* c2) const
    {
        bool b = ((c1->innExtrVal()== c2->innExtrVal()) && (c1->index==c2->index));
        return b;
    }
};

Iterator declaration:
typename std::set<Component<T,OP>*, ComponentEq<T,OP> >::iterator my_ite = sconn.find(my_ptr);

[cire]

norm b wrote:

That is the point that I was trying to make. For set::find() to work your comparator needs to return true if there is a match.

associative containers use the supplied comparator. It must ensure a strict weak ordering among the elements. A "compares equal" comparator isn't sufficient to do that. However, a "less" or "greater" comparator is sufficient to do that and also determine equality. (If a is not less than b, and b is not less than b a, then a and b are equal.) My suspicion here is that the strict weak ordering requirement is not being met.

Unfortunately, drilling down through the inheritance and template layers to find out what is actually going on in the comparison function isn't something I've the time to do. I did notice one of the classes may return a nan value for comparison, which seems like it would wreak havoc with the ordering if actually used in a comparison.

[panecasareccio]

Dear all,

I have found the origin of the bug!!!

In short, because I have a set of pointers, it is possible to modify the content of the pointed variable without changing their position in the set. Consequently, the order of the elements in the set is messed up (ordering based on my own comparator, which deferences the pointers and compares them based on the pointed variable).

The small code below should clarify what I mean.

I wish to thank you all for the inspiring comments I have received, which greatly helped me in understanding what was going wrong in my code.

#include<cstdio>
#include<set>
#include<algorithm>

class compare
{
  public:
	compare() {}
	bool operator() (int* a, int* b){return *a < *b;}
};

int main()
{
	std::set<int*, compare> S;
	const int N = 5;
	int a[N];
	for(int i=0; i<N; i++)
	{
		a[i] = i*i;
		S.insert(a+i);
	}						//S contain 5 pointers. The pointed values are, in this order,  0, 1, 4, 9, 16
	
	//display the content of the set
	printf("Displaying the content of the set:\n");
	for(std::set<int*, compare>::iterator it = S.begin(); it != S.end(); ++it)
		printf("pointer = %p, value = %d\n\n", *it, **it);
	printf("\n");
	
	//Now I mess it up
	int* bug = *S.begin();
	*bug = 500;
	printf("bug = %p, *bug = %d\n\n", bug, *bug);
	
	//display the content of the set
	printf("Displaying the content of the set after mess up - Notice that the values are no longer in the right order:\n");
	for(std::set<int*, compare>::iterator it = S.begin(); it != S.end(); ++it)
		printf("pointer = %p, value = %d\n", *it, **it);
	printf("\n");	
	//notice that [bug] is inside the set, it is indeed on the first position.
	
	//Now I search for bug with .find(). it will not because I have messed up the elements
	std::set<int*, compare>::iterator it_bug = S.find(bug);
	if (it_bug == S.end())
		printf("S.find() -> NOT FOUND!\n");
	else
		printf("S.find() -> FOUND!\n");
		
	//Now I search for the same pointer with std::find, which iterates over the whole set without caring for the order
	it_bug = std::find(S.begin(), S.end(), bug);
	if (it_bug == S.end())
		printf("std::find(...) -> NOT FOUND!\n");
	else
		printf("std::find(...) -> FOUND!\n");
		
	return 0;
}