¿Por qué cadenas terminadas en nulo? O: terminada en nulo vs almacenamiento de caracteres + longitud

Question

Estoy escribiendo un intérprete de lenguaje de C, y mi tipo string contiene un atributo length, así:

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

Debido a esto, tengo que pasar Mucho tiempo en mi intérprete maneja este tipo de cadena de forma manual ya que C no incluye soporte integrado para ella. 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 verificación de límites está incorporada si usa "longitud" en lugar de buscando un nulo.

Tiene que recorrer toda la cadena para encontrar su longitud.

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

Las cadenas terminadas en nulo no funcionan bien con Unicode.

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

Segmento de cadena (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 verificación de errores de begin y end a ambas funciones). Estoy pensando acerca de por qué los utiliza C:

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 es sobre si debería utilizar cadenas terminadas en cero, es decir!

Entonces mi pregunta es: ¿hay algún beneficio para la terminación nula que me falta?

Answer 1

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á listo para pasar la cuerda a cualquier función.

Las cadenas con terminación nula a menudo agotan el rendimiento, por la sencilla razón 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 2

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

Answer 3

Una ventaja es que con la 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 comience con el N-ésimo carácter (siempre que no haya desbordamiento del búfer) en alguna función de manejo de cadenas, no hay problema, simplemente pase la dirección desaprobada allí. Al almacenar el tamaño de alguna otra forma, necesitaría construir una nueva cadena.

Answer 4

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

Tome un sistema de 32 bits.

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

Para almacenar una cadena nula plazo 7 byte
char * + 8 = 16 bytes.

matrices de plazo fijo no necesitan ser inmutables como lo hacen sus cadenas. Felizmente puedo truncar la cadena de caracteres simplemente colocando un carácter nulo. Si codifica, necesitaría crear una nueva cadena, que implica asignar memoria.

Dependiendo del uso de las cadenas, sus cadenas nunca serán capaces de igualar el rendimiento posible con cadenas en c en lugar de sus cadenas.

Answer 5

Las longitudes tienen sus problemas también.

• La longitud requiere almacenamiento extra (no es un problema ahora, pero sí un factor importante hace 30 años).

• Cada vez que modifica una cadena, debe actualizar la longitud, por lo que obtiene un rendimiento reducido en todos los ámbitos.

• Con una cadena terminada en NUL, puede utilizar una longitud o almacenar un puntero al último carácter, por lo que si está realizando muchas manipulaciones de cadena, 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. Entonces puede almacenarlos en una matriz de caracteres común en lugar de tener que usar una estructura.

Answer 6

Simplemente tirar algunos casos hipotéticos:

• no hay manera de conseguir una aplicación "equivocado" de terminación nula cadenas. 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 7

De Joel Back to Basics:

¿Por qué cadenas de C funciona de esta manera? Se debe a que 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 significaba "ASCII con Z (cero) al final".

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

Answer 8

Una de las ventajas de cadenas nul terminados es que si usted está caminando a través de una cadena de caracteres por carácter, sólo es necesario para mantener un único puntero para hacer frente a la cadena:

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

mientras que para cuerdas sin centinelas, que necesita para mantener dos bits de estado en torno a: o bien un puntero y el í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 al asignarlos), esto era importante. Ahora, no tanto.

Answer 9

Tiene toda la razón de que la terminación 0 es un método que es pobre con respecto a la verificación de tipo 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 cadenas. Creo que mantiene una longitud/longitud máxima antes de la cadena (longitud variable). De esta forma, las cadenas pueden ser terminadas en nulo por compatibilidad.

Mi preocupación con su mecanismo: - puntero adicional - inmutabilidad si en las partes centrales de su idioma; Normalmente, los tipos de cuerda no son inmutables, por lo que si lo reconsideras, será difícil. Tendría que implementar un mecanismo 'crear copia en el cambio' - uso de malloc (difícilmente eficiente, pero puede incluirse aquí simplemente 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, es para mí)

Answer 10

Ligeramente offtopic, pero hay una manera más eficiente de hacer cadenas con prefijo de longitud que la forma en que describes. Crear una estructura como esta (válido en C99 y más):

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

Esto crea una estructura que tiene la longitud en la salida, con el elemento de los 'personajes' se puede usar como un char * como lo haría con su actual estructura La diferencia, sin embargo, es que puede asignar solo un elemento en el montón para cada cadena, en lugar de dos. Asignar sus secuencias de esta manera:

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

EG - la longitud de la estructura (que es sólo el size_t), además de suficiente espacio para poner la cadena real después de ella.

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