[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?
Auto comment: topic has been updated by RogueNinja (previous revision, new revision, compare).
Auto comment: topic has been updated by RogueNinja (previous revision, new revision, compare).
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.
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.
But won't your ordering of elements in the set change in the first and second case?
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)
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.
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://codeforces.me/contest/802/submission/27698161
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 ??
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.