C++: Strict Weak Ordering

想讲讲C++ STL中各种算法都用到的一个概念，Strict Weak Ordering。

举个例子，来说明为什么写C++要知道这个东西。

假如你定义了一个类型MyType，而且这个类型是可比的（comparable，定义了<这个operator）:

struct MyType {
    int first;
    int second;    MyType(int f,int s):first(f),second(s){}
    MyType(){
        ....
    }
    bool operator < (const MyType &b){
        return a.first < b.first;
    }
};

现在一个 vector里装着很多这种类型的对象，你想对这个 vector 排序：

vector<MyType>  vec { obj1,obj2,obj3 };
std::sort(vec.begin(),vec.end());

之所以能用std::sort()来对任意类型排序，而不用给std::sort()传递规则，是因为std::sort()是默认采用<这个operator来排序的。

现在问题来了，只有<这个operator怎么知道两个对象是否相等？

简单来说就是，假如!(a<b) && !(b<a)，那么a==b

但是，假如我没有为MyType定义<这个 operator，我想在std::sort()的时候用 lambda来给出比较规则，那么，怎么才能知道两个对象是否相等? 这样：

std::sort(vec.begin(),vec.end(), [](MyType a, MyType b){ a.second < b.second ; });

可以看到，这个 lambda就等同于上面的operator< ()。

可以看到，这里，只需要给std::sort()一个比较规则即可。这个比较规则不一定是要<，可以是>或者其他：

std::sort(vec.begin(),vec.end(),{ a.second > b.first; });

（术语上，这个比较规则就是离散数学里面讲的Relation，用来描述两个object之间的关系）

但是，并不是任何比较规则都是可以的，这个比较规则一定要满足 Strict Weak Ordering的要求。比如，你不能用<=或>=号这个比较规则：

std::sort(vec.begin(),vec.end(),[](MyType a, MyType b){ a.first <= b.first; });

为什么？因为，如果a确实等于b，当你用!(a<=b)&&!(b<=a)去看两者相不相等，会发现返回的是 false。这当然是不对的

（有人问我为什么不直接用==去比较a和b是否相等，因为我们并没有给 MyType 定义==这个 operator）

那么，什么是Strict Weak Ordering呢？

下面是由WikiPedia上抄来的定义。

A strict weak ordering is a binary relation < on a set S that is a strict partial order (a transitive relation that is irreflexive, or equivalently,^[5]that is asymmetric) in which the relation "neither a < b nor b < a" is transitive.^[1]Therefore, a strict weak ordering has the following properties:

• For all x in S, it is not the case that x < x (irreflexivity).
• For all x, y in S, if x < y then it is not the case that y < x (asymmetry).
• For all x, y, z in S, if x < y and y < z then x < z (transitivity).
• For all x, y, z in S, if x is incomparable with y (neither x < y nor y < x hold), and y is incomparable with z, then x is incomparable with z (transitivity of incomparability).

This list of properties is somewhat redundant, asasymmetryfollows readily fromirreflexivityandtransitivity.

注意定义中所说的relation就是我们上面说的“比较规则”（数学上叫relation。relation是一个更加广的概念，不一定是比较规则）

而且，定义中用到的<并不是小学数学中的小于号，它只是代表一个relation（当然，普通的小于号 < 是最简单的满足Strict Weak Ordering的relation了）。

容易看出，小于等于号<=和大于等于号>=并不满足irreflexivity的要求。

可以看到，我们上面说的相等，就是这个定义里说的 "the relation 'neither a<b nor b<a'"，也就是，incomparable

这里的一个比较细微的地方是，“相等”的概念。在这里，"相等"(equivelant )并不意味着a和b是一样( identical ) 的东西，而只是!(a<b) && !(b<a)(incomparable)（注意<只是一个relation，并不一定是我们常说的小于号）

也就是说，“相等”在这里已经变成了!(a<b) && !(b<a)，而不是==号（而且我们根本就没有定义==这个operator，你根本没法用这个运算符来看a和b是否相等）

比如，假如：

MyType a(1,100);

MyType b(1,99);

那么，在std::sort(vec.begin(),vec.end());中，std::sort()去判断a和b是否“相等”的时候，会把a和b当做是相等的，即使a和b这个两个对象的 second 并不一样(因此a,b也不一样)。这是因为我们用了<这个运算符，而<这个运算符并不去比较 second，只关心first。

在数学上，这个“相等”的其实就是一个equivalent relation(看下文定义)

明白这个概念很重要，不然，看文档会比较痛苦（我在看Matthew H. Austern那本《Generic Programming and the STL》的时候，就是没能明白这个概念，糊涂了很久......）

我想讲的已经讲完，最后，来捋一捋逻辑。

### Ｃ++ 语言中为什么要默认采用 < 来作为std::sort()和其他与排序相关的函数的比较符号呢?

第一，必须定义一个默认的比较运算符，否则每次排序都要提供一个运算子，太麻烦了。

### 为什么不用其他运算符?

可以用其他运算符号，比如，可以用 > 。只要这个运算符能满足strict weak ordering即可。

### 为什么一定要满足strict weak ordering?

因为，满足strict weak ordering的运算符能够表达其他所有的逻辑运算符（logical operator）：

• <(a, b) : (a < b)
• <=(a, b): !(b < a)
• ==(a, b): !(a < b) && !(b < a)
• !=(a, b) : (a < b) || (b < a)

• (a, b) : (b < a)

• =(a, b): !(a < b)

但是，不满足strict weak ordering的就不一行。比如上文中所讲的 <= 号和 >= 号，当a==b时，!(a<=b)&&!(b<=a)并不为真。

再次重申，这里所说的”运算符“，“相等”，“小于”等词汇，都应该与C++中的范型编程联系起来。

也就是说，“运算符”这个词，不仅仅是 < 号，> 号这些简单的数学运算符，同时应该包括C++中的functor，lamda等。说白了，能用来比较两个元素，并且返回true或false的东西。< 号和 > 号这些是最简单的的”运算符“了，但是你也可以写一个一千行的函数，接受两个参数，然后返回一个布尔值。

同样道理，”小于“，”大于“这些词汇也不单是 < 和 > 。

假如你定义了一个 < ，那么

• a > b， 即 b < a
• a == b，即 !(a < b) && !(b < a)
• ...

也就是，用一个运算符表示其他所有的运算符。

最后在这里补一补离散数学的坑。关于 relation 和 ordering。

关于reflexive，symmetry，transitivity这些术语的一个总结（摘自这里）：

Given a function f(which models a binary relation) over a domainD, and a, b∈ D:

• Reflexivity: f (a, a) is true.
• Asymmetry: For a ≠ b, if f(a, b) is true, f(b,a) is false
• Anti-symmetry: If f(a, b) and f(b, a) are both true iff a ≡ b
• Transitivity: If f(a, b) and f(b, c) are true, then f(a, c) is true
• Incomparability: Neither f(a, b) nor f(b, a) is true
• Transitivity of incomparability: If a and b are incomparable, and so are b and c, then a and c are incomparable.

首先是最常见的Partial Ordering 和 poset:

A (non-strict) *partial order R is a binary relation "≤" over a set S which is reflexive, antisymmetric, and transitive

***

( A set S together with a patial order R is called a patially ordered set, or poset, and is denoted by (S,R))

这个定义里面说的是non-strict partial ordering。最常见的non-strict partial ordering就是数学上的小于等于号 ≤ 了。这也是为什么定义中都使用 ≤ 来表示npn-strict partial odering。注意，如果没有特殊提示，一般人说的partial ordering 就是指 non-strict partial ordering。

如果要加上 strict的限制，则是：

A relation is astrictorder on a set if it is

1. Irreflexive: does not hold for any .

2. Asymmetric: if , then does not hold.

3. Transitive: and implies .

Note that transitivity and irreflexivity combined imply asymmetric.

最常见的strict partial order是 < 号了，这也是为什么常用 < 来表示strict partial ordering。

（non-strict partial ordering 和 strict partial ordering的定义从这里和这里都可以找到）

为了弄清楚 non-strict 和 strict 一词的含义，仔细看上面两个定义。

两者的区别在于，non-strict ordering 是 irreflexive 和 asymmetric的，而 strict ordering 是 reflexive和asymmetric的。

irreflexive 和 reflexive 是相反的概念，这个很好理解。但是 anti-symmetric 和 asymmetric 的概念却貌似没有交集，这个怎么理解？

首先看symmetric、asymmetric以及anti-symmetric的定义：

symmetric:

A binary relationRon a set Sis symmetric when :

∀a,b∈S(aRb→bRa)

asymmetric:

A binary relationR on a set Sis asymmetric when :

∀a,b∈S(aRb→¬(bRa))

anti-symmetric:

A binary relationRon a set Sis antisymmetric if there is no pair of distinct elements of Seach of which is related byR to the other; i.e. :

∀a,b∈S((aRb∧bRa)→a=b)

The difference between asymmetric and anti-symmetric is that：

Antisymmetric means that the only way for both$\mathrm{aRbandbRato\; hold\; is\; ifa=b.\; It\; can\; be\; reflexive,\; but\; it\; can\text{'}t\; be\; symmetric\; for\; two\; distinct\; elements.\; Think\; <=.Asymmetric\; is\; the\; same\; except\; it\; also\; can\text{'}t\; be\; reflexive.\; An\; asymmetric\; relation\; never\; has\; bothaRb\; andbRa,\; even\; ifa=b.\; Think<.So\; an\; asymmetric\; relation\; is\; just\; one\; that\; is\; both\; antisymmetric\; and\; irreflexive.}$

也就是说，anti-symmetric + irreflexive -> aymmetric

所以，strict partial ordering 中的 asymmetric可以换成 anti-symmetric + irreflexive（虽然数学上这样的替换是不正确的，但是这好理解一点），也就是说，non-strict 和 strict 的差别就在于 reflexive 和 irreflexive了。这样就好理解了。

多说一句，

Every(non-strict)partial order induces a strict partial order

Similarly, every strict partial order induces a (non-strict)partial order

加减一个条件就可以在两者之间转换了。

Total ordering:

If(S,<) is a poset and every two elements of S are comparable, S is called a totally ordered or linearly ordered set, and < is called a total order or a linear order. A totally ordered set is also called a chain.

这里，total 的概念怎么理解呢？这样：

A strict order is total if, for any , either , , or

也就是说，total 要求一个绝对的可比关系。

The notion of incomparable:

Let< denote the relation in setS. The elements a and b of a poset (S,<) are called comparable if either a<b or b<a. When a andb are elements of S such thatneither a<b nor b<a, a and b are called incomparable.

Well order:

(S,<) is a well-ordered set if it is a poset such that < is a total ordering and every nonempty subset of S has a least element

那么，可以看出，C++中的 strict weak ordering 和 strict partial ordering想比，就是差一个weak了，这个weak，就差在 transitivity of incomparablity上（对比一下定义看看）。

值得注意的是，transitivity of incomparablity 并不是说这个集合一定是 incomparable 的，只是说，如果有incomparable的元素，那么这些incomparable的关系是可传递的(transitive)

Reference:

• https://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings
• https://en.wikipedia.org/wiki/Partially_ordered_set
• https://en.wikipedia.org/wiki/Total_order
• http://sidd-reddy.blogspot.com/2011/01/i-was-going-over-c-stl-when-i-noticed.html
• http://math.stackexchange.com/questions/585396/what-is-meaning-of-strict-weak-ordering-in-laymans-term
• http://www.sgi.com/tech/stl/StrictWeakOrdering.html
• https://www.quora.com/What-is-strict-weak-ordering-in-C++-sort
• https://en.wikipedia.org/wiki/Equivalence_relation
• http://stackoverflow.com/questions/979759/operator-and-strict-weak-ordering
• http://stackoverflow.com/questions/14938163/total-weak-partial-orderings-complete-definition
• http://math.stackexchange.com/questions/778164/is-an-anti-symmetric-and-asymmetric-relation-the-same-are-irreflexive-and-anti
• http://mathworld.wolfram.com/StrictOrder.html

Last Edit: 2016-07-31, 12:03

:)

原文链接: https://www.cnblogs.com/walkerlala/p/5561339.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍