C / C++ / 系统课时

用 qsort 理解标准库回调

用 qsort 理解标准库回调

C 标准库的 qsort 是函数指针最典型的实际接口之一:库函数负责通用排序流程,调用者只提供“两个元素谁应该排在前面”的比较函数。掌握这个例子,就能把函数指针与真实 API 中的回调约定联系起来。

学习目标

  • 正确调用标准库 qsort 对整数数组排序
  • 写出符合 qsort 要求的比较回调,并理解三个返回区间的含义
  • 避免比较函数中的类型转换和整数溢出错误

qsort 把排序规则交给调用者

qsort 声明在 <stdlib.h> 中。它接收数组首地址、元素数量、单个元素大小以及比较函数。因为标准库不知道数组元素究竟是 int、结构体还是其他类型,所以数组地址和比较参数都使用通用指针形式。

其接口可以概括为:

c
void qsort(void *base,
           size_t count,
           size_t size,
           int (*compare)(const void *, const void *));

这是标准库函数声明的等价展示,不是独立可运行程序。compare 每次接收两个元素的地址,并通过返回值告诉 qsort 它们的相对顺序。

写一个安全的整数比较函数

下面把整数数组按升序排列。比较函数先把 const void * 转回 const int *,再读取两个元素。返回值只表达大小关系,不需要返回实际差值。

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

int compare_int(const void *first, const void *second) {
    const int left = *(const int *)first;
    const int right = *(const int *)second;

    // 正数表示 left 应排在 right 后面,负数表示应排在前面。
    return (left > right) - (left < right);
}

int main(void) {
    int numbers[] = {42, -7, 18, 18, 3};
    size_t count = sizeof numbers / sizeof numbers[0];

    qsort(numbers, count, sizeof numbers[0], compare_int);

    for (size_t i = 0; i < count; ++i) {
        printf("%d%s", numbers[i], i + 1 == count ? "\n" : " ");
    }
    return 0;
}

预期输出

text
-7 3 18 18 42

调用 qsort 时直接传入 compare_int,标准库在排序过程中会按需要多次回调它。调用者不负责决定比较发生多少次,也不应依赖某个固定的比较顺序。

看懂标准库与回调的分工

排序过程中至少同时存在数组、qsort 和比较函数三个角色。数组提供待排序元素,qsort 控制排序算法,比较函数只回答当前两个元素的先后关系。

qsort 与比较回调之间的调用关系

比较函数返回值的规则只有三类:小于 0 表示第一个元素应排在第二个之前,等于 0 表示两者在排序意义上相等,大于 0 表示第一个元素应排在第二个之后。标准并不要求返回 -1、0、1,只关心符号。

不要直接用相减比较整数

一种常见写法是 return left - right;。对于较小的数据它似乎能工作,但当 left 和 right 接近 int 的取值边界时,减法可能发生有符号整数溢出,而有符号整数溢出属于未定义行为。

因此示例使用:

c
return (left > right) - (left < right);

这是比较函数中的片段示例,依赖已经取得的 left 和 right 两个 int 值。两个关系表达式的结果只能是 0 或 1,组合后稳定得到 -1、0 或 1,不会因为两个原始整数差值过大而溢出。

void 指针为什么必须转回元素类型

qsort 要支持任意元素类型,因此比较函数参数只能统一写成 const void *。void * 本身没有元素类型信息,不能直接解引用;比较函数必须根据当前数组真实的元素类型,把地址转换回相应指针。

本例排序的是 int 数组,所以转换为 const int *。如果排序的是结构体数组,就应转换为对应的结构体指针,再比较需要参与排序的字段。这里保留 const 也很重要:比较函数的职责是观察两个元素并决定顺序,而不是修改数组元素。

回调接口的真正约束

使用 qsort 时,最重要的不是记住函数指针语法,而是遵守回调协议:参数必须按 API 约定解释,返回值必须表达规定的语义,而且回调不能假定库函数会按照某种固定次数或固定顺序调用它。

这种设计让标准库可以复用同一套排序流程处理不同数据。以后遇到事件处理器、遍历函数或库提供的回调 API,也可以用同样的方法阅读:先确认回调签名,再确认每个参数来自哪里,最后确认返回值或副作用代表什么。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用 qsort 理解标准库回调

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通