* kclib1のページ#2
-(by [[K]], 2019.04.16)

** (2) kqsort
** (4) kqsort
-void kqsort(void *base, int num, int size, int (*compare)(void *, const void *, const void *), void *opt)
--標準関数qsort()に対して、末尾に引数optを追加しました。これは比較関数compareを呼び出すときに、第一引数として渡します。それ以外はqsortと同じです。
----
-[詳細説明]
--そもそもなんで比較関数を呼び出すときにoptを渡せるようにする必要があるかを説明します。
--まずここに、学校で40人のクラスがあって、その成績があるとします。
 struct Data_ {
     int num[10];
     char *nam;
 } Data;
 enum { NO, KOKU, SUU, EI, RI, SYA, ON, BI, GIKA, TAI }; // 出席番号, 国語, 数学, 英語, 理科, 社会, 音楽, 美術, 技術・家庭, 体育.
 
 Data data[40] = { ... };
--これを国語の成績順に並べるとしたらどう書けばいいでしょうか？・・・まあこんな感じですよね。
 int comp1a(const void *a, const void *b)
 {
     const Data *da = a, *db = b;
     return da->num[KOKU] - db->num[KOKU]; // この書き方の場合、とりあえず低い順になる.
 }
 
 qsort(data, 40, sizeof (Data), comp1);
--では、算数の成績順に並べるとしたら？・・・こうですよね。
 int comp2a(const void *a, const void *b)
 {
     const Data *da = a, *db = b;
     return da->num[SUU] - db->num[SUU]; // この書き方の場合、とりあえず低い順になる.
 }
 
 qsort(data, 40, sizeof (Data), comp2);
--この調子で9教科＋出席番号順のソートを実装すると、10個の比較関数を用意しなければいけません。さらに降順もサポートしたければ、引き算を逆にしたバージョンも用意する必要があるので、さらに倍増して20個の比較関数を用意することになります。それだけで120行も要してしまいます。これってすごく無駄だと思いませんか？バグを見逃す温床しかなりません。
--では、どうすればいいでしょうか？・・・そうです、比較関数が追加の引数を取れればいいのです。
 int compAsc(void *opt, const void *a, const void *b)
 {
     int i = (int) opt;
     const Data *da = a, *db = b;
     return da->num[i] - db->num[i];
 }
 
 int compDesc(void *opt, const void *a, const void *b)
 {
     int i = (int) opt;
     const Data *da = a, *db = b;
     return db->num[i] - da->num[i];
 }
--これがあれば、国語の成績順に並べるときは、
 kqsort(data, 40, sizeof (Data), compAsc, (void *) KOKU);
--とやれば済むのです。もう新しい比較関数を作る必要はありません。つまり比較関数はたったの2つで済みます。合計14行です。実に''106行も節約できる''のです。
--このように、コールバック関数を関数に渡すときは、追加の引数として void * 型のパラメータを渡せるようにする方が一般です。・・・たとえばwin32のAPIにEnumWindows()というのがあるのですが、ちゃんと void * を渡せるようになっています。
--だから、むしろけしからんのはqsortのほうなのです。ということで、けしからんqsortを何とかしたものがkqsortになるわけです。
----
-[効果]この関数を使うことで、比較関数をたくさん書かなければいけないケースが減ります。上記の例だと106行も節約されることになります。
----
-[内部実装]
 #include <stdlib.h>
 
 static void *opt_;
 static int (*comp_)(void *, const void *, const void *);
 
 static int comp(const void *a, const void *b)
 {
     return comp_(opt_, a, b);
 }
 
 void kqsort(void *base, size_t num, size_t size, int (*compare)(void *, const void *, const void *), void *opt)
 {
     opt_ = opt;
     comp_ = compare;
     qsort(base, num, size, comp);
 }


* こめんと欄
#comment
トップ   編集 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS