Che cosa causa STD :: Ordina () per accedere all'indirizzo fuori portata

Question

Capisco che per utilizzare STD :: Ordinamento (), la funzione Confronta deve essere un ordine debole severo, altrimenti si bloccherà a causa dell'accesso all'indirizzo fuori limite.( https://gcc.gnu.org/ml/gcc-Bugs / 2013-12 / msg00333.html )

Tuttavia, perché sarebbe Std :: Ordinty () Accedi all'indirizzo out-of-bound quando la funzione di confronto non è un ordine debole severo?Cosa sta cercando di confrontare?

Inoltre mi chiedo se ci sono altre insidie in STL che dovrei essere a conoscenza di.

Answer 1

La prima cosa è che chiamare l'algoritmo con un comparatore che non rispetta i requisiti non è definito il comportamento e qualsiasi cosa va ...

Ma a parte questo, presumo che tu sia interessato a sapere quale tipo di implementazione potrebbe finire per accedere ai limiti se il comparatore è cattivo. Se l'implementazione non controlla i limiti prima di accedere agli elementi in primo luogo? I.e. Prima di chiamare il comparatore

La risposta è prestazione, e questa è solo una delle cose possibili che potrebbero portare a questo tipo di problemi. Ci sono diverse implementazioni di ordinamento di algoritmi, ma più spesso, std::sort è costruito in cima a una variante di Quicksort che degenerare su un diverso algoritmo di ordinamento come MergeSort per evitare la prestazione dei casi peggiore rapida.

L'implementazione di Quicksort seleziona un pivot e quindi le partizioni L'ingresso attorno al perno, quindi in modo indipendente ordina entrambi i lati. Ci sono diverse strategie per la selezione del perno, ma una comune è la mediana di tre: l'algoritmo ottiene i valori del primo, ultimo e medio elemento, seleziona la mediana dei tre e lo usa come il valore del rotolo.

Concettualmente partizione cammina da sinistra finché non trova un elemento che non è più piccolo del perno, quindi cammina dal destro che cerca di trovare un elemento che è più piccolo del perno. Se i due cursori si incontrano, la partizione completata. Se vengono trovati gli elementi fuori luogo, i valori sono scambiati e il processo continua nell'intervallo determinato da entrambi i cursori. Il ciclo che cammina da sinistra per trovare l'elemento da scambiare sembrerebbe:

while (pos < end && value(pos) < pivot) { ++pos; }

.

Mentre nella partizione generale non può presumere che il valore del pivot sarà nell'intervallo, Quicksort sa che è, dopo tutto selezionato il perno degli elementi nell'intervallo. Un'ottimizzazione comune in questo caso è quello di scambiare il valore della mediana per essere nell'ultimo elemento del loop. Ciò garantisce che value(pos) < pivot sarà true prima pos == end (caso peggiore: pos == end - 1). L'implicazione qui è che possiamo rilasciare il controllo per la fine dell'intervallo e possiamo usare un unchecked_partition (scegli la scelta del nome) con una condizione più semplice più semplice:

while (/*pos < end &&*/ value(pos) < pivot) ++pos;

.

Tutto perfettamente buono, tranne che < è scritto comparator(value(pos), pivot). Ora se il comparator è implementato in modo errato, potresti finire con comparator(pivot,pivot) == true e il cursore si esaurisce i limiti.

Si noti che questo è solo un esempio di ottimizzazione dell'algoritmo che può rimuovere i limiti check per le prestazioni: assumendo un ordine valido, è impossibile per uscire dall'array nel loop sopra se Quicksort Impostare il perno nell'ultimo elemento prima chiamando questa partizione modificata.

Torna alla domanda:

.

Se l'implementazione non controlla i limiti prima di accedere agli elementi in primo luogo? I.e. Prima di chiamare il comparatore

No, non se rimossa il controllo dei limiti dimostrando che non uscirà dalla matrice, ma ciò dimostra è costruito sulla premessa che il comparatore è valido.

Answer 2

std::sort Richiede effettivamente che il comparatore determinato stabilisca un rigoroso ordinamento debole, altrimenti l'ordinamento non ha molto senso.

Per quanto riguarda l'accesso fuori portata, il link che hai pubblicato è un rapporto di bug, I.e. Non dovrebbe effettivamente farlo. I compilatori come qualsiasi altro software possono e avranno bug. Come notato da Adam questo particolare rapporto di bug è stato rifiutato poiché non è davvero un bug.

Che cosa succede esattamente quando non hai rigoroso ordinamento debole non è definito dallo standard, non ha senso farlo ed è quindi escluso dallo standard. Pertanto è indefinito per omissione. Undefined significa che tutto può accadere, addirittura di accesso fuori portata.

Per evitare di "insidie" è solo a conoscenza dei requisiti degli algoritmi e delle funzioni che usi. Per C ++ c'è un bel sito di riferimento che di solito uso: cppreference

che su La pagina del std::sort dice:

.

Comp - Confronison Function Object (cioè un oggetto che soddisfa i requisiti di confronto) che restituisce true se il primo argomento è inferiore a (I.e. è ordinato prima) il secondo.

Con un collegamento alla descrizione di Confronta