kclib1のページ#2

  • (by K, 2019.04.16)

(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);
    }

こめんと欄


コメントお名前NameLink

トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2019-04-16 (火) 15:13:06 (216d)