Warum nullterminierte Strings? Oder: nullterminiert vs. Zeichen + Längenspeicherung

Lesezeit: 9 Minuten

Benutzeravatar von Imagist
Imagist

Ich schreibe einen Sprachdolmetscher in C und meine string Typ enthält a length Attribut, etwa so:

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

Aus diesem Grund muss ich viel Zeit in meinem Interpreter verbringen, um diese Art von Zeichenfolge manuell zu handhaben, da C keine integrierte Unterstützung dafür enthält. Ich habe überlegt, zu einfachen nullterminierten Strings zu wechseln, nur um dem zugrunde liegenden C zu entsprechen, aber es scheint viele Gründe zu geben, dies nicht zu tun:

Die Überprüfung von Grenzen ist integriert, wenn Sie “Länge” verwenden, anstatt nach einer Null zu suchen.

Sie müssen die gesamte Zeichenfolge durchlaufen, um ihre Länge zu ermitteln.

Sie müssen zusätzliche Dinge tun, um ein Nullzeichen in der Mitte einer nullterminierten Zeichenfolge zu verarbeiten.

Null-terminierte Zeichenfolgen kommen mit Unicode schlecht zurecht.

Nicht nullterminierte Strings können mehr intern, dh die Zeichen für „Hallo, Welt“ und „Hallo“ können an derselben Stelle gespeichert werden, nur mit unterschiedlicher Länge. Dies ist mit nullterminierten Strings nicht möglich.

String-Slice (Hinweis: Strings sind in meiner Sprache unveränderlich). Offensichtlich ist die zweite langsamer (und fehleranfälliger: Denken Sie darüber nach, eine Fehlerprüfung von hinzuzufügen begin und end zu beiden Funktionen).

struct String slice(struct String in, size_t begin, size_t end)
{
    struct String out;
    out.characters = in.characters + begin;
    out.length = end - begin;

    return out;
}

char* slice(char* in, size_t begin, size_t end)
{
    char* out = malloc(end - begin + 1);

    for(int i = 0; i < end - begin; i++)
        out[i] = in[i + begin];

    out[end - begin] = '\0';

    return out;
}

Nach all dem denke ich nicht mehr darüber nach, ob ich nullterminierte Strings verwenden sollte: Ich denke darüber nach, warum C sie verwendet!

Meine Frage ist also: Gibt es irgendwelche Vorteile der Nullterminierung, die ich vermisse?

  • Da malloc() in C so teuer ist, schlage ich vor, diese Struktur zu verwenden: struct String { size_t length; verkohlen[1] Figuren; } Weisen Sie einfach strlen(s)+1+sizeof(size_t) oder strlen(s)+sizeof(String) Bytes zu und kopieren Sie den String an die Adresse &characters.

    – Aaron Digulla

    10. August 2009 um 8:07 Uhr

  • Es ist einfach. Das ist der Vorteil.

    – Mike Dunlavey

    23. Oktober 2016 um 13:46 Uhr

Von Joels Zurück zum Wesentlichen:

Warum funktionieren C-Saiten so? Das liegt daran, dass der PDP-7-Mikroprozessor, auf dem UNIX und die Programmiersprache C erfunden wurden, einen ASCIZ-String-Typ hatte. ASCIZ bedeutete „ASCII mit einem Z (Null) am Ende“.

Ist dies die einzige Möglichkeit, Zeichenfolgen zu speichern? Nein, tatsächlich ist es eine der schlechtesten Möglichkeiten, Saiten zu speichern. Bei nicht-trivialen Programmen, APIs, Betriebssystemen, Klassenbibliotheken sollten Sie ASCIZ-Strings wie die Pest vermeiden.

  • Die Meinung von Denis Ritchie ist etwas anders. BCPL hatte eine Länge + Inhaltsdarstellung, wobei die Länge in einem Byte enthalten war. B wechselte zu einer abgeschlossenen Zeichenfolge, “teilweise um die Begrenzung der Länge einer Zeichenfolge zu vermeiden, die durch das Halten der Zählung in einem 8- oder 9-Bit-Slot verursacht wird, und teilweise, weil das Beibehalten der Zählung unserer Erfahrung nach weniger bequem erschien als die Verwendung eines Abschlusszeichens.” (Die Entwicklung der Sprache C, cm.bell-labs.com/cm/cs/who/dmr/chist.pdf)

    – Ein Programmierer

    10. August 2009 um 6:40 Uhr

Die übliche Lösung besteht darin, beides zu tun – die Länge beizubehalten und den Nullterminator beizubehalten. Es ist nicht viel zusätzliche Arbeit und bedeutet, dass Sie den String jederzeit an eine beliebige Funktion übergeben können.

Null-terminierte Zeichenfolgen beeinträchtigen häufig die Leistung, aus dem offensichtlichen Grund, dass die Zeit, die zum Ermitteln der Länge benötigt wird, von der Länge abhängt. Auf der positiven Seite sind sie die Standardmethode zur Darstellung von Zeichenfolgen in C, sodass Sie kaum eine andere Wahl haben, als sie zu unterstützen, wenn Sie die meisten C-Bibliotheken verwenden möchten.

  • Das macht Lua. Es macht die Schnittstelle zu C für normale Anwendungsfälle sehr sauber und unterstützt immer noch binäre Puffer beliebiger Länge.

    – RBerteig

    10. August 2009 um 6:36 Uhr

  • Es ist, was die meisten Dinge tun! Sie müssen nicht einmal ständig den Null-Terminator beibehalten – tun Sie es einfach str[len] = '\0' wann immer Sie es brauchen. Das macht `std::string::c_str“ normalerweise in C++.

    – Daniel Earwicker

    10. August 2009 um 6:40 Uhr

  • Mit den meisten Dingen meine ich die meisten String-Klassen und die meisten Interpreter-String-Darstellungen. Ein weit verbreitetes Beispiel unter Windows ist der Typ BSTR.

    – Daniel Earwicker

    10. August 2009 um 6:41 Uhr

  • Genau aus diesem Grund habe ich diese Frage gestellt; Ich dachte, ich könnte eine Lösung vermissen. Es scheint jetzt offensichtlich, aber ich habe nicht daran gedacht!

    – Imagist

    10. August 2009 um 7:29 Uhr

  • Kühl! Siehst du das grüne Häkchen neben meiner Antwort…?

    – Daniel Earwicker

    10. August 2009 um 7:34 Uhr

Ein Vorteil nullterminierter Strings besteht darin, dass Sie, wenn Sie Zeichen für Zeichen durch einen String gehen, nur einen einzigen Zeiger behalten müssen, um den String zu adressieren:

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

während Sie für Zeichenfolgen ohne Sentinels zwei Zustandsbits beibehalten müssen: entweder einen Zeiger und einen Index:

while (i < s.length)
{
    s.data[i] = toupper(s.data[i]);
    i++;
}

…oder ein aktueller Zeiger und ein Grenzwert:

s_end = s + length;
while (s < s_end)
{
    *s = toupper(*s);
    s++;
}

Als CPU-Register eine knappe Ressource waren (und Compiler sie schlechter zuordnen konnten), war dies wichtig. Nun, nicht so sehr.

  • “Als CPU-Register eine knappe Ressource waren” – Register sind immer noch eine knappe Ressource auf x86 und x64.

    – Jimmy

    10. August 2009 um 6:49 Uhr

  • Ich verstehe es nicht; wenn ich string in der speichere struct Beispiel, das ich gegeben habe, warum kann ich das nicht als Grenze verwenden?

    – Imagist

    10. August 2009 um 7:56 Uhr

  • Der Punkt ist, dass während einer Verarbeitungsschleife wie der obigen längenbasierte Zeichenfolgen wie Ihre zwei Register für die Zeichenfolgenbuchhaltung verwenden, während überwachungsbasierte Zeichenfolgen wie idiomatische C-Zeichenfolgen nur eines verwenden (das andere wird “kostenlos” erhalten). weil die Zeichenwerte geladen werden, um sie trotzdem zu verarbeiten).

    – Café

    10. August 2009 um 9:03 Uhr

Benutzeravatar von Jason Williams
Jason Williams

Längen haben auch ihre Probleme.

  • Die Länge nimmt zusätzlichen Speicherplatz in Anspruch (heute kein solches Problem, aber vor 30 Jahren ein großer Faktor).

  • Jedes Mal, wenn Sie eine Saite ändern, müssen Sie die Länge aktualisieren, sodass Sie auf der ganzen Linie eine reduzierte Leistung erhalten.

  • Bei einer NUL-terminierten Zeichenfolge können Sie immer noch eine Länge verwenden oder einen Zeiger auf das letzte Zeichen speichern. Wenn Sie also viele Zeichenfolgen manipulieren, können Sie immer noch die Leistung von Zeichenfolge-mit-Länge erreichen.

  • NUL-terminierte Zeichenfolgen sind viel einfacher – Der NUL-Terminator ist nur eine Konvention, die von Methoden wie verwendet wird strcat um das Ende der Zeichenfolge zu bestimmen. Sie können sie also in einem regulären char-Array speichern, anstatt eine Struktur verwenden zu müssen.

Ein Vorteil besteht darin, dass bei der Nullterminierung jedes Ende einer nullterminierten Zeichenfolge auch eine nullterminierte Zeichenfolge ist. Wenn Sie eine Teilzeichenfolge, die mit dem N-ten Zeichen beginnt (vorausgesetzt, es gibt keinen Pufferüberlauf), an eine Zeichenfolgenbehandlungsfunktion übergeben müssen – kein Problem, übergeben Sie einfach die versetzte Adresse dorthin. Wenn Sie die Größe auf andere Weise speichern, müssen Sie eine neue Zeichenfolge erstellen.

  • Können Sie ein Beispiel für eine Zeichenfolge geben, bei der Sie möglicherweise das Ende der Zeichenfolge drucken möchten?

    – weiqure

    10. August 2009 um 6:12 Uhr

  • Dies kann beim Verketten von Zeichenfolgen verwendet werden – Sie möchten möglicherweise nicht die gesamte Zeichenfolge anhängen, sondern nur das Ende davon. Dann rufst du strcat( target, source + offset); – und fertig.

    – scharfer Zahn

    10. August 2009 um 6:16 Uhr

  • Nehmen Sie einen vorderen Rand des weißen Raums. Sie können das erste Nicht-Leerzeichen bestimmen und anstatt die Zeichenfolge tatsächlich zu ändern, können Sie einfach den Start-Offset übergeben, wodurch Sie entweder neuen Speicher zuweisen oder Daten kopieren müssen.

    – Dan McGrath

    10. August 2009 um 6:17 Uhr

  • Das ist nicht allzu anders für das, was ich mit meiner Struktur mache: struct String new; new.characters = old.characters + offset; new.length = old.length - offset; Es ist ein bisschen Buchhaltung, aber was kommt heraus, 5 Anweisungen? Dies erscheint trivial im Vergleich zu dem Unterschied, wenn Sie etwas am Anfang der Zeichenfolge statt am Ende tun müssten.

    – Imagist

    10. August 2009 um 8:02 Uhr

  • Es macht es wirklich einfach, Dinge wie rekursive Zeichenfolgenübereinstimmung, Rechtschreibkorrektur usw. zu tun, wenn Sie die Zeichenfolge wie eine Liste in Lisp behandeln können.

    – Mike Dunlavey

    13. August 2009 um 0:57 Uhr

Benutzeravatar von Nick Johnson
Nick Johnson

Etwas offtopic, aber es gibt eine effizientere Möglichkeit, Zeichenfolgen mit Längenpräfixen zu erstellen, als die von Ihnen beschriebene. Erstellen Sie eine Struktur wie diese (gültig in C99 und höher):

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

Dadurch wird eine Struktur erstellt, die am Anfang die Länge hat, wobei das Element „Zeichen“ als Zeichen* verwendet werden kann, genau wie bei Ihrer aktuellen Struktur. Der Unterschied besteht jedoch darin, dass Sie für jede Zeichenfolge nur ein einziges Element auf dem Heap statt zwei zuweisen können. Weisen Sie Ihre Zeichenfolgen wie folgt zu:

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

ZB – die Länge der Struktur (die nur size_t ist) plus genügend Platz, um die eigentliche Zeichenfolge dahinter zu setzen.

Wenn Sie C99 nicht verwenden möchten, können Sie dies auch mit “char-Zeichen” tun[1]” und subtrahieren Sie 1 von der Länge der zuzuweisenden Zeichenfolge.

  • Können Sie ein Beispiel für eine Zeichenfolge geben, bei der Sie möglicherweise das Ende der Zeichenfolge drucken möchten?

    – weiqure

    10. August 2009 um 6:12 Uhr

  • Dies kann beim Verketten von Zeichenfolgen verwendet werden – Sie möchten möglicherweise nicht die gesamte Zeichenfolge anhängen, sondern nur das Ende davon. Dann rufst du strcat( target, source + offset); – und fertig.

    – scharfer Zahn

    10. August 2009 um 6:16 Uhr

  • Nehmen Sie einen vorderen Rand des weißen Raums. Sie können das erste Nicht-Leerzeichen bestimmen und anstatt die Zeichenfolge tatsächlich zu ändern, können Sie einfach den Start-Offset übergeben, wodurch Sie entweder neuen Speicher zuweisen oder Daten kopieren müssen.

    – Dan McGrath

    10. August 2009 um 6:17 Uhr

  • Das ist nicht allzu anders für das, was ich mit meiner Struktur mache: struct String new; new.characters = old.characters + offset; new.length = old.length - offset; Es ist ein bisschen Buchhaltung, aber was kommt heraus, 5 Anweisungen? Dies erscheint trivial im Vergleich zu dem Unterschied, wenn Sie etwas am Anfang der Zeichenfolge statt am Ende tun müssten.

    – Imagist

    10. August 2009 um 8:02 Uhr

  • Es macht es wirklich einfach, Dinge wie rekursive Zeichenfolgenübereinstimmung, Rechtschreibkorrektur usw. zu tun, wenn Sie die Zeichenfolge wie eine Liste in Lisp behandeln können.

    – Mike Dunlavey

    13. August 2009 um 0:57 Uhr

Jimmys Benutzeravatar
Jimmy

Ich werfe nur ein paar Hypothesen raus:

  • Es gibt keine Möglichkeit, eine “falsche” Implementierung von nullterminierten Zeichenfolgen zu erhalten. Eine standardisierte Struktur könnte jedoch anbieterspezifische Implementierungen haben.
  • Es sind keine Strukturen erforderlich. Nullterminierte Strings sind sozusagen “eingebaut”, da sie ein Sonderfall eines char* sind.

1390200cookie-checkWarum nullterminierte Strings? Oder: nullterminiert vs. Zeichen + Längenspeicherung

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy