Search code examples
c++algorithmexceptionstandards

Why will std::sort crash if the comparison function is not as operator <?

The following program is compiled with VC++ 2012.

#include <algorithm>

struct A
{
    A()
        : a()
    {}

    bool operator <(const A& other) const
    {
        return a <= other.a;
    }

    int a;
};

int main()
{
    A coll[8];
    std::sort(&coll[0], &coll[8]); // Crash!!!
}

If I change return a <= other.a; to return a < other.a; then the program runs as expected with no exception.

Why?

Solution

  • std::sort requires a sorter which satisfies the strict weak ordering rule, which is explained here

    So, your comparer says that a < bwhen a == b which doesn't follow the strict weak ordering rule, it is possible that the algorithm will crash because it'll enter in an infinite loop.