C++ strict weak ordering

C++

はじめに

標準テンプレートライブラリの多くのアルゴリズムが strict weak ordering という規則に従った演算子を要求します
strict weak ordering とは何でしょうか

本来は数学の用語ですが、C++ の文脈での strict weak ordering というのは、当たり前の operator< が満たしているべき条件を細かく言っただけのことです
operator< を自分で書くときは、この規則に従った実装にせよ
operator< を使うときは、この規則に従っている前提で使ってよい
ということです

特に説明することもないので、ここでは用語の紹介だけしておきます

その前に：同値律/同値関係(equivalence relation)

こちらは当たり前の operator== の性質です

  • 反射律(reflexivity/reflective relation)

        operator==( a, a )

    は常に true


  • 対称律(symmetry/symmetric relation)

        operator==( a, b )

    ならば

        operator==( b, a )

    も true


  • 推移律(transitivity/transitive relation)

        operator==( a, b ) && operator==( b, c )

    ならば

        operator==( a, c )

    は true


operator== を書くときは、この規則に従った実装にせよ
operator== を使うときは、この規則に従っている前提で使ってよい
ということです

operator== はある２つの要素が同じかどうかということは判定できますが、同じでないときにその順番を決めることはできません
要素の順序を決めたいときには operator< が必要です

その前に：全順序(total ordering)

全要素の順序が一意に決定可能で、等価性についても一意に決定できるが、要求水準が高い

  • 反対称律(antisymmetry/asymmetric relation)

    operator<=( a, b ) && operator<=( b, a )

    ならば a と b は等価である


  • 推移律(transitivity/transitive relation)

    operator<=( a, b )&& operator<=( b, c )

    ならば

    operator<=( a, c )

    は true


  • 全順序律(totality/comparability)

    operator<=( a, b ) || operator<=( b, a )

    は常に true


  • 反射律(reflexivity/reflective relation)

    operator<=( a, a )

    は常に true


その前に：半順序(partial ordering)

要求水準は低いが、順序を決定できない要素の組み合わせがないことは保証しない

  • 反対称律(antisymmetry/asymmetric relation)

    operator<=( a, b ) && operator<=( b, a )

    ならば a と b は等価である


  • 推移律(transitivity/transitive relation)

    operator<=( a, b ) && operator<=( b, c )

    ならば

    operator<=( a, c )

    は true


  • 反射律(reflexivity/reflective relation)

    operator<=( a, a )

    は常に true


strict weak ordering(狭義弱順序？)

全要素の順序が一意に決定可能で、等価性についても一意に決定できるが、全順序ほど要求水準は高くない

標準では次のように言っています：

N1905
25 Algorithms library
25.3 Sorting and related operations
1 All the operations in 25.3 have two versions:
one that takes a function object of type Compare
and one that uses an operator<.
2 Compare is used as a function object which returns true if the first argument is less than the second, and false otherwise.
Compare comp is used throughout for algorithms assuming an ordering relation.
It is assumed that comp will not apply any non-constant function through the dereferenced iterator.
3 For all algorithms that take Compare, there is a version that uses operator< instead.
That is, comp (*i, *j) != false defaults to *i < *j != false.
For algorithms other than those described in 25.3.3 to work correctly, comp has to induce a strict weak ordering on the values.
4 The term strict refers to the requirement of an irreflexive relation (!comp (x, x) for all x), and the term weak to requirements that are not as strong as those for a total ordering, but stronger than those for a partial ordering.
If we define equiv(a, b) as !comp (a, b) && !comp (b, a), then the requirements are that comp and equiv both be transitive relations:
- comp (a, b) && comp (b, c) implies comp (a, c)
- equiv(a, b) && equiv(b, c) implies equiv(a, c)
[ Note:
Under these conditions, it can be shown that
- equiv is an equivalence relation
- comp induces a well-defined relation on the equivalence classes determined by equiv
- The induced relation is a strict total ordering.
-end note ]
5 A sequence is sorted with respect to a comparator comp if for any iterator i pointing to the sequence and any nonnegative integer n such that i + n is a valid iterator pointing to an element of the sequence, comp (*(i + n), *i) == false.
6 A sequence [start, finish) is partitioned with respect to an expression f(e) if there exists an integer n such that for all 0 <= i < distance(start, finish), f(*(begin + i)) is true if and only if i < n.
7 In the descriptions of the functions that deal with ordering relationships we frequently use a notion of equivalence to describe concepts such as stability.
The equivalence to which we refer is not necessarily an operator==, but an equivalence relation induced by the strict weak ordering.
That is, two elements a and b are considered equivalent if and only if !(a < b) && !(b < a).
  • strict という語は、任意の要素 x について comp( x, x ) が常に false を返すという非反射関係(irreflexive relation) を要求することによる
  • weak という語はこれらの要求が、全順序(total ordering) ほど強い要求ではないが、半順序(partial ordering) ほど弱い要求でもないことによる
  • equiv( a, b ) とは !comp( a, b ) && !comp( b, a ) であるとの定義から、推移関係(transitive relations) も要求される：
    • comp( a, b ) && comp( b, c ) ならば comp( a, c ) も true
    • equiv( a, b ) && equiv( b, c ) ならば equiv( a, c ) も true
  • !comp( a, b ) && !comp( b, a ) が true のときのみ２つの要素は等価であるとみなされる
  • comp から equiv を導くことができるので operator== は必ずしも必要ではない

はじめにも言った通り、当たり前の operator< の特徴ですね

以前 ホワイトボードプログラミング で言っていた等値とか等価とかいうのは、実はこの文脈での話なのでした