[结贴]STL当中弱序的概念，和偏序/全序有什么区别和联系?

centos_71

STL里面的关联容器，元素的存储说是按照严格弱序来排列的。我查找了维基百科对于弱序这个概念本身并没有给出特别清晰的解释
我们学过的离散数学里面，只学过"偏序"和"全序"的概念。这个弱序到底是什么含义，和偏序的区别/联系是什么?

求大侠的解释。

windoze

回复 1# centos_71

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.

也就是说“strict weak ordering”满足以下几个条件

1、对于给定集合S，其中任意两个元素a和b都存在ordering，这一点和“partial ordering”不同，后者不能保证任意两个元素之间都存在ordering，所以才叫“partial”
2、transitive指如果a<b且b<c，则a<c
3、irreflexive是指a<a一定为假
4、asymmetric指若a<b，则b<a为假
5、最后一句说的是“(not a<b) and (not b<a)”有传递性，也就是说，如果“(not a<b) and (not b<a)”且“(not b<c) and (not c<b)”，则“(not a<c) and (not c<a)”

STL里的less定义就需要满足以上条件

centos_71

windoze 发表于 2015-01-17 13:35
回复 1# centos_71

谢谢，你的解释很专业，就是第(5)点有点不太明白:

为什么要用两个not之间加个and? 这个条件逻辑上等价于 ( a<b or b<a )------之前你在第(1)点和第(4)点不是说了吗，必然有a<b成立，或者b<a成立(两个不能同时成立)。如果是要说明这种关系可传递的，那么第(2)点也已经说了啊。

我的理解是，第(5)点是不是想表达，(1)(2)(4)所构成的等价关系(等价关系需要对称，自反，可传递)，也是可传递的。这是更高一层的可传递，对吗?

windoze

回复 3# centos_71

“(not a<b) and (not b<a)”咋能等价于“( a<b or b<a )”？明明是等价于“not ( a<b or b<a )”，话说你的数理逻辑要补课…………

(a<b)和(b<a)为啥一定要有一个成立？以自然数为例，难道a=b不行么？这不就是前面说的“(not a<b) and (not b<a)”的情况么？

weak ordering没有定义“=”，所以用了一种比较麻烦的方式。

centos_71

windoze 发表于 2015-01-17 20:17
回复 3# centos_71

“(not a

因为没有定义相等，所以定义了一个比较麻烦的等价! 这回我理解清楚了!