c++ - null character c

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

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 :)

Creo que tiene razones históricas y encontré esto en Wikipedia :

En el momento en que se desarrolló C (y los idiomas de los que se derivó), la memoria era extremadamente limitada, por lo que usar un solo byte de sobrecarga para almacenar la longitud de una cadena era atractivo. La única alternativa popular en ese momento, generalmente llamada "cadena de Pascal" (aunque también se usa en versiones anteriores de BASIC), usaba un byte principal para almacenar la longitud de la cadena. Esto permite que la cadena contenga NUL y que, al buscar la longitud, solo necesite un acceso a la memoria (tiempo O (1) (constante)). Pero un byte limita la longitud a 255. Esta limitación de longitud era mucho más restrictiva que los problemas con la cadena C, por lo que la cadena C en general ganó.

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í.

La pregunta se plantea como una Length Prefixed Strings (LPS) frente a zero terminated strings (SZ) , pero en su mayoría exponen los beneficios de las cadenas con prefijo de longitud. Esto puede parecer abrumador, pero para ser honesto, también debemos considerar los inconvenientes del LPS y las ventajas de la SZ.

Como lo entiendo, la pregunta puede incluso entenderse como una forma sesgada de preguntar "¿cuáles son las ventajas de las cadenas terminadas en cero?".

Ventajas (veo) de cadenas terminadas en cero:

Muy simple, no es necesario introducir nuevos conceptos en el lenguaje, los arreglos de caracteres / los punteros de caracteres pueden hacerlo.
el lenguaje central solo incluye un mínimo de azúcar sintáctico para convertir algo entre comillas dobles en un montón de caracteres (en realidad, un montón de bytes). En algunos casos, se puede usar para inicializar cosas que no están relacionadas con el texto. Por ejemplo, el formato de archivo de imagen xpm es una fuente de C válida que contiene datos de imagen codificados como una cadena.
por cierto, puede poner un cero en un literal de cadena, el compilador también agregará otro al final del literal: "this/0is/0valid/0C" . ¿Es una cuerda? o cuatro cuerdas? O un montón de bytes ...
Implementación plana, sin direccionamiento oculto, sin enteros ocultos.
no se requiere asignación de memoria oculta (bueno, algunas funciones infames no estándar como strdup realizan la asignación, pero eso es principalmente una fuente de problemas).
no es un problema específico para hardware pequeño o grande (imagine la carga de administrar el prefijo de 32 bits en microcontroladores de 8 bits, o las restricciones de limitar el tamaño de la cadena a menos de 256 bytes, ese fue un problema que tuve con los eones de Turbo Pascal).
la implementación de la manipulación de cadenas es solo un puñado de funciones de biblioteca muy simples
eficiente para el uso principal de cadenas: texto constante leído secuencialmente desde un inicio conocido (principalmente mensajes al usuario).
el cero de terminación ni siquiera es obligatorio, todas las herramientas necesarias para manipular caracteres como un grupo de bytes están disponibles. Al realizar la inicialización de la matriz en C, incluso puede evitar el terminador NUL. Sólo establece el tamaño correcto. char a[3] = "foo"; es válido C (no C ++) y no pondrá un cero final en a.
coherente con el punto de vista de Unix "todo es archivo", incluidos los "archivos" que no tienen una longitud intrínseca como stdin, stdout. Debe recordar que las primitivas de lectura abierta y escritura se implementan en un nivel muy bajo. No son llamadas de biblioteca, sino llamadas de sistema. Y la misma API se usa para archivos binarios o de texto. Los primitivos de lectura de archivos obtienen una dirección de búfer y un tamaño y devuelven el nuevo tamaño. Y puedes usar cadenas como el búfer para escribir. El uso de otro tipo de representación de cadena implicaría que no puede usar fácilmente una cadena literal como el búfer para generar, o tendría que hacer que tenga un comportamiento muy extraño al convertirlo en char* . Es decir, no para devolver la dirección de la cadena, sino para devolver los datos reales.
muy fácil de manipular datos de texto leídos desde un archivo en el lugar, sin una copia inútil del búfer, simplemente inserte los ceros en los lugares correctos (bueno, no realmente con C moderna, ya que las cadenas entre comillas dobles están formadas por matrices constantes en la actualidad, generalmente se mantienen en datos no modificables segmento).
anteponer algunos valores int de cualquier tamaño implicaría problemas de alineación. La longitud inicial debe estar alineada, pero no hay razón para hacerlo para los datos de los personajes (y, de nuevo, forzar la alineación de las cadenas implicaría problemas al tratarlos como un grupo de bytes).
la longitud se conoce en tiempo de compilación para cadenas literales constantes (sizeof). Entonces, ¿por qué alguien querría almacenarlo en la memoria antes de los datos reales?
de una manera que C hace como (casi) todos los demás, las cadenas se ven como matrices de char. Como la longitud de la matriz no es administrada por C, es lógico que la longitud no se administre para las cadenas. Lo único sorprendente es que 0 elementos se agregaron al final, pero eso es solo en el nivel del lenguaje central cuando se escribe una cadena entre comillas dobles. Los usuarios pueden perfectamente llamar a las funciones de manipulación de cadenas que pasan la longitud, o incluso usar una copia simple en su lugar. SZ son sólo una instalación. En la mayoría de los otros idiomas, la longitud de la matriz está administrada, es lógico que sea la misma para las cadenas.
en los tiempos modernos, de todos modos, los conjuntos de caracteres de 1 byte no son suficientes y, a menudo, tiene que tratar con cadenas codificadas de Unicode, donde el número de caracteres es muy diferente del número de bytes. Implica que los usuarios probablemente querrán más que "solo el tamaño", pero también otras informaciones. Mantener la longitud no le da ningún uso (particularmente no es un lugar natural para almacenarlos) con respecto a estas otras informaciones útiles.

Dicho esto, no es necesario quejarse en el raro caso de que las cadenas C estándar sean realmente ineficientes. Libs están disponibles. Si seguí esa tendencia, debería quejarme de que el estándar C no incluye ninguna función de soporte de expresiones regulares ... pero realmente todos saben que no es un problema real, ya que hay bibliotecas disponibles para ese propósito. Entonces, cuando se desea la eficiencia de la manipulación de cadenas, ¿por qué no usar una biblioteca como bstring ? ¿O incluso cuerdas de C ++?

EDITAR : Recientemente he echado un vistazo a D cuerdas . Es lo suficientemente interesante como para ver que la solución elegida no es un prefijo de tamaño ni una terminación cero. Al igual que en C, las cadenas literales encerradas entre comillas dobles son solo una pequeña parte de las matrices de caracteres inmutables, y el lenguaje también tiene una palabra clave de cadena que significa eso (matriz de caracteres inmutables).

Pero las matrices D son mucho más ricas que las matrices C. En el caso de arrays estáticos, la longitud se conoce en tiempo de ejecución, por lo que no es necesario almacenar la longitud. El compilador lo tiene en tiempo de compilación. En el caso de matrices dinámicas, la longitud está disponible pero la documentación D no indica dónde se guarda. Por lo que sabemos, el compilador podría optar por mantenerlo en algún registro, o en alguna variable almacenada lejos de los datos de los caracteres.

En matrices de caracteres normales o cadenas no literales no hay un cero final, por lo tanto, el programador tiene que ponerlo por sí mismo si quiere llamar a alguna función C desde D. En el caso particular de cadenas literales, el compilador D todavía pone un cero en el final de cada cadena (para permitir que la conversión fácil a las cadenas C facilite la función de llamar a C), pero este cero no forma parte de la cadena (D no la cuenta en el tamaño de la cadena).

Lo único que me decepcionó un poco es que se supone que las cadenas son utf-8, pero la longitud aparentemente todavía devuelve un número de bytes (al menos es cierto en mi compilador gdc) incluso cuando se usan caracteres de múltiples bytes. No me queda claro si es un error de compilación o por propósito. (De acuerdo, es probable que haya descubierto lo que sucedió. Para decirle al compilador D que usa la fuente utf-8, tiene que poner una marca de orden de bytes estúpida al principio. Escribo estúpido porque no conozco al editor, especialmente para UTF- 8 que se supone que es compatible con ASCII).

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

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.
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.
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.)
¿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.
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.
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).
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.
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).
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.
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.

Calavera tiene right , pero como la gente no entiende su punto de vista, daré algunos ejemplos de código.

Primero, consideremos qué es C: un lenguaje simple, donde todo el código tiene una traducción bastante directa al lenguaje de máquina. Todos los tipos encajan en los registros y en la pila, y no requiere un sistema operativo o una gran biblioteca de tiempo de ejecución para ejecutarse, ya que estaban destinados a escribir estas cosas (una tarea para la que está muy bien adaptada, considerando que ni siquiera es un competidor probable a este día).

Si C tuviera un tipo de string , como int o char , sería un tipo que no cabía en un registro o en la pila, y requeriría que la asignación de memoria (con toda su infraestructura de soporte) se manejara de cualquier manera. Todo lo cual va en contra de los principios básicos de C.

Entonces, una cadena en C es:

char s*;

Entonces, asumamos que esto tenía prefijo de longitud. Vamos a escribir el código para concatenar dos cadenas:

char* concat(char* s1, char* s2) { /* What? What is the type of the length of the string? */ int l1 = *(int*) s1; /* How much? How much must I skip? */ char *s1s = s1 + sizeof(int); int l2 = *(int*) s2; char *s2s = s2 + sizeof(int); int l3 = l1 + l2; char *s3 = (char*) malloc(l3 + sizeof(int)); char *s3s = s3 + sizeof(int); memcpy(s3s, s1s, l1); memcpy(s3s + l1, s2s, l2); *(int*) s3 = l3; return s3; }

Otra alternativa sería usar una estructura para definir una cadena:

struct { int len; /* cannot be left implementation-defined */ char* buf; }

En este punto, toda la manipulación de cadenas requeriría que se realicen dos asignaciones, lo que, en la práctica, significa que usted pasaría por una biblioteca para realizar cualquier manejo de la misma.

Lo gracioso es que ... estructuras como las que existen en C! Simplemente no se utilizan para sus mensajes de visualización diarios al usuario.

Entonces, este es el punto que Calavera está haciendo: no hay tipo de cadena en C. Para hacer cualquier cosa con él, tendría que tomar un puntero y decodificarlo como un puntero a dos tipos diferentes, y luego se vuelve muy relevante el tamaño de una cadena, y no puede dejarse como "implementación definida".

Ahora, C puede manejar la memoria de todos modos, y las funciones mem en la biblioteca (en <string.h> , incluso!) Proporcionan todas las herramientas que necesita para manejar la memoria como un par de punteros y tamaño. Las llamadas "cadenas" en C se crearon con un solo propósito: mostrar mensajes en el contexto de escribir un sistema operativo destinado a terminales de texto. Y, para eso, la terminación nula es suficiente.

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.

gcc acepta los siguientes códigos:

char s [4] = "abcd";

y está bien si lo tratamos es como un conjunto de caracteres pero no una cadena. Es decir, podemos acceder a ella con s [0], s [1], s [2] y s [3], o incluso con memcpy (dest, s, 4). Pero obtendremos caracteres desordenados cuando intentemos con put (s), o peor aún con strcpy (dest, s).

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.

Muchas decisiones de diseño que rodean a C se derivan del hecho de que cuando se implementó originalmente, el paso de parámetros fue algo costoso. Dada una elección entre por ejemplo

void add_element_to_next(arr, offset) char[] arr; int offset; { arr[offset] += arr[offset+1]; } char array[40]; void test() { for (i=0; i<39; i++) add_element_to_next(array, i); }

versus

void add_element_to_next(ptr) char *p; { p[0]+=p[1]; } char array[40]; void test() { int i; for (i=0; i<39; i++) add_element_to_next(arr+i); }

este último habría sido un poco más barato (y por lo tanto preferido) ya que solo requería pasar un parámetro en lugar de dos. Si el método al que se llama no necesita saber la dirección base de la matriz ni el índice dentro de ella, pasar un solo puntero combinando los dos sería más barato que pasar los valores por separado.

Si bien hay muchas maneras razonables en que C podría haber codificado las longitudes de las cadenas, los enfoques que se habían inventado hasta ese momento tendrían todas las funciones requeridas que deberían poder trabajar con parte de una cadena para aceptar la dirección base de la cadena y El índice deseado como dos parámetros separados. El uso de la terminación de cero bytes permitió evitar ese requisito. Aunque otros métodos serían mejores con las máquinas actuales (los compiladores modernos a menudo pasan parámetros en los registros, y memcpy puede optimizarse de manera que strcpy () - los equivalentes no pueden) un código de producción suficiente utiliza cadenas terminadas en cero bytes que es difícil cambiar a cualquier otra cosa.

PD: a cambio de una ligera penalización de velocidad en algunas operaciones y un poco de sobrecarga adicional en cadenas más largas, habría sido posible tener métodos que funcionen con cadenas que acepten punteros directamente a cadenas, búferes de cadena con límites comprobados o Estructuras de datos identificando subcadenas de otra cadena. Una función como "strcat" hubiera parecido algo así como [sintaxis moderna]

void strcat(unsigned char *dest, unsigned char *src) { struct STRING_INFO d,s; str_size_t copy_length; get_string_info(&d, dest); get_string_info(&s, src); if (d.si_buff_size > d.si_length) // Destination is resizable buffer { copy_length = d.si_buff_size - d.si_length; if (s.src_length < copy_length) copy_length = s.src_length; memcpy(d.buff + d.si_length, s.buff, copy_length); d.si_length += copy_length; update_string_length(&d); } }

Un poco más grande que el método K&R strcat, pero admitiría la verificación de límites, lo cual no es el método K&R. Además, a diferencia del método actual, sería posible concatenar fácilmente una subcadena arbitraria, por ejemplo

/* Concatenate 10th through 24th characters from src to dest */ void catpart(unsigned char *dest, unsigned char *src) { struct SUBSTRING_INFO *inf; src = temp_substring(&inf, src, 10, 24); strcat(dest, src); }

Tenga en cuenta que el tiempo de vida de la cadena devuelta por temp_substring estaría limitado por los de sy src, el que sea más corto (por lo que el método debe infser pasado: si era local, moriría cuando se devolviera el método).

En términos de costo de memoria, las cadenas y los buffers de hasta 64 bytes tendrían un byte de sobrecarga (igual que las cadenas terminadas en cero); las cadenas más largas tendrían un poco más (si una cantidad permitida de sobrecarga entre dos bytes y el máximo requerido sería una compensación de tiempo / espacio). Se usaría un valor especial del byte de longitud / modo para indicar que a una función de cadena se le asignó una estructura que contiene un byte de bandera, un puntero y una longitud de búfer (que podría indexarse arbitrariamente en cualquier otra cadena).

Por supuesto, K&R no implementó tal cosa, pero eso es muy probable porque no quisieron gastar mucho esfuerzo en el manejo de cadenas, un área donde incluso hoy en día muchos idiomas parecen bastante anémicos.

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 :)