Perché std :: sort crash se la funzione di confronto non è come operatore <?

Il seguente programma è compilato con VC++ 2012.Perché std :: sort crash se la funzione di confronto non è come operatore <?

#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!!! 
}

Se cambio return a <= other.a;-return a < other.a; quindi il programma viene eseguito come previsto senza alcuna eccezione.

Perché?

fonte

2013-08-17 xmllmx

Il comparatore per 'std :: sort' richiede un rigoroso ordine debole, che '<=' non * fornisce *. – WhozCraig

Dovresti scrivere un (0) per A ctor ... ma non si blocca qui comunque! – lpapp

@WhozCraig: il costruttore predefinito li inizializza a zero. – GManNickG

std::sort richiede una selezionatrice che soddisfa la rigida deboli ordinare regola , che si spiega here

Così, il vostro operatore di confronto dice che a < b quando a == b che non segue il rigorosa deboli ordinare regola, è possibile che l'algoritmo si arresti in modo anomalo perché entrerà in un ciclo infinito.

fonte

2013-08-17 17:53:55 xorguy

+1 Questo stabilisce i requisiti del comparatore 'std :: sort'. Lo seguirei usando 'std :: sort (std :: begin (coll), std :: end (coll));' se il compilatore è compatibile con C++ 11 (e gli OP * è * conforme; VS2012). Se cambi mai le dimensioni della tua matrice, o invece usi uno dei contenitori standard, sarai contento di averlo fatto. – WhozCraig

L'immissione di un ciclo infinito dovrebbe semplicemente causarne l'arresto. Invece scarica core. Perché? – btilly

@btilly Penso che 'std :: sort' usi un algoritmo ricorsivo che causerà un overflow dello stack in caso di un ciclo infinito. – xorguy

La risposta per xorguy è abbastanza buona.

vorrei solo aggiungere qualche citazione dalla norma:

25,4 ordinamento e le operazioni correlate [alg.sorting]

Per algoritmi diversi da quelli descritti in 25.4.3 per funzionare correttamente, comp deve indurre uno ordinamento debole rigoroso sui valori.

Il termine rigorosa riferisce al requisito di una relazione irriflessiva (! Comp (x, x) per ogni x), e il termine debole a requisiti che non sono forti come quelle di un ordinamento totale , ma più forte di quelli per un ordinamento parziale.

spiega Così xorguy molto bene: è la funzione comp dice che a < b quando a == b che non segue la stretta debole ordinare regola ...

fonte

2013-08-17 18:29:32

Perché std :: sort crash se la funzione di confronto non è come operatore <?

risposta

Problemi correlati