Non valido <asserzione operatore in ordinamento

Question

Sto cercando di implementare un semplice comparatore per l'ordinamento degli indici in base ai valori in un array "_vec". Ricevo un messaggio di errore di runtime "operatore < non valido". Non riesco a capire che cosa è sbagliato con il codice seguente:

class Compare{ 
vector<int>& _vec; 
public: 
    Compare(vector<int>& vec) : _vec(vec) {} 
    bool operator()(size_t i, size_t j){ 
     if(_vec[i] != _vec[j]) 
     return _vec[i] < _vec[j]; 
     else 
     return (double)rand()/RAND_MAX < 0.5; 
    } 
}; 

sto usando la seguente funzione di chiamata:

sort(inds.begin(),inds.end(),Compare(vals)); 

dove inds è solo una matrice contenente indici da 1 a 15 (diciamo) e vals è l'array di lunghezza 15 con alcuni valori i cui indici ordinati voglio calcolare. L'obiettivo generale è di randomizzare l'ordinamento quando due (o più) voci in val sono uguali. Qualsiasi aiuto?

Answer 1

std::sort() aspetta l'operazione di confronto sia stabile - se un determinato risultato viene restituito quando due oggetti vengono confrontate, il confronto deve restituire lo stesso risultato se tali elementi sono confrontati più tardi. Quando restituisci un valore casuale, ovviamente questo non è necessariamente valido.

C++ 03 25.3/4 "Sort e le operazioni correlate" dice:

Se definiamo equiv (a, b) come comp (a, b) & & comp (b, a!), poi i requisiti sono che comp e equiv sia essere relazioni transitive:

• comp (a, b) & & comp (b, c) implica comp (a, c)
• equiv (a, b) & & equiv (b, c) implica equiv (a, c)

[Nota: In queste condizioni, si può dimostrare che

• equiv è una relazione di equivalenza
• bozzetto induce un pozzo - relazione definita sulle classi di equivalenza determinate da equiv
• La relazione indotta è un rigoroso ordinamento totale.

-end nota]

E per chiarezza, Tabella 28 definisce una relazione di equivalenza:

== è una relazione di equivalenza, cioè, soddisfa le seguenti proprietà :

• Per tutti a, a == a.
• Se a == b, quindi b == a.

Quindi l'operazione Compare() non produrrà una relazione di equivalenza.

È piuttosto piacevole ottenere un'affermazione piuttosto che perdere dati a caso.

Un modo per risolvere il problema di randomizzare l'ordinamento quando due (o più) voci in _vec sono uguali è creare un valore casuale per quegli indici e tenere traccia di quei valori casuali in una mappa dell'indice => valore casuale o qualcosa. Assicurati di tenere traccia di questi valori casuali e utilizzarli in modo tale che le proprietà transitive e di equivalenza di Compare() siano valide.

Answer 2

std::sort aspetta il tuo operatore minore di fornire un transitiva rapporto, vale a dire quando il tipo vede A < B è vero e B < C è vero, è implica che A < C è vero pure.

Nell'implementazione, la regola di transitivity non viene mantenuta: quando due elementi sono uguali, si dice casualmente che uno di essi è maggiore dell'altro. Ciò attiva l'asserzione di debug.

Restituisce falso per valori uguali per risolvere questo problema.