¿Qué rendimiento podemos esperar de std :: string's c_str ()? Siempre en tiempo constante?

13

He estado haciendo algunas optimizaciones necesarias últimamente. Una cosa que he estado haciendo es cambiar algunos ostringstreams -> sprintfs. Estoy corriendo un montón de std :: strings a ac style array, ala

char foo[500];
sprintf(foo, "%s+%s", str1.c_str(), str2.c_str());

Resulta que la implementación std :: string :: c_str () de Microsoft se ejecuta en tiempo constante (solo devuelve un puntero interno). Parece que libstdc ++ hace lo mismo . Me doy cuenta de que el estándar no ofrece garantías para c_str, pero es difícil imaginar otra forma de hacerlo. Si, por ejemplo, copiaran en la memoria, tendrían que asignar memoria para un búfer (dejando que la persona que llama lo destruya, NO es parte del contrato STL) O tendrían que copiar a una estática interna buffer (probablemente no es seguro para subprocesos, y no tiene garantías de por vida). Entonces, simplemente devolver un puntero a una cadena terminada en nulo mantenida internamente parece ser la única solución realista.

c++ performance strings Doug T.
fuente

Respuestas:

9

Si recuerdo, el estándar permite string::c_str()devolver casi cualquier cosa que satisfaga:

  • Almacenamiento lo suficientemente grande para el contenido de la cadena y la terminación NULL
  • Debe ser válido hasta que stringse llame a un miembro no constante del objeto dado

Entonces, en la práctica, esto significa un puntero al almacenamiento interno; ya que no hay forma de rastrear externamente la vida del puntero devuelto. Creo que es seguro asumir que su optimización es un tiempo constante (pequeño).

En una nota relacionada, si el formato de cadena limita el rendimiento; puede encontrar mejor suerte aplazando la evaluación hasta que sea absolutamente necesario con algo como Boost.Phoenix .

Boost.Format Creo que difiere el formato internamente hasta que se requiera el resultado, y puede usar el mismo objeto de formato repetidamente sin volver a analizar la cadena de formato, que he encontrado que hace una diferencia significativa para el registro de alta frecuencia.

rvalue
fuente
2
Es posible que una implementación cree un búfer interno nuevo o secundario, lo suficientemente grande como para agregar un terminador nulo. Aunque c_stres un método constante (o al menos tiene una sobrecarga constante, no recuerdo cuál), esto no cambia el valor lógico, por lo que puede ser una razón mutable. Se podría romper punteros de otras llamadas a c_str, salvo que cualquiera de estos indicadores deben referirse a la misma cadena lógica (lo que no hay nueva razón para reasignar - ya debe haber un terminador nulo) o de lo contrario debe haber sido una llamada a un no -const método en el medio.
Steve314
Si esto realmente es válido, las c_strllamadas pueden ser O (n) tiempo para la reasignación y copia. Pero también es posible que haya reglas adicionales en el estándar que desconozco que evitarían esto. La razón por la que sugiero que - las llamadas a c_strno son realmente destinado a ser común que yo sepa, por lo que no puede considerarse importante asegurarse de que están rápido - evitando que byte adicional de almacenamiento para un terminador nulo normalmente innecesario en stringlos casos que nunca se uso c_strpuede han tenido prioridad.
Steve314
Boost.Formatinternamente pasa a través de corrientes que internamente sprintfterminan con una sobrecarga bastante grande. La documentación dice que es aproximadamente 8 veces más lenta que la normal sprintf. Si desea rendimiento y tipo de seguridad, intente Boost.Spirit.Karma.
Jan Hudec
Boost.Spirit.Karmaes un buen consejo para el rendimiento, pero tenga en cuenta que tiene una metodología muy diferente que puede ser difícil de adaptar el printfcódigo de estilo (y los codificadores) existentes. Me he quedado en gran parte Boost.Formatporque nuestra E / S es asíncrona; pero un factor importante es que puedo convencer a mis colegas para que lo usen de manera consistente (todavía permite cualquier tipo con una ostream<<sobrecarga, lo que evita el .c_str()debate) Los números de rendimiento de Karma .
rvalue
23

En el estándar c ++ 11 (estoy leyendo la versión N 3290), el capítulo 21.4.7.1 habla sobre el método c_str ():

const charT* c_str() const noexcept; const charT* data() const noexcept;

Devuelve: Un puntero p tal que p + i == & operador para cada i en [0, size ()].
Complejidad: tiempo constante.
Requiere: El programa no alterará ninguno de los valores almacenados en la matriz de caracteres.

Entonces, sí: la complejidad del tiempo constante está garantizada por el estándar.

Acabo de comprobar c ++ 03 estándar, y no tiene tales requisitos, ni dice la complejidad.

BЈовић
fuente
8

En teoría, C ++ 03 no requiere eso y, por lo tanto, la cadena puede ser una matriz de caracteres donde se agrega la presencia del terminador nulo justo en el momento en que se llama c_str (). Esto puede requerir una reasignación (no viola la constancia, si el puntero privado interno se declara como mutable).

C ++ 11 es más estricto: requiere una gran cantidad de tiempo, por lo que no se puede reubicar y la matriz siempre debe ser lo suficientemente amplia como para almacenar el valor nulo al final. c_str (), por sí mismo, todavía puede hacer " ptr[size()]='\0'" para asegurar que el nulo esté realmente presente. No viola la constancia de la matriz ya que el rango [0..size())no cambia.

Emilio Garavaglia
fuente