RogueNinja's blog

[Solved] Strange behavior of stl or not?
By RogueNinja, history, 8 years ago, In English

[SOLVED] .... Bug was in my code.....

Today while solving this problem I faced a strange behavior with set<>.

I made three identical submissions only with slight changes in compare function to see it's behavior.

My three submission:

verdict : AC

compare function : 

bool operator < ( const data& b ) const {
    if(pos == b.pos)    {
        return num > b.num;
    }
   return pos < b.pos;
}

verdict : AC

compare function : 

bool operator < ( const data& b ) const {
    if(pos == b.pos)    {
        return num < b.num;
    }
   return pos < b.pos;
}

verdict : WA

compare function : 

bool operator < ( const data& b ) const {
   return pos < b.pos;
}

Now, it can be my fault but I always have used third option when I have to compare single variable and class contains multiple variables. Also, choosing this always worked out for me, but it's not the case this time.

Now, I want to know what's causing this and why using third option is wrong? Also, what I should do if I only want to compare single or multiple variables but not all variables?

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by RogueNinja (previous revision, new revision, compare).

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by RogueNinja (previous revision, new revision, compare).

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

This is because in the 3rd case, whenever pos == b.pos, comparator will always return false, so your class will always be after the b class, which shouldn't be the case. If (pos == b.pos), the comparator in the first and second case might return true or false depending upon the num and b.num, so your *this class may be before or after b class in the ordering of set.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I am aware of the fact that in third case it will always return false in case of (pos == b.pos). But I don't see any problem with that. As compare function doesn't depend on num, it doesn't matter what function returns in case of (pos == b.pos) ... Even if it returns all false, it still should give correct ans.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But won't your ordering of elements in the set change in the first and second case?

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        yes, it will change .... and I showed first and second case to prove the fact that, it doesn't matter because my program doesn't depend on variable num. If I have two pair elements (2, 10) and (3, 10) ... and I only want to order it based on second element ..... then both of these orders are correct ....

        (2, 10), (3, 10)

        (3, 10), (2, 10)

        → Reply
»
8 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I believe when you are inserting into set it compares a < b and b < a. Since both these results are the same in the third case it thinks the objects are the same and does not insert the new object.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yes, you are right ..... I thought I only inserted unique position in my set, but for some numbers when there's no next position, I set a same default value for those numbers and that caused the prob.... So it does work, and bug was in my code ..... Thank you

    Here's the ac code which uses third case

    http://mirror.codeforces.com/contest/802/submission/27698161

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I am a beginner and now learning stl. On your class Data there is a line 'data() {}' . Is it necessary?? if not when it is necessary ??

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    That is constructor overloading with no parameter. Though it's not needed in this code, one has to overload it this way so that one can declare an object without any parameter.

    Constructor with no parameter is default and It's not mandatory if I didn't have another constructor ..... but I did have a constructor with 2 parameters .....So I had to overload it this way so that, I am free to declare an object with no parameter.

    → Reply