Почему std:: sort crash, если функция сравнения не является оператором <?

Следующая программа скомпилирована с VС++ 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!!!
}

Если я изменяю return a <= other.a; на return a < other.a;, то программа работает как ожидалось без исключения.

Почему?

Ответы

Ответ 1

std::sort требует сортировщика, который удовлетворяет правилу строгого слабого упорядочения, что объясняется здесь

Итак, ваш компартер говорит, что a < b, когда a == b, который не следует правилу строгого слабого упорядочения, возможно, что алгоритм потерпит крах, потому что он войдет в бесконечное цикл.

Ответ 2

Ответ на xorguy довольно хорош.

Я бы просто добавил некоторые цитаты из стандарта:

25.4 Сортировка и связанные операции [alg.sorting]

Для того, чтобы алгоритмы, отличные от описанных в 25.4.3, работать корректно, comp должен вызвать строгий слабый порядок значений.

Термин "строгий" относится к требованию нефлексивного отношения (! comp (x, x) для всех x), а термин слабый к требованиям, которые не так сильны, как требования для полного упорядочения, но более сильные, чем для частичный порядок.

Итак, xorguy объясняет это очень хорошо: функция comp говорит, что a < b, когда a == b, которая не соответствует правилу строгого слабого упорядочения...