rtanmay's blog

By rtanmay, history, 22 months ago, In English,

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

 
 
 
 
  • Vote: I like it
  • -5
  • Vote: I do not like it

»
22 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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   Vote: I like it 0 Vote: I do not like it

    I am sorry, but can you explain where both x<y and y<x are happening? In the compare function if x==y, then it returns true (meaning that x will come before y) but since they are same then it does not matter.

    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      And also x = y means that y comes before x . It should return false if x = y.

    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Your function says that a < a for any a. Such a function can't be a comparator

      • »
        »
        »
        »
        22 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thank you, I understand where I was making mistake.

»
22 months ago, # |
  Vote: I like it +6 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks a lot! I didn't knew about strict weak ordering.

»
2 months ago, # |
  Vote: I like it -24 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?