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

281

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

Billy ONeal
la source
110
J'ai toujours pensé que c'était un rite de passage pour tous les programmeurs C ++ d'écrire leur propre bibliothèque de chaînes.
Juliet
31
Qu'est-ce que c'est que d'attendre des explications rationnelles maintenant? Je suppose que vous voudrez entendre une justification pour x86 ou DOS ensuite? En ce qui me concerne, la pire technologie l'emporte. À chaque fois. Et la pire représentation des chaînes.
jalf
4
Pourquoi prétendez-vous que les chaînes de préfixe de longueur sont supérieures? Après tout, C est devenu populaire car il utilisait des chaînes terminées par zéro, ce qui le distinguait des autres langages.
Daniel C.Sobral
44
@Daniel: C est devenu populaire parce que c'est une représentation simple, efficace et portable des programmes exécutables sur les machines Von Neumann, et parce qu'il a été utilisé pour Unix. Ce n'est certainement pas parce qu'il a décidé d'utiliser des chaînes terminées par null. Si c'était une bonne décision de conception, les gens l'auraient copiée, et ils ne l'ont pas fait. Ils ont certainement copié à peu près tout le reste de C.
Billy ONeal
4
Concat est uniquement O (m) avec un préfixe de longueur si vous détruisez l'une des chaînes. Sinon, même vitesse. Les chaînes C les plus utilisées (historiquement) étaient l'impression et la numérisation. Dans ces deux cas, la terminaison nulle est plus rapide car elle enregistre un registre.
Daniel C.Sobral

Réponses:

195

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

Hans Passant
la source
12
Une autre citation pertinente: "... la sémantique des chaînes est entièrement englobée par des règles plus générales régissant tous les tableaux, et par conséquent le langage est plus simple à décrire ..."
AShelly
151

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

Robert S Ciaccio
la source
29
char *temp = "foo bar";est une déclaration valide en C ... hé! n'est-ce pas une chaîne? n'est-il pas terminé?
Yanick Rochon
56
@Yanick: c'est juste un moyen pratique de dire au compilateur de créer un tableau de caractères avec un null à la fin. ce n'est pas une "chaîne"
Robert S Ciaccio
28
@calavera: Mais cela aurait pu signifier tout simplement "Créer un tampon mémoire avec ce contenu de chaîne et un préfixe de longueur de deux octets",
Billy ONeal
14
@Billy: eh bien, comme une `` chaîne '' est vraiment juste un pointeur vers char, ce qui équivaut à un pointeur vers octet, comment sauriez-vous que le tampon que vous traitez est vraiment destiné à être une `` chaîne ''? vous auriez besoin d'un nouveau type autre que char / byte * pour indiquer cela. peut-être une struct?
Robert S Ciaccio
27
Je pense que @calavera a raison, C n'a pas de type de données pour les chaînes. Ok, vous pouvez considérer un tableau de caractères comme une chaîne, mais cela ne signifie pas que c'est toujours une chaîne (pour chaîne, je veux dire une séquence de caractères avec une signification définie). Un fichier binaire est un tableau de caractères, mais ces caractères ne signifient rien pour un humain.
Blackear
106

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

kriss
la source
7
... Suite ... Plusieurs de vos points, je pense, sont tout simplement faux, c'est-à-dire l'argument "tout est un fichier". Les fichiers sont un accès séquentiel, les chaînes C ne le sont pas. Le préfixe de longueur peut également être effectué avec un sucre syntaxique minimal. Le seul argument raisonnable ici est d'essayer de gérer les préfixes 32 bits sur un petit matériel (c'est-à-dire 8 bits); Je pense que cela pourrait être résolu simplement en disant que la taille de la longueur est déterminée par la mise en œuvre. Après tout, c'est ce qui std::basic_stringfait.
Billy ONeal
3
@Billy ONeal: il y a vraiment deux parties différentes dans ma réponse. L'une concerne ce qui fait partie du «langage C de base», l'autre concerne ce que les bibliothèques standard doivent fournir. En ce qui concerne la prise en charge des chaînes, il n'y a qu'un seul élément du langage de base: la signification d'un double guillemet entouré d'octets. Je ne suis pas vraiment plus heureux que toi avec le comportement C. Je me sens comme par magie en ajoutant que zéro à la fin de chaque double ferme des octets fermés est assez mauvais. Je préfère et explicite \0à la fin lorsque les programmeurs le souhaitent au lieu de l'implicite. La longueur de préparation est bien pire.
kriss
2
@Billy ONeal: ce n'est tout simplement pas vrai, les utilisations se soucient de ce qui est de base et de ce que sont les bibliothèques. Le plus gros point est lorsque C est utilisé pour implémenter le système d'exploitation. À ce niveau, aucune bibliothèque n'est disponible. C est également souvent utilisé dans des contextes intégrés ou pour des appareils de programmation où vous avez souvent le même type de restrictions. Dans de nombreux cas, Joes ne devrait probablement pas utiliser C du tout de nos jours: "OK, vous le voulez sur la console? Avez-vous une console? Non? Dommage ..."
kriss
5
@Billy "Eh bien, pour les .01% des programmeurs C qui implémentent des systèmes d'exploitation, très bien." Les autres programmeurs peuvent faire une randonnée. C a été créé pour écrire un système d'exploitation.
Daniel C.Sobral
5
Pourquoi? Parce qu'il dit que c'est un langage à usage général? Dit-il ce que faisaient les gens qui l'ont écrit lors de sa création? À quoi a-t-il servi pendant les premières années de sa vie? Alors, qu'est-ce qu'il dit qui n'est pas d'accord avec moi? Il s'agit d'un langage à usage général créé pour écrire un système d'exploitation . Le nie-t-il?
Daniel C.Sobral
61

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

khachik
la source
2
@muntoo Hmm ... compatibilité?
khachik
19
@muntoo: Parce que cela casserait des quantités monumentielles de code C et C ++ existant.
Billy ONeal
10
@muntoo: Les paradigmes vont et viennent, mais le code hérité est éternel. Toute future version de C devrait continuer à prendre en charge les chaînes terminées par 0, sinon plus de 30 ans de code hérité devraient être réécrits (ce qui ne se produira pas). Et tant que l'ancienne méthode est disponible, c'est ce que les gens continueront à utiliser, car c'est ce qu'ils connaissent.
John Bode
8
@muntoo: Croyez-moi, parfois j'aimerais pouvoir. Mais je préfère toujours les chaînes terminées par 0 aux chaînes Pascal.
John Bode
2
Parlons de l'héritage ... Les chaînes C ++ doivent maintenant se terminer par NUL.
Jim Balter
32

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.

Daniel C. Sobral
la source
2
1. +1. 2. Évidemment, si le comportement par défaut de la langue avait été fait en utilisant des préfixes de longueur, il y aurait eu d'autres choses pour faciliter cela. Par exemple, tous vos lancers auraient été cachés à la place par des appels à strlenet des amis. Quant au problème de "laisser le soin à l'implémentation", on pourrait dire que le préfixe est tout ce qui shortest sur la case cible. Ensuite, tout votre casting fonctionnerait toujours. 3. Je peux proposer des scénarios artificiels toute la journée qui font que l'un ou l'autre système a l'air mauvais.
Billy ONeal
5
@Billy La chose bibliothèque est assez vraie, à part le fait que C a été conçu pour une utilisation minimale ou nulle de la bibliothèque. L'utilisation de prototypes, par exemple, n'était pas courante au début. Dire le préfixe est shorten fait limite la taille de la chaîne, ce qui semble être une chose sur laquelle ils ne tenaient pas. Moi-même, après avoir travaillé avec des chaînes BASIC et Pascal 8 bits, des chaînes COBOL de taille fixe et des choses similaires, je suis rapidement devenu un grand fan de chaînes C de taille illimitée. De nos jours, une taille de 32 bits gérera n'importe quelle chaîne pratique, mais l'ajout précoce de ces octets était problématique.
Daniel C.Sobral
1
@Billy: Tout d'abord, merci Daniel ... tu sembles comprendre à quoi je veux en venir. Deuxièmement, Billy, je pense que vous manquez encore le point soulevé ici. Pour ma part, je ne discute pas les avantages et les inconvénients de préfixer les types de données de chaîne avec leur longueur. Ce que je veux dire, et ce que Daniel très clairement souligné, est qu'il y avait une décision prise dans la mise en œuvre de C pour ne pas traiter cet argument du tout . Les chaînes n'existent pas en ce qui concerne la langue de base. La décision sur la façon de gérer les chaînes est laissée au programmeur ... et la terminaison nulle est devenue populaire.
Robert S Ciaccio
1
+1 par moi. J'aimerais ajouter encore une chose; une structure telle que vous la proposez rate une étape importante vers un vrai stringtype: elle ne connaît pas les personnages. C'est un tableau de "char" (un "char" dans le jargon de la machine est autant un caractère qu'un "mot" est ce que les humains appellent un mot dans une phrase). Une chaîne de caractères est un concept de niveau supérieur qui pourrait être implémenté au-dessus d' un tableau charsi vous introduisiez la notion d'encodage.
Frerich Raabe
2
@ DanielC.Sobral: De plus, la structure que vous mentionnez ne nécessiterait pas deux allocations. Soit l'utiliser comme vous l'avez sur la pile (ne bufnécessite donc qu'une allocation), soit utiliser struct string {int len; char buf[]};et allouer le tout avec une allocation en tant que membre de tableau flexible, et le passer comme un string*. (Ou sans doute, struct string {int capacity; int len; char buf[]};pour des raisons évidentes de performances)
Mooing Duck
20

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

R .. GitHub ARRÊTEZ D'AIDER LA GLACE
la source
+1. Ce serait bien d'avoir un endroit standard pour stocker la longueur afin que ceux d'entre nous qui veulent quelque chose comme le préfixe de la longueur n'aient pas à écrire des tonnes de "code de colle" partout.
Billy ONeal
2
Il n'y a pas de place standard possible par rapport aux données de chaîne, mais vous pouvez bien sûr utiliser une variable locale distincte (la recalculer plutôt que de la passer lorsque la dernière n'est pas pratique et que la première n'est pas trop inutile) ou une structure avec un pointeur à la chaîne (et mieux encore, un indicateur indiquant si la structure "possède" le pointeur à des fins d'allocation ou s'il s'agit d'une référence à une chaîne appartenant à un autre. Et bien sûr, vous pouvez inclure un membre de tableau flexible dans la structure pour la flexibilité à allouer le string avec la structure quand il vous convient
R .. GitHub STOP HELPING ICE
13

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.

dvhh
la source
2
@deemoowoor: Concat: O(m+n)avec des chaînes nullterm, O(n)typiques partout ailleurs. Longueur O(n)avec chaînes nulles, O(1)partout ailleurs. Rejoignez: O(n^2)avec des chaînes nullterm, O(n)partout ailleurs. Il y a des cas où les chaînes terminées par null sont plus efficaces (c'est-à-dire qu'il suffit d'ajouter un cas au pointeur), mais la concaténation et la longueur sont de loin les opérations les plus courantes (la longueur au moins est requise pour le formatage, la sortie des fichiers, l'affichage de la console, etc.) . Si vous mettez en cache la longueur à amortir, O(n)vous avez simplement fait valoir que la longueur devrait être stockée avec la chaîne.
Billy ONeal
1
Je suis d'accord que dans le code d'aujourd'hui, ce type de chaîne est inefficace et sujet à des erreurs, mais par exemple, l'affichage de la console n'a pas vraiment besoin de connaître la longueur de la chaîne pour l'afficher efficacement, la sortie du fichier n'a pas vraiment besoin de connaître la chaîne length (allouant uniquement le cluster à la volée), et le formatage des chaînes à ce moment a été effectué sur une longueur de chaîne fixe dans la plupart des cas. Quoi qu'il en soit, vous devez écrire du mauvais code si vous concattez en C a une complexité O (n ^ 2), je suis presque sûr que je peux en écrire un en complexité O (n)
dvhh
1
@dvhh: je n'ai pas dit n ^ 2 - j'ai dit m + n - c'est toujours linéaire, mais il faut chercher à la fin de la chaîne d'origine pour faire la concaténation, alors qu'avec un préfixe de longueur pas de recherche est requis. (C'est vraiment juste une autre conséquence de la longueur nécessitant un temps linéaire)
Billy ONeal
1
@Billy ONeal: par simple curiosité, j'ai fait un grep sur mon projet C actuel (environ 50000 lignes de code) pour les appels de fonction de manipulation de chaîne. strlen 101, strcpy et variantes (strncpy, strlcpy): 85 (j'ai également plusieurs centaines de chaînes littérales utilisées pour le message, copies implicites), strcmp: 56, strcat: 13 (et 6 sont des concaténations à une chaîne de longueur nulle pour appeler strncat) . J'accepte qu'une longueur préfixée accélère les appels vers strlen, mais pas vers strcpy ou strcmp (peut-être si l'API strcmp n'utilise pas de préfixe commun). La chose la plus intéressante concernant les commentaires ci-dessus est que strcat est très rare.
kriss
1
@supercat: pas vraiment, regardez quelques implémentations. Les chaînes courtes utilisent un tampon basé sur une pile courte (pas d'allocation de tas) et n'utilisent un tas que lorsqu'elles deviennent plus grandes. Mais n'hésitez pas à fournir une implémentation réelle de votre idée en tant que bibliothèque. Habituellement, les problèmes n'apparaissent que lorsque nous arrivons aux détails, pas dans la conception globale.
kriss
9

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

Jonathan Wood
la source
Je ne vois pas ce qui est plus primitif sur les chaînes terminées par null qu'autre chose. Pascal est antérieur à C et utilise le préfixe de longueur. Bien sûr, il était limité à 256 caractères par chaîne, mais l'utilisation d'un champ de 16 bits aurait résolu le problème dans la grande majorité des cas.
Billy ONeal
Le fait qu'il limite le nombre de caractères est exactement le type de problèmes auxquels vous devez penser lorsque vous faites quelque chose comme ça. Oui, vous pourriez l'allonger, mais à l'époque, les octets importaient. Et un champ de 16 bits va-t-il être assez long pour tous les cas? Allez, vous devez admettre qu'une terminaison nulle est conceptuellement primitive.
Jonathan Wood
10
Soit vous limitez la longueur de la chaîne, soit vous limitez le contenu (pas de caractères nuls), soit vous acceptez la surcharge supplémentaire d'un nombre de 4 à 8 octets. Il n'y a pas de déjeuner gratuit. Au moment de la création, la chaîne terminée par zéro était parfaitement logique. Dans l'assemblage, j'ai parfois utilisé le bit supérieur d'un caractère pour marquer la fin d'une chaîne, économisant même un octet de plus!
Mark Ransom
Exactement, Mark: Il n'y a pas de déjeuner gratuit. C'est toujours un compromis. De nos jours, nous n'avons pas besoin de faire le même genre de compromis. Mais à l'époque, cette approche semblait aussi bonne que toute autre.
Jonathan Wood
8

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

Cristian
la source
2
Euh… non ça ne l'a pas fait. L'approche C ne permet pas du tout d'affecter la chaîne longue de 7 caractères à la chaîne longue de 3 caractères.
Billy ONeal
@Billy ONeal: pourquoi pas? Pour autant que je le comprends dans ce cas, toutes les chaînes sont du même type de données (char *), donc la longueur n'a pas d'importance. Contrairement à Pascal. Mais c'était une limitation de Pascal, plutôt qu'un problème avec les chaînes préfixées par la longueur.
Oliver Mason
4
@Billy: Je pense que vous venez de reformuler le point de Cristian. C traite ces questions en ne les traitant pas du tout. Vous pensez toujours en termes de C contenant réellement une notion de chaîne. C'est juste un pointeur, vous pouvez donc l'attribuer à tout ce que vous voulez.
Robert S Ciaccio
2
C'est comme ** la matrice: "il n'y a pas de chaîne".
Robert S Ciaccio
1
@calavera: Je ne vois pas comment cela prouve quoi que ce soit. Vous pouvez le résoudre de la même manière avec le préfixe de longueur ... c'est-à-dire ne pas autoriser l'affectation du tout.
Billy ONeal
8

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.

Pyry Jahkola
la source
Le problème est que les bibliothèques ne connaissent pas l'existence de votre structure et gèrent toujours incorrectement des choses comme les valeurs NULL incorporées. De plus, cela ne répond pas vraiment à la question que j'ai posée.
Billy ONeal
1
C'est vrai. Donc, le plus gros problème est qu'il n'y a pas de meilleur moyen standard de fournir des interfaces avec des paramètres de chaîne que les vieilles chaînes terminées par zéro. Je dirais toujours qu'il existe des bibliothèques qui prennent en charge l'alimentation par paires de pointeurs (enfin, au moins, vous pouvez construire une chaîne C ++ std :: avec elles).
Pyry Jahkola
2
Même si vous stockez une longueur, vous ne devez jamais autoriser les chaînes avec des valeurs null intégrées. C'est le bon sens de base. Si vos données peuvent contenir des valeurs nulles, vous ne devez jamais les utiliser avec des fonctions qui attendent des chaînes.
R .. GitHub STOP HELPING ICE
1
@supercat: Du point de vue de la sécurité, je saluerais cette redondance. Sinon, les programmeurs ignorants (ou privés de sommeil) finissent par concaténer des données binaires et des chaînes et les passer à des éléments qui attendent des chaînes [terminées par null] ...
R .. GitHub STOP HELPING ICE
1
@R ..: Alors que les méthodes qui attendent des chaînes terminées par null attendent généralement a char*, de nombreuses méthodes qui n'attendent pas de terminaison nulle attendent également a char*. Un avantage plus significatif de la séparation des types serait lié au comportement Unicode. Il peut être utile pour une implémentation de chaîne de conserver des indicateurs indiquant si les chaînes sont connues pour contenir certains types de caractères, ou sont connus pour ne pas les contenir. tous les personnages au-delà du plan multilingue de base seront des ordres de grandeur plus rapides ...
supercat
6

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

Brangdon
la source
Je pense avoir abordé tout cela dans la question. Oui, sur les plates-formes x64, un préfixe 32 bits ne peut pas contenir toutes les chaînes possibles. D'un autre côté, vous ne voulez jamais une chaîne aussi grosse qu'une chaîne terminée par un caractère nul, car pour faire quoi que ce soit, vous devez examiner les 4 milliards d'octets pour trouver la fin de presque toutes les opérations que vous pourriez souhaiter y faire. De plus, je ne dis pas que les chaînes terminées par null sont toujours mauvaises - si vous construisez l'une de ces structures de blocs et que votre application spécifique est accélérée par ce type de construction, allez-y. Je souhaite juste que le comportement par défaut de la langue ne le fasse pas.
Billy ONeal
2
J'ai cité cette partie de votre question parce qu'à mon avis, elle sous-estimait la question de l'efficacité. Le doublement ou le quadruplement des besoins en mémoire (sur 16 bits et 32 ​​bits respectivement) peut être un gros coût de performance. Les longues chaînes peuvent être lentes, mais au moins, elles sont prises en charge et fonctionnent toujours. Mon autre point, sur l'alignement, vous ne le mentionnez pas du tout.
Brangdon
L'alignement peut être traité en spécifiant que les valeurs au-delà de UCHAR_MAX doivent se comporter comme si elles étaient compressées et décompressées en utilisant des accès d'octets et un décalage de bits. Un type de chaîne convenablement conçu pourrait offrir une efficacité de stockage essentiellement comparable aux chaînes terminées par zéro, tout en permettant également la vérification des limites sur les tampons sans surcharge de mémoire supplémentaire (utilisez un bit dans le préfixe pour dire si un tampon est "plein"; s'il n'est pas et le dernier octet est différent de zéro, cet octet représenterait l'espace restant. Si le tampon n'est pas plein et le dernier octet est nul, alors les 256 derniers octets seraient inutilisés, donc ...
supercat
... on pourrait stocker dans cet espace le nombre exact d'octets inutilisés, sans aucun coût supplémentaire en mémoire). Le coût de travail avec les préfixes serait compensé par la possibilité d'utiliser des méthodes comme fgets () sans avoir à passer la longueur de la chaîne (car les tampons sauraient leur taille).
supercat
4

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

Sanjit Saluja
la source
5
Hein? Quelles «opérations de pointeur rapide» ne fonctionnent pas avec le préfixe de longueur? Plus important encore, d'autres langages qui utilisent le préfixe de longueur sont plus rapides que la manipulation de chaînes C wrt.
Billy ONeal
12
@billy: Avec les chaînes préfixées par la longueur, vous ne pouvez pas simplement prendre un pointeur de chaîne et y ajouter 4, et vous attendre à ce qu'il soit toujours une chaîne valide, car il n'a pas de préfixe de longueur (pas valide de toute façon).
Jörgen Sigvardsson
3
@j_random_hacker: la concaténation est bien pire pour les chaînes d'asciiz (O (m + n) au lieu de potentiellement O (n)), et la concaténation est beaucoup plus courante que toutes les autres opérations répertoriées ici.
Billy ONeal du
3
il y a une opération peu tiiny qui devient plus cher avec des chaînes terminées par null: strlen. Je dirais que c'est un peu un inconvénient.
2010
10
@Billy ONeal: tout le monde prend également en charge l'expression régulière. Et alors ? Utilisez des bibliothèques pour lesquelles elles sont conçues. C concerne l'efficacité maximale et le minimalisme, pas les piles incluses. Les outils C vous permettent également d'implémenter très facilement des chaînes de longueur préfixées à l'aide de structures. Et rien ne vous interdit d'implémenter les programmes de manipulation de chaînes en gérant vos propres tampons de longueur et de caractères. C'est généralement ce que je fais quand je veux de l'efficacité et que j'utilise C, ne pas appeler une poignée de fonctions qui s'attendent à un zéro à la fin d'un tampon de caractères n'est pas un problème.
Kriss
4

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.

supercat
la source
Le préfixe pourrait facilement être de taille définie par l'implémentation, tel quel sizeof(char).
Billy ONeal
@BillyONeal: en sizeof(char)est un. Toujours. On pourrait avoir le préfixe d'une taille définie par l'implémentation, mais ce serait gênant. De plus, il n'y a aucun moyen réel de savoir quelle devrait être la "bonne" taille. Si l'on détient beaucoup de chaînes de 4 caractères, le remplissage nul imposerait 25% de surcharge, tandis qu'un préfixe de longueur de quatre octets imposerait 100% de surcharge. En outre, le temps passé à empaqueter et à déballer les préfixes de longueur de quatre octets pourrait dépasser le coût de l'analyse des chaînes de 4 octets pour l'octet zéro.
supercat
1
Ah oui. Vous avez raison. Cependant, le préfixe pourrait facilement être autre chose que char. Tout ce qui ferait fonctionner les exigences d'alignement sur la plate-forme cible serait bien. Je ne vais pas y aller cependant - je l'ai déjà soutenu à mort.
Billy ONeal
En supposant que les chaînes avaient un préfixe de longueur, la chose la plus saine à faire serait probablement un size_tpréfixe (le gaspillage de mémoire soit damné, ce serait le plus sain --- autoriser des chaînes de toute longueur possible qui pourraient éventuellement tenir en mémoire). En fait, c'est un peu ce que fait D; les tableaux le sont struct { size_t length; T* ptr; }et les chaînes ne sont que des tableaux de immutable(char).
Tim Čas
@ TimČas: à moins que les chaînes soient obligatoirement alignées sur des mots, le coût du travail avec des chaînes courtes serait dominé sur de nombreuses plates-formes par l'exigence d'emballer et de déballer la longueur; Je ne pense vraiment pas que ce soit pratique. Si l'on veut que les chaînes soient des tableaux d'octets de taille arbitraire indépendants du contenu, je pense qu'il serait préférable de garder la longueur séparée du pointeur vers les données de caractère et d'avoir un langage permettant d'obtenir les deux informations pour une chaîne littérale. .
supercat
2

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.

supercat
la source
Il n'y a rien qui aurait empêché char* arrde pointer vers une structure du formulaire struct { int length; char characters[ANYSIZE_ARRAY] };ou similaire qui serait toujours passable en tant que paramètre unique.
Billy ONeal
@BillyONeal: Deux problèmes avec cette approche: (1) Elle ne permettrait que de passer la chaîne dans son ensemble, tandis que l'approche actuelle permet également de passer la queue d'une chaîne; (2) il perdra beaucoup d'espace lorsqu'il est utilisé avec de petites cordes. Si K&R avait voulu passer du temps sur les cordes, il aurait pu rendre les choses beaucoup plus robustes, mais je ne pense pas qu'ils voulaient que leur nouveau langage soit utilisé dix ans plus tard, et encore moins quarante.
supercat
1
Ce morceau sur la convention d'appel est une histoire juste sans rapport avec la réalité ... ce n'était pas une considération dans la conception. Et les conventions d'appel basées sur des registres avaient déjà été "inventées". De plus, des approches telles que deux pointeurs n'étaient pas une option car les structures n'étaient pas de première classe ... seules les primitives étaient assignables ou passables; la copie de structure n'est arrivée qu'UNIX V7. Besoin de memcpy (qui n'existait pas non plus) juste pour copier un pointeur de chaîne est une blague. Essayez d'écrire un programme complet, pas seulement des fonctions isolées, si vous faites semblant de concevoir un langage.
Jim Balter
1
"c'est probablement parce qu'ils ne voulaient pas consacrer beaucoup d'efforts à la gestion des chaînes" - un non-sens; le domaine d'application entier des premiers UNIX était la gestion des chaînes. Sans cela, nous n'en aurions jamais entendu parler.
Jim Balter
1
'Je ne pense pas que "le tampon de caractères commence par un entier contenant la longueur" soit plus magique' - c'est si vous voulez faire str[n]référence au bon caractère. Voilà le genre de choses auxquelles les gens qui discutent ne pensent pas .
Jim Balter
2

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.

BenK
la source
2
Ecoute, je respecte Joel pour beaucoup de choses; mais c'est quelque chose où il spécule. La réponse de Hans Passant vient directement des inventeurs de C.
Billy ONeal
1
Oui, mais si ce que dit Spolsky est vrai, cela aurait fait partie de la "commodité" à laquelle ils faisaient référence. C'est en partie pourquoi j'ai inclus cette réponse.
BenK
AFAIK .ASCIZétait juste une instruction d'assembleur pour construire une séquence d'octets, suivie de 0. Cela signifie simplement que la chaîne terminée par zéro était un concept bien établi à l'époque. Cela ne signifie pas que les chaînes terminées par zéro étaient liées à l'architecture d'un PDP- *, sauf que vous pouviez écrire des boucles serrées constituées de MOVB(copier un octet) et BNE(branche si le dernier octet copié n'était pas zéro).
Adrian W
Cela suppose de montrer que C est un langage ancien, flasque et décrépit.
purec
2

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.

Noir
la source
9 était un peu hors-base / mal représenté. Le préfixe de longueur n'a pas ce problème. Lenth passe comme une variable séparée. Nous parlions de pré-fiix mais je me suis emporté. C'est toujours une bonne chose à penser, alors je vais le laisser là. : d
Black
1

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.

Mr. Boy
la source
-3

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

kkaaii
la source
@Adrian W. Ceci est valide. Les chaînes de longueur exacte ont un boîtier spécial et NUL est omis pour elles. C'est généralement une pratique imprudente mais peut être utile dans des cas comme le remplissage de structures d'en-tête qui utilisent des "chaînes" FourCC.
Kevin Thibedeau
Vous avez raison. Ceci est un C valide, se compilera et se comportera comme décrit par kkaaii. La raison des downvotes (pas la mienne ...) est probablement plutôt que cette réponse ne répond en rien à la question d'OP.
Adrian W