Efficiente concatenazione di stringhe in C ++

Ho sentito alcune persone esprimere preoccupazioni per l’operatore “+” in std :: string e vari metodi per accelerare la concatenazione. Qualcuno di questi è davvero necessario? In tal caso, qual è il modo migliore per concatenare le stringhe in C ++?

Probabilmente il lavoro extra non ne vale la pena, a meno che tu non abbia davvero bisogno di efficienza. Probabilmente avrai un’efficienza molto migliore semplicemente usando l’operatore + = invece.

Ora, dopo questo disclaimer, risponderò alla tua domanda attuale …

L’efficienza della class di stringhe STL dipende dall’implementazione di STL che si sta utilizzando.

È ansible garantire l’efficienza e avere un maggiore controllo da soli concatenando manualmente tramite le funzioni incorporate.

Perché operator + non è efficiente:

Dai un’occhiata a questa interfaccia:

 template  basic_string operator+(const basic_string& s1, const basic_string& s2) 

Puoi vedere che un nuovo object viene restituito dopo ogni +. Ciò significa che ogni volta viene utilizzato un nuovo buffer. Se stai facendo un sacco di operazioni extra + non è efficiente.

Perché puoi renderlo più efficiente:

  • Stai garantendo efficienza invece di affidarti a un delegato per farlo in modo efficiente
  • la class std :: string non conosce la dimensione massima della stringa, né la frequenza con cui vi concatenate. Potresti avere questa conoscenza e puoi fare le cose basandosi sull’avere queste informazioni. Ciò comporterà meno ridistribuzioni.
  • Controllerai manualmente i buffer in modo da poter essere sicuro di non copiare l’intera stringa in nuovi buffer quando non vuoi che ciò accada.
  • È ansible utilizzare lo stack per i buffer anziché l’heap, che è molto più efficiente.
  • l’operatore string + creerà un nuovo object stringa e lo restituirà quindi utilizzando un nuovo buffer.

Considerazioni per l’implementazione:

  • Tieni traccia della lunghezza della corda.
  • Mantieni un puntatore fino alla fine della stringa e l’inizio, o solo l’inizio e usa l’inizio + la lunghezza come offset per trovare la fine della stringa.
  • Assicurati che il buffer in cui stai memorizzando la stringa sia abbastanza grande da non dover riassegnare i dati
  • Usa strcpy invece di strcat in modo da non dover iterare sulla lunghezza della stringa per trovare la fine della stringa.

Struttura dati della corda:

Se hai bisogno di concatenazioni davvero veloci, considera l’utilizzo di una struttura di dati della corda .

Prenota prima il tuo spazio finale, quindi usa il metodo append con un buffer. Ad esempio, supponiamo che la lunghezza della stringa finale sia di 1 milione di caratteri:

 std::string s; s.reserve(1000000); while (whatever) { s.append(buf,len); } 

Non me ne preoccuperei. Se lo fai in un loop, le stringhe preallacceranno sempre la memoria per minimizzare le riallocazioni: basta usare l’ operator+= in questo caso. E se lo fai manualmente, qualcosa come questo o più a lungo

 a + " : " + c 

Quindi crea dei provvisori, anche se il compilatore può eliminare alcune copie del valore di ritorno. Questo perché in un operator+ chiamato in successione operator+ non sa se il parametro di riferimento fa riferimento a un object con nome o un valore restituito temporaneo da un sub operator+ invocazione. Preferirei non preoccuparmene prima di non profilare prima. Ma facciamo un esempio per dimostrarlo. Per prima cosa introduciamo le parentesi per rendere chiara l’associazione. Metto gli argomenti direttamente dopo la dichiarazione della funzione che è usata per chiarezza. Al di sotto di questo, mostro che espressione risultante è:

 ((a + " : ") + c) calls string operator+(string const&, char const*)(a, " : ") => (tmp1 + c) 

Ora, in tmp1 , tmp1 è ciò che è stato restituito dalla prima chiamata all’operatore + con gli argomenti mostrati. Assumiamo che il compilatore sia davvero intelligente e ottimizzi la copia del valore di ritorno. Quindi finiamo con una nuova stringa che contiene la concatenazione di a e " : " . Ora, questo succede:

 (tmp1 + c) calls string operator+(string const&, string const&)(tmp1, c) => tmp2 ==  

Confronta questo al seguente:

 std::string f = "hello"; (f + c) calls string operator+(string const&, string const&)(f, c) => tmp1 ==  

Sta usando la stessa funzione per una stringa temporanea e per una stringa denominata! Quindi il compilatore deve copiare l’argomento in una nuova stringa e aggiungerlo e restituirlo dal corpo di operator+ . Non può prendere il ricordo di un temporaneo e aggiungerlo a quello. Più grande è l’espressione, più copie delle stringhe devono essere eseguite.

Next Visual Studio e GCC supporteranno la semantica del movimento di c ++ 1x (che completa la semantica della copia ) e i riferimenti di valore come aggiunta sperimentale. Ciò consente di capire se il parametro fa riferimento a un temporaneo o meno. Ciò renderà tali aggiunte incredibilmente veloci, poiché tutto quanto sopra finirà in una “add-pipeline” senza copie.

Se si rivela un collo di bottiglia, puoi ancora farlo

  std::string(a).append(" : ").append(c) ... 

Le chiamate append aggiungono l’argomento a *this e quindi restituiscono un riferimento a se stessi. Quindi nessuna copia dei provvisori è fatta lì. Oppure, in alternativa, è ansible utilizzare l’ operator+= , ma è necessario disporre di brutte parentesi per fissare la precedenza.

Per la maggior parte delle applicazioni, non importa. Basta scrivere il tuo codice, ignorando beatamente come funziona esattamente l’operatore +, e prendi le cose in mano solo se diventa un collo di bottiglia evidente.

A differenza di .NET System.Strings, le stringhe std :: di C ++ sono modificabili e, pertanto, possono essere costruite mediante una semplice concatenazione altrettanto veloce che con altri metodi.

forse std :: stringstream invece?

Ma sono d’accordo con il sentimento che probabilmente dovresti solo mantenerlo gestibile e comprensibile e poi profilare il profilo per vedere se hai davvero dei problemi.

In Imperfect C ++ , Matthew Wilson presenta un concatenatore di stringhe dinamico che precarica la lunghezza della stringa finale per avere un’unica allocazione prima di concatenare tutte le parti. Possiamo anche implementare un concatenatore statico giocando con modelli di espressioni .

Questo tipo di idea è stata implementata in STLport std :: implementazione delle stringhe – che non è conforms allo standard a causa di questo preciso hack.

std::string operator+ alloca una nuova stringa e copia le due stringhe di operando ogni volta. ripeti molte volte e diventa costoso, O (n).

std::string append e operator+= d’altra parte, aumentano la capacità del 50% ogni volta che la stringa deve crescere. Che riduce significativamente il numero di allocazioni di memoria e le operazioni di copia, O (log n).

Per le stringhe piccole non importa. Se hai grandi stringhe, ti conviene memorizzarle come sono in vettoriale o in qualche altra raccolta come parti. E aggiungi il tuo algoritmo per lavorare con un insieme di dati di questo tipo invece della sola stringa grande.

Preferisco std :: ostringstream per la concatenazione complessa.

Come con la maggior parte delle cose, è più facile non fare qualcosa che farlo.

Se vuoi esportare stringhe di grandi dimensioni su una GUI, potrebbe essere che qualunque cosa tu stia trasmettendo possa gestire le stringhe in pezzi meglio di una stringa di grandi dimensioni (ad esempio, concatenando il testo in un editor di testo – di solito mantengono le linee come separate strutture).

Se si desidera eseguire l’output su un file, eseguire lo streaming dei dati anziché creare una stringa di grandi dimensioni ed emetterli.

Non ho mai trovato la necessità di rendere più rapida la concatenazione necessaria se ho rimosso concatenazioni inutili dal codice lento.

Una serie di caratteri semplice, incapsulata in una class che tiene traccia delle dimensioni dell’array e del numero di byte allocati è la più veloce.

Il trucco è fare solo una grande allocazione all’inizio.

a

https://github.com/pedro-vicente/table-string

benchmark

Per Visual Studio 2015, x86 debug build, miglioramento sostanziale rispetto a C ++ std :: string.

 | API | Seconds | ----------------------|----| | SDS | 19 | | std::string | 11 | | std::string (reserve) | 9 | | table_str_t | 1 |