[SGI官方文件]
由于不可反身性和传递性,运算符
我还阅读了文档中严格弱排序的定义:严格弱排序
前三个公理,不可反身性、反对称性和传递性, 是部分排序的定义;等价的传递性 是严格弱排序的定义所要求的。总计 排序是满足更强大条件的排序:等价 必须与平等相同。
我不太确定这些定义。一些主要问题:
偏排序隐式定义等价 1.Is?
2.严格弱排序和总排序呢?
3.STL在排序算法中要求严格的弱排序,为什么不是部分排序或总排序?对于这个问题,我读过一些教科书,通过证明规则满足三个公理来证明比较规则是有效的:不可反性、反对称性、传递性(这是偏序的定义),文档引用该运算符<总是满足这个定义,那么为什么我们不能只使用部分排序来比较对象,或者等效地使用运算符>
部分排序本质上是<=
。如果两者都a <= b
和b <= a
那么你可以说a
等同于b
。但也有可能既不a <= b
也不b <= a
——这两个元素是无可比拟的。因此,您不能对具有偏序关系的集合强加总序(就像std::sort
需要的那样)——充其量您可以进行拓扑排序。你也不能推导出等价关系——同样,可能存在无法比拟的元素。
严格的弱排序就像<
.它不允许同时使用a < b
和b < a
,如果既不a < b
也不b < a
,你可以只发音a
和b
等价。
总排序只是严格的弱排序,其中两个元素是等价的,当且仅当它们相等时(这只有在除了小于谓词之外还有一个相等比较谓词时才有意义,并且没有C++标准库算法同时使用两者,因此这个问题在这种情况下基本上没有意义)。