C言語の愉快な標準関数たち

ちょっとC言語学んだことがある人向けの、ちょっとテクニカルなことができるようになる技術解説。

解説するにあたってひとつ面白い標準関数があるので、これを使って紹介したいと思う。
それはずばり、qsort。その名のとおり、ある配列に対してソートを行ってくれる関数である。

まずこの関数の定義

void qsort(
void *base,
size_t num,
size_t size,
int (*compare)(const void*, const void*)
)


引数は合計4つ、なかなか愉快な表現になっています。
順番に見ていくと

１、void *base
void　*で定義された引数。void *って何やねん、と思うけれども、そもそも

ポインタの教え方がよろしくないと思う。
*hogehoge(変数名)というのは、すべからくアドレスのみを表している。それがどんなものであれ、hogehogeの中身は4バイトのアドレスを指し示すものである。

では、その前についてるintとかfloatとかの型が何をさしているのかというと、そのデータがどこまで入っているのか、ということである。
つまり　*hogehogeがデータの開始位置、その前の型データがその開始位置からどこまでデータが入っているのか、という長さを表している。

この場合のvoidは不定を表している。
つまりqsortは長さが不明だけれど、アドレスの値を受け取っている。というわけ。
当然、そのままではデータは取り出せない、どこからどこまでデータなのかが分からないので、参照ができない。

そこで、出てくるのが2番目と3番目の引数。
2番目の引数は、配列の長さで、三番目の引数が変数の長さ。この変数の長さ、というのが型情報に相当するもので、2番目の値は配列の長さである。


そして極め付けが4番目の引数。C勉強してる人でも、ここはすっとばして教えることが多いので分からないかもしれない。

これは、関数ポインタと呼ばれるもの。

プログラムがメモリ上に配置される。
つまり、プログラムコード自身もアドレスを持っているわけである。なので、関数のアドレスを示すポインタ、というのも存在する。それがこの表現である。


もうちょこっと踏み込むと、今回の場合は、

int hogehoge(const void *, const void *)という関数のアドレスを渡す、という意味である。

このようにすることで、qsortからhogehogeを呼び出す（実行させる）ことができるのである。


こんな説明では何が何やらさっぱりですね、次回は実践編ということで、これを用いたソートプログラムの実装方法について解説したいと思います。





ここまで読んで

「ソートプログラムとか単純だし、自分で作れよ」

というのは、実はわりと正論で、ソートはちょっと理解すればすぐに作れます。
しかし、高速なソートとなると話は別。

C標準のqsortは実装はコンパイラにより多少異なりますが、おおむねアセンブラレベルでの最適化まで図られている超高速プログラムです。素人が組んだソートプログラムとは雲泥の差です。

ためしに10万個、8文字のパスワード(a-z、0-9からなる8文字の文字列)をソートさせてみました。
結果、20回平均わずか0.3秒で完了しました。恐ろしい速度です。
素人が適当に組むと軽く10倍は超えます。

あとは、冒頭にも書きましたがqsortは実装が本当に愉快で、C言語らしい関数なので、ぜひ紹介したいと思った次第です。