Chiavi a virgola mobile in std: map

Il seguente codice dovrebbe trovare la chiave 3.0 in una std::map che esiste. Ma a causa della precisione in virgola mobile non verrà trovato.

 map mymap; mymap[3.0] = 1.0; double t = 0.0; for(int i = 0; i  0); } 

Nell’esempio sopra, contains sarà sempre false . Il mio attuale workaround è semplicemente moltiplicare t per 0.1 invece di aggiungere 0.1, come questo:

 for(int i = 0; i  0); } 

Ora la domanda:

C’è un modo per introdurre un fuzzyCompare in std::map se uso le double chiavi? La soluzione comune per il confronto dei numeri in virgola mobile è solitamente qualcosa come ab < epsilon . Ma non vedo un modo semplice per farlo con std::map . Devo davvero incapsulare il double tipo in una class e sovrascrivere l’ operator<(...) per implementare questa funzionalità?

È ansible implementare la propria funzione di confronto.

 #include  class own_double_less : public std::binary_function { public: own_double_less( double arg_ = 1e-7 ) : epsilon(arg_) {} bool operator()( const double &left, const double &right ) const { // you can choose other way to make decision // (The original version is: return left < right;) return (abs(left - right) > epsilon) && (left < right); } double epsilon; }; // your map: map mymap; 

Aggiornato: vedi l’ articolo 40 in STL effettivi ! Aggiornato in base a suggerimenti.

Quindi ci sono alcuni problemi nell’usare i doppi come chiavi in ​​una std::map .

Innanzitutto, NaN , che confronta meno di se stesso è un problema. Se c’è qualche possibilità di inserimento di NaN , usa questo:

 struct safe_double_less { bool operator()(double left, double right) const { bool leftNaN = std::isnan(left); bool rightNaN = std::isnan(right); if (leftNaN != rightNaN) return leftNaN 

ma potrebbe essere eccessivamente paranoico. Non, ripeto, non includere una soglia epsilon nell'operatore di confronto che si passa a un object std::set o simile: questo violerà i requisiti di ordinamento del contenitore e determinerà un comportamento non definito imprevedibile.

(Ho inserito NaN come maggiore di tutti i double s, incluso +inf , nel mio ordine, senza una buona ragione. Meno di tutti i double s funzionerebbe anche).

Quindi usa l' operator< predefinito operator< , o il precedente safe_double_less , o qualcosa di simile.

Successivamente, consiglierei di usare std::multimap o std::multiset , perché dovresti aspettarti più valori per ogni ricerca. Si potrebbe anche rendere la gestione dei contenuti una cosa di tutti i giorni, invece di un caso angolo, per aumentare la copertura del test del codice. (Raccomanderei raramente questi contenitori) Inoltre questo operator[] blocchi operator[] , che non è consigliabile utilizzare quando si utilizzano chiavi in ​​virgola mobile.

Il punto in cui si desidera utilizzare un epsilon è quando si interroga il contenitore. Invece di usare l'interfaccia diretta, crea una funzione di supporto come questa:

 // works on both `const` and non-`const` associative containers: template auto my_equal_range( Container&& container, double target, double epsilon = 0.00001 ) -> decltype( container.equal_range(target) ) { auto lower = container.lower_bound( target-epsilon ); auto upper = container.upper_bound( target+epsilon ); return std::make_pair(lower, upper); } 

che funziona su entrambi std::map e std::set (e multi versioni).

(In una base di codice più moderna, mi aspetterei che un object range sia una cosa migliore per tornare da una funzione equal_range , ma per ora la renderò compatibile con equal_range ).

Questo trova una serie di cose le cui chiavi sono "sufficientemente vicine" a quella che stai chiedendo, mentre il contenitore mantiene le sue garanzie di ordine internamente e non esegue un comportamento indefinito.

Per verificare l'esistenza di una chiave, fai questo:

 template bool key_exists( Container const& container, double target, double epsilon = 0.00001 ) { auto range = my_equal_range(container, target, epsilon); return range.first != range.second; } 

e se si desidera eliminare / sostituire le voci, si dovrebbe considerare la possibilità che ci possa essere più di un colpo di entrata.

La risposta più breve è "non utilizzare valori in virgola mobile come chiavi per std::set e std::map ", perché è un po 'una seccatura.

Se usi le chiavi a virgola mobile per std::set o std::map , quasi certamente non .find mai .find o [] , poiché è altamente probabile che sia una fonte di bug. Puoi usarlo per una raccolta ordinata automaticamente di roba, purché l'ordine esatto non contenga (cioè, un particolare 1,0 è avanti o indietro o esattamente nello stesso punto di un altro 1.0). Anche allora, andrei con un multimap / multiset, poiché affidarmi a collisioni o mancanza di ciò non è qualcosa su cui fare affidamento.

Ragionare sul valore esatto dei valori in virgola mobile IEEE è difficile e la fragilità del codice che si basa su di essa è comune.

Ecco un esempio semplificato di come l’utilizzo di soft-compare (ovvero epsilon o quasi uguale) può portare a problemi.

Lascia epsilon = 2 per semplicità. Inserisci 1 e 4 nella tua map . Ora potrebbe assomigliare a questo:

 1 \ 4 

Quindi 1 è la radice dell’albero.

Ora inserisci i numeri 2 , 3 , 4 in questo ordine. Ciascuno sostituirà la radice, perché è paragonabile ad esso. Allora hai

 4 \ 4 

che è già rotto. (Supponete che nessun tentativo di riequilibrare l’albero sia fatto.) Possiamo continuare con 5 , 6 , 7 :

 7 \ 4 

e questo è ancora più rotto, perché ora se chiediamo se 4 è lì, dirà “no”, e se chiediamo un iteratore per valori inferiori a 7 , non includerà 4 .

Anche se devo dire che ho usato le map s basate su questo sfocato confrontato con l’operatore numerose volte in passato, e ogni volta che ho individuato un bug, non è mai stato a causa di questo. Questo perché i set di dati nelle mie aree applicative non sono mai in grado di stressare questo problema.

Come dice Naszta , puoi implementare la tua funzione di confronto. Quello che lascia fuori è la chiave per farlo funzionare – è necessario assicurarsi che la funzione restituisca sempre false per tutti i valori che rientrano nella tolleranza per l’equivalenza.

 return (abs(left - right) > epsilon) && (left < right); 

Modifica: come sottolineato in molti commenti a questa risposta e ad altri, esiste una possibilità che questo si risolva in modo errato se i valori che si alimentano sono distribuiti arbitrariamente, perché non si può garantire che !(a e !(b risulta in !(a . Questo non sarebbe un problema nella domanda come richiesto , perché i numeri in questione sono raggruppati intorno a 0,1 incrementi; finché il tuo epsilon è abbastanza grande da tenere conto di tutti gli errori di arrotondamento possibili ma è inferiore a 0.05, sarà affidabile. È di vitale importanza che le chiavi della mappa non siano mai più vicine di 2 * epsilon a parte.

Usare i doppi come chiavi non è utile. Non appena esegui operazioni aritmetiche sulle chiavi, non sei sicuro di quali siano i valori esatti e quindi non puoi utilizzarli per indicizzare la mappa. L’unico uso ragionevole sarebbe che i tasti sono costanti.