Ist der strcasecmp-Algorithmus fehlerhaft?

Lesezeit: 7 Minuten

Benutzer-Avatar
Pausen

Ich versuche die neu zu implementieren strcasecmp Funktion in C und ich bemerkte, was eine Inkonsistenz im Vergleichsprozess zu sein scheint.

Aus man strcmp

Die Funktion strcmp() vergleicht die beiden Strings s1 und s2. Das Gebietsschema wird nicht berücksichtigt (für einen Vergleich, der das Gebietsschema berücksichtigt, siehe strcoll(3)). Sie gibt eine ganze Zahl kleiner, gleich oder größer als Null zurück, wenn festgestellt wird, dass s1 kleiner als, übereinstimmend oder größer als s2 ist.

Aus man strcasecmp

Die Funktion strcasecmp() führt einen Byte-für-Byte-Vergleich der Zeichenfolgen s1 und s2 durch, wobei die Groß-/Kleinschreibung der Zeichen ignoriert wird. Sie gibt eine ganze Zahl kleiner, gleich oder größer als Null zurück, wenn festgestellt wird, dass s1 kleiner als, übereinstimmend oder größer als s2 ist.

int strcmp(const char *s1, const char *s2);
int strcasecmp(const char *s1, const char *s2);

Angesichts dieser Informationen verstehe ich das Ergebnis des folgenden Codes nicht:

#include <stdio.h>
#include <string.h>

int main()
{
    // ASCII values
    // 'A' = 65
    // '_' = 95
    // 'a' = 97

    printf("%i\n", strcmp("A", "_"));
    printf("%i\n", strcmp("a", "_"));
    printf("%i\n", strcasecmp("A", "_"));
    printf("%i\n", strcasecmp("a", "_"));
    return 0;
}

Ausgang:

-1  # "A" is less than "_"
1   # "a" is more than "_"
2   # "A" is more than "_" with strcasecmp ???
2   # "a" is more than "_" with strcasecmp

Es scheint, dass, wenn das aktuelle Zeichen in s1 ein Buchstabe ist, wird dieser immer in Kleinbuchstaben umgewandelt, egal ob das aktuelle Zeichen in s2 ist ein Buchstabe oder nicht.

Kann sich jemand dieses Verhalten erklären? Sollten die erste und dritte Zeile nicht identisch sein?

Danke im Voraus!

PS:
ich benutze gcc 9.2.0 auf Manjaro.
Auch wenn ich mit dem kompiliere -fno-builtin flag bekomme ich stattdessen:

-30
2
2
2

Ich denke, es liegt daran, dass das Programm nicht die optimierten Funktionen von gcc verwendet, aber die Frage bleibt.

  • Fügen Sie Ihrem Set einen weiteren Testfall hinzu: printf("%i\n", strcasecmp("a", "_")); Dies sollte vermutlich das gleiche Ergebnis haben wie printf("%i\n", strcasecmp("A", "_")); Aber das bedeutet das eines dieser beiden Aufrufe ohne Berücksichtigung der Groß-/Kleinschreibung wird mit seinem Gegenstück, bei dem die Groß-/Kleinschreibung beachtet wird, nicht übereinstimmen.

    – anton.burger

    21. Februar 2020 um 16:15 Uhr

  • Es scheint die Beschreibung von strcasecmp Sie beziehen sich auf ist nicht korrekt. Weitere Details in den positiv bewerteten Antworten.

    – Jabberwocky

    21. Februar 2020 um 16:58 Uhr


  • Es ist das einzige, was Sinn macht. Eine Funktion, die sagt A < _ && a > _ && A == a würde so viele Probleme machen.

    – Ikegami

    21. Februar 2020 um 17:25 Uhr

  • Beiseite: “Ich versuche, die strcasecmp-Funktion in C neu zu implementieren ” –> Obwohl der Code nicht angezeigt wird, achten Sie darauf, “als ob” zu vergleichenunsigned char. C17/18 “Stringhandling ” –> “Für alle Funktionen in diesem Unterabschnitt soll jedes Zeichen so interpretiert werden, als hätte es den Typ unsigned char“. Das macht einmal einen Unterschied char Werte liegen außerhalb des ASCII-Bereichs 0-127.

    – chux – Wiedereinsetzung von Monica

    21. Februar 2020 um 17:37 Uhr


  • Zu den Unterschieden in den Ausgaben mit eingebauten und ohne: Beide sagen dasselbe, da ihre Ergebnisse identisch <0 und >0 sind, und Sie kein Beispiel für ==0 haben. Aber Sie können sehen, dass die Algorithmen durchscheinen: Einige der zurückgegebenen Werte sind die Unterschiede des ersten ungleichen Zeichens.

    – die fleißige Biene

    22. Februar 2020 um 15:38 Uhr

Benutzer-Avatar
Andreas Henle

Das Verhalten ist korrekt.

Pro die POSIX str\[n\]casecmp() Spezifikation:

Wenn der LC_CTYPE Kategorie des verwendeten Gebietsschemas aus dem POSIX-Gebietsschema stammt, müssen sich diese Funktionen so verhalten, als ob die Zeichenfolgen in Kleinbuchstaben konvertiert und dann ein Bytevergleich durchgeführt worden wären. Andernfalls sind die Ergebnisse nicht spezifiziert.

Das gehört auch dazu das ANMERKUNGEN Abschnitt der Linux-Manpage:

Der POSIX.1-2008-Standard sagt über diese Funktionen:

Wenn die LC_CTYPE-Kategorie des verwendeten Gebietsschemas aus dem POSIX-Gebietsschema stammt, verhalten sich diese Funktionen so, als ob die Zeichenfolgen in Kleinbuchstaben konvertiert und dann ein Bytevergleich durchgeführt worden wären. Andernfalls sind die Ergebnisse nicht spezifiziert.

Wieso den?

Wie @HansOlsson in seiner Antwort betonte, führte er Vergleiche ohne Berücksichtigung der Groß- und Kleinschreibung nur zwischen Buchstaben durch und ließ zu, dass alle anderen Vergleiche ihre “natürlichen” Ergebnisse wie in ausgeführt hatten strcmp() würde die Sortierung unterbrechen.

Wenn 'A' == 'a' (die Definition eines Vergleichs ohne Berücksichtigung der Groß-/Kleinschreibung) dann '_' > 'A' und '_' < 'a' (die “natürlichen” Ergebnisse im ASCII-Zeichensatz) können nicht beide wahr sein.

  • Vergleiche ohne Berücksichtigung der Groß-/Kleinschreibung nur zwischen Buchstaben würden nicht dazu führen '_' > 'A' && '_' < 'a'; scheint nicht das beste Beispiel zu sein.

    – Asteroiden mit Flügeln

    22. Februar 2020 um 14:44 Uhr

  • @AsteroidsWithWings Das sind die in der Frage verwendeten Zeichen. Und wenn 'a' == 'A' per Definitionwenn Sie einen Vergleich zwischen den “natürlichen” Werten machen 'a', 'A'und '_‘, Sie kann nicht Führen Sie einen Vergleich zwischen Groß- und Kleinschreibung durch 'A' und 'a' um Gleichheit und konsistente Sortierergebnisse zu erhalten.

    – Andreas Henle

    22. Februar 2020 um 18:54 Uhr


  • Ich bestreite das nicht, aber das von Ihnen angegebene spezifische Gegenbeispiel scheint nicht relevant zu sein.

    – Asteroiden mit Flügeln

    22. Februar 2020 um 19:27 Uhr

  • @AsteroidsWithWings Machen Sie die mentale Übung zum Erstellen eines Binärbaums aus 'a', 'A'und '_', alle 6 Reihenfolgen des Einfügens in den Baum durchlaufen und die Ergebnisse aus den angegebenen “immer Kleinbuchstaben” mit den in der Frage vorgeschlagenen “Buchstaben nur konvertieren, wenn es sich um einen Buchstaben-zu-Buchstaben-Vergleich handelt” vergleichen. Verwenden Sie beispielsweise den letzteren Algorithmus und beginnen Sie mit '_', 'a' und 'A' auf gegenüberliegenden Seiten des Baumes landen, aber sie sind als gleich definiert. Der Algorithmus “bei Buchstaben-Buchstaben-Vergleichen nur Buchstaben in Kleinbuchstaben umwandeln” ist gebrochen und diese 3 Zeichen zeigen das.

    – Andreas Henle

    23. Februar 2020 um 12:49 Uhr


  • Okay, dann schlage ich vor, das in der Antwort zu demonstrieren, denn im Moment geht es nur darum, darauf hinzuweisen '_' > 'A' und '_' < 'a' kann nicht beides wahr sein” ohne uns zu sagen, warum wir jemals hätten denken sollen, dass es so wäre. (Das ist eine Aufgabe für den Antwortenden, nicht für einen von Millionen Lesern.)

    – Asteroiden mit Flügeln

    23. Februar 2020 um 15:07 Uhr

Andere Verbindungen, http://man7.org/linux/man-pages/man3/strcasecmp.3p.html für strcasecmp sagen, dass die Konvertierung in Kleinbuchstaben das richtige Verhalten ist (zumindest im POSIX-Gebietsschema).

Der Grund für dieses Verhalten ist, dass, wenn Sie strcasecmp verwenden, um ein Array von Zeichenfolgen zu sortieren, dies erforderlich ist, um vernünftige Ergebnisse zu erhalten.

Andernfalls, wenn Sie versuchen, “A”, “C”, “_”, “b” zu sortieren, indem Sie zB qsort verwenden, würde das Ergebnis von der Reihenfolge der Vergleiche abhängen.

  • Andernfalls, wenn Sie versuchen, “A”, “C”, “_”, “b” zu sortieren, indem Sie zB qsort verwenden, würde das Ergebnis von der Reihenfolge der Vergleiche abhängen. Guter Punkt. Das ist wahrscheinlich der Grund, warum POSIX das Verhalten spezifiziert.

    – Andreas Henle

    21. Februar 2020 um 16:22 Uhr

  • Konkreter braucht man a Gesamtbestellung zum Sortieren, was nicht der Fall wäre, wenn Sie den Vergleich wie in der Frage definieren (da er nicht transitiv wäre).

    – Bernhard Barker

    22. Februar 2020 um 17:57 Uhr

Benutzer-Avatar
Adrian Mol

Wenn das aktuelle Zeichen in s1 ein Buchstabe ist, wird es anscheinend immer in Kleinbuchstaben konvertiert, unabhängig davon, ob das aktuelle Zeichen in s2 ein Buchstabe ist oder nicht.

Das ist richtig – und es ist, was die strcasecmp() Funktion sollte tun! Es ist ein POSIX Funktion, anstatt Teil der C Standard aber, von der “The Open Group Base Specifications, Ausgabe 6“:

In der POSIX-Locale sollen sich strcasecmp() und strncasecmp() so verhalten, als ob die Strings in Kleinbuchstaben umgewandelt und dann ein Byte-Vergleich durchgeführt worden wäre. Die Ergebnisse sind in anderen Gebietsschemas nicht angegeben.

Dieses Verhalten gilt übrigens auch für die _stricmp() Funktion (wie in Visual Studio/MSCV verwendet):

Die _stricmp-Funktion vergleicht string1 und string2 ordinal, nachdem sie jedes Zeichen in Kleinbuchstaben konvertiert hat, und gibt einen Wert zurück, der ihre Beziehung angibt.

Benutzer-Avatar
Anastaciu

Der ASCII-Dezimalcode für A ist 65 zum _ ist 95 und für a ist 97Also strcmp() es tut, was es tun soll. Lexikografisch gesprochen _ ist dann kleiner a und größer als A.

strcasecmp() betrachten A als seiend a*, und da a ist größer als _ die Ausgabe ist auch korrekt.

*Der POSIX.1-2008-Standard sagt über diese Funktionen (strcasecmp() und strncasecmp()):

Wenn die LC_CTYPE-Kategorie des verwendeten Gebietsschemas aus dem POSIX-Gebietsschema stammt, verhalten sich diese Funktionen so, als ob die Zeichenfolgen in Kleinbuchstaben konvertiert und dann ein Bytevergleich durchgeführt worden wären. Andernfalls sind die Ergebnisse nicht spezifiziert.

Quelle: http://man7.org/linux/man-pages/man3/strcasecmp.3.html

1385470cookie-checkIst der strcasecmp-Algorithmus fehlerhaft?

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

Privacy policy