Dlaczego std :: sort crash, jeśli funkcja porównania nie jest operatorem <?

Question

Poniższy program jest skompilowany z 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!!! 
} 

Jeśli zmienię return a <= other.a; do return a < other.a; następnie program działa zgodnie z oczekiwaniami, bez wyjątku.

Dlaczego?

Answer 1

std::sort wymaga sorter, który spełnia ścisłego słaby nakazujący reguły, co wynika here

Więc twój comparer mówi, że a < b gdy a == b który nie zastosuje się do ścisłego słaby zamawiania zasady, jest możliwe, że algorytm się zawiesi, ponieważ wejdzie w nieskończoną pętlę.

Answer 2

Odpowiedź dla xorguy jest całkiem niezła.

Chciałbym tylko dodać jakiś cytat z normą:

25,4 Sortowanie i związanych z tym działań [alg.sorting]

Dla algorytmów innych niż opisane w 25.4.3 pracować prawidłowo, comp musi induceć ścisłe słabe zamówienie na wartości.

Określenie surowe odnosi się do zapotrzebowania na irreflexive związku (Comp + (x, x) dla wszystkich x), a termin słaby do wymagań, które nie są tak silne jak w przypadku całkowitej zamawiania , ale silniejszy niż w przypadku częściowego zamówienia.

Więc xorguy wyjaśnia to bardzo dobrze: Ty comp funkcja mówi, że a < b gdy a == b który nie zastosuje się do ścisłego słabą zasadę nakazującą ...