string c++




¿Cuál es la razón para las cadenas terminadas en nulo? (12)

Por mucho que me encantan C y C ++, no puedo evitar rascarme la cabeza por la elección de cadenas terminadas en nulo:

  • Longitud prefijada (es decir, Pascal) cadenas existían antes de C
  • Las cadenas con prefijo de longitud hacen que varios algoritmos sean más rápidos al permitir la búsqueda de longitud de tiempo constante.
  • La longitud de las cadenas prefijadas hace que sea más difícil causar errores de saturación del búfer.
  • Incluso en una máquina de 32 bits, si permite que la cadena tenga el tamaño de la memoria disponible, una cadena con longitud de prefijo es solo tres bytes más ancha que una cadena terminada en nulo. En las máquinas de 16 bits, este es un byte único. En las máquinas de 64 bits, 4 GB es un límite de longitud de cadena razonable, pero incluso si desea expandirlo al tamaño de la palabra de la máquina, las máquinas de 64 bits generalmente tienen suficiente memoria, lo que hace que los siete bytes adicionales sean un argumento nulo. Sé que el estándar C original fue escrito para máquinas increíblemente pobres (en términos de memoria), pero el argumento de la eficiencia no me vende aquí.
  • Casi todos los otros lenguajes (es decir, Perl, Pascal, Python, Java, C #, etc.) usan cadenas con prefijo de longitud. Estos lenguajes generalmente superan a C en los puntos de referencia de manipulación de cadenas porque son más eficientes con las cadenas.
  • C ++ rectificó esto un poco con la plantilla std::basic_string , pero las matrices de caracteres simples que esperan cadenas terminadas en nulo siguen siendo generalizadas. Esto también es imperfecto porque requiere asignación de montón.
  • Las cadenas terminadas en nulo tienen que reservar un carácter (a saber, nulo), que no puede existir en la cadena, mientras que las cadenas con prefijo de longitud pueden contener nulos incrustados.

Varias de estas cosas han salido a la luz más recientemente que C, por lo que tendría sentido que C no supiera de ellas. Sin embargo, varios fueron claramente mucho antes de que surgiera C. ¿Por qué se habrían elegido cadenas terminadas en nulo en lugar del prefijo de longitud obviamente superior?

EDITAR : Dado que algunos solicitaron datos (y no me gustaron los que ya proporcioné) en mi punto de eficiencia anterior, se derivan de algunas cosas:

  • La concat que utiliza cadenas terminadas en nulo requiere complejidad de tiempo O (n + m). El prefijo de longitud a menudo requiere solo O (m).
  • La longitud que utiliza cadenas terminadas en nulo requiere O (n) complejidad de tiempo. El prefijo de longitud es O (1).
  • Longitud y concat son, con mucho, las operaciones de cadena más comunes. Hay varios casos en los que las cadenas terminadas en nulo pueden ser más eficientes, pero estas ocurren con menos frecuencia.

De las respuestas a continuación, estos son algunos casos donde las cadenas terminadas en nulo son más eficientes:

  • Cuando necesita cortar el inicio de una cadena y pasarla a algún método. Realmente no puede hacer esto en un tiempo constante con prefijo de longitud, incluso si se le permite destruir la cadena original, ya que el prefijo de longitud probablemente deba seguir las reglas de alineación.
  • En algunos casos en los que simplemente recorre la cadena de caracteres por caracteres, es posible que pueda guardar un registro de CPU. Tenga en cuenta que esto solo funciona en el caso de que no haya asignado dinámicamente la cadena (porque entonces tendría que liberarla, lo que requiere usar el registro de la CPU que guardó para mantener el puntero que originalmente obtuvo de malloc y sus amigos).

Ninguno de los anteriores es tan común como la longitud y la concat.

Hay una más afirmada en las respuestas a continuación:

  • Necesitas cortar el final de la cuerda.

pero este es incorrecto: es la misma cantidad de tiempo para las cadenas prefijadas terminadas en nulo y con longitud. (Las cadenas terminadas en nulo simplemente pegan un nulo donde desea que esté el nuevo extremo, los prefijos de longitud se restan del prefijo).


"Incluso en una máquina de 32 bits, si permite que la cadena tenga el tamaño de la memoria disponible, una cadena con longitud de prefijo es solo tres bytes más ancha que una cadena terminada en nulo".

Primero, los 3 bytes adicionales pueden ser una sobrecarga considerable para cadenas cortas. En particular, una cadena de longitud cero ahora toma 4 veces más memoria. Algunos de nosotros estamos utilizando máquinas de 64 bits, por lo que necesitamos 8 bytes para almacenar una cadena de longitud cero, o el formato de cadena no puede hacer frente a las cadenas más largas que admite la plataforma.

También puede haber problemas de alineación para tratar. Supongamos que tengo un bloque de memoria que contiene 7 cadenas, como "solo \ 0second \ 0 \ 0four \ 0five \ 0 \ 0seventh". La segunda cadena comienza en el desplazamiento 5. El hardware puede requerir que los enteros de 32 bits estén alineados en una dirección que sea un múltiplo de 4, por lo que debe agregar relleno, lo que aumenta aún más la sobrecarga. La representación de C es muy eficiente en memoria en comparación. (La eficiencia de la memoria es buena; ayuda al rendimiento del caché, por ejemplo).


C no tiene una cadena como parte del lenguaje. Una 'cadena' en C es solo un puntero a char. Así que tal vez estás haciendo la pregunta equivocada.

"Cuál es la razón para dejar de lado un tipo de cadena" podría ser más relevante. A eso le señalo que C no es un lenguaje orientado a objetos y solo tiene tipos de valores básicos. Una cadena es un concepto de nivel superior que debe implementarse combinando de alguna manera valores de otros tipos. C está en un nivel más bajo de abstracción.

a la luz de la agitación que sigue abajo:

Solo quiero señalar que no estoy tratando de decir que esta es una pregunta estúpida o mala, o que la forma C de representar cadenas es la mejor opción. Estoy tratando de aclarar que la pregunta sería más sucinta si se tiene en cuenta el hecho de que C no tiene ningún mecanismo para diferenciar una cadena como un tipo de datos de una matriz de bytes. ¿Es esta la mejor opción en vista del procesamiento y la capacidad de memoria de las computadoras de hoy? Probablemente no. Pero la retrospectiva es siempre 20/20 y todo eso :)


De la boca del caballo

Ninguno de BCPL, B o C admite datos de caracteres en gran medida en el idioma; Cada uno trata las cadenas como vectores de números enteros y complementa las reglas generales mediante unas pocas convenciones. Tanto en BCPL como en B, un literal de cadena denota la dirección de un área estática inicializada con los caracteres de la cadena, empaquetada en celdas. En BCPL, el primer byte empaquetado contiene el número de caracteres en la cadena; en B, no hay recuento y las cadenas se terminan con un carácter especial, que B deletrea *e . Este cambio se realizó parcialmente para evitar la limitación en la longitud de una cadena causada por mantener el conteo en una ranura de 8 o 9 bits, y en parte porque mantener el conteo parece, en nuestra experiencia, menos conveniente que usar un terminador.

Dennis M. Ritchie, Desarrollo del lenguaje C


La pereza, el registro de la frugalidad y la portabilidad considerando el instinto de ensamblaje de cualquier idioma, especialmente C, que está un paso por encima del ensamblaje (heredando así una gran cantidad de código heredado del ensamblado) Usted estaría de acuerdo, ya que un carácter nulo sería inútil en esos días ASCII, y probablemente tan bueno como un personaje de control EOF.

veamos en pseudo codigo

function readString(string) // 1 parameter: 1 register or 1 stact entries
    pointer=addressOf(string) 
    while(string[pointer]!=CONTROL_CHAR) do
        read(string[pointer])
        increment pointer

uso total de 1 registro

caso 2

 function readString(length,string) // 2 parameters: 2 register used or 2 stack entries
     pointer=addressOf(string) 
     while(length>0) do 
         read(string[pointer])
         increment pointer
         decrement length

total 2 registros utilizados

Eso podría parecer miope en ese momento, pero teniendo en cuenta la frugalidad en el código y el registro (que fueron PREMIUM en ese momento, el momento en que se sabe, usan una tarjeta perforada). Por lo tanto, al ser más rápido (cuando la velocidad del procesador podía contarse en kHz), este "Hack" era bastante bueno y portátil para un procesador sin registro con facilidad.

Por el bien del argumento implementaré 2 operaciones de cadena común

stringLength(string)
     pointer=addressOf(string)
     while(string[pointer]!=CONTROL_CHAR) do
         increment pointer
     return pointer-addressOf(string)

complejidad O (n) donde, en la mayoría de los casos, la cadena PASCAL es O (1) porque la longitud de la cadena está pendiente a la estructura de la cadena (eso también significaría que esta operación tendría que realizarse en una etapa anterior).

concatString(string1,string2)
     length1=stringLength(string1)
     length2=stringLength(string2)
     string3=allocate(string1+string2)
     pointer1=addressOf(string1)
     pointer3=addressOf(string3)
     while(string1[pointer1]!=CONTROL_CHAR) do
         string3[pointer3]=string1[pointer1]
         increment pointer3
         increment pointer1
     pointer2=addressOf(string2)
     while(string2[pointer2]!=CONTROL_CHAR) do
         string3[pointer3]=string2[pointer2]
         increment pointer3
         increment pointer1
     return string3

la complejidad O (n) y anteponer la longitud de la cadena no cambiaría la complejidad de la operación, aunque admito que tomaría 3 veces menos tiempo.

Por otro lado, si usa la cadena PASCAL tendría que rediseñar su API para tener en cuenta la longitud del registro y el endianness de bits, la cadena PASCAL obtuvo la bien conocida limitación de 255 caracteres (0xFF) porque la longitud se almacenó en 1 byte (8 bits) ), y si deseara una cadena más larga (16 bits -> cualquier cosa) tendría que tener en cuenta la arquitectura en una capa de su código, lo que significaría que en la mayoría de las API de cadenas incompatibles si quisiera una cadena más larga.

Ejemplo:

Un archivo fue escrito con su api de cadena prependida en una computadora de 8 bits y luego tendría que leerse en una computadora de 32 bits. ¿Qué haría el programa perezoso si sus 4 bytes son la longitud de la cadena y luego asignan esa cantidad de memoria? entonces intenta leer tantos bytes. Otro caso sería la lectura de la cadena PPC de 32 bytes (little endian) en un x86 (big endian), por supuesto, si no sabe que uno está escrito por el otro, habrá problemas. La longitud de 1 byte (0x00000001) se convertiría en 16777216 (0x0100000) que es de 16 MB para leer una cadena de 1 byte. Por supuesto, usted diría que la gente debería estar de acuerdo con un estándar, pero incluso unicode de 16 bits tiene poca y gran capacidad.

Por supuesto, C también tendría sus problemas, pero se vería muy poco afectado por los problemas planteados aquí.


Obviamente, para el rendimiento y la seguridad, querrás mantener la longitud de una cuerda mientras trabajas con ella en lugar de ejecutar strlen repetidamente o su equivalente. Sin embargo, almacenar la longitud en una ubicación fija justo antes del contenido de la cadena es un diseño increíblemente malo. Como señaló Jörgen en los comentarios sobre la respuesta de Sanjit, esto impide tratar la cola de una cadena como una cadena, lo que, por ejemplo, hace que muchas operaciones comunes como path_to_filename o filename_to_extension imposibles sin asignar nueva memoria (e incurrir en la posibilidad de fallas y errores) manejo). Y, por supuesto, está el problema de que nadie puede acordar cuántos bytes debe ocupar el campo de longitud de la cadena (muchos lenguajes incorrectos de "cadena de Pascal" utilizaron campos de 16 bits o incluso campos de 24 bits que impiden el procesamiento de cadenas largas).

El diseño de C de permitir que el programador elija si / dónde / cómo almacenar la longitud es mucho más flexible y poderoso. Pero claro, el programador tiene que ser inteligente. C castiga la estupidez con programas que se bloquean, frenan o detienen a sus enemigos.


No es una razón necesariamente, sino un contrapunto a la longitud codificada

  1. Ciertas formas de codificación de longitud dinámica son superiores a la codificación de longitud estática en lo que se refiere a la memoria, todo depende del uso. Basta con mirar a UTF-8 para la prueba. Es esencialmente una matriz de caracteres extensible para codificar un solo carácter. Esto utiliza un solo bit para cada byte extendido. La terminación NUL utiliza 8 bits. Longitud-prefijo Creo que se puede denominar razonablemente longitud infinita también usando 64 bits. Con qué frecuencia golpeas el caso de tus bits adicionales es el factor decisivo. ¿Solo 1 cuerda extremadamente grande? ¿A quién le importa si estás usando 8 o 64 bits? Muchas cadenas pequeñas (es decir, cadenas de palabras en inglés)? Entonces sus costos de prefijo son un gran porcentaje.

  2. Las cadenas con prefijo de longitud que permiten ahorrar tiempo no son cosas reales . Si se requiere que los datos suministrados tengan una longitud proporcionada, se cuenta en el momento de la compilación o si realmente se le proporcionan datos dinámicos que debe codificar como una cadena. Estos tamaños se calculan en algún punto del algoritmo. Una variable independiente para almacenar el tamaño de una cadena terminada en nulo puede ser proporcionada. Lo que hace que la comparación de ahorro de tiempo sea discutible. Uno solo tiene un NUL adicional al final ... pero si la codificación de longitud no incluye ese NUL, entonces literalmente no hay diferencia entre los dos. No hay ningún cambio algorítmico requerido en absoluto. Solo un pase previo que debe diseñarse manualmente en lugar de que un compilador / tiempo de ejecución lo haga por usted. C se trata principalmente de hacer las cosas manualmente.

  3. Longitud-prefijo siendo opcional es un punto de venta. No siempre necesito esa información adicional para un algoritmo, por lo que ser obligado a hacerlo para cada cadena hace que mi tiempo de cálculo + de precomputa nunca pueda caer por debajo de O (n). (Es decir, generador de números aleatorios de hardware 1-128. Puedo extraer de una "cadena infinita". Digamos que solo genera caracteres tan rápido. Por lo tanto, la longitud de nuestra cadena cambia todo el tiempo. Pero a mi uso de los datos probablemente no le importe cómo muchos bytes aleatorios que tengo. Solo quiere el siguiente byte no utilizado disponible tan pronto como pueda obtenerlo después de una solicitud. Podría estar esperando en el dispositivo. Pero también podría tener un buffer de caracteres previamente leído. Una comparación de longitud es un innecesario desperdicio de cálculo. Una comprobación nula es más eficiente.)

  4. ¿El prefijo de longitud es una buena protección contra el desbordamiento del búfer? También lo es el uso sensato de las funciones y la implementación de la biblioteca. ¿Qué pasa si paso en datos malformados? Mi búfer tiene 2 bytes de longitud, ¡pero le digo a la función que es 7! Por ejemplo: si se pretendía que get () se usara en datos conocidos, podría haber tenido una verificación interna del búfer que probó los búferes compilados y malloc ()Llama y aun sigue las especificaciones. Si estaba destinado a ser utilizado como una tubería para que STDIN desconocido llegue a un búfer desconocido, entonces claramente no se puede saber sobre el tamaño del búfer, lo que significa que una longitud arg no tiene sentido, necesita algo más como un cheque de canario. En este caso, no puede prefijar la longitud de algunos flujos y entradas, simplemente no puede. Lo que significa que la verificación de longitud debe estar integrada en el algoritmo y no una parte mágica del sistema de escritura. TL; la terminación de DR NUL nunca tuvo que ser insegura, simplemente terminó de esa manera por mal uso.

  5. contador de contrapunto: la terminación NUL es molesta en binario. O bien es necesario hacer un prefijo de longitud aquí o transformar los bytes NUL de alguna manera: códigos de escape, reasignación de rango, etc., lo que por supuesto significa más uso de memoria / información reducida / más operaciones por byte. Longitud-prefijo en su mayoría gana la guerra aquí. La única ventaja de una transformación es que no es necesario escribir funciones adicionales para cubrir las cadenas de prefijo de longitud. Lo que significa que en sus rutinas sub-O (n) más optimizadas puede hacer que actúen automáticamente como sus equivalentes O (n) sin agregar más código. El inconveniente es, por supuesto, el tiempo, la memoria y la pérdida de compresión cuando se usa en cuerdas pesadas NUL.Dependiendo de cuánto de su biblioteca termine duplicando para operar con datos binarios, puede tener sentido trabajar únicamente con cadenas de prefijo de longitud. Dicho esto, también se podría hacer lo mismo con las cadenas de prefijo de longitud ... longitud -1 podría significar terminado en NUL y se podrían usar cadenas terminadas en NUL dentro de terminados en longitud.

  6. Concat: "O (n + m) vs O (m)" Supongo que se refiere a m como la longitud total de la cadena después de la concatenación porque ambas tienen que tener ese número mínimo de operaciones (no puede simplemente -en la cadena 1, ¿qué pasa si tienes que realloc?). Y supongo que n es una cantidad mítica de operaciones que ya no tiene que hacer debido a un cálculo previo. Si es así, entonces la respuesta es simple: precomputación. Siinsiste en que siempre tendrá suficiente memoria para no necesitar reasignación y esa es la base de la notación de gran O, entonces la respuesta es aún más simple: haga una búsqueda binaria en la memoria asignada para el final de la cadena 1, claramente hay una gran Muestra de ceros infinitos después de la cadena 1 para que no nos preocupemos por realloc. Allí, fácilmente conseguí n log (n) y apenas lo intenté. Lo que si recuerda el registro (n) es esencialmente solo 64 en una computadora real, que es esencialmente como decir O (64 + m), que es esencialmente O (m). (Y sí, esa lógica se ha utilizado en el análisis en tiempo real de las estructuras de datos reales en uso hoy en día. No es una tontería en mi cabeza).

  7. Concat () / Len () otra vez : Memoize resultados. Fácil.Convierte todos los cálculos en precálculos si es posible / necesario. Esta es una decisión algorítmica. No es una restricción forzada del lenguaje.

  8. El paso de sufijo de cadena es más fácil / posible con la terminación NUL. Dependiendo de cómo se implemente el prefijo de longitud, puede ser destructivo en la cadena original y, a veces, ni siquiera puede ser posible. Requerir una copia y pasar O (n) en lugar de O (1).

  9. El paso de argumentos / la desreferenciación es menor para el prefijo terminado en NUL versus longitud. Obviamente porque estás pasando menos información. Si no necesita longitud, esto ahorra mucho espacio y permite optimizaciones.

  10. Puedes hacer trampa. Es realmente sólo un puntero. ¿Quién dice que tienes que leerlo como una cadena? ¿Qué pasa si quieres leerlo como un solo carácter o un flotador? ¿Qué pasa si quieres hacer lo contrario y leer un float como una cadena? Si tiene cuidado, puede hacer esto con la terminación NUL. No puede hacer esto con el prefijo de longitud, es un tipo de datos claramente diferente de un puntero normalmente. Lo más probable es que tenga que construir una cadena byte a byte y obtener la longitud. Por supuesto, si quisiera algo como un flotador completo (probablemente tenga un NUL en su interior) tendría que leer byte por byte de todos modos, pero los detalles quedan por decidir.

TL; DR ¿Estás utilizando datos binarios? Si no, la terminación NUL permite más libertad algorítmica. Si es así, entonces la cantidad de código frente a la velocidad / memoria / compresión es su principal preocupación. Una combinación de los dos enfoques o memoización podría ser la mejor.


De alguna manera entendí que la pregunta implica que no hay compatibilidad de compilador para cadenas con prefijo de longitud en C. El siguiente ejemplo muestra, al menos, puedes iniciar tu propia biblioteca de cadenas en C, donde las longitudes de las cadenas se cuentan en tiempo de compilación, con una construcción como esta:

#define PREFIX_STR(s) ((prefix_str_t){ sizeof(s)-1, (s) })

typedef struct { int n; char * p; } prefix_str_t;

int main() {
    prefix_str_t string1, string2;

    string1 = PREFIX_STR("Hello!");
    string2 = PREFIX_STR("Allows \0 chars (even if printf directly doesn't)");

    printf("%d %s\n", string1.n, string1.p); /* prints: "6 Hello!" */
    printf("%d %s\n", string2.n, string2.p); /* prints: "48 Allows " */

    return 0;
}

Sin embargo, esto no tendrá ningún problema, ya que debe tener cuidado cuando libere específicamente el puntero de cadena y cuando se asigna de forma estática ( charmatriz literal ).

Edición: como una respuesta más directa a la pregunta, mi opinión es que esta es la forma en que C podría admitir que ambos tengan una longitud de cadena disponible (como una constante de tiempo de compilación), en caso de que la necesite, pero aún sin memoria de sobrecarga si desea usar Sólo punteros y terminación en cero.

Por supuesto, parece que trabajar con cadenas terminadas en cero era la práctica recomendada, ya que la biblioteca estándar en general no toma longitudes de cadena como argumentos, y dado que extraer la longitud no es un código tan sencillo como char * s = "abc", como muestra mi ejemplo.


La terminación nula permite operaciones rápidas basadas en punteros.


Aún no se ha mencionado un punto: cuando se diseñó C, había muchas máquinas donde un 'char' no era de ocho bits (incluso hoy en día hay plataformas DSP donde no lo está). Si uno decide que las cadenas deben tener un prefijo de longitud, ¿cuántos prefijos de longitud de caracteres deben usarse? El uso de dos impondría un límite artificial en la longitud de la cadena para máquinas con caracteres de 8 bits y espacio de direccionamiento de 32 bits, mientras que desperdicia espacio en máquinas con caracteres de 16 bits y espacio de direcciones de 16 bits.

Si uno quisiera permitir que las cadenas de longitud arbitraria se almacenaran eficientemente, y si 'char' siempre fuera de 8 bits, uno podría, por algún gasto en velocidad y tamaño de código, definir un esquema como una cadena con el prefijo de un número par N tendría una longitud de N / 2 bytes, una cadena prefijada por un valor impar N y un valor par M (lectura hacia atrás) podría ser ((N-1) + M * char_max) / 2, etc. y requerir que cualquier búfer Los reclamos para ofrecer una cierta cantidad de espacio para mantener una cadena deben permitir que haya suficientes bytes que preceden ese espacio para manejar la longitud máxima. Sin embargo, el hecho de que 'char' no sea siempre de 8 bits, complicaría tal esquema, ya que el número de 'char' requerido para mantener la longitud de una cadena variaría dependiendo de la arquitectura de la CPU.


En muchos sentidos, C era primitivo. Y me encantó.

Fue un paso por encima del lenguaje ensamblador, brindándole casi el mismo rendimiento con un lenguaje que era mucho más fácil de escribir y mantener.

El terminador nulo es simple y no requiere soporte especial por parte del idioma.

Mirando hacia atrás, no parece tan conveniente. Pero usé el lenguaje ensamblador en los años 80 y me pareció muy conveniente en ese momento. Simplemente creo que el software está evolucionando continuamente, y las plataformas y herramientas se vuelven cada vez más sofisticadas.


Según Joel Spolsky en este blog ,

Es porque el microprocesador PDP-7, en el que se inventaron UNIX y el lenguaje de programación C, tenía un tipo de cadena ASCIZ. ASCIZ significa "ASCII con una Z (cero) al final".

Después de ver todas las otras respuestas aquí, estoy convencido de que incluso si esto es cierto, es solo una parte de la razón por la que C tiene "cadenas" terminadas en nulo. Ese post es bastante esclarecedor de cómo las cosas simples como las cuerdas pueden ser bastante difíciles.


Suponiendo por un momento que C implementó cadenas a la manera de Pascal, prefijándolas por longitud: ¿es una cadena de 7 caracteres el mismo TIPO DE DATO que una cadena de 3 caracteres? Si la respuesta es sí, ¿qué tipo de código debe generar el compilador cuando asigno el primero a este último? ¿Debería truncarse la cadena o cambiar su tamaño automáticamente? Si se cambia el tamaño, ¿debería esa operación estar protegida por una cerradura para hacer que la hebra sea segura? El lado de aproximación C abordó todas estas cuestiones, nos guste o no :)





null-terminated