Il modo migliore per confrontare std :: stringhe

Question

Qual è il modo migliore per confrontare std::string s? Il modo ovvio sarebbe con if/else:

std::string input; 
std::cin >> input; 

if (input == "blahblahblah") 
{ 
    // do something. 
} 

else if (input == "blahblah") 
{ 
    // do something else. 
} 

else if (input == "blah") 
{ 
    // do something else yet. 
} 

// etc. etc. etc. 

Un'altra possibilità è quella di utilizzare un std::map e un switch/case. Qual è il modo migliore per fare un sacco (come 8, 10, 12+) di questi confronti?

Answer 1

Ecco un esempio utilizzando std :: map.

#include <map> 
#include <string> 
#include <iostream> 
#include <utility> 

void first() 
{ 
    std::cout << "first\n"; 
} 

void second() 
{ 
    std::cout << "second\n"; 
} 

void third() 
{ 
    std::cout << "third\n"; 
} 


int main() 
{ 
    typedef void(*StringFunc)(); 
    std::map<std::string, StringFunc> stringToFuncMap; 

    stringToFuncMap.insert(std::make_pair("blah", &first)); 
    stringToFuncMap.insert(std::make_pair("blahblah", &second)); 
    stringToFuncMap.insert(std::make_pair("blahblahblah", &third)); 

    stringToFuncMap["blahblah"](); 
    stringToFuncMap["blahblahblah"](); 
    stringToFuncMap["blah"](); 
} 

uscita è:

second 
third 
first 

I vantaggi di questo approccio sono:

• E 'facilmente estendibile.
• Ti costringe a suddividere le routine di gestione delle stringhe in funzioni separate (programmazione per intenzione).
• funzione di ricerca è O (log n), mentre il vostro esempio è O (n)

considerare di usare boost :: funzione per rendere la sintassi un po 'più bello, soprattutto con le funzioni di membro di classe.

Answer 2

"12" non è molto ... ma comunque.

È possibile utilizzare solo un switch per i tipi integrali (char, int, etc.), di modo che è fuori questione per std::string. L'utilizzo di una mappa sarebbe probabilmente più leggibile.

Quindi, di nuovo, tutto dipende da come si definisce "migliore".

Answer 3

utilizzando operator== è piuttosto buono, ma se le prestazioni sono davvero critiche, è possibile migliorare a seconda del caso d'uso. Se l'obiettivo è scegliere una delle poche scelte ed eseguire un'azione specifica, è possibile utilizzare uno TRIE. Anche se le stringhe sono abbastanza differenti, si potrebbe fare qualcosa di simile:

switch(s[0]) { 
case 'a': 
    // only compare to strings which start with an 'a' 
    if(s == "abcd") { 

    } else if (s == "abcde") { 

    } 
    break; 
case 'b': 
    // only compare to strings which start with an 'b' 
    if(s == "bcd") { 

    } else if (s == "bcde") { 

    } 
    break; 
default: 
    // we know right away it doesn't match any of the above 4 choices... 
} 

usare fondamentalmente un certo carattere della stringa che buona unicità (non deve essere il primo, se tutte le stringhe sono almeno in N lunghezza qualsiasi carattere prima che N lo faccia!) per fare un switch poi fare una serie di confronti su un sottoinsieme delle stringhe che corrispondono a quella caratteristica unica

Answer 4

La risposta a questa domanda dipende fin troppo dal problema. Hai nominato due esempi. Puoi aggiungere alle tue opzioni cose come tabelle hash, espressioni regolari, ecc ...

Answer 5

Con 8, 10 e anche 12 confronti puoi ancora usare lo schema if ... else if ..., niente di male. Se vuoi 100 o qualcosa, ti consiglio di scrivere una funzione che calcoli un hash di stringa (anche con semplici xoring di tutti i caratteri, ma qualche altro buon metodo sarebbe preferibile per una migliore distribuzione) e poi passare il suo risultato come Evan proposto. Se la funzione restituisce numeri univoci per tutte le stringhe di input possibili, è ancora meglio e non richiede confronti aggiuntivi.

Answer 6

Se si intende "più efficiente" da "il migliore", leggere in anticipo.

Sto suggerendo di utilizzare il seguente metodo se c'è davvero molto.
stringa in Switch è in realtà qualcosa sarà in Java 7. (Come parte della Project Coin)

E secondo il proposal, questo è il modo in cui il linguaggio Java intende recepirlo.
Prima viene calcolato il valore di hash di ognuna delle stringhe. Questo problema è quindi un problema di "switch int", che è disponibile nella maggior parte della lingua corrente ed è efficiente. In ciascuna delle case statement, si controlla se questa è realmente la stringa (in casi molto rari stringhe diverse potrebbero essere hash per lo stesso int).
Io personalmente non faccio l'ultimo passaggio in pratica a volte poiché la necessità dipende dalla situazione in cui si trova il programma specifico, cioè se le stringhe possibili sono sotto il controllo del programmatore e quanto deve essere robusto il programma.

Una pseudo campione gli corrisponde

String s = ... 
switch(s) { 
case "quux": 
    processQuux(s); 
    // fall-through 

    case "foo": 
    case "bar": 
    processFooOrBar(s); 
    break; 

    case "baz": 
    processBaz(s); 
    // fall-through 

    default: 
    processDefault(s); 
    break; 
} 

da the fore-mentioned proposal per aiutarvi a capire.

// Advanced example 
{ // new scope for synthetic variables 
    boolean $take_default = false; 
    boolean $fallthrough = false; 
    $default_label: { 
     switch(s.hashCode()) { // cause NPE if s is null 
     case 3482567: // "quux".hashCode() 
      if (!s.equals("quux")) { 
       $take_default = true; 
       break $default_label; 
      } 
      processQuux(s); 
      $fallthrough = true; 
       case 101574: // "foo".hashCode() 
      if (!$fallthrough && !s.equals("foo")) { 
       $take_default = true; 
       break $default_label; 
      } 
      $fallthrough = true; 
     case 97299: // "bar".hashCode() 
      if (!$fallthrough && !s.equals("bar")) { 
       $take_default = true; 
       break $default_label; 
      } 
      processFooOrBar(s); 
      break; 

     case 97307: // "baz".hashCode() 
      if (!s.equals("baz")) { 
       $take_default = true; 
       break $default_label; 
      } 
      processBaz(s); 
      $fallthrough = true; 

     default: 
      $take_default = true; 
      break $default_label; 
     } 
    } 
    if($take_default) 
     processDefault(s); 
}