Concatenación de cadenas eficiente en C++
performance string (11)
A diferencia de .NET System.Strings, las std :: cadenas de C ++ son mutables y, por lo tanto, pueden construirse mediante una simple concatenación con la misma rapidez que a través de otros métodos.
Escuché algunas personas expresando preocupaciones sobre el operador "+" en std :: string y varias soluciones 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 ++?
Como con la mayoría de las cosas, es más fácil no hacer algo que hacerlo.
Si desea enviar cadenas grandes a una GUI, puede ser que lo que sea que esté produciendo pueda manejar las cadenas en pedazos mejor que como una cadena grande (por ejemplo, concatenar texto en un editor de texto, generalmente mantienen las líneas separadas estructuras).
Si desea hacer una salida a un archivo, transmita los datos en lugar de crear una cadena grande y publicarla.
Nunca he encontrado la necesidad de hacer una concatenación más rápida si se elimina la concatenación innecesaria del código lento.
En Imperfect C ++ , Matthew Wilson presenta un concatenador dinámico de cuerdas que calcula previamente la longitud de la cuerda final para tener solo una asignación antes de concatenar todas las partes. También podemos implementar un concatenado 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.
Para cuerdas pequeñas, no importa. Si tiene grandes cadenas, será mejor que las guarde como si fueran vectores o en alguna otra colección como partes. Y addapt su algoritmo para trabajar con ese conjunto de datos en lugar de una gran cadena.
Prefiero std :: ostringstream para la concatenación compleja.
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 las cosas en sus propias manos si se convierte en un cuello de botella aparente.
Reserve su espacio final antes, luego use el método de agregar con un buffer. Por ejemplo, supongamos que espera que su longitud de cadena final sea de 1 millón de caracteres:
std::string s;
s.reserve(1000000);
while (whatever)
{
s.append(buf,len);
}
Una matriz simple de caracteres, encapsulada en una clase que realiza un seguimiento del tamaño de la matriz y la cantidad de bytes asignados, es la más rápida.
El truco es hacer solo una gran asignación al inicio.
a
https://github.com/pedro-vicente/table-string
Puntos de referencia
Para Visual Studio 2015, construcció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 |
Yo no me preocuparía por eso. Si lo haces en un bucle, las cadenas siempre preasignarán la memoria para minimizar las reasignaciones, simplemente usa el operator+= en ese caso. Y si lo haces manualmente, algo así o más
a + " : " + c
Luego está creando temporarios, incluso si el compilador puede eliminar algunas copias de valor de retorno. Esto se debe a que en un operator+ llamado sucesivamente operator+ no se sabe si el parámetro de referencia hace referencia a un objeto nombrado o un temporal devuelto por un operator+ secundario operator+ invocación. Prefiero no preocuparme por eso antes de no haberlo hecho 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 la función que se utiliza 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, en esa adición, tmp1 es lo que fue devuelto por la primera llamada al operador + con los argumentos mostrados. Suponemos 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 que copiar el argumento en una nueva cadena y anexar a eso y devolverlo desde el cuerpo del operator+ . No puede tomar la memoria de un temporal y anexar a eso. Cuanto mayor es la expresión, más copias de cadenas se tienen que hacer.
A continuación, Visual Studio y GCC admitirán la semántica de movimientos de c ++ 1x (que complementa la semántica de copia ) y las referencias de valores como una adición experimental. Eso permite determinar si el parámetro hace referencia a un temporal o no. Esto hará que esas adiciones sean increíblemente rápidas, ya que todo lo anterior terminará en una "adición de canalización" sin copias.
Si resulta ser un cuello de botella, aún puede hacer
std::string(a).append(" : ").append(c) ...
Las llamadas anexadas añaden el argumento a *this y luego devuelven una referencia a ellos mismos. Entonces no se hace copia de provisionales allí. O alternativamente, se puede usar el operator+= , pero necesitaría feos paréntesis para corregir la precedencia.
quizás std :: stringstream en su lugar?
Pero estoy de acuerdo con el sentimiento de que probablemente debería mantenerlo fácil de mantener y comprensible y luego hacer un perfil para ver si realmente está teniendo problemas.
std::string operator+ asigna una nueva cadena y copia las dos cadenas de operandos cada vez. repite muchas veces y se vuelve caro, O (n).
std::string append y operator+= por otro lado, reducen la capacidad en un 50% cada vez que la cadena necesita crecer. Lo que reduce significativamente la cantidad de asignaciones de memoria y las operaciones de copia, O (log n).
El trabajo adicional probablemente no valga la pena, a menos que realmente necesite eficiencia. Probablemente tendrá una eficiencia mucho mejor simplemente usando operator + = en su lugar.
Ahora, después de esa exención de responsabilidad, responderé a su pregunta real ...
La eficacia de la clase de cadena STL depende de la implementación de STL que esté utilizando.
Puede garantizar la eficiencia y tener un mayor control haciendo la concatenación manualmente a través de las funciones incorporadas de 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 buffer cada vez. Si estás haciendo un montón de operaciones extra + no es eficiente.
Por qué puedes hacerlo más eficiente:
- Está garantizando la eficiencia en lugar de confiar en un delegado para que lo haga de manera eficiente para usted
- la clase std :: string no sabe nada sobre el tamaño máximo de su cuerda, ni con qué frecuencia lo concatenará. Puede tener este conocimiento y puede hacer cosas basadas en tener esta información. Esto conducirá a menos reasignaciones.
- Controlará los búferes manualmente para asegurarse de no copiar toda la cadena en búferes nuevos cuando no desee que eso suceda.
- Puede usar la pila para sus almacenamientos intermedios en lugar del montón, que es mucho más eficiente.
- string + operator creará un nuevo objeto de cadena y lo devolverá usando un nuevo buffer.
Consideraciones para la implementación:
- Mantenga un registro de la longitud de la cuerda.
- Mantenga un puntero al final de la cadena y el inicio, o solo el 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 la cadena sea lo suficientemente grande para que no tenga que volver a asignar datos
- Use strcpy en lugar de strcat para no tener que iterar sobre la longitud de la cadena para encontrar el final de la cadena.
Estructura de datos de cuerda:
Si necesita concatenaciones realmente rápidas considere usar una estructura de datos de cuerda .