Передать дополнительный параметр в компаратор для qsort

Question

Мне просто интересно, есть ли способ передать дополнительный параметр моему компаратору, который затем будет использоваться в моей функции qsort?

Например, у меня есть эти 2 компаратора (один в порядке возрастания, а другой в порядке убывания)

qsort(entries, 3, sizeof(struct entry), compare_desc);

int compare_asc(const void *elem1, const void *elem2)
{
     return strcmp(elem1.name.last, elem2.name.last);
}


int compare_desc(const void *elem1, const void *elem2)
{
     return strcmp(elem2.name.last, elem1.name.last);
}

Есть ли способ, чтобы я мог сделать что-то вроде этого:

int compare(const void *elem1, const void *elem2, const char *order)
{
     if (strcmp(order, "asc") == 0)
         return strcmp(elem1.name.last, elem2.name.last);
     else if (strcmp(order, "desc") == 0)
         return strcmp(elem2.name.last, elem1.name.last);
}

Причина, по которой я спрашиваю, состоит в том, что моя программа сортировки должна принимать переключатели, и если у меня есть 2 различных переключателя (+ a, -a) для повышения и понижения соответственно, то мне нужно выполнить 2 различные функции компаратора. Если я добавлю больше, это будет сложнее. Есть ли способ улучшить дизайн этой программы?

РЕДАКТИРОВАТЬ: глобальные и внешние переменные не допускаются.

Answer 1

Старый вопрос, но в случае, если кто-то наткнется на него ...

Существуют нестандартные версии qsort (), которые позволяют передавать дополнительный параметр в функцию обратного вызова.glib предлагает qsort_r (), а VC - qsort_s ().

Answer 2

В вашем примере лучше иметь два разных компаратора. Если бы у вас был только один, каждое сравнение без необходимости должно было бы определять порядок сортировки, который вы не могли бы изменить в любом случае для любых значимых результатов. Поэтому вместо того, чтобы помещать if (ascending_sort) { } else { } в компаратор, поставьте его на свой qsort вызов:

qsort(e, n, sizeof(*e), (strcmp(order, "asc") ? compare_desc : compare_asc));

Редактировать: Несколько советов, если вы добавите больше компараторов:

- помните, что вам не нужно переписывать каждый компаратор; вы можете сделать так, чтобы они вызывали друг друга, если вы сортируете по нескольким полям (и вы всегда можете инвертировать результат компаратора с помощью -, например, compare_asc(a, b) может вернуть -compare_desc(a, b)).

- в конце легко поменять порядок всего массива, поэтому вам не нужно удваивать количество компараторов для поддержки возможности полностью изменить порядок сортировки

- вы можете заменить триединый оператор (? :) в моем примере функцией, которая возвращает соответствующий компаратор, как предлагается в комментариях ниже

Answer 3

> Есть ли способ улучшить дизайн этой программы?

Не делайте этого - это не улучшение дизайна, это всего лишь эксперимент.

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

int comparefx(const void *a, const void *b) {
    static int extra = 0;
    if (a == NULL) {
        extra = (int)b;
        return 0;
    }
    switch (extra) {
        case 24: puts("24"); return *(const int*)a + *(const int*)b; break;
        case 42: puts("42"); return *(const int*)b - *(const int*)a; break;
        default: puts("--"); return *(const int*)a - *(const int*)b; break;
    }
}

int main(void) {
    int entries[] = {4, 2, 8};

    qsort(entries, 3, sizeof *entries, comparefx);
    printf("%d %d %d\n", entries[0], entries[1], entries[2]);

    comparefx(NULL, (void*)42); /* set 'extra' parameter */
    qsort(entries, 3, sizeof *entries, comparefx);
    printf("%d %d %d\n", entries[0], entries[1], entries[2]);

    return 0;
}

"Чисто" компилируется с 3 компиляторами

$ gcc -std=c89 -pedantic -Wall 4210689.c
4210689.c: In function 'comparefx':
4210689.c:7: warning: cast from pointer to integer of different size

$ clang -std=c89 -pedantic -Wall 4210689.c
$ tcc -Wall 4210689.c
$ 

И работает так, как ожидалось

$ ./a.out
--
--
--
2 4 8
42
42
42
8 4 2

Answer 4

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

Учитывая ваш сценарий, это может быть что-то вроде

// selectively invoke qsort:
if(strcmp(var, "+a")){
    qsort(entries, 3, sizeof(struct entry), compare_asc);
}else{
    qsort(entries, 3, sizeof(struct entry), compare_desc);
}

Или вы можете сделать что-то вроде:

// declare a function pointer
int (*func)(const void*, const void*);

// sometime later decide which function to assign
// to the function pointer
if(strcmp(var, "+a")){
    func = compare_asc;
}else{
    func = compare_Desc;
}

// sometime later invoke qsort
qsort(entries, 3, sizeof(struct entry), compare_desc);

Answer 5

Без использования глобальной переменной, AFAIK, как правило, вы не можете, вы должны предоставить две разные функции для двух методов сортировки. На самом деле это одна из причин , почему в C ++ функторы (объекты, которые предоставляют перегруженный оператор вызова функции) часто используются.

Answer 6

В простых случаях вы можете использовать глобальную переменную.

Answer 7

qsort_r() и qsort_s()

В некоторых реализациях доступны функции с именем qsort_r() или qsort_s(), которые делают то, что вам нужно - взять указатель на дополнительные данные, которые передаются в функции компаратора.

Варианты реализации BSD (включая macOS или Mac OS X) предоставляют версию qsort_r(), также как и библиотека GNU C.К сожалению, оба варианта имеют разные подписи.Это не мешает им быть полезными, но это означает, что один и тот же исходный код не может быть использован на двух платформах, и, кроме того, вы должны убедиться, что понимаете, какой вариант qsort_r() доступен на любой машине, где вы пытаетесь

Аналогичным образом, Microsoft предоставляет версию qsort_s(), а стандарт C11 определяет версию qsort_s() (в качестве дополнительной функции в Приложении K, основанной на TR-24731), но эти дваразнятся в подписи снова.Возможно, к счастью, функции Приложения K не получили широкого распространения.

BSD qsort_r()

void qsort_r(void *base, size_t nel, size_t width, void *thunk,
             int (*compar)(void *, const void *, const void *));

Библиотека GNU C qsort_r()

void qsort_r(void *base, size_t nmemb, size_t size,
             int (*compar)(const void *, const void *, void *),
             void *arg);

Обратите внимание, чтов BSD 'thunk' эквивалентен 'arg' в GNU, но эти аргументы появляются в разных местах в последовательности вызова функции qsort_r() (до и после указателя функции компаратора).Кроме того, обратите внимание, что «thunk» передается в качестве аргумента 1 в функции компаратора BSD, но «arg» передается в качестве аргумента 3 в функции компаратора GNU.

Мнемоника для qsort_r: данные контекстауказывается в отношении компаратора в вызывающей последовательности в том же отношении, что и контекст, передаваемый компараторам в отношении двух сравниваемых значений.Контекст перед указателем на компаратор означает контекст перед значениями в вызове компаратора;контекст после указателя на компаратор означает контекст после значений в вызове компаратора.

Приложение K qsort_s()

errno_t qsort_s(void *base, rsize_t nmemb, rsize_t size,
               int (*compar)(const void *x, const void *y, void *context),
               void *context);

Приложение K qsort_s() является уникальным по возврату значения;все остальные варианты не возвращают никакого значения.В противном случае для большинства практических целей он соответствует функции GNU qsort_r().

Microsoft qsort_s()

void qsort_s(void *base, size_t num, size_t width,
             int (__cdecl *compare )(void *, const void *, const void *),
             void * context);

Различия rsize_t и size_tне очень важно при сравнении вариантов приложения K и Microsoft qsort_s(), но в приложении K qsort_s() контекст передается в качестве аргумента 3 компаратору, а в Microsoft qsort_s() контекст передается какаргумент 1 для компаратора.

Сводка

Функции, вызываемые qsort_r() или qsort_s(), обеспечивают необходимую функциональность.Однако вы должны проверить спецификацию платформы, для которой присутствует функция, и для правильной последовательности вызова для аргументов функции сортировки, и правильную последовательность вызова для аргументов для компараторов.

Номинально, вам также следует проверить тип возвращаемого значения функции, но немногие программы рассмотрят возможность его проверки, в основном потому, что большинство вариантов qsort() не возвращают значения.

Answer 8

Просто используйте лямбда-функцию для закрытия. Примерно такой код C ++:

string sortOrder="asc";   
qsort(entries, 3, sizeof(struct entry),    
[=](const void *elem1, const void *elem2) -> int{
        myCompare(elem1,elem2,sortOrde)             

});

Answer 9

Отсутствие классов и замыканий в значительной степени означает, что вы застряли в написании отдельного компаратора для каждого типа сравнения, который вы хотите.

Одна вещь, которую вы могли бы сделать, - это чтобы каждый элемент массива был структурой, содержащей поля value и sort_order. Все поля sort_order были бы одинаковыми ... но это хуже, чем просто наличие двух компараторов.

Думайте об этом так: в конечном итоге вы все равно пишете все тот же код компаратора. Но вместо сложного вложенного if / else с 8 случаями у вас есть 8 функций. Разница заключается в некоторых дополнительных объявлениях функций.

РЕДАКТИРОВАТЬ: Чтобы ответить на комментарии R .. это хороший момент. У меня было это раньше, но я удалил это:

Вы можете создать фреймворк, похожий на функцию list.sort() в Python. В значительной степени:

• Создать структуру с полями value и sortvalue.
• Поместить начальные значения в value.
• Напишите любой код для преобразования элементов в поле sortvalue.
• Используйте для этого стандартный компаратор вместе с qsort.
• Когда вы закончите, просто удалите элементы из полей value. Они будут отсортированы в соответствии с sortvalue, но значения будут правильными.

Это используется в Python, например, где, если вы хотите отсортировать, скажем, 4-й элемент в кортеже, вы не пишете целый компаратор (например, lambda v1,v2: v1[3]-v2[3]), а вместо этого просто преобразовываете входные данные с помощью key функция (lambda k: k[3]) и использовать стандартный метод сортировки. Это будет работать в случае «миллиардов видов», поскольку ваш код может выполнять любую сложную операцию с любым количеством входных данных для преобразования значений.