Trova se una stringa contiene un carattere in C++ (boost consentito)

Question

Supponiamo che abbia una stringa e voglio scoprire se un carattere specifico (come '|') è presente o meno, qual è la tecnica migliore e più veloce da fare così? Conosco l'implementazione della ricerca di stringhe. Sto chiedendo un'implementazione ancora più veloce di questa.

Answer 1

Usa std::string::find

if (str.find('|') != std::string::npos) 
{ 
    // ... 
} 

C'è improbabile che sia qualcosa di più efficiente. O (n) è il meglio che puoi fare. L'implementazione della libreria standard dovrebbe essere praticamente ottimale.

Answer 2

C'è un solo modo per farlo. Basta scorrere la stringa per verificare se il personaggio che stai cercando esiste. È possibile farlo utilizzando la funzione string::find, che ottiene un carattere e restituisce la prima posizione che si verifica nella stringa o string::npos se il valore non è presente. È anche possibile utilizzare std::find, che ottiene due iteratori, begin e end e un valore chiave 'k' e restituisce un iteratore puntato alla prima occorrenza di k nell'intervallo [begin, end] o end se non è stato trovato k. E, naturalmente, è possibile implementare la funzione di ricerca da soli, in questo modo:

string::size_type pos=string::npos; 
for(string::size_type i=0; i<s.size(); ++i) { 
    if(s[i] == key) { 
    pos=i; 
    break; 
    } 
} 
if(pos != string::npos) { 
    // key was found 
} else { 
    // not found 
} 

o questo:

string::iterator pos=s.end(); 
for(string::iterator i=s.begin(); i!=s.end(); ++i) { 
    if(*i == key) { 
    pos=i; 
    break; 
    } 
} 
if(pos != s.end()) { 
    // found 
} else { 
    // not found 
} 

Maggiori informazioni sul std::string::find e std::find:

• http://www.cplusplus.com/reference/string/string/find/
• http://www.cplusplus.com/reference/algorithm/find/

Answer 3

Data la tua affermazione che vuoi qualcosa più veloce di string :: find, l'unica cosa che posso pensare sarebbe di creare una classe che avesse operatori di assegnazione altamente personalizzati che su ogni aggiornamento della stringa aggiornasse una tabella interna che conteneva il prima posizione nella stringa di ogni carattere possibile (256 per una stringa di caratteri, 65536 (?) per una stringa ampia). Questo ha O (1) ricerca a scapito di un bel po 'di complessità aggiunta alle operazioni non const.

Answer 4

Un altro modo è quello di utilizzare la funzione strchr sulla stringa c_str corrispondente:

if(strchr(str.c_str(), '|')) 
{ 
    \\found 
} 

Non so come si paragona a std trovare in termini di velocità anche se ...

La posizione del trovato carattere è

size_t pos = strchr(str.c_str(),'|') - str.c_str(); 

Answer 5

Aggiunta sulla risposta di Tom Tanner. Se non vuoi eseguire calcoli a priori, sarai bloccato su O (n), cioè esiste una correlazione lineare tra la lunghezza della stringa che stai cercando e il consumo di tempo. Tom ha suggerito di impostare un array (o vettore) di valori booleani che indica se si è verificato un determinato personaggio. Avrebbe bisogno di O (n) una volta per indicizzare la stringa, ma in tal caso è possibile verificare qualsiasi numero di caratteri in O (1) (tempo costante) se è incluso. Il lato negativo di questo approccio è che avrete bisogno di molta memoria (una volta che decidete di dover supportare l'unicode).

Come compromesso è possibile utilizzare un file std :: set o simile, memorizzando solo i caratteri effettivamente presenti nella stringa di input.Il consumo di memoria sarebbe quindi lineare rispetto al numero di caratteri diversi nella stringa, ma la ricerca sarebbe O (log n), cioè logaritmico nel tempo.

Ovviamente è necessario misurare/profilo e quindi spiegare qui per quale caso di utilizzo si sta effettivamente ottimizzando. Finché non lo hai fatto, segui ciò che è più facile da capire e leggere.

Answer 6

Da this source test empirico fatto con Visual Studio 2013 compilatore mostra che strchr di routine è di circa 2 volte più veloce di std :: string :: trovare attuazione.

Answer 7

Si può provare questo:

string s1 = "Hello"; 
    string s2 = "el"; 
    if(strstr(s1.c_str(),s2.c_str())) 
    { 
    cout << " S1 Contains S2"; 
    }