ここのところの仕事の中で、vectorを一定の（しかし単なる大小比較ほどシンプルじゃないルールで）ソートする必要があり、コーディングしていました。
差し支えない程度にざっくり言うと、(x, y)座標の点を表す構造体があり、それを左上から右下へ並べ替えます。その時に、一定の閾値以下のズレはないものとして扱う、イコールとする、という仕掛けを入れたかったのです。
せっかくSTL使ってるんだから、ソートもSTLのやつを使えばいいじゃんということで、std::sortを使うことにしました。イメージとして、RubyのArray::sort、ブロック付きのやつが頭にあり、そんな雰囲気でstd::sortを使うつもりでいました。
サクサクとつくり、実際動かしてみたところ、Assertが発生しました。曰く「invalid comparator」。理由がわからず検索をかけてみたところ、StackOverflowの記事に行き当たり、比較関数は「Strict Weak Ordering」なるルールに従う必要があるとのこと。
これが、Wikipediaやここやここを読んでもさっぱりピンとこなかったのです。
なんとか理解したものを噛みくだくと、比較関数 comp(a, b) は以下の3点を守る必要がある、ということ。
- すべての場合において、comp(a,a) が false となること
- comp(a,b) が true のとき、comp(b,a) が必ず false になること
- comp(a,b) が true かつ comp(b,c) が true のとき、comp(a,c) が必ず true になること
最終的に、ここの記述に行きつき、腑に落ちた次第。
なんでもVisualStudioはデバッグビルド時にこのルールをチェックして、違反する場合にアサート飛ばしてくれるんだそうな。VisualStudioさまさま。