7

【SGI官方文档】

由于非自反性和传递性,operator< 总是满足偏序的定义。严格弱序的定义更加严格,全序的定义更加严格。

而且我还阅读了文档中严格弱排序的定义:StrictWeakOrdering

前三个公理,非自反性、反对称性和传递性,是偏序的定义;等价的传递性是严格弱排序的定义所要求的。全序是满足更严格条件的排序:等价必须与等价相同。

我不太确定这些定义。一些主要问题:

1.偏序是否隐含地定义了等价?

2.严格弱排序全排序呢?

3.STL在排序算法中要求严格的弱排序,为什么不是偏序或全序? 对于这个问题,我已经阅读了一些教科书,这些教科书通过证明规则满足三个公理来证明有效的比较规则:非自反性、反对称性、传递性,这是偏序的定义,并且文档中提到 operator< 总是满足这个定义,所以为什么我们不能只使用偏序比较对象,或者等效地,使用运算符

4

1 回答 1

9

偏序本质上是<=. 如果两者都a <= bb <= a那么您可能会说这a相当于b. 但也有可能两者都不a <= bb <= a——这两个元素是无法比拟的。结果,您不能对std::sort具有部分排序关系的集合强加一个总顺序(就像需要的那样) - 充其量您可以进行拓扑排序。您也无法推导出等价关系——同样,可能存在无法比较的元素。

严格的弱排序就像<. 它不允许同时拥有a < band b < a,如果两者都不是a < bor b < a,你可以只发音ab等价。

总排序只是严格的弱排序,其中两个元素当且仅当它们相等时才等效(仅当除了小于谓词之外还有相等比较谓词时才有意义,并且没有同时使用两者的 C++ 标准库算法同时,因此在这种情况下,这个问题在很大程度上是没有实际意义的)。

于 2013-09-13T13:21:42.787 回答