C++ invalid comparator

Question

I have a strange problem, maybe I'm missing something obvious but I can't fiugre out.

Here is the C++ code that throws the assert:

int compareByX(const Vector2D &a, const Vector2D &b)
{
    if (a.x < b.x) // if i put a.x > b.x nothing changes
        return -1;
    return 1;
}
int main(int argc, char *argv[])
{
    double pts[6] = { 5, 34, 3, 54, 10, 34 };
    std::vector<Vector2D> points;
    for (int i = 0; i < 6; i += 2)
        points.push_back({ pts[i],pts[i + 1] });
    std::sort(points.begin(), points.end(), compareByX);
}

what happens is that first point (3, 54) is tested against (5, 34), and then viceversa. At that point the assert (invalid comparator) is thrown. But as I see it its right to return -1 as 3 is lesser than 5 and then return 1 since 5 is more than 3...

Can you tell me what is wrong with this?

Solution 1

The invalid comparator assert was thrown because the function returned -1 and 1, while std::sort takes only true or false in order to have a weak strict ordering.

By changing the function to:

bool compareByX(const Vector2D &a, const Vector2D &b)
{
   return a.x < b.x;
}

Everything works as expected.

In the end it was indeed a very obvious mistake.

Solution 2

According to the reference for sort a comparator must:

comparison function object (i.e. an object that satisfies the requirements of Compare) which returns ​true if the first argument is less than (i.e. is ordered before) the second. The signature of the comparison function should be equivalent to the following:

bool cmp(const Type1 &a, const Type2 &b);

I guess that what you really want is something as the following:

   std::sort(points.begin(), points.end(), 
         [] (const Vector2D& a1, const Vector2D&a2){return a1.x < a2.x;}
      );

Comments

[BoBTFish]

sort expects the comparison function to return true (1) or false (0). What do you think happens with -1? What about this way of implementing compareByX: { return a.x < b.x; }?

[Some programmer dude]

This std::sort reference should be helpful.

[deight]

Now i get it, thanks! Thought i was working with qsort :/

[stefaanv]

for qsort, you still need to return 0 on equality.

[deight]

Yeah, but first i started with: double diff =a.x-b.x ; return (double(0) < diff) - (diff < double(0)); And then since i had the assert i tried to make the simplest function, and then i was like wtf

[463035818_is_not_a_number]

you already know the answer, but for the question it would be good if you mention what assert you are talking of

[463035818_is_not_a_number]

btw what is a SisVector2D ?

[deight]

I renamed the other to make it more clear, but i forgot the b. Its just a struct with two double x and y. I have now edited the question

[463035818_is_not_a_number]

strictly speaking your answer is wrong. The comparator is only required to return something that is implicilty convertible to bool, thus returning int is fine. The real problem was that your comparator yielded compareByX(a,b) == true and compareByX(b,a) == true at the same time, which means no strict ordering. See here for a working example where the comparator returns an int but is completely fine

[463035818_is_not_a_number]

the should be in the quote isnt that accurate. See here for the more precise statement: "return type: implicitly convertible to bool". Anyhow, the part you put in bold is what caused the problem (while returning int or bool doesnt really matter)

[Davide Spataro]

@tobi303 Yes, but from the point of view of the functions using the comparator it does not really matter. What they see is true or false. It does not matter that you return non-zero for true (or whatever other implicitly convertible to bool) as soon you know how implicit conversion works. Thanks for pointing that out that reference!

[463035818_is_not_a_number]

no problem, I just saw that OPs own answer got that point wrong, and thought it would be worth mentioning here also just to avoid misunderstanding