static const std :: map <string, int> vs if-elseif

Question

Scrivo una funzione che dovrebbe convertire una stringa in un numero. Vedo due possibili varianti di scriverlo:

int convert(const std::string input) { 
    if (input == "one") { 
     return 1; 
    } else if (input == "two") { 
     return 2; 
    } 
    // etc. 
    return 0; 
} 

O

int convert(const std::string input) { 
    static const map<string, int> table = { 
     {"one", 1}, 
     {"two", 2} 
     // etc. 
    } 

    const auto result = table.find(input); 

    if (result == table.end()) 
    { 
     return 0; 
    } 

    return result->second; 
} 

Quale modo è più efficace/accettabile/leggibile?

Answer 1

La risposta dipende molto da come molti differenti stringhe voi stanno andando a sostenere da questo.

A poche stringhe: andare con if-else. Lo sforzo necessario per capire il codice in seguito è poco.

Un sacco di stringhe: creare una mappa. Lo sforzo di comprensione del codice è piccolo rispetto allo sforzo di leggere un enorme costrutto if-else. Probabilmente, dovrai estendere questa lista spesso. L'aggiunta di dati richiede una digitazione inferiore.

Non sono sicuro di quanto la mappa intelligente di C++ utilizzi le stringhe come chiavi. Nel peggiore dei casi, entrambi hanno le stesse prestazioni. Se la lista diventa davvero enorme, potresti pensare di creare un valore hash delle stringhe e usarlo come chiave. Questo potrebbe migliorare notevolmente le prestazioni. Dovrai assicurarti che le collisioni non avvengano però.(Un buon algoritmo di hash e una dimensione di hash a 64 bit dovrebbero essere sufficienti.) Potrebbe essere che le moderne implementazioni cartografiche lo facciano già.

Answer 2

Per un numero ridotto di valori di input possibili, preferirei la soluzione 1 che è semplice e probabilmente ha le migliori prestazioni.

Se l'elenco di valori diventa troppo grande, allora che cosa si ha realmente bisogno è un convertitore tra interi e numeri scritti, e che in realtà è una storia diversa (vedi la libreria "Humanizer" fa riferimento nel commento di NathanOliver

Answer 3

Un (o uno switch, se disponibile) è utile per i casi di piccole dimensioni e puoi anche controllare l'ordine dei test nel caso in cui i test più comuni possano ritagliare rapidamente la ricerca, è possibile testarli per primi

In molti casi, un switch è di gran lunga migliore di un elenco di if-else s. Entrambi sono più facili da leggere e molto probabilmente più veloci. ugh switch non è la scelta migliore con string.

È tuttavia possibile attivare uno enum anziché utilizzare le stringhe; questo è sicuramente l'approccio migliore, ad eccezione di map.

A map o std::unordered_map è di gran lunga migliore per un gran numero di possibilità o quando sono necessarie queste possibilità aggiornate in fase di esecuzione.

Answer 4

Per piccoli file di testo, mi piacerebbe utilizzare una semplice tabella di ricerca:

struct LookupTable { 
    const char* text; 
    int value; 
}; 
const LookupTable table[] = { 
    { "one", 1 }, 
    { "two", 2 } 
}; 
int convert(const char* text) { 
    if (!text) return 0; 
    for (int i=0; i<sizeof(table)/sizeof(LookupTable); i++) { 
     if (strcasecmp(text, table[i].text) == 0) { 
      return table[i].value; 
     } 
    } 
    return 0; 
} 

Per grande insieme di testo, vorrei considerare l'utilizzo std::unordered_map<std::string,int>, e la funzione di hash forse personalizzato (bkdr hash o hash elfo è buono a parole).

---

EDIT: Come David ha sottolineato in commento, se non si desidera che il brutto sizeof, utilizzare il moderno ciclo for:

int convert(const char* text) { 
    if (!text) return 0; 
    for (auto& entry: table) { 
     if (strcasecmp(text, entry.text) == 0) { 
      return entry.value; 
     } 
    } 
    return 0; 
} 

Answer 5

Suggerisco map. La ragione principale è che si adatta meglio, in entrambi i significati possibili della parola.

Se è necessario aggiungere più condizioni in futuro, il che probabilmente è probabile, è più manutenibile e maneggevole per utilizzare la mappa. Inoltre, consente la modifica in fase di esecuzione della tabella di ricerca, che può essere molto utile in alcuni contesti.

Ho dovuto affrontare una domanda simile in qualcosa che sto sviluppando, in cui un simile aspetto doveva essere modificabile da classi di bambini. Ho deciso che le mappe offrivano maggiore flessibilità. Le mappe mi consentono di definire una funzione virtuale, ad esempio getLookup(), che restituisce una tabella di ricerca. In quella funzione posso mantenere una mappa statica (che ho impostato nel modo in cui ho bisogno in occasione della prima chiamata) specifica per quel tipo di classe. Se stai considerando questo tipo di applicazione, ti suggerisco caldamente di mappare le catene. Se le catene sono completamente ingestibili nell'eredità. Inizierai a chiedere "come faccio a cambiare ciò che X risolve?" prima o poi, e ci sarà ben poca risposta pratica oltre agli spaghetti.

Un altro commento: considerare unordered_map. L'iterazione dell'intervallo sembra altamente improbabile per questo caso d'uso.

Answer 6

La ricerca if-else ha una complessità di O (n) mentre la ricerca della mappa O (log n). Inoltre, quando la lista si allunga, le istruzioni if-else diventeranno illeggibili. Pertanto, la mappa è migliore.

D'altra parte riguardante l'argomento dichiarazione di funzione:

int convert(const std::string input) 

avrei cambiare a passaggio per costante riferimento invece di pass-by-costante copia per essere più efficiente:

int convert(const std::string& input) 

Answer 7

Questa è una delle cose X macros sono grandi per:

Questo è simile a @ metodo tabella di ricerca di Calvino, senza dover tenere traccia di mul set tiple di dati in più posti.

//alphabetically sorted by string X macro 

#define MAP_AS_ENUM(e,v,s) MYENUM_##e, 
#define MAP_AS_STRING(e,v,s) s, 
#define MAP_AS_VALUE(e,v,s) v, 
#define MYMAP(OP) \ 
    OP(NONE, -1,"") \ 
    OP(FIVE, 5, "five") \ 
    OP(FOUR, 4, "four") \ 
    OP(ONE, 1, "one") \ 
    OP(THREE, 3, "three") \ 
    OP(TWO, 2, "two") \ 
    OP(ZERO, 0, "zero") 

enum myenums{ MYMAP(MAP_AS_ENUM) }; 
char *mystrings[] = { MYMAP(MAP_AS_STRING) }; 
char myvalues[]={ MYMAP(MAP_AS_VALUE) }; 

//now you can use a binary search on mystrings to get the index 
//which will correspond to the associated enum 

Answer 8

Quale modo è più efficace/accettabile/leggibile?

La soluzione if/else è il più efficiente se avete solo un paio di valori, ed è certamente abbastanza semplice soprattutto per le persone non utilizzati per la libreria standard, tuttavia devolve rapidamente in un pasticcio.

Pertanto, non appena si raggiunge un 5 o più articoli, passare a utilizzare un contenitore.

Avvertenza: sfortunatamente, std::string_view, che eviterebbe un'allocazione di memoria, non è ancora standard; per semplicità userò quindi std::string, anche se se l'allocazione di memoria è un problema, std::string_view o una classe personalizzata CStr sarebbe meglio.

Ci sono 3 scelte valide:

• std::map<std::string, int> e std::unordered_map<std::string, int> sono le scelte più intuitivi, non è chiaro che sarebbe stato più veloce
• std::vector<std::pair<std::string, int>> (ordinate) sarà sempre più efficiente di std::map<std::string, int>

Quindi, se l'efficienza è un problema:

int convert(std::string const& name) { 
    static std::vector<std::pair<std::string, int>> const Table = []() { 
     std::vector<std::pair<std::string, int>> result = { 
      { "one", 1 }, 
      { "two", 2 }, 
      { "three", 3 }, 
      { "four", 4 } 
     }; 
     std::sort(result.begin(), result.end()); 
     return result; 
    }(); 

    auto const it = 
     std::lower_bound(Table.begin(), Table.end(), std::make_pair(name, 0)); 

    if (it != Table.end() and it->first == name) { 
     return it->second; 
    } 
    return 0; 
} 

Un array ordinato è, dopo tutto, il modo più efficiente per eseguire una ricerca binaria, a causa di un comportamento migliore della cache. Dovrebbe anche sovraperformare std::unordered_map su input piccoli per gli stessi motivi.

Ovviamente, è leggermente meno leggibile.

Answer 9

ho fatto qualche crude measurements di molte delle diverse risposte qui, più un paio di mie idee e per il caso dei numeri "uno" a "nove" in GCC ha trovato che questo è stato il più veloce:

int convert(const std::string& input) { 
    static const std::array<std::string, 9> numbers 
     = {"one", "two", "three", "four", "five", "six", "seven", "eight", "nine"}; 
    auto find_result = std::find(numbers.begin(), numbers.end(), input); 
    if (find_result == numbers.end()) 
     return 0; 
    return std::distance(numbers.begin(), find_result) + 1; 
} 

Penso che sia anche ragionevolmente "accettabile" e "leggibile".

Non c'è una grande differenza di prestazioni tra i suggerimenti.

I risultati erano simili con Clang. È interessante notare che è abbastanza diverso per Visual Studio 2015.