Why does std::sort work when the comparison function uses greater-than (>), but not greater-than-or-equal (>=)?

user_14406763 0
Viewed 139

On WIN32, Visual Studio 2022. When I define a vector<int> containing one hundred 0s and sort it with the code below, an exception "invalid comparator" throws.

vector<int> v(100, 0);
sort(v.begin(), v.end(), [](const int& a, const int& b)
    {
        return a >= b;
    });

However, if I use return a > b, it will execute well. Why is that?

c++11 c++
2 Answers

This is just how it is required to work. You need strict weak ordering.

For the rationale, I believe that the sufficient explanation is that this enables you to determine whether those elements are equal (useful for e.g. std::sets). <= or >= can't do that.

<= or >= can also do that, but it seems like it was just decided to use < instead of any other relation. With this decision in mind, standard library facilities are implemented and they heavily rely on it.

user_71514940

The problem is that the comparator(aka comparing function) that you've provided does not implement a strict-weak-ordering and thus it violates a precondition of std::sort leading to undefined behavior.

From std::sort:

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

And from Compare:

The return value of the function call operation applied to an object of a type satisfying Compare, when contextually converted to bool, yields true if the first argument of the call appears before the second in the strict weak ordering relation induced by this type, and false otherwise.

This basically means that the comparator function Compare that we provide should not evaluate to true for both of the expressions: Compare(x, y) and Compare(y, x) where x and y are some arguments. Otherwise, the comparator does not obey the strict-weak-ordering.

To solve this you should replace the >= with >.

user_120025700
Related