invalid operator < while sorting std::list

Question

I have a std::list graph edges and i want to sort the edges based on their destination outdegree and then their indegree. But i am getting getting exception of invalid operator < during my comparison function below is my code. My list contains the pointers to the edges and edges have destination nodes as their member.

bool compareEdges(const Edge  *e1,const Edge *e2){
if(e1->destination->outdegree < e2->destination->outdegree){
    return true;
}
else if(e1->destination->outdegree > e2->destination->outdegree){
    return false;
}
else if(e1->destination->indegree > e2->destination->indegree){
        return false;
    }
return true;

}

And here is the call to the sort function.

currentNode->edgeList.sort(compareEdges);

Please help me in removing this exception.

Thanks

Solution

Your comparator returns true when both relevant fields are equal. This is invalid, so it may well be what the sort implementation has detected via assert.

You're supposed to pass a "less than" predicate to sort: formally a "strict weak order". Anything else is undefined behavior. It seems in this case you got lucky, and the implementation detects that it has got into an impossible situation due to inconsistent comparisons.

Comments

[Abdul Samad]

What does sort have to do if two things are equal in my opinion it just needs a return true or false value. Can you please elaborate a little bit more how it should be if want to sort the edges first on the basics of outdegree and if they are same then on the basics of indegree.

[Steve Jessop]

It must return false when they're equal, I'm afraid your opinion doesn't enter into it ;-) The comparator should behave like "less than", and x < x is false. If you want to know the precise requirements, look up the definition of a "strict weak order".

[Abdul Samad]

So did u mean that i should not return any thing when two values are equal?

[Michael Krelin - hacker]

@AbdulSamad, it's just that you end up with a < b and b < a both true.

[Steve Jessop]

@Abdul: no, I don't mean that you shouldn't return anything. I mean what I said, return false.

[visitor]

else if(e1->destination->indegree >= e2->destination->indegree) - This greater-or-equal modification should turn it into a valid comparator. You really can't sort something if a should go both before and after b (a<b && b<a == true)