Uso di std :: sort et al. con una routine di confronto definita dall'utente

Question

Uso di std :: sort et al. con una routine di confronto definita dall'utente

#1 da (2 voti)

5

Nel valutatore di un linguaggio personalizzato, vorrei sostituire le nostre routine di ordinamento con std::sort o altre routine, possibilmente tbb::parallel_sort . Il problema è che consentiamo agli utenti della lingua di fornire la propria routine di confronto e, nelle implementazioni che ho provato, std::sort non accetta le routine che non sono rigorose. In particolare, inizia rapidamente a cercare "elementi" al di fuori dell'intervallo iteratore per ordinare.

Suppongo che se inserissi uno strato di riferimento indiretto sugli iteratori, potrei evitarlo usando sentinelle virtuali, ma non c'è ragione di supporre che le chiamate risultanti terminerebbero necessariamente.

Quindi, data una scatola nera bool f(widget const &a, widget const &b) e un ordine totale non controllato dall'utente operator<(widget const &a, widget const &b) , quale sarebbe la quantità minima di chiamate che avrei bisogno di fare per ottenere una chiamata di ordinamento che termina e che ordina secondo f se questo è, in effetti, un ordine? Mi sembra che il seguente dovrebbe funzionare, ma spero che potrei ottenere con meno chiamate a f con un metodo intelligente, forse ricordando le precedenti chiamate di confronto:

bool f_stabilized(widget const &a, widget const &b) {
  bool fab = f(a, b);
  bool fba = f(b, a);
  return (fab != fba) ? fab : (a < b);
}

Sarebbe ragionevole iniziare chiamando solo f e solo dopo aver visto n ^ 2 chiamate per un elenco di lunghezza n a ricorrere a una versione così "stabilizzata"? Mi rendo conto che non vi è alcun motivo per ritenere che il risultato sarebbe stato correttamente ordinato e che avrei dovuto ricominciare da capo con tale wrapper.

c++ algorithms

posta Christopher Creutzig 30.12.2013 - 17:33

fonte

1 risposta

Leggi altre domande sui tag c++ algorithms

Progettazione di servizi orientati al dominio e architettura dei servizi WCF Mobile / Global User Authentication? (Non di dominio e non di impresa)

score 2 · Answer 1

La tua domanda sembra riassumere se la std::sort di C ++ può essere utilizzata con funzioni di confronto che non si comportano come l'operatore < . L'operatore < è un ordine debole e non un ordine totale. Qualsiasi contenitore o algoritmo nella libreria standard C ++ che dipende dall'operatore < presuppone che formi un severo ordinamento debole, e se si viola tale presupposto allora può verificarsi il caos (come hai visto). Quindi, per rispondere senza mezzi termini alla domanda nel tuo titolo, std::sort funziona perfettamente con le routine di confronto personalizzate, ma quelle routine personalizzate devono comportarsi correttamente.

Per quanto riguarda come generare un ordinamento corretto per std::sort dato un possibile ordine totale, puoi provare quanto segue. Data una funzione di ordinamento personalizzata f , definisci una nuova funzione di ordinamento f_weak in questo modo:

template <typename T, typename F>
auto f_weak(F comparator)
{
    return [comparator](T a, T b) {
               return comparator(a, b) // true if a <= b
                        && a != b;
    };
}

e quindi passa f_weak<T>(f) come ultimo parametro a std::sort . Questo codice non è stato testato e utilizza alcune funzionalità C ++ moderne, ma sono sicuro che ne riceverai il significato.