bsearch的不同比较函数

Question

两个cmp函数似乎都有效；在qsort_cmp的情况下，我无法理解int*类型的arg1是如何解析的。据我所知: int*被传递给qsort_cmp，在那里它被更改为void*，然后在return语句中转换为struct s*。到目前为止没有问题，但是强制转换对象应该有一个名为b的成员，它的强制转换类型有这个成员，但是它的实例没有...

struct s { int a, b; };

int qsort_cmp(const void *r1, const void *r2) {
     return ((struct s*) r1)->b - ((struct s*) r2)->b;
}

int bsearch_cmp(const void *key, const void *r2) {
     return *(int*) key - ((struct s*) r2)->b;
}

/* themap is already qsorted */
int k = 'w'//hatever;
void *ret = bsearch(&k, themap, thenumber_ofelements, sizeof(one_element), qsort_cmp);

Answer 1

这些比较函数不能互换:一个比较两个参数的b字段，另一个比较第一个参数直接指向的int和第二个参数指向的结构的b字段。如果使用a字段而不是b字段，它们将是等效的，因为a字段位于结构的开头。

规格说明如下：

7.22.5.1 bsearch函数

..。

compar指向的比较函数通过两个参数调用，这两个参数依次指向键对象和数组元素。如果键对象分别被视为小于、匹配或大于数组元素，则函数应返回一个小于、等于或大于零的整数。

因此，只要比较函数与bsearch调用方案一致，第一个参数可以是指向int的指针，第二个参数可以是指向结构数组的指针

相反，qsort中使用的比较函数是用2个指向数组元素的指针调用的，因此这两个指针都是指向s结构的指针。

但是请注意，减去2个int值并不是产生比较结果的可靠方法，因为这种减法可能会对许多值造成溢出:例如，INT_MIN - 1。一种更好的方法是：

struct s { int a, b; };

int qsort_cmp(const void *r1, const void *r2) {
    const struct s *s1 = r1;
    const struct s *s2 = r2;
    return (s2->b < s1->b) - (s1->b < s2->b);
}

int bsearch_cmp(const void *key, const void *r2) {
    const int *ip = key;
    const struct s *s2 = r2;
    return (s2->b < *ip) - (*ip < s2->b);
}

现代编译器为此生成无分支代码：https://godbolt.org/z/sW3dn6