Concatenación eficiente de cadenas en C ++

Question

Escuché a algunas personas expresar preocupaciones acerca de '' + '' operador en std :: string y varias soluciones alternativas para acelerar la concatenación. ¿Alguno de estos es realmente necesario? Si es así, ¿cuál es la mejor manera de concatenar cadenas en C ++?

Answer 1

El trabajo extra probablemente no valga la pena, a menos que realmente necesite eficiencia. Probablemente tendrá una eficiencia mucho mejor simplemente usando el operador + = en su lugar.

Ahora, después de ese descargo de responsabilidad, responderé su pregunta real ...

La eficiencia de la clase de cadena STL depende de la implementación de STL que esté utilizando.

Podrías garantizar la eficiencia y tener un mayor control tú mismo haciendo la concatenación manualmente a través de las funciones integradas en C.

Por qué el operador + no es eficiente:

Eche un vistazo a esta interfaz:

template <class charT, class traits, class Alloc>
basic_string<charT, traits, Alloc>
operator+(const basic_string<charT, traits, Alloc>& s1,
          const basic_string<charT, traits, Alloc>& s2)

Puede ver que se devuelve un nuevo objeto después de cada +. Eso significa que se usa un nuevo búfer cada vez. Si está haciendo un montón de operaciones extra +, no es eficiente.

Por qué puede hacerlo más eficiente:

• Usted garantiza la eficiencia en lugar de confiar en un delegado para que lo haga de manera eficiente por usted
• la clase std :: string no sabe nada sobre el tamaño máximo de su cadena, ni con qué frecuencia estará concatenando. Puede tener este conocimiento y puede hacer cosas basándose en tener esta información. Esto conducirá a menos reasignaciones.
• Controlará los buffers manualmente para asegurarse de que no copiará toda la cadena en nuevos buffers cuando no quiera que eso suceda.
• Puedes usar la pila para tus buffers en lugar del montón, que es mucho más eficiente.
• string + operator creará un nuevo objeto de cadena y lo devolverá utilizando un nuevo búfer.

Consideraciones para la implementación:

• Mantenga un registro de la longitud de la cadena.
• Mantenga un puntero al final de la cadena y al inicio, o simplemente al inicio y use el inicio + la longitud como un desplazamiento para encontrar el final de la cadena.
• Asegúrese de que el búfer en el que está almacenando su cadena sea lo suficientemente grande como para no tener que reasignar datos
• Use strcpy en lugar de strcat para que no necesite iterar sobre la longitud de la cadena para encontrar el final de la cadena.

Estructura de datos de la cuerda:

Si necesita concatenaciones realmente rápidas, considere usar una cuerda estructura de datos .

Answer 2

Reserve su espacio final antes, luego use el método append con un buffer. Por ejemplo, supongamos que espera que la longitud de la cadena final sea de 1 millón de caracteres:

std::string s;
s.reserve(1000000);

while (whatever)
{
  s.append(buf,len);
}

Answer 3

No me preocuparía por eso. Si lo hace en un bucle, las cadenas siempre preasignarán memoria para minimizar las reasignaciones; solo use operator + = en ese caso. Y si lo haces manualmente, algo como esto o más

a + " : " + c

Luego está creando temporarios, incluso si el compilador podría eliminar algunas copias de valor de retorno. Esto se debe a que en un sucesivo llamado operator + no se sabe si el parámetro de referencia hace referencia a un objeto con nombre o un temporal devuelto por una invocación de sub operator + . Prefiero no preocuparme por eso antes de no haber perfilado primero. Pero tomemos un ejemplo para mostrar eso. Primero presentamos paréntesis para aclarar el enlace. Puse los argumentos directamente después de la declaración de función que se usa para mayor claridad. Debajo de eso, muestro cuál es la expresión resultante:

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

Ahora, además de eso, tmp1 es lo que devolvió la primera llamada al operador + con los argumentos mostrados. Asumimos que el compilador es realmente inteligente y optimiza la copia del valor de retorno. Así que terminamos con una nueva cadena que contiene la concatenación de a y " : " . Ahora, esto sucede:

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

Compare eso con lo siguiente:

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

¡Está usando la misma función para una cadena temporal y para una cadena con nombre! Entonces, el compilador tiene para copiar el argumento en una nueva cadena y anexarlo y devolverlo desde el cuerpo del operator + . No puede tomar la memoria de un temporal y anexar a eso. Cuanto más grande es la expresión, más copias de cadenas deben hacerse.

Next Visual Studio y GCC admitirán semántica de movimiento de c ++ 1x (complementando semántica de copia ) y referencias de valor como una adición experimental. Eso permite determinar si el parámetro hace referencia a un temporal o no. Esto hará que estas adiciones sean increíblemente rápidas, ya que todo lo anterior terminará en una "tubería adicional". sin copias.

Si resulta ser un cuello de botella, aún puede hacerlo

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

Las llamadas append agregan el argumento a * this y luego devuelven una referencia a ellos mismos. Por lo tanto, no se realiza ninguna copia de temporarios allí. O, alternativamente, se puede usar el operator + = , pero necesitaría paréntesis feos para fijar la prioridad.

Answer 4

Para la mayoría de las aplicaciones, simplemente no importará. Simplemente escriba su código, felizmente inconsciente de cómo funciona exactamente el operador +, y solo tome el asunto en sus propias manos si se convierte en un aparente cuello de botella.

Answer 5

A diferencia de .NET System.Strings, std :: strings de C ++ son mutables y, por lo tanto, pueden construirse mediante una concatenación simple tan rápido como a través de otros métodos.

Answer 6

¿quizás std :: stringstream en su lugar?

Pero estoy de acuerdo con el sentimiento de que probablemente deberías mantenerlo mantenible y entendible y luego perfilar para ver si realmente estás teniendo problemas.

Answer 7

En Imperfecto C ++ , Matthew Wilson presenta un concatenador de cadena dinámico que calcula previamente la longitud de la cadena final para tener una sola asignación antes de concatenar todas las partes. También podemos implementar un concatenador estático jugando con plantillas de expresión .

Ese tipo de idea se ha implementado en la implementación STLport std :: string, que no se ajusta al estándar debido a este truco preciso.

Answer 8

std :: string operator + asigna una nueva cadena y copia las dos cadenas de operando cada vez. repite muchas veces y se vuelve caro, O (n).

std :: string append y operator + = por otro lado, aumenta la capacidad en un 50% cada vez que la cadena necesita crecer . Lo que reduce significativamente el número de asignaciones de memoria y operaciones de copia, O (log n).

Answer 9

Para cadenas pequeñas no importa. Si tiene cadenas grandes, es mejor que las almacene como están en vectores o en alguna otra colección como partes. Y adapte su algoritmo para que funcione con ese conjunto de datos en lugar de una cadena grande.

Prefiero std :: ostringstream para concatenación compleja.

Answer 10

Como con la mayoría de las cosas, es más fácil no hacer algo que hacerlo.

Si desea generar cadenas grandes en una GUI, puede ser que lo que sea que esté generando pueda manejar las cadenas en pedazos mejor que como una cadena grande (por ejemplo, concatenando texto en un editor de texto, generalmente mantienen líneas como estructuras separadas).

Si desea exportar a un archivo, transmita los datos en lugar de crear una cadena grande y generarlos.

Nunca he encontrado la necesidad de hacer que la concatenación sea más rápida si elimino la concatenación innecesaria del código lento.

Answer 11

Una matriz simple de caracteres, encapsulada en una clase que realiza un seguimiento del tamaño de la matriz y el número de bytes asignados es la más rápida.

El truco es hacer solo una asignación grande al inicio.

en

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

Puntos de referencia

Para Visual Studio 2015, compilación de depuración x86, mejora sustancial sobre C ++ std :: string.

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

Answer 12

Probablemente el mejor rendimiento si preasigna (reserva) espacio en la cadena resultante.

template<typename... Args>
std::string concat(Args const&... args)
{
    size_t len = 0;
    for (auto s : {args...})  len += strlen(s);

    std::string result;
    result.reserve(len);    // <--- preallocate result
    for (auto s : {args...})  result += s;
    return result;
}

Uso:

std::string merged = concat("This ", "is ", "a ", "test!");