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?

Neutralize

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; }? – Quixote

This std::sort reference should be helpful. – Pulver

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

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

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 – Neutralize

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

btw what is a SisVector2D ? – Zima

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 – Neutralize

Answer 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.

Neutralize

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 – Zima

Answer 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;}
      );

Insipience

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) – Zima

@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! – Insipience

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 – Zima

Answer 3

You'll get this error if your sort function returns the same item even when the parameters are reversed.

Gipson