simp1eton's blog

Extremely Weird Bug with Sets
By simp1eton, 14 years ago, In English
Hi all,

I have this really weird bug with STL set that I cannot understand.

My set function is given below.

struct pt{int a,b,node;}tmp,ins;
struct cmp{
    bool operator()(pt a, pt b){
        if(ans[a.node] != ans[b.node]) return ans[a.node] < ans[b.node];
        if(a.node != b.node) return a.node<b.node;
        if(a.a != b.a) return a.a<b.a;
        return a.b<b.b;
    }
};
set <pt,cmp> pq;

I am using this modified set for running dijkstra algorithm. However, I got some infinite loop somewhere. When I ran some debugging output, I noticed something extremely weird.

//Code portion with bug

while(!pq.empty()){
       tmp = *pq.begin();
       pq.erase(tmp);
      printf("removed %d %d %d\n", tmp.node, tmp.a, tmp.b);  //This node is removed.
       if(pq.find(tmp) == pq.end()) printf("erased\n");    //This line is printed, which means the element is removed
       printf("first element is now %d %d %d\n", pq.begin()->node, pq.begin()->a, pq.begin()->b);
               //Amazingly, the first element is exactly the same as tmp! And I thought I already deleted it and cannot find it in the set...
}

Can someone tell me what is wrong? Is there something wrong with my comparison function or something that leads to the bug?

Thanks in advance.
Tags gcj
  • Vote: I like it
  • 0
  • Vote: I do not like it

14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
hm.. your code works fine in my PC. The top most element is successfully removed.
Can you paste the whole code?
→ Reply
14 years ago, # |
  Vote: I like it +12 Vote: I do not like it
I think it'll be great if you paste your code not here, but in other service like Codepad.
Thanks in advise.
→ Reply
14 years ago, # |
  Vote: I like it +3 Vote: I do not like it
Maybe you change ans[] array somewhere in the loop?
It breaks the comparison condition and internal set data structure becomes incorrect.
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Another possible reason - you don't check that set is not empty before the last printf.
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Hi all,

My friend has found the bug for me.

In case anyone is interested, the bug is actually in the comparison function. In my comparison function, the elements in the set are actually only sorted by the array ans[]. However, there might be multiple such elements with the same ans[] element but with different a and b values. Yet, when I update the value of ans[], I will only be inserting and removing one element and will not be updating all the elements with the same ans[] value. Therefore, over time, my set might get unsorted, which leads to problems like the one given above.

But thank you all for trying to help :)
→ Reply