Является ли алгоритм strcasecmp некорректным?

34

Я пытаюсь переопределить strcasecmpфункцию в C, и я заметил несоответствие в процессе сравнения.

От man strcmp

Функция strcmp () сравнивает две строки s1 и s2. Локаль не учитывается (сравнение с учетом локали смотрите в strcoll (3)). Он возвращает целое число, меньшее, равное или большее нуля, если найдено, что s1 соответственно меньше, соответствует или больше s2.

От man strcasecmp

Функция strcasecmp () выполняет побитовое сравнение строк s1 и s2, игнорируя регистр символов. Он возвращает целое число, меньшее, равное или большее нуля, если найдено, что s1 соответственно меньше, соответствует или больше s2.

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

Учитывая эту информацию, я не понимаю результат следующего кода:

#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;
}

Ouput:

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

Похоже, что если текущий символ в s1 является буквой, он всегда преобразуется в нижний регистр, независимо от того, является ли текущий символ в s2букве или нет.

Может кто-нибудь объяснить это поведение? Разве первая и третья строки не должны совпадать?

Заранее спасибо!

PS:
я использую gcc 9.2.0на Манджаро.
Кроме того, когда я компилирую с -fno-builtinфлагом, я получаю вместо этого:

-30
2
2
2

Я думаю, это потому, что программа не использует оптимизированные функции gcc, но вопрос остается.

Haltarys
источник
2
Добавьте еще один тестовый набор к вашему набору: он printf("%i\n", strcasecmp("a", "_"));должен иметь тот же результат, что и printf("%i\n", strcasecmp("A", "_"));Но, это означает, что один из этих двух нечувствительных к регистру вызовов будет не согласен с его чувствительным к регистру аналогом.
anton.burger
Кажется, описание, к strcasecmpкоторому вы обращаетесь, не является точным. Больше подробностей в ответах.
Джаббервоки
9
Это единственное, что имеет смысл. Функция, которая говорит A < _ && a > _ && A == a, вызовет так много проблем.
икегами
В стороне: «Я пытаюсь переопределить функцию strcasecmp в C» -> Хотя код не показан, не забудьте сравнить «как будто» unsigned char. C17 / 18 «Обработка строк <string.h>» -> «Для всех функций в этом подпункте каждый символ должен интерпретироваться так, как если бы он имел тип unsigned char». Это имеет значение, когда charзначения выходят за пределы диапазона ASCII 0-127.
chux - Восстановить Монику
1
О различиях в выходных данных со встроенными модулями и без них: оба говорят одно и то же, поскольку их результаты идентичны <0 и> 0, и у вас нет примера для == 0. Но вы можете видеть, как алгоритмы просвечивают: некоторые возвращаемые значения являются отличиями первого неравного символа.
занятая пчела

Ответы:

31

Поведение правильное.

Согласно спецификации POSIXstr\[n\]casecmp() :

Когда LC_CTYPEкатегория используемой локали относится к локали POSIX, эти функции должны вести себя так, как будто строки были преобразованы в нижний регистр, а затем выполняется сравнение байтов. В противном случае результаты не уточняются.

Это также является частью в NOTES части страницы человека Linux :

Стандарт POSIX.1-2008 говорит об этих функциях:

Когда категория LC_CTYPE используемой локали относится к локали POSIX, эти функции должны вести себя так, как если бы строки были преобразованы в нижний регистр, а затем выполнено сравнение байтов. В противном случае результаты не уточняются.

Почему?

Как указал @HansOlsson в своем ответе , сравнение без учета регистра выполняется только для букв и позволяет всем другим сравнениям получать свои «естественные» результаты, как это сделано вstrcmp() случае, нарушит сортировку.

Если 'A' == 'a'(определение сравнения без учета регистра), то '_' > 'A'и '_' < 'a'(«естественный» результат в наборе символов ASCII) не могут быть оба истинными.

Эндрю Хенле
источник
Сравнение только букв не учитывает регистр '_' > 'A' && '_' < 'a'; не похоже на лучший пример.
Астероиды с крыльями
1
@AsteroidsWithWings Это символы, используемые в вопросе. И если , 'a' == 'A' по определению , если сделать сравнение между «естественными» значениями 'a', 'A'и '_», вы не можете сделать регистронезависимое сравнение 'A'и 'a'получить равенство и получить устойчивые результаты сортировки.
Эндрю Хенле
Я не оспариваю это, но конкретный контрпример, который вы привели, кажется неуместным.
Астероиды с крыльями
@AsteroidsWithWings Пройдите мысленное упражнение по построению двоичного дерева из 'a', 'A'и '_', пройдя все 6 порядков вставки в дерево, и сравнив результаты из указанных «всегда строчных букв» с предложенным вопросом «только преобразовывать буквы». когда это сравнение букв в буквы ". Например, используя последний алгоритм и начиная с '_', 'a'и 'A'сверните на противоположных сторонах дерева, но они определены как равные. «Конвертировать только буквы нижнего регистра в письме-буквенных сравнений» алгоритм разбит и те 3 символы показывают , что.
Эндрю Хенле
Хорошо, тогда я предлагаю продемонстрировать это в ответе, потому что в данный момент он просто указывает на то, что « '_' > 'A' и '_' < 'a'оба не могут быть правдой», не говоря нам, почему мы должны были когда-либо думать, что это будет. (Это задача для ответчика, а не для одного из миллионов читателей.)
Астероиды с крыльями
21

Другие ссылки, http://man7.org/linux/man-pages/man3/strcasecmp.3p.html для strcasecmp, говорят о том, что преобразование в нижний регистр - это правильное поведение (по крайней мере, в локали POSIX).

Причина такого поведения заключается в том, что если вы используете strcasecmp для сортировки массива строк, это необходимо для получения разумных результатов.

В противном случае, если вы попытаетесь отсортировать «A», «C», «_», «b» с помощью, например, qsort, результат будет зависеть от порядка сравнений.

Ханс Олссон
источник
3
В противном случае, если вы попытаетесь отсортировать «A», «C», «_», «b» с помощью, например, qsort, результат будет зависеть от порядка сравнений. Хорошая точка зрения. Это, вероятно, причина, по которой POSIX определяет поведение.
Эндрю Хенле
6
Более конкретно, вам нужен общий порядок для сортировки, что было бы не так, если бы вы определили сравнение как в вопросе (так как оно не будет транзитивным).
Dukeling
8

Похоже, что если текущий символ в s1 является буквой, он всегда преобразуется в нижний регистр, независимо от того, является ли текущий символ в s2 буквой или нет.

Это правильно - и это то, что должна делать strcasecmp()функция ! Это функция, а не часть Стандарта, но из « Базовых спецификаций открытой группы, выпуск 6 »:POSIXC

В локали POSIX strcasecmp () и strncasecmp () должны вести себя так, как будто строки были преобразованы в нижний регистр, а затем выполняется сравнение байтов. Результаты не указаны в других регионах.

Кстати, это поведение также имеет отношение к _stricmp()функции (как используется в Visual Studio / MSCV):

Функция _stricmp обычно сравнивает строку1 и строку2 после преобразования каждого символа в нижний регистр и возвращает значение, указывающее их взаимосвязь.

Адриан Моул
источник
2

Десятичный код ASCII для for Aпредназначен 65для _is 95и for ais 97, поэтому strcmp()он делает то, что должен делать. Лексикографически говоря _меньшеa и больше, чем A.

strcasecmp()будет рассматривать Aкак являющийся a*, а так какa больше , чем _на выходе тоже правильно.

* Стандарт POSIX.1-2008 говорит об этих функциях (strcasecmp () и strncasecmp ()):

Когда категория LC_CTYPE используемой локали относится к локали POSIX, эти функции должны вести себя так, как если бы строки были преобразованы в нижний регистр, а затем выполнено сравнение байтов. В противном случае результаты не уточняются.

Источник: http://man7.org/linux/man-pages/man3/strcasecmp.3.html

anastaciu
источник
3
Смысл OP в том, что Aон «больше», чем _при сравнении без учета регистра, и удивляет, почему результат не такой, как при сравнении с учетом регистра.
anton.burger
6
Оператор Since strcasecmp () `нечувствителен к регистру, он будет рассматривать A как a`, что является недействительным выводом Процедура без учета регистра может обрабатывать все заглавные буквы, как если бы они были строчными буквами, могла обрабатывать все строчные буквы, как если бы они были заглавными буквами, или могла обрабатывать каждую заглавную букву как равную соответствующей строчной букве и наоборот, но все равно сравнивать их к буквенным символам с их необработанными значениями. В этом ответе не указывается причина предпочтения какой-либо из этих возможностей (правильная причина, по которой в документации сказано использовать строчные буквы).
Эрик Постпишил
@EricPostpischil Стандарт POSIX.1-2008 говорит об этих функциях (strcasecmp () и strncasecmp ()): когда категория LC_CTYPE используемой локали происходит из локали POSIX, эти функции должны вести себя так, как если бы строки были преобразованы в строчная и затем выполняется сравнение байтов. В противном случае результаты не уточняются.
Анастасиу