qsort: передать саму функцию компаратора или параметры в теле функции компаратора?

Есть несколько очевидных способов использования qsort: cast в компараторе:

int cmp(const void *v1, const void *v2) 
{
    const double *d1 = v1, *d2 = v2;
    ⋮
}

qsort(p, n, sizeof(double), cmp);

или бросьте компаратор:

int cmp(const double *d1, const double *d2) 
{
    ⋮
}

qsort(p, n, sizeof(double), (int (*)(const void *, const void *))cmp);

Я склонен использовать первый, больше из эстетических соображений, чем из чего-либо еще. Есть ли какие-либо технические причины для предпочтения одного над другим?


person jjg    schedule 27.02.2021    source источник


Ответы (3)


Вы должны избегать последнего случая, потому что это недопустимо.

Чтобы два типа функций были совместимы, возвращаемые типы должны быть совместимы, а соответствующие типы параметров должны быть совместимы. const void * несовместим с const double *, поэтому типы функций несовместимы. Вызов функции через несовместимый тип указателя приводит к неопределенному поведению.

Обратите внимание: тот факт, что два типа могут быть неявно преобразованы, не означает, что они совместимы. На примере const double * и const void * преобразование между двумя типами может выполняться без приведения, однако представление двух типов не обязательно должно быть одинаковым.

Это означает, что способ передачи const double * функции может отличаться от способа передачи const void * функции. Таким образом, вызывая функцию типа int (*)(const double*, const double*) так, как если бы она имела тип int (*)(const void*, const void*), параметры могли быть переданы неверным образом.

Хотя системы x64 и ARM обычно используют одно и то же представление для всех типов указателей, вы можете обойтись без первого варианта, но это все равно не гарантируется. Современные компиляторы часто предполагают, что неопределенное поведение не произойдет, и выполняют оптимизацию на основе этого факта.

Первый случай является правильным методом, поскольку сигнатура функции совместима с тем, что ожидает функция qsort.

person dbush    schedule 27.02.2021
comment
Интересно, спасибо - вы видите последнее использование повсюду, я предположил, что по этой причине оно соответствует. - person jjg; 27.02.2021
comment
@jjg: количество видимых мест кода не является показателем его соответствия какому-либо стандарту или спецификации. - person Eric Postpischil; 27.02.2021
comment
Это отличный вопрос и отличный ответ. И это стоит хорошо понять, потому что, хотя метод приведения компаратора выглядит разумным на первый взгляд, если вы думаете о коде, который компилятор собирается сгенерировать (или уже сгенерировал сгенерированный) вниз в qsort, чтобы фактически вызвать функцию сравнения, вы увидите, что она вызывает функцию с двумя указателями void *, поэтому ваша функция сравнения должна быть именно такой. (Если все типы указателей данных одинаковы — как, конечно, все они на всех популярных машинах в наши дни — неправильный код будет работать, но он все равно будет неправильным.) - person Steve Summit; 27.02.2021
comment
Если бы void qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *)); было void qsort(void *base, size_t nmemb, size_t size, int (*compar)();, я подозреваю, что любая форма была бы правильной. Поскольку указатели непрототипированных объектов преобразуются в void * (возможно). Важным вопросом является то, как объявляется compar. - person chux - Reinstate Monica; 27.02.2021
comment
@chux-ReinstateMonica Я так не думаю, поскольку преобразование в void * не входит в число рекламных акций по умолчанию. Вот почему указатели, переданные в printf, соответствующие спецификатору формата %p, должны быть явно приведены к void *. - person dbush; 27.02.2021
comment
@dbush Ах да. требуется явное преобразование/приведение. - person chux - Reinstate Monica; 27.02.2021
comment
Было бы интересно, если бы был реальный пример, в котором это не работает, либо из-за необычных соглашений о вызовах или представлений указателя, либо из-за агрессивной оптимизации. - person Nate Eldredge; 27.02.2021
comment
@NateEldredge Хотя я никогда не использовал его, я полагаю, что он не работал бы на машинах с адресацией слов, таких как PR1ME, которые имели 16-битные указатели на слова, но (эквивалент) 18-битные указатели char и void. Некоторая информация об этом содержится в списке часто задаваемых вопросов по C. - person Steve Summit; 27.02.2021
comment
@NateEldredge Конечно, сравнение char с ранними Cray было бы неудачным, потому что указатели Cray адресовали 64-битные слова и содержали дополнительные внутренние поля для обработки char данных, упакованных по 8 байтов в слово. - person alephzero; 28.02.2021

В качестве дополнения, есть еще одна стратегия вызова qsort: создать промежуточную qsort требуемую функцию-прототип, которая вызывает функцию сравнения с поддержкой типов.

#include <stdlib.h>
#include <stdio.h>

static int double_cmp(const double *d1, const double *d2)
    { return (*d1 > *d2) - (*d2 > *d1); }

static int double_void_cmp(const void *v1, const void *v2)
    { return double_cmp(v1, v2); }

int main(void) {
    double p[] = { 2.18, 6.28, 3.14, 1.20, 2.72, 0.58, 4.67, 0.0, 1, 1.68 };
    const size_t n = sizeof p / sizeof *p;
    size_t i;
    qsort(p, n, sizeof *p, &double_void_cmp);
    for(i = 0; i < n; i++) printf("%s%.2f", i ? ", " : "", p[i]);
    fputs(".\n", stdout);
    return EXIT_SUCCESS;
}

Хотя у этого есть свои проблемы, можно использовать double_cmp в качестве компаратора для других вещей, не относящихся к qsort. Кроме того, он не требует приведения типов или явных присваиваний, согласно моей интерпретации ISO 9899 6.3.2.3,

Указатель на void может быть преобразован в или из указателя на любой незавершенный или объектный тип. . . и обратно.

person Neil    schedule 27.02.2021
comment
примечание: на жаргоне программирования для этой техники используется thunk, что означает промежуточную функцию, которая вносит небольшие коррективы, чтобы несовместимые источник и место назначения могли сойтись вместе. - person M.M; 02.03.2021
comment
@M.M Я думаю, это будет называться оберткой, а не преобразователем. Преобразователь — это использование функции или замыкания для приостановки вычисления выражения, передавая код как данные, чтобы добавить лени к нетерпеливому языку. Это обычная техника в строгих функциональных языках. Преобразователи обычно не принимают аргументов и возвращают значение указанного типа. - person Mario Carneiro; 04.03.2021

В дополнение к отличному ответу dbush следует отметить, что случай альтернативной функции сравнения с прототипом int cmp(const char *s1, const char *s2), таким как strcmp, не так ясен, как тот, что указан в вопросе. Стандарт C указывает, что:

6.2.5 Типы

[...] Указатель на void должен иметь те же требования к представлению и выравниванию, что и указатель на символьный тип. Точно так же указатели на квалифицированные или неквалифицированные версии совместимых типов должны иметь одинаковые требования к представлению и выравниванию. Все указатели на типы структур должны иметь одинаковые требования к представлению и выравниванию. Все указатели на типы объединения должны иметь одинаковые требования к представлению и выравниванию. Указатели на другие типы не обязательно должны иметь такие же требования к представлению или выравниванию.

Таким образом, указатели на функции с прототипами int cmp(const void *v1, const void *v2) и int cmp(const char *v1, const char *v2) несовместимы, но маловероятно, что последовательность вызовов будет отличаться даже для тех чрезвычайно редких целей, где int cmp(const double *v1, const double *v2) будет проблематичным (ранние системы Cray и процессоры, не обладающие байтовой адресацией). .


Вы не предоставляете код для функций сравнения: распространенной ошибкой является простое возвращение разницы значений (*d1 - *d2). Это не работает для значений с плавающей запятой, а также для значений int, поскольку вычитание может переполниться.

Вот реализация возрастающего порядка, которая работает для всех типов чисел:

int cmp(const void *v1, const void *v2) {
    const int *p1 = v1, *p2 = v2;
    return (*p1 > *p2) - (*p1 < *p2);
}

Для типов с плавающей запятой может потребоваться специальная обработка значений NaN:

// sort by increasing values, with NaN after numbers
int cmp(const void *v1, const void *v2) {
    const double *p1 = v1, *p2 = v2;
    if (isnan(*p1)) {
        return isnan(*p2) ? 0 : 1;
    } else
    if (isnan(*p2)) {
        return -1;
    } else {
        return (*p1 > *p2) - (*p1 < *p2);
    }
}
person chqrlie    schedule 27.02.2021
comment
Мне нравится это double сравнение обработки NAN UV - как этот хороший ответ. Сначала уберите эти NAN с дороги. - person chux - Reinstate Monica; 27.02.2021
comment
Это не имеет ничего общего с проблемой, заданной в вопросе, и должно быть комментарием или отдельным вопросом. - person pipe; 28.02.2021
comment
@pipe: этот ответ действительно дает пищу для размышлений в связи с вопросом. ОП не опубликовал код своих функций сравнения, но случайные читатели должны научиться правильно писать эти функции сравнения, помимо проблемы прототипирования. - person chqrlie; 28.02.2021
comment
@chqrlie Напишите об этом в блоге или задайте вопрос. Пища для размышлений — это в лучшем случае комментарий. - person pipe; 01.03.2021
comment
@pipe: это может быть скорее комментарий, но а) он не будет хорошо работать в качестве комментария из-за его длины и включения кода, и б) он очень явно представляет ценность для читателей этой темы и, таким образом, помогает создавать от принятого ответа. Я не вижу причин, например. удалите его как не ответ. Если есть повод для усмотрения при рассмотрении ответов, то это, безусловно, один из таких случаев; удаление его окажет плохую услугу будущим читателям. - person Jeremy Caney; 01.03.2021
comment
@JeremyCaney: в этой ветке есть проблема, заключающаяся в том, что дизайн Stack Overflow явно и намеренно не является многопоточной доской/форумом. Длина комментариев намеренно ограничена, чтобы избежать путаницы. (См. соответствующие обсуждения Meta SO) - person MSalters; 01.03.2021
comment
@MSalters: Возможно. Хотя я отметил или просмотрел более 7500 ответов, и я столкнулся только с двумя или тремя «ответами с комментариями», которые имеют достаточную ценность, и мне неудобно голосовать за их удаление. Подавляющее большинство очень четко очерчены. - person Jeremy Caney; 01.03.2021