c++で構造体に格納された分数をstd::qsortする時のqsortの引数および処理について

Question

こちら(https://yukicoder.me/problems/no/750)の問題のコードで、入力された分数をソートして出力するものになっています。

わからない内容としては
①str::qsortの第4引数であるcompareの関数になぜ引数が与えられていないのか
②compare関数はconst void型のポインタを構造体s型のポインタにキャストしていますが、関数が構造体やクラスのメンバ変数を参照する場合は、基本的にconst void型ポインタを使うという理解でいいのでしょうか？
③compareの戻り値は常に0になると思いますが、qsortの処理とはどのように対応するのでしょうか?

#include <iostream>
using namespace std;

struct s {
    int A, B;
};

int compare(const void *x, const void *y) {
    return ((s*)x)->B * ((s*)y)->A - ((s*)x)->A * ((s*)y)->B;
}

int main() {
    int n;
    cin >> n;
    s frac[n];
    for (int i = 0; i < n; ++i) cin >> frac[i].A >> frac[i].B;
    qsort(frac, n, sizeof(s), compare); 
    for (int i = 0; i < n; ++i) cout << frac[i].A << ' ' << frac[i].B << endl;
}

Answer 1

qsort

ここをみるとわかりますが、第４引数の定義はこの様になってます
int (*compar)(const void *, const void *)

① qsort の引数に与えているのは関数のアドレスです
② 比較関数の定義は上記のようになってます。並び替える対象によって何でも使えるように void* となってるので、比較関数内では、並び替える要素のアドレスにキャストしますねー
③ リンク先に説明があります

Comments

[chili]

関数ポインタの使い方について勉強が必要だと思いました。ありがとうございます！

Answer 2

こんにちは。

そのqsortはC++ではなくC言語の関数です。

①str::qsortの第4引数であるcompareの関数になぜ引数が与えられていないのか

compareに実引数を与えるとcompare関数呼び出しとなってしまい、compareを呼び出して得られた戻り値がqsortの第4引数に与えられることになります。
しかし、qsortの第4引数には、compare関数の戻り値のintではなく関数ポインタを与えます。この関数がqsortの内部から呼び出されてソート処理が実行されるのです。

②compare関数はconst void型のポインタを構造体s型のポインタにキャストしていますが、関数が構造体やクラスのメンバ変数を参照する場合は、基本的にconst void型ポインタを使うという理解でいいのでしょうか？

C言語ではYESです。C++ではＮＯです。C++ではなるべく型情報の管理はコンパイラに任せた方が幸せになれます。（C言語では型情報を維持する仕組みがないので諦めてvoid*を使うことが多いです。）
もし、学習時間を割けることができるならば、std::sortを使うとより安全なプログラムを書けるようにます。

③compareの戻り値は常に0になると思いますが、qsortの処理とはどのように対応するのでしょうか?

パラメータxとyにそれぞれ与えられたS構造体のメンバA, Bの値により結果は変わりますので、常に0にはならないですよ。
x, yにはソート対象の配列の各要素のどれかが与えられます。ソートするために２つの要素を比較するためにqsortがcompareを呼び出します。

Comments

[chili]

詳細な説明で勉強になりました！ありがとうございます。

Answer 3

①比較関数(compare)の実際の呼び出しはqsort内部で行われます。このとき、引数として比較する配列の要素が渡されます。

②事前にどんな型の配列が渡されるかわからないため、qsortの内部では配列の要素はvoid *となっています。配列を各要素に分割するには、要素の型(構造体)を知らなくても、要素の個数とサイズ(第2,3引数)がわかれば十分です。
よって、比較関数(compare)では、要素を比較する前に元の型(構造体)にキャストし直す必要があります。

③比較関数(compare)は、qsort内部で配列の要素を比較するために何度も呼び出されます。よって、常に0になることはありません。
qsortは分割した要素の型(構造体)を知らないため、要素を比較するために比較関数(compare)を呼び出します。

Comments

[chili]

関数ポインタの使い方について勉強が必要だと思いました。ありがとうございます！