qsort比较函数能否始终返回非零值? [英] Can the qsort comparison function always return a non-zero value?

问题描述

在 int 数组上的 qsort 和 bsearch 的升序排序回调函数可能看起来像这样:

An ascending sort callback function for qsort and bsearch on an array of int could look like this:

int ascending(const void *o1, const void *o2) {
    int a = *(const int *)o1;
    int b = *(const int *)o2;
    return a < b ? -1 : 1;
}

但是，此函数似乎违反了C标准中指定的 compar 函数的约束:

Yet this function seems to violate the constraint on the compar function as specified in the C Standard:

7.22.5.2 qsort 函数

7.22.5.2 The qsort function

简介

#include <stdlib.h>
void qsort(void *base, size_t nmemb, size_t size,
           int (*compar)(const void *, const void *));

说明
qsort 函数对 nmemb 对象的数组进行排序，该对象的初始元素由 base 指向.每个对象的大小由 size 指定.

Description
The qsort function sorts an array of nmemb objects, the initial element of which is pointed to by base. The size of each object is specified by size.

根据 compar 所指向的比较函数，数组的内容按升序排序，该函数带有两个指向要比较的对象的参数来调用.如果认为第一个参数分别小于，等于或大于第二个参数，则该函数应返回小于，等于或大于零的整数.

The contents of the array are sorted into ascending order according to a comparison function pointed to by compar, which is called with two arguments that point to the objects being compared. The function shall return an integer less than, equal to, or greater than zero if the first argument is considered to be respectively less than, equal to, or greater than the second.

如果两个元素比较相等，则未指定它们在结果排序数组中的顺序.

If two elements compare as equal, their order in the resulting sorted array is unspecified.

此比较功能正常还是会导致未定义的行为?

Is this comparison function OK or can it cause undefined behavior?

推荐答案

C 2018 7.22.5 4说:

C 2018 7.22.5 4 says:

当相同的对象(由大小字节组成，而不管它们在数组中的当前位置)多次传递给比较函数时，结果应彼此一致.也就是说，对于 qsort ，它们应在数组上定义总顺序；对于 bsearch ，相同的对象应始终以相同的方式与键进行比较.

When the same objects (consisting of size bytes, irrespective of their current positions in the array) are passed more than once to the comparison function, the results shall be consistent with one another. That is, for qsort they shall define a total ordering on the array, and for bsearch the same object shall always compare the same way with the key.

总订单要求 a = 一个.(要从Wikipedia页面上的定义中看到这一点:Connexity说，对于任何 a 和 b ， a ≤ b 或 b ≤ a .用 a 代替 b 得出 a ≤ a 或 a ≤ a .所以 a ≤ a .那么反对称的条件满足:我们有 a ≤ a 和 a ≤ a ，所以 a = a .)

A total order requires that a = a. (To see this from the definition in the Wikipedia page: Connexity says, for any a and b, a ≤ b or b ≤ a. Substituting a for b gives a ≤ a or a ≤ a. So a ≤ a. Then the condition of antisymmetry is satisfied: We have a ≤ a and a ≤ a, so a = a.)

这篇关于qsort比较函数能否始终返回非零值?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！