### rtanmay's blog

By rtanmay, history, 22 months ago, ,

Hello,

I was solving this problem. In this I have sorted the array of structures.

//This is my structure:
typedef struct node
{
int a,b,c;
} node;


Submission

//This gets runtime error on test-32.
//Error: comparison doesn't meet irreflexive requirements, assert(!(a < a)).
bool compare(node n1, node n2)
{
if(n1.c > n2.c) return false;
else return true;
}


Submission

//However this gets accepted, only change is in >=
bool compare(node n1, node n2)
{
if(n1.c >= n2.c) return false;
else return true;
}


Why is this error coming? I thought even if we give only > then for equal value it will return true, so there should not be any problem between comparison of equal elements.

Thank you

• -5

 » 22 months ago, # | ← Rev. 2 →   0 because if x = y then both x < y and y < x according to your first submission. It causes UB while sorting.
•  » » 22 months ago, # ^ | ← Rev. 2 →   0 I am sorry, but can you explain where both x
•  » » » 22 months ago, # ^ |   0 And also x = y means that y comes before x . It should return false if x = y.
•  » » » 22 months ago, # ^ |   +8 Your function says that a < a for any a. Such a function can't be a comparator
•  » » » » 22 months ago, # ^ |   0 Thank you, I understand where I was making mistake.
 » 22 months ago, # |   +6 The comparator function in stl::sort() follows and requires strict weak ordering.eg. Consider Comp for ascending order: bool comp(int x, int y){ if(x < y) return true; // this will ensure that x comes before y if and only if(x < y). return false; } And This is what you are doing : bool comp(int x, int y){ if(x > y) return false; // this function will return true even when (x == y) which does not follow return true; // strict weak ordering. } Your accepted solution solves this problem and that is why it is not throwing any error.
•  » » 22 months ago, # ^ |   0 Thanks a lot! I didn't knew about strict weak ordering.
 » 2 months ago, # |   -24 is it some kind of bug in stl:sort(), why it is giving runtime error when rearranging equal elements?According to me, it should work fine even if we are trying to swap the elements which don't need swapping. Any thoughts on it?
•  » » 2 months ago, # ^ |   0 If you sort with a crap comparator function that returns true for equal elements, then you define "new" math that is right only to you. Because if two elements 'a1' and 'a2' are equal, it is obvious that the statement a1 < a2 is false. AFAIK, std::sort() documentation defines this as undefined behaviour. Reason could be that the underlying algorithm has certain assumptions about the state of the container or something like that.For further reading, Google this: Why must comparator return false when its arguments are equal?