PartialOrdering,StrictWeakOrdering,TotalOrdering,应用程序的主要区别是什么

Question

由于无反射性和传递性,operator <始终满足部分排序的定义.严格弱序的定义更严格,总排序的定义更严格.

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

前三个公理,无反射性,反对称性和传递性,是部分排序的定义; 严格弱排序的定义需要等价的传递性.总排序是满足更强条件的顺序:等价必须与平等相同.

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

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

2. 严格的弱订货和总订货怎么样？

3.STL在排序算法中需要严格的弱排序,为什么不是部分排序或总排序？ 对于这个问题,我通过证明规则满足三个公理来阅读一些证明有效比较规则的教科书:无反射性,反对称性,传递性,这是部分排序的定义,文件指的是运算符<总是满足这个定义,所以为什么我们不能只使用部分排序比较对象,或者等效地使用运算符

Answer 1

Igo*_*nik 5

部分订购基本上是<=.如果同时a <= b和b <= a那么你就可以说a是相当于b.但它也有可能是既不a <= b也不b <= a-这两个元素是无法比拟的.因此,您不能std::sort在具有部分排序关系的集合上强加总订单(如需要) - 充其量您可以进行拓扑排序.你也不能得出等价关系 - 同样,可能存在无法比拟的元素.

严格的弱排序就像<.它不允许同时使用a < b和b < a,如果两者都a < b没有b < a,你只能发音a和b等效.

总排序只是严格的弱排序,其中两个元素是等价的,当且仅当它们相等时(除了小于谓词之外,如果你有一个相等比较谓词,并且没有使用这两个元素的C++标准库算法,这只是有意义的)与此同时,这个问题在这方面基本上没有实际意义.

下面是一个打破等价传递性规则的（看似合理的）关系示例： `bool noticeouslyLessThan(double a, double b) {return a < b-epsilon; }` 这个想法是将两个“足够接近”的浮点值声明为等效的。问题出在边缘：可能“a”与“b”足够接近，“b”与“c”足够接近，但“a”与“c”不够接近。这可能会破坏“std::sort”使用的算法。 (3认同)
我的字面意思不是小于.我的意思是,"行为类似于少于或等于较少或等于"(例如,偏序关系是反身的,严格的弱有序关系是无反射的).大于具有与小于的所有相同的属性,并且同样适合. (2认同)

归档时间：	12 年，1 月前
查看次数：	1198 次
最近记录：	12 年，1 月前