Ist der strcasecmp-Algorithmus fehlerhaft?

34

Ich versuche, die strcasecmpFunktion in C erneut zu implementieren, und habe festgestellt, dass der Vergleichsprozess inkonsistent ist.

Von man strcmp

Die Funktion strcmp () vergleicht die beiden Zeichenfolgen s1 und s2. Das Gebietsschema wird nicht berücksichtigt (für einen Gebietsschema-fähigen Vergleich siehe strcoll (3)). Es gibt eine Ganzzahl zurück, die kleiner, gleich oder größer als Null ist, wenn festgestellt wird, dass s1 kleiner als, übereinstimmend oder größer als s2 ist.

Von man strcasecmp

Die Funktion strcasecmp () führt einen byteweisen Vergleich der Zeichenfolgen s1 und s2 durch, wobei die Groß- und Kleinschreibung der Zeichen ignoriert wird. Es gibt eine Ganzzahl zurück, die kleiner, gleich oder größer als Null ist, 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;
}

Ausgabe:

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

Wenn das aktuelle Zeichen in s1ein Buchstabe ist, wird es anscheinend immer in Kleinbuchstaben umgewandelt, unabhängig davon, ob das aktuelle Zeichen in s2ein Buchstabe ist oder nicht.

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

Vielen Dank im Voraus!

PS:
Ich benutze gcc 9.2.0auf Manjaro.
Wenn ich mit dem -fno-builtinFlag kompiliere, bekomme ich stattdessen:

-30
2
2
2

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

Haltarys
quelle
2
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", "_"));Dies bedeutet jedoch, dass einer dieser beiden Anrufe , bei denen die Groß- und Kleinschreibung nicht berücksichtigt wird, nicht mit dem Gegenstück übereinstimmt, bei dem zwischen Groß- und Kleinschreibung unterschieden wird.
anton.burger
Es scheint, dass die Beschreibung, auf die strcasecmpSie sich beziehen, nicht korrekt ist. Weitere Details in den positiv bewerteten Antworten.
Jabberwocky
9
Es ist das einzige, was Sinn macht. Eine Funktion, die besagt, A < _ && a > _ && A == awürde so viele Probleme verursachen.
Ikegami
Nebenbei: "Ich versuche, die strcasecmp-Funktion in C erneut zu implementieren" -> Obwohl der Code nicht angezeigt wird, vergleichen Sie "als ob" unsigned char. C17 / 18 "String-Behandlung <string.h>" -> "Für alle Funktionen in diesem Unterabschnitt ist jedes Zeichen so zu interpretieren, als hätte es den Typ unsigned char". Dies macht einen Unterschied, sobald die charWerte außerhalb des ASCII-Bereichs 0-127 liegen.
chux - Monica
1
Zu den Unterschieden in den Ausgängen mit und ohne Einbauten: Beide sagen dasselbe, da ihre Ergebnisse identisch <0 und> 0 sind und Sie kein Beispiel für == 0 haben. Sie können jedoch sehen, wie die Algorithmen durchscheinen: Einige der zurückgegebenen Werte sind die Unterschiede des ersten ungleichen Zeichens.
Der Busybee

Antworten:

31

Das Verhalten ist korrekt.

Gemäß der POSIX- str\[n\]casecmp()Spezifikation :

Wenn die LC_CTYPEKategorie des verwendeten Gebietsschemas aus dem POSIX-Gebietsschema stammt, verhalten sich diese Funktionen so, als ob die Zeichenfolgen in Kleinbuchstaben konvertiert und anschließend ein Byte-Vergleich durchgeführt worden wäre. Andernfalls sind die Ergebnisse nicht spezifiziert.

Das ist auch ein Teil der NOTES Abschnitt des Linux - man - Seite :

Der POSIX.1-2008-Standard schreibt folgende Funktionen vor:

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

Warum?

Wie @HansOlsson in seiner Antwort hervorhob,strcmp() würde es die Sortierung unterbrechen , wenn nur Vergleiche zwischen Buchstaben ohne Berücksichtigung der Groß- und Kleinschreibung vorgenommen würden und alle anderen Vergleiche ihre "natürlichen" Ergebnisse wie in erhalten würden.

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

Andrew Henle
quelle
Vergleiche, bei denen die Groß- und Kleinschreibung nicht berücksichtigt wird, führen nicht zu Buchstaben '_' > 'A' && '_' < 'a'. scheint nicht das beste Beispiel zu sein.
Asteroiden mit Flügeln
1
@AsteroidsWithWings Dies sind die in der Frage verwendeten Zeichen. Und wenn Sie 'a' == 'A' per Definition einen Vergleich zwischen den "natürlichen" Werten von 'a', 'A'und '_'durchführen, können Sie keinen Vergleich zwischen 'A'und ohne Berücksichtigung der Groß- und Kleinschreibung durchführen 'a', um Gleichheit zu erhalten und konsistente Sortierergebnisse zu erhalten.
Andrew Henle
Ich bestreite das nicht, aber das spezifische Gegenbeispiel, das Sie zur Verfügung gestellt haben, scheint nicht relevant zu sein.
Asteroiden mit Flügeln
@AsteroidsWithWings Führen Sie die mentale Übung durch, einen Binärbaum aus 'a', 'A'und zu erstellen '_', alle 6 Einfügungsreihenfolgen in den Baum durchzugehen und die Ergebnisse aus den angegebenen "immer Kleinbuchstaben" mit den vorgeschlagenen Fragen "Nur Buchstaben konvertieren" zu vergleichen wenn es ein Brief-zu-Brief-Vergleich ist ". Beispielsweise unter Verwendung des Algorithmus letzteren und ausgehend von '_', 'a'und 'A'wickeln auf gegenüberliegenden Seiten des Baumes bis doch sind sie als gleich definiert. Der Algorithmus "Nur Buchstaben in Buchstaben-Buchstaben-Vergleiche in Kleinbuchstaben umwandeln" ist fehlerhaft und diese 3 Zeichen zeigen dies.
Andrew Henle
Okay, dann schlage ich vor, dies in der Antwort zu demonstrieren, weil es im Moment nur darum geht, darauf hinzuweisen, dass " '_' > 'A' und '_' < 'a'nicht beide wahr sein können", ohne uns zu sagen, warum wir jemals gedacht hätten, dass es so sein würde. (Das ist eine Aufgabe für den Antwortenden, nicht für einen von Millionen Lesern.)
Asteroids With Wings
21

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

Der Grund für dieses Verhalten ist, dass wenn Sie strcasecmp zum Sortieren eines Arrays von Zeichenfolgen verwenden, dies erforderlich ist, um angemessene Ergebnisse zu erzielen.

Andernfalls hängt das Ergebnis von der Reihenfolge der Vergleiche ab, wenn Sie versuchen, "A", "C", "_", "b" mit z. B. qsort zu sortieren.

Hans Olsson
quelle
3
Andernfalls hängt das Ergebnis von der Reihenfolge der Vergleiche ab, wenn Sie versuchen, "A", "C", "_", "b" mit z. B. qsort zu sortieren. Guter Punkt. Dies ist wahrscheinlich der Grund, warum POSIX das Verhalten angibt.
Andrew Henle
6
Genauer gesagt benötigen Sie eine Gesamtreihenfolge für die Sortierung, was nicht der Fall wäre, wenn Sie den Vergleich wie in der Frage definieren (da er nicht transitiv wäre).
Dukeling
8

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

Das ist richtig - und genau das sollte die strcasecmp()Funktion tun! Es ist eine Funktion und nicht Teil des Standards, sondern aus den " The Open Group Base Specifications, Ausgabe 6 ":POSIXC

Im POSIX-Gebietsschema verhalten sich strcasecmp () und strncasecmp () so, als ob die Zeichenfolgen in Kleinbuchstaben konvertiert und anschließend ein Byte-Vergleich durchgeführt worden wären. Die Ergebnisse sind in anderen Regionen nicht angegeben.

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

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

Adrian Mole
quelle
2

Der ASCII-Dezimalcode für Ais 65for _is 95und for ais macht 97also strcmp()das, was er tun soll. Lexikographisch gesehen _ist dann kleiner aund größer als A.

strcasecmp()wird Aals a* betrachtet, und da agrößer als _die Ausgabe ist auch korrekt.

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

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

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

anastaciu
quelle
3
Der Punkt von OP ist, dass Aes "größer" ist als _beim Vergleich ohne Berücksichtigung der Groß- und Kleinschreibung und sich fragt, warum das Ergebnis nicht das gleiche ist wie beim Vergleich ohne Berücksichtigung der Groß- und Kleinschreibung.
anton.burger
6
Die Anweisung Since strcasecmp () `unterscheidet nicht zwischen Groß- und Kleinschreibung und betrachtet A als a` ist ein ungültiger Abzug. Eine Routine, bei der die Groß- und Kleinschreibung nicht berücksichtigt wird, kann alle Großbuchstaben wie Kleinbuchstaben behandeln, alle Kleinbuchstaben wie Großbuchstaben behandeln oder jeden Großbuchstaben als gleichwertig mit dem entsprechenden Kleinbuchstaben behandeln und umgekehrt, aber dennoch vergleichen zu Nicht-Buchstaben-Zeichen mit ihren Rohwerten. Diese Antwort gibt keinen Grund an, eine dieser Möglichkeiten zu bevorzugen (der richtige Grund dafür ist, dass in der Dokumentation die Verwendung von Kleinbuchstaben angegeben ist).
Eric Postpischil
@EricPostpischil Der POSIX.1-2008-Standard schreibt diese Funktionen vor (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 konvertiert worden wären Kleinbuchstaben und dann ein Byte-Vergleich durchgeführt. Andernfalls sind die Ergebnisse nicht spezifiziert.
Anastaciu