Quelle est la justification des chaînes terminées par null?

Autant que j'aime C et C ++, je ne peux pas m'empêcher de me gratter la tête au choix de chaînes terminées par null:

• Des chaînes de longueur préfixées (c'est-à-dire Pascal) existaient avant C
• Les chaînes préfixées par la longueur accélèrent plusieurs algorithmes en permettant une recherche de durée constante.
• Les chaînes préfixées par la longueur rendent plus difficile de provoquer des erreurs de dépassement de tampon.
• Même sur une machine 32 bits, si vous autorisez la chaîne à avoir la taille de la mémoire disponible, une chaîne préfixée de longueur n'est que de trois octets plus large qu'une chaîne terminée par null. Sur les machines 16 bits, il s'agit d'un seul octet. Sur les machines 64 bits, 4 Go est une limite de longueur de chaîne raisonnable, mais même si vous souhaitez l'étendre à la taille du mot machine, les machines 64 bits ont généralement suffisamment de mémoire, ce qui fait des sept octets supplémentaires une sorte d'argument nul. Je sais que la norme C d'origine a été écrite pour des machines incroyablement pauvres (en termes de mémoire), mais l'argument de l'efficacité ne me vend pas ici.
• Presque tous les autres langages (par exemple Perl, Pascal, Python, Java, C #, etc.) utilisent des chaînes de longueur préfixées. Ces langages battent généralement C dans les benchmarks de manipulation de chaînes car ils sont plus efficaces avec les chaînes.
• C ++ a rectifié cela un peu avec le std::basic_stringmodèle, mais les tableaux de caractères simples qui attendent des chaînes terminées par null sont toujours omniprésents. Ceci est également imparfait car il nécessite une allocation de tas.
• Les chaînes terminées par Null doivent réserver un caractère (à savoir, null), qui ne peut pas exister dans la chaîne, tandis que les chaînes préfixées par la longueur peuvent contenir des null incorporés.

Plusieurs de ces choses sont apparues plus récemment que C, il serait donc logique que C ne les connaisse pas. Cependant, plusieurs étaient simples bien avant la naissance de C. Pourquoi des chaînes terminées nulles auraient-elles été choisies au lieu du préfixe de longueur évidemment supérieure?

EDIT : Puisque certains ont demandé des faits (et n'ont pas aimé ceux que j'ai déjà fournis) sur mon point d'efficacité ci-dessus, ils découlent de quelques choses:

• Concat utilisant des chaînes terminées nulles nécessite une complexité temporelle O (n + m). Le préfixe de longueur ne nécessite souvent que O (m).
• La longueur utilisant des chaînes terminées par null nécessite une complexité temporelle O (n). Le préfixe de longueur est O (1).
• La longueur et la concaténation sont de loin les opérations de chaîne les plus courantes. Il existe plusieurs cas où les chaînes terminées par null peuvent être plus efficaces, mais elles se produisent beaucoup moins souvent.

D'après les réponses ci-dessous, voici quelques cas où les chaînes terminées par null sont plus efficaces:

• Lorsque vous devez couper le début d'une chaîne et le transmettre à une méthode. Vous ne pouvez pas vraiment le faire en temps constant avec le préfixe de longueur même si vous êtes autorisé à détruire la chaîne d'origine, car le préfixe de longueur doit probablement suivre les règles d'alignement.
• Dans certains cas, lorsque vous parcourez simplement la chaîne caractère par caractère, vous pourrez peut-être enregistrer un registre CPU. Notez que cela ne fonctionne que dans le cas où vous n'avez pas alloué dynamiquement la chaîne (car alors vous devriez la libérer, ce qui nécessite d'utiliser ce registre CPU que vous avez enregistré pour contenir le pointeur que vous avez initialement reçu de malloc et de ses amis).

Rien de ce qui précède n'est presque aussi commun que la longueur et le concat.

Il y en a un de plus affirmé dans les réponses ci-dessous:

• Vous devez couper la fin de la chaîne

mais celui-ci est incorrect - c'est le même laps de temps pour les chaînes terminées par null et préfixées par la longueur. (Les chaînes terminées par des valeurs nulles collent simplement une valeur nulle où vous voulez que la nouvelle fin soit, les préfixes de longueur soustraient simplement le préfixe.)

De la bouche du cheval

Aucun de BCPL, B ou C ne prend fortement en charge les données de caractères dans la langue; chacun traite les chaînes comme des vecteurs d'entiers et complète les règles générales par quelques conventions. Dans BCPL et B, un littéral de chaîne indique l'adresse d'une zone statique initialisée avec les caractères de la chaîne, compressée dans des cellules. Dans BCPL, le premier octet compressé contient le nombre de caractères de la chaîne; en B, il n'y a pas de comptage et les chaînes se terminent par un caractère spécial, que B a orthographié *e. Cette modification a été apportée en partie pour éviter la limitation de la longueur d'une chaîne causée par le maintien du comptage dans un intervalle de 8 ou 9 bits, et en partie parce que le maintien du comptage semblait, selon notre expérience, moins pratique que l'utilisation d'un terminateur.

_{Dennis M Ritchie, Développement du langage C}

C n'a pas de chaîne dans le langage. Une «chaîne» en C n'est qu'un pointeur sur char. Alors peut-être que vous posez la mauvaise question.

"Quelle est la justification de l'omission d'un type de chaîne" pourrait être plus pertinent. Pour cela, je voudrais souligner que C n'est pas un langage orienté objet et n'a que des types de valeurs de base. Une chaîne est un concept de niveau supérieur qui doit être implémenté en combinant d'une certaine manière les valeurs d'autres types. C est à un niveau d'abstraction inférieur.

à la lumière de la bourrasque qui fait rage ci-dessous:

Je veux juste souligner que je n'essaie pas de dire que c'est une question stupide ou mauvaise, ou que la façon C de représenter les cordes est le meilleur choix. J'essaie de clarifier que la question serait posée plus succinctement si vous prenez en compte le fait que C n'a pas de mécanisme pour différencier une chaîne en tant que type de données d'un tableau d'octets. Est-ce le meilleur choix compte tenu de la puissance de traitement et de mémoire des ordinateurs actuels? Probablement pas. Mais le recul est toujours de 20/20 et tout ça :)

La question est posée comme une chose Length Prefixed Strings (LPS)vs zero terminated strings (SZ), mais expose principalement les avantages des chaînes de longueur préfixées. Cela peut sembler écrasant, mais pour être honnête, nous devons également considérer les inconvénients du LPS et les avantages de la SZ.

Si je comprends bien, la question peut même être comprise comme une manière biaisée de demander "quels sont les avantages des cordes à terminaison zéro?".

Avantages (je vois) des cordes à terminaison zéro:

• très simple, pas besoin d'introduire de nouveaux concepts dans le langage, les tableaux char / pointeurs char peuvent le faire.
• le langage de base comprend juste un minimum de sucre syntaxique pour convertir quelque chose entre des guillemets doubles en un tas de caractères (vraiment un tas d'octets). Dans certains cas, il peut être utilisé pour initialiser des choses sans aucun rapport avec le texte. Par exemple, le format de fichier d'image xpm est une source C valide qui contient des données d'image codées sous forme de chaîne.
• en passant, vous pouvez mettre un zéro dans un littéral de chaîne, le compilateur juste ajouter un autre à la fin du littéral: "this\0is\0valid\0C". Est-ce une chaîne? ou quatre cordes? Ou un tas d'octets ...
• implémentation plate, pas d'indirection cachée, pas d'entier caché.
• aucune allocation de mémoire cachée n'est impliquée (enfin, certaines fonctions infâmes non standard comme strdup effectuent l'allocation, mais c'est surtout une source de problème).
• pas de problème spécifique pour le matériel petit ou grand (imaginez la charge de gérer la longueur de préfixe 32 bits sur les microcontrôleurs 8 bits, ou les restrictions de limiter la taille des chaînes à moins de 256 octets, c'était un problème que j'avais en fait avec Turbo Pascal il y a des éons).
• la mise en œuvre de la manipulation de chaînes n'est qu'une poignée de fonctions de bibliothèque très simples
• efficace pour l'utilisation principale des chaînes: texte constant lu séquentiellement à partir d'un début connu (principalement des messages à l'utilisateur).
• le zéro final n'est même pas obligatoire, tous les outils nécessaires pour manipuler les caractères comme un tas d'octets sont disponibles. Lors de l'initialisation du tableau en C, vous pouvez même éviter le terminateur NUL. Réglez simplement la bonne taille. char a[3] = "foo";est un C valide (pas C ++) et ne mettra pas de zéro final dans a.
• cohérent avec le point de vue unix "tout est fichier", y compris les "fichiers" qui n'ont pas de longueur intrinsèque comme stdin, stdout. N'oubliez pas que les primitives de lecture et d'écriture ouvertes sont implémentées à un niveau très bas. Ce ne sont pas des appels de bibliothèque, mais des appels système. Et la même API est utilisée pour les fichiers binaires ou texte. Les primitives de lecture de fichiers obtiennent une adresse de tampon et une taille et renvoient la nouvelle taille. Et vous pouvez utiliser des chaînes comme tampon pour écrire. L'utilisation d'un autre type de représentation sous forme de chaîne impliquerait que vous ne pouvez pas facilement utiliser une chaîne littérale comme tampon pour la sortie, ou vous devriez lui donner un comportement très étrange lors de sa conversion char*. À savoir non pas pour renvoyer l'adresse de la chaîne, mais pour renvoyer les données réelles.
• très facile à manipuler les données de texte lues à partir d'un fichier sur place, sans copie inutile du tampon, insérez simplement des zéros aux bons endroits (enfin, pas vraiment avec du C moderne car les chaînes entre guillemets doubles sont des tableaux de caractères const de nos jours généralement conservés dans des données non modifiables segment).
• ajouter des valeurs int de n'importe quelle taille implique des problèmes d'alignement. La longueur initiale doit être alignée, mais il n'y a aucune raison de le faire pour les données de caractères (et encore une fois, forcer l'alignement des chaînes impliquerait des problèmes lors de leur traitement comme un tas d'octets).
• la longueur est connue au moment de la compilation pour les chaînes littérales constantes (sizeof). Alors, pourquoi voudrait-on le stocker en mémoire avant de le préparer aux données réelles?
• d'une manière C fait comme (presque) tout le monde, les chaînes sont considérées comme des tableaux de caractères. Comme la longueur du tableau n'est pas gérée par C, c'est la longueur logique qui n'est pas gérée non plus pour les chaînes. La seule chose surprenante est que 0 élément a été ajouté à la fin, mais ce n'est qu'au niveau du langage de base lors de la saisie d'une chaîne entre guillemets doubles. Les utilisateurs peuvent parfaitement appeler des fonctions de manipulation de chaîne en passant la longueur, ou même utiliser la memcopy ordinaire à la place. SZ sont juste une installation. Dans la plupart des autres langues, la longueur du tableau est gérée, il est logique qu'il en soit de même pour les chaînes.
• dans les temps modernes de toute façon, les jeux de caractères de 1 octet ne suffisent pas et vous devez souvent traiter des chaînes unicode codées où le nombre de caractères est très différent du nombre d'octets. Cela implique que les utilisateurs voudront probablement plus que "juste la taille", mais aussi d'autres informations. Garder la longueur ne donne aucune utilité (en particulier aucun endroit naturel pour les stocker) concernant ces autres informations utiles.

Cela dit, pas besoin de se plaindre dans les rares cas où les chaînes C standard sont en effet inefficaces. Libs sont disponibles. Si j'ai suivi cette tendance, je devrais me plaindre que le standard C n'inclut aucune fonction de support regex ... mais vraiment tout le monde sait que ce n'est pas un vrai problème car il y a des bibliothèques disponibles à cet effet. Donc, lorsque l'efficacité de la manipulation de chaînes est souhaitée, pourquoi ne pas utiliser une bibliothèque comme bstring ? Ou même des chaînes C ++?

EDIT : J'ai récemment un regard à cordes D . Il est assez intéressant de voir que la solution choisie n'est ni un préfixe de taille, ni une terminaison nulle. Comme en C, les chaînes littérales entre guillemets doubles sont juste un raccourci pour les tableaux de caractères immuables, et le langage a également un mot clé de chaîne signifiant cela (tableau de caractères immuable).

Mais les tableaux D sont beaucoup plus riches que les tableaux C. Dans le cas de tableaux statiques, la longueur est connue au moment de l'exécution, il n'est donc pas nécessaire de stocker la longueur. Le compilateur l'a au moment de la compilation. Dans le cas des tableaux dynamiques, la longueur est disponible mais la documentation D n'indique pas où elle est conservée. Pour tout ce que nous savons, le compilateur pourrait choisir de le garder dans un registre ou dans une variable stockée loin des données des caractères.

Sur les tableaux de caractères normaux ou les chaînes non littérales, il n'y a pas de zéro final, donc le programmeur doit le mettre lui-même s'il veut appeler une fonction C à partir de D. Dans le cas particulier des chaînes littérales, cependant le compilateur D met toujours un zéro à la fin de chaque chaîne (pour permettre une conversion facile en chaînes C pour faciliter l'appel de la fonction C?), mais ce zéro ne fait pas partie de la chaîne (D ne le compte pas dans la taille de la chaîne).

La seule chose qui m'a un peu déçu est que les chaînes sont censées être utf-8, mais la longueur renvoie apparemment toujours un certain nombre d'octets (du moins c'est vrai sur mon compilateur gdc) même lorsque j'utilise des caractères multi-octets. Il n'est pas clair pour moi s'il s'agit d'un bogue du compilateur ou par objectif. (OK, j'ai probablement découvert ce qui s'est passé. Pour dire au compilateur D que votre source utilise utf-8, vous devez mettre une marque d'ordre d'octets stupide au début. J'écris stupide parce que je sais que ce n'est pas l'éditeur qui fait ça, surtout pour UTF- 8 qui est censé être compatible ASCII).

Je pense qu'il a des raisons historiques et a trouvé cela dans wikipedia :

Au moment où C (et les langages dont il était dérivé) ont été développés, la mémoire était extrêmement limitée, donc l'utilisation d'un seul octet de surcharge pour stocker la longueur d'une chaîne était intéressante. La seule alternative populaire à l'époque, généralement appelée "chaîne Pascal" (bien qu'utilisée également par les premières versions de BASIC), utilisait un octet de tête pour stocker la longueur de la chaîne. Cela permet à la chaîne de contenir NUL et fait que la recherche de la longueur n'a besoin que d'un seul accès à la mémoire (temps O (1) (constant)). Mais un octet limite la longueur à 255. Cette limitation de longueur était beaucoup plus restrictive que les problèmes avec la chaîne C, donc la chaîne C en général l'a emporté.

Calavera est bonne , mais que les gens ne semblent pas comprendre son point, je vais donner des exemples de code.

Tout d'abord, considérons ce qu'est C: un langage simple, où tout le code a une traduction assez directe en langage machine. Tous les types s'intègrent dans les registres et sur la pile, et cela ne nécessite pas de système d'exploitation ou une grande bibliothèque d'exécution, car il était destiné à écrire ces choses (une tâche à laquelle est parfaitement bien adaptée, compte tenu de là n'est même pas un concurrent probable à ce jour).

Si C avait un stringtype, comme intou char, ce serait un type qui ne rentrerait pas dans un registre ou dans la pile, et nécessiterait l'allocation de mémoire (avec toute son infrastructure de support) pour être gérée de quelque manière que ce soit. Tout cela va à l'encontre des principes de base de C.

Ainsi, une chaîne en C est:

char s*;

Supposons donc que ce soit préfixé en longueur. Écrivons le code pour concaténer deux chaînes:

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;
}

Une autre alternative serait d'utiliser une structure pour définir une chaîne:

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

À ce stade, toute manipulation de chaîne nécessiterait deux allocations, ce qui, dans la pratique, signifie que vous devez passer par une bibliothèque pour en faire le traitement.

La chose drôle est ... struct comme ça font existent dans C! Ils ne sont tout simplement pas utilisés pour l'affichage quotidien des messages destinés à l'utilisateur.

Donc, voici le point Calavera fait: il n'y a pas de type chaîne en C . Pour faire quoi que ce soit avec cela, vous devez prendre un pointeur et le décoder en tant que pointeur vers deux types différents, puis il devient très pertinent quelle est la taille d'une chaîne, et ne peut pas simplement être laissé comme "défini par l'implémentation".

Maintenant, C peut gérer la mémoire de toute façon, et les memfonctions de la bibliothèque (dans <string.h>, même!) Fournissent tous les outils dont vous avez besoin pour gérer la mémoire comme une paire de pointeurs et de taille. Les soi-disant "chaînes" en C ont été créées dans un seul but: afficher des messages dans le contexte de l'écriture d'un système d'exploitation destiné aux terminaux de texte. Et, pour cela, la résiliation nulle est suffisante.

Évidemment, pour des raisons de performances et de sécurité, vous souhaiterez conserver la longueur d'une chaîne pendant que vous travaillez avec elle plutôt que de la répéter strlenou l'équivalent. Cependant, le stockage de la longueur dans un emplacement fixe juste avant le contenu de la chaîne est une conception incroyablement mauvaise. Comme l'a souligné Jörgen dans les commentaires sur la réponse de Sanjit, cela empêche de traiter la queue d'une chaîne comme une chaîne, ce qui rend par exemple beaucoup d'opérations courantes comme path_to_filenameou filename_to_extensionimpossible sans allouer de nouvelle mémoire (et encourant la possibilité d'échec et de gestion des erreurs) . Et puis bien sûr, il y a le problème que personne ne peut s'entendre sur le nombre d'octets que le champ de longueur de chaîne doit occuper (beaucoup de mauvaises "chaîne Pascal"

La conception de C de laisser le programmeur choisir si / où / comment stocker la longueur est beaucoup plus flexible et puissante. Mais bien sûr, le programmeur doit être intelligent. C punit la stupidité avec des programmes qui plantent, s'arrêtent ou donnent racine à vos ennemis.

Paresse, enregistrez la frugalité et la portabilité en tenant compte de l'intestin de l'assemblage de tout langage, en particulier C qui est une étape au-dessus de l'assemblage (héritant ainsi de beaucoup de code hérité de l'assemblage). Vous seriez d'accord car un caractère nul serait inutile en ces jours ASCII (et probablement aussi bon qu'un caractère de contrôle EOF).

voyons en pseudo code

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

total 1 utilisation du registre

cas 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 registre utilisé

Cela peut sembler à courte vue à ce moment-là, mais compte tenu de la frugalité du code et du registre (qui étaient PREMIUM à l'époque, au moment où vous le savez, ils utilisent des cartes perforées). Ainsi, étant plus rapide (lorsque la vitesse du processeur pouvait être comptée en kHz), ce "Hack" était sacrément bon et portable pour enregistrer sans difficulté le processeur.

Pour des raisons d'argument, je vais implémenter 2 opération de chaîne commune

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

complexité O (n) où dans la plupart des cas, la chaîne PASCAL est O (1) car la longueur de la chaîne est suspendue à la structure de la chaîne (cela signifierait également que cette opération devrait être effectuée à un stade antérieur).

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 complexité O (n) et l'ajout de la longueur de la chaîne ne changeraient pas la complexité de l'opération, alors que j'admets que cela prendrait 3 fois moins de temps.

D'un autre côté, si vous utilisez une chaîne PASCAL, vous devrez repenser votre API pour prendre en compte la longueur du registre et le bit-endianness, la chaîne PASCAL a la limitation bien connue de 255 caractères (0xFF) car la longueur a été stockée dans 1 octet (8 bits) ), et si vous vouliez une chaîne plus longue (16 bits -> n'importe quoi), vous devrez prendre en compte l'architecture dans une couche de votre code, ce qui signifierait dans la plupart des cas des API de chaîne incompatibles si vous vouliez une chaîne plus longue.

Exemple:

Un fichier a été écrit avec votre API de chaîne pré-ajoutée sur un ordinateur 8 bits et devrait ensuite être lu sur un ordinateur 32 bits, que ferait le programme paresseux si vos 4 octets sont la longueur de la chaîne, puis allouez ce lot de mémoire essayez ensuite de lire autant d'octets. Un autre cas serait la lecture d'une chaîne de 32 octets PPC (petit endian) sur un x86 (gros endian), bien sûr si vous ne savez pas que l'un est écrit par l'autre, il y aura des problèmes. La longueur de 1 octet (0x00000001) deviendrait 16777216 (0x0100000), soit 16 Mo pour la lecture d'une chaîne de 1 octet. Bien sûr, vous diriez que les gens devraient s'accorder sur une norme, mais même l'unicode 16 bits a une endianité faible et grande.

Bien sûr, C aurait aussi ses problèmes, mais serait très peu affecté par les problèmes soulevés ici.

À bien des égards, C était primitif. Et j'ai adoré.

C'était une étape au-dessus du langage d'assemblage, vous offrant presque les mêmes performances avec un langage beaucoup plus facile à écrire et à maintenir.

Le terminateur nul est simple et ne nécessite aucun support spécial de la langue.

Avec le recul, cela ne semble pas si pratique. Mais j'ai utilisé le langage d'assemblage dans les années 80 et cela semblait très pratique à l'époque. Je pense simplement que les logiciels évoluent continuellement et que les plates-formes et les outils sont de plus en plus sophistiqués.

En supposant un instant que C implémente les chaînes de la manière Pascal, en les préfixant par la longueur: une chaîne de 7 caractères est-elle le même TYPE DE DONNÉES qu'une chaîne de 3 caractères? Si la réponse est oui, alors quel type de code le compilateur doit-il générer lorsque j'attribue le premier au second? La chaîne doit-elle être tronquée ou automatiquement redimensionnée? En cas de redimensionnement, cette opération doit-elle être protégée par un verrou afin de la sécuriser par thread? Le côté approche C a franchi toutes ces questions, que cela plaise ou non :)

D'une manière ou d'une autre, j'ai compris que la question impliquait qu'il n'y avait pas de prise en charge du compilateur pour les chaînes à préfixe de longueur en C. L'exemple suivant montre qu'au moins vous pouvez démarrer votre propre bibliothèque de chaînes C, où les longueurs de chaîne sont comptées au moment de la compilation, avec une construction comme celle-ci:

#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;
}

Cependant, cela ne posera aucun problème car vous devez faire attention quand libérer spécifiquement ce pointeur de chaîne et quand il est alloué statiquement ( chartableau littéral ).

Edit: Comme réponse plus directe à la question, mon avis est que c'était la façon dont C pouvait prendre en charge à la fois la longueur de chaîne disponible (en tant que constante de temps de compilation), si vous en avez besoin, mais toujours sans surcharge de mémoire si vous souhaitez utiliser seulement des pointeurs et zéro terminaison.

Bien sûr, il semble que travailler avec des chaînes terminées par zéro était la pratique recommandée, car la bibliothèque standard en général ne prend pas les longueurs de chaîne comme arguments, et puisque l'extraction de la longueur n'est pas aussi simple que char * s = "abc", comme le montre mon exemple.

"Même sur une machine 32 bits, si vous autorisez la chaîne à avoir la taille de la mémoire disponible, une chaîne préfixée de longueur n'est plus large que de trois octets qu'une chaîne terminée par un caractère nul."

Tout d'abord, 3 octets supplémentaires peuvent représenter une surcharge considérable pour les chaînes courtes. En particulier, une chaîne de longueur nulle prend désormais 4 fois plus de mémoire. Certains d'entre nous utilisent des machines 64 bits, nous avons donc besoin de 8 octets pour stocker une chaîne de longueur nulle, ou le format de chaîne ne peut pas gérer les chaînes les plus longues prises en charge par la plate-forme.

Il peut également y avoir des problèmes d'alignement à régler. Supposons que j'ai un bloc de mémoire contenant 7 chaînes, comme "solo \ 0second \ 0 \ 0four \ 0five \ 0 \ 0seventh". La deuxième chaîne commence à l'offset 5. Le matériel peut nécessiter que les entiers 32 bits soient alignés à une adresse qui est un multiple de 4, vous devez donc ajouter un remplissage, augmentant encore la surcharge. La représentation C est très efficace en mémoire en comparaison. (L'efficacité de la mémoire est bonne; elle aide les performances de cache, par exemple.)

La terminaison nulle permet des opérations rapides basées sur un pointeur.

Un point non encore mentionné: lorsque C a été conçu, il y avait de nombreuses machines où un «char» n'était pas huit bits (même aujourd'hui, il existe des plates-formes DSP où il ne l'est pas). Si l'on décide que les chaînes doivent être préfixées par la longueur, combien de préfixes de longueur vaut-il utiliser? L'utilisation de deux imposerait une limite artificielle sur la longueur de chaîne pour les machines avec un caractère d'adressage 8 bits et un espace d'adressage 32 bits, tout en gaspillant de l'espace sur les machines avec un caractère d'adressage 16 bits et un espace d'adressage 16 bits.

Si l'on voulait permettre le stockage efficace de chaînes de longueur arbitraire, et si 'char' était toujours de 8 bits, on pourrait - pour certaines dépenses en vitesse et en taille de code - définir un schéma était une chaîne préfixée par un nombre pair N serait long de N / 2 octets, une chaîne préfixée par une valeur impaire N et une valeur paire M (lecture à l'envers) pourrait être ((N-1) + M * char_max) / 2, etc. et exiger que tout tampon qui prétend offrir une certaine quantité d'espace pour contenir une chaîne doit permettre suffisamment d'octets précédant cet espace pour gérer la longueur maximale. Le fait que 'char' ne soit pas toujours 8 bits, cependant, compliquerait un tel schéma, car le nombre de 'char' requis pour contenir la longueur d'une chaîne varierait en fonction de l'architecture du CPU.

De nombreuses décisions de conception concernant C découlent du fait que lors de sa mise en œuvre initiale, le passage des paramètres était quelque peu coûteux. Étant donné un choix entre par exemple

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);
}

contre

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);
}

cette dernière aurait été légèrement moins chère (et donc préférée) car elle n'aurait nécessité que de passer un paramètre plutôt que deux. Si la méthode appelée n'avait pas besoin de connaître l'adresse de base du tableau ni son index, passer un seul pointeur combinant les deux serait moins cher que de passer les valeurs séparément.

Bien qu'il existe de nombreuses manières raisonnables pour C de coder des longueurs de chaîne, les approches qui avaient été inventées jusqu'à ce moment auraient toutes les fonctions requises qui devraient pouvoir fonctionner avec une partie d'une chaîne pour accepter l'adresse de base de la chaîne et l'index souhaité comme deux paramètres distincts. L'utilisation d'une terminaison à zéro octet a permis d'éviter cette exigence. Bien que d'autres approches soient meilleures avec les machines d'aujourd'hui (les compilateurs modernes transmettent souvent les paramètres dans les registres, et memcpy peut être optimisé de manière strcpy () - les équivalents ne le peuvent pas) suffisamment de code de production utilise des chaînes terminées à zéro octet qu'il est difficile de changer pour autre chose.

PS - En échange d'une légère pénalité de vitesse sur certaines opérations et d'une infime surcharge supplémentaire sur les chaînes plus longues, il aurait été possible que les méthodes qui fonctionnent avec les chaînes acceptent les pointeurs directement vers les chaînes, les tampons de chaîne vérifiés par les limites ou structures de données identifiant les sous-chaînes d'une autre chaîne. Une fonction comme "strcat" aurait ressemblé à quelque chose comme [syntaxe moderne]

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 peu plus grand que la méthode K&R strcat, mais il prendrait en charge la vérification des limites, contrairement à la méthode K&R. De plus, contrairement à la méthode actuelle, il serait possible de concaténer facilement une sous-chaîne arbitraire, par exemple

/* 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);
}

Notez que la durée de vie de la chaîne retournée par temp_substring serait limitée par celles de set src, qui a toujours été plus courte (c'est pourquoi la méthode nécessiteinf d'être passée - si elle était locale, elle mourrait lorsque la méthode reviendrait).

En termes de coût de mémoire, les chaînes et les tampons jusqu'à 64 octets auraient un octet de surcharge (comme les chaînes terminées par zéro); des chaînes plus longues auraient un peu plus (si l'on autorisait des quantités de surcharge entre deux octets et le maximum requis serait un compromis temps / espace). Une valeur spéciale de l'octet longueur / mode serait utilisée pour indiquer qu'une fonction chaîne a reçu une structure contenant un octet indicateur, un pointeur et une longueur de tampon (qui pourrait ensuite être indexée arbitrairement dans n'importe quelle autre chaîne).

Bien sûr, K&R n'a pas implémenté une telle chose, mais c'est probablement parce qu'ils ne voulaient pas consacrer beaucoup d'efforts à la gestion des chaînes - un domaine où même aujourd'hui de nombreuses langues semblent plutôt anémiques.

Selon Joel Spolsky dans ce billet de blog ,

C'est parce que le microprocesseur PDP-7, sur lequel UNIX et le langage de programmation C ont été inventés, avait un type de chaîne ASCIZ. ASCIZ signifiait "ASCII avec un Z (zéro) à la fin."

Après avoir vu toutes les autres réponses ici, je suis convaincu que même si cela est vrai, ce n'est qu'une partie de la raison pour laquelle C a des "chaînes" à terminaison nulle. Ce post est assez éclairant sur la façon dont des choses simples comme les cordes peuvent être assez difficiles.

Pas nécessairement une justification, mais un contrepoint à la longueur codée

1. Certaines formes d'encodage de longueur dynamique sont supérieures à l'encodage de longueur statique en ce qui concerne la mémoire, tout dépend de l'utilisation. Regardez simplement UTF-8 pour la preuve. Il s'agit essentiellement d'un tableau de caractères extensible pour encoder un seul caractère. Cela utilise un seul bit pour chaque octet étendu. La terminaison NUL utilise 8 bits. Le préfixe de longueur, je pense, peut aussi être raisonnablement appelé longueur infinie en utilisant 64 bits. La fréquence à laquelle vous frappez le cas de vos bits supplémentaires est le facteur décisif. Une seule chaîne extrêmement large? Peu importe si vous utilisez 8 ou 64 bits? Beaucoup de petites chaînes (c'est-à-dire des chaînes de mots anglais)? Vos coûts de préfixe représentent alors un pourcentage élevé.

2. Les chaînes préfixées en longueur permettant un gain de temps ne sont pas une réalité . Que vos données fournies doivent avoir une longueur fournie, vous comptez au moment de la compilation ou vous recevez vraiment des données dynamiques que vous devez coder sous forme de chaîne. Ces tailles sont calculées à un moment donné de l'algorithme. Une variable distincte pour stocker la taille d'une chaîne terminée par null peut être fournie. Ce qui rend la comparaison sur le gain de temps discutable. On a juste un NUL supplémentaire à la fin ... mais si le codage de longueur ne comprend pas ce NUL, il n'y a littéralement aucune différence entre les deux. Aucun changement algorithmique n'est nécessaire. Juste un pré-pass, vous devez vous concevoir manuellement au lieu d'avoir un compilateur / runtime pour le faire. C consiste principalement à faire les choses manuellement.

3. Le préfixe de longueur étant facultatif est un argument de vente. Je n'ai pas toujours besoin de ces informations supplémentaires pour un algorithme, donc le fait de le faire pour chaque chaîne rend mon temps de précalcul + de calcul jamais capable de descendre en dessous de O (n). (C'est-à-dire le générateur de nombres aléatoires matériels 1-128. Je peux tirer d'une "chaîne infinie". Disons que cela ne génère que des caractères si rapidement. Donc, notre longueur de chaîne change tout le temps. Mais mon utilisation des données ne se soucie probablement pas de savoir comment de nombreux octets aléatoires que j'ai. Il veut juste le prochain octet inutilisé disponible dès qu'il peut l'obtenir après une demande. Je pourrais attendre sur l'appareil. Mais je pourrais aussi avoir un tampon de caractères pré-lu. Une comparaison de longueur est un gaspillage inutile de calcul. Un contrôle nul est plus efficace.)

4. Le préfixe de longueur est un bon garde contre le débordement de tampon? Il en va de même pour l'utilisation rationnelle des fonctions et de l'implémentation de la bibliothèque. Et si je transmets des données mal formées? Mon tampon fait 2 octets mais je dis à la fonction que c'est 7! Ex: si gets () était destiné à être utilisé sur des données connues, il aurait pu y avoir une vérification de tampon interne qui a testé les tampons compilés et malloc ()appels et toujours suivre les spécifications. S'il était destiné à être utilisé comme un tuyau pour un STDIN inconnu pour arriver à un tampon inconnu, il est clair que l'on ne peut pas connaître la taille du tampon, ce qui signifie qu'un argument de longueur est inutile, vous avez besoin d'autre chose ici comme un test canari. Pour cette question, vous ne pouvez pas préfixer la longueur de certains flux et entrées, vous ne pouvez tout simplement pas. Ce qui signifie que la vérification de la longueur doit être intégrée à l'algorithme et non une partie magique du système de frappe. TL; DR terminé par NUL n'a jamais dû être dangereux, il s'est simplement retrouvé de cette façon par une mauvaise utilisation.

5. contre-point: la terminaison NUL est ennuyeuse en binaire. Vous devez soit faire un préfixe de longueur ici, soit transformer des octets NUL d'une manière ou d'une autre: codes d'échappement, remappage de plage, etc ... ce qui signifie bien sûr plus d'utilisation de la mémoire / informations réduites / plus d'opérations par octet. Le préfixe de longueur gagne principalement la guerre ici. Le seul avantage d'une transformation est qu'aucune fonction supplémentaire ne doit être écrite pour couvrir les chaînes de préfixe de longueur. Ce qui signifie que sur vos routines sub-O (n) plus optimisées, vous pouvez les faire agir automatiquement comme leurs équivalents O (n) sans ajouter plus de code. L'inconvénient est, bien sûr, un gaspillage de temps / mémoire / compression lorsqu'il est utilisé sur des chaînes lourdes NUL.Selon la quantité de votre bibliothèque que vous finissez par dupliquer pour fonctionner sur des données binaires, il peut être judicieux de travailler uniquement avec des chaînes de préfixe de longueur. Cela dit, on pourrait également faire de même avec des chaînes de préfixe de longueur ... -1 longueur pourrait signifier terminé par NUL et vous pouvez utiliser des chaînes terminées par NUL à l'intérieur terminé par longueur.

6. Concat: "O (n + m) vs O (m)" Je suppose que vous faites référence à m comme la longueur totale de la chaîne après la concaténation car ils doivent tous les deux avoir ce nombre d'opérations minimum (vous ne pouvez pas simplement virer de bord -sur la chaîne 1, que faire si vous devez réallouer?). Et je suppose que n est une quantité mythique d'opérations que vous n'avez plus à faire à cause d'un pré-calcul. Si oui, alors la réponse est simple: pré-calculer. Sivous insistez pour que vous ayez toujours assez de mémoire pour ne pas avoir besoin de réaffecter et c'est la base de la notation big-O alors la réponse est encore plus simple: faites une recherche binaire sur la mémoire allouée pour la fin de la chaîne 1, il y a clairement un grand échantillon de zéros infinis après la chaîne 1 pour que nous ne nous soucions pas de la réallocation. Là, facilement obtenu n pour se connecter (n) et j'ai à peine essayé. Ce qui si vous vous souvenez que log (n) n'est pratiquement jamais aussi grand que 64 sur un ordinateur réel, ce qui revient essentiellement à dire O (64 + m), qui est essentiellement O (m). (Et oui, cette logique a été utilisée dans l'analyse au moment de l'exécution des structures de données réelles utilisées aujourd'hui. Ce n'est pas une connerie du haut de ma tête.)

7. Concat () / Len () à _nouveau : Mémorisez les résultats. Facile. Transforme tous les calculs en pré-calculs si possible / nécessaire. Il s'agit d'une décision algorithmique. Ce n'est pas une contrainte imposée de la langue.

8. Le passage du suffixe de chaîne est plus facile / possible avec la terminaison NUL. Selon la façon dont le préfixe de longueur est implémenté, il peut être destructeur sur la chaîne d'origine et parfois même impossible. Exiger une copie et passer O (n) au lieu de O (1).

9. Le passage d'argument / le déréférencement est moins important pour les terminaisons NUL que pour les préfixes de longueur. Évidemment parce que vous transmettez moins d'informations. Si vous n'avez pas besoin de longueur, cela permet d'économiser beaucoup d'empreinte et de permettre des optimisations.

10. Vous pouvez tricher. C'est vraiment juste un pointeur. Qui a dit que vous deviez le lire sous forme de chaîne? Et si vous voulez le lire comme un seul caractère ou un flottant? Et si vous voulez faire le contraire et lire un flottant comme une chaîne? Si vous faites attention, vous pouvez le faire avec la terminaison NUL. Vous ne pouvez pas faire cela avec le préfixe de longueur, c'est un type de données distinctement différent d'un pointeur généralement. Vous devrez probablement construire une chaîne octet par octet et obtenir la longueur. Bien sûr, si vous vouliez quelque chose comme un flotteur entier (il y a probablement un NUL à l'intérieur), vous devriez quand même lire octet par octet, mais les détails vous sont laissés à décider.

TL; DR Utilisez-vous des données binaires? Si non, la terminaison NUL permet plus de liberté algorithmique. Si oui, alors la quantité de code vs vitesse / mémoire / compression est votre principale préoccupation. Un mélange des deux approches ou de la mémorisation pourrait être le meilleur.

Je n'achète pas la réponse "C n'a pas de chaîne". Certes, C ne prend pas en charge les types intégrés de niveau supérieur, mais vous pouvez toujours représenter les structures de données en C et c'est ce qu'est une chaîne. Le fait qu'une chaîne ne soit qu'un pointeur en C ne signifie pas que les N premiers octets ne peuvent pas prendre une signification particulière en tant que longueur.

Les développeurs Windows / COM seront très familiers avec le BSTRtype qui est exactement comme ceci - une chaîne C à préfixe de longueur où les données de caractères réelles ne commencent pas à l'octet 0.

Il semble donc que la décision d'utiliser la terminaison nulle soit simplement ce que les gens préfèrent, pas une nécessité de la langue.

gcc accepte les codes ci-dessous:

char s [4] = "abcd";

et c'est ok si nous traitons comme un tableau de caractères mais pas de chaîne. Autrement dit, nous pouvons y accéder avec s [0], s [1], s [2] et s [3], ou même avec memcpy (dest, s, 4). Mais nous aurons des personnages en désordre lorsque nous essaierons avec put (s), ou pire avec strcpy (dest, s).