voto - ¿Por qué cadenas terminadas en nulo? O: almacenamiento terminado en nulo vs. caracteres+longitud

voto en blanco donde va

Question

Estoy escribiendo un intérprete de idiomas en C, y mi tipo de string contiene un atributo de length , como:

struct String
{
    char* characters;
    size_t length;
};

Debido a esto, tengo que pasar mucho tiempo en mi intérprete manejando este tipo de cadena manualmente ya que C no incluye soporte incorporado para él. He considerado cambiar a cadenas simples terminadas en nulo solo para cumplir con la C subyacente, pero parece que hay muchas razones para no:

La comprobación de límites está integrada si utiliza "longitud" en lugar de buscar un valor nulo.

Tienes que atravesar toda la cadena para encontrar su longitud.

Tienes que hacer cosas adicionales para manejar un carácter nulo en medio de una cadena terminada en nulo.

Las cadenas terminadas en nulo tratan mal con Unicode.

Las cadenas no terminadas en nulo pueden internarse más, es decir, los caracteres para "Hola, mundo" y "Hola" se pueden almacenar en el mismo lugar, solo que con diferentes longitudes. Esto no se puede hacer con cadenas terminadas en nulo.

String slice (nota: las cadenas son inmutables en mi idioma). Obviamente, el segundo es más lento (y más propenso a errores: piense en agregar la comprobación de errores de begin y end a ambas funciones).

struct String slice(struct String in, size_t begin, size_t end)
{
    struct String out;
    out.characters = in.characters + begin;
    out.length = end - begin;

    return out;
}

char* slice(char* in, size_t begin, size_t end)
{
    char* out = malloc(end - begin + 1);

    for(int i = 0; i < end - begin; i++)
        out[i] = in[i + begin];

    out[end - begin] = ''/0'';

    return out;
}

Después de todo esto, mi pensamiento ya no se trata de si debo usar cadenas terminadas en nulo: ¡Estoy pensando en por qué C las usa!

Así que mi pregunta es: ¿hay algún beneficio para la terminación nula que me estoy perdiendo?

Answer 1

Aunque prefiero el método array + len en la mayoría de los casos, hay razones válidas para usar terminados en nulo.

Tome un sistema de 32 bits.

Para almacenar una cadena de 7 bytes
char * + size_t + 8 bytes = 19 bytes

Para almacenar una cadena de término nulo de 7 bytes
char * + 8 = 16 bytes.

Las matrices de término nulo no tienen que ser inmutables como lo hacen sus cadenas. Felizmente puedo truncar el c-string simplemente colocando un carácter nulo. Si codifica, deberá crear una nueva cadena, que implica la asignación de memoria.

Dependiendo del uso de las cadenas, sus cadenas nunca podrán igualar el rendimiento posible con las cadenas en C en lugar de las cadenas.

Answer 2

Creo que la razón principal es que el estándar no dice nada concreto sobre el tamaño de ningún tipo que no sea char. Pero sizeof (char) = 1 y eso definitivamente no es suficiente para el tamaño de la cadena.

Answer 3

De la vuelta a lo básico de Joel:

¿Por qué las cadenas en C funcionan de esta manera? 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".

¿Es esta la única manera de almacenar cadenas? No, de hecho, es una de las peores formas de almacenar cadenas. Para programas no triviales, API, sistemas operativos, bibliotecas de clases, debe evitar cadenas ASCIZ como la plaga.

Answer 4

La solución habitual es hacer ambas cosas: mantener la longitud y mantener el terminador nulo. No es mucho trabajo extra y significa que siempre estás listo para pasar la cadena a cualquier función.

Las cadenas terminadas en nulo son a menudo una pérdida de rendimiento, por la razón obvia de que el tiempo necesario para descubrir la longitud depende de la longitud. En el lado positivo, son la forma estándar de representar cadenas en C, por lo que no tiene más remedio que apoyarlas si desea usar la mayoría de las bibliotecas de C.

Answer 5

Las longitudes también tienen sus problemas.

• La longitud requiere almacenamiento adicional (no es un problema de este tipo ahora, sino un factor importante hace 30 años).

• Cada vez que modifica una cadena, tiene que actualizar la longitud, para obtener un rendimiento reducido en todos los ámbitos.

• Con una cadena terminada en NUL, todavía puede usar una longitud o almacenar un puntero al último carácter, por lo que si está haciendo muchas manipulaciones de cadena, aún puede igualar el rendimiento de cadena con longitud.

• Las cadenas terminadas en NUL son mucho más simples: el terminador NUL es solo una convención utilizada por métodos como strcat para determinar el final de la cadena. Por lo tanto, puede almacenarlos en una matriz de caracteres normal en lugar de tener que usar una estructura.

Answer 6

Ligeramente fuera de lugar, pero hay una forma más eficiente de hacer cadenas con prefijo de longitud que la que describe. Crea una estructura como esta (válida en C99 y superior):

struct String 
{
  size_t length;
  char characters[0];
}

Esto crea una estructura que tiene la longitud al comienzo, con el elemento ''caracteres'' que se puede usar como char * tal como lo haría con su estructura actual. Sin embargo, la diferencia es que puede asignar un solo elemento en el montón para cada cadena, en lugar de dos. Asigna tus cuerdas de esta manera:

mystr = malloc(sizeof(String) + strlen(cstring))

Por ejemplo, la longitud de la estructura (que es solo el tamaño_t) más el espacio suficiente para poner la cadena real detrás de ella.

Si no desea usar C99, también puede hacer esto con "caracteres char [1]" y restar 1 de la longitud de la cadena para asignar.

Answer 7

Simplemente arrojando algunas hipótesis:

• no hay forma de obtener una implementación "incorrecta" de cadenas terminadas en nulo. Sin embargo, una estructura estandarizada podría tener implementaciones específicas del proveedor.
• no se requieren estructuras Las cadenas terminadas en nulo están "incorporadas", por así decirlo, en virtud de ser un caso especial de un char *.

Answer 8

Un beneficio es que, con terminación nula, cualquier cola de una cadena terminada en nulo también es una cadena terminada en nulo. Si necesita pasar una subcadena que comienza con el carácter Nth (siempre que no haya un desbordamiento del búfer) en alguna función de manejo de cadenas, no hay problema, simplemente pase la dirección de salida allí. Cuando almacene el tamaño de alguna otra manera, necesitará construir una nueva cadena.

Answer 9

Una de las ventajas de las cadenas terminadas en nulo es que si está recorriendo una cadena carácter por carácter, solo necesita mantener un solo puntero para dirigir la cadena:

while (*s)
{
    *s = toupper(*s);
    s++;
}

mientras que para cadenas sin centinelas, debe mantener dos bits de estado alrededor: un puntero y un índice:

while (i < s.length)
{
    s.data[i] = toupper(s.data[i]);
    i++;
}

... o un puntero actual y un límite:

s_end = s + length;
while (s < s_end)
{
    *s = toupper(*s);
    s++;
}

Cuando los registros de CPU eran un recurso escaso (y los compiladores eran peores en su asignación), esto era importante. Ahora, no tanto.

Answer 10

Usted tiene toda la razón de que la terminación 0 es un método deficiente con respecto a la verificación de tipos y el rendimiento de parte de las operaciones. Las respuestas en esta página ya resumen los orígenes y usos de la misma.

Me gustó la forma en que Delphi almacenaba las cuerdas. Creo que mantiene una longitud / longitud máxima antes de la cadena (longitud variable). De esta manera, las cadenas pueden terminarse en nulo por compatibilidad.

Mis preocupaciones con respecto a su mecanismo: - puntero adicional - inmutabilidad en las partes centrales de su idioma; Normalmente, los tipos de cuerdas no son inmutables, así que si alguna vez reconsidera esto será difícil. Necesitaría implementar un mecanismo de ''crear copia en cambio'' - uso de malloc (difícilmente eficiente, pero ¿se puede incluir aquí solo por facilidad?)

Buena suerte; escribir su propio intérprete puede ser muy educativo para comprender principalmente la gramática y la sintaxis de los lenguajes de programación. (al menos, fue para mi)