Ce qui ' s la raison d’être pour les chaînes null résiliées ?

Question

Autant que j'aime le C et le C++, je ne peux pas m'empêcher de gratter ma tête sur le choix de la valeur null chaînes:

• Longueur de préfixe (c, Pascal) les chaînes de caractères existait avant C
• Longueur de préfixe de chaînes de faire plusieurs algorithmes plus rapides en permettant constante longueur de temps de recherche.
• Longueur de préfixe de chaînes de rendre plus difficile pour cause de dépassement de mémoire tampon d'erreurs.
• Même sur un ordinateur 32 bits, si vous laissez la chaîne à la taille de la mémoire disponible, une longueur de préfixe de la chaîne est à seulement trois octets plus large qu'une chaîne terminée par null. Sur 16 bits machines c'est un seul octet. Sur 64 bits machines, de 4 go est raisonnable chaîne de limite de longueur, mais même si vous voulez l'étendre à la taille de la machine word, 64 bits machines ont généralement beaucoup de mémoire en faisant l'appoint sept octets de tri d'un argument null. Je sais que l'original C standard a été écrit pour incroyablement machines pauvres (en termes de mémoire), mais l'efficacité d'un tel argument ne vend pas de moi ici.
• Presque tous les autres langue (c'est à dire Perl, Pascal, Python, Java, C#, etc) utiliser la longueur de préfixe de chaînes. Ces langues battre C de manipulation de chaîne de repères parce qu'ils sont plus efficaces avec des chaînes.
• C++ corrigé ce un peu avec l' std::basic_string modèle, mais de la plaine des tableaux de caractères attend les chaînes vides sont encore omniprésents. C'est aussi imparfaite, car elle nécessite l'allocation de tas.
• Null chaînes ont pour réserver un personnage (à savoir, null), qui ne peut exister dans la chaîne, tandis que la longueur de préfixe de chaînes de caractères peuvent contenir des valeurs null incorporées.

Plusieurs de ces choses sont venus à la lumière, plus récemment, de C, de sorte qu'il serait judicieux pour les C de ne pas avoir connu d'entre eux. Cependant, plusieurs ont été clair bien avant C est venu pour être. Pourquoi les chaînes vides ont été choisi à la place de l', bien sûr, supérieure longueur de préfixe?

EDIT: Depuis que certains ont demandé des faits (et n'aime pas ceux que j'ai déjà fourni) sur mon point de rendement ci-dessus, il résulte que peu de choses:

• Concat à l'aide null chaînes nécessite O(n + m) temps de complexité. Longueur de préfixe ne requièrent souvent que O(m).
• Longueur à l'aide d'une valeur null chaînes nécessite O(n) le temps de la complexité. Longueur de préfixe est O(1).
• La longueur et la concat sont de loin les plus fréquentes opérations de la chaîne. Il y a plusieurs cas où la valeur null chaînes de caractères peuvent être plus efficaces, mais ils se produisent moins souvent.

À partir des réponses données ci-dessous, ce sont des cas où les chaînes vides sont plus efficaces:

• Lorsque vous avez besoin de couper le début d'une chaîne et de la nécessité de passer à une méthode. Vous ne pouvez pas vraiment faire en temps constant avec la longueur de préfixe, même si vous êtes autorisé à détruire la chaîne d'origine, parce que le préfixe de longueur a probablement besoin de suivre l'alignement des règles.
• Dans certains cas où vous êtes juste une boucle dans la chaîne de caractère par caractère, vous pourriez être en mesure d'enregistrer un PROCESSEUR inscrire. Notez que cela ne fonctionne que dans le cas que vous n'avez pas alloué dynamiquement la chaîne (Car alors vous auriez à le libérer, nécessitant de l'aide que le PROCESSEUR inscrire vous avez enregistré à l'maintenez le pointeur d'origine que vous avez obtenu à partir de malloc et amis).

Aucun des ci-dessus sont presque aussi commune que la longueur et la concat.

Il y a une plus affirmée dans les réponses ci-dessous:

• Vous avez besoin de couper la fin de la chaîne

mais celui-ci est incorrect, c'est la même quantité de temps pour valeur null et la longueur de préfixe de chaînes. (Null chaînes de caractères bâton null où vous souhaitez que la nouvelle fin, longueur prefixers juste soustraire à partir du préfixe.)

Answer 1

De la bouche des chevaux:

Aucun de BCPL, B, ou C prend en charge les données de caractère fortement dans le langue; chaque traite les chaînes de beaucoup comme les vecteurs d'entiers et les suppléments de règles générales par quelques les conventions. Dans les deux BCPL et B un un littéral de chaîne indique l'adresse de une zone statique initialisée avec la caractères de la chaîne, emballé dans les cellules. En BCPL, le premier octet emballé contient le nombre de caractères dans la chaîne; en B, il n'est aucun compte et les chaînes de caractères terminées par un caractère spécial, qui B orthographié *e. Ce changement a été fait partiellement pour éviter la limitation sur la longueur d'une chaîne provoquée par la tenue de la le comte de 8 ou 9 bits emplacement, et en partie parce que le maintien de la comte semble, dans notre expérience, moins pratique que d'utiliser un terminator.

Answer 2

C ne dispose pas d'une chaîne de caractères comme une partie de la langue. Une "chaîne" C est juste un pointeur vers char. Alors peut-être vous vous posez la mauvaise question.

"Quelle est la justification pour quitter une chaîne de type" pourrait être plus pertinent. À qui je tiens à souligner que C est pas un langage orienté objet et uniquement a base de types de valeur. Une chaîne est un niveau plus élevé concept qui doit être mise en oeuvre, d'une certaine façon en combinant les valeurs d'autres types. C est à un plus bas niveau d'abstraction.

à la lumière de la violence de la bourrasque ci-dessous:

Je tiens juste à signaler que je ne suis pas en train de dire que c'est un de stupide ou de mauvaise question, ou que le C mode de représentation des chaînes de caractères est le meilleur choix. Je suis en train de préciser que la question serait plus le mettre succinctement, si vous prenez en compte le fait que le C n'a pas de mécanisme permettant de différencier une chaîne de caractères comme un type de données à partir d'un tableau d'octets. Est-ce le meilleur choix à la lumière de la transformation et de la mémoire de la puissance actuelle des ordinateurs? Probablement pas. Mais le recul est toujours 20/20 et tout ça :)

Answer 3

La question est posée en tant que Length Prefixed Strings (LPS) vs zero terminated strings (SZ) chose, mais surtout d'exposer les avantages de la longueur de préfixe de chaînes. Qui peut sembler écrasante, mais pour être honnête, nous devrions également considérer les inconvénients de la LPS et les avantages de SZ.

Si je comprends bien, la question peut même être comprise comme une façon biaisée de se demander "quels sont les avantages de Zéro Chaînes terminées ?".

Avantages (je vois) de Zéro Chaînes terminées:

• très simple, pas besoin d'introduire de nouveaux concepts dans la langue, le char les tableaux/pointeurs de char peut faire.
• le langage de base suffit d'inclure minimale sucre syntaxique pour convertir quelque chose entre guillemets pour une tas de caractères (vraiment un tas de octets). Dans certains cas, il peut être utilisé pour initialiser des choses complètement sans rapport avec le texte. Par exemple xpm format de fichier d'image est valide source C qui contient les données d'image codées comme une chaîne de caractères.
• par la manière, vous pouvez mettre un zéro dans une chaîne littérale, le compilateur va juste aussi en ajouter un autre à la fin de la lettre: "this\0is\0valid\0C". C'est une chaîne de caractères ? ou quatre cordes ? Ou un tas d'octets...
• plat de mise en œuvre, pas caché indirection, pas caché entier.
• pas de mémoire cachée de l'allocation en cause (bien, certains infâme non les fonctions standard comme strdup effectuer l'allocation, mais c'est surtout une source de problème).
• pas de problème spécifique pour les petits ou gros matériel (imaginez la charge de gérer les 32 bits de préfixe de longueur sur 8 bits microcontrôleurs, ou la restrictions de limiter la taille de la chaîne à moins de 256 octets, qui a été un problème en fait j'ai eu avec Turbo Pascal il y a des éons).
• la mise en œuvre de manipulation de chaîne est juste une poignée de très simple fonction de bibliothèque
• efficace pour l'utilisation principale de cordes : constante de lire le texte de manière séquentielle à partir d'une start (la plupart des messages de l'utilisateur).
• la terminaison zéro est même pas obligatoire, tous les outils nécessaires pour manipuler des caractères comme un tas de les octets sont disponibles. Lors de l'exécution de tableau d'initialisation en C, vous pouvez même à éviter le NUL de terminaison. Juste définir la bonne taille. char a[3] = "foo"; est valide en C (pas C++) et ne pas mettre un zéro final dans un.
• cohérente avec les unix point de vue "tout est fichier", y compris "fichiers" qui n'ont pas intrinsèque de la longueur comme stdin, stdout. Vous devez vous rappeler que ouvrir lire et à écrire primitives sont mis en œuvre à un niveau très faible. Ils ne sont pas les appels à la bibliothèque, mais les appels système. Et de la même API est utilisée pour les fichiers binaires ou du texte. La lecture du fichier de primitives obtenir une adresse de mémoire tampon et d'une taille et retour la nouvelle taille. Et vous pouvez utiliser les chaînes de caractères comme la mémoire tampon d'écriture. En utilisant un autre type de chaîne la représentation implique que vous ne pouvez pas utiliser facilement une chaîne littérale comme le tampon de sortie, ou vous devez rendre un très étrange comportement lors de moulage char*. À savoir ne pas retourner l'adresse de la chaîne, mais au lieu de retourner les données réelles.
• très facile à manipuler du texte de lecture de données à partir d'un fichier en place, sans d'inutiles copie de la mémoire tampon, il suffit d'insérer des zéros à la bonne place (enfin, pas vraiment moderne, C que les chaînes entre guillemets doubles sont des tableaux de char const aujourd'hui généralement conservés dans non modifiables segment de données).
• ajoutant des int les valeurs quelle que soit la taille implique des problèmes d'alignement. La première la longueur doit être aligné, mais il n'y a pas de raison de le faire pour les caractères de données (et encore une fois, forcer l'alignement des chaînes impliquerait des problèmes lors de le traiter comme un tas de octets).
• la longueur est connue au moment de la compilation pour les constantes chaînes de caractères littérales (sizeof). Alors, pourquoi voudrais - quelqu'un veut-il de le stocker dans la mémoire ajoutant aux données réelles ?
• dans un sens C est de faire comme (presque) tout le monde, les chaînes sont considérées comme des tableaux de char. Comme la longueur du tableau n'est pas géré par C, il est logique que la longueur n'est pas géré soit pour les chaînes. La seule chose surprenante est que 0 élément ajouté à la fin, mais c'est juste à la base du niveau de langue lors de la saisie d'une chaîne de caractères entre guillemets doubles. Les utilisateurs peuvent parfaitement d'appel de fonctions de manipulation de chaîne passant longueur, ou même l'utilisation de la plaine memcopy à la place. SZ sont juste un établissement. Dans la plupart des autres langues longueur du tableau est réussi, c'est de la logique qui est la même pour les chaînes.
• dans les temps modernes, de toute façon 1 octet jeux de caractères ne sont pas assez et vous avez souvent affaire avec des chaînes de caractères unicode codés où le nombre de caractères est très différent du nombre d'octets. Il implique que les utilisateurs voudront probablement plus que "la taille", mais aussi d'autres informations. En gardant la longueur de donner de rien (surtout pas d'endroit pour les stocker) au sujet de ces autres éléments d'information utiles.

Cela dit, pas besoin de se plaindre dans les rares cas où la norme C les chaînes de caractères sont en effet inefficace. Libs sont disponibles. Si j'ai suivi cette tendance, je devrais me plaindre que C standard ne comprennent pas les regex fonctions de soutien... mais vraiment tout le monde sait que c'est pas un réel problème, car il est de bibliothèques disponibles à cette fin. Ainsi, lorsque la manipulation de la chaîne de l'efficacité est voulu, pourquoi ne pas utiliser une bibliothèque comme bstring ? Ou même les chaînes C++?

EDIT: j'ai récemment eu un coup d'oeil à D cordes. Il est assez intéressant de voir que la solution choisie n'est ni une taille préfixe, ni nulle la résiliation. Comme en C, les chaînes littérales sont entre guillemets sont juste à court de main pour immuable des tableaux de char, et la langue aussi est un mot clé de chaîne de sens que (immuable char array).

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

Sur normal des tableaux de char ou non des chaînes de caractères littérales il n'y a pas de finale de zéro, d'où le programmeur doit mettre lui-même s'il veut appeler quelques-fonction C de D. Dans le cas particulier des chaînes littérales, cependant le D compilateur toujours mettre un zéro à la fin de chaque chaîne de caractères (pour faciliter la fonte de chaînes C, afin de faciliter l'appel de fonction C ?), mais ce nul n'est pas une partie de la chaîne D ne compte pas dans la chaîne de taille).

La seule chose qui m'a déçu un peu, c'est que les chaînes sont censés être en utf-8, mais la longueur apparemment renvoie toujours un nombre d'octets (au moins, il est vrai, sur mon compilateur gdc), même lors de l'utilisation de multi-octets caractères. Il est clair pour moi si c'est un bug du compilateur ou de l'en but. (OK, j'ai probablement trouvé ce qui s'est passé. Dire D compilateur de votre source utiliser l'utf-8, vous devez mettre un peu stupide marque d'ordre des octets au début. J'écris stupide parce que je ne connais pas l'éditeur de le faire, en particulier pour l'UTF-8, ce qui est censé être compatible ASCII).

Answer 4

Je pense, il a des raisons historiques et trouvé ceci sur wikipedia:

Au moment de C (et les langues il a été dérivé) ont été développés, la mémoire a été extrêmement limitée, à l'aide de un seul octet de surcharge pour stocker les la longueur d'une chaîne est intéressante. L' seule alternative populaire à l'époque, habituellement appelé une "chaîne Pascal" (mais aussi utilisé par les premières versions de De BASE), utilisé l'un des principaux octet pour stocker la longueur de la chaîne. Cela permet la chaîne de contenir NUL et fait trouver la longueur de besoin d'un seul l'accès à la mémoire (O(1) (constante de temps). Mais un octet permet de limiter la longueur de 255. Cette limitation de longueur a été beaucoup plus restrictives que les problèmes avec les Chaîne C, de sorte que la chaîne C en général qui a gagné.

Answer 5

Calavera est droit, mais comme les gens ne semblent pas à obtenir son point de vue, je vais vous donner quelques exemples de code.

Tout d'abord, considérons ce que C est: un langage simple, où tout le code a une jolie traduction directe en langage machine. Tous les types d'ajustement dans les registres et sur la pile, et il ne nécessite pas un système d'exploitation ou une grande bibliothèque run-time à exécuter, car il était destiné à écrire ces choses (une tâche à laquelle est superbement bien adaptée, considérant qu'il ya n'est même pas un probable concurrent à ce jour).

Si C avait une string le type, comme int ou char, ce serait un type qui n'entrent pas dans un registre ou dans la pile, et aurait besoin d'allocation de mémoire (avec l'ensemble de son infrastructure d'appui) pour être manipulé en toute manière. Tous aller à l'encontre des principes de base de la C.

Ainsi, une chaîne de caractères en C est:

char s*;

Ainsi, supposons ensuite que c'était la longueur de préfixe. Nous allons écrire le code pour concaténer deux chaînes de caractères:

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 de caractères:

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

À ce stade, toute manipulation de chaîne aurait besoin de deux allocations, ce qui, en pratique, signifie que vous alliez grâce à une bibliothèque pour faire la manipulation.

Le plus drôle, c'est... des structures comme ça n' existe pas en C! Ils sont tout simplement pas utilisé pour votre journée-à-jour de l'affichage des messages à l'utilisateur de manutention.

Donc, ici, est le point de Calavera est prise: il n'y a pas de type chaîne de caractères en C. Faire quelque chose avec elle, vous avez à prendre d'un pointeur et le décoder comme un pointeur vers deux types différents, et il devient alors très pertinent ce qui est de la taille d'une chaîne de caractères, et ne peut pas être de gauche "la mise en œuvre définies".

Maintenant, C peut gérer la mémoire de toutes les façons, et l' mem fonctions dans la bibliothèque (en <string.h>, même!) fournir tous les outils vous avez besoin pour gérer la mémoire comme une paire de pointeur et de la taille. Le soi-disant "strings" dans C ont été créés pour un seul objectif: affichage des messages dans le contexte de l'écriture d'un système d'exploitation conçu pour les terminaux texte. Et, pour cela, de fin null est assez.