オーダーについて解説しる！

Order I Say! « C++Next

strict weak orderingって何よというお話。

アキラさんが興味を示していたので読んでみた。幸い、Not Foundではなかった。しかし、イケメンのアキラさんとは違い、私には数学が分からない。でも、英語はちょっとだけ分かる。そこで、ここでは、高校までの数学の概念と、英語力だけで、無理やり理解したふりをして解説する。

規格では、ソートや連想コンテナへの要求として、strict weak orderingというのがあるが、これは一体どういう意味だろうか。

調べていくと、"a strict weak ordering is a strict partial order in which incomparability is transitive."とある。なるほど、ちょっとルールが追加されたstrict partial orderなんだな。、しかしstrict partial orderとは、一体何だろう。

strict total orderというものがあるが、これは複雑すぎる（ルールが多すぎる）。strict partial orderは簡単だが（ルールが少ないが）、あまりにも貧弱すぎる。strict weak orderは、その中間に位置する。

と、ここまでが、orderの数学的定義へ言及することを避けての解説である。数学が理解出来ない者としては、orderの数学的な定義の解説は理解できない。しかし、なぜstrict weak orderingであることが、そんなに重要なのか。なぜわざわざ、規格のいたる所で、strict weak orderingであることを明記しなければならないのか。

それは、アルゴリズム的に、ある場面で、比較を省略することができるからだ。高校までの数学で考える。x, y, zという整数に対して、不等号、<、を適用した場合。x < y, y < z, ということを知っていれば、x < z, は比較しなくても分かるということは、高校までの数学を知るものならば、当然のことである。つまりこれは、もし、このルールが保証されているならば、x < y, y < zであることを知っておけば、x < z, という比較は、省略できるということを意味する。strict weak orderingは、これを数学的に保証するのである。

原文では、二つの問題が出されている。数学が得意であれば、挑戦してみるのも面白いかもしれない。

私は数学が壊滅的にできないので、細かい部分を知りたい数学オタクは、こんな解説より原文を読んで欲しい。結局、私の興味は、なぜ、規格でstrict weak orderingと明記することが重要なのかということにあるのだから。