Я немного подойду к значению строки, но прежде чем я это сделаю, давайте разберемся с некоторыми причинами того, почему qsort() нужен свой последний параметр того типа, который ему нужен. qsort() - это функция, которая может сортировать данные любого типа.
Вы предоставляете:
- базовый указатель, который указывает на начало непрерывного блока данных,
- количество элементов в блоке
- размер одного элемента данных и
- функция, которая сравнивает два значения данных.
Поскольку алгоритм сортировки в общем случае не зависит от типа сортируемых данных, qsort() можно записать без знания типов данных, которые он сортирует. Но чтобы сделать это, qsort() принимает void * параметров, что означает "универсальный указатель" в C.
Допустим, у вас есть массив несортированных int значений:
#define N 1024
int data[N] = { 10, 2, 3, -1, ... } /* 1024 values */
Затем вы можете отсортировать их, позвонив по номеру qsort():
qsort(data, N, sizeof data[0], compare_int);
data имеет тип int * при передаче в qsort(), а первый параметр qsort() имеет тип void *. Поскольку любой указатель объекта может быть преобразован в void * в C, это нормально. Следующие два аргумента тоже в порядке. Последний аргумент, compare_int, должен быть функцией, которая принимает два const void * параметра и возвращает int. Функция будет вызываться qsort() с парами указателей от &data[0] до &data[N-1] столько раз, сколько необходимо.
Чтобы объявить функцию f(), которая "принимает два const void * параметра и возвращает int":
int f(const void *, const void *);
Если кто-то хочет объявить указатель функции, который мы можем установить на f, указатель объявляется как:
int (*pf)(const void *, const void *);
pf = f;
Требуются круглые скобки, потому что в противном случае pf будет функцией, возвращающей int *. Теперь pf - указатель на функцию, возвращающую int.
Возвращаясь к нашему int алгоритму сортировки, и, исходя из вышесказанного, мы можем определить compare_int() как:
int compare_int(const void *a, const void *b)
{
const int *the_a = a;
const int *the_b = b;
if (*the_a > *the_b) return 1;
else if (*the_a < *the_b) return -1;
else return 0;
}
При написании compare_int() мы знаем, что переданные указатели int * замаскированы под void *, поэтому мы конвертируем их обратно в int *, что в порядке, и затем мы сравниваем числа.
Теперь обратим внимание на рассматриваемый код:
static int compare_wid( TRELLIS_ATOM* a, TRELLIS_ATOM* b )
означает, что compare_wid - это функция, которая принимает два параметра TRELLIS_ATOM * и возвращает int. Как мы только что видели, последний аргумент qsort() должен быть функцией типа:
int (*)(const void *, const void *)
Т.е., функция принимает два const void * параметра и возвращает int. Поскольку типы не совпадают, программист преобразует compare_wid() в тип, требуемый для qsort().
Однако у этого есть проблемы. Функция типа:
int (*)(TRELLIS_ATOM *, TRELLIS_ATOM *)
не эквивалентно функции типа:
int (*)(const void *, const void *)
, поэтому не гарантируется, что приведение будет работать. Намного проще, правильнее и стандартнее объявить compare_wid() как:
static int compare_wid(const void *a, const void *b);
И определение compare_wid() должно выглядеть так:
static int compare_wid(const void *a, const void *b)
{
const TRELLIS_ATOM *the_a = a;
const TRELLIS_ATOM *the_b = b;
...
/* Now do what you have to do to compare the_a and the_b */
return x;
}
Если вы сделаете это, вам не понадобится приведение к вызову qsort(), и ваша программа будет не только легче читать, но и исправлять.
Если вы не можете изменить compare_wid(), напишите другую функцию:
static int compare_stub(const void *a, const void *b)
{
return compare_wid(a, b);
}
и звоните qsort() с compare_stub() (без приведения) вместо compare_wid().
Редактировать : Основываясь на многих неправильных ответах, вот тестовая программа:
$ cat qs.c
#include <stdio.h>
#include <stdlib.h>
struct one_int {
int num;
};
#ifdef WRONG
static int compare(const struct one_int *a, const struct one_int *b)
{
#else
static int compare(const void *a_, const void *b_)
{
const struct one_int *a = a_;
const struct one_int *b = b_;
#endif
if (a->num > b->num) return 1;
else if (a->num < b->num) return -1;
else return 0;
}
int main(void)
{
struct one_int data[] = {
{ 42 },
{ 1 },
{ 100 }
};
size_t n = sizeof data / sizeof data[0];
qsort(data, n, sizeof data[0], compare);
return 0;
}
Компиляция с compare() определяется как принятие двух const struct one_int * значений:
$ gcc -DWRONG -ansi -pedantic -W -Wall qs.c
qs.c: In function `main':
qs.c:32: warning: passing argument 4 of `qsort' from incompatible pointer type
Компиляция с правильным определением:
$ gcc -ansi -pedantic -W -Wall qs.c
$
Редактировать 2 : Кажется, существует некоторая путаница относительно законности использования compare_wid как есть для окончательного аргумента qsort(). В comp.lang.c FAQ, вопрос 13.9 есть хорошее объяснение (выделено мной):
Чтобы понять, почему необходимо преобразование любопытных указателей в функции сравнения qsort ( и почему приведение указателя функции при вызове qsort не может помочь ), полезно подумать как работает qsort qsort ничего не знает о типе или представлении сортируемых данных: он просто перемешивает маленькие кусочки памяти. (Все, что он знает о чанках, это их размер, который вы указываете в третьем аргументе qsort.) Чтобы определить, нужно ли поменять местами два чанка, qsort вызывает функцию сравнения. (Чтобы поменять их местами, используется эквивалент memcpy.)
Так как qsort имеет дело с общими фрагментами памяти неизвестного типа, он использует общие указатели (void *) для ссылки на них. Когда qsort вызывает вашу функцию сравнения, она передает в качестве аргументов два общих указателя на блоки для сравнения. Так как он передает универсальные указатели, ваша функция сравнения должна принимать универсальные указатели и преобразовывать указатели обратно в их соответствующий тип, прежде чем манипулировать ими (т.е. перед выполнением сравнения). Указатель void не того же типа, что и указатель структуры, и на некоторых машинах он может иметь другой размер или представление (именно поэтому эти приведения необходимы для корректности).
Как уже упоминалось в FAQ, см. Также this .