厳密で弱い順序（Strict Weak Order）

C++ STL 数学

STLにおいて，順序を定める述語を指定するときにはすべからく「厳密で弱い順序（Strict Weak Order）」という概念が出てきます．この概念がいかにSTLで重要な位置を占めているかは次の事実を見てもらえば一目瞭然です．

  • std::setで要素の比較に使われる述語（boolを返すファンクタ）には厳密で弱い順序であることが要求される
  • std::mapでkeyの比較に使われる述語には厳密で弱い順序であることが要求される
  • std::sortに渡される述語には厳密で弱い順序であることが要求される
  • ・・・e.t.c.

いかにこの概念が重要かということは理解できましたでしょうか？この概念の重要性は，STLを扱っている書籍では必ずといっていいほど議論されているので，そちらもぜひ参考にしてください（e.x."Effective STL"第21項．後で分かりますが第19項も深く関連します）．
ここではさらに一歩踏み込んで「厳密で弱い順序とは何か？」，そして「厳密で弱い順序が何故ここまで重要視されるのか？」を議論します．
ある集合の要素を一列に並べるときに「大きい順」とか「小さい順」とかいうふうな基準を決めますが，この基準のことを普通は「順序」と呼びます．しかしここでは「順序」という言葉を数学的・抽象的な意味，即ち，ある集合の任意の2つの要素の間にある関係が有る（true）か無い(false)か，という意味で使います．この意味で，順序は2つの値を引数に取ってbool値を返す関数の形式を取ります．STLで使われる「順序」もこの形式を取っているのはご存知の通りです．

int a = 1;
int b = 2;
assert( less()(a, b) ); // STLがデフォルトで使う「順序」であるless

順序には様々な種類があり，厳密で弱い順序はこの種類の中の一つです．まず先に代表的な順序の種類である「全順序（Total Order）」を説明した方が良いと思われるので，そちらからやります．
全順序とは以下の性質を満たしている順序です（より正確には「厳密な（strict）」全順序の定義）．ここで，f(x, y)は2つの要素xとyの順序を定義する関数とします．

  • （非）反射性：f(x, x)は常にfalseである
  • （非）対称性：f(x, y)がtrueならば!f(y, x)もtrueである
  • 推移性：f(x, y)がtrueでありf(y, z)がtrueであるならf(x, z)はtrueである
  • f(x, y)がfalseでありf(y, x)もfalseであるならば，xとyは等しい(equal)

よく分かりませんので具体的な全順序の例としてlessに登場してもらって，条件の意味を順に追っていきます．

  • （非）反射性
int i = 3;
assert( !less()(i, i) );

要するに同じ値に対して常にfalseを返す，というのが一つ目の条件「（非）反射性」です．
この条件に関して非常に重要な指摘として，less_equalやgreater_equalはこの条件を満たさないということです．これらの「順序」は同じ値に対してtrueを返してしまいます．このような「順序」はSTLにおける比較の条件として絶対に使えません．この制約を破ると何が起きるか具体的に知りたい方は，例えば以下のコードを実行してみてください．

set > s;
s.insert(1); // 1を挿入
s.insert(1); // すでに1はsに入っているからこの挿入では何も起こらないはずだ！
copy(s.begin(), s.end(), ostream_iterator(cout, "\n"); // ありゃりゃ？

この現象の解説の詳細については"Effective STL"をどうぞ．

  • （非）対称性
int i;
int j;
...
if( less()(i, j) ){
  assert( !less()(j, i) );
}

これは「順序」という言葉から直感的に分かる条件です．具体的には例えば「aはbより小さい」なら「bはaより小さくない」と言えるのは当然でしょう，ということです．

  • 推移性
int i;
int j;
int k;
...
if( less()(i, j) && less()(j, k) ){
  assert( !less()(i, k) );
}

これまた「順序」という言葉から直感的に理解できる条件です．言葉で言えば「aはbより小さい」かつ「bはcより小さい」なら「aはcより小さい」ということです．

  • 最後の条件
int i, j;
...
if( !less()(i, j) && !less()(j, i) ){
  assert( i == j );
}

これも分かりやすい条件です．「iがjよりも小さいことはない」かつ「jがiよりも小さいことはない」なら「iとjは同じ値である」ということは，通常の順序なら当然でしょう．そもそも，「全」順序という言葉は異なる2つの要素x, yの間全てにf(x, y)またはf(y, x)が成り立つことから来ている名前で，そのどちらも成り立たないということは，そもそもxとyは同じ要素だったのだ，ということが言えるわけです．
さて，これを踏まえた上で，次に厳密で弱い順序の定義を見てみます．
厳密で弱い順序では全順序の最後の条件だけが緩められています（緩められているのかどうかパッと見て分からないですが）．

  • （非）反射性：f(x, x)は常にfalseである
  • （非）対称性：xとyが（equalityの意味で）等しくないとき，f(x, y)がtrueならば!f(y, x)もtrueである
  • 推移性：f(x, y)がtrueでありf(y, z)がtrueであるならf(x, z)はtrueである
  • equivalenceに対する推移性：xとyがequivalentでありyとzもequivalentであるとき，xとzもequivalentである

ここで初めてequivalenceという言葉が出てきます．xとyがequivalentであるというのは，f(x, y)がfalseでありかつf(y, x)がfalseである，ということです．
具体的な例で見てみます．厳密で弱い順序として一番有名なのが「大文字小文字を無視した文字列の大小比較」です．この文字列比較の実装は簡単なので省略して，この順序（文字列として小さいほうが前にきたらtrue）を定義した述語をci_lessとします．

assert( ci_less("ABC", "acb") );

さて問題は"ABC"と"aBc"にこのci_lessで順序をつけるとどうなるか，です．当然，ci_less("ABC", "aBc")もci_less("aBc", "ABC")も両方falseを返します．
ここで，全順序の定義の最後の条件を思い出してください．全順序の定義では上のように双方の比較がfalseだった場合，その値は等しい（equal）ことが必要でした．ところがci_lessによる順序付けができないこの"ABC"と"aBc"は値が等しいとはいえません．要するにci_lessは，異なる値である"ABC"と"aBc"の大小を決定できないのです．
この，ci_lessにおける"ABC"と"aBc"の比較のように，値として等しくないにもかかわらず，双方の順序関係が定義できないような比較が存在します．つまり，値は違うけれどもある順序付けによっては「等しいとみなされる」値の関係が存在するわけです．これが"Equivalence"です．例えば上の例で言えば，ci_lessにおいては"ABC"と"aBc"はequivalentである，というふうに言うことができます．
さて，もう一度厳密で弱い順序の定義に戻ります．

  • （非）反射性：f(x, x)は常にfalseである
  • （非）対称性：xとyが等しくないとき，f(x, y)がtrueならば!f(y, x)もtrueである
  • 推移性：f(x, y)がtrueでありf(y, z)がtrueであるならf(x, z)はtrueである
  • equivalenceに対する推移性：xとyがequivalentでありyとzもequivalentであるとき，xとzもequivalentである

実はさっき例に出したci_lessは4番目の条件を満たします．具体的に言うと，ci_lessでは"abc"と"abC"の順序を決められません．同時に，"abC"と"aBc"の順序も決められません．このとき，"abc"と"aBc"の順序も決められない，というのが最後の条件です．
一見，「だからどうした？」と思えるようなこの最後の条件こそ，STLにおいて決定的な意味を持つことが後で分かります．
ここで2点だけ．全順序の最後の条件は，f(x, y)でもf(y, x)でもないとき，xとyは値が等しい（equal），となっていましたが，このequalityというのはequivalenceよりもキツイ条件です．というのも，f(x, x)もf(x, x)も（←x同士の順番を入れ替えたつもり）falseを返すので，値が等しい（equal）なら当然equivalentでもある，ということになります．また，equalityはxとyが値が等しくyとzも値が等しいならxとzも値が等しいという推移性（厳密で弱い順序の最後の条件）を満たすので，結局，全順序は厳密で弱い順序の条件がキツイ形である，ということが分かります．
もう一つ．equivalenceの関係は，数学の言葉で言うところの「同値関係（equivalent relation）」になっています．equivalenceの関係が反射律と対称律を満たしているのはすぐに確認できます．推移律は最後の条件そのものですね．equivalenceという言葉は恐らくここから来ているのでしょう．
＃追記：上の言い方は数学的に非常にまずいか？「無関係」の関係が同値関係になるような半順序が「厳密で弱い順序」だというべき．